Search all library resources

Achieving both low latency and strong consistency in large-scale systems

Today's datacenter applications demand large-scale and low-latency systems. Unfortunately, consistency mechanisms were not designed in consideration of large-scale and low-latency settings. Most existing consistency mechanisms incur huge penalties on scalability or latency, so many datacenter systems have forgone consistency. As a result, application developers or end-users suffer from unpredictable system behaviors. This dissertation presents two new consistency mechanisms for large-scale and low-latency systems: Reusable Infracture for Linearizability (RIFL) and Consistent Unordered Replication Protocol (CURP). RIFL provides a general-purpose mechanism for converting at-least-once RPC semantics to exactly-once semantics, thereby making it easy to turn non-linearizable operations into linearizable ones. RIFL is designed for large-scale systems and is lightweight enough to be used in low-latency environments. On the RAMCloud storage system, RIFL adds only 0.5 us to the 13.5 us base latency for durable writes, and it can support 1 million clients with minimal performance degradation (~5% latency increase). We also used RIFL to construct a new multi-server transaction mechanism (RIFL-TX) in RAMCloud; RIFL's facilities significantly simplified the transaction implementation. The transaction mechanism can commit simple distributed transactions in about 20 us and it outperforms the H-Store main-memory database system for the TPC-C benchmark. Replication is a must-have for large-scale systems for masking individual server failures and maintaining high availability. However, consistent replication incurs significant overhead, such as doubling the latency of operations. As a result, many large-scale systems have settled for weakly consistent replication. To address this dilemma, I present Consistent Unordered Replication Protocol (CURP), which removes most of the overhead of consistent replication. CURP avoids performance penalties by allowing clients to directly replicate their requests, as long as the requests are commutative. This strategy allows most operations to complete in 1 RTT (the same as an unreplicated system). On RAMCloud, CURP improved write latency by ~2x (14 us -> 7.1 us) and write throughput by 4x. Compared to unreplicated RAMCloud, CURP's latency overhead for 3-way replication is just 1 us (6.1 us vs. 7.1 us).