Bigtable is a compressed, high performance, proprietary data storage system built on Google File System, Chubby Lock Service, SSTable (log-structured storage like LevelDB) and a few other Google technologies. On May 6, 2015, a public version of Bigtable was made available as a service. Bigtable also underlies Google Cloud Datastore, which is available as a part of the Google Cloud Platform.^[1][2]

History[edit]

Bigtable development began in 2004^[3] and is now used by a number of Google applications, such as web indexing,^[4]MapReduce, which is often used for generating and modifying data stored in Bigtable,^[5]Google Maps,^[6]Google Book Search, "My Search History", Google Earth, Blogger.com, Google Code hosting, YouTube,^[7] and Gmail.^[8] Google's reasons for developing its own database include scalability and better control of performance characteristics.^[9]

Google's Spanner RDBMS is layered on an implementation of Bigtable with a Paxos group for two-phase commits to each table. Google F1 was built using Spanner to replace an implementation based on MySQL.^[10]

Design[edit]

Bigtable is one of the prototypical examples of a wide column store. It maps two arbitrary string values (row key and column key) and timestamp (hence three-dimensional mapping) into an associated arbitrary byte array. It is not a relational database and can be better defined as a sparse, distributed multi-dimensional sorted map.^[4]:1 Bigtable is designed to scale into the petabyte range across "hundreds or thousands of machines, and to make it easy to add more machines [to] the system and automatically start taking advantage of those resources without any reconfiguration".^[11]

Each table has multiple dimensions (one of which is a field for time, allowing for versioning and garbage collection). Tables are optimized for Google File System (GFS) by being split into multiple tablets – segments of the table are split along a row chosen such that the tablet will be ~200 megabytes in size. When sizes threaten to grow beyond a specified limit, the tablets are compressed using the algorithm BMDiff^[12][13] and the Zippy compression algorithm^[14] publicly known and open-sourced as Snappy,^[15] which is a less space-optimal variation of LZ77 but more efficient in terms of computing time. The locations in the GFS of tablets are recorded as database entries in multiple special tablets, which are called "META1" tablets. META1 tablets are found by querying the single "META0" tablet, which typically resides on a server of its own since it is often queried by clients as to the location of the "META1" tablet which itself has the answer to the question of where the actual data is located. Like GFS's master server, the META0 server is not generally a bottleneck since the processor time and bandwidth necessary to discover and transmit META1 locations is minimal and clients aggressively cache locations to minimize queries.

See also[edit]

• Big data


• Distributed data store


• Dynamo (storage system)


• Wide column store

References[edit]

Bibliography[edit]

• 
  Chang, Fay; Dean, Jeffrey; Ghemawat, Sanjay; Hsieh, Wilson C.; Wallach, Deborah A.; Burrows, Mike; Chandra, Tushar; Fikes, Andrew; Gruber, Robert E. (2006), "Bigtable: A Distributed Storage System for Structured Data", (download ebook) (PDF), Google.

External links[edit]

• 
  Bigtable: A Distributed Structured Storage System, Washington. Video, Google.
  
  
  
  • 
    UWTV, archived from the original (video) on 15 June 2006.
  
  
  • 
    Witchcock, Andrew, Google's Bigtable (notes on the official presentation).
  
  
  
  


• 
  Carr, David F (2006-07-06), "How Google Works", Baseline.


• 
  "Is the Relational Database Doomed?", Read-write web.