rsync algoritem

Am, to je samo na dolg način razloženo delovanje zaprte hash tabele, ki kolizije razrešuje tako da na isto mesto daje seznam vseh elementov z istim hashom (to je najpogostejša implementacija hash tabele v jezikih, vključno z Javo, C# in ostalimi runtimi).

Kaj ti dopovejo je to - client dobi seznam 32bit checksumov blokov fajla, ki jih shrani v hash tabelo. Hash tabela uporablja 16-bitne hashe, kar pomeni da se pri vstavljanju teh checksumov v tabelo zračuna ta 16-bitni hash.
Potem pa preprosto računaš rolling checksum čez fajl in preverjaš, če v tej hash tabeli tisti checksum obstaja. Če obstaja, potem pomeni da imaš isti kos fajla kot na drugam koncu (torej ni treba pošilat), če je null, potem ni bilo ujemanja pri checksumu.

V Javi bi recimo algoritem v tisti točki zgledal nekak takole:

HashMap<short, Checksum> checksums = new HashMap(prejetiChecksumi);

Checksum rollingChecksum;
while(rollingChecksum = getNextRollingChecksum())
{
   if (checksums.contains(rollingChecksum))
   {
      System.out.println("Najden zadetek!");
   }
}

To je to :)

Okej, stvari so tak:

1.) Ker hash table slika 32-bitne checksume v 16-bit številke, je verjetnost kolizije precej velika, zato mora po tistem ko najde match še preveriti na seznamu elementov na tistem mestu, če so dejansko enaki (to spada k implementaciji tabele). To je 2nd level check s tistega dokumenta. Ker je seznam sortiran se lahko iskanje konča takoj ko najde 16-bitni hash, ki je isti a predstavlja drugi checksum.

2.) rsync uporablja en svoj checksum algoritem, ki je zelo hiter, a ima večjo verjetnost kolizije ("weak checksum"). Vsak najdeni match je zato potrebno preveriti še s "pravim" checksum algoritmom ("strong checksum", CPU precej zahtevnejši), da se izloči možnost napačnega matcha. To je 3rd level check.

Potem si pa mislim da narobe razumel zadnji odstavek - ne pošlje se blok za katerega si zračunal rolling checksum, ampak se pošlje del datoteke od zadnjega matcha pa do začetka trenutnega matcha ("from last match to current file offset") - torej pošlje se kos fajla med dvema matchoma, ki ni mel matchev.