Doctoral Thesis Defense - Ricardo Jorge Tomé Gonçalves

Friday, September 28, 2018, 10:00am

Title: Multi-Value Distributed Key-Value Stores

Abstract: Many large scale distributed data stores rely on optimistic replication to scale and remain highly available in the face of network partitions. Man- aging data without strong coordination results in eventually consistent data stores that allow for concurrent data updates. To allow writing ap- plications in the absence of linearizability or transactions, the seminal Dynamo data store proposed a multi-value API in which a get returns the set of concurrent written values. In this scenario, it is important to be able to accurately and efficiently identify updates executed concur- rently. Logical clocks are often used to track data causality, necessary to distinguish concurrent from causally related writes on the same key. However, in traditional mechanisms there is a non-negligible metadata overhead per key, which also keeps growing with time, proportional to the node churn rate. Another challenge is deleting keys while respect- ing causality: while the values can be deleted, per-key metadata cannot be permanently removed in current data stores.

These systems often use anti-entropy mechanisms (like Merkle Trees) to detect and repair divergent data versions across nodes. However, in practice hash-based data structures are not suitable to a store using consistent hashing and create too many false positives.

Also, highly available systems usually provide eventual consistency, which is the weakest form of consistency. This results in a program- ming model difficult to use and to reason about. It has been proved that causal consistency is the strongest consistency model achievable if we want highly available services. It provides better programming seman- tics such as sessions guarantees. However, classical causal consistency is a memory model that that is problematic for concurrent updates, in the absence of concurrency control primitives. Used in eventually con- sistent data stores, it leads to arbitrating between concurrent updates which leads to data loss. 

We propose three novel techniques in this thesis. The first is Dotted Version Vectors: a solution that combines a new logical clock mecha- nism and a request handling workflow that together support the tra- ditional Dynamo key-value store API while capturing causality in an accurate and scalable way, avoiding false conflicts. It maintains concise information per version, linear only on the number of replicas, and in- cludes a container data structure that allows sets of concurrent versions to be merged efficiently, with time complexity linear on the number of replicas plus versions. 

The second is DottedDB: a Dynamo-like key-value store, which uses a novel node-wide logical clock framework, overcoming three funda- mental limitations of the state of the art: (1) minimize the metadata per key necessary to track causality, avoiding its growth even in the face of node churn; (2) correctly and durably delete keys, with no need for tombstones; (3) offer a lightweight anti-entropy mechanism to converge replicated data, avoiding the need for Merkle Trees. 

The third and final contribution is Causal Multi-Value Consistency: a novel consistency model that respects the causality of client operations while properly supporting concurrent updates without arbitration, by having the same Dynamo-like multi-value nature. In addition, we ex- tend this model to provide the same semantics with read and write transactions. For both models, we define an efficient implementation on top of a distributed key-value store.

Supervisors: Paulo Sérgio Soares Almeida and Victor Francisco Fonte

Jury: Rector of the University of Minho

        Doctor Luís Eduardo Teixeira Rodrigues, Full Professor - Departamento de Engenharia Informática do Instituto Superior Técnico da Universidade de Lisboa

        Doctor Beatriz Sousa Santos, Associate Professor with Habilitation - Departamento de Eletrónica, Telecomunicações e Informática da Universidade de Aveiro

        Doctor Nuno Miguel Ribeiro Preguiça, Associate Professor - Departamento de Informática da Faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa

        Doctor Annette Bieniusa, Senior Researcher do Department of Computer Science da University of Kaiserslautern, Alemanha

Location: Auditorium B1, University of Minho, Campus de Gualtar, Braga