Syncpal: a simple and iterative reconciliation algorithm for file synchronizers

Shekow, Marius Alwin; Jarke, Matthias; Prinz, Wolfgang; Gross, Tom

doi:10.18154/RWTH-2019-11267

Syncpal: a simple and iterative reconciliation algorithm for file synchronizers = Syncpal: Ein schlichter, iterativer Abgleichungsalgorithmus für File Synchronizer

Shekow, Marius Alwin^RWTH*

2019 & 2020

Verantwortlichkeitsangabevorgelegt von Marius Alwin Shekow (M.Sc.)

ImpressumAachen 2019

Umfang1 Online-Ressource (xi, 243 Seiten) : Illustrationen, Diagramme

Dissertation, RWTH Aachen University, 2019

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University 2020

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Jarke, Matthias (Thesis advisor)^RWTH* ; Prinz, Wolfgang (Thesis advisor)^RWTH* ; Gross, Tom (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2019-11-22

Online
DOI: 10.18154/RWTH-2019-11267
URL: http://publications.rwth-aachen.de/record/773759/files/773759.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
conflict detection (frei) ; file synchronizer (frei) ; file system (frei) ; heterogeneous synchronization (frei) ; optimistic replication (frei) ; synchronizer (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
File Synchronizer sind Tools, die Kollaborationsszenarien und Daten-Management über mehrere Geräte hinweg vereinfachen sollen. Sie replizieren Dateisysteme, z. B. von Cloud-Speichern auf Festplatten. Dateisystem-Konvergenz wird erreicht, indem nur Änderungen übertragen werden. In der Praxis haben sich zustandsbasierte File Synchronizer wie Dropbox oder ähnliche Produkte durchgesetzt. Sie erkennen Operationen via Differenzbildung aus einem zuvor persistierten und dem aktuellen Zustand zweier Dateisystem-Replikate und erreichen dadurch deren bidirektionale Synchronisation. Benutzer sind darauf angewiesen, dass die Synchronisation fehlerfrei abläuft. Marktübliche File Synchronizer erschweren dies jedoch, sodass Benutzer Synchronisationsfehler oft selbst erkennen und unter großem Zeitaufwand beheben müssen und manche Fehler lange Zeit unerkannt bleiben. Dadurch entstehen im Kooperationsprozess kostenintensive Iterationen, die es in Wissenschaft und Wirtschaft zu vermeiden gilt. Diese Arbeit identifiziert drei zentrale Defizite der zustandsbasierten Dateisynchronisation. Erstens bedingt die Heterogenität verschiedener Dateisysteme, dass File Synchronizer inkompatible Eigenschaften oft nicht erkennen und behandeln. Zweitens muss ein Synchronizer Konflikte erkennen und lösen, die durch den isolierten Zugriff mehrerer Benutzer auf Dateisysteme entstehen. Drittens sind konfliktfreie Operationen, die via Differenzbildung der Zustände erkannt wurden, nicht unmittelbar für die Übertragung geeignet. Hier ist die Reihenfolge der Operationen unbekannt und diese wurden evtl. konsolidiert, sodass wichtige Zwischenoperationen fehlen. Dieses Problem betrifft insbesondere Dateisysteme, die Verschiebe-Operationen unterstützen, die den Überordner eines Objekts ändern. Ziel dieser Arbeit ist es, diese Defizite durch einen neuartigen, verbesserten File Synchronizer zu beheben. Zum besseren Verständnis der Heterogenität analysiert diese Arbeit bestehende wissenschaftliche Arbeiten und reale Dateisystem-Implementierungen wie NTFS und deren Kompatibilität. Der Autor identifiziert sechs Dateisystem-Fähigkeiten, definiert ein formales Dateisystem-Modell F, das zu bestehenden Definitionen größtenteils kompatibel ist, und schlägt mehrere Alternativen für den Umgang mit inkompatiblen Eigenschaften vor. Zur Konflikt-Identifizierung wird eine Vorbedingungsanalyse der Operationen von F durchgeführt. Das Lösen von Konflikten ist diffizil, da der geeignete Ansatz vom Kontext abhängt. Ein Großteil wissenschaftlicher Arbeiten löst Konflikte willkürlich und ohne Begründung der konkreten Entscheidungen auf. Zur Findung eines reflektierten Konfliktlösungsansatzes hat der Autor ein vierstufiges Framework entwickelt, das eine informelle Definition von Konsistenzeigenschaften iterativ zu einer Menge von formal definierten, detaillierten Konfliktauflösungsschritten verfeinert. Neben F und dem obigen Konfliktlösungsansatz ist der Hauptbeitrag dieser Arbeit der iterative Algorithmus Syncpal, der die Abweichungen zweier Dateisysteme synchronisiert und die genannten Defizite löst. Konflikte werden nacheinander behandelt, ohne dass sich die Lösung eines Konflikts negativ auf andere auswirkt. Wenn möglich werden Konflikte vermieden. Anschließend werden eine valide Übertragungsreihenfolge der verbleibenden, konfliktfreien Operationen ermittelt und eventuelle zyklische Abhängigkeiten aufgelöst. Dieser iterative Ansatz reduziert die Gesamtkomplexität und die Wahrscheinlichkeit von Programmierfehlern. Die technische Evaluation der Syncpal-Implementierung umfasst eine Komplexitätsanalyse, automatisierte Tests sowie einen Vergleich mit fünf weiteren, etablierten File Synchronizern. Die Ergebnisse zeigen, dass Syncpal die Dateisystem-Heterogenität besser bewältigt und Änderungen aus langen Offline-Phasen korrekt synchronisiert. Andere Implementierungen scheitern hier häufig, was bis hin zu Datenverlust führen kann. Die Verwendung der Syncpal-Implementierung durch 30 Benutzer über einen Zeitraum von über 18 Monaten liefert für weitere Forschungsfragen wertvolle Einblicke bzgl. Nutzerverhalten und Anforderungen aus der Praxis.

File synchronizers are tools with the goal to facilitate collaboration scenarios and data management across multiple devices. They replicate the file system, e.g. from a cloud storage to a device disk, achieving convergence by only transmitting detected changes. A popular variant available in a plethora of widely adopted products are state-based file synchronizers such as Dropbox. They detect operations by computing the difference between a previously persisted state and the respective current state, performing a bi-directional synchronization of two replicas. While users rely on synchronization to run without errors, bugs in industrial synchronizers make this difficult. Users often have to detect and fix synchronization errors themselves, and some errors remain undetected for a long time. This results in cost-intensive iterations in cooperation processes, which should be avoided in academia and industry. This work identifies three core challenges of state-based file synchronization. The first challenge is the heterogeneity of different file systems, which requires the file synchronizer to detect and handle incompatible capabilities. Second, a synchronizer needs to detect and resolve conflicting operations that result from a group of users working on their replica in isolation. Third, non-conflicting operations computed from state differencing are not immediately suitable for propagation. The operation order is not available and operations may be affected by consolidation, such that important intermediate operations are missing. This problem most notably affects file systems that support the move operation which changes an object's parent folder. The goal of this work is to design and analyze an algorithm and develop an implementation of a file synchronizer that solves these challenges. To address heterogeneity we analyze existing real-world implementations (such as the NTFS file system) and their compatibility issues, and also examine related academic works. We identify six file system capabilities relevant to file synchronizers, formally define a file system model F that is in large parts compatible to the various existing definitions and suggest several alternatives for handling incompatible differences. To detect conflicts we perform a precondition analysis of the operations of F. Resolving conflicts is an open problem where the right approach depends on the context. Our related work analysis finds that most academic works present arbitrary resolution methods that lack a rationale for their decisions. To determine a reflected conflict resolution approach we design a four-step framework which starts with an informal definition of consistency properties and iteratively refines it to a set of formal and detailed steps for resolving concrete conflicts. Apart from F and a conflict resolution approach the main contribution of this work is Syncpal, an iterative algorithm that reconciles two divergent file systems, solving all of the above challenges. It first handles conflicts, one at a time, such that resolving one conflict does not negatively affect others. Whenever possible, conflicts are avoided. It then finds a valid propagation order for the remaining non-conflicting operations, breaking cyclic dependencies if necessary. The iterative nature of Syncpal reduces the overall complexity and the probability of bugs. The technical evaluation of our implementation of Syncpal includes its complexity analysis, automated testing and a comparison with five industrial-grade file synchronizers. We find that our algorithm improves the handling of file system heterogeneity and synchronizes changes from long offline periods correctly, where other implementations fail and may even cause data loss. Our implementation has been in operation by 30 users over a period of over 18 months, providing valuable insights for further research regarding usage patterns and practical requirements.

OpenAccess:
PDF
(additional files)