Algorytm rsync
Algorytm rsync stanowi fundament działania zarówno protokołu, jak i narzędzia do transferu plików rsync. Jego głównym zadaniem jest identyfikacja różnic pomiędzy dwoma plikami znajdującymi się na różnych komputerach (lub ogólnie: urządzeniach) połączonych łączem o niskiej przepustowości. Różnice te są przedstawiane jako lista poleceń, które wskazują, jak przekształcić jeden plik w drugi, eliminując potrzebę przesyłania wszystkich danych.
Podstawowe założenia algorytmu są takie, że jeden plik jest całkowicie dostępny na pierwszym komputerze (A), natomiast informacje dotyczące drugiego pliku, znajdującego się na innym komputerze (B), są niepełne.
Pierwszy krok algorytmu realizowany jest na komputerze B. Synchronizowany plik dzielony jest na bloki o wielkości od kilkuset bajtów do kilku kilobajtów. Dla każdego bloku obliczane są wartości dwóch funkcji mieszających – słabej 32-bitowej (oznaczanej jako H) oraz mocniejszej, 128-bitowej MD5 (łączna wielkość to 20 bajtów na blok). Te informacje są następnie przesyłane do komputera A.
Na komputerze A następuje wyszukiwanie wszystkich wystąpień bloków w pliku, przy czym ich lokalizacja może być dowolna. Jeśli plik ma rozmiar n bajtów, a blok k bajtów, sprawdzane są n – k bloków. Dla każdego z rozpatrywanych bloków obliczana jest wartość 32-bitowej funkcji skrótu. Jeśli skrót ten został przesłany z komputera B, obliczany jest skrót MD5, na podstawie którego określa się numer bloku.
Wydajność wyszukiwania jest kluczowa i opiera się na 32-bitowej funkcji mieszającej, która ma tę właściwość, że znając a1 oraz H(a1, \ldots, ak), można łatwo obliczyć H(a2, \ldots, ak+1) przy znajomości ak+1. Oprócz tego, funkcja wykorzystywana w praktycznej implementacji generuje relatywnie niewiele kolizji.
Na końcu, na podstawie pozycji bloków, przesyłane są albo dane, które nie występują na komputerze B, albo numery odnalezionych bloków, co umożliwia rekonstrukcję wszystkich informacji z komputera A.
Zobacz też
- algorytm Karpa-Rabina
- diff
- najdłuższy wspólny podciąg
