Algorytm rsync

Algorytm rsync – algorytm będący podstawą działania protokołu i narzędzia transferu plików rsync. Algorytm znajduje różnice między dwoma plikami umieszczonymi na dwóch różnych komputerach (czy bardziej ogólnie: urządzeniach) połączonych łączem o niskiej przepustowości; różnice dane są jako lista poleceń, które opisują w jaki sposób przekształcić jeden plik w drugi, bez konieczności transmisji wszystkich danych.

Założenia algorytmu są następujące: jeden plik jest w pełni dostępny na pierwszym komputerze (A), natomiast informacje o drugim pliku, znajdującym się na innym komputerze (B), są częściowe.

Pierwszy etap algorytmu wykonywany jest na komputerze B. Synchronizowany plik jest dzielony na bloki o rozmiarze kilkuset bajtów-kilku kilobajtów. Dla każdego z nich liczone są wartości dwóch funkcji mieszających – słabej 32-bitowej (ozn. $H$) oraz mocniejszej, wymagającej więcej obliczeń, 128-bitowej MD5 (w sumie 20 bajtów na blok). Te dane są transmitowane do komputera A.

Natomiast na komputerze A, w pliku wyszukiwane są wszystkie wystąpienia bloków, przy czym ich pozycje mogą być dowolne; jeśli plik ma rozmiar $n$ bajtów, a blok $k$ bajtów, to sprawdzane jest $n-k$ bloków. Dla każdego rozpatrywanego bloku oblicza się wartość słabej 32-bitowej funkcji skrótu. Jeśli taki skrót został przesłany z komputera B, obliczany jest skrót MD5 i dopiero na jego podstawie określa się numer bloku.

Kluczowa dla wydajności wyszukiwania jest 32-bitowa funkcja mieszająca, o takiej własności, że znając $a_{1},$ $H(a_{1},\dots ,a_{k})$ i $a_{k+1},$ można łatwo wyliczyć $H(a_{2},\dots ,a_{k+1}).$ Oprócz tego funkcja używana w praktycznej implementacji powoduje relatywnie małą ilość kolizji.

Ostatecznie na podstawie pozycji bloków wysyłane są albo dane niewystępujące na komputerze B, albo numery znalezionych bloków, co pozwala na odtworzenie wszystkich informacji z komputera A.

Zobacz też

• algorytm Karpa-Rabina
• diff
• najdłuższy wspólny podciąg

Linki zewnętrzne

• Opis algorytmu w języku angielskim