How Bigtable and HBase Work: LSM Trees and Tablets

It slows down because every insert must also update its indexes in place. Once an index outgrows memory, a flood of tiny inserts turns into scattered disk reads and writes. Sensor data never stops arriving, so the backlog keeps growing once writes outpace the disk.

Picture a common setup, the kind Bigtable was built for. A city air-quality network has 3,000 sensors on rooftops, bus stops and market corners. Each sends one reading a minute: two sizes of fine dust (PM2.5 and PM10), nitrogen dioxide, temperature and humidity. The setup is made up, but the problem is real.

That is 3,000 sensors times 1,440 minutes, or 43.2 lakh (4.32 million) readings a day. The team first stores them in one relational table, indexed on sensor id and time.

It works for a few months. Then the first smog week of winter arrives and everyone checks the app. Inserts queue up, and the hourly ward charts take 40 seconds to load (made up).

Research partners also want five years of minute-level history. That is about 788 crore (7.88 billion) readings, and the write rate grows with every new sensor. The team wants storage that grows by adding machines, not by buying a bigger one.

This guide follows the team's readings table through the Bigtable design. You will see how data is laid out, why writes stay fast, how one table spreads across servers, and an easy row key mistake.

Bigtable is a distributed storage system for structured data that Google described in a 2006 paper at OSDI, a systems research conference. It was designed to scale to petabytes of data across thousands of ordinary servers.

The paper defines a Bigtable as a sparse, distributed, persistent, multi-dimensional sorted map. That sounds dense, so take it one word at a time.

• Map: a lookup from a key to a value, like a Python dictionary.
• Sorted: the keys are kept in order, so reading a run of neighbouring keys is cheap.
• Multi-dimensional: the key has three parts, a row, a column and a timestamp, instead of one.
• Persistent: the data lives on disk and survives restarts.
• Distributed: the map is cut into pieces that live on many machines.
• Sparse: empty cells cost nothing. A sensor with no nitrogen dioxide meter simply has no such cell.

HBase is the open-source system modelled on Bigtable. Its project page promises Bigtable-like capabilities on top of Hadoop and HDFS. Hadoop is an open-source toolkit for storing and processing very large data sets. HDFS is its distributed file system, which splits big files across machines and keeps copies.

In the paper, Bigtable keeps its files on GFS, the Google File System, which plays the same role as HDFS. Google also sells Bigtable as a managed cloud service. Its docs say data is never stored on the serving nodes themselves, only in Colossus, Google's file system (as of October 2026).

This guide follows the design from the paper and from HBase, because that is what interviews and real debugging need. Where the cloud service behaves differently, the guide says so and dates it.

Every value sits at an address with three parts: a row key, a column and a timestamp. The value itself is just bytes, and Bigtable does not interpret them.

Row key. The row key names the row, and the whole table is sorted by it, byte by byte, like words in a dictionary. Every read or write under one row key is atomic, meaning it happens completely or not at all.

The paper's design offers no general transactions across rows. The cloud service still supports transactions only within a single row (as of October 2026). If two values must change together, design them into one row.

Column family. A column family is a named group of columns that you create before storing data in it. The team uses two: air for readings and meta for device details. In HBase each family gets its own set of files, so keep families few.

Column qualifier. The qualifier is the column's name inside its family, written family:qualifier, like air:pm25. You can add qualifiers at any time without a schema change. When the team adds ozone sensors next year, new rows simply gain an air:o3 cell.

Timestamp. Each cell can keep several versions of its value, each tagged with a 64-bit timestamp. The paper stores versions newest first, so the latest is read first. A garbage-collection rule on each family keeps only the last few versions, or only recent ones.

Defaults differ, so check yours. HBase keeps one version per cell unless you raise it. Cloud Bigtable keeps unlimited versions when a family is created with Google's cbt or gcloud command-line tools, and one with the HBase client (as of October 2026).

Here is a slice of the readings table. Notice that the row key carries both the sensor and the time, and that one row has no nitrogen dioxide cell at all.

The odd number after the hash is a reversed time, explained in the row key section. For now, see that rows for sensor DL-0412 sit next to each other, because the table is sorted by row key.

An LSM tree, short for log-structured merge tree, is a storage design that turns many small random writes into a few large sequential ones. New data waits in memory, then goes to disk in big sorted batches.

The idea comes from a 1996 paper by Patrick O'Neil and colleagues. It compared this design with a B-tree, the usual index in relational databases, which edits pages in place on disk.

