strong consistency and transactional correctness guarantees. It achieves these properties using a batch-oriented
interface, guaranteeing atomicity of updates by introducing transient versioning of data that eliminates the
need for lock-based synchronization of query and update
transactions. Mesa is geo-replicated across multiple datacenters for increased fault-tolerance. Finally, within each
datacenter, Mesa’s controller/worker framework allows it
to distribute work and dynamically scale the required computation over a large number of machines to provide high
We would like to thank everyone who has served on the Mesa
team, including former team members Karthik Lakshmi-narayanan, Sanjay Agarwal, Sivasankaran Chandrasekar,
Justin Tolmer, Chip Turner, and Michael Ballbach, for their
substantial contributions to the design and development
of Mesa. We are also grateful to Sridhar Ramaswamy for
providing strategic vision and guidance to the Mesa team.
Finally, we thank the anonymous reviewers, whose feedback
significantly improved the paper.
Ashish Gupta, Fan Yang, Jason Govig,
Adam Kirsch, Kelvin Chan, Kevin Lai,
Shuo Wu, Sandeep Dhoot, Abhilash
Rajesh Kumar, Ankur Agiwal,
Sanjay Bhansali, Mingsheng Hong,
Jamie Cameron, Masood Siddiqi,
David Jones, Jeff Shute, Andrey
Gubarev, Shivakumar Venkataraman,
and Divyakant Agrawal, Google, Inc.,
Mountain View, CA.
A distributed storage system for
structured data. In OSDI (2006). 205–218.
4. Cohen, J., Eshleman, J., et al.
Online expansion of largescale data
warehouses. PVLDB 4, 12 (2011),
5. Corbett, J.C., Dean, J., et al. Spanner:
database. In OSDI (2012). 251–264.
6. Dean, J., Ghemawat, S. MapReduce:
Simplified data processing on large
clusters. Commun. ACM 51, 1 (2008),
7. Fikes, A. Storage architecture and
challenges. http://goo.gl/pF6kmz, 2010.
8. Glendenning, L., Beschastnikh, I., et al.
Scalable consistency in scatter. In
SOSP (2011). 15–28.
9. Gupta, A., Yang, F., et al. Mesa: Geo-replicated, near real-time, scalable
data warehousing. In VLDB (2014).
10. Lamb, A., Fuller, M., et al. The Vertica
analytic database: C-Store 7 years
later. PVLDB 5, 12 (2012), 1790–1801.
11. Lamport, L. The part-time parliament.
ACM Trans. Comput. Syst. 16, 2
12. Lee, G., Lin, J., et al. The unified
logging infrastructure for data
analytics at Twitter. PVLDB 5, 12
13. Project Voldemort: A Distributed
14. SAP HANA. http://www.saphana.com/
15. Shute, J., Vingralek, R., et al. F1:
A distributed SQL database
that scales. PVLDB 6, 11 (2013),
16. Thusoo, A., Shao, Z., et al. Data
warehousing and analytics
infrastructure at Facebook. In
SIGMOD (2010). 1013–1020.
17. Weiss, R. A technical overview of the
oracle exadata database machine and
exadata storage server. Oracle White
Paper. Oracle Corporation, Redwood
1. Abouzeid, A., Bajda-Pawlikowski, K.,
et al. HadoopDB: An architectural
hybrid of MapReduce and DBMS
technologies for analytical workloads.
PVLDB 2, 1 (2009), 922–933.
2. Baker, J., Bond, C., et al. Megastore:
Providing scalable, highly
available storage for interactive
services. In CIDR (2011).
3. Chang, F., Dean, J., et al. Bigtable:
Copyright held by authors/owner.
ACM Transactions on Interactive
Intelligent Systems (TIIS). This
quarterly journal publishes papers
on research encompassing the
design, realization, or evaluation of
interactive systems incorporating
some form of machine intelligence.
World-Renowned Journals from ACM
ACM publishes over 50 magazines and journals that cover an array of established as well as emerging areas of the computing field.
IT professionals worldwide depend on ACM's publications to keep them abreast of the latest technological developments and industry
news in a timely, comprehensive manner of the highest quality and integrity. For a complete listing of ACM's leading magazines & journals,
including our renowned Transaction Series, please visit the ACM publications homepage: www.acm.org/pubs.
PLEASE CONTACT ACM MEMBER
SERVICES TO PLACE AN ORDER
Phone: 1.800.342.6626 (U.S. and Canada)
+ 1.212.626.0500 (Global)
Fax: + 1.212.944.1318
(Hours: 8:30am–4:30pm, Eastern Time)
Mail: ACM Member Services
General Post Office
PO Box 30777
New York, NY 10087-0777 USA
ACM Transactions on Computation
Theory (ToCT). This quarterly peer-reviewed journal has an emphasis
on computational complexity, foundations of cryptography and other
computation-based topics in theoretical computer science.
PUBS_halfpage_Ad.indd 1 6/7/12 11:38AM