research-article

Centiman: elastic, high performance optimistic concurrency control by watermarking

Authors:

Johannes GehrkeAuthors Info & Claims

SoCC '15: Proceedings of the Sixth ACM Symposium on Cloud Computing

Pages 262 - 275

https://doi.org/10.1145/2806777.2806837

Published: 27 August 2015 Publication History

Abstract

We present Centiman, a system for high performance, elastic transaction processing in the cloud. Centiman provides serializability on top of a key-value store with a lightweight protocol based on optimistic concurrency control (OCC).

Centiman is designed for the cloud setting, with an architecture that is loosely coupled and avoids synchronization wherever possible. Centiman supports sharded transaction validation; validators can be added or removed on-the-fly in an elastic manner. Processors and validators scale independently of each other and recover from failure transparently to each other. Centiman's loosely coupled design creates some challenges: it can cause spurious aborts and it makes it difficult to implement common performance optimizations for read-only transactions. To deal with these issues, Centiman uses a watermark abstraction to asynchronously propagate information about transaction commits through the system.

In an extensive evaluation we show that Centiman provides fast elastic scaling, low-overhead serializability for read-heavy workloads, and scales to millions of operations per second.

References

[1]

AmazonS3. http://aws.amazon.com/s3/.

[2]

HBase. http://hbase.apache.org/.

[3]

TATP. http://tatpbenchmark.sourceforge.net/.

[4]

Apache Zookeeper. http://zookeeper.apache.org/.

[5]

A. Adya and B. Liskov. Lazy consistency using loosely synchronized clocks. In PODC, pages 73--82, 1997.

Digital Library

[6]

A. Adya, R. Gruber, B. Liskov, and U. Maheshwari. Efficient optimistic concurrency control using loosely synchronized clocks. In SIGMOD, pages 23--34, 1995.

Digital Library

[7]

D. Agrawal, A. J. Bernstein, P. Gupta, and S. Sengupta. Distributed optimistic concurrency control with reduced rollback. Distributed Computing, 2(1):45--59, 1987.

Digital Library

[8]

R. Agrawal, M. J. Carey, and M. Livny. Concurrency control performance modeling: Alternatives and implications. ACM Trans. Database Syst., 12(4):609--654, 1987.

Digital Library

[9]

P. Bailis, A. Fekete, M. J. Franklin, A. Ghodsi, J. M. Hellerstein, and I. Stoica. Coordination avoidance in database systems. PVLDB, 8(3):185--196, 2014.

Digital Library

[10]

P. Bailis, A. Fekete, J. M. Hellerstein, A. Ghodsi, and I. Stoica. Scalable atomic visibility with RAMP transactions. In SIGMOD, pages 27--38, 2014.

Digital Library

[11]

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

[12]

M. Balakrishnan, D. Malkhi, T. Wobber, M. Wu, V. Prabhakaran, M. Wei, J. D. Davis, S. Rao, T. Zou, and A. Zuck. Tango: Distributed data structures over a shared log. In SOSP, pages 325--340, 2013.

Digital Library

[13]

N. S. Barghouti and G. E. Kaiser. Concurrency control in advanced database applications. ACM Comput. Surv., 23(3): 269--317, 1991.

Digital Library

[14]

D. Beaver, S. Kumar, H. C. Li, J. Sobel, and P. Vajgel. Finding a needle in haystack: Facebook's photo storage. In OSDI, pages 47--60, 2010.

Digital Library

[15]

H. Berenson, P. Bernstein, J. Gray, J. Melton, E. O'Neil, and P. O'Neil. A critique of ansi sql isolation levels. In SIGMOD, pages 1--10, 1995.

Digital Library

[16]

P. A. Bernstein and S. Das. Scaling optimistic concurrency control by approximately partitioning the certifier and log. IEEE Data Eng. Bull., 38(1):32--49, 2015.

[17]

P. A. Bernstein, C. W. Reid, and S. Das. Hyder - A transactional record manager for shared flash. In CIDR, pages 9--20, 2011.

[18]

P. A. Bernstein, C. W. Reid, M. Wu, and X. Yuan. Optimistic concurrency control by melding trees. PVLDB, 4(11):944--955, 2011.

Digital Library

[19]

P. A. Bernstein, S. Das, B. Ding, and M. Pilman. Optimizing optimistic concurrency control for tree-structured, log-structured databases. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, Melbourne, Victoria, Australia, May 31 -- June 4, 2015, pages 1295--1309, 2015.

Digital Library

[20]

C. Boksenbaum, M. Cart, J. Ferrié, and J. Pons. Concurrent certifications by intervals of timestamps in distributed database systems. IEEE Trans. Software Eng., 13(4):409--419, 1987.

Digital Library

[21]

