BigTable — Google's Wide-Column Store

What you'll learn

• What BigTable Is (and Isn't)

  BigTable is a distributed storage system for managing structured data at scale, designed to run on thousands of commodity machines and petabytes of data. The 2006 Chang et al. paper describes it as "a sparse, distributed, persistent mult…

• The Real Data Model

  The data model looks deceptively simple but demands careful design. A BigTable table is a collection of rows, each identified by a row key (arbitrary string, typically 10-100 bytes). Row keys are stored in lexicographic order, which is c…

• Building Blocks — Google's Stack

  BigTable didn't build everything from scratch. It layered on top of Google's existing infrastructure: GFS (Google File System): BigTable stores all persistent data in GFS — both the append-only commit logs and the immutable SSTable files…

• Architecture — Master + Tablet Servers + Clients

  BigTable's architecture separates control plane (master) from data plane (tablet servers), ensuring the master is never a bottleneck for reads or writes. Master: A single master (elected via Chubby) is responsible for: - Tablet assignmen…

• Tablets — Unit of Distribution

  A tablet is the unit of load balancing and replication in BigTable. Each tablet contains a contiguous range of rows from a single table, e.g., all rows with keys from "aardvark" to "banana" (inclusive start, exclusive end). Tablet Lifecy…

• METADATA Table Structure in Detail

  The METADATA table stores location and configuration for every user tablet. Each row has a key of the form: The table-id is a unique identifier for the user table, and the end-row-key is the last row in the tablet's range. This encoding…

• LSM-Tree Engine — Reads and Writes

  BigTable's storage engine within each tablet server is an LSM-tree (Log-Structured Merge-Tree). This is the crown jewel of the design, optimizing for write-heavy workloads by deferring expensive disk I/O.

• Write Path

  When a write (Put or Delete) arrives at a tablet server: 1. Authorization check — verify the client has write permission (ACLs cached from Chubby). 2. Append to commit log — the write is serialized and appended to the tablet's commit log…

• Read Path

  To read a cell (row, column, timestamp): 1. Check authorization — verify read permission for the column family. 2. Merge read — the tablet server must merge data from: - The current memtable (unflushed writes). - All live SSTable files f…

• Compaction

  Over time, writes create many small SSTable files. To keep read performance acceptable, BigTable runs background compactions: Merging Compaction: Periodically, select a few SSTables (e.g., 2-10) and the memtable, merge them into a single…

• Pseudo-Code

• Locality Groups & Compression

  BigTable allows column families to be grouped into locality groups for storage optimization. Each locality group is stored in a separate set of SSTable files. Why Locality Groups? Columns that are accessed together should be stored toget…

• Tablet Recovery When a Tablet Server Dies

  Tablet server failures are common at Google's scale. BigTable's recovery protocol minimizes unavailability: Failure Detection: Each tablet server holds a Chubby lock. The tablet server refreshes this lock periodically. If the lock expire…

• Chubby's Role

  Chubby is central to BigTable's coordination: Master Election: When the master starts, it attempts to acquire a Chubby lock. Only one master can hold the lock at a time. If the master crashes, the lock is automatically released (via Chub…

• Single-Row Transactions

  BigTable provides atomic read-modify-write operations on a single row. For example, you can atomically increment a counter or perform a conditional update within one row. Why Single-Row Only? Cross-row transactions require distributed co…

• What BigTable Influenced

  BigTable's design shaped the NoSQL movement and influenced several major open-source and commercial systems: HBase (2007): A direct open-source clone of BigTable, built on Hadoop's HDFS (instead of GFS) and ZooKeeper (instead of Chubby).…

• Interview Takeaways

  1. Why LSM beats B-tree for BigTable's workload: B-trees require random disk I/O on every write (updating a leaf page). LSM-trees buffer writes in memory and flush sequentially, turning random writes into sequential writes. For write-hea…

• BigTable vs GFS Integration

  BigTable's tight integration with GFS is central to its design. All persistent data — SSTables and commit logs — are stored as GFS files. GFS provides: - Replication: Each chunk is replicated 3× by default across different ChunkServers.…

• Performance Numbers from the Paper

  The original BigTable paper (2006) reported performance on Google's production clusters: Single Tablet Server (1 CPU, 1GB RAM): - Random reads (1000-byte values): ~1,200 reads/sec - Random writes (unbatched): ~10,000 writes/sec - Sequent…

• Comparison: BigTable vs Traditional RDBMS

  | Dimension | BigTable | Traditional RDBMS (e.g., MySQL, PostgreSQL) | |-----------|----------|---------------------------------------------| | Data Model | Sparse, multi-dimensional map; wide-column store | Tables with fixed schema, row…

• Comparison: BigTable vs HDFS/MapReduce

  | Dimension | BigTable | HDFS + MapReduce | |-----------|----------|------------------| | Primary Use | Real-time random read/write access to structured data | Batch processing of large datasets | | Access Pattern | Low-latency point rea…