Implementing linearizability at large scale and low latency
Authors:
- Satoshi MatsushitaSMSatoshi Matsushita
Open Access
- 4 October 2015
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 71-86
Abstract
Linearizability is the strongest form of consistency for concurrent systems, but most large-scale storage systems settle for weaker forms of consistency. 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. RIFL handles data migration by associating linearizability metadata with objects in the underlying store and migrating metadata with the corresponding objects. It uses a lease mechanism to implement garbage collection for metadata. We have implemented RIFL in the RAMCloud storage system and used it to make basic operations such as writes and atomic increments linearizable; RIFL adds only 530 ns to the 13.5 μs base latency for durable writes. We also used RIFL to construct a new multi-object transaction mechanism in RAMCloud; RIFL's facilities significantly simplified the transaction implementation. The transaction mechanism can commit simple distributed transactions in about 20 μs and it outperforms the H-Store main-memory database system for the TPC-C benchmark.Keywords
Funding Information
- NetApp
- Emulex
- Huawei
- Inventec
- Samsung
- VMware
- NEC
This publication has 16 references indexed in Scilit:
- The RAMCloud Storage SystemACM Transactions on Computer Systems, 2015
- CassandraACM SIGOPS Operating Systems Review, 2010
- SinfoniaACM Transactions on Computer Systems, 2009
- Queued Transaction Processing2009
- H-storeProceedings of the VLDB Endowment, 2008
- DynamoACM SIGOPS Operating Systems Review, 2007
- The part-time parliamentACM Transactions on Computer Systems, 1998
- Linearizability: a correctness condition for concurrent objectsACM Transactions on Programming Languages and Systems, 1990
- Useless Actions Make a DifferenceJournal of the ACM, 1982
- On optimistic methods for concurrency controlACM Transactions on Database Systems, 1981