B. F. Cooper, R. Ramakrishnan, U. Srivastava, A. Silberstein, P. Bohannon, H. Jacobsen, N. Puz, D. Weaver, and R. Yerneni. PNUTS: Yahoo!'s hosted data serving platform. PVLDB, 1(2): 1277--1288, 2008.

Digital Library

[22]

J. C. Corbett et al. Spanner: Google's globally-distributed database. In OSDI, pages 261--264, 2012.

Digital Library

[23]

S. Das, A. El Abbadi, and D. Agrawal. ElasTraS: An elastic transactional data store in the cloud. In HotCloud, 2009.

Digital Library

[24]

S. Das, D. Agrawal, and A. El Abbadi. G-store: a scalable data store for transactional multi key access in the cloud. In SoCC, pages 163--174, 2010.

Digital Library

[25]

G. DeCandia et al. Dynamo: amazon's highly available key-value store. In SOSP, pages 205--220, 2007.

Digital Library

[26]

A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, and D. Terry. Epidemic algorithms for replicated database maintenance. In PODC, pages 1--12, 1987.

Digital Library

[27]

C. Diaconu, C. Freedman, E. Ismert, P. Larson, P. Mittal, R. Stonecipher, N. Verma, and M. Zwilling. Hekaton: SQL server's memory-optimized OLTP engine. In SIGMOD, pages 1243--1254, 2013.

Digital Library

[28]

R. Escriva, B. Wong, and E. G. Sirer. Warp: Lightweight multi-key transactions for key-value stores. Technical report, Cornell University, Ithaca, NY, USA, 2013. URL http://rescrv.net/pdf/warp-tech-report.pdf.

[29]

J. M. Faleiro and D. J. Abadi. Rethinking serializable multiversion concurrency control. CoRR, abs/1412.2324, 2014. URL http://arxiv.org/abs/1412.2324.

[30]

D. G. Ferro, F. Junqueira, I. Kelly, B. Reed, and M. Yabandeh. Omid: Lock-free transactional support for distributed data stores. In ICDE, pages 676--687, 2014.

[31]

R. E. Gruber. Optimism vs. locking: A study of concurrency control for client-server object-oriented databases. Technical report, Massachusetts Institute of Technology, Cambridge, MA, USA, 1997. URL http://dspace.mit.edu/handle/1721.1/10762.

Digital Library

[32]

M. Herlihy. Apologizing versus asking permission: Optimistic concurrency control for abstract data types. ACM Trans. Database Syst., 15(1):96--124, 1990.

Digital Library

[33]

R. Johnson, I. Pandis, and A. Ailamaki. Eliminating unscalable communication in transaction processing. The VLDB Journal, 23(1):1--23, Feb 2014.

Digital Library

[34]

E. P. C. Jones, D. J. Abadi, and S. Madden. Low overhead concurrency control for partitioned main memory databases. In SIGMOD, pages 603--614, 2010.

Digital Library

[35]

R. Kallman et al. H-Store: a high-performance, distributed main memory transaction processing system. PVLDB, 1(2): 1496--1499, 2008.

Digital Library

[36]

S. S. Kulkarni, M. Demirbas, D. Madappa, B. Avva, and M. Leone. Logical physical clocks. In OPODIS, pages 17--32, 2014.

[37]

H. T. Kung and J. T. Robinson. On optimistic methods for concurrency control. ACM Trans. Database Syst., 6(2):213--226, 1981.

Digital Library

[38]

M. Lai and W. K. Wilkinson. Distributed transaction management in Jasmin. In VLDB, pages 466--470, 1984.

Digital Library

[39]

A. Lakshman and P. Malik. Cassandra: a decentralized structured storage system. Operating Systems Review, 44(2):35--40, 2010.

Digital Library

[40]

P. Larson, S. Blanas, C. Diaconu, C. Freedman, J. M. Patel, and M. Zwilling. High-performance concurrency control mechanisms for main-memory databases. PVLDB, 5(4):298--309, 2011.

Digital Library

[41]

J. J. Levandoski, D. B. Lomet, M. F. Mokbel, and K. Zhao. Deuteronomy: Transaction support for cloud data. In CIDR, pages 123--133, 2011.

[42]

C. Li, D. Porto, A. Clement, J. Gehrke, N. M. Preguiça, and R. Rodrigues. Making geo-replicated systems fast as possible, consistent when necessary. In OSDI, pages 265--278, 2012.

Digital Library

[43]

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

Digital Library

[44]

D. B. Lomet, A. Fekete, G. Weikum, and M. J. Zwilling. Unbundling transaction services in the cloud. In CIDR, 2009.

[45]

S. Mu, Y. Cui, Y. Zhang, W. Lloyd, and J. Li. Extracting more concurrency from distributed transactions. In OSDI, pages 479--494, 2014.