Its example was a bank's history table from TPC-A, a standard database benchmark modelled on bank transactions. Keeping a B-tree index on that table up to date in real time would effectively double each transaction's disk I/O, meaning its disk reads and writes.

Three parts make up the write side. Each has a Bigtable name and an HBase name.

• Commit log (HBase calls it the WAL, the write-ahead log): an append-only file on the distributed file system. It exists so that nothing in memory is lost if the server crashes. HBase lets a write skip the WAL, and its guide warns this puts data at risk.
• Memtable (HBase: MemStore): a sorted buffer in memory that holds the latest writes.
• SSTable (HBase: HFile): a file of key-value pairs, sorted by key, that never changes once written. SSTable stands for sorted string table.

Think of a stamp collector in Old Delhi. New stamps arrive every day, and he does not walk to the shelf to slot each one into the right album. He notes each stamp in a diary, drops it in a tray, and files a full tray as one fresh, ordered set of pages.

In this picture the diary is the commit log, the tray is the memtable, and each filed set of pages is an SSTable. Merging old sets into one album later is compaction, covered below.

Where the picture breaks: the real memory buffer stays sorted at every moment, and a filed SSTable is never edited again. A real collector would happily paste one more stamp onto an old page.

Now follow one reading from sensor DL-0412 through the write path. Notice that the slow disk file is written only when the memtable fills up, not on every write.

The paper calls that flush a minor compaction. It has two goals: free up memory, and shorten the log a server must replay after a crash. Reads and writes keep running while it happens.

How big is full? In HBase 2.6.7 and 3.0.0, a region flushes once its MemStores together pass 128 MiB (about 134 million bytes) by default, set by hbase.hregion.memstore.flush.size.

A read checks the memtable and the tablet's SSTables, merges what it finds and lets the newest version win. Every source is already sorted, so the merge itself is cheap.

The cost is the number of files. With eight SSTables, a careless read could touch the disk eight times. Three tricks keep that down.

• Block index. Each SSTable is cut into blocks, typically 64 KB in the paper, with an index at the end. The index is loaded into memory when the file opens, so finding a block takes one disk seek.
• Bloom filter. A Bloom filter is a small bit pattern in memory that answers one question: is this row definitely not in this file, or maybe in it? A no skips the file.
• Block cache. Recently read blocks stay in memory, so popular data is served without touching the disk.

Bloom filters are optional in the paper, switched on per locality group, a set of column families stored together. HBase has turned on row Bloom filters by default since version 0.96.

The paper notes that with Bloom filters, most lookups for rows or columns that do not exist never touch disk. That makes them ideal for a point read of one exact row.

Deletes work in a surprising way. An SSTable is never edited, so a delete writes a small deletion marker, called a tombstone. The tombstone hides older values during the merge, until compaction removes both for good.

Say the ingest service timed out on a write and, before resending, asks whether the 07:45 reading for DL-0412 was stored. Follow that check below.

Scope that win carefully. HBase's guide says Bloom filters do not work with scans, such as the 60 rows of a sensor's last hour. A scan relies on sorted order and the block index instead.

Compaction is background work that merges SSTables into fewer, larger ones, so reads touch fewer files. It is also when deleted and expired data finally leaves the disk.

Back to the stamp collector. After a year he has a stack of thin sets of pages, and finding one stamp means checking every set. So now and then he merges sets into one album and throws out the stamps marked as sold.

The Bigtable paper names three kinds of compaction.

1. 1

   Minor compaction

   The full memtable is frozen and written out as a new SSTable. This is the flush from the write path.

2. 2

   Merging compaction

   A few SSTables and the memtable are read and written out as one new SSTable. The inputs are deleted afterwards. The output can still hold tombstones.

3. 3

   Major compaction

   All SSTables of a tablet are rewritten into exactly one. Only this kind drops tombstones and the data they hide, which frees the space for good.

HBase uses two of these names with its own meaning. Its minor compaction rewrites a few small, adjacent files into one but keeps the tombstones. Its major compaction rewrites all of a store's files into one, and that is when tombstones are removed.

A store is one column family inside one region. By default HBase schedules a major compaction for each store about once a week; the engineer section shows how loose that week is.

The reference guide also says minor compactions keep expired versions. The 2.6.7 and 3.0.0 source disagrees, with default settings, as of October 2026. A minor compaction already drops expired cells, extra versions and values hidden by a tombstone in its input files.

Compaction is not free. The same reading is rewritten several times over its life: flushed once, then merged again and again. This repeat work is called write amplification, and it uses disk and network bandwidth that live traffic also needs.

