rsync fragte den Empfänger, was er schon hatte. Die langsame Leitung atmete auf.

Zusammenfassung

• Im ursprünglichen Bericht von Tridgell und Mackerras zerlegt der Empfänger seine vorhandene Datei in Blöcke und sendet je zwei Prüfsummen. Der Sender sucht diese Blöcke an jeder möglichen Stelle der neuen Datei und übermittelt Verweise sowie nicht passende Daten.
• Die praktische Beschreibung des rsync-Projekts nennt die Gegenleistung: die Suche kostet den Sender CPU-Zeit, der Neuaufbau den Empfänger Festplattenarbeit. Eine Prüfsumme über die fertige Datei kontrolliert das Ergebnis.

Der Empfänger schickte erst einmal sein Inventar

Eine große Datei liegt in zwei ähnlichen Fassungen auf getrennten Maschinen. Vorne wurde ein Absatz eingefügt, vieles dahinter ist gleich geblieben. Eine einfache Kopie verschickt die bekannten Daten erneut. Auch ein Vergleich an denselben Blockpositionen hilft wenig: Durch die Einfügung haben die unveränderten Stellen andere Adressen. Der Originalbericht setzte die beiden Rechner an eine Verbindung mit wenig Bandbreite und hoher Verzögerung. Keiner besitzt beide vollständigen Dateien, um vor dem Transfer bequem einen lokalen Unterschied zu berechnen.

Der erste nützliche Schritt gehört deshalb der Zielmaschine. Sie teilt ihre vorhandene Datei in aufeinanderfolgende Blöcke, berechnet für jeden eine schnelle rollende und eine stärkere Prüfsumme und schickt diese Kurzbeschreibung zur Quelle. In der historischen Ausführung war die schwache Summe 32 Bit lang und die starke beruhte auf MD4. Das sind Angaben zum damaligen Entwurf, keine pauschale Beschreibung heutiger Versionen. Der Sender erfährt, welche Stücke am anderen Ende liegen, ohne die alte Datei selbst zu empfangen.

Nun durchsucht er die gewünschte Fassung. Bei einem Treffer schickt er die Kennung eines Blocks, den das Ziel bereits hat. Für einen Bereich ohne Treffer sendet er die echten neuen Bytes. Der Empfänger baut aus beiden Sorten Material die fertige Datei. Prüfsummen und Blockkennungen gehen ebenfalls über die Leitung; die Parole „nur Unterschiede übertragen“ verkürzt diese Verkehrsrechnung. Bei ähnlichen Dateien und einem langsamen Link kann der Zusatz dennoch viel kleiner sein als eine vollständige Zweitlieferung.

Die Prüfsumme musste um je ein Byte rutschen

Wer nur alte und neue Blöcke an gleicher Position prüft, verliert nach einer Einfügung fast alle Übereinstimmungen. Der Sender muss einen alten Block an jeder Byteposition der neuen Fassung finden können. Für jede Position die gesamte Blocksumme neu zu berechnen, wäre teuer.

Der Abschnitt über die rollende Prüfsumme nutzt den vorherigen Wert: beim Verschieben des Fensters wird das auslaufende Byte entfernt und das nächste einbezogen. Erst ein Treffer dieser billigen Prüfung löst die stärkere aus. Im Suchabschnitt kommt eine Hash-Tabelle als weitere Auswahlstufe hinzu. So findet der Rechner auch Text, der an eine andere Stelle gerückt ist. Seine Rechenarbeit erspart dem schmalen Kabel die Fahrt mit demselben Buch.

Der Bericht beschreibt zudem das Überlappen von Suche und Übertragung. Bei einem Treffer können bislang nicht passende Bytes und der Blockindex sofort gesendet werden, während die Suche weiterläuft. Das ursprüngliche Verfahren braucht nur einen Hin- und Rückweg für die Blockliste und die Bauanweisung. Bei großer Verzögerung ist auch eine gesparte Gesprächsrunde wertvoll.

Die eingesparten Bytes landeten auf einer anderen Rechnung

Die Implementierungsbeschreibung des Projekts trennt Generator, Sender und Empfänger. Der Generator am Ziel prüft, welche Dateien aktualisiert werden müssen, und sendet die Summen der vorhandenen Basisdatei. Der Sender sucht nach Übereinstimmungen; er verbraucht viel CPU. Der Empfänger liest möglicherweise verstreute Stücke der alten Datei und schreibt zugleich eine temporäre neue; das fordert den Datenträger. Am Ende wird die Prüfsumme der vollständig gebauten Datei verglichen. Ein falsches Ergebnis wird verworfen.

Auch das kompakte Protokoll hatte seinen Preis. Die eigene Dokumentation beschreibt einen durchgehenden Bytestrom, dessen Bedeutung stark von Zusammenhang und Protokollversion abhängt. Klare Nachrichtengrenzen sind selten. Das spart Übertragungsaufwand, erschwert aber Dokumentation, Fehlersuche und Erweiterung. Die Entscheidung zugunsten der knappen Leitung band die Wartung an einen anspruchsvollen Datenstrom.

Nicht jede Aktualisierung lohnt sich. Eine Zielmaschine ohne ähnliche alte Datei kann kaum Blöcke wiederverwenden. An einer schnellen Leitung mit langsamem Datenträger kosten Prüfen und Lesen unter Umständen mehr als das Kopieren. Der Originalbericht nannte ähnliche Dateien über eine langsame Verbindung als den besten Fall. Der Algorithmus verschob Kosten dorthin, wo Kapazität vorhanden war; er beseitigte sie nicht.

Die Reihenfolge der Auskunft war die Erfindung

Die Quelle kennt die fertige Datei. Das Ziel kennt seine verfügbaren alten Stücke. rsync ließ zuerst das Ziel diese Stücke beschreiben, dann die Quelle Verweise und neue Bytes auswählen. Beide vollständigen Dateien mussten dafür nicht an einem Ort liegen. Die Rücksendung war eine Bauanweisung: diesen Block nehmen, dann jenen und dazwischen die neuen Daten einsetzen.

Der Empfänger musste noch bauen und prüfen. Die historische Leistung bestand nicht in einem kostenlosen Zauberwort namens „Differenzen“. Rechenzeit, Festplattenzugriffe und Protokollkomplexität kauften knappe Netzkapazität zurück. Der Spediteur musste nicht die ganze Bibliothek erneut bringen; beide Lager mussten ihre Regale genauer sortieren.