Digital Library

[46]

S. Patterson, A. J. Elmore, F. Nawab, D. Agrawal, and A. El Abbadi. Serializability, not serial: Concurrency control and availability in multi-datacenter datastores. PVLDB, 5(11): 1459--1470, 2012.

Digital Library

[47]

D. Peng and F. Dabek. Large-scale incremental processing using distributed transactions and notifications. In OSDI, pages 251--264, 2010.

Digital Library

[48]

E. Rahm. Design of optimistic methods for concurrency control in database sharing systems. In ICDCS, pages 154--161, 1987.

[49]

S. Roy, L. Kot, G. Bender, B. Ding, H. Hojjat, C. Koch, N. Foster, and J. Gehrke. The homeostasis protocol: Avoiding transaction coordination through program analysis. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, Melbourne, Victoria, Australia, May 31 - June 4, 2015, pages 1311--1326, 2015.

Digital Library

[50]

M. Serafini, E. Mansour, A. Aboulnaga, K. Salem, T. Rafiq, and U. F. Minhas. Accordion: Elastic scalability for database systems supporting distributed transactions. PVLDB, 7(12): 1035--1046, 2014.

Digital Library

[51]

M. K. Sinha, P. D. Nanadikar, and S. L. Mehndiratta. Timestamp based certification schemes for transactions in distributed database systems. In Proceedings of the 1985 ACM SIGMOD International Conference on Management of Data, Austin, Texas, May 28--31, 1985., pages 402--411, 1985.

Digital Library

[52]

X. Song and J. W. S. Liu. Maintaining temporal consistency: pessimistic vs. optimistic concurrency control. Knowledge and Data Engineering, IEEE Transactions on, 7(5):786--796, Oct 1995.

Digital Library

[53]

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

Digital Library

[54]