Here is the whole cycle in a tiny Python class: writes, a flush every three entries, a tombstone and a major compaction. It skips the commit log and the disk, so the logic stays visible.

FLUSH_AT = 3       # HBase flushes at 128 MiB by default; 3 keeps the demo tiny
TOMBSTONE = None   # the marker a delete writes

class TinyLSM:
    def __init__(self):
        self.memtable = {}   # newest writes, kept in memory
        self.sstables = []   # sorted files that are never edited, oldest first

    def put(self, key, value):
        self.memtable[key] = value   # a real system appends to the commit log first
        if len(self.memtable) >= FLUSH_AT:
            self.sstables.append(dict(sorted(self.memtable.items())))   # flush
            self.memtable = {}

    def delete(self, key):
        self.put(key, TOMBSTONE)     # a delete is just one more write

    def get(self, key):
        for table in [self.memtable] + self.sstables[::-1]:   # newest first
            if key in table:
                return table[key]    # the newest entry wins, tombstone or not
        return None

    def major_compact(self):
        merged = {}
        for table in self.sstables:  # oldest first, so newer entries overwrite
            merged.update(table)
        live = {k: v for k, v in sorted(merged.items()) if v is not TOMBSTONE}
        self.sstables = [live]       # one file, no tombstones left

db = TinyLSM()
for minute in range(6):
    db.put(f"DL-0412#{minute}", 150 + minute)
db.delete("DL-0412#0")
db.put("DL-0412#6", 156)
db.put("DL-0412#7", 157)

stored = sum(len(t) for t in db.sstables)
print("files:", len(db.sstables), "entries on disk:", stored, "minute 0:", db.get("DL-0412#0"))
db.major_compact()
stored = sum(len(t) for t in db.sstables)
print("files:", len(db.sstables), "entries on disk:", stored, "minute 0:", db.get("DL-0412#0"))

Run it with Python 3 and you should see two lines. First: files: 3 entries on disk: 9 minute 0: None. Second: files: 1 entries on disk: 7 minute 0: None.

What just happened? Before compaction, three files hold nine entries: eight readings and one tombstone. Minute 0 already reads as None, yet its old value still sits on disk. After the major compaction, one file holds seven entries, because the value and its tombstone are both gone.

Compaction also enforces retention. The team gives the air family a five-year TTL (time to live). In HBase, reads skip expired cells straight away, and compaction later drops them from disk without any tombstone.

A tablet is a range of neighbouring rows from one table, and it is the unit Bigtable moves between servers to spread the load. A table starts as one tablet and splits automatically as it grows.

In the paper, each tablet was about 100 to 200 MB by default. HBase calls the same thing a region. Its guide says HBase is designed for 20 to 200 fairly large regions per server, of 5 to 20 GB each.

In HBase, a new table starts as one region, so at first every write hits one server, however good the row key. HBase's guide calls pre-splitting, creating several regions up front, generally a best practice.

Rows are sorted by key, so each tablet covers a clean range, like sensors DL-0001 to DL-1500. Four kinds of parts keep track of the tablets.

• Tablet servers hold tablets and answer reads and writes. The paper describes ten to a thousand tablets per server. A server splits a tablet that grows too large.
• The master assigns tablets to servers, notices dead servers and balances load. Client data never flows through it, so it stays lightly loaded.
• A lock service, Chubby in Bigtable and ZooKeeper in HBase, makes sure only one master is active and tracks which tablet servers are alive.
• A metadata table records which server holds which tablet. Clients look it up and cache the answer.

With an empty cache, a client needs three network round trips to find a tablet. A file in Chubby names the root tablet, the root tablet indexes the METADATA tablets, and those name the user tablets.

A stale cache can need up to six round trips. In HBase, the location of the hbase:meta table, its version of METADATA, is kept in ZooKeeper. HBase 2.6.7 clients look it up there by default, while 3.0.0 clients ask the HBase servers instead.

The diagram shows the team's cluster. Look at the app's arrows: it asks where data lives, then talks to tablet servers directly, never through the master.

Because every file lives on the distributed file system, a tablet server holds no data that exists only on its own disk. When one dies, the master moves its tablets to other servers.

Each new owner reads the tablet's list of SSTables and its redo points, positions in the commit log, from the metadata table. It then replays the log from those points to rebuild the memtable.

