Requirements and the get/put API

In one line: every mechanism in the rest of this chapter exists because of one of these requirements. Getting them stated precisely is what makes the design defensible instead of arbitrary.

Functional requirements

Functional or non-functional? It depends on context

"Always write" looks like a non-functional requirement — it is availability. In a shopping cart system it reasonably is one.

Following Dynamo's design principles, we treat it as functional here, because it is the defining behavior of the product rather than a quality attribute of it. A store that rejects writes under partition is a different product, not a slower one.

Being able to argue that classification either way — and saying why you chose one — is a genuinely senior move. The label matters less than the reasoning.

Non-functional requirements

• Scalability — the system must support tens of thousands of servers globally. Incremental scalability is essential: servers can be added or removed with minimal service disruption.
• Fault tolerance — the system must operate uninterrupted despite server or component failures.

"Incremental scalability with minimal disruption" is the phrase that kills modulo hashing in the next lesson. Read it as a hard constraint, not an aspiration.

Assumptions

Three simplifications, stated so the interviewer can challenge them:

• Data centers hosting the service are trusted (non-hostile).
• Authentication and authorization are handled externally.
• User requests and responses use HTTPS.

The first is the interesting one — it lets us assume crash faults rather than Byzantine faults, which is what makes gossip and quorums sufficient. In an adversarial setting the whole design would need 3f+1 replicas and signed messages.

API design

Like hash tables, key-value stores provide exactly two primary operations.

The get function

get(key)

Returns the value associated with key. In replicated environments the system locates the object replica, hidden from the user. If configured for weaker consistency — eventual consistency — the system may return multiple values (versions) for a single key.

The put function

put(key, value)

Stores the value associated with key. The system automatically determines data placement and maintains metadata such as the object version.

Read that get() note again — it is the whole chapter in one sentence

"May return multiple values for a single key."

A hash table returns one value. This returns several, because under an always-write requirement two clients can write concurrently to different nodes and both writes must survive. The store cannot decide which is correct, so it hands you all of them.

That single API consequence generates vector clocks (Lesson 6), reconciliation, and the context parameter the API grows in Lesson 6. If you notice it early in an interview, you have effectively predicted the rest of the design.

Data type

The key serves as the unique identifier; the value can be any arbitrary binary data.

What happens on one node

Everything after this lesson is about distribution — which node holds a key, how many copies exist, how they reconcile. None of that says how a single node actually stores and finds a value, and an interviewer will often ask, because the answer explains why these systems are so write-fast.

The obvious structure is the one a relational database uses: a B-tree, kept sorted on disk, updated in place. It gives excellent reads. It gives poor writes at this scale, because updating in place means a random write — seek to the right page, modify it, write it back — and random writes are the slowest thing a disk does.

A key-value store built for write throughput inverts it.

This is the log-structured merge tree. Every write is an append or an in-memory insert, so writes are sequential and fast regardless of which key was written. Nothing is ever modified in place — an update writes a new version, and the old one stays until compaction removes it.

That immutability is the same property the blob store relied on, and it buys the same things here: no in-place mutation means no partial-update failures, and files that never change are trivially safe to copy, cache, and repair.

Reads pay for what writes saved

The cost lands on the read path, and it is the honest trade to state.

Two mechanisms make it tolerable.

Bloom filters. Each SSTable carries a small probabilistic structure that answers "is this key definitely not here?" A negative is certain, so most files are skipped without being read at all. A positive may be wrong, which costs one unnecessary lookup — a false-positive rate traded against memory. It is the right shape of tool precisely because the expensive outcome (reading a file) is the one it can rule out.

Compaction. A background process merges SSTables, keeping the newest version of each key and discarding superseded ones. That bounds the number of files a read must consult, and it is where obsolete data is actually reclaimed.

Compaction is also where the cost reappears, which is worth naming rather than glossing: it consumes disk I/O and CPU continuously in the background, competing with live traffic. So the trade is not "writes are free" — it is write amplification moved off the critical path, paid later by a process you have to size and schedule.

The one-line version to carry: B-trees optimise reads and pay on every write; LSM trees optimise writes and pay on reads and in compaction. Which is right depends on the ratio, and a key-value store at web scale is overwhelmingly write-heavy.

Why we start with the non-functional requirements

The next lesson begins with scalability rather than with features, because the chosen scalability strategy shapes how the functional requirements are implemented. Consistent hashing determines where data lives; where data lives determines how it is replicated; how it is replicated determines what conflicts are possible.

Interview signal by level

Next: making it scale, and why the obvious approach fails.