M. Stonebraker, S. Madden, D. J. Abadi, S. Harizopoulos, N. Hachem, and P. Helland. The end of an architectural era (it's time for a complete rewrite). In VLDB, pages 1150--1160, 2007.

Digital Library

[55]

R. Taft, E. Mansour, M. Serafini, J. Duggan, A. J. Elmore, A. Aboulnaga, A. Pavlo, and M. Stonebraker. E-store: Fine-grained elastic partitioning for distributed transaction processing. In VLDB, 2014.

Digital Library

[56]

D. B. Terry, A. J. Demers, K. Petersen, M. Spreitzer, M. Theimer, and B. B. Welch. Session guarantees for weakly consistent replicated data. In PDIS, pages 140--149, 1994.

Digital Library

[57]

A. Thomasian. Concurrency control: Methods, performance, and analysis. ACM Comput. Surv., 30(1):70--119, 1998.

Digital Library

[58]

A. Thomasian. Distributed optimistic concurrency control methods for high-performance transaction processing. IEEE Trans. Knowl. Data Eng., 10(1):173--189, 1998.

Digital Library

[59]

A. Thomson, T. Diamond, S. Weng, K. Ren, P. Shao, and D. J. Abadi. Calvin: fast distributed transactions for partitioned database systems. In SIGMOD, pages 1--12, 2012.

Digital Library

[60]

S. Tu, W. Zheng, E. Kohler, B. Liskov, and S. Madden. Speedy transactions in multicore in-memory databases. In ACM SIGOPS, pages 18--32, 2013.

Digital Library

[61]

P. S. Yu and D. M. Dias. Analysis of hybrid concurrency control schemes for a high data contention environment. IEEE Trans. Softw. Eng., 18(2):118--129, Feb. 1992.

Digital Library

[62]

Y. Zhang, R. Power, S. Zhou, Y. Sovran, M. K. Aguilera, and J. Li. Transaction chains: achieving serializability with low latency in geo-distributed storage systems. In SOSP, pages 276--291, 2013.

Digital Library

Cited By

Lai ZCui FFan HLo EZhou WLi F(2024)Occam's Razor for Distributed ProtocolsProceedings of the 2024 ACM Symposium on Cloud Computing10.1145/3698038.3698514(618-636)Online publication date: 20-Nov-2024
https://dl.acm.org/doi/10.1145/3698038.3698514
Lai ZFan HZhou WMa ZPeng XLi FLo E(2023)Knock Out 2PC with Practicality Intact: a High-performance and General Distributed Transaction Protocol2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00179(2317-2331)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00179
Kim IWang WQi YHumphrey M(2022) Forecasting Cloud Application Workloads With CloudInsight for Predictive Resource Management IEEE Transactions on Cloud Computing10.1109/TCC.2020.299801710:3(1848-1863)Online publication date: 1-Jul-2022
https://doi.org/10.1109/TCC.2020.2998017
Show More Cited By

Index Terms

Centiman: elastic, high performance optimistic concurrency control by watermarking

Recommendations

Improving transaction abort rates without compromising throughput through judicious scheduling
SAC '13: Proceedings of the 28th Annual ACM Symposium on Applied Computing

Althought optimistic concurrency control protocols have increasingly been used in distributed database management systems, they imply a trade-off between the number of transactions that can be executed concurrently, hence, the peak throughput, and ...
Infinite Resources for Optimistic Concurrency Control
NetCompute '18: Proceedings of the 2018 Morning Workshop on In-Network Computing

Optimistic concurrency control (OCC) is inefficient for high-contention workloads. When concurrent transactions conflict, an OCC system wastes CPU resources verifying transactions, only to abort them. This paper presents a new system, called Network ...
Optimistic concurrency for clusters via speculative locking
SYSTOR '09: Proceedings of SYSTOR 2009: The Israeli Experimental Systems Conference

Transactional memory and speculative locking are optimistic concurrency control mechanisms, whose goal is to enable highly concurrent execution while reducing the programming effort. The same basic idea lies in the heart of both methods: optimistically ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SoCC '15: Proceedings of the Sixth ACM Symposium on Cloud Computing

August 2015

446 pages

ISBN:9781450336512

DOI:10.1145/2806777

General Chair:
Shahram Ghandeharizadeh
University of Southern California
,
Program Chairs:
Magdalena Balazinska
University of Washington
,
Michael J. Freedman
Princeton University
,
Publications Chair:
Sumita Barahmand
Microsoft

Copyright © 2015 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 August 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

SoCC '15

Sponsor:

SoCC '15: ACM Symposium on Cloud Computing

August 27 - 29, 2015

Hawaii, Kohala Coast

Acceptance Rates

SoCC '15 Paper Acceptance Rate 34 of 157 submissions, 22%;

Overall Acceptance Rate 169 of 722 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
561
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lai ZCui FFan HLo EZhou WLi F(2024)Occam's Razor for Distributed ProtocolsProceedings of the 2024 ACM Symposium on Cloud Computing10.1145/3698038.3698514(618-636)Online publication date: 20-Nov-2024
https://dl.acm.org/doi/10.1145/3698038.3698514
Lai ZFan HZhou WMa ZPeng XLi FLo E(2023)Knock Out 2PC with Practicality Intact: a High-performance and General Distributed Transaction Protocol2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00179(2317-2331)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00179
Kim IWang WQi YHumphrey M(2022) Forecasting Cloud Application Workloads With CloudInsight for Predictive Resource Management IEEE Transactions on Cloud Computing10.1109/TCC.2020.299801710:3(1848-1863)Online publication date: 1-Jul-2022
https://doi.org/10.1109/TCC.2020.2998017
Vandevoort BKetsman BKoch CNeven F(2021)Robustness against read committed for transaction templatesProceedings of the VLDB Endowment10.14778/3476249.347626814:11(2141-2153)Online publication date: 1-Jul-2021
https://dl.acm.org/doi/10.14778/3476249.3476268
Chockler GGotsman A(2021)Multi-shot distributed transaction commitDistributed Computing10.1007/s00446-021-00389-4Online publication date: 24-Mar-2021
https://doi.org/10.1007/s00446-021-00389-4
Sang BRoman PEugster PLu HRavi SPetri GBilas AMagoutis KMarkatos EKostic DSeltzer M(2020)PLASMAProceedings of the Fifteenth European Conference on Computer Systems10.1145/3342195.3387553(1-15)Online publication date: 15-Apr-2020
https://dl.acm.org/doi/10.1145/3342195.3387553
Sadoghi MBlanas S(2019)Transaction Processing on Modern HardwareSynthesis Lectures on Data Management10.2200/S00896ED1V01Y201901DTM05814:2(1-138)Online publication date: 8-Mar-2019
https://doi.org/10.2200/S00896ED1V01Y201901DTM058
Ding BKot LGehrke J(2018)Improving optimistic concurrency control through transaction batching and operation reorderingProceedings of the VLDB Endowment10.14778/3282495.328250212:2(169-182)Online publication date: 1-Oct-2018
https://dl.acm.org/doi/10.14778/3282495.3282502
Fan HGolab W(2018)Scalable Transaction Processing Using Functors2018 IEEE 38th International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS.2018.00101(1004-1016)Online publication date: Jul-2018
https://doi.org/10.1109/ICDCS.2018.00101
Kim IWang WQi YHumphrey M(2018)CloudInsight: Utilizing a Council of Experts to Predict Future Cloud Application Workloads2018 IEEE 11th International Conference on Cloud Computing (CLOUD)10.1109/CLOUD.2018.00013(41-48)Online publication date: Jul-2018
https://doi.org/10.1109/CLOUD.2018.00013
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