Section 5: A Cart That Knows How to Merge - Data Modeling

Executive Summary: Dynamo can tell you that two versions of a cart are concurrent, but it can't tell you what the merged cart should be. Only the shape of the value can answer that. We key each cart as cart:<customerId> and store the whole cart as one object: an observed-remove set, where every add carries a unique add-tag and every remove leaves a tombstone naming the tags it saw. On Dana's split cart, this merge keeps the gift card and keeps the headphones removed. The plain union in the 2007 paper's cart would bring the headphones back, and last-write-wins would silently drop one of the two edits. Each stored record is about 5 KB per replica, kept in a pluggable local engine and grouped into one file per partition.

The interviewer taps the get signature from Section 4. "Your get can hand the cart service two carts. What's inside them that lets it produce one?"

You: "That's the real data-modeling question here. There's no schema to normalize, just one key and one value, and the value has to be designed so that any two versions merge without asking the customer."

The Key: One Cart, One Object

The key is cart:<customerId>. Dana's key is cart:7731, and its MD5 lands in partition 517. Guests get cart:guest:<sessionId>. When a guest signs in, the cart service reads both carts, merges them with the same function it uses for siblings, and writes the result under the customer key. A login merge is just a planned conflict.

Interviewer: "Why not one key per item, like cart:7731:item:kindle? Then the adds never collide."

You: "Because then I can't read the cart. Hashing destroys key order, so there's no range scan to list a customer's items, and the API has no multi-key operation. I'd have to keep a separate index key, and that index would have the same merge problem. A cart is about 4 KB, well under the 1 MB ceiling Dynamo targets, so I rewrite the whole object on each put."