Priority register: Application-defined replacement orderings for ad hoc reconciliation

Reconciliation of replicated data objects is tedious and error-prone in eventually consistent systems. Syntactic reconciliation techniques use serializability or causality as the basis for conflict-detection and resolution. These techniques are fast and efficient and the resolutions can be directly managed at the database side. However, for use cases where conflict resolution demands knowledge of the application semantics, domain-specific semantic reconciliation is required. Semantic reconciliation techniques often involve maintaining all possible values and perform the resolution via domain-specific knowledge at the client side. This involves additional cost in terms of network bandwidth and latency, and considerable complexity. In this paper, we discuss the motivation and design of a novel data type called priority register that implements a domain-specific conflict detection and resolution scheme directly at the database side, while leaving open the option of additional reconciliation at the application level. Our approach uses the notion of an application-defined replacement ordering and we show that a data type parameterized by such an order can provide an efficient solution for applications that demand domain-specific conflict resolution. We also describe the proof-of-concept implementation of the priority register inside the Cassandra distributed storage system.