Keyboard shortcuts

/ or ⌘/Ctrl K
Find a note
j / k
Next / previous section or linked note
h / l
Collapse or go to parent / expand or enter
e or Alt-click
Read a linked note here
o
Open focused note on its own
g g / G
First / last section or linked note
g h / g a
Home / all notes
g b / g t
Backlinks / table of contents
t
Cycle System, Light, Dark
? / Esc
Show / close this reference

Search: ↑/↓ or Ctrl N/P, Enter to open. Shortcuts pause while typing.

sectionBigTable [c792edd0]

Part of Databases

  • Key features

    • Single row transactions
    • No batching across row keys
    • Integer counters

    • MapReduce jobs as input source and output target

      2024-02-21_16-32-56_screenshot.png

  • Uses a column family style, with groups of columns and a timestamp within each cell
  • Treats all data as raw byte strings
  • All rows have a row key (64kb string), each write and read is atomic
  • Column families allow for efficient read/write operations, since they usually hold data of the same type (data within a family is physically close)
  • Also has timestamps, keeps the latest 3 versions

1. Components

1.1. Memtable

  • Recent modifications in an in-memory, mutable sorted buffer
  • When a memtable grows big enough, its gets flushed to disk as an SSTable
  • Uses a write-ahead-log for this

1.2. SSTable (Sorted String Table)

  • Components

    • Data File
    • Primary Index
    • Bloom filter (for quickly checking if it's in the data structure)
    • Compression information
    • Stats
    • 64kb blocks
  • Immutable k/v mappings used to represent tablet states, consisting of blocks, with block indexes facilitating efficient disk access, and can be loaded into memory for quick queries

1.3. Chubby

  • Highly available and persistent distributed lock service
  • typically runs with five operating replicas, similar to zoo
  • Used in BigTable to ensure there's only one operational manager
  • Saves a bootstrap information as well as new tablet servers and failures
  • ACLs too

2. Operations

  • Locating tablets for a piece of data

    • Uses a three level structure similar to a B+ tree
    • root tablet's location is stored in a Chubby file
    • second tier contains all metadata tablets
    • third tier contains all user tablets
  • The root tablet is a pointer to other tablets
  • first tablet in the metadata data is the root tablet, which is treated differently
  • We cache tablet positions in the client library
  • Client can then check the metadata server, which then goes to chubby, to get info
  • Basically the thing to know is that this is similar to an inode, where there's three layers of indirection
  • A tablet is assigned to just one tablet server, the manager also maintains a record of unassigned tablets and allocates them to tablet servers that have enough space
  • Manager requires heartbeats and locks via chubby to assure that a tablet server is holding a tablet
  • New managers interact with each active tablet server after looking them up in the tablet server directory in chubby

2.1. Writes

  • When a write is received by a tablet server, it gets checked to ensure to ensure data validity and proper formatting

    • check authorizations in the lock

2.2. Reads

  • Same thing as write, initial check is via authorization in chubby, and then loads the SS tables

3. Minor, Merging, and Major Compactions

  • Minor compaction is when it flushes the memtable to disk and turns it into an sstable
  • Merging compaction is when sstables become too many and we merge them together, although this could include deleted entries
  • Major compaction is when we merge multiple sstables together and remove the deleted datace the tombstones are handled

4. Design Refinements

  • Column family locality

    • compression is also done on the column family locality to store data

  • Tablet caches in two ways

    • Scan cache - high level cache that stores k/v given to the tablet server
    • Block cache - caches blocks, like page caching

  • Bloom filters

    • Bloom filters tell you 100% if it is not in the table.
    • Quickly check which things are in a sstable

  • Commit logs

    • There's only one big commit log
    • Recovering servers must load off of another's commit log
    • Duplicate log reads are by sorting the entries by <table, row name, log seq number>.

  • Speeding up tablet recovery

    • Most challenging and time consuming jobs is ensuring the tablet server gets all entries from the commit log
    • Minor compactions are done before moving to reduce the amount of stuff needed to move.

5. System Design Wisdom

  • Uses other services (Chubby and GFS) as building blocks
  • Locality hints from the users for many of its optimizations, such as column families
  • One log file per tablet is a way to allow individual tablets to recover
  • Single manager interface