Extract More Concurrency From Distributed Transactions

In distributed storage systems, a transaction request needs to access data items located in multiple machines. To ensure serializability and satisfy application semantics requirements, certain distributed concurrency control protocols are needed. Traditional protocols for distributed transactions usually are based on two-phase locking(2PL) or optimistic concurrency control(OCC). 2PL serializes transactions when they conflict and OCC resorts to aborts, thus both leave many opportunities for concurrency on the table.This paper presents the following:1. This paper presents a novel concurrency control protocol(Dep Tran) for one-shot distributed transactions based on decentralized dependency tracking and propagation. Dep Tran preprocesses transactions by chopping them into pieces, each of which can execute atomically on a single server. Servers track dependencies between concurrent transactions at runtime. At commit time, the transaction coordinator disseminates a transaction’s dependency information to all servers so they can re-order interfering pieces into a serializable order. Compared to traditional approach, Dep Tran acheives 3.2~6.7x improvement in throughput.2. This paper presents novel concurrency control protocol(Rococo) for general distributed transactions, based on offline-checking, conflicts reordering and optimistic read-only protocols. Rococo uses offline checking and combines traditional methods to ensure every participating piece is reorderable, and provide separate protocols for read-only transactions The performance of Rococo is strictly better than traditional protocols in workloads with normal contention, having 1.2~5.3x improvement in throughput.3. This paper presents a rigorous analysis on the protocols it proposes. In this anlysis,we divide the complex concurrency controls into a few important invariants, with one supporting another. These invariants show the correctness of the concurrency control protocols step by step. They also help developers to better understand the design of the protocols and provide a blueprint on the correct implementation of the system. Moreover, we use a formal system specification language named TLA+ to describe our procotols and apply model checking to show the correctness of possible optimizations.4. Based on the recent trend of using a single working-thread model to build distributed database, this paper points out the possible “stack ripping” problem when using a moderately complex concurrency control protocols. To fix this problem, we present a user-space light-weight thread framework, Tran Fiber, supporting both cooperative task management and automatic stack management. Tran Fiber can largely ease the programming efforts on building distributed concurrency protocols in databases.