Candidate: Hua Fan
Title: Building Scalable and Consistent Distributed Databases under Conflicts
Date: March 22, 2018
Time: 1:30 PM
Place: EIT 3142
Supervisor(s): Golab, Wojciech
Abstract:
Distributed databases, which have redundant and distributed storage across multiple servers, are able to provide mission-critical data management services at large scale. Parallelism is the key to the scalability of distributed databases, but concurrent queries having conflicts may block or abort each other when strong consistency is enforced by the rigorous concurrency control protocols.
This thesis studies the techniques of building scalable distributed databases under strong consistency guarantees even in face of high contention workloads. These techniques share a common idea, conflicts avoidance, meaning proactively avoiding potential conflicts in the concurrency control in the first place other than resolving conflicts by contending. Using this idea, concurrent queries under conflicts can be executed in a way of high parallelism. This thesis practices this idea on both databases that support serializable ACID (atomic, consistency, isolation, durability) transactions, and eventually consistent NoSQL systems.
First, the epoch-based concurrency control (ECC) is proposed in ALOHA-KV, a new built distributed key-value store that supports high performance read-only and write-only distributed transactions. ECC demonstrates that concurrent serializable distributed transactions can be processed in parallel with low-overhead even under high contention. With ECC, a new atomic commitment protocol is developed that only requires amortized one round trip for a distributed write-only transaction to commit when failures do not present. Thus, ALOHA-KV can execute distributed read-only and write-only transactions in conflicts efficiently, and experiment results show that ALOHA-KV can process close to 15 million read/write operations per second per server when each transaction batches together thousands of such operations.
Second, a novel paradigm of serializable distributed transaction processing is developed to extend ECC with read-write transaction processing support. This paradigm uses a newly proposed database operator, functors, which conceptually resemble futures in modern programming languages. A functor is a placeholder for the value of a key, which can be computed asynchronously in the future in parallel with other functor computations of the same or other transactions. Functor-enabled ECC achieves finer-grained concurrency control --- resolving conflicts for generating the value of a key in the transaction other than resolving all conflicts for the whole transaction --- while ECC already guarantees transaction atomicity and resolves transaction orders. This combination of techniques never aborts transactions due to read-write or write-write conflicts but allows transactions to fail due to logic errors or constraint violations while guaranteeing serializability. ALOHA-DB, a scalable distributed transaction processing system, is implemented atop of ALOHA-KV to support functor-enabled ECC. In the experimental results, ALOHA-DB performs 2.4 million TPC-C transactions per second over 20 eight-core virtual machines, which outperforms Calvin, a state-of-the-art transaction processing and replication layer, by one to two orders of magnitude.
Third, a read-write conflict, if which is not resolved appropriately, may result in a consistency violation. An investigation of the consistency violation anomalies, referred to as ``consistency spikes'', is conducted on an eventually consistent distributed database, Apache Cassandra. This investigation shows that the consistency spikes exhibited by Cassandra are strongly correlated with garbage collection, particularly the ``stop-the-world" phase in the Java virtual machine. Avoiding potential read-write conflicts by delaying read operations artificially at servers immediately after a garbage collection pause, can virtually eliminate these spikes. In the experimental evaluations, this simple technique yields more than a 98% reduction in the number of consistency anomalies that exceed 5ms, and has negligible impact on throughput and latency.