Selection at Application Level — Reservations and Assignments

Selection at Application Level — Reservations and Assignments #

Application-level Selection is the same mechanism as infrastructure-level Selection (Chapter 3) — multiple actors compete for a finite resource and exactly one must win — but operating at a different scale with different failure semantics.

Infrastructure Selection (Raft leader election):

• Participants: tens of nodes
• Error recovery: unrecoverable — two leaders corrupt the log permanently
• Implementation: Raft consensus, strong consistency required, cluster-wide coordination

Application Selection (seat reservation):

• Participants: millions of concurrent users
• Error recovery: recoverable — a failed reservation expires via TTL, the seat is re-released
• Implementation: optimistic locking or database row locks, with a TTL-bounded hold period

The same mechanism, different implementations, different failure costs.

The Two Phases of Application Selection #

Most application-level Selection problems decompose into two distinct phases:

Intent phase (fast path): the user claims a resource. This is optimistic — we assume the claim will succeed. The resource is marked as “held” but not yet committed. If the user fails to complete the second phase (payment, confirmation), the hold expires via TTL and the resource is released.

Commitment phase (slow path): the user completes the transaction. The resource is marked as permanently assigned. This phase typically involves durable state changes (payment charge, database write) that cannot be TTL-expired.

The intent phase must be fast (low latency, high throughput) because millions of concurrent users experience it. The commitment phase can be slower because fewer users reach it and the operation is worth the latency.

This two-phase structure is the dominant pattern for application-level Selection.

Seat Reservation: Ticketmaster #

Ticketmaster’s core coordination problem: when Taylor Swift’s Eras Tour goes on sale, 2 million users simultaneously try to purchase one of 60,000 seats. Each seat can be sold exactly once. The system must:

1. Show users which seats are available.
2. Let a user select a seat and hold it during checkout.
3. Prevent two users from purchasing the same seat.
4. Release held seats if the user abandons checkout.

The Naïve Approach: Database Locks #

BEGIN;
SELECT * FROM seats WHERE seat_id = '101' AND status = 'available' FOR UPDATE;
-- If found, mark as reserved
UPDATE seats SET status = 'held', user_id = ?, hold_expiry = NOW() + INTERVAL 10 MINUTES
WHERE seat_id = '101' AND status = 'available';
COMMIT;

SELECT FOR UPDATE acquires a pessimistic row lock. Only one transaction can hold the lock at a time. This is correct — exactly one user can successfully update the seat from ‘available’ to ‘held’.

The problem with pessimistic locking at scale: at 2 million concurrent users each trying to lock rows, the database becomes the bottleneck. Each SELECT FOR UPDATE creates a lock entry, and contention on popular seats (front row, aisle seats) causes lock queues. Database connection pools are exhausted. The p99 latency degrades from milliseconds to seconds.

Pessimistic locking is correct but does not scale to millions of concurrent users.

Optimistic Locking #

Optimistic locking avoids locks by using a version counter and a compare-and-swap write:

-- Read the seat (no lock)
SELECT seat_id, status, version FROM seats WHERE seat_id = '101';
-- Returns: (101, 'available', 42)

-- Write only if version has not changed
UPDATE seats SET status = 'held', user_id = ?, hold_expiry = NOW() + 10 min, version = 43
WHERE seat_id = '101' AND status = 'available' AND version = 42;
-- If 0 rows updated: another user got here first, retry

If two users simultaneously read version 42 and attempt the update, exactly one will see 1 row updated; the other will see 0 rows updated and must retry with a different seat.

Properties: optimistic locking works well when contention is low — most updates succeed on the first try. When contention is high (many users trying the same seat), retry rates increase. For popular seats, optimistic locking degrades to a retry storm.

The hybrid approach: use optimistic locking for the initial selection, but reserve an in-memory claim layer in front of the database for the highest-contention events.

The In-Memory Intent Layer #

For large-scale events, Ticketmaster uses a two-tier approach:

Tier 1: Redis-backed intent layer (fast path)

