BigTable
Encyclopedia
BigTable is a compressed
, high performance, and proprietary
database system
built on Google File System
(also known as the "GFS"), Chubby Lock Service, SSTable
and a few other Google
technologies; it is currently not distributed nor is it used outside of Google, although Google offers access to it as part of their Google App Engine
.
, which is often used for generating and modifying data stored in BigTable, Google Reader
, Google Maps
, Google Book Search
, "My Search History", Google Earth
, Blogger.com, Google Code
hosting, Orkut
, YouTube
, and Gmail
. Google's reasons for developing its own database include scalability and better control of performance characteristics.
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".
Each table
has multiple dimensions (one of which is a field
for time, allowing for versioning and garbage collection
). Tables are optimized for GFS by being split into multiple tablets - segments of the table as split along a row chosen such that the tablet will be ~200 megabyte
s in size. When sizes threaten to grow beyond a specified limit, the tablets are compressed using the algorithm BMDiff (referenced in ) and the Zippy compression algorithm publicly known and open-sourced as Snappy
, 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, bandwidth necessary to discover and transmit META1 locations is minimal and clients aggressively cache locations to minimize queries.
Data compression
In computer science and information theory, data compression, source coding or bit-rate reduction is the process of encoding information using fewer bits than the original representation would use....
, high performance, and proprietary
Proprietary software
Proprietary software is computer software licensed under exclusive legal right of the copyright holder. The licensee is given the right to use the software under certain conditions, while restricted from other uses, such as modification, further distribution, or reverse engineering.Complementary...
database system
Database management system
A database management system is a software package with computer programs that control the creation, maintenance, and use of a database. It allows organizations to conveniently develop databases for various applications by database administrators and other specialists. A database is an integrated...
built on Google File System
Google File System
Google File System is a proprietary distributed file system developed by Google Inc. for its own use. It is designed to provide efficient, reliable access to data using large clusters of commodity hardware...
(also known as the "GFS"), Chubby Lock Service, SSTable
SSTable
SSTable is an on-disk file format that represents a string-to-string mapping. It is an immutable system so that once written, the map remains unchanged....
and a few other Google
Google
Google Inc. is an American multinational public corporation invested in Internet search, cloud computing, and advertising technologies. Google hosts and develops a number of Internet-based services and products, and generates profit primarily from advertising through its AdWords program...
technologies; it is currently not distributed nor is it used outside of Google, although Google offers access to it as part of their Google App Engine
Google App Engine
Google App Engine is a platform as a service cloud computing platform for developing and hosting web applications in Google-managed data centers. It virtualizes applications across multiple servers,...
.
History
BigTable development began in 2004 and is now used by a number of Google applications, such as MapReduceMapReduce
MapReduce is a software framework introduced by Google in 2004 to support distributed computing on large data sets on clusters of computers. Parts of the framework are patented in some countries....
, which is often used for generating and modifying data stored in BigTable, Google Reader
Google Reader
Google Reader is a Web-based aggregator, capable of reading Atom and RSS feeds online or offline. It was released by Google on October 7, 2005 through Google Labs. Reader was graduated from beta status on September 17, 2007.-Interface:...
, Google Maps
Google Maps
Google Maps is a web mapping service application and technology provided by Google, free , that powers many map-based services, including the Google Maps website, Google Ride Finder, Google Transit, and maps embedded on third-party websites via the Google Maps API...
, Google Book Search
Google Book Search
Google Books is a service from Google that searches the full text of books that Google has scanned, converted to text using optical character recognition, and stored in its digital database. The service was formerly known as Google Print when it was introduced at the Frankfurt Book Fair in October...
, "My Search History", Google Earth
Google Earth
Google Earth is a virtual globe, map and geographical information program that was originally called EarthViewer 3D, and was created by Keyhole, Inc, a Central Intelligence Agency funded company acquired by Google in 2004 . It maps the Earth by the superimposition of images obtained from satellite...
, Blogger.com, Google Code
Google Code
Google Code is Google's site for developer tools, APIs and technical resources. The site contains documentation on using Google developer tools and APIs—including discussion groups and blogs for developers using Google's developer products....
hosting, Orkut
Orkut
Orkut is a social networking website that is owned and operated by Google Inc. The service is designed to help users meet new and old friends and maintain existing relationships...
, YouTube
YouTube
YouTube is a video-sharing website, created by three former PayPal employees in February 2005, on which users can upload, view and share videos....
, and Gmail
Gmail
Gmail is a free, advertising-supported email service provided by Google. Users may access Gmail as secure webmail, as well via POP3 or IMAP protocols. Gmail was launched as an invitation-only beta release on April 1, 2004 and it became available to the general public on February 7, 2007, though...
. Google's reasons for developing its own database include scalability and better control of performance characteristics.
Design
BigTable 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. BigTable is designed to scale into the petabytePetabyte
A petabyte is a unit of information equal to one quadrillion bytes, or 1000 terabytes. The unit symbol for the petabyte is PB...
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".
Each table
Table (database)
In relational databases and flat file databases, a table is a set of data elements that is organized using a model of vertical columns and horizontal rows. A table has a specified number of columns, but can have any number of rows...
has multiple dimensions (one of which is a field
Field (computer science)
In computer science, data that has several parts can be divided into fields. Relational databases arrange data as sets of database records, also called rows. Each record consists of several fields; the fields of all records form the columns....
for time, allowing for versioning and garbage collection
Garbage collection (computer science)
In computer science, garbage collection is a form of automatic memory management. The garbage collector, or just collector, attempts to reclaim garbage, or memory occupied by objects that are no longer in use by the program...
). Tables are optimized for GFS by being split into multiple tablets - segments of the table as split along a row chosen such that the tablet will be ~200 megabyte
Megabyte
The megabyte is a multiple of the unit byte for digital information storage or transmission with two different values depending on context: bytes generally for computer memory; and one million bytes generally for computer storage. The IEEE Standards Board has decided that "Mega will mean 1 000...
s in size. When sizes threaten to grow beyond a specified limit, the tablets are compressed using the algorithm BMDiff (referenced in ) and the Zippy compression algorithm publicly known and open-sourced as Snappy
Snappy
Snappy is a fast compression and decompression library based on LZ77's ideas developed by Google. It was designed to be very fast and stable, but not to achieve a high compression ratio. Compression speed is 250 MB/s and decompression speed is 500 MB/s using a single threaded, 64-bit Core i7...
, 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
Bottleneck
A bottleneck is a phenomenon where the performance or capacity of an entire system is limited by a single or limited number of components or resources. The term bottleneck is taken from the 'assets are water' metaphor. As water is poured out of a bottle, the rate of outflow is limited by the width...
since the processor time, bandwidth necessary to discover and transmit META1 locations is minimal and clients aggressively cache locations to minimize queries.
Other similar software
- Apache Cassandra — brings together Dynamo's fully distributed design and BigTable's data model. Written in Java.
- HBaseHBaseHBase is an open source, non-relational, distributed database modeled after Google's BigTable and is written in Java. It is developed as part of Apache Software Foundation's Apache Hadoop project and runs on top of HDFS , providing BigTable-like capabilities for Hadoop...
— Written in Java. Provides BigTable-like support on the HadoopHadoopApache Hadoop is a software framework that supports data-intensive distributed applications under a free license. It enables applications to work with thousands of nodes and petabytes of data...
Core. - HypertableHypertableHypertable is an open source database inspired by publications on the design of Google's BigTable. The project is based on experience of engineers who were solving large-scale data-intensive tasks for many years....
— Hypertable is designed to manage the storage and processing of information on a large cluster of commodity servers. - KDI — KosmixKosmixKosmix was an American privately held company in Mountain View, California. Their website earned revenue from advertising related to its categorization engine. The engine organizes the Internet into topic pages allowing users to explore the Web by topic, "presenting a dashboard of relevant videos,...
attempt to make a BigTable clone. Written in C++. - LevelDBLevelDBLevelDB is an open source on-disk key-value store written by Google Fellows Jeffrey Dean and Sanjay Ghemawat, who built parts of Google's platform...
- Google's embedded key/value store that uses similar design concepts as the BigTable Tablet
See also
- Amazon SimpleDBAmazon SimpleDBAmazon SimpleDB is a distributed database written in Erlang by Amazon.com. It is used as a web service in concert with Amazon Elastic Compute Cloud and Amazon S3 and is part of Amazon Web Services. It was announced on December 13, 2007....
- Big dataBig dataBig data are datasets that grow so large that they become awkward to work with using on-hand database management tools. Difficulties include capture, storage, search, sharing, analytics, and visualizing...
- Distributed data storeDistributed data storeA distributed data store is a blurred concept and means either a distributed database where users store their information on a number of nodes, or a network in which a user stores their information on a number of peer network nodes ....
s, an overview - Dynamo (storage system)Dynamo (storage system)Dynamo is a highly available, proprietary key-value structured storage system or a distributed data store. It has properties of both databases and distributed hash tables...
- Column-oriented DBMSColumn-oriented DBMSA column-oriented DBMS is a database management system that stores its content by column rather than by row. This has advantages for data warehouses and library catalogues where aggregates are computed over large numbers of similar data items....
- HadoopHadoopApache Hadoop is a software framework that supports data-intensive distributed applications under a free license. It enables applications to work with thousands of nodes and petabytes of data...
External links
- Bigtable: A Distributed Storage System for Structured Data -(official paper; PDF)
- BigTable: A Distributed Structured Storage System (video)
- more video
- Google's BigTable -(notes on the official presentation)
- "How Google Works"
- Is the Relational Database Doomed?