Article

Granola: low-overhead distributed transaction coordination

Authors:

Barbara LiskovAuthors Info & Claims

USENIX ATC'12: Proceedings of the 2012 USENIX conference on Annual Technical Conference

Page 21

Published: 13 June 2012 Publication History

Abstract

This paper presents Granola, a transaction coordination infrastructure for building reliable distributed storage applications. Granola provides a strong consistency model, while significantly reducing transaction coordination overhead. We introduce specific support for a new type of independent distributed transaction, which we can serialize with no locking overhead and no aborts due to write conflicts. Granola uses a novel timestamp-based coordination mechanism to order distributed transactions, offering lower latency and higher throughput than previous systems that offer strong consistency.

Our experiments show that Granola has low overhead, is scalable and has high throughput. We implemented the TPC-C benchmark on Granola, and achieved 3× the throughput of a platform using a locking approach.

References

[1]

Amazon SimpleDB. http://aws.amazon.com/ simpledb/.

[2]

Apache Cassandra. http://cassandra.apache.org.

[3]

Apache CouchDB. http://couchdb.apache.org.

[4]

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

[5]

MongoDB. http://www.mongodb.com.

[6]

TPC benchmark C. Technical report, Transaction Processing Performance Council, February 2010. Revision 5.11.

[7]

M. K. Aguilera, A. Merchant, M. A. Shah, A. C. Veitch, and C. T. Karamanolis. Sinfonia: A new paradigm for building scalable distributed systems. ACM TOCS, 2009.

[8]

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

[9]

H. Boral, W. Alexander, L. Clay, G. Copeland, S. Danforth, M. Franklin, B. Hart, M. Smith, and P. Valduriez. Prototyping Bubba, a highly parallel database system. IEEE TKDE, March 1990.

[10]

M. Castro and B. Liskov. Practical Byzantine Fault Tolerance and Proactive Recovery. ACM TOCS, 2002.

[11]

F. Chang, J. Dean, S. Ghemawat, W. C. Hsieh, D. A. Wallach, M. Burrows, T. Chandra, A. Fikes, and R. E. Gruber. Bigtable: a distributed storage system for structured data. In OSDI, 2006.

[12]

B. F. 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. VLDB, 2008.

[13]

J. Cowling. Low-Overhead Distributed Transaction Coordination. PhD thesis, MIT, June 2012.

[14]

G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman, A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels. Dynamo: Amazon's highly available keyvalue store. In SOSP, 2007.

[15]

D. DeWitt, S. Ghandeharizadeh, D. Schneider, A. Bricker, H. l Hsiao, and R. Rasmussen. The Gamma database machine project. IEEE TKDR, March 1990.

[16]

K. P. Eswaran, J. N. Gray, R. A. Lorie, and I. L. Traiger. The Notions of Consistency and Predicate Locks in a Database System. CACM, Nov. 1976.

[17]

R. Guy, J. Heidemann, W. Mak, T. Page Jr., G. Popek, and D. Rothneier. Implementation of the Ficus replicated file system. In USENIX, 1990.

[18]

S. Harizopoulos, D. J. Abadi, S. Madden, and M. Stonebraker. OLTP through the looking glass, and what we found there. In SIGMOD, 2008.

[19]

E. P. C. Jones. Fault-Tolerant Distributed Transactions for Partitioned OLTP Databases. PhD thesis, MIT, 2012.

[20]

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

[21]

R. Ladin, B. Liskov, L. Shrira, and S. Ghemawat. Providing High Availability Using Lazy Replication. ACM TOCS, Nov. 1992.

[22]

L. Lamport. The Part-Time Parliament. Technical Report Research Report 49, Digital Equipment Corporation Systems Research Center, Palo Alto, CA, Sept. 1989.

[23]

K.-J. Lin. Consistency issues in real-time database systems. In System Sciences, 1989.

[24]

B. Liskov and J. Cowling. Viewstamped replication revisited. Technical report, MIT CSAIL, Cambridge, MA, 2012.

[25]

B. Liskov, S. Ghemawat, R. Gruber, P. Johnson, L. Shrira, and M. Williams. Replication in the Harp File System. In SOSP, 1991.

[26]

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, 2011.

[27]

C. Mohan, B. Lindsay, and R. Obermarck. Transaction management in the R* distributed database management system. ACM TODS, December 1986.

[28]

B. Oki and B. Liskov. Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems. In PODC, 1988.

[29]

M. Satyanarayanan, J. J. Kistler, P. Kumar, M. E. Okasaki, E. H. Siegel, David, and C. Steere. Coda: A highly available file system for a distributed workstation environment. IEEE TC, 1990.

[30]

F. B. Schneider. The state machine approach: A Tutorial. Technical Report TR 86-600, Cornell University, Dept. of Computer Science, Ithaca, N. Y., Dec. 1986.

[31]

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

[32]

M. Stonebraker, S. R. 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, 2007.

[33]

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

[34]

D. B. Terry, M. M. Theimer, K. Petersen, A. J. Demers, and M. J. Spreitzer. Managing Update Conflicts in Bayou, a Weakly Connected Replicated Storage System. In SOSP, 1995.

