Section 4: Two Verbs and an Opaque Context - API Design (with Pushback)

Executive Summary: The whole storage contract is two calls. get(key) returns a list of objects plus an opaque context, and put(key, context, object) returns OK. The list exists because hiding concurrent versions would amount to last-write-wins. The context is how the store tells which versions a write supersedes. Delete, compare-and-swap, scans and per-request consistency flags are absent or folded elsewhere, and each absence traces back to "never refuse an add". This section writes the contract, shows the cart's read-modify-write loop, and defends five pushbacks, ending on what OK actually promises.

The interviewer points at Section 3's peak figure. "Twenty-five thousand requests a second at the holiday peak. What do they say to the store?"

You: "Get and put. The unusual parts are what a get returns and what a put must send back. Those two choices let the store accept every write without coordinating with anyone."

The Contract

get(key: bytes) -> (objects: list<bytes>, context: opaque)
put(key: bytes, context: opaque, object: bytes) -> OK

Keys and values are byte arrays the store never looks inside. The MD5 of the key is a 128-bit ring position that picks the partition and its N replicas: Dana's cart:7731 lands in partition 517, preference list B (DC1), F (DC2), K (DC3). Our cart record averages 5 KB and Dynamo targets objects well under 1 MB, so there are no streaming or chunked-upload verbs.

This is the 2007 paper's interface. get returns one object or, when replicas hold versions that don't descend from one another, a list of them, plus a context that put takes back. The context is opaque: the caller only hands it back. Inside are the vector clocks of every version returned, plus a hint the paper adds: which replica answered fastest, so that node coordinates the next write (Section 8 explains why that helps read-your-writes and the 99.9th percentile). The client library coordinates the get itself and sends the put to that node, because vector-clock entries belong to storage nodes (Section 6).

Three things are missing on purpose:

• No delete verb. The cart records removal inside the value as a tombstone on the item's add-tag (Section 5), so it merges like any other change.
• No per-request consistency flags. (N, R, W) and the engine are set per instance: the cart runs (3, 2, 2) on Berkeley DB, a read-heavy catalog instance runs (3, 1, 3). The owning team tunes once; callers don't negotiate quorums.
• No multi-key operations. Section 1 already ruled out cross-key transactions, so every call names exactly one key.

Quick check before moving on: