Bigtable: A Distributed Storage System for Structured Data

ABSTRACT

Bigtable is a distributed storage system for managing structured data that is designed to scale to a very large size: petabytes of data across thousands of commodity servers. Many projects at Google store data in Bigtable, including web indexing, Google Earth, and Google Finance. These applications place very different demands on Bigtable, both in terms of data size (from URLs to web pages to satellite imagery) and latency requirements (from backend bulk processing to real-time data serving). Despite these varied demands, Bigtable has successfully provided a flexible, high-performance solution for all of these Google products. In this article, we describe the simple data model provided by Bigtable, which gives clients dynamic control over data layout and format, and we describe the design and implementation of Bigtable.

REFERENCES

• 1: Daniel Abadi , Samuel Madden , Miguel Ferreira, Integrating compression and execution in column-oriented database systems, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142548]
• 2: Anastassia Ailamaki , David J. DeWitt , Mark D. Hill , Marios Skounakis, Weaving Relations for Cache Performance, Proceedings of the 27th International Conference on Very Large Data Bases, p.169-180, September 11-14, 2001
• 3: Gaurav Banga , Peter Druschel , Jeffrey C. Mogul, Resource containers: a new facility for resource management in server systems, Proceedings of the third symposium on Operating systems design and implementation, p.45-58, February 1999, New Orleans, Louisiana, United States
• 4: C. K. Baru , G. Fecteau , A. Goyal , H. Hsiao , A. Jhingran , S. Padmanabhan , G. P. Copeland , W. G. Wilson, DB2 parallel edition, IBM Systems Journal, v.34 n.2, p.292-322, 1995
• 5: Andy Bavier , Mic Bowman , Brent Chun , David Culler , Scott Karlin , Steve Muir , Larry Peterson , Timothy Roscoe , Tammo Spalink , Mike Wawrzoniak, Operating system support for planetary-scale network services, Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation, p.19-19, March 29-31, 2004, San Francisco, California
• 6: Jon Bentley , Douglas McIlroy, Data Compression Using Long Common Strings, Proceedings of the Conference on Data Compression, p.287, March 29-31, 1999
• 7: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 8: Mike Burrows, The Chubby lock service for loosely-coupled distributed systems, Proceedings of the 7th symposium on Operating systems design and implementation, November 06-08, 2006, Seattle, Washington
• 9: Tushar D. Chandra , Robert Griesemer , Joshua Redstone, Paxos made live: an engineering perspective, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, p.398-407, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281103]
• 10: Fay Chang , Jeffrey Dean , Sanjay Ghemawat , Wilson C. Hsieh , Deborah A. Wallach , Mike Burrows , Tushar Chandra , Andrew Fikes , Robert E. Gruber, Bigtable: a distributed storage system for structured data, Proceedings of the 7th symposium on Operating systems design and implementation, November 06-08, 2006, Seattle, Washington
• 11: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• 12: George Copeland , William Alexander , Ellen Boughter , Tom Keller, Data placement in Bubba, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.99-108, June 01-03, 1988, Chicago, Illinois, United States
• 13: Jeffrey Dean , Sanjay Ghemawat, MapReduce: simplified data processing on large clusters, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.10-10, December 06-08, 2004, San Francisco, CA
• 14: David J DeWitt , Randy H Katz , Frank Olken , Leonard D Shapiro , Michael R Stonebraker , David Wood, Implementation techniques for main memory database systems, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 15: David DeWitt , Jim Gray, Parallel database systems: the future of high performance database systems, Communications of the ACM, v.35 n.6, p.85-98, June 1992 [doi>10.1145/129888.129894]
• 16: Clark D. French, “One size fits all” database architectures do not work for DSS, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.449-450, May 22-25, 1995, San Jose, California, United States
• 17: Gawlick, D. and Kinkade, D. 1985. Varieties of concurrency control in IMS/VS fast path. Datab. Eng. Bull. 8, 2, 3--10.
• 18: Sanjay Ghemawat , Howard Gobioff , Shun-Tak Leung, The Google file system, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 19: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• 20: Rick Greer, Daytona and the fourth-generation language Cymbal, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.525-526, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 21: R. Hagmann, Reimplementing the Cedar file system using logging and group commit, Proceedings of the eleventh ACM Symposium on Operating systems principles, p.155-162, November 08-11, 1987, Austin, Texas, United States
• 22: John H. Hartman , John K. Ousterhout, The Zebra striped network file system, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.29-43, December 05-08, 1993, Asheville, North Carolina, United States
• 23: kx.com. kx.com/products/database.php. Product page.
• 24: Leslie Lamport, The part-time parliament, ACM Transactions on Computer Systems (TOCS), v.16 n.2, p.133-169, May 1998 [doi>10.1145/279227.279229]
• 25: John MacCormick , Nick Murphy , Marc Najork , Chandramohan A. Thekkath , Lidong Zhou, Boxwood: abstractions as the foundation for storage infrastructure, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.8-8, December 06-08, 2004, San Francisco, CA
• 26: John McCarthy, Recursive functions of symbolic expressions and their computation by machine, Part I, Communications of the ACM, v.3 n.4, p.184-195, April 1960 [doi>10.1145/367177.367199]
• 27: Patrick O'Neil , Edward Cheng , Dieter Gawlick , Elizabeth O'Neil, The log-structured merge-tree (LSM-tree), Acta Informatica, v.33 n.4, p.351-385, 1996 [doi>10.1007/s002360050048]
• 28: oracle.com. www.oracle.com/technology/products/database/clustering/index.html. Product page.
• 29: Rob Pike , Sean Dorward , Robert Griesemer , Sean Quinlan, Interpreting the data: Parallel analysis with Sawzall, Scientific Programming, v.13 n.4, p.277-298, October 2005
• 30: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 31: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 32: sensage.com. sensage.com/products-sensage.htm. Product page.
• 33: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 34: Stonebraker, M. 1986. The case for shared nothing. Datab. Eng. Bull. 9, 1 (Mar.), 4--9.
• 35: Mike Stonebraker , Daniel J. Abadi , Adam Batkin , Xuedong Chen , Mitch Cherniack , Miguel Ferreira , Edmond Lau , Amerson Lin , Sam Madden , Elizabeth O'Neil , Pat O'Neil , Alex Rasin , Nga Tran , Stan Zdonik, C-store: a column-oriented DBMS, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 36: Michael Stonebraker , Paul M. Aoki , Robert Devine , Witold Litwin , Michael A. Olson, Mariposa: A New Architecture for Distributed Data, Proceedings of the Tenth International Conference on Data Engineering, p.54-65, February 14-18, 1994
• 37: sybase.com. www.sybase.com/products/databaseservers/sybaseiq. Product page.
• 38: Ben Y. Zhao , John D. Kubiatowicz , Anthony D. Joseph, Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and, University of California at Berkeley, Berkeley, CA, 2001
• 39: Zukowski, M., Boncz, P. A., Nes, N., and Heman, S. 2005. MonetDB/X100 --- A DBMS in the CPU cache. IEEE Data Eng. Bull. 28, 2, 17--22.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed databases

General Terms:
Design

Keywords:
Large-Scale Distributed Storage