Design a Distributed Multi-Garage Parking System

Design a Distributed, Multi-Garage Parking System

You already built the single-lot allocator: one process, one mutex, a per-size free-list, O(1) park/unpark. That code is correct and it will never see the bug this lab is about — because the bug only exists once the "lot" becomes a network of lots. The moment a parking company runs 5,000 garages across 40 cities, with a mobile app that shows "3 EV spots free at SFO Garage C" and lets you reserve one before you drive there, your in-process mutex is gone. Two regional servers, two customers, one physical spot — and nothing in your single-lot design stops both from getting a confirmed reservation. This is the same double-allocation race from the LLD kata, except now it's a distributed race, and a mutex can't cross a data center boundary. This is the HLD "next version" of that kata, and it's exactly the escalation interviewers pull once you've nailed the single-lot version: "great — now make it work for a chain of 5,000 garages."

Play with it first — geo-sharding is consistent hashing wearing a trench coat

The core routing decision below — "which shard/region owns this garage's data" — is the same mechanism as consistent hashing. Play with the simulator: add and remove nodes (think: regions or shard servers) and watch how few keys (garages) have to move. That's exactly the property you want when a region goes down or you add a fourth data center — most garages should stay pinned to their existing home shard.

Scope it like a senior (ask before you design)

Don't start drawing boxes. Pin these down first — the answers change the design materially:

