research-article

ChainReaction: a causal+ consistent datastore based on chain replication

Authors:

Sérgio Almeida,

Luís RodriguesAuthors Info & Claims

EuroSys '13: Proceedings of the 8th ACM European Conference on Computer Systems

Pages 85 - 98

https://doi.org/10.1145/2465351.2465361

Published: 15 April 2013 Publication History

Abstract

This paper proposes a Geo-distributed key-value datastore, named ChainReaction, that offers causal+ consistency, with high performance, fault-tolerance, and scalability. ChainReaction enforces causal+ consistency which is stronger than eventual consistency by leveraging on a new variant of chain replication. We have experimentally evaluated the benefits of our approach by running the Yahoo! Cloud Serving Benchmark. Experimental results show that ChainReaction has better performance in read intensive workloads while offering competitive performance for other workloads. Also we show that our solution requires less metadata when compared with previous work.

References

[1]

S. Almeida. Geo-replication in large scale cloud computing applications. Master's thesis, Univ. Técnica de Lisboa, 2007.

[2]

D. Andersen, J. Franklin, M. Kaminsky, A. Phanishayee, L. Tan, and V. Vasudevan. FAWN: a fast array of wimpy nodes. Comm. ACM, 54(7):101--109, 2011.

Digital Library

[3]

J. Baker, C. Bond, J. Corbett, J. Furman, A. Khorlin, J. Larson, J.-M. Leon, Y. Li, A. Lloyd, and V. Yushprakh. Megastore: Providing scalable, highly available storage for interactive services. In CIDR, pages 223--234, 2011.

[4]

N. Belarami, M. Dahlin, L. Gao, A. Nayate, A. Venkataramani, P. Yalagandula, and J. Zheng. PRACTI replication. In USENIX NSDI, pages 59--72, 2006.

Digital Library

[5]

E. Brewer. Towards robust distributed systems (abstract). In ACM PODC, page 7, 2000.

Digital Library

[6]

B. Cooper, R. Ramakrishnan, U. Srivastava, A. Silberstein, P. Bohannon, H.-A. Jacobsen, N. Puz, D. Weaver, and R. Yerneni. PNUTS: Yahoo!'s hosted data serving platform. In VLDB, pages 1277--1288. VLDB Endowment, 2008.

Digital Library

[7]

B. Cooper, A. Silberstein, E. Tam, R. Ramakrishnan, and R. Sears. Benchmarking cloud serving systems with YCSB. In ACM SOCC, pages 143--154, 2010.

Digital Library

[8]

M. Couceiro, P. Romano, N. Carvalho, and L. Rodrigues. D2STM: Dependable distributed software transactional memory. In IEEE PRDC, pages 307--313, 2009.

Digital Library

[9]

R. Escriva, B. Wong, and E. G. Sirer. HyperDex: A distributed, searchable key-value store for cloud computing. Technical report, CSD, Cornell University, 2011.

[10]

D. Hastorun, M. Jampani, G. Kakulapati, A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels. Dynamo: amazon's highly available key-value store. In ACM SOSP, pages 205--220, 2007.

Digital Library

[11]

M. Herlihy and J. Wing. Linearizability: a correctness condition for concurrent objects. ACM TOPLAS, 12:463--492, 1990.

Digital Library

[12]

G. Laden, R. Melamed, and Y. Vigfusson. Adaptive and dynamic funnel replication in clouds. In ACM LADIS, 2011.

[13]

R. Ladin, B. Liskov, L. Shrira, and S. Ghemawat. Providing high availability using lazy replication. ACM TOCS, 10:360--391, 1992.

Digital Library

[14]

A. Lakshman and P. Malik. Cassandra: a decentralized structured storage system. SIGOPS OSR, 44:35--40, 2010.

Digital Library

[15]

L. Lamport. Time, clocks, and the ordering of events in a distributed system. Comm. of the ACM, 21:558--565, 1978.

Digital Library

[16]

C. Lesniewski-Laas. A sybil-proof one-hop DHT. In ACM SNS, pages 19--24, 2008.

Digital Library

[17]

W. Lloyd, M. Freedman, M. Kaminsky, and D. Andersen. Don't settle for eventual: scalable causal consistency for wide-area storage with cops. In ACM SOSP, pages 401--416, 2011.

