Design a Wide-Column Store

The ask

The ask is a database for tables with billions of rows. Each row describes one thing, like one user or one device.

A row key is the name that identifies one row. Different rows need different facts, and each row is found by its key.

One user row carries a city, and another carries none. Empty facts stay absent instead of stored as blanks.

Writes pour in all day. Reads fetch one row, or a run of rows, by key.

Joins across tables are not offered. Fast writes and fast single-row reads come first.

Estimate the scale

The worked table holds 10,000,000,000 rows. One row takes 1 KB.

10,000,000,000 rows x 1 KB = 10 TB in the table.

Writes reach 100,000,000 a day.

100,000,000 writes / 86,400 seconds = 1,157 writes per second.

100,000,000 writes x 1 KB = 100 GB of new rows a day.

API and data

Put takes a row key, a column name, and a value. Get takes a row key and returns its columns.

Columns group into families that are stored together. A column family is a set of columns usually read together.

A cell can hold several versions over time. Each version carries the time it was written.

Empty columns cost nothing. A row stores only the columns it actually has.

High-level design

Rows are split by row key across many servers. Each server owns a range of keys.

A write lands on the server that owns its row key. A read for one row visits one server.

Copies of each range live on other servers. A server failure does not lose its rows.

Sorting is built in. Rows stay ordered by row key on each server, so runs of rows read fast.

Deep dive: the write path

Every write enters the write-ahead log first. The log sits on disk, so accepted writes survive a crash.

The write then lands in a memory table. The memory table holds recent writes in sorted order.

When the memory table fills, its contents flush to disk as a sorted file. The log entries for those writes are then discarded.

Writes never update old files in place. New files appear instead, and reads merge the pieces.

Reading a row

A read checks the memory table first. The newest version of each column wins.

Sorted files are checked next, newest first. The search stops once every asked column is found.

Small summaries on each file say which keys it can hold. Files outside the key are skipped.

Many small files slow reads down. Background merging combines small files into larger ones.

Deletes and versions

A delete writes a marker instead of erasing at once. The marker hides older versions of the cell.

Background merging removes marked data for good. Space returns during merges, not during the delete.

Old versions fade by a stated keeping rule. A cell keeps only recent versions, and the rest drop away during merges.

When a server fails

The write-ahead log is copied to other servers. A copy can replay the log and take over the range.

Checks that a server answers run between servers. Silence moves the range to a healthy server.

Reads continue from copies during the handover. Writes pause briefly for the affected range only.

Evaluation and trade-offs

Writes are cheap because they append and sort later. Reads pay for merging pieces across files.

Rows must be designed around their key. A bad key choice concentrates writes on one server.

The store suits huge tables with uneven columns. Small, joined tables belong in a relational database.

Each row carries the columns it needs, and no row pays for columns it lacks. That freedom is the point of the wide shape.

The table in numbers