• Scale: how many garages, how many cities/regions, how many spots per garage on average? (Drives whether one DB region is even plausible.)
• Reservations vs walk-in only: can a user reserve a spot before arriving, or is it first-come-first-served at the gate? (Reservations are what create the distributed double-booking problem — walk-in-only avoids it almost entirely.)
• Freshness of "spots available": does the count shown in the app need to be exact, or is "3 free, give or take a few seconds" acceptable? (This is the whole ballgame for the consistency model.)
• Payments: in scope, or a downstream service we just call? (Assume downstream — don't design a payment ledger inside a parking-availability system.)
• Failure expectations: if a region goes down, is "can't reserve in that city for a minute" acceptable, or must reservations survive a region failure with zero downtime?

Assume for this lab: 5,000 garages, ~200 cities, 3 regions (us-west / us-east / eu-west); reservations ARE supported (that's the interesting problem); availability counts can be a few seconds stale; payments are a downstream call; a region outage may degrade that region's write path but must not corrupt data.

Reason to the design (derive it, don't recite it)

Attempt 1 — one central database, one lock, like the LLD kata but bigger. Every garage's spot counts live in one SQL database in one region; reserve() does the exact same read-modify-write your single-lot allocator did, just now behind a network call. It's correct... and every request from Tokyo pays a trans-Pacific round trip to us-east, and that single database is now a single point of failure for the entire company. This doesn't survive "city-wide, multi-datacenter" — it just moves the LLD kata's bottleneck onto the network instead of removing it.

Attempt 2 — geo-shard by garage. A garage doesn't need to talk to any other garage to answer "do you have a spot" — there's no cross-garage transaction anywhere in this domain. So shard by garage_id (with the shard's home region chosen close to the garage's city — a garage in Austin lives in us-east, one in Munich lives in eu-west). A Global Load Balancer (GeoDNS/Anycast) routes each request to the nearest region, and a lightweight shard directory (garage_id → home region) forwards writes that need to land in a specific garage's home partition. Now most traffic never leaves the region it entered, and a regional outage only blast-radiuses the garages homed there — see Sharding Strategies: range vs hash vs directory vs geo and Data Partitioning for the general mechanism.

Attempt 3 — split the two things that were bundled together. "3 spots free" is read millions of times a day by people just browsing the app, but a reservation write that actually claims a spot happens rarely by comparison, and it's the only place double-booking can occur. Bundling them into one consistency model forces a bad trade either way: make every read strongly consistent and your read-heavy path pays cross-region coordination for no reason; make every write eventually consistent and you double-book spots. So split them: reservation writes are strongly consistent (single partition per garage, atomic conditional write), while availability reads are served from a regional, eventually-consistent replica/cache, refreshed a second or two behind the source of truth via the same CDC/replication stream that already flows out of each home shard. See Strong vs Eventual Consistency — this system is the textbook case of "different consistency for different operations on the same data," not a single global choice.

Build it — the design worksheet

This is the artifact you'd actually produce on a whiteboard or doc in a 45-minute interview. Work through it in order.

1. Back-of-envelope estimation (BOTE)

• Footprint: 5,000 garages × avg 300 spots = 1.5M spots total.
• Turnover events: assume each spot turns over ~8 times/day (park+unpark pairs) → 1.5M × 8 = 12M turnovers/day → 24M entry/exit events/day. Average: 24M / 86,400s ≈ 278 events/s. Rush-hour concentration (~6× average over a few hours) → ~1,700 events/s peak. Each event is a single-row CAS on one garage's counter — trivially partitionable.
• Reservation writes: assume 10% of parks are pre-reserved → 1.2M/day ≈ 14 reservations/s avg, ~80/s peak. Small in absolute terms — this is why paying for strong consistency here is cheap.
• Availability reads (the dominant load): people check the app far more than they park. Assume 5M daily active users × 3 sessions × 3 "nearby garages" queries ≈ 45M reads/day ≈ 520 qps avg, ~3,000 qps peak — this is the path that MUST be served from cache/replica, never from the strongly-consistent write path.
• Storage: reservation rows ≈ 200 bytes; 1.2M/day × 200B × 90-day retention ≈ ~22 GB — fits comfortably in a sharded relational store, no exotic storage engine needed. Garage/spot-type metadata is a few thousand rows, negligible.

2. API sketch

GET  /garages/nearby?lat={}&lon={}&radius_km={}
     -> [{ garage_id, name, distance_m, spots_free_by_type }]   // EVENTUAL, served from regional cache

POST /garages/{garage_id}/reserve
     body: { spot_type, start_time, end_time, user_id }
     -> { reservation_id, lease_expires_at } | 409 SPOT_UNAVAILABLE   // STRONG, single-partition CAS

POST /garages/{garage_id}/enter
     body: { reservation_id? , spot_type? }        // reservation OR walk-in
     -> { ticket_id, spot_id }

POST /garages/{garage_id}/exit
     body: { ticket_id }
     -> { fee }

3. Data model & partitioning

• Shard key = garage_id. Every table below is partitioned by it, so a single request never spans a shard — no distributed transaction is ever required for the hot path. See How Do I Choose a Good Shard Key and Avoid Hotspots.
• garage_registry (small, replicated everywhere, not sharded): garage_id, city, geohash, home_region, spot_type_capacity. This is the directory the Global LB / router consults.
• availability_counter (per garage, per spot type — like the LLD kata's free-list, but a count instead of a stack, because we don't need to hand out a specific physical spot ID until enter()): key (garage_id, spot_type) → available_count, lives in the home shard, updated via conditional write.
• reservation: reservation_id (PK), garage_id (partition key), spot_type, user_id, start_time, end_time, status, lease_expires_at. Colocated with its garage's shard — a reservation and the counter it decremented are one atomic write.

4. High-level diagram — geo-shard routing + the two consistency paths

The reservation path (solid blue) always resolves to exactly one home shard per garage and performs one atomic conditional write there. The availability-read path (dashed amber) never touches that shard directly — it reads a regional replica that trails the source of truth by about a second, fed by the same async replication stream from every garage's home shard.

5. Rubric — what a strong answer hits

• States the scale assumptions and BOTE numbers out loud (§1) — doesn't skip to a diagram.
• Names garage_id as the shard key and explains why (no cross-garage transaction exists in this domain).
• Explicitly splits reservation-write consistency (strong) from availability-read consistency (eventual) — and gives the reason, not just the label.
• Names the concrete mechanism that prevents double-booking — a compare-and-set / conditional write or an equivalent lease-based lock — not a hand-wave "we'd use a lock."
• Identifies at least one hotspot (a single very popular garage) and proposes a concrete mitigation.
• Can defend every entry in the trade-off table (§7) with "buys X, costs Y, use when Z."
• Model-answer reading: the closest existing guide treatments to check your worksheet against are Data Partitioning, Consistent Hashing, Strong vs Eventual Consistency, and Distributed Locking — there's no single "distributed parking" reference page because this lab is a synthesis of exactly those four ideas applied to one concrete domain.

Break it — the distributed double-allocation race

Here's the design flaw a naive-but-plausible answer ships, traced with real numbers. Suppose the naive reserve() does what looks like the obvious distributed version of the LLD kata's logic — but as two separate steps against a counter that's replicated (not single-writer):

// NAIVE — read, check, then write as two separate operations
count = db.read("G123:EV")        // step 1: read
if count > 0:
    db.write("G123:EV", count - 1)  // step 2: write — NOT atomic with step 1
    return CONFIRMED
else:
    return REJECTED

Trace the race: Garage G123 has exactly 1 free EV spot left.

• t=100ms — User A's request lands in us-west (routed there by a stale GLB health check after a brief us-east blip). It reads the local replica: count = 1.
• t=101ms — User B's request, genuinely closer, lands in us-east. Replication from us-west's last write hasn't arrived yet (it's ~1-2s behind by design — that's the eventual-consistency lag we deliberately accepted for reads). It also reads count = 1.
• t=105ms — Both requests independently see count > 0, both write count = 0 to their local region, and both insert a reservation row and return CONFIRMED to their user.
• Result: two confirmed reservations for one physical EV spot. The bug isn't "we forgot a lock" — it's that the read and the write were two independent operations, and the eventually-consistent replica was allowed to serve the write path, not just the read path. That's the same shape as the LLD kata's "split find from remove is the classic bug," except a mutex can't fix it because the two writers are in different processes in different regions.

The fix — make the decrement one atomic, conditional operation, on the single home shard:

-- one round trip, one partition, one row, condition baked into the WHERE clause
UPDATE availability_counter
SET available = available - 1
WHERE garage_id = 'G123' AND spot_type = 'EV' AND available > 0;
-- rows_affected == 0  =>  reject (SPOT_UNAVAILABLE); rows_affected == 1 => commit the reservation row
-- in the SAME transaction as the reservation INSERT.

Whichever request's write reaches the home shard second now affects zero rows — the database itself is the arbiter, and there is only one database instance (the home shard) that is ever allowed to accept this write. An equivalent fix is a distributed lock with a TTL lease (acquire a lease on G123:EV, do read-check-write, release) — strictly more machinery for the same guarantee, so prefer the CAS/conditional-write unless you need to hold the lock across multiple operations (see the trade-off table).

Optimise — with trade-offs

Bottlenecks worth naming out loud:

• The hot popular garage (an airport garage on a holiday weekend): thousands of CAS attempts/second can pile up on one (garage_id, spot_type) row even though the system-wide load is fine. Fix: shard the counter further — e.g., split "EV" into EV#0..EV#7 buckets and CAS a random bucket, summing for reads — the same sharded-counter trick used for hot database rows anywhere else. It buys throughput at the cost of a rare, harmless over-rejection (you might reject a request when bucket #3 is empty but bucket #5 has a spot) — acceptable because a retry with a different bucket resolves it instantly.
• Reservation-write consistency vs availability-read staleness: these are NOT the same knob. Tightening read consistency to "fix" perceived staleness would slow down the 3,000 qps read path to fix a problem the read path doesn't actually have — the reservation CAS is the only place double-booking can occur, and it's already strong. Resist the urge to over-correct the wrong path.
• Reservation-vs-availability skew: a reservation decrements the counter immediately, but if a user never shows up, that spot is "lost" until a no-show reaper releases it at lease_expires_at — size the lease TTL (e.g., 15 min grace) as a product trade-off, not an engineering afterthought.

Decision	Option A	Option B	Pick when
Reservation writes	Strong (single-partition CAS)	Eventual (replicate then reconcile)	Always strong here — the absolute write volume is tiny (≤80/s peak) so the "cost" of strong consistency is negligible, and eventual writes for a scarce physical resource means double-booking, full stop.
Availability reads	Strong (read the home shard)	Eventual (regional cache/replica)	Always eventual here — 3,000 qps of cross-region reads to a single shard would be a self-inflicted bottleneck for a number that's allowed to be a few seconds stale; the reservation CAS is the actual source of truth at the moment it matters.
Data placement	One central store	Geo-sharded by garage_id	Geo-shard once you have garages spread across regions/continents and no cross-garage transaction — which is this domain. Keep one central store only for a single-city deployment where cross-region latency isn't a problem yet.
Concurrency control on the counter	CAS / conditional write	Distributed lock (Redlock/etcd lease)	CAS when the critical section is one row, one operation (this system). Reach for a distributed lock only when you must hold exclusivity across multiple operations (e.g., reserve + charge-hold + notify as one indivisible unit) — and then budget for lease-expiry bugs (a paused process that outlives its TTL).

Defend under pushback

Q1 — "Two users reserve the last spot in different regions at nearly the same time — what actually happens?"
Both requests are routed by the shard directory to the same home shard for that garage (routing is by garage_id, not by the requester's region) — there is only ever one writer for that row. The conditional UPDATE ... WHERE available > 0 executes as two sequential transactions on that one shard; whichever commits first drops available to 0, and the second affects zero rows and gets 409 SPOT_UNAVAILABLE. The user's own region only decided where to route the request, never who wins — the home shard's atomic conditional write is the sole arbiter.

Q2 — "Where exactly is this strong, and where is it eventual — justify each, don't just label them."
Strong: the reservation write (decrement + insert), because it's the only operation that permanently commits a scarce resource, and its volume (~80/s peak) is cheap to serialize on one shard. Eventual: the availability count shown to browsers, because it's read ~40× more often than it's written and a few seconds of staleness costs nothing — worst case a user attempts to reserve a spot that was just taken and gets a polite 409, which is a fine UX outcome for a "check availability" feature.

Q3 — "A garage at an airport goes viral-busy on a holiday — single row becomes a hotspot. What do you do?"
Split that garage's per-type counter into N sub-buckets (e.g., 8) and CAS a randomly chosen bucket; sum buckets for reads. This trades a small chance of a spurious rejection (bucket empty while a sibling bucket has room — resolved by an instant retry against another bucket) for spreading write contention across N rows instead of hammering one. I would NOT solve this by loosening the CAS to eventual consistency — that reintroduces double-booking exactly where it hurts most (the busiest garage).

Q4 — "A region just failed over — the read cache in the new serving region is cold. What happens to users querying availability right after?"
Two options, and I'd combine them: (a) fall back to a slightly-stale last-known-good snapshot replicated cross-region for exactly this case (better an old number than no number), while (b) the cache warms from the CDC stream within its normal ~1-2s lag. Critically, a cold/stale read cache never risks correctness — the reservation path doesn't trust the cache at all; it re-checks against the home shard's live counter at write time. Staleness in the read path is a UX quality issue, never a correctness issue, by construction.

Q5 — "This works at 5,000 garages. What actually breaks first at 10,000, and what doesn't need to change?"
What doesn't change: the shard-per-garage model, the CAS mechanism, and the strong/eventual split — none of those are a function of garage count. What does need attention: the shard directory (garage_id → home region) itself becomes a bigger, more frequently-consulted dataset and a caching layer in front of it (with a short TTL, since garages rarely change home region) becomes worth adding; and the sub-bucketing from Q3 stops being a "hot garage" special case and becomes a default for every popular garage above a QPS threshold, decided by a runtime policy rather than a one-off fix.

What you've mastered when this is done

• You can take a correct single-process LLD design and identify exactly which invariant (the atomic read-modify-write) breaks once state is replicated across regions — and why "just add a lock" doesn't survive the trip.
• You can split one system into a strongly-consistent write path and an eventually-consistent read path, and justify the split by traffic shape and cost of being wrong, not by habit.
• You can name and implement the concrete fix for distributed double-allocation — a conditional write (CAS) on a single-partition row — and explain when a distributed lock with a TTL lease is the better tool instead.
• You can defend hot-partition mitigation (sharded counters) and cold-cache-after-failover behavior without ever compromising the correctness guarantee that actually matters.

---

Re-authored/Deepened for this guide. Escalation of the Design a Parking Lot LLD kata; model-answer concepts: Data Partitioning, Consistent Hashing, Strong vs Eventual Consistency, Distributed Locking.

I just read a lesson on **Design a Distributed Multi-Garage Parking System** (Hands-On Builds) and want to truly understand it. Explain Design a Distributed Multi-Garage Parking System from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Teach me **Design a Distributed Multi-Garage Parking System** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Quiz me on **Design a Distributed Multi-Garage Parking System** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Help me remember **Design a Distributed Multi-Garage Parking System** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.