System design practice

Always-writable Shopping Cart

easy Based on a system published by Amazon availability consistency replication real-world

Amazon's Dynamo cart: never reject an add; merge versions on read.

Solve it in your browser Read the lesson first

Amazon's shopping cart must take every "Add to cart", even while servers, disks or network links fail: an add that is rejected or forgotten is a lost sale. This is the service Amazon built Dynamo for. Dynamo gives up consistency under failure to stay writable: any replica takes a write, and when concurrent writes leave several versions of a cart, the application merges them on the next read.

Functional requirements

Use these use case and scenario names exactly: the traffic, requirements and tests in problem.proschi refer to them.

Scale

Constraints

What is given

problem.proschi declares the shopper and holds the traffic, requirements and tests. Add the components, the connections and the two use cases.

Based on

How your design is checked

You write the design as text in Proschi. Tests run in your browser: a simulation of the traffic above checks latency, availability, cost and what happens when a machine fails. How the simulation works.

Start designing

Lesson · 14 min read

Learn it: Always-writable Shopping Cart #

What you'll learn #

The problem, explained #

This problem is modelled on a real system. In 2007 Amazon published the paper on Dynamo, the key-value store built because some services, the shopping cart first, must stay writable whatever is failing. If "Add to cart" fails, the customer may leave and the sale is gone: a briefly out-of-date cart is an annoyance, a rejected add is lost revenue.

Two use cases:

The non-functional requirements:

given.proschi declares the shopper and the traffic mix ("One version" 99.94%, "Divergent versions" 0.06%), the requirements and two tests:

  1. Adds go to an eventually consistent store that is always writable: Add to cart writes a database before answering, never calls a strong store, and answers 200.
  2. Divergent versions are merged and written back: View cart has a "Divergent versions" scenario that writes to a database before answering.

Back-of-the-envelope #

of downtime a month at five nines
≈ 26 s
of downtime a year
≈ 5.3 min
best write availability of one primary
99.995%
writes to the store
≈ 500 rps
merges
≈ 0.6 / s
QuantityArithmeticResult
Write share500 ÷ (500 + 1,000)one request in three is a write
Merges per second1,000 × 0.06%≈ 0.6
Writes to the store500 adds + 0.6 merges≈ 500 rps
Reads from the store1,000 views1,000 rps
Five nines, per year525,600 min × 0.001%≈ 5.3 minutes of downtime
Five nines, per month43,200 min × 0.001%≈ 26 seconds of downtime
Cart data (assumption)100 M carts × 2 KB≈ 200 GB (600 GB in three copies)

The cart count and size are assumptions to show the method; far more still fits one store with replicas.

Availability per component, with the simulation's default numbers:

ComponentUp per replicaWith 2 replicasWith 3 replicas
Load balancer99.99%99.999999%—
Service ([REST API])99.5%99.9975%99.99999%
Leaderless NoSQL ([DynamoDB])99.99%99.999999%≈ 100%
Relational ([PostgreSQL]), writes99.95%99.995%99.995%

The last row is the key insight. In the model, as in real life, a relational database has one primary per shard taking every write. Replicas serve reads and can be promoted when the primary dies, but writes wait out the promotion. The simulation keeps 10% of the primary's downtime for that, so writes reach 99.995% however many replicas you add: below five nines, by design.

A leaderless store takes a write on any replica, so each added replica cuts its unavailability by another factor. Path availability is the product of its nodes: with enough replicas of each, Add to cart comes out far above 99.999%.

The store is not the only link to check. The service is the least reliable machine on the path (99.5%), and two replicas of it give 99.9975%: already below five nines, whatever the store does. It needs three.

Load and latency:

Concepts #

Availability vs consistency #

What it is. When the network splits replicas apart (a partition), a replicated store must choose: refuse requests it can't coordinate (stay consistent: every read sees the latest write), or accept them and reconcile later (stay available). That's the CAP theorem in one sentence. Even without partitions, coordinating every write costs latency, and a single coordinator, such as a primary, is one place where writes stop.

