Achieving both low latency and strong consistency in large-scale systems
Abstract/Contents
- Abstract
- 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).
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource. |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2019; ©2019 |
| Publication date | 2019; 2019 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Park, Seo Jin |
|---|---|
| Degree supervisor | Ousterhout, John K |
| Thesis advisor | Ousterhout, John K |
| Thesis advisor | Mazières, David (David Folkman), 1972- |
| Thesis advisor | Rosenblum, Mendel |
| Degree committee member | Mazières, David (David Folkman), 1972- |
| Degree committee member | Rosenblum, Mendel |
| Associated with | Stanford University, Computer Science Department. |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Seo Jin Park. |
|---|---|
| Note | Submitted to the Computer Science Department. |
| Thesis | Thesis Ph.D. Stanford University 2019. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2019 by Seo Jin Park
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...