Analysis of reconciliation protocols for divergent replicas

Abstract

Das Ziel von Replikation ist, die Erreichbarkeit und/oder Leistung in einem Verteilten System zu erhöhen. Optimistische Replikationstechniken erlauben Schreiboperationen in verschiedenen Partitionen im Falle einer Teilung des Netzwerkes. Daher können sich Repliken unterscheiden und somit Update-Konflikte auftreten. Wenn die Partitionen wieder zusammengefügt werden, muss eventuell die Konsistenz unter den Repliken wieder hergestellt werden. Dieser Prozess wird Reconciliation genannt. Das Ziel dieser Arbeit ist die Implementierung und Evaluierung solcher Reconciliation Protokolle unter Verwendung von .NET Technologien.<br />Es wurde eine umfangreiche empirische Evaluierung der vorgestellten Ansätze vorgenommen. Einige haben sich als brauchbar herausgestellt, während andere aus gewissen Gründen eher unbrauchbar sind. Die zwei vorgestellten Ansätze zur Erkennung von Replika-Konflikten (Customized Version Vectors und Hash History) sind sich sehr ähnlich, aber wenn Coincidental Equalities ausgenützt werden können, ist der Hash History Ansatz im Vorteil. Andernfalls ist der Customized Version Vectors Ansatz zu empfehlen. Die vorgestellten Ansätze zur Konfliktlösung können grundsätzlich in zwei Gruppen aufgeteilt werden. Eine Gruppe berücksichtigt etwaige Constraints in keiner Weise und ist etwas schneller, während der Ansatz, der Constraints berücksichtigt, zu weniger verworfenen Operationen führt.<br />Zusätzlich wurden noch zwei Constraint Consistency Re-Establishment Ansätze, Replay und Partition Logs (berücksichtigt die Semantik der Anwendung), untersucht. Verglichen mit einem Stepwise Rollback bieten sie eine sehr schlechte Leistung, dafür sorgen sie aber für weniger verworfene Operationen.<br />

The objective of replication is to enhance availability and/or performance in distributed systems. Optimistic replication techniques allow updates in different partitions in case of network splits. Hence, replicas might diverge and update conflicts could occur. Eventually, when the partitions are merged, consistency among replicas has to be re-established. This process is known as reconciliation. The objective of this thesis was to implement and evaluate reconciliation protocols using .NET technologies.<br />A comprehensive empirical evaluation has been performed on the featured approaches. Some of them have proved to be very practical and others have proved to be impractical for some reasons. The two replica conflict detection approaches (customized version vectors and hash history) are similar, but if coincidental equalities can be exploited, the hash history is in advantage, otherwise the customized version vectors can be recommended. The featured conflict resolution strategies basically can be divided into two groups. Those which do not consider constraints are faster and the one which considers data constraints leads to lesser rejected operations. Additionally the replay approach and a partition logs approach (considers application semantics), which are two constraint consistency re-establishment approaches, have been examined.<br />They perform bad compared with the stepwise rollback, though they may reject lesser operations.