Why it matters here. The business has chosen: an add is never rejected. That makes the cart an AP system (available under partition), with eventual consistency: replicas converge once they can talk again.

Trade-offs. Readers may briefly see an older cart, and two versions may coexist; the application must handle that.

When not to choose availability. Money, inventory counts, unique usernames: anything where two conflicting "yes" answers can't be merged afterwards. They come in this roadmap's consistency stage.

title "Strong vs eventual"

app    "App"          [REST API]   x2
ledger "Ledger"       [PostgreSQL] x2 "Strong: one primary orders every write"
prefs  "Preferences"  [Cassandra]  x3 "Eventual: any replica takes a write"

app -> ledger : SQL
app -> prefs  : CQL

Leaderless replication and quorums #

What it is. In a leaderless store (Dynamo, Cassandra, Riak), every key is copied to N replicas. A write goes to all N and succeeds once W acknowledge; a read waits for R answers. With N=3, W=2, R=2 (common, per the Dynamo paper), any read overlaps any successful write on at least one replica, because R + W > N.

Why it's always writable. No replica is special, so losing one doesn't stop writes. Dynamo goes further with a sloppy quorum: if some of a key's usual replicas are unreachable, the write goes to the next healthy nodes, which hold it as a hint and hand it back when the owners return (hinted handoff). The add is accepted and durable even mid-failure.

Trade-offs. Lower W means faster, more available writes but a greater chance of stale reads. Concurrent writes to different replicas create conflicts that someone has to resolve. Operations get harder: background repair (Dynamo compares replicas with Merkle trees) and membership gossip.

When not to use it. When you need transactions across keys, unique constraints or strict ordering: a relational database with a primary is simpler and gives you those.

title "Leaderless store"

client "Client"     [Actor]
svc    "Service"    [REST API]  x3
kv     "Replicated" [DynamoDB]  x3 "N=3: any replica takes a write"

client -> svc
svc    -> kv : read / write

usecase "Save" {
  client -> svc   : PUT /things/7
  svc    -> kv    : PutItem thing 7
  kv    --> svc   : ok from W replicas
  svc   --> client : 200
}

Versioning and merge on read #

What it is. If two writes to the same cart land on different replicas without seeing each other, neither is "newer": they are concurrent. Dynamo tags every version with a vector clock, a small list of (node, counter) pairs. Comparing two clocks tells whether one version descends from the other (keep the descendant) or they're concurrent (keep both, and return all of them to the application on read).

Why merge in the application. Only the application knows what a cart means. The union of the items in both versions keeps every add. The merged cart is written back with a clock descending from both, resolving the conflict for every later reader.

Trade-offs. The union can bring back an item the shopper deleted in one of the versions. Amazon judged that acceptable: a resurrected item is a nuisance, a lost add is a lost sale.

When not to use it. When there's no meaningful merge (two people booking the last seat), or conflicts are rare and harmless enough for last-write-wins (a "last seen" timestamp).

Deep dive Merge on read in Proschi
title "Merge on read"

client "Client"   [Actor]
svc    "Service"  [REST API] x2
kv     "Store"    [DynamoDB] x3

client -> svc
svc    -> kv : read / write

usecase "Read doc" {
  client -> svc : GET /docs/7
  svc    -> kv  : GetItem doc 7, every version
  alt "Single" {
    kv --> svc : one version
  } alt "Conflict" {
    kv  --> svc : two versions
    svc  -> kv  : PutItem merged doc 7
    kv  --> svc : ok
  }
  svc --> client : 200
}
Deep dive Dynamo is not DynamoDB

The 2007 Dynamo paper and today's Amazon DynamoDB service are not the same system. DynamoDB isn't leaderless: each partition elects a leader replica (with Multi-Paxos) that takes its writes. It doesn't hand you vector clocks or sibling versions either; you'd use conditional writes instead. The open-source store closest to the paper is Riak, which keeps sibling versions. Cassandra shares the leaderless replication but settles conflicts by timestamp: last write wins. In Proschi, [DynamoDB] simply stands for a leaderless, eventually consistent store, which is the property this problem is about.

