Towards a General Database Management System of Conflict-Free Replicated Relations

Abstract

This project aims to explore creating a relational database of Conflict-Free Replicated Relations (CRR) that is generally applicable for most user applications. We aim to achieve generality by using SQLite because it is a commonly used embedded Database Management System that comes default in all Android or iOS devices. The implementation challenge is making CRR using only SQL.

We propose a two-layer database design using Causal Lenght-set for rows in the relations and Last Write Wins-registers for attributes in the rows. Achieving this means implementing methods to propagate data between layers, storing necessary metadata that automatically upholds CRDT functionality. Merges are performed entirely in SQLite. CL-set functionality decides the state of each row, and LWW-registers determine the values of each attribute. In merges, the SQL script resolves reference integrity constraints.

We base experiments on data and client-centric consistency and availability as latency. The experiments highlight the strong eventual consistency across two merge methods. Full merges are when the entire system merges periodically, which grants the system complete consistency on demand. Partial merges simulate that even though nodes are not always available, the system can uphold a consistency threshold. Availability is a trade-off compared to a local datastore when measured as transaction latency. However, the system's scalability outperforms other fairer comparisons like Paxos and Raft.