Serializability, not serial: concurrency control and availability in multi-datacenter datastores

Abstract

We present a framework for concurrency control and availability in multi-datacenter datastores. While we consider Google's Megastore as our motivating example, we define general abstractions for key components, making our solution extensible to any system that satisfies the abstraction properties. We first develop and analyze a transaction management and replication protocol based on a straightforward implementation of the Paxos algorithm. Our investigation reveals that this protocol acts as a concurrency prevention mechanism rather than a concurrency control mechanism. We then propose an enhanced protocol called Paxos with Combination and Promotion (Paxos-CP) that provides true transaction concurrency while requiring the same per instance message complexity as the basic Paxos protocol. Finally, we compare the performance of Paxos and Paxos-CP in a multi-datacenter experimental study, and we demonstrate that Paxos-CP results in significantly fewer aborted transactions than basic Paxos.

References

1. Amazon SimpleDB. http://aws.amazon.com/simpledb. {Accessed: 5-Oct-2011}.
2. 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.
3. P. Bernstein, I. Cseri, N. Dani, N. Ellis, A. Kalhan, G. Kakivaya, D. Lomet, R. Manne, L. Novik, and T. Talius. Adapting Microsoft SQL Server for cloud computing. In ICDE, pages 1255--1263, 2011.
4. P. A. Bernstein, V. Hadzilacos, and N. Goodman. Concurrency Control and Recovery in Database Systems. Addison-Wesley, 1987.
5. M. Butcher. Amazon EC2 goes down, taking with it Reddit, Foursquare and Quora. http://eu.techcrunch.com/2011/04/21/amazon-ec2-goes-down-taking-with-it-reddit-foursquare-and-quora/, April 2011. {Accessed: 5-Oct-2011}.
6. B. Calder, J. Wang, A. Ogus, N. Nilakantan, A. Skjolsvold, S. McKelvie, Y. Xu, S. Srivastav, J. Wu, H. Simitci, et al. Windows Azure Storage: A highly available cloud storage service with strong consistency. In SOSP, pages 143--157, 2011.
7. T. D. Chandra, R. Griesemer, and J. Redstone. Paxos made live: an engineering perspective. In PODC, pages 398--407, 2007.
8. 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, pages 15--28, 2006.
9. B. Cooper, A. Silberstein, E. Tam, R. Ramakrishnan, and R. Sears. Benchmarking cloud serving systems with ycsb. In SOCC, pages 143--154, 2010.
10. 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.
11. S. Das, D. Agrawal, and A. El Abbadi. Elastras: An elastic transactional data store in the cloud. In HotCloud, 2009.
12. 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 Endow., 4(8):494--505, 2011.
13. X. Défago, A. Schiper, and P. Urbán. Total order broadcast and multicast algorithms: Taxonomy and survey. ACM Comput. Surveys, 36(4):372--421, 2004.
14. S. Ghemawat, H. Gobioff, and S.-T. Leung. The google file system. In SOSP, pages 29--43, 2003.
15. A. Greene. Lightning strike causes Amazon, Microsoft cloud outage in Europe. TechFlash, August 2011.
16. HBase. http://hbase.apache.org. {Accessed: 18-Jul-2011}.
17. P. Hunt, M. Konar, F. P. Junqueira, and B. Reed. ZooKeeper: wait-free coordination for internet-scale systems. In USENIX, 2010.
18. L. Lamport. The part-time parliament. ACM Trans. Computer Systems, 16(2):133--169, 1998.
19. L. Lamport. Paxos made simple. ACM SIGACT News, 32(4):18--25, 2001.
20. K. Muthukkaruppan. The underlying technology of messages. http://www.facebook.com/notes/facebook-engineering/the-underlying-technology-of-messages/454991608919, 2011. {Accessed: 5-Oct-2011}.
21. S. Patterson, A. J. Elmore, F. Nawab, D. Agrawal, and A. El Abbadi. Serializability, not serial: Concurrency control and availability in multi-datacenter datastores. Technical Report 2012--04, University of California, Santa Barbara, 2012.
22. J. Rao, E. J. Shekita, and S. Tata. Using Paxos to build a scalable, consistent, and highly available datastore. Proc. VLDB Endow., 4:243--254, 2011.
23. B. Reed and F. P. Junqueira. A simple totally ordered broadcast protocol. In LADIS, pages 2:1--2:6, 2008.
24. Summary of the Amazon EC2 and Amazon RDS service disruption in the US East Region. http://aws.amazon.com/message/65648/, 2011. {Accessed: 5-Oct-2011}.
25. R. van Renesse. Paxos made moderately complex. http://www.cs.cornell.edu/courses/cs7412/2011sp/paxos.pdf. {Accessed: 28-Jun-2012}.