Section 1: It's Not a Database, It's a Sorted Map - Problem Understanding & Clarifications

Executive Summary: The prompt says "structured data", and that phrase pulls candidates toward one of two reflexes: a distributed SQL database with schemas, joins and multi-row transactions, or a Dynamo-style hashed key-value store that spreads keys evenly and cannot scan. Neither is what the question is testing. Nine clarifying questions turn the prompt into a sparse, sorted, multi-dimensional map, range-partitioned into tablets, served by about a thousand tablet servers whose bytes live in GFS, with Chubby deciding who is alive. The section ends with written assumptions, an out-of-scope list, and the two tenants every later section uses as its running example.

The interviewer reads one paragraph aloud:

"Design a distributed storage system for structured data, like Google's Bigtable. It should hold petabytes across a thousand commodity servers, serve latency-sensitive applications in milliseconds, and feed batch pipelines at gigabytes per second, from the same cluster."

Here's the trap. "Structured data" sounds like rows and columns with types, which sounds like a relational database. One candidate spends twenty minutes on query planners and two-phase commit. Another hears "petabytes" and draws a consistent-hash ring, which shards beautifully and then can't answer "every page from cnn.com" without touching every machine.

The real design sits between them: a map from (row, column, timestamp) to uninterpreted bytes, with rows kept in sorted order. Everything else in this topic is machinery to keep that map fast and alive.

Key Insight: The prompt asks for two opposite workloads, millisecond serving and gigabytes-per-second scanning, from one cluster. That tension, not the data volume, is what the question is really about. A sorted map serves both because a point read and a range scan are the same operation on it, one with a short range and one with a long one.

The Clarification Exchange

Ask questions whose answers visibly remove or add a piece of the design.

You: "Do clients need SQL: ad-hoc queries, joins, a query language?"
Interviewer: "No. The clients are internal applications. They'll link a library."
What died: a parser, a planner, and joins; we ship a client library. Rejected: a SQL engine inside the store. Flip trigger: if joins and ad-hoc queries come to dominate, a SQL layer goes above the store (the Spanner direction, Section 12), never inside it.

You: "Do applications need transactions across rows?"
Interviewer: "The apps we have in mind update one entity at a time: a web page, a user."
What died: distributed transactions, two-phase commit across servers, and the deadlock handling that comes with them. Every mutation to a single row will be atomic, including read-modify-write. Flip trigger: cross-row invariants such as secondary indexes or transfers become common. Then a transaction layer goes on top (Section 12), and the core engine doesn't change.

You: "What consistency do readers expect?"
Interviewer: "If I write a row and read it back, I see my write."
What changed: linearizable consistency per row, inside one cell, so exactly one server owns each row at a time. Rejected: a leaderless, eventually consistent quorum.

You: "What do the workloads look like?"
Interviewer: "Both. A crawler and an indexer that churn through the whole dataset, and user-facing services that read one row in a few milliseconds."
This one adds work: the cell must protect serving latency from batch throughput. Isolation, caching and column-skipping scans all trace back to this answer.

You: "Do the batch jobs scan contiguous key ranges, or only look up keys?"
Interviewer: "They scan. The indexer walks every page of a site together."
What died: hash partitioning. Hashing scatters neighbours, so a scan becomes a broadcast. We partition by row-key range into tablets. Flip trigger: a workload of pure point reads on monotonically increasing keys. Even then the fix is to hash or salt in the application's row key; the engine stays range-based.

You: "How fixed is the schema? Do rows share the same columns?"
Interviewer: "Not at all. A web page might have links from millions of different sites, and most pages have none of them."
What died: fixed columns and per-column nulls. Columns are sparse and unbounded, and only a small set of column families is declared up front. An absent column costs nothing.

You: "Do applications need history, or only the latest value?"
Interviewer: "The crawler keeps a few versions of each page. The personalization team wants a user's recent actions."
What changed: every cell carries a timestamp, and each family declares a garbage-collection policy: keep the last N versions or keep data newer than some age. Rejected: single-version storage plus app-managed history tables.

You: "What's underneath? Do I build replicated disks and a membership service myself?"
Interviewer: "You have GFS for files and Chubby for locks."
What died: our own replication and consensus. Bytes go to GFS, which is replicated and append-only; liveness and fencing go to Chubby. Tablet servers hold no durable state, so moving a tablet moves a pointer, not data (Section 6).

You: "One datacenter, or global?"
Interviewer: "One cell per datacenter to start. Cross-datacenter copies can come later."
What died, for now: synchronous geo-replication. Cross-cell replication arrives later, asynchronous by design (Section 12).

Quick check before moving on: