Minimizing Commit Latency of Transactions in Geo-Replicated Data Stores

ABSTRACT

Cross datacenter replication is increasingly being deployed to bring data closer to the user and to overcome datacenter outages. The extent of the influence of wide-area communication on serializable transactions is not yet clear. In this work, we derive a lower-bound on commit latency. The sum of the commit latency of any two datacenters is at least the Round-Trip Time (RTT) between them. We use the insights and lessons learned while deriving the lower-bound to develop a commit protocol, called Helios, that achieves low commit latencies. Helios actively exchanges transaction logs (history) between datacenters. The received logs are used to decide whether a transaction can commit or not. The earliest point in the received logs that is needed to commit a transaction is decided by Helios to ensure a low commit latency. As we show in the paper, Helios is theoretically able to achieve the lower-bound commit latency. Also, in a real-world deployment on five datacenters, Helios has a commit latency that is close to the optimal.

References

1. Summary of the Amazon EC2 and Amazon RDS service disruption in the US East Region. http://aws.amazon.com/message/65648/, 2011. {Online; acc. 5-Oct-2011}.
2. Summary of the December 24, 2012 Amazon ELB Service Event in the US-East Region. http://aws.amazon.com/message/680587/, 2012. {Online; acc. 10-May-2013}.
3. A. Adya, R. Gruber, B. Liskov, and U. Maheshwari. Efficient optimistic concurrency control using loosely synchronized clocks. ACM SIGMOD Record, 24(2):23--34, 1995.
4. A. Adya and B. Liskov. Lazy consistency using loosely synchronized clocks. In Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, pages 73--82. ACM, 1997.
5. Apache Cassandra, 2011. {Online; acc. 5-Oct-2011}.
6. P. Bailis, A. Fekete, M. J. Franklin, A. Ghodsi, J. M. Hellerstein, and I. Stoica. Coordination avoidance in database systems. Proceedings of the VLDB Endowment, 8(3), 2014.
7. P. Bailis and A. Ghodsi. Eventual Consistency today: Limitations, extensions, and beyond. ACM Queue, 11(3):20:20--20:32, Mar. 2013.
8. P. Bailis, A. Ghodsi, J. M. Hellerstein, and I. Stoica. Bolt-on causal consistency. In SIGMOD, 2013.
9. 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 Conf. Innovative Data Systems Research, pages 223--234, 2011.
10. N. M. Belaramani, M. Dahlin, L. Gao, A. Nayate, A. Venkataramani, P. Yalagandula, and J. Zheng. Practi replication. In NSDI, volume 6, pages 5--5, 2006.
11. H. Berenson, P. Bernstein, J. Gray, J. Melton, E. O'Neil, and P. O'Neil. A critique of ansi sql isolation levels. ACM SIGMOD Record, 24(2):1--10, 1995.
12. P. Bernstein, C. Reid, and S. Das. Hyder-a transactional record manager for shared flash. In Proc. of CIDR, pages 9--20, 2011.
13. P. A. Bernstein, V. Hadzilacos, and N. Goodman. Concurrency Control and Recovery in Database Systems. Addison-Wesley, 1987.
14. B. Cooper, A. Silberstein, E. Tam, R. Ramakrishnan, and R. Sears. Benchmarking cloud serving systems with ycsb. In Proc. 1st ACM Symp. Cloud Computing, pages 143--154. ACM, 2010.
15. 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. Proc. VLDB Endow., 1(2):1277--1288, Aug. 2008.
16. J. Corbett, J. Dean, M. Epstein, A. Fikes, C. Frost, J. Furman, S. Ghemawat, A. Gubarev, C. Heiser, P. Hochschild, et al. Spanner: Google's globally-distributed database. in Proceedings of OSDI, page 1, 2012.
17. S. Das, S. Nishimura, D. Agrawal, and A. El Abbadi. Albatross: lightweight elasticity in shared storage databases for the cloud using live data migration. Proc. VLDB Endowment, 4(8):494--505, 2011.
18. K. Daudjee and K. Salem. Lazy database replication with snapshot isolation. In Proceedings of the 32nd international conference on Very large data bases, pages 715--726. VLDB Endowment, 2006.
19. G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman, A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels. Dynamo: Amazon's highly available key-value store. In Proc. 21st ACM Symp. Operating Systems Principles, pages 205--220, 2007.
20. J. Du, S. Elnikety, A. Roy, and W. Zwaenepoel. Orbe: scalable causal consistency using dependency matrices and physical clocks. In Proceedings of the 4th annual Symposium on Cloud Computing, page 11. ACM, 2013.
21. J. Du, S. Elnikety, and W. Zwaenepoel. Clock-si: Snapshot isolation for partitioned data stores using loosely synchronized clocks. In Reliable Distributed Systems (SRDS), 2013 IEEE 32nd International Symposium on, pages 173--184. IEEE, 2013.
22. J. Du, C. Iorgulescu, A. Roy, and W. Zwaenepoel. Gentlerain: Cheap and scalable causal consistency with physical clocks. In Proceedings of the ACM Symposium on Cloud Computing, pages 1--13. ACM, 2014.
23. L. Glendenning, I. Beschastnikh, A. Krishnamurthy, and T. Anderson. Scalable consistency in scatter. In Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles, SOSP '11, pages 15--28, New York, NY, USA, 2011. ACM.
24. L. Glendenning, I. Beschastnikh, A. Krishnamurthy, and T. Anderson. Scalable consistency in scatter. In Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles, pages 15--28. ACM, 2011.
25. HBase. http://hbase.apache.org, 2011. {Online; acc. 18-Jul-2011}.
26. B. Kemme, R. Jimenez-Peris, and M. Patino-Martinez. Database replication. Synthesis Lectures on Data Management, 2(1):1--153, 2010.
27. T. Kraska, G. Pang, M. J. Franklin, S. Madden, and A. Fekete. Mdcc: Multi-data center consistency. In Proceedings of the 8th ACM European Conference on Computer Systems, pages 113--126. ACM, 2013.
28. R. Ladin, B. Liskov, L. Shrira, and S. Ghemawat. Providing high availability using lazy replication. ACM Transactions on Computer Systems (TOCS), 10(4):360--391, 1992.
29. L. Lamport. Time, clocks, and the ordering of events in a distributed system. Commun. ACM, 21(7):558--565, July 1978.
30. L. Lamport. The part-time parliament. ACM Trans. Computer Systems, 16(2):133--169, May 1998.
31. L. Lamport. Paxos made simple. ACM SIGACT News, 32(4):18--25, December 2001.
32. L. Lamport. Fast paxos. Distributed Computing, 19(2):79--103, 2006.
33. Y. Lin, B. Kemme, M. Patiño-Martínez, and R. Jiménez-Peris. Middleware based data replication providing snapshot isolation. In Proceedings of the 2005 ACM SIGMOD international conference on Management of data, pages 419--430. ACM, 2005.
34. Y. Lin, B. Kemme, M. Patino-Martinez, and R. Jimenez-Peris. Enhancing edge computing with database replication. In Reliable Distributed Systems, 2007. SRDS 2007. 26th IEEE International Symposium on, pages 45--54. IEEE, 2007.
35. B. Liskov. Practical uses of synchronized clocks in distributed systems. Distributed Computing, 6(4):211--219, 1993.
36. 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 Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles, pages 401--416. ACM, 2011.
37. W. Lloyd, M. J. Freedman, M. Kaminsky, and D. G. Andersen. Stronger semantics for low-latency geo-replicated storage. In Symposium on Networked Systems Design and Implementation, 2013.
38. H. Mahmoud, F. Nawab, A. Pucher, D. Agrawal, and A. El Abbadi. Low-latency multi-datacenter databases using replicated commits. Proceedings of the VLDB Endowment, 6(9), 2013.
39. R. Miller. Massive Flooding Damages Several NYC Data Centers. http://www.datacenterknowledge.com/archives/2012/10/30/major-flooding-nyc-data-centers/, 10 2012. {Online; acc. 10-May-2013}.
40. F. Nawab, D. Agrawal, and A. El Abbadi. Message futures: Fast commitment of transactions in multi-datacenter environments. In Conf. Innovative Data Systems Research, 2013.
41. F. Nawab, V. Arora, D. Agrawal, and A. E. Abbadi. Chariots: A scalable shared log for data management in multi-datacenter cloud environments. In EDBT, 2015.
42. D. Obasanjo. When databases lie: Consistency vs. availability in distributed systems, 2009.
43. D. Ongaro, S. M. Rumble, R. Stutsman, J. Ousterhout, and M. Rosenblum. Fast crash recovery in ramcloud. In Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles, pages 29--41. ACM, 2011.
44. S. Patterson, A. J. Elmore, F. Nawab, D. Agrawal, and A. E. Abbadi. Serializability, not serial: Concurrency control and availability in multi-datacenter datastores. PVLDB, 5(11):1459--1470, 2012.
45. K. Petersen, M. J. Spreitzer, D. B. Terry, M. M. Theimer, and A. J. Demers. Flexible update propagation for weakly consistent replication, volume 31. ACM, 1997.
46. E. Schurman and J. Brutlag. Performance related changes and their user impact. In velocity web performance and operations conference, 2009.
47. Y. Sovran, R. Power, M. K. Aguilera, and J. Li. Transactional storage for geo-replicated systems. In Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles, pages 385--400. ACM, 2011.
48. D. B. Terry, V. Prabhakaran, R. Kotla, M. Balakrishnan, M. K. Aguilera, and H. Abu-Libdeh. Consistency-based service level agreements for cloud storage. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, pages 309--324. ACM, 2013.
49. D. B. Terry, M. M. Theimer, K. Petersen, A. J. Demers, M. J. Spreitzer, and C. H. Hauser. Managing update conflicts in Bayou, a weakly connected replicated storage system, volume 29. ACM, 1995.
50. A. Thomson, T. Diamond, S.-C. Weng, K. Ren, P. Shao, and D. J. Abadi. Calvin: fast distributed transactions for partitioned database systems. In Proceedings of the 2012 international conference on Management of Data, pages 1--12. ACM, 2012.
51. H. T. Vo, S. Wang, D. Agrawal, G. Chen, and B. C. Ooi. Logbase: a scalable log-structured database system in the cloud. Proceedings of the VLDB Endowment, 5(10):1004--1015, 2012.
52. Z. Wu, M. Butkiewicz, D. Perkins, E. Katz-Bassett, and H. V. Madhyastha. Spanstore: cost-effective geo-replicated storage spanning multiple cloud services. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, pages 292--308. ACM, 2013.
53. G. T. Wuu and A. J. Bernstein. Efficient solutions to the replicated log and dictionary problems. In Proceedings of the third annual ACM symposium on Principles of distributed computing, PODC '84, pages 233--242, New York, NY, USA, 1984. ACM.
54. 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 Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, pages 276--291. ACM, 2013.

Index Terms

• Information systems

  • Data management systems

    • Database management system engines

      • Database transaction processing

      • Parallel and distributed DBMSs