# Atomic claim using Redis SET with NX (not exists) and EX (expiry)
claimed = redis.set(f"seat:{seat_id}:hold", user_id, nx=True, ex=600)
if not claimed:
    return "SEAT_TAKEN"
# Store hold details
redis.hset(f"seat:{seat_id}:hold:meta", mapping={
    "user_id": user_id,
    "claimed_at": time.time(),
    "order_id": order_id
})

SET NX is atomic — only one process can set the key when it does not exist. If two users race, exactly one wins. The key has a 10-minute expiry; if the user abandons checkout, the seat is released automatically.

Tier 2: Database commitment (slow path)

When the user completes payment:

BEGIN;
-- Verify the Redis hold is still valid (user_id match)
-- Verify seat is still available in DB (belt-and-suspenders)
INSERT INTO seat_purchases (seat_id, user_id, order_id, purchase_time)
SELECT '101', ?, ?, NOW()
WHERE NOT EXISTS (SELECT 1 FROM seat_purchases WHERE seat_id = '101');
-- Commit atomically
COMMIT;

The database write is the final arbiter. Even if the Redis hold was granted, the database write checks for an existing purchase. This handles the edge case where Redis fails after granting a hold but before the TTL-based cleanup triggers.

Why Redis locks are acceptable here (contrast with Chapter 3): seat reservation is an efficiency lock, not a correctness lock. If Redis fails and two users both complete checkout, the database write provides the final safety net. The cost of a duplicate hold is a user reaching checkout only to find the seat taken — recoverable, not catastrophic. The cost of a duplicate leader election in a distributed system is permanent data corruption — unrecoverable.

Queue-Based Fairness #

For events with extreme demand (Beyoncé, Taylor Swift), the challenge is not just correctness but fairness: how do you ensure that users who joined the queue first get access first?

Virtual waiting room: before the sale opens, users join a virtual queue. The system assigns each user a position and issues a time-limited token when it is their turn. The token grants access to the seat selection page. Users without a valid token cannot attempt to claim seats.