Digital Library

[18]

P. Mahajan, L. Alvisi, and M. Dahlin. Consistency, availability, and convergence. Technical Report TR-11-22, Univ. Texas at Austin, 2011.

[19]

D. Malkhi, M. Balakrishnan, J. Davis, V. Prabhakaran, and T. Wobber. From paxos to CORFU: a flash-speed shared log. SIGOPS OSR, 46:47--51, Feb. 2012.

Digital Library

[20]

K. Petersen, M. Spreitzer, D. Terry, M. Theimer, and A. J. Demers. Flexible update propagation for weakly consistent replication. In ACM SOSP, pages 288--301, 1997.

Digital Library

[21]

F. Schneider. Replication management using the state-machine approach. In S. Mullender, editor, Distributed Systems (2nd Ed.), ACM-Press, chapter 7. Addison-Wesley, 1993.

Digital Library

[22]

Y. Sovran, R. Power, M. Aguilera, and J. Li. Transactional storage for geo-replicated systems. In ACM SOSP, pages 385--400, 2011.

Digital Library

[23]

J. Terrace and M. J. Freedman. Object storage on CRAQ: high-throughput chain replication for read-mostly workloads. In Proc. USENIX Annual Tech. Conference, USA, 2009.

Digital Library

[24]

R. Thomas. A majority consensus approach to concurrency control for multiple copy databases. ACM TODS, 1979.

Digital Library

[25]

R. van Renesse and F. Schneider. Chain replication for supporting high throughput and availability. In USENIX OSDI, USA, 2004.

Digital Library

Cited By

Fouto PPreguiça NLeitão J(2024)Large-Scale Causal Data Replication for Stateful Edge Applications2024 IEEE 44th International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS60910.2024.00028(209-220)Online publication date: 23-Jul-2024
https://doi.org/10.1109/ICDCS60910.2024.00028
Ferreira Loff JPorto DGarcia JMace JRodrigues RDruschel PKaufmann AMace JFlinn JSeltzer M(2023)Antipode: Enforcing Cross-Service Causal Consistency in Distributed ApplicationsProceedings of the 29th Symposium on Operating Systems Principles10.1145/3600006.3613176(298-313)Online publication date: 23-Oct-2023
https://dl.acm.org/doi/10.1145/3600006.3613176
Frey DMostefaoui APerrin MRoman PTaïani F(2023)Differentiated Consistency for Worldwide GossipsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2022.320915034:1(1-15)Online publication date: 1-Jan-2023
https://doi.org/10.1109/TPDS.2022.3209150
Show More Cited By

Index Terms

ChainReaction: a causal+ consistent datastore based on chain replication

Recommendations

GentleRain: Cheap and Scalable Causal Consistency with Physical Clocks
SOCC '14: Proceedings of the ACM Symposium on Cloud Computing

GentleRain is a new causally consistent geo-replicated data store that provides throughput comparable to eventual consistency and superior to current implementations of causal consistency.

GentleRain uses a periodic aggregation protocol to determine ...
Don't settle for eventual: scalable causal consistency for wide-area storage with COPS
SOSP '11: Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles

Geo-replicated, distributed data stores that support complex online applications, such as social networks, must provide an "always-on" experience where operations always complete with low latency. Today's systems often sacrifice strong consistency to ...
Keeping up with storage: Decentralized, write-enabled dynamic geo-replication
Abstract
Large-scale applications are ever-increasingly geo-distributed. Maintaining the highest possible data locality is crucial to ensure high performance of such applications. Dynamic replication addresses this problem by dynamically creating replicas ...
Highlights
- We propose a decentralized data popularity measurement method to identify hot data cluster-wide.
- We describe a dynamic data replication algorithm which dynamically creates and manages replicas of hot data.
- We enable clients to ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

EuroSys '13: Proceedings of the 8th ACM European Conference on Computer Systems

April 2013

401 pages

ISBN:9781450319942

DOI:10.1145/2465351

General Chairs:
Zdenek Hanzálek
Czech Technical University Prague
,
Hermann Härtig
Technische Universität Dresden
,
Program Chairs:
Miguel Castro
Microsoft Research Cambridge
,
M. Frans Kaashoek
MIT

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 April 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Fundação para a Ciência e a Tecnologia

Conference

EuroSys '13

Sponsor:

SIGOPS

EuroSys '13: Eighth Eurosys Conference 2013

April 15 - 17, 2013

Prague, Czech Republic

Acceptance Rates

EuroSys '13 Paper Acceptance Rate 28 of 143 submissions, 20%;

Overall Acceptance Rate 241 of 1,308 submissions, 18%

Upcoming Conference

EuroSys '25

Sponsor:
sigops

Twentieth European Conference on Computer Systems

March 30 - April 3, 2025

Rotterdam , Netherlands

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

86
Total Citations
View Citations
599
Total Downloads

Downloads (Last 12 months)38
Downloads (Last 6 weeks)8

Reflects downloads up to 06 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Fouto PPreguiça NLeitão J(2024)Large-Scale Causal Data Replication for Stateful Edge Applications2024 IEEE 44th International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS60910.2024.00028(209-220)Online publication date: 23-Jul-2024
https://doi.org/10.1109/ICDCS60910.2024.00028
Ferreira Loff JPorto DGarcia JMace JRodrigues RDruschel PKaufmann AMace JFlinn JSeltzer M(2023)Antipode: Enforcing Cross-Service Causal Consistency in Distributed ApplicationsProceedings of the 29th Symposium on Operating Systems Principles10.1145/3600006.3613176(298-313)Online publication date: 23-Oct-2023
https://dl.acm.org/doi/10.1145/3600006.3613176
Frey DMostefaoui APerrin MRoman PTaïani F(2023)Differentiated Consistency for Worldwide GossipsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2022.320915034:1(1-15)Online publication date: 1-Jan-2023
https://doi.org/10.1109/TPDS.2022.3209150
Huang CGao YChen WLi DXiao YZhang RTian CWang XDou WChen GWang YXiao F(2023)MC-RDMA: Improving Replication Performance of RDMA-based Distributed Systems with Reliable Multicast Support2023 IEEE 31st International Conference on Network Protocols (ICNP)10.1109/ICNP59255.2023.10355619(1-11)Online publication date: 10-Oct-2023
https://doi.org/10.1109/ICNP59255.2023.10355619
Yuan YHuang JSun YWang TNelson JPorts DWang YWang RTai CKim N(2023)Rambda: RDMA-driven Acceleration Framework for Memory-intensive µs-scale Datacenter Applications2023 IEEE International Symposium on High-Performance Computer Architecture (HPCA)10.1109/HPCA56546.2023.10071127(499-515)Online publication date: Feb-2023
https://doi.org/10.1109/HPCA56546.2023.10071127
Reznichenko V(2022)60 Years of Databases (part three)PROBLEMS IN PROGRAMMING10.15407/pp2022.01.034(034-066)Online publication date: Mar-2022
https://doi.org/10.15407/pp2022.01.034
Sharif AGan EWei M(2022)Styx++: Reliable Data Access and Availability Using a Hybrid Paxos and Chain Replication ProtocolExtended Abstracts of the 2022 CHI Conference on Human Factors in Computing Systems10.1145/3491101.3519635(1-7)Online publication date: 27-Apr-2022
https://dl.acm.org/doi/10.1145/3491101.3519635
Goncalves JMatos MRodrigues R(2022)SconeKV: A Scalable, Strongly Consistent Key-Value StoreIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2022.317990333:12(4164-4175)Online publication date: 1-Dec-2022
https://doi.org/10.1109/TPDS.2022.3179903
An SCao YZhao W(2022)Competitive Consistent Caching for Transactions2022 IEEE 38th International Conference on Data Engineering (ICDE)10.1109/ICDE53745.2022.00207(2154-2167)Online publication date: May-2022
https://doi.org/10.1109/ICDE53745.2022.00207
Brahneborg DDuvignau RAfzal WMubeen S(2022)GeoRep—Resilient Storage for Wide Area NetworksIEEE Access10.1109/ACCESS.2022.319168610(75772-75788)Online publication date: 2022
https://doi.org/10.1109/ACCESS.2022.3191686
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents