0

I'm reading google's bigtable paper. I noticed that in section 5.3, it says

Updates are committed to a commit log that stores redo records. Of these updates, the recently committed ones are stored in memory in a sorted buffer called a memtable; the older updates are stored in a sequence of SSTables.

What confuses me is that, according to this answer, SSTable should store the sorted key-value pairs. But from the texts quoted above, it gives me the feeling that both memtable and sstable stores update operations, instead of the actual value. So what does bigtable actually do when there comes an write request?

Marçal Garolera Huguet
  • 92
  • 5
Patrick
  • 555
  • 1
  • 6
  • 25

1 Answers1

4

According to official documentation [1]:

"A Cloud Bigtable table is sharded into blocks of contiguous rows, called tablets, to help balance the workload of queries. (Tablets are similar to HBase regions.) Tablets are stored on Colossus, Google's file system, in SSTable format. An SSTable provides a persistent, ordered immutable map from keys to values, where both keys and values are arbitrary byte strings. Each tablet is associated with a specific Cloud Bigtable node. In addition to the SSTable files, all writes are stored in Colossus's shared log as soon as they are acknowledged by Cloud Bigtable, providing increased durability."

The official documentation has a link to this document where is explained more detailed [2]:

“A "Sorted String Table" then is exactly what it sounds like, it is a file which contains a set of arbitrary, sorted key-value pairs inside. Duplicate keys are fine, there is no need for "padding" for keys or values, and keys and values are arbitrary blobs.

If we need to preserve the fast read access which SSTables give us, but we also want to support fast random writes, turns out, we already have all the necessary pieces: random writes are fast when the SSTable is in memory, that is the definition of the memtable.”

In effect, what happens during a write is the Tablet Server (Cloud Bigtable Node) generates a committed log entry describing the mutation, plus a modification to the row in the memtable. Once this memtable is too large, the entire memtable is compacted into many immutable SSTables, partitioned by locality group (column family) and then each is added to the respective stack of SSTables for each locality group.

Note that each SSTable does not contain the cell values for all rows in the locality group, only the most recent updates. Reads may need to group updates from one or many SSTables in the locality group to construct a response.

See section "5.4 Compactions" in the paper [3] for more information on how mutations may be moved around to increase performance. Furthermore, see the heading "Locality Groups" under section "6 Refinements" for more information on the implications of using locality groups.

[1] https://cloud.google.com/bigtable/docs/overview#architecture

[2] https://www.igvita.com/2012/02/06/sstable-and-log-structured-storage-leveldb/

[3] https://static.googleusercontent.com/media/research.google.com/en//archive/bigtable-osdi06.pdf

Community
  • 1
  • 1
Harif Velarde
  • 733
  • 5
  • 10