Design a Wide-Column Database

Functional

This problem is fundamentally different from most system design interviews. Instead of designing a service that uses a database, you are designing the database itself. Every component you discuss (the storage engine, the replication protocol, the query routing, is internal machinery that a typical system design question treats as a black box. The interviewer wants to see that you understand what happens inside the database when an application calls put(key, value).

A wide-column database stores data in rows identified by a row key, where each row can contain an arbitrary number of columns grouped into column families. Unlike a relational table where every row has the same columns, each row in a wide-column store can have a completely different set of columns. This "wide" schema flexibility is what gives the database its name.

Write and Read Throughput

• Sustained writes: 10,000 writes per second during normal operation, each averaging 1KB (row key + column family data). This gives 10MB/s of sustained write throughput to the storage engine.
• Peak writes: During traffic spikes (batch ingestion, event bursts), writes peak at 50,000 per second = 50MB/s. The memtable must absorb this without back-pressure.
• Reads: 20,000 reads per second. Average response size is 2KB (multi-column rows). This gives 40MB/s of read throughput.
• Combined peak QPS: 50,000 writes + 20,000 reads = 70,000 QPS during the worst-case peak. With consistent hashing across 10 nodes, each node handles roughly 7,000 QPS.

Storage

The API exposes the primitives that clients use to interact with the database. Since we are designing the database itself, these are the internal client-facing operations, not a REST API wrapping another database.

Table and Schema Management

1POST /tables
2{
3"name": "user_events",
4"column_families": ["metadata", "event_data"],
5"partition_key": "user_id",
6"clustering_key": "event_timestamp"
7}

This section is meta, we are designing the internal storage structures of the database itself. There is no external database to choose. Every structure described here lives inside each node of the wide-column cluster.

On-Disk Format: SSTables

An SSTable (Sorted String Table) is an immutable file containing key-value pairs sorted by row key. Each SSTable consists of:

Cluster Topology

The cluster consists of identical nodes, there is no master. Any node can act as the coordinator for a client request. This masterless (peer-to-peer) design eliminates single points of failure: if any node goes down, clients connect to another node and operations continue. Cassandra uses this architecture, while HBase and Bigtable use a master-based approach where a dedicated master node manages region assignments.

Write Path

1. Client sends a write request (PUT /tables/user_events/rows/user_123:2026-03-01) to the coordinator node.
2. Coordinator hashes the row key user_123:2026-03-01 to find the token range. With RF=3, it identifies 3 replica nodes.
3. Coordinator forwards the write to all 3 replica nodes simultaneously.
4. On each replica node, the write follows this path:

LSM-Tree Write Path (GATE)

This is the core mechanism that makes wide-column databases write-optimized. Understanding this end-to-end flow is what separates a strong answer from a surface-level one.

Step 1: WAL Append. The write is serialized and appended to the end of the write-ahead log file. This is a single sequential disk write, the fastest possible disk operation. The WAL is fsync'd to guarantee the write is durable even if the node loses power immediately after. Why sequential? Disk drives (both HDD and SSD) write sequentially at nearly their maximum throughput. No seeking, no page lookup, no index traversal.

LSM-Tree vs B-Tree

This is the foundational choice. LSM-trees optimize writes by converting random I/O into sequential I/O (WAL append + memtable + background compaction). B-trees optimize reads by maintaining a sorted tree structure that supports single-disk-seek point lookups. Wide-column stores choose LSM-trees because their target workloads (time-series, event logging, IoT) are write-heavy. The trade-off: reads may need to check multiple SSTables (read amplification) and compaction generates significant background I/O (write amplification). B-trees have lower read amplification (one tree traversal) but higher write amplification for random writes (each write updates a page in place, potentially triggering page splits).

Masterless vs Master-Based Architecture

Node Crash During Write

A node crashes after appending to the WAL but before the memtable insert is complete (or before the SSTable flush finishes).

Recovery: On restart, the node replays its WAL from the last checkpoint. Each WAL entry is re-inserted into a fresh memtable. Once replay is complete, the memtable is flushed to an SSTable. No data is lost because the WAL is fsync'd before acknowledging the write. The replay is idempotent, replaying the same write twice produces the same result (last-write-wins by timestamp).

Auto-Scaling

Dynamically add or remove nodes based on CPU utilization, storage usage, or QPS thresholds. When storage on existing nodes exceeds 70%, automatically provision a new node, assign it vnodes from the most loaded nodes, and stream data to it. When utilization drops, decommission underused nodes by transferring their vnodes to remaining nodes. This requires integration with cloud infrastructure APIs (AWS Auto Scaling Groups, Kubernetes Horizontal Pod Autoscaler) and careful token rebalancing to avoid hotspots during transitions.

Tiered Storage