Rsync Algorithm

Rsync는 원격지에 있는 파일과 디렉토리를 동기화하기 위해 사용하는 알고리즘이다. 두 머신이 낮은 대역폭과 대기 시간이 긴 양방향 통신 링크로 연결되어 있다고 가정하자. 알고리즘은 소스 파일의 일부가 대상 파일의 일부와 동일한 부분을 식별하고, 일치하지 않는 부분만 전송한다. 이 알고리즘은 두 파일이 같은 머신에 존재하지 않아도 효과적으로 일치하지 않는 부분을 계산한다. 이 알고리즘은 파일이 유사할 때 가장 잘 동작하지만, 파일이 상당히 다른 경우에도 정확하고 합리적이며 효율적으로 동작한다.

The Ploblem

A와 B라는 두 파일이 있고, B를 A와 동일하게 업데이트 하고 싶다고 가정하자. 가장 확실한 방법은 A를 B에 복사하는 것이다. 이 두 파일이 느린 네트워크 링크로 연결되어 있다고 가정하자. 그렇다면 A의 크기가 커질수록 복사하는 속도가 느려진다. 속도를 높이기 위해 A를 전송하기 전에 압축하는 방법도 있겠지만, 일반적으로 2~4의 계수배 정도만 증가한다.

이제 A와 B가 매우 유사하고 둘 다 동일한 원본 파일에서 파생되었다고 가정하자. 실제 속도를 높이려면 이런 유사성을 활용해야 한다. 일반적인 방법은 링크를 통해 A와 B의 차이점만 전송한 다음 이 차이점 목록을 사용해 파일을 재구성하는 것이다. 문제는 두 파일 간의 차이점 집합을 만드는 일반적인 방법이 두 파일을 모두 읽을 수 있어야 한다는 것이다. 따라서 링크의 한쪽 끝에서 두 파일을 미리 사용할 수 있어야 한다. 동일한 노드에서 두 파일을 모두 사용할 수 없는 경우 위의 방법을 사용할 수 없다. 이 문제가 rsync가 해결하고자 하는 바이다.

Rsync 알고리즘은 소스 파일의 어떤 부분이 기존 대상 파일의 어떤 부분과 일치하는지 효율적으로 계산한다. 이러한 부분은 링크를 통해 전송할 필요가 없이, 대상 파일의 일부에 대한 참조만 있으면 된다. 이러한 방식으로 일치하지 않는 소스 파일의 일부만 그대로 전송하면 된다. 그러면 수신자는 기존 대상 파일의 일부에 대한 참조와 축약된 데이터를 사용해 소스 파일의 복사본을 재구성할 수 있다.

이런 데이터 전송과정에서는 다양한 일반적 압축 알고리즘을 사용해 속도를 더 향상시킬 수 있다.

The rsync algorithm

느린 네트워크로 연결된 두 대의 컴퓨터 $\alpha$ 와 $\beta$가 있다고 가정하자. $\alpha$ 는 파일 A를 소유하고 $\beta$는 파일 B를 소유하고 있다. 여기서 A와 B는 유사한 파일이다. Rsync 알고리즘은 아래와 같이 동작한다.

1. $\beta$는 파일 B를 S바이트 크기의 겹치지 않는 고정 크기 블록으로 분할한다. 마지막 블록은 S바이트 보다 적을 수 있다.
2. 각 블록에 대해 $\beta$는 weak rolling 32-bit checksum와 strong 128-bit MD4 checksum의 계산을 수행한다.
3. $\beta$는 이 checksum을 $\alpha$로 보낸다.
4. $\alpha$는 A에서 B가 보낸 weak rolling 32-bit checksum과 동일한 S바이트 블록을 찾는다. 이 과정은 straight forward하게 single path로 진행할 수 있다. 그 뒤 일치하는 블록에서 strong 128-bit MD4 checksum과 일치하는 블록을 찾는다.
5. $\alpha$는 A의 복사본을 구성하기 위해 필요한 블록 데이터를 B에 전송한다. 이 데이터는 일치하지 않는 섹션에 대해서만 전송하게 된다. 최종적으로 $\beta$가 A의 복사본을 구성할 수 있지만, B에서 찾을 수 없는 A의 일부분만을 링크로 전송하게 되기 때문에 링크 지연의 영향을 최소화 한다.

이 알고리즘의 가장 중요한 핵심은 rolling checksum을 사용한 다중 블록 검색 메커니즘으로 이를 통해 오프셋 체크섬 검색을 빠르게 진행하는데 있다. 여기서 사용되는 rolling checksum은 단순성과 속도를 위해 적절한 modular 계수를 설정 해야한다. Rolling checksum (RH 알고리즘과 유사)을 통해서 일치하는 hash block을 발견한 뒤엔, 해당 블록에서 128-bit MD4 checksum의 값이 일치하는지를 계산한다. 이를 통해 rolling hash algorithm에서 발생하는 확률을 매우 낮출 수 있게 된다. 일치하는 항목이 발생하면 이 전까지 일치했던 데이터의 오프셋부터 일치하는 블록의 시작 오프셋 까지의 데이터를 전송하게 된다. 일치하는 항목이 발생하지 않으면 다음 블록에 대한 계산을 동일하게 일치하는 항목이 발생할 때 까지 진행한다.

Pipelining

지금까지는 원격지 시스템에서 하나의 파일 복사본을 구성하는 프로세스를 살펴봤다. 다중 파일의 복사본을 구성할 때는 파이프라이닝을 통해 대기 시간의 이점을 얻을 수 있다. 프로세스 중 하나는 체크섬을 생성하고 전송하는 반면, 다른 프로세스는 파일에서 차이점 정보를 수신하고 파일을 재구성하는 방식으로 동작하게 된다.

Results

약 24MB에서 진행한 rsync 알고리즘의 동작 결과는 아래와 같다. 많은 block들 중에서도 rolling hash checksum 으로 걸러낼 수 있는 false alarms는 일치 수의 $1/1000$ 미만으로 상당히 낮은 수치를 보여준다. 또한 300바이트로 분할된 블록에서는 매우 작은 부분의 데이터만 전송된 것을 확인할 수 있다.

block size	matches	tag hits	false alarms	data	written	read
300	64247	3817434	948	5312200	5629158	1632284
500	46989	620013	64	1091900	1283906	979384
700	33255	571970	22	1307800	1444346	699564
900	25686	525058	24	1469500	1575438	544124
1100	20848	496844	21	1654500	1740838	445204