Designing it step by step #

Step 1: Scope #

Ask what failure means to the business: "If the cart can't take an add for 30 seconds, what happens?" Lost sales justifies everything else. Confirm the numbers: 500 adds, 1k views, five nines on adds, p99.9 under 300 ms. Checkout, prices and inventory are out of scope; checkout is where you do want strong consistency, in a different service.

Step 2: High-level design #

Shopper → load balancer → stateless cart service → store, which holds all state. Draw both use cases; for View cart write both scenarios with alt and when conditions that explain them.

The first real decision is the store:

OptionUpsideCost
Relational with replicasFamiliar, transactionalEvery add needs the one primary, and a failover blocks adds: writes cap out around 99.995%
An in-memory cacheFast and always writableA node restarts and the adds are gone
A leaderless, eventually consistent storeAny replica takes a write; durability comes from writing to several disksConflict handling

The third fits the requirement, and the tests check that adds never touch a strong store.

Step 3: Deep dive #

The add. The service writes the cart with its version information and answers 200 only after the store acknowledges. No queues, no write-behind: the add is durable before the answer.

The view. Read every version. "One version" needs nothing more. In "Divergent versions", merge (union of items), write the merged cart back, then answer; otherwise every future read sees the conflict again and versions pile up.

Replication. How many replicas of each node does five nines take? Use the table above and multiply along the path: load balancer × service × store. The service decides it: two replicas (99.9975%) miss the target on their own, three pass. survive any node failure removes one replica of each node and re-checks saturation and latency, so a node with one replica fails it.

Cost. The store is the expensive line. Price your replica counts against the $3,000 limit before running the analysis, and don't pay for replicas that neither availability nor load needs.

Step 4: Wrap up #

"A stateless cart service over a leaderless, replicated store. Adds go to any replica, so they're accepted during failures. Concurrent writes leave versions; reads merge them by union and write the result back. We accept that a deleted item may reappear; we never lose an add." Then name the edges: checkout (re-validate the cart against a strongly consistent order system), bounding version growth, and monitoring conflict rates.

Common mistakes #

Carts in PostgreSQL (wrong/carts-in-postgres). The most natural first answer, and wrong here. Every add goes to one primary per shard; when it fails, adds are rejected until a replica is promoted: in the real world, a burst of failed adds during every failover and every primary maintenance window. Caught twice: Adds go to an eventually consistent store that is always writable (PostgreSQL is a strong store) and availability of Add to cart ≥ 99.999% (writes reach 99.995% at best).

Carts in Redis (wrong/carts-in-redis). Fast and always writable, so tempting. But a cache keeps data in memory: a restart, an eviction or a failover with asynchronous replication can drop adds the shopper already saw confirmed. Caught by Add to cart is durable; both flow tests fail too, because they ask for a database and a cache is not one.

Last write wins (wrong/last-write-wins). The design reads both versions and keeps the newest, writing nothing back. Two tabs (or one shopper on phone and laptop) add different items at the same moment, and one add silently disappears; clock skew between servers makes "newest" unreliable too. Caught by Divergent versions are merged and written back.

Merging without writing back. The view looks right, but the conflict is never resolved: every reader pays for the merge and versions accumulate. Also caught by Divergent versions are merged and written back.

A single store replica. A single point of failure: 99.99% alone, short of five nines before the rest of the path counts. Caught by availability of Add to cart ≥ 99.999% and survive any node failure. Two replicas pass the simulation's arithmetic; a real quorum system wants a third, so a write quorum survives losing one copy.

Two service replicas. "Two of everything" feels safe and survives a node failure, but two replicas at 99.5% each give 99.9975%, under five nines before the store is even counted. Caught by availability of Add to cart ≥ 99.999%. The least reliable component on the path sets how many replicas you need, and here that is the service, not the store.

In the interview #

Follow-up questions:

Further reading #

Now design it

Review cards for this problem

Short questions on the ideas it needs, from the review cards. Review them daily so they stick.

More system design problems