Detailed Design of Bigtable: Part I

Components

Here’s a list of major components in our Bigtable design:

• SSTable
• MemTable
• GFS
• Chubby

Let’s discuss the components of Bigtable design in detail.

SSTable

The data is kept as files in Bigtable using the Google File System (GFS), a persistent distributed file storage system. Sorted String Table, or SSTable for short, is the file format that Bigtable uses to store its data. It is a persistent, ordered, immutable map of keys to values, where both the keys and the values are random byte stringsA byte string is similar to a string, but it is a sequence of bytes instead of characters.. They are used to store the persistent state of tablets. Multiple SSTable comprise a tablet. There are operations to search up a particular key’s linked value and to loop over all key/value pairings within a defined key range. An SSTable is made up of a series of blocks, which are normally 64 KB in size but can be configured to be a different size.

When the SSTable is accessed, a block index is loaded into memory and utilized to find blocks. Single disk seek can be utilized to perform a lookup. By using a binary search to locate the correct block in the in-memory index, we then read the correct block from the disk. It is ...