Ares - So 13.03.11 10:06
Titel: Algrothmus für die Daten-Synchronisation gesucht

---

Hallo!

Es sollen Datensätze (Dateien, Einträge in einer DB, was auch immer) zwischen zwei verschiedenen Systemen synchronisiert werden. Ich bin schon länger auf der Suche nach einem guten Algroithmus hierfür, bislang leider ohne Erfolgt.

Zum Thema "Synchronisation" gibt es zwar jede Menge Literatur, aber 90% aller Fundstellen beziehen sich auf die Synchronisation von Prozessen und Threads und den Zugriff auf Kritische Daten/Abschnitte. Das ist natürlich ein ganz anderes Thema... Die restlichen 10% sind Fundstellen zu fertigen Programmen die Daten synchronisieren können.

Ich bin jedoch auf der Suche nach einem ganz allgemeinen Algorithmus und es wundert mich sehr, dass dieser scheinbar so schwer zu finden ist. Klar, das Thema Synchronisation ist keine triviale Aufgabe. Heute kann aber jedes Telefon seine Daten mit einem PC synchronisieren und es gibt zig 1000 Programme um Ordner und Dateien zu synchronisieren. Es muss daher doch irgendeinen allgemeinen Algorithmus für dieses Problem geben.

Zu allen anderen allgemeinen Problemen der Informatik gibt es doch auch "Standardlösungen" (Stichwort Suche, Sortierung, Datenstrukturen, etc.). Kennt also jemand die richtigen Stichworte nach denen ich suchen könnte? Ich suche quasi für Synchronisation das, was Quicksort für die Sortierung ist.

Besten Dank
Ares

Th69 - So 13.03.11 11:06

---

Hallo,

einer der häufig verwendeten Tools ist ja rsync [http://de.wikipedia.org/wiki/rsync]. Und dafür wurde eben der sog. RSync-Algorithmus erfunden (schau dir einfach mal die Links unten auf der Wiki-Seite an, z.B. http://rsync.samba.org/tech_report/tech_report.html ).
Als darauf aufbauendes Verfahren gibt es auch noch rdiff-backup [http://www.nongnu.org/rdiff-backup] - ich weiß aber nicht, ob es über die Implementation genug Infos gibt.

Da rsync (pro Datei) jedoch nur in eine Richtung synchronisiert, mußt du bei Änderungen auf beiden Seiten evtl. auch noch einen Merge [http://de.wikipedia.org/wiki/Merge]-Algorithmus einsetzen (wie in auch Versionsverwaltungssysteme einsetzen). CVS-Merge nutzt(e?) z.B. den diff3-Algorithmus ( http://www.cis.upenn.edu/~bcpierce/papers/diff3-short.pdf )
Und bei Mercurial kann man das Merge-Programm sogar festlegen, s. http://mercurial.selenic.com/wiki/MergeProgram (evtl. findest du zu den einzelnen Programmen Erklärungen zu den eingesetzten Algorithmen).

Ich hoffe, du hast nun einige Suchbegriffe zum Weitersuchen...