Bigtable & HBase
In 2006, Fay Chang, Jeffrey Dean, Sanjay Ghemawat and six colleagues published "Bigtable: A Distributed Storage System for Structured Data" at OSDI. By then Bigtable had been in production at Google for over a year, holding the web crawl, Google Earth imagery, Google Analytics, Personalized Search, Orkut and more than sixty other products. It was neither a relational database nor a key-value store. It was a sparse, distributed, persistent, multidimensional sorted map — a new data model, which the paper argued fit a surprising range of workloads.
Bigtable is the ancestor of a whole family: Apache HBase (a near-direct reimplementation on HDFS, started at Powerset in 2007), Apache Accumulo (NSA, with cell-level security), Hypertable, the storage side of Cassandra, and Cloud Bigtable, Google's hosted version since 2015. Its storage design — memtable, immutable SSTables, compactions — is what most people mean by an LSM tree in production.
This page follows the structure of the OSDI 2006 paper and the Apache HBase Reference Guide. Numbers are from the paper unless stated otherwise.
1. The problem and its constraints
Google had GFS for files and MapReduce for batch processing. What it lacked was a way to store structured data — billions of URLs with many versions of each page, per-user settings for hundreds of millions of users, satellite imagery tiles — with:
- Petabyte scale across thousands of commodity servers.
- Both batch and serving workloads: high-throughput MapReduce scans over the whole data set, and low-latency point reads for user-facing products.
- Wide variability in data shape: the web table had a few columns per row for some URLs and thousands for others (one per inbound link).
- Self-management: servers added and removed without downtime, load rebalanced automatically.
Commercial databases of the time couldn't scale that far at acceptable cost, and Google wanted control over the low-level storage layout for performance. So the team built a system with deliberately limited features:
| Constraint / choice | Consequence |
|---|---|
| Must run on GFS and commodity machines | Persistent data is immutable files on GFS; servers are stateless enough to fail over by reassigning files |
| Simple, predictable performance over full relational features | No SQL, no joins, no secondary indexes, no general multi-row transactions |
| Clients should control locality | Row keys are sorted, so clients design keys that put related data together |
| One system for both scans and point reads | Sorted storage (good for scans) with in-memory indexes, caches and Bloom filters (good for point reads) |
The paper is explicit that Bigtable "does not support a full relational data model; instead, it provides clients with a simple data model that supports dynamic control over data layout and format".
2. Data model
The paper's definition is precise:
A Bigtable is a sparse, distributed, persistent multidimensional sorted map. The map is indexed by a row key, column key, and a timestamp; each value in the map is an uninterpreted array of bytes.
(row:string, column:string, time:int64) → string
Each part of that sentence matters:
- Sparse: a row only stores the columns it has. No space is used for absent columns, so a table can have millions of possible columns with each row using a handful.
- Distributed: the map is split across many servers by row range.
- Persistent: stored durably on GFS.
- Multidimensional: three-part key — row, column, timestamp.
- Sorted: by row key, lexicographically. This is the property clients design around.
Rows
Row keys are arbitrary strings (up to 64 KB, typically 10–100 bytes). Two guarantees hang off rows:
- Every read or write of data under a single row key is atomic, no matter how many columns it touches. This is Bigtable's only built-in atomicity.
- Rows are stored in lexicographic order, and the table is dynamically partitioned into contiguous row ranges called tablets. A scan over a short row range touches few machines.
The paper's flagship example is Webtable: row keys are URLs with the host name reversed, so www.cnn.com/index.html is stored as com.cnn.www/index.html. All pages from one domain are then adjacent, which makes per-domain analysis efficient and improves compression, because pages from one site are similar.
Column families and qualifiers
Column keys have the form family:qualifier. Column families are declared in the schema and are few — the paper says a table should have a small number of distinct families (hundreds at most) that rarely change. Qualifiers are arbitrary and unbounded; they're created by writing to them.
In Webtable, the contents: family holds the page HTML (empty qualifier), the language: family holds a language ID, and the anchor: family has one qualifier per referring site: anchor:cnnsi.com holds the anchor text of the link from cnnsi.com.
flowchart LR
subgraph Row["Row key: com.cnn.www"]
subgraph FC["Family contents:"]
c1["contents: @ t6 = html v3"]
c2["contents: @ t5 = html v2"]
c3["contents: @ t3 = html v1"]
end
subgraph FA["Family anchor:"]
a1["anchor:cnnsi.com @ t9 = CNN"]
a2["anchor:my.look.ca @ t8 = CNN.com"]
end
subgraph FL["Family language:"]
l1["language: @ t6 = EN"]
end
end
Families matter beyond naming: they're the unit of access control and of disk and memory accounting, and (through locality groups) the unit of physical storage layout. All data in one family is usually of the same type and is compressed together.
Timestamps
Each cell can hold multiple versions, indexed by a 64-bit timestamp — either assigned by Bigtable (real time in microseconds) or explicitly by the client. Versions are stored in decreasing timestamp order, so the newest is read first. Per column family, clients choose garbage collection: keep only the last n versions, or only versions newer than some age (e.g. the last seven days). Webtable kept the three most recent crawls of each page.
The full logical model is therefore a map of maps:
table: row → family → qualifier → timestamp → value
sorted by row; families fixed in schema; qualifiers free; timestamps descending
API
The API (paper Section 3) has calls to create and delete tables and families, change metadata such as ACLs, and:
- Write:
RowMutation— set and delete cells in one row, applied atomically (Apply). - Read:
Scanner— iterate over a row range, restricting to families, specific columns, a timestamp range or a number of versions. - Single-row transactions: atomic read-modify-write sequences on data under a single row key.
- Cells as counters: atomic increment.
- Server-side scripts: client-supplied scripts in Google's Sawzall language for filtering and transformation on the servers (read-only — they couldn't write back).
- MapReduce integration: tables as input and output of MapReduce jobs.
What's not there, deliberately: transactions across rows, though the client can batch writes across rows (each row's mutation is atomic; the batch is not).
3. Architecture
Building blocks
Bigtable is built on three other Google systems (paper Section 4):
- GFS stores the log and data files. (Today that's Colossus — see GFS & HDFS.)
- SSTable is the file format: a persistent, ordered, immutable map from keys to values. Internally an SSTable is a sequence of blocks (64 KB by default, configurable), with a block index at the end. When an SSTable is opened, the index is loaded into memory, so a lookup is one binary search in memory plus at most one disk seek. An SSTable can optionally be mapped entirely into memory.
- Chubby is a highly available, persistent distributed lock service: five replicas, one elected master, kept consistent with Paxos, exposing a namespace of small files and directories that can each be used as a lock, with sessions and callbacks — the direct inspiration for ZooKeeper.
Bigtable uses Chubby to:
- Ensure there is at most one active master at any time.
- Store the bootstrap location of Bigtable data (the root tablet).
- Discover tablet servers and finalise tablet server deaths.
- Store schema information (column families per table).
- Store access control lists.
The paper is frank about the dependency: if Chubby becomes unavailable for an extended period, Bigtable becomes unavailable. They measured it across 14 Bigtable clusters spanning 11 Chubby instances: the average percentage of Bigtable server hours during which some data was unavailable because of Chubby was 0.0047%, and 0.0326% for the single most affected cluster.
Components
A Bigtable deployment has three parts: a client library linked into every client, one master server, and many tablet servers.
flowchart TB
subgraph Client["Client process"]
LIB["Bigtable client library<br/>(caches tablet locations)"]
end
CH["Chubby<br/>(master lock, servers directory,<br/>root tablet location, schema, ACLs)"]
M["Master<br/>(assign tablets, balance load,<br/>detect server changes, schema, GFS GC)"]
subgraph TS["Tablet servers (10 to 1,000 tablets each)"]
T1["Tablet server 1"]
T2["Tablet server 2"]
T3["Tablet server N"]
end
subgraph G["GFS / Colossus"]
LOG["Commit logs"]
SST["SSTables"]
end
LIB -->|"locate root tablet"| CH
LIB ==>|"reads and writes go directly here"| T2
M <-->|"master lock"| CH
T1 <-->|"exclusive lock on own file in servers dir"| CH
M -->|"load / unload tablet"| T1
T1 --> LOG
T1 --> SST
T2 --> SST
- The master assigns tablets to tablet servers, detects added and expired tablet servers, balances load, garbage-collects unused files in GFS, and handles schema changes. As in GFS, client data doesn't flow through the master. Clients talk to tablet servers directly, and most clients never talk to the master at all, so the master is lightly loaded.
- Tablet servers each manage a set of tablets (typically 10 to 1,000), handle reads and writes to them, and split tablets that grow too large.
- Tablets start at one per table and split as the table grows; by default each is roughly 100–200 MB.
Locating a tablet
Tablet locations are stored in a three-level hierarchy, like a B+ tree (paper Section 5.1):
flowchart LR
F["Chubby file<br/>(location of root tablet)"] --> R["Root tablet<br/>(first METADATA tablet, never split)"]
R --> M1["METADATA tablet 1"]
R --> M2["METADATA tablet 2"]
R --> M3["METADATA tablet N"]
M1 --> U1["User tablet"]
M1 --> U2["User tablet"]
M2 --> U3["User tablet"]
M3 --> U4["User tablet"]
- A file in Chubby holds the location of the root tablet.
- The root tablet holds the locations of all tablets of a special METADATA table. It is the first METADATA tablet but is never split, so the hierarchy never gets deeper than three levels.
- Each METADATA tablet holds the locations of a set of user tablets. The METADATA row key is an encoding of the tablet's table identifier and its end row.
Each METADATA row is about 1 KB. With modest 128 MB METADATA tablets, the scheme can address 2³⁴ tablets (2⁶¹ bytes in 128 MB tablets). The client library caches locations; with an empty cache, a lookup needs three network round trips including one to Chubby; with a stale cache it can take up to six (stale entries are only discovered on a miss). The library also prefetches — it reads the locations of several tablets whenever it reads the METADATA table.
HBase follows the same idea with two levels: ZooKeeper stores the location of the hbase:meta table, and hbase:meta lists every region. (HBase had a separate -ROOT- table until 0.96, when it was removed because a single meta region was sufficient.)
Tablet assignment and server liveness
Each tablet is assigned to one tablet server at a time. Liveness is all done through Chubby (paper Section 5.2):
- When a tablet server starts, it creates and acquires an exclusive lock on a uniquely named file in a Chubby
serversdirectory. The master watches that directory to discover tablet servers. - A tablet server stops serving its tablets if it loses its exclusive lock — for example because a network partition made it lose its Chubby session. It tries to re-acquire the lock as long as the file exists; if the file is gone, it kills itself.
- The master periodically asks each tablet server about its lock. If a server reports it lost the lock, or the master can't reach it after several attempts, the master tries to acquire the server's lock file itself. If it succeeds, Chubby is alive and the tablet server is either dead or can't reach Chubby — so the master deletes the file, guaranteeing that server can never serve again, and moves its tablets to the unassigned set.
- The master kills itself if its own Chubby session expires. Master failure doesn't change tablet assignments.
At startup the master grabs a unique master lock in Chubby, scans the servers directory, asks every live tablet server which tablets it has, and scans the METADATA table to find unassigned tablets.
This is the clever part: Chubby acts as the arbiter of "is this server allowed to serve?", so the master never assigns a tablet while a previous owner might still serve it. A tablet server that can't reach Chubby stops serving, and the master only reassigns after it has proved, by taking the lock, that the old server can't hold it.
Splits and merges
The set of tablets changes when tables are created or deleted, two tablets merge, or one tablet splits. The master initiates all changes except splits. A split is initiated by the tablet server: it commits the split by recording the new tablet's information in the METADATA table, then notifies the master. If the notification is lost, the master discovers the split when it next asks a server to load the tablet.
Splits are cheap because SSTables are immutable: the two child tablets share the parent's SSTables initially and each only reads its half of the key range. Real rewriting happens later, during compaction.
4. Storage: memtable, SSTables and compactions
Each tablet's persistent state is a set of SSTables plus a portion of a shared commit log, all in GFS. Recent writes live in memory.
flowchart TB
W["Write (row mutation)"] --> CL["Commit log on GFS<br/>(redo records, group commit)"]
W --> MT["Memtable<br/>(sorted, in memory)"]
MT -->|"minor compaction<br/>(memtable full)"| S0["New SSTable"]
S0 --> MERGE["Merging compaction<br/>(a few SSTables + memtable to one)"]
S1["SSTable"] --> MERGE
S2["SSTable"] --> MERGE
MERGE --> S3["Merged SSTable"]
S3 --> MAJ["Major compaction<br/>(all SSTables to exactly one,<br/>deletes and expired versions dropped)"]
R["Read"] --> V["Merged view:<br/>memtable + all SSTables"]
MT --> V
S1 --> V
S3 --> V
Write and read inside a tablet server
From the paper (Section 5.3):
- Write: the server checks that the request is well-formed and that the sender is authorised (by reading a list of permitted writers from a Chubby file — almost always a cache hit). A valid mutation is written to the commit log; group commit batches many small mutations into one log write for throughput. After the commit, the mutation is inserted into the memtable, a sorted in-memory buffer.
- Read: after the same checks, the read executes on a merged view of the memtable and the tablet's SSTables. Because all of them are sorted lexicographically, the merge is efficient.
- Recovery: to load a tablet, a server reads its METADATA entry, which lists its SSTables and a set of redo points — positions in the commit logs that might contain data for the tablet. It reads the SSTables' indexes into memory and rebuilds the memtable by applying the redo records after the redo points.
Reads and writes continue while tablets split and merge.
Three kinds of compaction
As writes arrive, the memtable grows. Bigtable has three compaction types (paper Section 5.4):
- Minor compaction. When the memtable reaches a size threshold, it's frozen, a new memtable is created, and the frozen one is written to GFS as a new SSTable. Two goals: shrink the server's memory use, and reduce how much commit log must be replayed if the server dies.
- Merging compaction. Each minor compaction adds an SSTable. Left alone, reads would have to merge more and more files. A merging compaction periodically reads a few SSTables and the memtable and writes one new SSTable; the inputs are discarded when it's done.
- Major compaction. A merging compaction that rewrites all SSTables into exactly one. Non-major compactions may produce SSTables that still contain deletion entries (tombstones) that suppress older data in other SSTables. A major compaction produces an SSTable with no deletion information and no deleted data. Bigtable cycles through all its tablets and regularly runs major compactions, which lets it reclaim the resources used by deleted data and ensure deleted data disappears from the system in a timely fashion — the paper points out that's important for services storing sensitive data.
The write/read/space trade-off of this design is the standard LSM-tree one, analysed in depth on the Storage Engines page: writes are sequential (log append + memory insert), reads may touch several files, and compaction trades background I/O for read speed and space.
5. Refinements that make it fast
Section 6 of the paper is a list of refinements that turned the basic design into something with good performance and availability. Several became standard features of every LSM-based store.
Locality groups
Clients can group column families into a locality group. Each locality group gets its own SSTable per tablet. Separating families that aren't read together makes reads cheaper: in Webtable, page metadata (language, checksums) can be one locality group and page contents another, so an application that only wants metadata never reads the HTML.
Locality groups can be declared in-memory: their SSTables are loaded lazily into the tablet server's memory, so reads don't touch disk. The METADATA table's location family is in an in-memory group.
Locality groups also carry tuning parameters: compression, block size, and Bloom filters are configured per locality group.
Compression
Clients choose a compression format per locality group, applied to each SSTable block separately (so a read doesn't decompress the whole file). Many clients used a two-pass scheme: Bentley–McIlroy to find long common strings across a large window, then a fast compressor looking for repetitions in a small 16 KB window. Both passes are fast — encode at 100–200 MB/s, decode at 400–1000 MB/s on 2006 hardware. In a Webtable experiment storing one version of each page, they got a 10-to-1 reduction, compared with the typical 3- or 4-to-1 of Gzip on HTML, because reversed-URL keys put similar pages from one host next to each other. With multiple versions per page the ratio is even better.
Caching
Tablet servers have two levels of cache: the Scan Cache, a higher-level cache of key-value pairs returned by the SSTable interface (good for applications that read the same data repeatedly), and the Block Cache, a lower-level cache of SSTable blocks read from GFS (good for applications that read data close to recently read data — sequential reads, or different columns in the same locality group of a hot row).
Bloom filters
A read may need to consult every SSTable of the tablet. If those SSTables aren't in memory, that's many disk accesses. Clients can ask for Bloom filters to be built for the SSTables of a locality group. A Bloom filter answers "might this SSTable contain data for this row/column pair?" with no false negatives and a small false-positive rate, using a few bits per key. For most lookups of non-existent rows or columns, the filters let the server skip every SSTable without touching disk.
Commit log design
If each tablet had its own commit log, a server with hundreds of tablets would write to hundreds of GFS files concurrently, causing many disk seeks and defeating group commit. So Bigtable uses one commit log per tablet server, interleaving mutations for all its tablets.
That makes recovery harder: when a server dies, its tablets go to many other servers, and each would have to read the entire log to find its tablet's entries. Bigtable avoids that by first sorting the log entries by (table, row name, log sequence number), so each tablet's mutations are contiguous. The sort is parallelised: the log is partitioned into 64 MB segments, sorted in parallel on different tablet servers, coordinated by the master. HBase does the same thing, called distributed log splitting (and later WAL splitting to recovered-edits files or, in HBase 2.x, procedure-based splitting).
GFS write latency spikes could stall the log. So each tablet server has two log-writing threads, each writing to its own file, with only one active at a time. If writes to the active file perform badly, the server switches to the other thread. Log entries carry sequence numbers so recovery can drop duplicates written by both.
Faster tablet moves
When the master moves a tablet, the source server first does a minor compaction (reducing the commit log the destination would need to replay), stops serving the tablet, does a second, usually very fast minor compaction to flush anything that arrived meanwhile, and then unloads it. The destination can then load the tablet without any log recovery.
Exploiting immutability
Since SSTables never change after they're written:
- Reads of SSTables need no synchronisation. Only the memtable is mutable, and it uses copy-on-write per row so reads and writes proceed in parallel.
- Deleting data becomes garbage collection of obsolete SSTables. The master runs a mark-and-sweep, with the METADATA table's SSTable lists as the roots.
- Splits are fast, because children share the parent's SSTables.
6. Consistency guarantees
Bigtable's guarantees are deliberately narrow, and the paper states them precisely:
- Single-row atomicity. Every read or write of data under a single row key is atomic, regardless of the number of columns involved. Single-row read-modify-write transactions are supported. A reader never sees half of a row mutation.
- No multi-row transactions. Batched writes across rows are not atomic as a group. The paper's lessons section says the team originally planned general-purpose transactions, but found that most applications only needed single-row transactions, and that the main request for distributed transactions was for maintaining secondary indexes — which they planned to address with a specialised mechanism rather than general transactions.
- Strong consistency within a cluster. Each tablet is served by exactly one tablet server at a time, enforced through Chubby, so all reads and writes for a row go through one server and see a single, up-to-date order of mutations. There's no replica divergence to reason about inside a cluster: durability comes from GFS's replication of the log and SSTables, not from multiple serving replicas.
- Durability on acknowledgment. A write is acknowledged after its commit-log record is written to GFS.
The caveats:
- Availability is bounded by single-server ownership. When a tablet server dies, its tablets are unavailable until the master detects the failure (via Chubby lock loss), reassigns them, and the new servers replay the log. That's typically seconds to tens of seconds, not milliseconds. It's a CP design: during that window, those rows can't be read or written.
- Timestamps are not a transaction mechanism. Client-assigned timestamps can be anything; Bigtable just orders versions by them. Two writers with skewed clocks can make an "older" write appear newer.
- Cross-cluster replication is eventual. In the 2006 paper, replication across data centres wasn't part of Bigtable's core; later Bigtable (and Cloud Bigtable today) replicates between clusters asynchronously, with eventual consistency between clusters and an option to route an application to a single cluster for read-your-writes.
HBase's guarantees
HBase's documented ACID semantics (in the Reference Guide) mirror Bigtable's:
- Atomicity: all mutations within a single row (
Put,Delete,Increment,Append,checkAndMutate, andmutateRowwith multiple operations on one row) are atomic. Multi-row operations are not, exceptMultiRowMutationEndpoint-style coprocessors for rows in the same region. - Consistency and isolation: a
Getreturns a complete row as it existed at some point in time — it never mixes parts of two mutations. HBase implements this with an internal MVCC read point per region: a write gets a sequence number, and readers only see writes whose numbers are below the region's read point, which advances only once all earlier writes are complete. - Scans are not consistent snapshots of the whole table. Each row returned is consistent, but a scan does not see a single point-in-time view across rows; rows mutated after the scan started may or may not appear.
- Visibility: once a write is acknowledged, any later read sees it. Since all reads and writes for a region go through its single RegionServer, this is strong consistency per row.
- Durability: a write acknowledged with the default durability is in the WAL on HDFS (by
hflush— in the memory of three DataNodes, not necessarily fsynced, unlesshbase.wal.hsyncorDurability.FSYNC_WALis used).
HBase later added region replicas (HBASE-10070) for read availability: secondary replicas of a region on other RegionServers serve timeline-consistent reads that may be stale, flagged with Result.isStale(). Writes still go only to the primary.
7. HBase in detail
HBase is the most widely deployed open-source Bigtable. The mapping is close:
| Bigtable | HBase |
|---|---|
| Tablet | Region |
| Tablet server | RegionServer |
| Master | HMaster (active + standbys) |
| Chubby | ZooKeeper |
| GFS | HDFS |
| SSTable | HFile |
| Memtable | MemStore (one per column family per region) |
| Commit log | WAL (write-ahead log) |
| METADATA table | hbase:meta |
| Locality group | Column family (each family is its own set of HFiles) |
One difference matters a lot: in HBase, each column family has its own MemStore and its own HFiles. That makes a family behave like a Bigtable locality group. It also means a region with many families flushes many small files, which is why HBase's guidance is to keep the number of column families small (one to three).
HBase write path
sequenceDiagram
autonumber
participant C as Client
participant ZK as ZooKeeper
participant META as RegionServer hosting hbase:meta
participant RS as RegionServer hosting the region
participant WAL as WAL on HDFS
participant MS as MemStore
C->>ZK: where is hbase:meta (cached after first time)
ZK-->>C: meta RegionServer address
C->>META: which region contains row key K (cached)
META-->>C: region R on RegionServer RS
C->>RS: Put row K, family f, qualifier q
RS->>RS: take row lock, assign MVCC write number
RS->>WAL: append edit, sync to HDFS pipeline
WAL-->>RS: durable on the DataNode pipeline
RS->>MS: insert into MemStore for family f
RS->>RS: advance MVCC read point, release row lock
RS-->>C: success
Note over RS,MS: Later, MemStore reaches flush size and is written as a new HFile
When a MemStore reaches hbase.hregion.memstore.flush.size (128 MB by default), the region flushes: it snapshots the MemStore and writes it as a new HFile to HDFS — a Bigtable minor compaction. HBase also forces flushes when total MemStore memory on the RegionServer passes a global limit or when the WAL has too many files, so old WALs can be archived. If MemStores can't flush fast enough, HBase blocks writes to the region to protect memory — the classic "blocking updates" warning in RegionServer logs.
HBase read path
sequenceDiagram
autonumber
participant C as Client
participant RS as RegionServer
participant BC as BlockCache
participant MS as MemStore
participant HF as HFiles on HDFS
C->>RS: Get row K (region location already cached)
RS->>RS: take the region's MVCC read point
RS->>MS: look up K in MemStore
RS->>RS: for each HFile, check time range and Bloom filter
RS->>BC: look up candidate data blocks
alt block not cached
RS->>HF: read block via HDFS, ideally a short-circuit local read
HF-->>RS: block
RS->>BC: cache block
end
RS->>RS: merge MemStore and HFile cells, newest version first, apply deletes
RS-->>C: row as of the read point
HFiles carry a block index and optional Bloom filters (per row, ROW, which is the default; or per row+column, ROWCOL). The BlockCache holds data and index blocks — on-heap LRU, or the off-heap BucketCache for large caches. Because HBase stores HFiles on HDFS, it relies on data locality: a RegionServer is ideally on the same machine as a DataNode holding a replica of its HFiles, so reads can be short-circuit local reads. After a region moves, locality is lost until a major compaction rewrites its files on the new host.
Compactions in HBase
- Minor compactions pick a few small HFiles of a store (family) and merge them. The default selection policy (exploring compaction) picks a set of files whose sizes are within a ratio of each other, to bound write amplification. Minor compactions can drop deleted cells only if they can see the delete marker and the data together, but they keep delete markers.
- Major compactions rewrite all HFiles of a store into one, dropping deleted cells, delete markers and expired versions. By default they run periodically (
hbase.hregion.majorcompaction, 7 days, with jitter). Many operators disable time-based major compactions and run them off-peak, because they rewrite every byte of a region and can saturate disk and network. - Stripe and date-tiered compaction policies exist for specific workloads (large regions, time-series).
Region splits
When a region grows past a size threshold, its RegionServer splits it. In HBase 2.x the default policy is SteppingSplitPolicy: split at 2 × flush size when the table has a single region on that server, and at hbase.hregion.max.filesize (10 GB by default) otherwise — so new tables spread quickly, and mature tables have large regions.
The split itself is cheap, as in Bigtable:
- The RegionServer picks a split point (the middle key of the largest store file).
- The split is coordinated by the master as a procedure (HBase 2's Procedure v2 framework, which persists each step so a crashed master can resume): the parent region is closed and flushed.
- Two daughter regions are created. Instead of copying data, each daughter gets reference files pointing to the top or bottom half of the parent's HFiles.
hbase:metais updated atomically: the parent is marked offline and split, and the daughters are added.- The daughters are opened, usually on the same RegionServer; the master may later move one for balance.
- When the daughters' compactions have rewritten their data into real HFiles, the references are dropped and the parent's files are deleted by the CatalogJanitor.
The pause in availability is the time to close, flush and reopen — typically well under a few seconds. Pre-splitting tables at creation (giving a list of split keys) is the standard way to avoid a new table starting as a single hot region.
Failure recovery in HBase
- A RegionServer holds a ZooKeeper session and an ephemeral znode under
/hbase/rs. When it dies (or pauses pastzookeeper.session.timeout, 90 seconds by default), the znode disappears and the active HMaster is notified. - The master runs a ServerCrashProcedure: it splits the dead server's WAL by region (distributed across live RegionServers), so each region's edits are grouped.
- To make sure the dead server can't keep writing, the master recovers the HDFS lease on its WAL files — once that succeeds, the old process can no longer append. This is the fencing step.
- The regions are reassigned; each new host replays its recovered edits into the MemStore, then the region opens.
Mean time to recovery is dominated by failure detection (the session timeout) and WAL splitting. Many deployments lower the ZooKeeper session timeout and tune GC to keep it short — the tension is that a too-short timeout turns a GC pause into a RegionServer death, with a full recovery cycle.
8. Performance numbers from the paper
The paper's benchmark (Section 7) used N tablet servers, each with 1 GB of memory, writing to a GFS cell of 1,786 machines, each with two 400 GB IDE hard drives. N client machines generated load. The tablet servers, master, test clients and GFS servers all ran on the same pool of machines. Each benchmark read or wrote roughly 1 GB per tablet server, with 1,000-byte values.
Single tablet server, values read or written per second (paper's Figure 6 table):
| Benchmark | Ops/s per server | Why |
|---|---|---|
| Random reads | 1,212 | Each read fetches a 64 KB SSTable block from GFS to return 1,000 bytes — about 75 MB/s of GFS traffic, saturating the server's network |
| Random reads (in-memory) | 10,811 | Locality group marked in-memory; no GFS reads |
| Random writes | 8,850 | Commit-log append with group commit + memtable insert |
| Sequential reads | 4,425 | Each 64 KB block fetched is used for 64 consecutive reads; block cache helps |
| Sequential writes | 8,547 | Same path as random writes — the LSM design makes them equally cheap |
| Scans | 15,385 | One RPC returns many values, amortising RPC overhead |
The single-server numbers show the LSM signature: random writes are as fast as sequential writes, and both are much faster than random reads from disk.
Scaling: aggregate throughput rose dramatically with tablet servers — by over a factor of 100 going from 1 to 500 servers for several benchmarks, with in-memory random reads rising by almost 300× for a 500× increase in servers. Per-server throughput fell, however, mostly because of load imbalance across servers (other processes on the shared machines contending for CPU and network) and the rebalancing algorithm's limited ability to keep up. Random reads scaled worst: each read moves a 64 KB block across the network, and the shared 1 Gbps links in the network saturated.
Production use (paper Section 8): as of August 2006, there were 388 non-test Bigtable clusters with about 24,500 tablet servers in total. Some table sizes: the crawl table about 800 TB, Google Analytics' raw click table about 200 TB (and a summary table of about 20 TB), Google Earth imagery about 70 TB. Some clusters were for batch processing, others served user requests with latency requirements.
9. What it got right, what it got wrong, and successors
What it got right
- A data model between key-value and relational. Sorted rows with dynamic columns covered web crawl data, user profiles, time series and indexes. The idea that clients control locality through key design is now standard (data partitioning by range).
- LSM storage on a shared file system. Writes are sequential; files are immutable; servers are nearly stateless because all state is in GFS. Moving a tablet means changing ownership, not copying data.
- One owner per tablet, enforced by a lock service. Simple strong consistency per row without quorum reads or conflict resolution.
- The refinements. Bloom filters, per-block compression, two-level caches, locality groups and a shared commit log with sorted recovery are now standard in every LSM-based system.
- Lessons in the paper itself: large systems fail in surprising ways (memory and network corruption, large clock skew, hung machines, extended and asymmetric partitions, bugs in Chubby, GFS quota overflows); delay features until you see how they'll be used; build system-level monitoring (they added RPC tracing); and simple designs are easier to debug — the team described how a complex tablet-server membership protocol caused problems and was replaced with a simpler one.
What it got wrong or left out
- No cross-row transactions. Applications that needed consistent secondary indexes or multi-entity updates had to build fragile logic themselves. Google's answers: Percolator (OSDI 2010) added snapshot-isolation multi-row transactions on top of Bigtable for incremental indexing; Megastore (CIDR 2011) added ACID transactions within entity groups and synchronous Paxos replication; and finally Spanner (OSDI 2012), whose paper explicitly cites Bigtable's lack of transactions and of synchronous cross-datacenter replication as motivation.
- Availability gaps on server failure. One owner per tablet means seconds to tens of seconds of unavailability for that tablet when its server dies. Bigtable later improved this, and HBase added timeline-consistent region replicas, but it's inherent in the single-owner model.
- Schema-less values push complexity to clients. Values are bytes; no types, no secondary indexes, no query language. HBase grew Apache Phoenix (SQL over HBase) to fill this gap.
- Hotspotting from sorted keys. Monotonically increasing keys (timestamps, sequence IDs) send all writes to the last tablet. Applications have to salt, hash or reverse keys — a recurring source of production incidents.
- Dependence on GFS and Chubby. Bigtable is only as available as both.
Successors and descendants
- Cloud Bigtable (2015): Google's hosted Bigtable, with an HBase-compatible API, multi-cluster asynchronous replication, and storage on Colossus separate from serving nodes, so adding nodes rebalances in minutes without moving data.
- Apache HBase: reimplementation on HDFS and ZooKeeper; added coprocessors, region replicas, off-heap caching, Procedure v2 for reliable master operations.
- Apache Accumulo: Bigtable design with cell-level visibility labels.
- Spanner: the direct successor inside Google — it started as a Bigtable-like versioned key-value store and evolved into a temporal multi-version SQL database with transactions and synchronous replication.
How it differs from Cassandra
Cassandra (see Cassandra Internals) is often described as "Bigtable's data model on Dynamo's distribution", and that's a useful summary:
| Bigtable / HBase | Cassandra | |
|---|---|---|
| Partitioning | Range partitioning by sorted row key; tablets/regions split dynamically | Hash partitioning (consistent hashing of the partition key); order only within a partition |
| Serving replicas | One server owns a tablet/region at a time; durability from the replicated file system | N replicas each serve reads and writes (leaderless) |
| Coordination | Master + Chubby/ZooKeeper | Peer-to-peer gossip; no master |
| Consistency | Strong per row; single owner | Tunable per request (ONE, QUORUM, ALL…); eventual by default; lightweight transactions with Paxos for compare-and-set |
| Failure behaviour | Region unavailable until reassigned (CP) | Stays available if enough replicas answer (AP with tunable C) |
| Storage engine | Memtable + SSTables/HFiles on a distributed FS | Memtable + SSTables on local disks; commit log local |
| Conflict resolution | None needed (one writer per row) | Last-write-wins by timestamp per cell |
| Range scans | Efficient across the whole key space | Efficient only within a partition (unless using order-preserving partitioners, which are discouraged) |
| Multi-datacenter | Async replication between clusters | Built-in, per-keyspace replication across datacentres |
Interview-level summary: choose HBase/Bigtable when you need strong per-row consistency, efficient range scans over the global key order, and integration with Hadoop/Spark analytics; choose Cassandra when you need high write availability across datacentres with no single point of failure, and can model access by partition key.
10. Lessons for system design interviews
- Key design is the schema. In a sorted store, the row key determines locality, scan efficiency and hotspots. Show a key design: reversed domains,
userId#reverseTimestampfor newest-first per user, salted prefixes for monotonically increasing IDs. - Know the LSM write and read paths cold. Log + memtable for writes; memtable + SSTables merged for reads; Bloom filters to skip files; compaction to bound read amplification and reclaim deletes.
- Separate serving from storage. A shared, replicated file system lets serving nodes be nearly stateless and makes rebalancing a metadata change.
- Use a lock service to enforce single ownership. "Server loses its lock → stops serving; master proves the lock is free before reassigning" is the template for safe ownership handoff.
- Single-row atomicity is a real design constraint. Model data so that what must change together lives in one row (wide rows, nested qualifiers). If you need cross-row atomicity, say so and pick a system that offers it (Spanner, a NewSQL database, or Percolator-style transactions).
- Know the failure-recovery timeline. Detection (session timeout) + log split + replay. Interviewers like candidates who can estimate MTTR and know which knob controls it.
- Wide-column ≠ Cassandra. Be ready to contrast range-partitioned, single-owner Bigtable/HBase with hash-partitioned, leaderless Cassandra.
11. Interview questions
1. Why does Webtable store URLs with the host name reversed?
Because rows are sorted lexicographically. Reversing the host (com.cnn.www/…) makes all pages from one domain — and from sibling subdomains — adjacent. Scans over a domain touch a few tablets, and similar pages compress better together because they sit in the same SSTable blocks.
2. Walk through what happens on a Bigtable write and why it's fast.
The tablet server checks authorisation (cached Chubby ACL), appends a redo record to its commit log on GFS — batched with other writes by group commit — and inserts the mutation into the in-memory sorted memtable. No disk seeks or read-before-write are needed. Later, minor compactions flush the memtable to an SSTable in one sequential write. That's why random and sequential writes performed about the same (around 8,500–8,850 ops/s per server in the paper).
3. Explain minor, merging and major compactions. Which one removes deleted data?
Minor compaction freezes a full memtable and writes it out as a new SSTable, freeing memory and shortening log replay. Merging compaction combines a few SSTables and the memtable into one SSTable, to keep the number of files a read must consult bounded. Major compaction rewrites all of a tablet's SSTables into exactly one, and only it is guaranteed to drop deletion markers and the data they suppress, because only then can it be sure no older SSTable still holds data the marker must hide.
4. How does Bigtable make sure two tablet servers never serve the same tablet?
Each tablet server holds an exclusive Chubby lock on a file named for it, and stops serving if it loses the lock. Before reassigning a server's tablets, the master acquires that server's lock file itself and deletes it. Holding the lock proves the old server no longer holds it and therefore has stopped serving; deleting the file ensures it can never re-acquire it. Only then are its tablets reassigned.
5. Why one commit log per tablet server instead of per tablet, and what does it cost?
Per-tablet logs would mean hundreds of concurrent log files per server, causing many disk seeks in GFS and making group commit ineffective. A single interleaved log is fast to write. The cost is recovery: a dead server's tablets go to many servers, and each would need to scan the whole log. Bigtable sorts the log by (table, row, sequence number) in parallel 64 MB segments first, so each new owner reads only its tablet's contiguous section.
6. Your HBase table uses timestamps as row keys and all writes go to one RegionServer. Why, and how do you fix it?
Rows are range-partitioned by sorted key, and increasing timestamps always sort last, so every write lands in the last region; splitting just creates a new last region. Fixes: prefix the key with a salt or hash bucket (hash(id) mod N, then timestamp), lead with a high-cardinality field such as device or user ID followed by the timestamp, or reverse the timestamp per entity for newest-first reads. Pre-split the table into the expected buckets. The cost of salting is that a time-range scan becomes N parallel scans.
7. What does HBase guarantee for a Get, and for a Scan?
A Get returns a complete row as of a single point in time: all mutations to a row are atomic and isolated through per-region MVCC, so you never see half of a Put. A Scan returns each row consistently, but the scan as a whole isn't a snapshot — rows changed during the scan may or may not be included. Multi-row writes aren't atomic except via special coprocessors within one region.
8. A RegionServer goes through a 120-second GC pause. Describe what happens.
Its ZooKeeper session expires (default 90 s), its ephemeral znode is removed, and the master starts crash recovery: it recovers the HDFS lease on the server's WAL files — fencing the paused server so it can't append any more edits — splits the WAL by region, and reassigns the regions, which replay their edits and open elsewhere. When the paused server wakes, its next WAL write fails (the lease is gone) and it learns from ZooKeeper that its session expired, so it aborts. The affected regions were unavailable from the start of the pause until reopened elsewhere.
9. When would you choose HBase over Cassandra, and vice versa?
HBase: strongly consistent per-row reads and writes, efficient ordered range scans across the whole key space, tight Hadoop/Spark integration, and workloads that tolerate brief unavailability of a region during failover. Cassandra: always-on writes across multiple data centres, no master or ZooKeeper dependency, tunable consistency, and access patterns that fit partition-key lookups and in-partition ranges.
Further reading
- Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, Robert E. Gruber. Bigtable: A Distributed Storage System for Structured Data. OSDI 2006.
- Mike Burrows. The Chubby lock service for loosely-coupled distributed systems. OSDI 2006.
- Daniel Peng, Frank Dabek. Large-scale Incremental Processing Using Distributed Transactions and Notifications (Percolator). OSDI 2010.
- Apache HBase Reference Guide — architecture, regions, write-ahead log, compactions, ACID semantics, region replicas.
- Lars George. HBase: The Definitive Guide. O'Reilly.
- Related on Archon: Storage Engines, Cassandra Internals, Bloom Filters, Sharding, GFS & HDFS, ZooKeeper, Spanner, Dynamo.