One detail surprises people. The paper keeps a single commit log per tablet server, mixing writes for all its tablets in one file. That makes normal writes faster but recovery harder, because the log must be sorted so each new owner reads only its slice.

HBase made the same choice. Its guide says there is usually one WAL per RegionServer (HBase's tablet server), stored in HDFS, with a separate one for the server that carries hbase:meta.

Put the thing you query by first, such as the sensor id, and the time after it. Do not start a row key with a timestamp, because then every new write lands on the same last tablet.

The team's first key was the time followed by the sensor, like 202611030745#DL-0412. It looked tidy. But all 3,000 sensors write the current minute, so every new row sorts after all the old ones.

Pause and predict: the table has four tablets, split evenly over yesterday's data. How many of this minute's 3,000 writes land on each tablet?

All of them land on the last one. HBase's guide calls this hotspotting: a large share of traffic hitting one node, or a few, while the rest sit idle. It advises against a timestamp or a running sequence as the row key.

The fix is to lead with the sensor id. The 3,000 sensors cover the whole key range, so writes spread across every tablet. The team also adds a reversed time after the sensor, so the newest reading sorts first.

from bisect import bisect_right
from collections import Counter
from datetime import datetime, timedelta, timezone

MAX_MINUTE = 99_999_999   # a far-future minute count, for reverse order

def bad_key(sensor, t):
    return f"{t:%Y%m%d%H%M}#{sensor}"                 # time first

def good_key(sensor, t):
    minute = int(t.timestamp() // 60)
    return f"{sensor}#{MAX_MINUTE - minute:08d}"      # sensor first, newest first

now = datetime(2026, 11, 3, 7, 45, tzinfo=timezone.utc)
print(bad_key("DL-0412", now), good_key("DL-0412", now))

# Four tablets, split where yesterday's hourly keys divide into quarters
sensors = [f"DL-{i:04d}" for i in range(1, 3001)]
yesterday = [now - timedelta(days=1, hours=h) for h in range(24)]
for key in (bad_key, good_key):
    old = sorted(key(s, t) for s in sensors for t in yesterday)
    splits = [old[len(old) * q // 4] for q in (1, 2, 3)]
    hits = Counter(bisect_right(splits, key(s, now)) for s in sensors)
    print(key.__name__, [hits[n] for n in range(4)])   # writes per tablet this minute

Run it and you should see three lines. First: 202611030745#DL-0412 DL-0412#70105134. Then bad_key [0, 0, 0, 3000] and good_key [751, 750, 750, 749].

What just happened? bisect_right finds which tablet range a key falls into. With time first, all 3,000 writes of 07:45 went to the last tablet. With the sensor first, each tablet took about 750.

The split points came from yesterday's keys, just as a real table splits along data it already holds.

The line that matters is the return in good_key. Subtracting the minute from a big fixed number makes later times give smaller numbers. The zero padding keeps every number eight digits wide, because row keys sort as text, not as numbers.

As text, 10 sorts before 9, which would scramble the order. The :08d format pads to eight digits, and with this fixed number the width holds until the year 2141.

HBase's guide describes this reverse timestamp trick, with Long.MAX_VALUE (Java's largest long integer) minus the timestamp in place of our smaller number. A scan that starts at DL-0412# now returns the latest reading first, which is what the live screen needs.

Do you still need it? HBase has offered reverse scans since version 0.98. Cloud Bigtable offers them too, but its docs call them less efficient than forward scans and suggest them for short scans of about 50 rows (as of October 2026).

So for a read that runs on every screen load, the reversed time keeps it a cheap forward scan. Google's schema guide adds one warning: avoid starting a key with a reversed timestamp too, for the same hotspot reason.

There is a price. A question like all sensors in Karol Bagh in the last hour no longer matches one range of rows. The team keeps a second small table keyed by ward and time, written alongside the first.

HBase's guide calls this a dual-write secondary index. It costs extra writes and space, which is the normal trade in Bigtable designs.

Leading with an id is not the only fix. HBase's guide lists others, each with a cost.

• Salting: add a random prefix, so writes spread out. Reads must then look under every possible prefix.
• Hashing: derive the prefix from a hash of the key, so a reader can work out the exact key again.
• Reversing: flip a fixed-width number so its fastest-changing digit comes first. This spreads writes but loses the useful sort order.

They share one design; the differences are who runs it, what the parts are called and some limits. Bigtable is Google's system and cloud service, while HBase is open source and usually runs on a Hadoop cluster you manage.

HBase's guide says its HFile format is based on the SSTable from the Bigtable paper. Google's docs say the cloud service can be used through an extension to the Apache HBase library for Java. Once you learn one set of names, the table below translates.

Cassandra uses the same storage pieces: a commit log, memtables, immutable SSTables and compaction. It places data differently. It hashes each partition key onto a ring of nodes, and every replica can accept writes for the keys it owns.

Hashing spreads writes evenly, and no single master hands out row ranges. The cost is that neighbouring partition keys no longer sit together for one cheap range scan.

A wide-column store fits some jobs very well and others badly. Use this checklist before moving data.

• Good fit: huge, steady write streams, like sensor readings, clicks or logs.
• Good fit: reads by key or by short key ranges, like one sensor's last day.
• Good fit: sparse rows, where most possible columns are empty.
• Poor fit: changes that must update many rows together, like moving money between accounts.
• Poor fit: ad hoc queries with joins and filters on any column.
• Poor fit: data small enough for one relational database, which is simpler to run.

The readings pass the first three checks. Billing and user accounts fail them, so they stay in the relational database, and only the readings move.

Beginners can stop here. The surprises below come from cleanup defaults you never chose. Each one comes from the HBase 2.6.7 and 3.0.0 source, the HBase reference guide or Google's docs, as of October 2026.

The weekly major compaction is not weekly

HBase's default period is 7 days, set by hbase.hregion.majorcompaction as 604800000 milliseconds. The shipped jitter is 0.50, so each store's deadline moves by up to half a period either way.

A store with two or more files qualifies once its oldest file is 3.5 to 10.5 days old. We ran the deadline formula 100,000 times and got exactly that range. A lone file qualifies only in special cases, such as expired TTL data. HBase checks after flushes and in a background scan every 10,000 seconds, about 2.8 hours.

The reference guide still says plus or minus 4.8 hours (as of October 2026). The source comment at both tags says plus or minus 3.5 days. Trust the code you deploy, and pin your version.

The random offset is seeded from the store's files, so it stays the same across restarts. The source says this avoids a major compaction storm when a cluster comes back up.

Too many files can stop writes

Each flush adds a file. If compaction falls behind and a store has more than 16 files (hbase.hstore.blockingStoreFiles), HBase delays that region's flushes for up to 90 seconds while it compacts. The property's description says updates are blocked, but the 2.6.7 and 3.0.0 source delays the flush instead.

Writes keep filling the MemStore meanwhile. Once it passes 4 times the flush size, 512 MiB, HBase rejects writes to that region with a RegionTooBusyException until a flush frees memory. A sensor fleet that writes evenly into every region can hit these limits everywhere at once, so watch file counts per store, not only disk space.

Time-series tables have their own compaction policy

HBase ships date tiered compaction, which groups files by the time of their data. Its guide recommends it for scans of limited time ranges, especially recent data, which is exactly a sensor dashboard.

The same guide warns against it for frequent deletes and updates, out-of-order writes, and random gets without a time range. You switch it on per table or column family through hbase.hstore.engine.class.

Expired data can still show up in Cloud Bigtable

Cloud Bigtable removes data that matches a garbage-collection rule during compaction, and its docs say that can take up to a week. Until then, that data still appears in read results.

Google's advice is to add a read filter that matches your garbage-collection rule. A delete also uses extra storage at first, because the tombstone is new data until compaction runs. HBase behaves differently: its reads skip TTL-expired cells at once.

Explain it as a sorted map split into tablets, with LSM storage inside each tablet, and justify each part with the workload it serves.

1. 1

   Start with the workload

   Name the shape: millions of small writes a day, reads by key or recent time range. Say why in-place B-tree updates struggle once the index outgrows memory.

2. 2

   Give the data model

   Row key, column family, qualifier and timestamp. Mention that one row is atomic and rows are sorted by key.

3. 3

   Walk the write path

   Commit log, then memtable, then a flush to an immutable SSTable. Say that this turns random writes into sequential ones.

4. 4

   Walk the read path

   Merge the memtable and SSTables, with Bloom filters for point reads and block indexes to find blocks. Then add compaction to keep the file count low.

5. 5

   Scale out with tablets

   Row ranges split as they grow, a master assigns them, a lock service keeps one master, and files live on a shared file system.

6. 6

   Finish with the row key

   Show the hotspot from a timestamp-first key, then fix it. Mention a second table for a second query shape.

If the interviewer pushes on failure, describe recovery: the master reassigns a dead server's tablets, and the new owners replay the commit log. If they ask about deletes, explain tombstones and major compaction.