Exploiting Commutativity For Practical Fast Replication
summary
Proposes consistent unordered replication (CURP): clients replicate requests to small temporary witnesses without waiting for global ordering, allowing 1 RTT for commutative operations and falling back to two RTTs when witnesses reject. Implements CURP in Redis and RAMCloud; RAMCloud write latency drops from 14µs to 7.1µs (2x) and write throughput increases 4x, with only ~1µs overhead versus unreplicated (6.1µs vs 7.1µs). Redis becomes durable with small cost.
AI-written summary · about
chapters (13)
- 0:00Start
- 1:58Consistent Replication Doubles Latencies
- 2:40Strawman 1 RTT Replication
- 3:34What Makes consistent Replication Expensive?
- 4:26Exploiting Commutativity to Defer Ordering
- 5:30Overview of CURP
- 8:05Crash Recovery
- 8:46Replay From Witness May Be Out Of Order
- 9:41Primaries May Reveal Not-yet-durable Data
- 10:44Replay Can Cause Duplicate Executions
- 12:33RAMCloud's Latency after CURP
- 14:25Related work
- 15:53Conclusion
related talks
37mGeo-Replicated Transactions in 1.5RTT
36mConflict-Free Replicated Datatypes (CRDT)
24mStronger Semantics for Low-Latency Geo-Replicated Storage
29mLet's replicate state together
48mCRDTs: From sequential to concurrent executions
57mLiving in eventually consistent reality
50mCRDTs in Practice
18mCuckoo for Clients: Disaggregated Cuckoo Hashing