[35]

A. Thomson, T. Diamond, S. chun Weng, P. Shao, K. Ren, P. Shao, and D. J. Abadi. Calvin: Fast distributed transactions for partitioned database systems. In SIGMOD, 2012.

[36]

VoltDB Inc. VoltDB. http://voltdb.com.

Cited By

Lu YYu XCao LMadden S(2021)Epoch-based commit and replication in distributed OLTP databasesProceedings of the VLDB Endowment10.14778/3446095.344609814:5(743-756)Online publication date: 23-Mar-2021
https://dl.acm.org/doi/10.14778/3446095.3446098
Lu HSen SLloyd WLu SHowell J(2020)Performance-optimal read-only transactionsProceedings of the 14th USENIX Conference on Operating Systems Design and Implementation10.5555/3488766.3488785(333-349)Online publication date: 4-Nov-2020
https://dl.acm.org/doi/10.5555/3488766.3488785
Lu YYu XCao LMadden S(2020)AriaProceedings of the VLDB Endowment10.14778/3407790.340780813:12(2047-2060)Online publication date: 14-Sep-2020
https://dl.acm.org/doi/10.14778/3407790.3407808
Show More Cited By

Granola: low-overhead distributed transaction coordination

Recommendations

WFR-TM

Transactional Memory (TM) is a promising concurrent programming paradigm which employs transactions to achieve synchronization in accessing common data known as transactional variables. A transaction may either commit, making its updates to ...
Speculation-based techniques for transactional lock-free execution of lock-based programs
Wait-n-GoTM: improving HTM performance by serializing cyclic dependencies
ASPLOS '13

Transactional memory (TM) has been proposed to alleviate some key programmability problems in chip multiprocessors. Most TMs optimistically allow concurrent transactions, detecting read-write or write-write conflicts. Upon conflicts, existing hardware ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

USENIX ATC'12: Proceedings of the 2012 USENIX conference on Annual Technical Conference

June 2012

41 pages

Publisher

USENIX Association

United States

Publication History

Published: 13 June 2012

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

46
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lu YYu XCao LMadden S(2021)Epoch-based commit and replication in distributed OLTP databasesProceedings of the VLDB Endowment10.14778/3446095.344609814:5(743-756)Online publication date: 23-Mar-2021
https://dl.acm.org/doi/10.14778/3446095.3446098
Lu HSen SLloyd WLu SHowell J(2020)Performance-optimal read-only transactionsProceedings of the 14th USENIX Conference on Operating Systems Design and Implementation10.5555/3488766.3488785(333-349)Online publication date: 4-Nov-2020
https://dl.acm.org/doi/10.5555/3488766.3488785
Lu YYu XCao LMadden S(2020)AriaProceedings of the VLDB Endowment10.14778/3407790.340780813:12(2047-2060)Online publication date: 14-Sep-2020
https://dl.acm.org/doi/10.14778/3407790.3407808
Zamanian EShun JBinnig CKraska TMaier DPottinger RDoan ATan WAlawini ANgo H(2020)Chiller: Contention-centric Transaction Execution and Data Partitioning for Modern NetworksProceedings of the 2020 ACM SIGMOD International Conference on Management of Data10.1145/3318464.3389724(511-526)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3318464.3389724
Zamanian EYu XStonebraker MKraska T(2019)Rethinking database high availability with RDMA networksProceedings of the VLDB Endowment10.14778/3342263.334263912:11(1637-1650)Online publication date: 1-Jul-2019
https://dl.acm.org/doi/10.14778/3342263.3342639
Didona DFatourou PGuerraoui RWang JZwaenepoel WScheideler CBerenbrink P(2019)Distributed Transactional Systems Cannot Be FastThe 31st ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3323165.3323189(369-380)Online publication date: 17-Jun-2019
https://dl.acm.org/doi/10.1145/3323165.3323189
Mu SAngel SShasha D(2019)Deferred Runtime Pipelining for contentious multicore software transactionsProceedings of the Fourteenth EuroSys Conference 201910.1145/3302424.3303966(1-16)Online publication date: 25-Mar-2019
https://dl.acm.org/doi/10.1145/3302424.3303966
Shacham OGottesman YBergman ABortnikov EHillel EKeidar I(2018)Taking omid to the cloudsProceedings of the VLDB Endowment10.14778/3229863.322986811:12(1795-1808)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.14778/3229863.3229868
Zhang ISharma NSzekeres AKrishnamurthy APorts D(2018)Building Consistent Transactions with Inconsistent ReplicationACM Transactions on Computer Systems10.1145/326998135:4(1-37)Online publication date: 16-Dec-2018
https://dl.acm.org/doi/10.1145/3269981
Jepsen Tde Sousa LMoshref MPedone FSoulé R(2018)Infinite Resources for Optimistic Concurrency ControlProceedings of the 2018 Morning Workshop on In-Network Computing10.1145/3229591.3229597(26-32)Online publication date: 7-Aug-2018
https://dl.acm.org/doi/10.1145/3229591.3229597
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents