Design an Efficient Parking Lot System

You build a parking app. A driver reserves a spot for 2-4 PM, drives across town, and arrives to find someone else parked there. The reservation was double-booked. The real challenge is not finding an open spot, it is guaranteeing that the spot you reserved is still yours when you arrive, even when hundreds of users are booking the same lot simultaneously.

Functional

Reserve a parking spot for a time window: Users specify a lot, vehicle type, start time, and end time. The system finds an available spot and creates a reservation. This is the core operation that the entire architecture must protect from race conditions. Note that the user reserves a specific lot, not a specific spot, the system assigns the best available spot. This design choice simplifies the user experience (no spot-by-spot browsing) and gives the system freedom to optimize spot assignment for utilization.

Pay for the reservation: After reserving, the user is redirected to a third-party payment provider (Stripe, PayPal). The reservation is held in a tentative state until payment completes. If payment does not complete within 15 minutes, the hold is released.

Check in and check out at the physical gate: When the vehicle arrives, the gate hardware scans a QR code or license plate, records the check-in time, and opens the barrier. On departure, the gate records the check-out time.

Handle no-shows: If a user makes a reservation but never arrives, the system cancels the reservation after a grace period and charges for the first 24 hours per policy. The no-show detection is inherently asynchronous, you cannot detect the absence of an event (vehicle arrival) in real time. A background monitor must periodically scan for confirmed reservations with no matching check-in transaction.

Check capacity and pricing before booking: Users can query how many spots are available in a given lot for a given time window and see pricing before committing to a reservation. This is the most frequently called API, for every user who books, 5-10 users browse first. It must be fast (sub-100ms) but does not need to be perfectly accurate, since the authoritative check happens inside reserve_spot.

Handle overstay billing: If a vehicle stays past the reservation end time, the system calculates additional charges based on the lot's hourly rate, rounded up to the nearest 15-minute slot. The overstay charge is billed to the payment method on file. This means the system must track not just reservations but also physical presence, comparing check-out time against reservation end time.

Non-Functional

Strong consistency (no double-booking): This is the defining requirement. Once a spot is reserved for a time window, no other user can reserve the same spot for an overlapping window. A single double-booking destroys user trust.

High availability: The system must stay operational during component failures. A cache failure should not prevent bookings, it should just be slower. The architecture achieves this through graceful degradation: each component has a fallback path. Cache down? Query the database directly. Payment provider down? Hold the reservation and reconcile later. Gate offline? Validate against a local cache of confirmed reservations.

Scalability: 1000+ parking lots across 10 countries, 200 spots per lot, 200K reservations per day globally. The system must scale horizontally without sacrificing consistency, adding lots should not require architectural changes. The sharding strategy (by lot_id) means adding a new lot is a data operation, not an architectural one, provision the lot's data on the appropriate shard and it inherits all existing reservation, payment, and gate functionality.

Out of Scope

Real-time navigation, valet services, multi-vehicle fleet management, dynamic surge pricing, per-floor capacity tracking, and ADA spot compliance are out of scope. These are valuable features but do not change the core reservation algorithm.

The core thesis: a parking lot reservation system is fundamentally a time-slot overlap detection problem. When a user calls reserve_spot(lot_id, start, end), the system must find a spot where no existing reservation overlaps the requested time window, and do so atomically while hundreds of other users compete for the same lot. The naive approach (query available spots, pick one, INSERT) has a TOCTOU race condition: two users both see spot #42 as available and both reserve it. The entire architecture, bitmap representation, SELECT FOR UPDATE, single-shard transactions, advisory-only cache, flows from solving this one problem correctly.

The data is surprisingly small, and that drives the biggest architectural decision. When you estimate the numbers, you discover that the entire reservation dataset fits comfortably in a single relational database. That means you get ACID transactions and strong consistency for free, without any distributed systems complexity.

Traffic

10 countries with 100 lots each gives 1000 parking lots. Each lot has 200 spots and receives roughly 200 reservation requests per day. That is 200K reservations per day globally, or about 2.3 QPS on average. Even at peak hours, a single hot lot might see 10 QPS, well within PostgreSQL's comfort zone.

The read-to-write ratio is roughly 10:1. For every user who books (reserve_spot), about 10 users browse (check_capacity). That means roughly 23 QPS of reads and 2.3 QPS of writes. The reads hit the Redis cache, the writes hit PostgreSQL. This asymmetry is why the advisory cache makes sense, it absorbs the majority of traffic (browsing) while the database handles only the minority that matters (booking).

Storage

Each reservation record contains a reservation ID, spot ID, user ID, start time, end time, status, and payment status, roughly 128 bytes. At 200K reservations per day, the system generates 25.6 MB of data daily. Over 2 years with 50% growth, that totals approximately 280 GB. This is comfortably within a single PostgreSQL instance.

Bitmap Overhead

Each spot needs a 96-bit bitmap per day (24 hours divided into 15-minute slots). That is 12 bytes per spot per day, or roughly 4 KB per spot per year. For all spots: 1000 lots x 200 spots x 4 KB = 800 MB total. This fits entirely in Redis cache for fast advisory checks.

Stay Profile

80% of users park short-term (averaging 4 hours). 20% park long-term (averaging 5 days). Long-term reservations occupy more bitmap slots but are less frequent, the system handles both identically through the same bitmap mechanism.

A 4-hour short-term stay occupies 16 bitmap slots (4 hours x 4 slots per hour). A 5-day long-term stay occupies 480 slots across 5 daily bitmaps. The bitmap approach handles both naturally, the check and update operations are identical. The only difference is that long-term reservations span multiple daily bitmaps, requiring the availability check to iterate over more days. But each daily check is still a single O(1) bitwise AND operation.

Why These Numbers Matter

The low write volume is why SELECT FOR UPDATE works without bottlenecks. Locking a row for a few milliseconds at 10 QPS (peak for a hot lot) means negligible contention. At 10,000 QPS, the serialization from row-level locks would become a real bottleneck and you would need optimistic concurrency or distributed locks instead.

The 10:1 read-to-write ratio is why the Redis cache exists. For every user who actually books, 5-10 users checked capacity first. The cache absorbs this browsing load so the database handles only the transactional writes that require ACID guarantees.

Two sets of users need two sets of APIs. End users search, reserve, and pay. Gate hardware at the physical lot checks vehicles in and out. Mixing them creates a confusing interface, the gate does not care about pricing, and the user does not call vehicle_arrived. The separation also enables independent scaling, user-facing APIs handle bursty traffic (everyone books at the same time for a concert), while gate APIs handle steady traffic (vehicles arrive and leave throughout the day).

User APIs

check_capacity(lot_id, vehicle_type, start_time, end_time): Returns available spot count and price for the requested window. Reads from Redis cache for fast response. If cache is stale or unavailable, falls back to database. The response includes both the count and the price so users can make an informed decision before committing. The response does not reveal which specific spots are available, only the count. This prevents users from racing to specific spots and simplifies the API.

reserve_spot(user_id, lot_id, vehicle_type, start_time, end_time): Finds an available spot, creates a TENTATIVE reservation, and returns the reservation_id plus a payment redirect URL. The spot is held for 15 minutes while the user completes payment. This is the most critical endpoint, it must be atomic, consistent, and handle concurrent access correctly. The response includes the assigned spot number (for the gate display), the payment URL, and the hold expiration time so the client can show a countdown.

complete_reservation(user_id, reservation_id, payment_token): Verifies the payment token with the third-party provider and updates the reservation status to CONFIRMED. If the token is invalid, the reservation stays TENTATIVE until the hold expires. This endpoint does not touch the bitmap, the bitmap was already updated during reserve_spot. It only changes the reservation status.

Gate APIs

vehicle_arrived(reservation_id, timestamp): Records check-in time in the Transaction table. Called by the gate hardware when a vehicle enters. The gate validates the reservation exists and has status=CONFIRMED before opening the barrier.

vehicle_left(reservation_id, timestamp): Records check-out time. If the vehicle stayed past the reservation end time, flags the overstay for additional charges. The charge is calculated based on the lot's hourly rate for the overstay duration, rounded up to the nearest 15-minute slot.

Notice the gate APIs take reservation_id, not spot_id. The gate scans the reservation QR code, it does not need to know which physical spot the vehicle is in. The system maps reservation to spot internally. This means the gate hardware is stateless, it does not track which vehicles are in which spots. It only records entry and exit events, letting the backend handle all business logic.

Payment Flow

The reserve_spot endpoint creates a tentative hold, not a finalized booking. The user pays via a third-party provider. Then complete_reservation verifies the payment and finalizes. If payment does not complete within 15 minutes, a background sweeper releases the hold and clears the bitmap bits.

Why three API calls instead of one? A single "book and pay" endpoint would need to hold a database lock while the user interacts with the payment provider, potentially minutes. This blocks other users from reserving that spot. The three-call flow separates the fast database operation (reserve_spot takes milliseconds) from the slow external call (payment takes seconds to minutes), minimizing lock hold time.

The Reservation table is the center of this system. Every other table exists to support it. The key design decision is how to represent time-slot availability efficiently, this is where the bitmap column lives.

A strong database design in an interview demonstrates that you understand how the data model supports the core algorithm. The bitmap lives in the Spot table because reserve_spot needs to lock a spot row and check its bitmap atomically. The Transaction table is separate from Reservation because gate events should not create write contention with booking operations. Every table placement decision connects back to the reservation consistency requirement.

Reservation Table

1reservation_id PK
2spot_id FK -> Spot
3user_id FK -> User
4start_time TIMESTAMP
5end_time TIMESTAMP
6status ENUM (TENTATIVE, CONFIRMED, CANCELLED, COMPLETED, NO_SHOW)
7payment_status ENUM (PENDING, PAID, REFUNDED)
8created_at TIMESTAMP
9expires_at TIMESTAMP

The status field tracks the reservation lifecycle: TENTATIVE (created, awaiting payment), CONFIRMED (paid), CANCELLED (expired or cancelled by user), COMPLETED (vehicle checked out), NO_SHOW (no check-in after grace period). Transitions are strictly ordered, a reservation can only move forward through these states, never backward. Each transition has exactly one writer service, preventing cross-service status conflicts.

Composite index on (spot_id, start_time, end_time) enables efficient overlap queries as a fallback when bitmaps are unavailable.

Spot Table

1spot_id PK
2lot_id FK -> Lot
3spot_label VARCHAR
4spot_type ENUM (COMPACT, STANDARD, LARGE)
5floor_number INT
6bitmap BYTEA (12 bytes per day, 96 bits)

The bitmap column stores the daily availability schedule. Each bit represents a 15-minute slot. A 1 means occupied, a 0 means free. Updated atomically inside the same transaction that inserts the reservation.

Why store the bitmap in the Spot table rather than a separate table? Because the SELECT FOR UPDATE during reserve_spot locks the spot row to check the bitmap. If the bitmap were in a separate table, you would need to lock rows in two tables within the same transaction, increasing lock overhead and the risk of deadlocks. Co-locating the bitmap with the spot data means one lock, one row, one atomic operation.

Lot Table

1lot_id PK
2name VARCHAR
3address VARCHAR
4capacity INT
5timezone VARCHAR
6contact_info VARCHAR

User and Vehicle Tables

1user_id PK vehicle_id PK
2email VARCHAR user_id FK -> User
3phone VARCHAR license_plate VARCHAR
4vehicle_type ENUM (COMPACT, STANDARD, LARGE)

Transaction Table

1transaction_id PK
2reservation_id FK -> Reservation
3check_in_time TIMESTAMP
4check_out_time TIMESTAMP

This is an append-only audit trail of physical gate events. Each row records one vehicle entering and leaving. It is separate from Reservation because a reservation is a booking intent, while a transaction is a physical event.

The separation matters for queries too. "Show me all reservations for lot X next week" queries the Reservation table. "Show me all vehicles that overstayed in lot X this month" queries the Transaction table joined with Reservation on end_time. Different questions, different tables, different access patterns.

Status Lifecycle

A reservation moves through these states:

TENTATIVE → CONFIRMED → COMPLETED
↘ CANCELLED (hold expired or user cancelled)
↘ NO_SHOW (no check-in after 8h)

TENTATIVE: spot is held, bitmap is set, awaiting payment (15-min timeout). CONFIRMED: payment verified, user can arrive at the gate. COMPLETED: vehicle has checked out, transaction record exists. CANCELLED: hold expired, user cancelled, or admin override. NO_SHOW: no check-in after grace period, charged per policy. Only forward transitions are allowed, a CONFIRMED reservation cannot go back to TENTATIVE.

Each transition has exactly one writer: reserve_spot creates TENTATIVE, complete_reservation moves to CONFIRMED, vehicle_left triggers COMPLETED, the hold sweeper moves to CANCELLED, and the no-show monitor moves to NO_SHOW. No two services compete to set the same status. The status column uses a PostgreSQL CHECK constraint to enforce valid transitions, the database rejects any UPDATE that violates the lifecycle ordering.

Why RDB Over NoSQL for This Schema

The Reservation table has foreign keys to Spot, User, and Vehicle. The Transaction table has a foreign key to Reservation. These relational constraints are natural for RDB and awkward in NoSQL. More importantly, the bitmap update and reservation INSERT must happen in the same ACID transaction, PostgreSQL provides this natively, while DynamoDB or Cassandra would require application-level coordination. A DynamoDB approach would need conditional writes (PutItem with ConditionExpression) for optimistic concurrency, plus a separate mechanism to ensure bitmap-reservation atomicity, adding application-level complexity that PostgreSQL gives you for free.

Sharding Strategy

Partition by lot_id. All spots, reservations, and transactions for a lot live on the same shard. This means the SELECT FOR UPDATE transaction never crosses shard boundaries, single-shard ACID transactions handle all concurrency. A user who has reservations at multiple lots will have data on multiple shards, the user-facing "my reservations" page requires a scatter-gather query. This is acceptable because it is a read-only, non-critical query that tolerates higher latency. The critical write path (reserve_spot) is always single-shard.

Five components, one critical invariant: the Reservation Service is the only component that writes reservations, and it always does so inside a transaction. Everything else (the cache, the gate service, the payment provider) is either advisory or downstream.

API Gateway: Rate limiting, TLS termination, authentication, and request routing. Routes reservation-related requests to the Reservation Service and gate-related requests to the Transaction Service. Also protects against DDoS attacks that could prevent legitimate users from booking during high-demand events. Rate limiting is per-user for check_capacity (prevent scraping) and per-lot for reserve_spot (prevent inventory hoarding). The gateway also validates request parameters before forwarding, rejecting requests with end_time before start_time or reservation windows exceeding the maximum allowed duration (7 days).

Reservation Service: Handles check_capacity, reserve_spot, and complete_reservation. This is the only service that writes to the Reservation table and updates bitmaps. All writes happen inside PostgreSQL transactions. This single-writer design is intentional, having one service own all bitmap mutations eliminates cross-service coordination and makes concurrency reasoning straightforward.

Transaction Service: Handles vehicle_arrived and vehicle_left. Writes to the Transaction table only. It never modifies reservations or bitmaps. This boundary is enforced at the code level, the Transaction Service has a database connection with write access only to the Transaction table, not the Reservation or Spot tables.

Redis Cache: Stores lot capacity snapshots for fast check_capacity reads. This cache is advisory only, it tells users "roughly how many spots are available" but never authorizes a booking. The database always has the final say.

PostgreSQL: Source of truth for all reservation and transaction data. Sharded by lot_id for data locality. Each shard has a primary and at least one read replica for fault tolerance. The bitmap columns and reservation records for a lot always reside on the same shard, enabling single-shard transactions. Indexes on (lot_id, status, start_time) accelerate the common queries: finding active reservations for a lot, expired tentative holds, and no-show candidates.

Payment Provider: Third-party service (Stripe/PayPal) that handles payment processing. The Reservation Service verifies payment tokens with the provider during complete_reservation. The system stores only the transaction reference, not credit card details, PCI compliance is delegated entirely to the payment provider.

Background Sweepers: Two scheduled jobs. The hold expiration sweeper runs every minute, finding TENTATIVE reservations past their expires_at and releasing their bitmap bits. The no-show monitor runs every 15 minutes, finding CONFIRMED reservations with no check-in after 8 hours. Both clear bitmap bits and update reservation status inside transactions.

Why This Component Split

The key separation: cache answers "roughly how many spots are available?" (fast, possibly stale). The database answers "is this specific spot actually available right now?" (authoritative, transactional). The cache never authorizes a booking. The Reservation Service and Transaction Service are separate because they serve different actors with different latency requirements, a gate must open in under 500ms for a waiting driver, while a reservation can tolerate 2-3 seconds for payment verification.

Think about why this separation matters. A user calls check_capacity and sees "15 spots available." They call reserve_spot, and between those two calls, 14 other users reserved. The bitmap check inside the transaction sees only 1 spot left and assigns it. The stale cache number (15) was wrong, but it did not matter, the transactional check caught the reality. If the cache had authorized the booking directly, 15 users would have all been told "your spot is confirmed" for the same physical parking space.

Two flows define this system. The reservation flow (user books and pays) and the gate flow (vehicle physically arrives and leaves). They interact through the Reservation table but serve different actors with different timing. Understanding both flows is critical because they reveal where consistency matters (reservation flow) versus where eventual consistency is acceptable (gate flow, a delayed check-in record does not cause double-booking).

Reservation Flow

1. User calls check_capacity(lot_id, vehicle_type, start, end).
2. Reservation Service reads from Redis cache (or DB on cache miss). Returns available spot count and pricing.
3. User calls reserve_spot(user_id, lot_id, vehicle_type, start, end).
4. Reservation Service begins a transaction. Executes SELECT FOR UPDATE on candidate spot rows in the requested lot.
5. For each locked spot, performs bitwise AND between the request bitmap and the spot's existing bitmap. If the result is zero, the spot is free.
6. For the first free spot: INSERT reservation with status=TENTATIVE, update the bitmap with OR (existing OR request), COMMIT.
7. Returns reservation_id and payment redirect URL to the user.
8. User pays via the third-party provider, then calls complete_reservation(user_id, reservation_id, payment_token).
9. Reservation Service verifies the token with the payment provider. On success: UPDATE reservation SET status=CONFIRMED, payment_status=PAID.

Notice that steps 4-6 are the critical section, they happen inside a single database transaction with row-level locks. Steps 7-9 happen outside the transaction, so the lock is released quickly. This separation is why the bitmap check is fast even under contention: the lock is held only for the microseconds needed to check bitmap, insert, and commit. The payment (which takes seconds) happens after the lock is released.

Gate Flow

1. Vehicle arrives at the gate. Gate scans the reservation QR code or license plate.
2. Gate calls vehicle_arrived(reservation_id, timestamp).
3. Transaction Service creates a transaction record with the check_in_time.
4. Vehicle departs. Gate calls vehicle_left(reservation_id, timestamp).
5. Transaction Service updates the check_out_time. If the departure is past the reservation end_time, the overstay is flagged for additional charges. The Reservation Service is notified to process the extra payment against the user's payment method on file.

The gate flow is deliberately simple, the complexity lives in the reservation flow where money and spot allocation happen. The gate is just recording physical events. This means gate hardware can be cheap, stateless devices running minimal firmware. If the Transaction Service is temporarily unreachable, the gate can cache events locally and sync later. A delayed check-in record does not cause a double-booking because the bitmap was already set during reservation.

No-Show Flow

The No-Show Monitor runs every 15 minutes. It scans for confirmed reservations where start_time + 8 hours has passed and no matching transaction with a check_in_time exists. For each no-show: cancel the reservation, clear the bitmap bits, and charge the user for 24 hours per policy.

Why 8 hours? It is a business decision that balances two concerns. Too short (1 hour) and you cancel reservations for users stuck in traffic or delayed by meetings, they arrive to find their paid spot given away. Too long (24 hours) and genuinely abandoned spots sit empty all day, losing revenue and frustrating other drivers. 8 hours accommodates most real-world delays while still freeing spots within the same day.

"What happens when two users try to reserve the last available spot for the same time window?" This is the core interview question. User A and User B both call check_capacity and both see spot #42 is free from 2-4 PM. Both call reserve_spot. Without protection, both succeed, and the driver who arrives second finds their spot taken.

GATE: Bitmap Overlap Detection with Atomic Claiming

Each spot's daily schedule is a 96-bit bitmap (24 hours / 15 minutes = 96 slots). When reserve_spot is called:

1. Convert start_time and end_time to slot indices. For example, 2:00 PM = slot 56, 4:00 PM = slot 64.
2. Create a request bitmap with 1s for slots 56-63 (the 2-4 PM window).
3. BEGIN TRANSACTION.
4. SELECT bitmap FROM spots WHERE spot_id = ? FOR UPDATE, this locks the row.
5. Compute existing_bitmap AND request_bitmap. If the result is non-zero, the spot is occupied for that window. Try the next spot.
6. If the result is zero, the spot is free. UPDATE spots SET bitmap = existing_bitmap OR request_bitmap. INSERT the reservation. COMMIT.

The FOR UPDATE lock ensures only one transaction can check-and-reserve a spot at a time. The second user's transaction blocks until the first commits, then sees the updated bitmap and gets a conflict. This is the heart of the concurrency solution, the database itself enforces mutual exclusion, so the application code does not need distributed locks, semaphores, or any custom synchronization logic.

The elegance of the bitmap approach is that both the availability check (AND) and the reservation recording (OR) are single CPU operations. The entire critical section (lock row, AND, check zero, OR, insert, commit) involves no loops, no external calls, and no branching beyond the zero check. This is why the lock hold time is measured in microseconds, not milliseconds. The shorter the critical section, the lower the contention under concurrent access.

Why Bitmap Over Interval Query

A naive approach queries SELECT * FROM reservations WHERE spot_id = ? AND start_time < ? AND end_time > ? for each candidate spot. With 200 spots and dozens of reservations per spot, this is O(spots x reservations) per request. The bitmap approach is O(spots), one bitwise AND per spot, regardless of how many existing reservations exist. At 200 spots per lot, the entire scan takes microseconds.

Think about it concretely. Spot #42 has 30 existing reservations today. The naive approach must compare each of those 30 time ranges against the requested window. The bitmap approach has already encoded all 30 reservations into a single 96-bit integer, the AND check is one CPU instruction. Multiply that difference by 200 spots, and the bitmap approach is orders of magnitude faster under real-world load.

Bitmap Memory

As calculated in the capacity estimation, the total bitmap footprint is 800 MB (1000 lots x 200 spots x 4 KB per spot per year). A single Redis instance with 4 GB of memory holds all bitmaps with room to spare. If this number were 80 GB, you would need a Redis cluster or an entirely different availability representation. The small footprint is a direct consequence of bounded granularity: 96 bits per day is tiny because parking operates on hour-scale durations, not second-scale.

Hold Expiration

Tentative reservations (unpaid) have an expires_at timestamp. A background sweeper runs every minute, finds expired tentatives, clears their bitmap bits, and sets status=CANCELLED. This prevents phantom holds from blocking real bookings.

The sweeper uses the same transactional approach: BEGIN, SELECT FOR UPDATE on the spot row, clear the bitmap bits, UPDATE reservation SET status=CANCELLED, COMMIT. This ensures bitmap and reservation status stay synchronized even during cleanup. Without the transaction, a crash between clearing the bitmap and updating the status would leave the reservation marked as TENTATIVE with a cleared bitmap, a confusing state.

A subtle edge case: the sweeper must check payment status before cancelling. If the user initiated payment at minute 14 but the payment provider is slow to confirm, the hold might expire at minute 15 while payment is in flight. The sweeper skips reservations where a payment verification is pending (status=TENTATIVE AND payment_initiated_at IS NOT NULL). The reconciliation job handles these, it checks with the payment provider and either confirms or cancels based on the actual payment outcome.

Hot-Lot Contention

During events (concerts, Olympics), hundreds of users hit one lot simultaneously. All SELECT FOR UPDATE calls serialize on the same spot rows. Mitigation: scan spots in random order (not always starting from spot #1) so different users lock different spots first. If all spots for the requested window are taken, return 409 Conflict immediately with estimated next availability.

Why does random scanning help? If 100 users all start scanning at spot #1, they all try to lock the same row. User 1 gets the lock, the other 99 wait. User 1 finishes, user 2 gets the lock, the other 98 wait. This is O(n) serialization. With random scanning, user 1 might start at spot #47, user 2 at spot #183, user 3 at spot #12. They lock different rows in parallel and proceed simultaneously. The contention drops from O(n) to O(n/spots), which for 200 spots means 200x less serialization.

Three cascading decisions shape this system: what database to use, how to represent availability, and how to handle payments. Each choice constrains the next.

RDB vs NoSQL

Data fits in roughly 280 GB over 2 years, well within PostgreSQL's comfort zone. RDB gives ACID transactions, which are essential for the SELECT FOR UPDATE pattern that prevents double-booking. NoSQL (DynamoDB, Cassandra) scales better horizontally but requires application-level consistency (conditional writes, lightweight transactions). Since the data is small and consistency is the number one requirement, RDB wins decisively.

The capacity estimation settled this decision. At 280 GB and 2.3 QPS, PostgreSQL handles the load with room to spare. Proposing DynamoDB here means choosing a harder architecture (application-level consistency, conditional writes) for no benefit. Always let the numbers drive the database choice.

Bitmap vs Interval Tree

Bitmap: O(1) per-spot overlap check, fixed 15-minute granularity, roughly 4 KB per spot per year. The 96-bit integer fits in a single CPU register for the AND operation. The trade-off is that reservations snap to 15-minute boundaries, wasting up to 14 minutes at each end.

Interval tree: O(log n) lookup where n is the number of reservations, flexible time precision, more memory-efficient per reservation but slower under high contention. The tree must be balanced and maintained as reservations are added and removed.

Bitmap wins for parking lots because the number of slots per day is bounded (96) and the constant-time check matters when scanning 200 spots under contention. If the system needed second-level precision (conference room scheduling with 5-minute slots), an interval tree might be more appropriate because the bitmap would need 17,280 bits per day, still small, but the waste from rounding becomes more significant with shorter bookings.

Replication Factor for PostgreSQL

A primary with one synchronous read-replica ensures no data loss on primary failure. The replica also handles read-heavy check_capacity queries (which are safe to serve from a slightly stale replica since the cache is advisory). Adding a second async replica in another availability zone provides disaster recovery without adding latency to writes. For this system's low QPS (roughly 2.3 average), a single primary handles all writes easily, the replica exists for durability, not throughput.

Synchronous Payment Verify vs Async Webhook

Synchronous: complete_reservation calls the payment provider's verify API inline. Simpler implementation but adds roughly 500ms of latency to the response.

Async webhook: The payment provider calls our webhook on completion. Lower latency for the user but requires webhook infrastructure, idempotency handling, and reconciliation for missed callbacks. The webhook must be idempotent, the same callback might arrive twice if the provider retries. Without deduplication (using the transaction reference as an idempotency key), a single payment could confirm the reservation twice or trigger double billing.

The system uses synchronous verification for simplicity, with a reconciliation job as a safety net for payment provider timeouts. The reconciliation job runs every 5 minutes, queries for reservations in TENTATIVE state with payment_initiated_at older than 2 minutes, and calls the provider's check-payment-status API. This catches the roughly 0.1% of payments where the synchronous verify timed out but payment actually succeeded. In an interview, explicitly stating this trade-off shows you understand that simpler is often better when the performance characteristics are acceptable.

Cache Invalidation Strategy

When a reservation is created or cancelled, the Reservation Service updates the Redis cache for that lot's capacity. This is a write-through cache, on write, update both DB and cache. If the cache update fails, it is acceptable because the cache is advisory only. The next check_capacity call on a cache miss will refresh from the database. This fire-and-forget cache update is safe precisely because no booking decision depends on cache data.

Every failure maps to a business impact. Double-booking destroys user trust. Lost reservations mean empty spots with angry customers. Phantom charges trigger chargebacks. The system is designed so that failures cause delays (higher latency, temporary unavailability) but never corruption (double-booking, lost data). This is a deliberate architectural choice: the system prioritizes correctness over availability. A user who cannot book for 30 seconds during a failover is annoyed. A user who arrives at a double-booked spot after driving 30 minutes is furious.

Database Failure

Primary goes down. A read replica is promoted to primary. In-flight transactions roll back, users retry and succeed on the new primary. No double-booking occurs because uncommitted reservations are lost (this is safe, the user simply retries). The bitmap and reservation table stay consistent because they are always updated in the same transaction.

This is the power of ACID transactions for failure handling. Because the bitmap update and reservation INSERT are in the same transaction, there is no partial state to clean up after a crash. Either both persisted (committed) or neither did (rolled back). Compare this to a NoSQL approach where you would need to manually detect and repair inconsistencies between separate bitmap and reservation writes.

The failover timing matters. A typical PostgreSQL streaming replica can be promoted in 10-30 seconds. During this window, all write operations (reserve_spot, complete_reservation) fail. Read operations (check_capacity) can still be served by the remaining replicas. The system needs connection retry logic with exponential backoff, clients retry failed writes after 1s, 2s, 4s until the new primary accepts connections. The no-show monitor and hold expiration sweeper also pause during failover and resume on the new primary.

Cache Failure

Redis goes down. check_capacity falls back to direct DB queries. Slower (10ms vs 1ms) but correct. reserve_spot is unaffected, it always reads from DB anyway. No data loss, no inconsistency. This is why the cache is advisory only, by design, every operation that depends on cache data has a database fallback that produces the same correct result, just slower. The Reservation Service detects Redis unavailability via connection timeout (50ms) and automatically routes to the database. When Redis recovers, the service reconnects and resumes caching. No manual intervention is needed.

Payment Provider Timeout

The user paid but complete_reservation times out on the verify call. The reservation stays TENTATIVE. A reconciliation job polls the payment provider every 5 minutes, finds confirmed payments, and finalizes reservations. The user sees a "payment processing" status temporarily but does not lose their spot because the tentative hold is still active. The hold expiration timer is paused for reservations with pending payment verification, preventing the sweeper from cancelling a reservation the user actually paid for.

Hot-Lot Surge

500 concurrent reserve_spot calls for a 100-spot lot near a concert venue. SELECT FOR UPDATE serializes access, but the bitmap check is fast, most users get 409 Conflict quickly. Mitigations: return estimated wait times, suggest nearby lots with availability, and implement a virtual queue for high-demand time windows. Random spot scanning distributes lock contention. The key insight is that even under extreme contention, the system fails gracefully, users get fast 409 responses, not timeouts or double-bookings.

Why does the system handle 500 concurrent requests gracefully? Because the critical section (lock, check bitmap, update, commit) takes microseconds per spot. Even if all 500 requests serialize on the same spot, the total wall time is 500 x 50 microseconds = 25 milliseconds. Most requests will find the spot already taken after waiting for the lock, get a conflict, and move to the next spot. The entire lot scan for a single request takes about 200 x 50 microseconds = 10 milliseconds. Combined with random scanning, 500 concurrent users can all complete within a few hundred milliseconds.

Gate Offline

Vehicle arrives but the gate cannot reach the API. The gate stores events locally and syncs when connectivity restores. Transaction records may be delayed but the reservation is already confirmed, the vehicle can enter using an offline-cached reservation list at the gate. The gate periodically downloads a snapshot of confirmed reservations for its lot, a small dataset (at most a few hundred active reservations per lot). This snapshot is refreshed every 5 minutes when the network is available. During an outage, the gate validates against the most recent snapshot. A reservation confirmed after the last snapshot sync would be missed, the gate falls back to letting the vehicle in and logging the event for later reconciliation. This is the correct trade-off: rejecting a paying customer is worse than admitting one unvalidated vehicle.

Bitmap-Reservation Inconsistency

If a bug or crash leaves the bitmap out of sync with the Reservation table (bitmap says occupied, no matching reservation), the reconciliation process rebuilds the bitmap from active reservations. This is safe because the Reservation table is the source of truth, the bitmap is a derived index. The rebuild runs inside a transaction with SELECT FOR UPDATE on the affected spot rows to prevent concurrent reservations during reconstruction.

A compact car just reserved the last standard spot in a busy downtown lot, leaving an SUV driver with no options. Meanwhile, a concert venue lot charges the same rate at 7 PM on a Saturday as it does at 3 AM on a Tuesday. The current system treats every vehicle and every hour identically. Four improvements address this.

Vehicle Type and Spot Matching

Support compact, standard, large, and EV spots. A compact car can park in a large spot but not vice versa. EV spots include charging station integration with per-kWh billing. This requires extending the Spot table with spot_type and adding type-aware filtering to the bitmap scan, check only spots that match or exceed the vehicle's size requirements. The type hierarchy (compact fits in standard fits in large) means the scanner tries the smallest matching type first to leave larger spots available for larger vehicles.

The scanner's ordering matters. If a compact car grabs a large spot because it was scanned first, a subsequent SUV has fewer options. The type-aware scan iterates compact spots first for compact vehicles, then falls back to standard and large only when compact spots are full. This greedy-smallest-first strategy maximizes overall lot utilization by preserving flexibility for larger vehicles that have fewer eligible spots.

Dynamic Pricing

Adjust rates based on lot occupancy, time of day, and local events. High-demand windows (concert night, weekday mornings near offices) charge more. A pricing service reads real-time occupancy from the cache and event calendars from a third-party API to compute dynamic rates. The main challenge is price consistency: the price shown during check_capacity might change by the time the user calls reserve_spot. A quote expiration mechanism (valid for 5 minutes) solves this by locking in the price at check_capacity time.

The pricing model for most lots is simple: a base hourly rate with time-of-day multipliers (1.5x during morning rush, 2x during events). The pricing service stores these multipliers per lot and computes the total price for a given time window. For event-based surges, lot operators can manually set a price override for specific date ranges. The override takes precedence over the computed rate, giving operators direct control during known high-demand periods.

Geographic Optimization

A global load balancer routes users to the nearest data center. Database replicas in multiple regions handle read-heavy check_capacity calls. Write operations (reserve_spot) still route to the primary shard for consistency. Cross-region replication provides disaster recovery. The sharding-by-lot_id strategy works well here: lots in Europe are on European shards, lots in Asia on Asian shards. A user booking a lot near them gets low-latency writes because the shard is geographically nearby.

The geographic strategy also simplifies compliance. Parking data in Europe stays on European servers (GDPR compliance). Pricing in local currency is handled per-region. Each regional deployment is essentially an independent instance with the same architecture, which means scaling to a new country requires deploying infrastructure, not redesigning the system.

Reservation Marketplace

Allow users to transfer or sell reservations for high-demand events. This requires an escrow mechanism and a transfer API that atomically reassigns the reservation to a new user, updating the reservation's user_id and creating a settlement record between buyer and seller. The key constraint is that the transfer must be atomic, a cancel-then-rebook approach opens a window where another user could grab the spot, defeating the purpose of the marketplace.

The marketplace introduces a pricing challenge. The original reservation has a fixed price, but the market price for a concert Saturday spot may be 3x higher. The transfer API needs a separate pricing layer: the seller sets an asking price, the buyer pays that price to the platform, and the platform settles with the seller minus a service fee. The original reservation price is between the seller and the platform, the buyer never sees it.