User joins queue → position assigned (e.g., #45,231)
On-sale time → system processes 1,000 users/second
User #45,231's turn → issued JWT token {user_id, seat_tier_access, expires: +15min}
User presents token → allowed to select seats for 15 minutes

This transforms a thundering herd problem into a controlled, metered flow. The seat selection system receives traffic at a predictable, manageable rate rather than absorbing the full spike of 2 million simultaneous users.

Driver Assignment: Uber #

Uber’s driver assignment is a different flavor of Selection: for each ride request, exactly one driver must be assigned, and the assignment must account for proximity, availability, and driver preferences.

The Assignment Problem #

When a rider requests a ride:

1. Uber determines the set of eligible drivers (within radius, available, matching ride type).
2. Uber must assign exactly one driver to the ride.
3. The driver must accept within a timeout; if not, the next driver in the candidate set is offered.
4. The assignment must be consistent — the same driver cannot be offered two rides simultaneously.

This is Selection, but with an additional dimension: the “best” driver, not just any available driver.

Geospatial Indexing and Candidate Selection #

Uber uses a geospatial index (a custom system called H3, based on hexagonal grid cells) to find nearby drivers.

# Find drivers within search radius
hex_cells = h3.k_ring(h3.geo_to_h3(rider_lat, rider_lng, resolution=9), k=2)
candidate_drivers = redis.sunion(*[f"drivers:{cell}" for cell in hex_cells])

Each driver’s location is stored in a Redis set keyed by H3 hex cell. Nearby drivers are found by taking the union of driver sets across the target hex cell and its immediate neighbors. This is O(1) per query regardless of total driver count.

Exclusive Assignment via Atomic Claim #

Once candidates are ranked (by ETA, rating, etc.), the system offers the ride to the top candidate:

# Atomic claim using Redis SET NX with TTL
# The driver must respond within 15 seconds
claimed = redis.set(f"driver:{driver_id}:active_offer", ride_id, nx=True, ex=15)
if not claimed:
    # Driver already has an active offer; skip to next candidate
    continue

# Offer sent to driver's app
send_offer_to_driver(driver_id, ride_id)

The SET NX ensures a driver can only have one active offer at a time. If the driver does not respond within 15 seconds, the key expires, the driver’s availability is restored, and the next candidate is offered.

When the driver accepts:

# Verify the offer is still valid (may have expired if driver was slow)
current_offer = redis.get(f"driver:{driver_id}:active_offer")
if current_offer != ride_id:
    return "OFFER_EXPIRED"

# Commit the assignment (database write)
db.execute("""
    INSERT INTO ride_assignments (ride_id, driver_id, assigned_at)
    VALUES (?, ?, NOW())
    ON CONFLICT (ride_id) DO NOTHING
""", ride_id, driver_id)

The ON CONFLICT DO NOTHING is the database-level fencing: even if two acceptance messages arrive (network retry), only one succeeds.

The Dispatch Loop #

Uber’s dispatch loop is:

For each unmatched ride:
  1. Find candidate drivers (geospatial query)
  2. Rank candidates (ETA + rating + surge preference)
  3. For top-ranked candidate:
     a. Atomic claim (Redis SET NX)
     b. If claimed: send offer, start 15s timeout
     c. If not claimed: move to next candidate
  4. On driver accept: commit to DB, clear Redis offer key
  5. On driver decline or timeout: release Redis offer key, retry with next candidate

This loop runs continuously for every unmatched ride. The Redis layer handles the fast, high-frequency claim checks. The database handles the durable, authoritative commitment.

Optimistic vs Pessimistic Locking: When to Use Each #

Rule: optimistic locking for programmatic, automated flows where retry is cheap. Pessimistic locking (or TTL-bounded holds) for user-facing flows where the user is expected to act within a bounded time window.

Two-Phase Reservation Pattern #

The two-phase reservation is the generalization of the Ticketmaster pattern to any resource that must be held during a multi-step process:

Phase 1: Reserve (intent)

POST /reservations
{
  "resource_id": "seat_101",
  "user_id": "user_xyz",
  "ttl_seconds": 600
}
→ 201 Created: { "reservation_id": "res_abc", "expires_at": "..." }

Phase 2: Commit (finalize)

POST /reservations/res_abc/commit
{
  "payment_method": "pm_xxx"
}
→ 200 OK: { "order_id": "ord_yyy", "status": "confirmed" }

TTL expiration (cleanup)

(background job or Redis keyspace notification)
On reservation TTL expiry: release resource_id back to available pool

The reservation ID is the idempotency key for the commit operation — retrying the commit with the same reservation ID is safe because the database write includes a unique constraint on reservation_id.

The reservation ID as fencing token: a reservation ID issued at time T is invalidated when the TTL expires. If a user’s checkout session takes longer than the TTL, they will find their reservation has expired. The commit operation checks the reservation expiry and rejects expired reservations — the same logic as a fencing token rejecting stale lock holders.

Failure Modes at Application Level #

Double-booking despite optimistic lock: can occur if:

• The database constraint (unique index on seat_id in seat_purchases) is not present.
• Two transactions read “no purchase exists” concurrently and both insert.
• Mitigation: always have a unique constraint as the final backstop, independent of application-layer locking.

TTL too short: the user is in the middle of checkout when their hold expires. Another user claims the seat. The first user completes payment, but the database write fails (seat already taken). Mitigation: display a clear countdown timer; allow TTL extension via heartbeat if the user is actively engaged.

TTL too long: a user claims a seat and abandons checkout without closing the tab. The seat is unavailable to other users for the full TTL. Mitigation: TTL should be the minimum necessary (10 minutes is standard for ticketing). Use heartbeat-based hold extension rather than a single long TTL.

Redis failure during claim: the Redis SET NX succeeds but the application crashes before recording the claim. The Redis key exists but no application state tracks it. Mitigation: Redis key expiry handles this automatically — the hold expires and the seat is released.

Split-brain between Redis and database: the Redis hold says user A holds the seat; the database says no purchase exists. Mitigation: the commitment phase always performs an authoritative database check (INSERT ... WHERE NOT EXISTS). The Redis layer is advisory, not authoritative.