Der clevere Rsync-Algorithmus findet Gemeinsamkeiten in Dateien auf verschiedenen Rechnern

Bandbreite sparen klingt altmodisch, ist es aber nicht - selbst bei einer flotten 16-GBit-Anbindung dauert es Stunden, mehrere DVD-Images einer Linux-Distribution zu laden. Besonders ärgerlich ist, wenn man die Betaversion schon hat und sich zur Final nur kleine Teile geändert haben. Wo es für Quelltexte vielleicht ein Patch gibt, wird\'s bei Binärdaten schon schwieriger. Binärpatch-Utilitys wie BS-Diff [4] und X-Delta [5] haben sich nicht durchgesetzt.

Patches leiden sowieso unter einer Einschränkung: Sie geben den Unterschied zweier vorgegebener Versionen wider [6]. Wer mehrere Zwischenstände überspringen will oder eine Kopie verändert, wird damit nicht glücklich, er braucht viele Patches oder scheitert anderweitig. Rsync [1] nimmt ihm die Sucherei ab und gleicht gar Files einander an, die nicht voneinander abstammen.

Rsync verteilt die Aufgabe sehr geschickt zwischen Client und Server. Der Empfänger einer Datei teilt dem Sender mit, was er schon hat, der Sender vergleicht das mit seinem Original-Datenbestand und schickt alles rüber, was dem Empfänger fehlt.

Nicht lange quatschen

Die Kunst bei dieser Aktion ist, den Kommunikationsaufwand klein zu halten. Beide Beteiligten wissen vorab nicht, wo sich Unterschiede und Gemeinsamkeiten befinden. Mag sein, dass die Files identisch sind oder dass einer Version Daten anhängen, die die andere Seite nicht hat. Häufig auch stimmen in Binärdaten zwar große Teile überein, aber die liegen an unterschiedlichen Positionen in der Datei. Einen Algorithmus, ein Protokoll und ein Tool, das die Gemeinsamkeiten nutzt, hat der Samba-Pionier Andrew Tridgell entwickelt und in seiner Doktorarbeit beschrieben (siehe Kasten "Entwicklungsziele").

Den genauen Ablauf bei der Kommunikation fasst [3] zusammen - und weist auch darauf hin, dass das Rsync-Protokoll keineswegs zu den Glanzstücken gehört. Der Algorithmus dafür umso mehr: Der Rsync-Empfänger teilt die vorhandene Zieldatei in Blöcke fester Größe auf (je nach Dateigröße), berechnet für jeden Block eine Prüfsumme und teilt nur diese Summen dem Sender mit. Der durchforstet seine eigene Datei und ermittelt, welchen der Blöcke er ebenfalls hat. Am Ende sendet er alle fehlenden Stellen zusammen mit Hinweisen, welche Blöcke der Empfänger an welcher Stelle wiederverwenden muss.

Die Aufgabe "Finde einen Abschnitt in der Datei, der eine bestimmte Prüfsumme besitzt, egal an welcher Stelle dieser Abschnitt liegt" bedeutet auf den ersten Blick sehr viel Rechnerei. Ein wenig geschickter Ansatz wäre es, sich für jede mögliche Position alle Bytes zu holen, um die komplette Summe zu berechnen (Abbildung 1).

Abbildung 1: Vorgegeben ist die Prüfsumme über einen Block fester Größe, unbekannt aber die Stelle des Blocks innerhalb einer Datei. Die langsamste Lösung berechnet die komplette Prüfsumme an jeder möglichen Stelle erneut.

Schiebung

Andrew Tridgell fand eine Möglichkeit, nicht jedes Mal die komplette Prüfsumme zu ermitteln. Bei jeder neuen Position ändern sich schließlich nur zwei Stellen im Block: einer fällt hinten raus und vorne kommt ein neuer dazu. Tridgells Algorithmus braucht für die Berechnung der nächsten Stelle nur den herausfallenden und den neu hinzukommenden Wert (Abbildung 2).

Abbildung 2: Die optimierte Version bestimmt ab der zweiten Position nicht mehr die komplette Summe, sondern zieht nur den Wert vor dem Block ab und rechnet den neu hinzugekommenen Wert ein.

Der 32-Bit-Wert seiner Prüfsumme teilt sich in zwei Hälften: 16 Bit berechnen sich als simple Modulo-216-Summe. Beim Verschieben addiert Rsync den neuen und subtrahiert den herausfallenden Wert. Dummerweise ergibt das gleiche Prüfsummen, wenn zwei Werte ihre Reihenfolge tauschen. Um auch die Byteposition mit einzubeziehen, multipliziert der zweite Teil des Prüfsummenwerts jede Stelle des Blocks mit ihrer Nummer innerhalb des Blocks, wobei die Nummern von hinten beginnen.

Beim zweiten Teil ist die Verschiebung auch verblüffend einfach berechenbar: Den wegfallenden Wert subtrahieren und danach das Ergebnis der ersten Hälfte addieren. In ihr stecken die addierten Werte aller Bytepositionen, womit sich der Faktor jeder Stelle um eins erhöht. Mit gerade mal zwei Additionen, zwei Subtraktionen und einer Multiplikation (für den wegfallenden Wert der zweiten Hälfte) sind beide Teile berechnet (Abbildung 3). Beim Vereinen fallen noch ein Shift- und ein Additionsschritt an.

Abbildung 3: Dieser Algorithmus berechnet die rollierende Rsync-Prüfsumme. Er besteht aus zwei Teilen: Einer einfachen und einer gewichteten Summe, bei der jede Stelle mit einem Faktor multipliziert ist. Von einer Prüfsumme ausgehend berechnet sich die verschobene Summe wie rechts unten dargestellt.