[Algorithm] What is RFP Algorithm on deduplication?

1. RFP 란 ?

Rabin Finger Printing 알고리즘은 긴 문자열을 해싱하는 데에 사용하는 대표적인 알고리즘이다.

이 알고리즘은 일반적인 Chunking 알고리즘이지만 최신기술은 아니다. 그래서 Chunking 알고리즘에서 수행능력이 높은 면은 아니지만 가장 기본적인 알고리즘 중 하나이다. 

FIgure 1. Formula of RFP

d 의 경우 fingerprint 값의 가능한 범위를 나타낸다. 이 값은 257로 설정하는 것이 좋은데 그 이유는 만약 256으로 할경우 값의 충돌이 나타날 수 있기 때문이다.

q의 경우 값이 클 수록 fingerprint value가 겹치지 않기에 이것 또한 값이 클 수록 좋다.

m의 경우 Window size로 가장 작은 chunk size를 나타낸다.

 

2. RFP on deduplication

먼저 m=4이기 때문에 첫번째 RFP를 구하면 공식을 이용하여 12가 된다. 이때 mask와 AND operation을 적용할 경우 0이 아니기 때문에 chunk가 만들어질 수 없다.

다음 RFP를 계산하면 0이 되기 때문에 mask 와 AND operation을 적용할 경우 0이 되기 때문에 3까지가 anchor point가 되어 첫번째 chunk가 생성된다.

이러한 식으로 계속해서 chunk를 만들어가면 RFP 알고리즘을 적용한 variable size의 chunk를 만들 수 있다.

 

3. What if the input contains many runs of zeros?

만약 file이 0이 많이 구성된 파일일 경우 무수한 chunk를 생성할 거기에 chunk size를 variable하게 할 경우 비효율 적일 수 있다. 그래서 오히려 fixed size로 하는 것이 더 효율적일 수 있다. 만약 chunk 숫자를 줄이고 싶을 경우 0이 아닌 다른 숫자가 나올 때 anchor point를 만들어 준다면 chunk 숫자를 조금 더 효율적으로 만들 수 도 있다.