# Bigtable

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

## Why Bigtable?

* Non-relational
  * flexible schema, unlimited columns
* Highly scalable
  * low latency: \~10ms in-memory reads, 100ms disk read
  * high throughput: 10k qps
* Not good for
  * relational data
  * transaction
  * small dataset

## Data model

* Flexible schema (Semi-structured/Sparse)
  * Number of ColumnFamily is limited, but # of column is unlimited
  * One can store data in column names
  * Sparse: if a row doesn't have value(cell) for a column, that cell is not stored at all.
* RowKey + ColumnFamily:ColumnName + VersionTimestamp identify a value: `(row:string, column:string, time:int64) → string`
  * The Bigtable is mapped onto SSTables with a key that consists of (row, column, timestamp)
* Row ordering
  * key on SSTable: `RowKey - ColumnFamily - ColumnName - Timestamp`
  * 1\) RowKey: sorted lexicographically in ascending order (A->Z)
  * 2\) ColumnFamily: unsorted
  * 3\) Columns: ascending sorted within a ColumnFamily
  * 4\) Timestamp: latest -> oldest
* Column
  * ColumnName format: FamilyName:ColumnName, column name is a string with 0 or more characters. When the length is 0, it is a default column, e.g. `FamilyName:`
  * FamilyName stored as numeric value, so doesn't impact storage too much. But column name will impact storage.
  * ColumnFamily: unique, limited to 100
    * smallest granularity for: data type restriction, replication, ACL, Garbage collection
* Some technical details
  * Row data size limit
    * RowKey: 64kb limit, also used for index(METADATA table)
    * row data: around 200MB
    * single version of a cell: 100MB

![](https://3398971849-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-M9HSM8Jn9nrPTh34ajG%2Fuploads%2Fgit-blob-1c46d36512b9cf18c14ecf9dda0237fd625fa039%2Fimage.png?alt=media)

* Tablet
  * a tablet holds a range of row key, at least 1 row
  * consists of 0 or more SSTable
    * one locality group is stored together in a SSTable
  * a table starts with 1 tablet, and split up (by tablet server) as data grows

![](https://3398971849-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-M9HSM8Jn9nrPTh34ajG%2Fuploads%2Fgit-blob-9482146d4745e66a621dd961843373c98aec308e%2Fimage.png?alt=media)

## Architecture

* Chubby:
  * bookeeping live tablet servers(stored in small file)
    * initial tablet server lookup
    * start/kill a tablet server
  * Handle metadat operation, e.g. create/update table
  * master election, if there are multiple masters in a Bigtable cell
* Master server
  * health check tablet server
  * assign tablets
  * handle garbage collection
  * client rarely interact with master
* Tablet server
  * server multiple tablets, from 10 to 10k.
  * split tablet when data grows over limit (1GB by default)
  * if a sever becomes too hot, it shifts some tablets to other servers, to distribute the load
  * in memory
    * block cache: recently read SSTable blocks
    * memtable: holds recent mutations
    * bloom filter: one per locality group. if bloom filter returns false, the data is not there.
    * `in-memory` locality group: speed up read
* GFS: file system to store actual data(SSTable). Tablet servers do not store data in local disk, other than caching in memory.
* Tablet
  * essentially a slice of a table, consists of multiple SSTables (stored in GFS)
  * unit for load balancing accross servers
* Client: talk to Tablet servers directly, after querying Chubby for location

![](https://3398971849-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-M9HSM8Jn9nrPTh34ajG%2Fuploads%2Fgit-blob-194acf36dd4533d9563289a2e1610af0658a1ab2%2Fimage.png?alt=media)

## Implementation details

### Tablet locations lookup

3 level:

* Root tablet(METADATA 0). File location stored in Chubby, actual file stored in GFS.
  * Root tablet never split, to ensure 3-level index
* METADATA 1: stores tablet location

![](https://3398971849-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-M9HSM8Jn9nrPTh34ajG%2Fuploads%2Fgit-blob-f956f2a0134330b500c7b9b929c923e05ec6f047%2Fimage.png?alt=media)

### Tablet Assignment

* Each tablet is assigned to one tablet server at a time.
* Master(single) keeps track of tablet servers and assign tablets to servers
  * Tablet server registers in Chubby file
  * If a server fails, it lost the lock on Chubby. Master re-assign its tablets.
* Master workflow
  * 1\) acquire master lock in Chubby
  * 2\) scan Chubby's server directory to find all live tablet servers
  * 3\) communicate with servers to know the tablets assignment
  * 4\) scan METADATA table to find and assign un-assigned tablets

![](https://3398971849-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-M9HSM8Jn9nrPTh34ajG%2Fuploads%2Fgit-blob-36a4353aca7170e8dc72962af4bd06d3027a5e6b%2Fimage.png?alt=media)

### Tablet serving

#### Tablet discovery

* Client asks Chubby where is the METADATA 0(stored in GFS)
* Client reads MD0 from GFS -> reads MD1 -> finds address of tablet server
* Client cache tablet locations in memory. Optimization: it reads more tablet locations than it needs.

#### Write path

* mutation request arrives in server
* server validatse format, auth(check ACL in Chubby, or client cache)
* mutation persisted to commit log
* mutation applied in memtable

#### Read path

* Tablet server validate request format and auth
* Query memtable + SSTable files -> merge data
  *   SSTables and the memtable are lexicographically sorted data structures, the merged view can be

      formed efficiently.

![](https://3398971849-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-M9HSM8Jn9nrPTh34ajG%2Fuploads%2Fgit-blob-120a932a4d8198530be51129856cbfc3e2cfed1f%2Fimage.png?alt=media)

### Compactions

3 levels of compaction

* Minor compaction: memtable to SSTable
* Merging compaction: recent multiple SSTable to one SSTable
* Major compaction: all SSTable to exactly one SSTable
  * deletion happens in this stage

## Refinement

### Locality

* Bundle the data that you frequently access together into a single locality group for faster access. If not specified, all column families are in `default` locality group
* Bigtable has `in-memory` locaility group that holds the data in memory for fast access.
* Bundle similar data also helps compression.

### Compression

* Compress SSTable block
* Better compression: cluster similar data by designing row key

### Read performance improvement

* Caching
  * scan cache: key-value pairs, for clients that read the same data repeatly
  * block cache: SSTable blocks, for clients read close data, e.g. sequential read, different columns of a hot locality group.
* Bloom Filter: one per locality group, hosted in tablet server memory

### Commit log

* a single commit log per tablet server
  * improve write performance
* optimization for failure recovery
  * sort commit log in order of the keys \<table, row name, log sequence number>
* cope with GFS latency spikes
  * each tablet server actually has two log writing threads, each writing to its own log file. only one of these two threads is actively in use at a time
  * when one thread perform poorly, switch to the other
  * use log sequence number in recovery process

### Speeding up tablet recovery

* Master moves a tablet to another server
* source tablet do minor compaction to persist memtable to SSTable, thus reduce the work to process commit log

### Benefits of immutability

* SSTable is immutable
  * concurrency control is easy, i.e. don't need to worry about concurrency.
  * delete data: set a tombstone. removing deleted data is transformed to garbage collecting obsolete SSTables.
  * split tablet: children tablets share SSTables of parent tablet.
* Memtable
  * each row copy-on-write, so read and write can proceed in parallel.

## Advanced feature in real word

* Transactions implementation: actually read locks or write locks on specific values in a bigtable.

## Reference

* [https://hypertable.com/documentation/architecture/](https://hypertable.com/documentation/architecture/)
