Local Delivery Service: System Design #

A complete derivation of a local grocery/item delivery system (Instacart / DoorDash Grocery pattern) using the 20-step derivation framework — from functional requirements to operable architecture, with every mechanism derived mechanically from invariants.

Ordering Principle #

Every layer constrains the next. Skipping a layer makes later choices arbitrary.

Functional requirements
  → normalize into operations over state          (Step 1)
  → extract primary objects                       (Step 2)
  → assign ownership, ordering, evolution         (Step 3)
  → extract invariants                            (Step 4)
  → derive minimal DPs from invariants            (Step 5)
  → select concrete mechanisms                    (Step 6)  ← the mechanical bridge
  → validate independence and source-of-truth     (Step 7)
  → specify exact algorithms                      (Step 8)
  → define logical data model                     (Step 9)
  → map to technology landscape                   (Step 10)
  → define deployment topology                    (Step 11)
  → classify consistency per path                 (Step 12)
  → identify scaling dimensions and hotspots      (Step 13)
  → enumerate failure modes                       (Step 14)
  → define SLOs                                   (Step 15)
  → define operational parameters                 (Step 16)
  → write runbooks                                (Step 17)
  → define observability                          (Step 18)
  → estimate costs                                (Step 19)
  → plan evolution                                (Step 20)

Step 1 — Problem Normalization #

Functional Requirements (Raw) #

1. Customer browses items available at nearby stores within their delivery zone.
2. Customer places an order for multiple items, possibly from one store.
3. System assigns a shopper/courier to fulfill the order.
4. Customer tracks shopper location in real-time during fulfillment.
5. Shopper reports item unavailability and can propose substitutes; customer approves or rejects.
6. Order status updates in real-time: accepted → shopping → picked → in-transit → delivered.
7. Customer is charged only after delivery is confirmed (authorization at placement, capture at delivery).
8. Items are reserved at order placement — no oversell is permitted.

Normalized Table #

Key Seams Exposed by Normalization #

• FR1 vs FR8: There is a race between “show available stock” (read projection) and “reserve stock” (conditional write). These are separate operations with a window between them. CAS on stock quantity is required.
• FR2 vs FR3: Order creation and shopper assignment are not atomic — shopper assignment is a downstream step triggered after order is persisted.
• FR5: Substitution is not an update to an OrderItem. It creates a new SubstitutionRequest object with its own approval lifecycle.
• FR7: Payment is a two-step process (auth then capture) separated by the entire fulfillment duration — potentially hours. Payment authorization expiry is a real failure mode.

Step 2 — Object Extraction #

Candidates and Classification #

Primary Objects #

Derived / Rejected Objects #

Four Purity Tests Applied #

InventoryReservation #

1. Ownership: System creates on order placement; system transitions on fulfillment or cancellation. Single writer pipeline. PASS.
2. Evolution: State machine (pending → confirmed → released | fulfilled). Does not append, does not merge. PASS.
3. Ordering: Reservations ordered by creation time within one item (to determine which get confirmed if stock runs out). PASS.
4. Non-derivability: Cannot reconstruct which orders hold locks on which quantities without this object. PASS.

LocationPing #

1. Ownership: Shopper device is the sole writer. PASS.
2. Evolution: Append-only, immutable once written. PASS.
3. Ordering: Ordered by timestamp within one shopper_id. PASS.
4. Non-derivability: Raw GPS history cannot be derived from elsewhere. PASS.

SubstitutionRequest #

1. Ownership: Shopper creates; customer transitions (approve/reject); system can expire. Multi-actor but pipeline-ordered (shopper writes first, customer responds). PASS.
2. Evolution: State machine (pending_approval → approved | rejected | expired). PASS.
3. Ordering: At most one active SubstitutionRequest per OrderItem at a time (uniqueness invariant). PASS.
4. Non-derivability: Customer intent (approve/reject) cannot be derived from other state. PASS.

Step 3 — Axis Assignment #

Per-Object Axis Table #

Critical Axis Combinations #

Shopper (multi-writer one-winner + state machine): Multiple assignment service instances may simultaneously attempt to claim the same shopper for different orders. Only one claim can succeed. This combination resolves to a Lease (SETNX in Redis on shopper_id), as derived in Step 6.

InventoryReservation (system-only + state machine, but race at creation): The creation step is a conditional write — “create reservation only if available_quantity > 0.” Multiple concurrent orders may race for the same item. This is effectively multi-writer one-winner at creation, resolving to CAS on a quantity counter.

Order (multi-stage pipeline + state machine): No two services should advance the same order state simultaneously. Transitions must be guarded by CAS on (current_state, version).

Step 4 — Invariant Extraction #

Invariant Table #

Step 5 — Design Point (DP) Derivation #

Each DP is the minimal mechanism that enforces its invariant cluster, derived bottom-up from invariant types.

Step 6 — Mechanism Selection #

The mechanical bridge maps invariant clusters and axis assignments to concrete implementation mechanisms.

6.1 Invariant Type → Mechanism Family #

6.2 Ownership × Evolution → Concurrency Mechanism #

6.3 Full Mechanical Derivation for Four Key Flows #

Derivation 1: Inventory Reservation (Multi-Item Atomicity) #

Problem statement: When a customer places an order with N items, all N items must be reserved or none. If item 3 is out of stock after items 1 and 2 are reserved, the partial reservation must be rolled back.

Q1 (Scope): Is this within one service or cross-service?

• The inventory check and reservation creation happen within the Order service’s write path, but reservation records may span multiple store-partitions. This is cross-object but within-service for the reservation logic. However, compensation (unreserve) crosses logical boundaries. → Cross-service decomposable (compensation is well-defined: “release reservation”).

Q2 (Failure): What happens if the writer crashes mid-reservation (e.g., after reserving items 1-2 but before attempting item 3)?

• The reservation records for items 1-2 exist in a confirmed-pending state. No compensating transaction has been applied. → Saga with compensation is required. Each step must be independently compensable. → Idempotency Key on each reservation step (keyed by order_id + item_id) ensures that retries after crash do not double-reserve.

Q3 (Data): Is the stock state commutative?

• No. “Reserve 5 units” and “Reserve 3 units” applied concurrently when only 5 are available must not both succeed. Not commutative under scarcity. → CAS on quantity counter (not CRDT).

Q4 (Access): Read pattern for stock availability?

• Read » Write (millions of customers browse, few place orders). → Cache-Aside for browse reads (AvailableItemView cached in Redis). The reservation write path hits Postgres directly (cache is advisory; Postgres is authoritative).

Q5 (Coupling): How does reservation propagate to the shopper view?

• Shopper needs to see which items are reserved (i.e., what to pick). → Outbox + Relay: Order service writes reservation to Postgres + Outbox atomically; relay publishes to Kafka; Shopper service consumes. Avoids dual-write.

Resulting mechanism combination:

Saga (per-item steps)
  + CAS on quantity counter (prevents oversell at each step)
  + Idempotency Key per step (keyed by order_id:item_id:reserve)
  + Compensation (release reservation) on Saga rollback
  + Outbox + Relay (propagate reservation to downstream consumers)

Required by 6.4: CAS + Idempotency Key — satisfied. (Saga does not require Lease; Lease applies to shopper assignment below.)

Derivation 2: Shopper Assignment #

Problem statement: When an order is accepted, the system must claim exactly one available shopper. Multiple assignment service instances may race to claim the same shopper for different orders.

Q1 (Scope): Within-service or cross-service?

• Assignment is within the Assignment service, but shopper state is shared across all instances. → Distributed CAS (not cross-region; no CRDT because not commutative).

Q2 (Failure): What if the assignment service instance crashes after claiming the shopper but before persisting the assignment to Order?

• Shopper remains locked (claimed) but Order has no shopper_id. The shopper lease must expire so another instance can re-claim. → Lease (SETNX with TTL). Lease TTL = assignment processing timeout (e.g., 30s). If Order is not updated within TTL, lease expires and shopper is returned to available pool.

Q3 (Data): Is shopper availability commutative?

• No. “Claim shopper X” by two different orders — only one should win. → Not CRDT. Lease is correct.

Q4 (Access): How is the nearest available shopper found?

• Geospatial query: find shoppers within N km of store, sorted by distance. → Spatial Partition + Scatter-Gather. Redis Geo index on shopper locations; GEORADIUS query to find candidates; claim attempt in order of proximity.

Q5 (Coupling): How does assignment propagate to Order?

• Assignment service must atomically: (a) acquire lease on shopper, (b) update Order.shopper_id, (c) update Shopper.status = on_order. Steps b and c must both succeed or both roll back. → Saga with compensation: if Order update fails, release shopper lease. If Shopper status update fails (shopper went offline), release lease and retry with next candidate.

Resulting mechanism combination:

Lease (Redis SETNX on "shopper:{shopper_id}:claim" with TTL=30s)
  + fencing token (lease token included in all subsequent writes; stale writes rejected)
  + Saga (multi-step assignment: lease → Order.shopper_id → Shopper.status)
  + Spatial query (Redis GEORADIUS) for candidate generation
  + CAS on Order.status (pending → accepted) to prevent duplicate assignment

Required by 6.4: Lease + fencing token — satisfied.

Derivation 3: Substitution Approval Workflow #

Problem statement: When a shopper finds an item unavailable, they propose a substitute. The customer must approve or reject within a time window. If the window expires, the item is dropped automatically. This is an intent/future-constraint object with a deadline.

Q1 (Scope): Within-service or cross-service?

• SubstitutionRequest is created by Shopper service; approved/rejected by Customer service; expired by Scheduler service. Cross-service. → Cross-service decomposable (approval and rejection are compensable in both directions).

Q2 (Failure): What if the deadline expires and the scheduler crashes before processing the expiry?

• The SubstitutionRequest remains in pending_approval state indefinitely. → Deadline enforced by a durable delayed job: scheduled via Redis sorted set (score = expiry_unix_timestamp) + a sweeper that runs every 10s and processes expired requests. The sweeper is idempotent (CAS on SubstitutionRequest.status from pending_approval → expired). If sweeper crashes mid-way, it retries; CAS prevents double-processing.

Q3 (Data): Can multiple SubstitutionRequests for the same (order_id, item_id) exist simultaneously?

• No. I18 prohibits this. → Unique constraint on (order_id, item_id) filtered to status = pending_approval. Database enforces; service layer validates.

Q4 (Access): Customer must see the substitution request in real-time (push notification + UI update).

• → Fan-out on Write: when SubstitutionRequest is created, publish to Kafka → push notification service → APNs/FCM. Also pub/sub channel per order_id for live UI update (WebSocket).

Q5 (Coupling): On approval, the OrderItem must be updated (replace item_id + update reservation). On rejection, the InventoryReservation for the original item must be released.

• → Outbox + Relay: SubstitutionRequest service writes to DB + Outbox atomically; relay publishes event to Kafka; downstream services (InventoryReservation service, OrderItem service) consume and apply their respective changes. Each downstream step is idempotent (keyed by substitution_request_id + action).

Resulting mechanism combination:

SubstitutionRequest state machine (pending_approval → approved | rejected | expired)
  + CAS on (status, version) for all transitions
  + Unique constraint on (order_id, item_id) for active requests
  + Durable deadline: Redis ZSET (key=substitution_request_id, score=expiry_ts)
  + Idempotent sweeper (CAS on status prevents double-expiry)
  + Outbox + Relay (propagate approval/rejection to InventoryReservation + OrderItem)
  + Fan-out on Write (push notification + WebSocket on creation)

Derivation 4: Payment Authorization and Capture #

Problem statement: Payment is authorized at order placement (hold on card) but captured only after delivery confirmation. The authorization and capture are separate PSP calls, potentially hours apart. Authorization can expire (typically 7 days for most card networks). Double-capture must be impossible.

Q1 (Scope): Cross-service (Payment service → PSP external call). → Cross-service non-decomposable at PSP level (PSP calls cannot be Saga-compensated within milliseconds; compensation = refund, which is a different operation). Within the system, Payment state transitions are a state machine.

Q2 (Failure):

• PSP call for authorization times out: retry with same idempotency key → PSP returns cached result or processes once. → Idempotency Key on all PSP calls (key = order_id:auth or order_id:capture).
• System crashes after PSP confirms authorization but before persisting Payment.status = authorized: on restart, query PSP with idempotency key to recover status, then persist. → Idempotency Key + recovery reconciliation job.
• Authorization expiry: if delivery takes > 7 days (edge case), auth expires. → Scheduler: daily job checks Payment records in authorized state older than 6 days and triggers re-authorization.

Q3 (Data): Is payment state commutative?

• No. Capture must happen exactly once. Not commutative. → CAS on Payment.status (authorized → captured). Two concurrent capture attempts → only one CAS succeeds.

Q4 (Access): Payment reads are infrequent (per-order); PSP calls are the bottleneck.

• No special caching needed. Payment record is small; read from Postgres.

Q5 (Coupling): Capture must be triggered by Order reaching delivered status. How is this propagated?

• → CDC (Change Data Capture): Order service updates Order.status = delivered in Postgres; Debezium publishes change event to Kafka; Payment service consumes and initiates capture. This ensures the trigger is the DB row change, not a dual-write.

Resulting mechanism combination:

Payment state machine (pending → authorized → captured | refunded | failed)
  + CAS on (status, version) for all transitions
  + Idempotency Key on all PSP calls (key = order_id:operation)
  + CDC (Debezium on Order table) → Kafka → Payment capture trigger
  + Auth expiry scheduler (daily reconciliation job)
  + Recovery reconciliation (on startup, query PSP for in-flight payments)

6.4 Required Combinations Check #

Step 7 — Axiomatic Validation (Source-of-Truth Table) #

Rule: Each piece of state has exactly one source of truth. No dual truth.

Dual-Truth Resolution Log #

1. Item.available_quantity: Resolution — cache is advisory only. All reservation write paths use SELECT FOR UPDATE on Postgres item row. Cache is populated by Postgres read after write; cache miss falls through to Postgres.

2. Shopper.status (Redis vs Postgres): Resolution — Postgres Shopper.status is updated only with the valid fencing token from the Redis lease. On lease expiry, a lease-expiry handler (not the expired holder) updates Postgres.status = available using a system-level write (no fencing token required because the lease has expired and no other writer holds it).

Step 8 — Algorithm Design #

Algorithm 1: Multi-Item Order Placement (Saga) #

function placeOrder(customer_id, store_id, items[{item_id, quantity}]):
    # Step 0: Eligibility check
    zone_ok = checkDeliveryZone(customer_id, store_id)
    if not zone_ok: raise EligibilityError

    # Step 1: Create Order in pending state
    order_id = generateUUID()
    idempotency_key = hash(customer_id + cart_fingerprint)
    existing = lookupIdempotencyKey(idempotency_key)
    if existing: return existing  # idempotent replay

    order = INSERT INTO orders (id, customer_id, store_id, status='pending', version=0)
    persistIdempotencyKey(idempotency_key, order_id)

    # Step 2: Authorize payment (async, but must succeed before reservations)
    auth_result = authorizePayment(customer_id, estimatedTotal(items),
                                   idempotency_key=order_id+":auth")
    if auth_result.failed:
        markOrder(order_id, status='cancelled', reason='payment_auth_failed')
        return Error("payment_authorization_failed")

    INSERT INTO payments (order_id, status='authorized', auth_token=auth_result.token,
                          authorized_amount=auth_result.amount)

    # Step 3: Reserve items (Saga — each step compensable)
    reserved = []
    for item in items:
        step_key = order_id + ":" + item.item_id + ":reserve"
        if lookupIdempotencyKey(step_key):
            reserved.append(item)
            continue  # already reserved (retry path)

        # CAS on stock counter
        result = executeSQL("""
            UPDATE items
            SET stock_count = stock_count - :qty,
                version = version + 1
            WHERE item_id = :item_id
              AND stock_count >= :qty
              AND version = :expected_version
        """, item_id=item.item_id, qty=item.quantity,
             expected_version=item.read_version)

        if result.rows_affected == 0:
            # Saga rollback: release all previously reserved items
            for prev in reserved:
                releaseReservation(order_id, prev.item_id)  # idempotent
            markOrder(order_id, status='cancelled', reason='item_unavailable:'+item.item_id)
            voidPaymentAuth(order_id, idempotency_key=order_id+":void")
            return Error("item_out_of_stock", item_id=item.item_id)

        INSERT INTO inventory_reservations (
            order_id, item_id, quantity, status='confirmed'
        )
        persistIdempotencyKey(step_key, "confirmed")
        reserved.append(item)

    # Step 4: Advance order to accepted
    CAS_update(orders, order_id,
               expected_status='pending', new_status='accepted',
               expected_version=0, new_version=1)

    publishToOutbox(order_id, event='order_accepted', payload=order)
    return order_id


function releaseReservation(order_id, item_id):
    # Idempotent: safe to call multiple times
    reservation = SELECT ... WHERE order_id=order_id AND item_id=item_id
    if reservation.status == 'released': return  # already done

    UPDATE items SET stock_count = stock_count + reservation.quantity
      WHERE item_id = item_id
    UPDATE inventory_reservations SET status='released'
      WHERE order_id=order_id AND item_id=item_id AND status != 'released'

Algorithm 2: Shopper Assignment #

function assignShopper(order_id, store_id):
    order = getOrder(order_id)
    assert order.status == 'accepted'

    MAX_ATTEMPTS = 5
    attempts = 0

    while attempts < MAX_ATTEMPTS:
        # Find nearby available shoppers
        store_location = getStoreLocation(store_id)
        candidates = GEORADIUS(key='shoppers:available',
                               lat=store_location.lat, lon=store_location.lon,
                               radius=10km, sort=ASC, count=10)

        for shopper_id in candidates:
            lease_key = "shopper:" + shopper_id + ":claim"
            fencing_token = generateFencingToken()

            # Attempt to acquire lease
            acquired = SETNX(lease_key,
                             value=json(order_id=order_id, token=fencing_token),
                             EX=30)  # 30s TTL

            if not acquired: continue  # already claimed by another order

            # Verify shopper is still available in Postgres (lease acquired)
            shopper = SELECT ... FROM shoppers WHERE id=shopper_id FOR UPDATE
            if shopper.status != 'available':
                DEL(lease_key)  # release lease — stale Redis state
                continue

            # Saga step 1: Update Order with shopper
            order_updated = CAS_update(orders, order_id,
                expected_status='accepted', new_status='shopping',
                expected_version=order.version,
                new_version=order.version+1,
                new_shopper_id=shopper_id,
                new_fencing_token=fencing_token)

            if not order_updated:
                DEL(lease_key)  # compensate
                return  # concurrent assignment won — OK

            # Saga step 2: Update Shopper status (with fencing token validation)
            UPDATE shoppers SET status='on_order', assigned_order_id=order_id
              WHERE id=shopper_id
                AND status='available'
                AND (last_fencing_token IS NULL OR last_fencing_token < fencing_token)

            # Lease remains held; will be released when order reaches delivered/cancelled
            publishToOutbox(order_id, event='shopper_assigned', shopper_id=shopper_id)
            return order_id

        attempts++
        sleep(exponential_backoff(attempts))

    # No shopper available — requeue order for retry
    publishDelayed(order_id, event='assignment_retry', delay=60s)

Algorithm 3: Substitution Approval Flow #

function proposeSubstitution(shopper_id, order_id, item_id, substitute_item_id, reason):
    # Verify shopper is assigned to this order
    order = getOrder(order_id)
    assert order.assigned_shopper_id == shopper_id
    assert order.status == 'shopping'

    # Verify original item reservation is active
    reservation = getReservation(order_id, item_id)
    assert reservation.status == 'confirmed'

    # Uniqueness check (also enforced by DB constraint)
    existing = SELECT ... FROM substitution_requests
      WHERE order_id=order_id AND item_id=item_id AND status='pending_approval'
    if existing: raise UniqueConstraintError

    expiry = now() + 10 minutes  # configurable window
    sub_req = INSERT INTO substitution_requests (
        id=generateUUID(), order_id, item_id, substitute_item_id, reason,
        status='pending_approval', version=0, expires_at=expiry
    )

    # Register deadline in Redis ZSET
    ZADD('substitution:deadlines', expiry.unix_timestamp, sub_req.id)

    # Outbox event → Kafka → push notification + WebSocket
    publishToOutbox(sub_req.id, event='substitution_proposed',
                    payload={order_id, item_id, substitute_item_id, expiry})
    return sub_req.id


function approveSubstitution(customer_id, substitution_request_id):
    sub = getSubstitutionRequest(substitution_request_id) FOR UPDATE
    assert sub.status == 'pending_approval'
    assert sub.expires_at > now()
    assert getOrder(sub.order_id).customer_id == customer_id  # access control

    # CAS transition
    CAS_update(substitution_requests, sub.id,
               expected_status='pending_approval', new_status='approved',
               expected_version=sub.version, new_version=sub.version+1)

    # Remove deadline from Redis ZSET
    ZREM('substitution:deadlines', sub.id)

    # Outbox → Kafka → downstream effects:
    #   - InventoryReservation service: release old item reservation, create new
    #   - OrderItem service: update item_id to substitute
    publishToOutbox(sub.id, event='substitution_approved',
                    payload={order_id=sub.order_id, old_item=sub.item_id,
                             new_item=sub.substitute_item_id})


function sweepExpiredSubstitutions():
    # Runs every 10 seconds
    now_ts = unix_timestamp()
    expired_ids = ZRANGEBYSCORE('substitution:deadlines', 0, now_ts, LIMIT 100)

    for sub_id in expired_ids:
        sub = getSubstitutionRequest(sub_id) FOR UPDATE
        if sub.status != 'pending_approval':
            ZREM('substitution:deadlines', sub_id)
            continue  # already resolved

        # Idempotent CAS
        updated = CAS_update(substitution_requests, sub_id,
                             expected_status='pending_approval', new_status='expired',
                             expected_version=sub.version)
        if updated:
            ZREM('substitution:deadlines', sub_id)
            publishToOutbox(sub_id, event='substitution_expired',
                            payload={order_id=sub.order_id, item_id=sub.item_id})
            # Downstream: release InventoryReservation for original item
            #             remove OrderItem from order

Algorithm 4: Payment Capture #

function capturePayment(order_id):
    # Triggered by CDC event: Order.status changed to 'delivered'

    payment = SELECT ... FROM payments WHERE order_id=order_id FOR UPDATE
    if payment.status != 'authorized':
        log("Ignoring capture trigger — payment status: " + payment.status)
        return  # idempotent: already captured or not authorizable

    # Calculate final amount (may differ from auth due to substitutions/removals)
    final_amount = calculateFinalAmount(order_id)
    assert final_amount <= payment.authorized_amount * 1.10  # max 10% variance

    # Call PSP with idempotency key
    capture_result = psp.capture(
        auth_token=payment.auth_token,
        amount=final_amount,
        idempotency_key=order_id + ":capture"
    )

    if capture_result.success:
        CAS_update(payments, payment.id,
                   expected_status='authorized', new_status='captured',
                   expected_version=payment.version,
                   new_captured_amount=final_amount,
                   captured_at=now())
    else if capture_result.auth_expired:
        # Authorization expired — re-authorize then capture
        reauth_result = psp.authorize(
            customer_payment_method=payment.payment_method_token,
            amount=final_amount,
            idempotency_key=order_id + ":reauth"
        )
        if reauth_result.success:
            psp.capture(auth_token=reauth_result.token, amount=final_amount,
                        idempotency_key=order_id + ":capture:v2")
            UPDATE payments SET status='captured', ... WHERE id=payment.id
        else:
            UPDATE payments SET status='failed', failure_reason='reauth_declined'
            # Alert: manual review required
            publishAlert('payment_capture_failed', order_id=order_id)
    else:
        # Transient PSP error — exponential retry (max 3 attempts over 5 minutes)
        scheduleRetry('capture_payment', order_id=order_id, attempt=1, delay=30s)

Order State Machine #

States: pending → accepted → shopping → substitution_pending → picked → in_transit → delivered
         └──────────────────────────────────────────────────────────────────────────────────→ cancelled

Legal transitions:
  pending        → accepted           (system: shopper assigned)
  pending        → cancelled          (customer: within cancellation window)
  accepted       → shopping           (shopper: arrived at store, started shopping)
  accepted       → cancelled          (customer: before shopper starts)
  shopping       → substitution_pending (system: when SubstitutionRequest created)
  substitution_pending → shopping     (system: when all pending substitutions resolved)
  shopping       → picked             (shopper: all items confirmed picked)
  picked         → in_transit         (shopper: left store with order)
  in_transit     → delivered          (shopper: confirmed delivery)
  any non-terminal → cancelled        (system: forced cancellation with compensation)

Note: substitution_pending is a synthetic state — the Order may have multiple concurrent
SubstitutionRequests. The state returns to 'shopping' when all are resolved.
Guard: Order may only transition to picked when zero SubstitutionRequests are in pending_approval state.

Step 9 — Logical Data Model #

Schema #

-- Stable entities

CREATE TABLE delivery_zones (
    zone_id         UUID PRIMARY KEY,
    name            TEXT NOT NULL,
    boundary        GEOMETRY(POLYGON, 4326) NOT NULL,  -- PostGIS
    active          BOOLEAN DEFAULT TRUE,
    created_at      TIMESTAMPTZ DEFAULT NOW()
);
-- Index: GIST(boundary) for zone containment queries

CREATE TABLE stores (
    store_id        UUID PRIMARY KEY,
    name            TEXT NOT NULL,
    zone_id         UUID NOT NULL REFERENCES delivery_zones(zone_id),
    location        GEOMETRY(POINT, 4326) NOT NULL,
    active          BOOLEAN DEFAULT TRUE,
    created_at      TIMESTAMPTZ DEFAULT NOW()
);
-- Index: store_id (PK), zone_id, GIST(location)

CREATE TABLE items (
    item_id         UUID PRIMARY KEY,
    store_id        UUID NOT NULL REFERENCES stores(store_id),
    name            TEXT NOT NULL,
    price_cents     INTEGER NOT NULL,
    stock_count     INTEGER NOT NULL DEFAULT 0 CHECK (stock_count >= 0),
    version         BIGINT NOT NULL DEFAULT 0,
    active          BOOLEAN DEFAULT TRUE,
    updated_at      TIMESTAMPTZ DEFAULT NOW()
);
-- Partition key: store_id (logical partition; physical by store_id range or hash)
-- Index: (store_id, active) for browse queries
-- Note: stock_count is the single source of truth for available inventory.
--       It is decremented by CAS at reservation time.

CREATE TABLE shoppers (
    shopper_id      UUID PRIMARY KEY,
    name            TEXT NOT NULL,
    status          TEXT NOT NULL DEFAULT 'offline'
                    CHECK (status IN ('offline', 'available', 'on_order')),
    assigned_order_id UUID,
    zone_id         UUID REFERENCES delivery_zones(zone_id),
    last_fencing_token TEXT,
    version         BIGINT NOT NULL DEFAULT 0,
    updated_at      TIMESTAMPTZ DEFAULT NOW()
);
-- Index: (status, zone_id) for availability queries

-- Process objects

CREATE TABLE orders (
    order_id        UUID PRIMARY KEY,
    customer_id     UUID NOT NULL,
    store_id        UUID NOT NULL REFERENCES stores(store_id),
    shopper_id      UUID REFERENCES shoppers(shopper_id),
    status          TEXT NOT NULL DEFAULT 'pending'
                    CHECK (status IN ('pending','accepted','shopping',
                                     'substitution_pending','picked',
                                     'in_transit','delivered','cancelled')),
    cancellation_reason TEXT,
    version         BIGINT NOT NULL DEFAULT 0,
    idempotency_key TEXT UNIQUE,
    created_at      TIMESTAMPTZ DEFAULT NOW(),
    updated_at      TIMESTAMPTZ DEFAULT NOW()
);
-- Partition key: customer_id (most queries scoped to customer)
-- Index: (customer_id, created_at DESC), (shopper_id, status), (status, created_at)

CREATE TABLE order_items (
    order_item_id   UUID PRIMARY KEY,
    order_id        UUID NOT NULL REFERENCES orders(order_id),
    item_id         UUID NOT NULL REFERENCES items(item_id),
    quantity        INTEGER NOT NULL CHECK (quantity > 0),
    unit_price_cents INTEGER NOT NULL,  -- price at order time, snapshot
    resolution      TEXT DEFAULT 'pending'
                    CHECK (resolution IN ('pending','fulfilled','substituted','removed')),
    created_at      TIMESTAMPTZ DEFAULT NOW()
);
-- Index: (order_id) — always queried by order

CREATE TABLE inventory_reservations (
    reservation_id  UUID PRIMARY KEY,
    order_id        UUID NOT NULL REFERENCES orders(order_id),
    item_id         UUID NOT NULL REFERENCES items(item_id),
    quantity        INTEGER NOT NULL,
    status          TEXT NOT NULL DEFAULT 'confirmed'
                    CHECK (status IN ('confirmed','released','fulfilled')),
    idempotency_key TEXT UNIQUE,  -- order_id:item_id:reserve
    created_at      TIMESTAMPTZ DEFAULT NOW(),
    updated_at      TIMESTAMPTZ DEFAULT NOW(),
    UNIQUE (order_id, item_id)  -- enforces I5
);
-- Partition key: item_id (for stock aggregation queries)
-- Index: (order_id), (item_id, status)

CREATE TABLE substitution_requests (
    substitution_id     UUID PRIMARY KEY,
    order_id            UUID NOT NULL REFERENCES orders(order_id),
    item_id             UUID NOT NULL REFERENCES items(item_id),
    substitute_item_id  UUID NOT NULL REFERENCES items(item_id),
    shopper_reason      TEXT,
    status              TEXT NOT NULL DEFAULT 'pending_approval'
                        CHECK (status IN ('pending_approval','approved','rejected','expired')),
    version             BIGINT NOT NULL DEFAULT 0,
    expires_at          TIMESTAMPTZ NOT NULL,
    created_at          TIMESTAMPTZ DEFAULT NOW(),
    updated_at          TIMESTAMPTZ DEFAULT NOW()
);
-- Unique constraint: only one pending per (order_id, item_id)
-- Enforced by partial unique index:
CREATE UNIQUE INDEX uq_substitution_active
    ON substitution_requests(order_id, item_id)
    WHERE status = 'pending_approval';
-- Index: (expires_at) for sweeper queries, (order_id)

CREATE TABLE payments (
    payment_id          UUID PRIMARY KEY,
    order_id            UUID NOT NULL UNIQUE REFERENCES orders(order_id),
    status              TEXT NOT NULL DEFAULT 'pending'
                        CHECK (status IN ('pending','authorized','captured','refunded','failed')),
    authorized_amount   INTEGER,  -- in cents
    captured_amount     INTEGER,
    auth_token          TEXT,     -- PSP auth token
    payment_method_token TEXT,    -- tokenized card reference
    failure_reason      TEXT,
    version             BIGINT NOT NULL DEFAULT 0,
    authorized_at       TIMESTAMPTZ,
    captured_at         TIMESTAMPTZ,
    auth_expires_at     TIMESTAMPTZ,
    created_at          TIMESTAMPTZ DEFAULT NOW()
);
-- Index: (order_id) unique, (status, authorized_at) for expiry reconciliation

-- Events (append-only, high volume)

-- LocationPing stored in Cassandra (see Step 10)
-- Schema shown here for reference:
-- CREATE TABLE location_pings (
--     shopper_id  UUID,
--     ts          TIMESTAMP,
--     lat         DOUBLE,
--     lon         DOUBLE,
--     accuracy_m  FLOAT,
--     PRIMARY KEY ((shopper_id), ts)
-- ) WITH CLUSTERING ORDER BY (ts DESC);

-- Outbox table (per-service, for transactional outbox pattern)

CREATE TABLE outbox_events (
    event_id        UUID PRIMARY KEY DEFAULT gen_random_uuid(),
    aggregate_id    UUID NOT NULL,
    event_type      TEXT NOT NULL,
    payload         JSONB NOT NULL,
    published       BOOLEAN DEFAULT FALSE,
    created_at      TIMESTAMPTZ DEFAULT NOW()
);
-- Index: (published, created_at) for relay queries

-- Idempotency key store

CREATE TABLE idempotency_keys (
    idem_key        TEXT PRIMARY KEY,
    result_ref      TEXT NOT NULL,  -- order_id or reservation_id
    created_at      TIMESTAMPTZ DEFAULT NOW()
);
-- TTL managed by background cleanup job (keys older than 24h deleted)

Step 10 — Technology Landscape #

Technology Selection Table #

Why Not Alternatives #

Step 11 — Deployment Topology #

Service Decomposition #

┌─────────────────────────────────────────────────────────────────────────┐
│                          API Gateway (Kong)                             │
│          TLS termination, auth, rate limiting, routing                  │
└──────┬────────────┬──────────────┬─────────────┬────────────────────────┘
       │            │              │             │
       ▼            ▼              ▼             ▼
┌─────────┐  ┌──────────┐  ┌──────────┐  ┌──────────────┐
│ Customer│  │  Order   │  │ Shopper  │  │   Payment    │
│ Service │  │ Service  │  │ Service  │  │   Service    │
│         │  │          │  │          │  │              │
│ Profile │  │ Place    │  │ Location │  │ Auth/Capture │
│ Auth    │  │ Status   │  │ Tracking │  │ Reconcile    │
└────┬────┘  └────┬─────┘  └────┬─────┘  └──────┬───────┘
     │            │              │                │
     ▼            ▼              ▼                ▼
┌──────────────────────────────────────────────────────────┐
│                    Postgres (Primary)                     │
│  orders, order_items, payments, customers, shoppers,     │
│  inventory_reservations, substitution_requests, outbox   │
│  Read replicas for browse/reporting queries              │
└────────────────────────┬─────────────────────────────────┘
                         │ Debezium CDC
                         ▼
┌──────────────────────────────────────────────────────────┐
│                  Apache Kafka (3 brokers)                 │
│  Topics: order-events, location-stream, inventory-events │
│          substitution-events, payment-events, outbox-relay│
└──────┬────────────────┬─────────────────┬────────────────┘
       │                │                 │
       ▼                ▼                 ▼
┌───────────┐   ┌─────────────┐  ┌─────────────────┐
│Notification│  │  Analytics  │  │ Outbox Relay    │
│  Service  │   │  Consumer   │  │ (Debezium sink) │
│ FCM/APNs  │   │ (Spark/Flink│  │                 │
└───────────┘   └─────────────┘  └─────────────────┘

┌──────────────────────────────────────────────────────────┐
│                   Redis Cluster                          │
│  - Shopper leases (SETNX)                               │
│  - Shopper geo index (GEOADD)                           │
│  - Substitution deadline ZSET                           │
│  - Order status pub/sub channels                        │
│  - Available item cache (read-through)                  │
└──────────────────────────────────────────────────────────┘

┌──────────────────────────────────────────────────────────┐
│                  Cassandra Cluster (3 nodes)             │
│  - LocationPing history                                  │
│  Partition: shopper_id; Cluster: timestamp DESC         │
└──────────────────────────────────────────────────────────┘

Regions and Replication #

• Primary region: Active-active multi-AZ within one region (3 AZs).
• Postgres: Primary + 2 synchronous replicas (for failover). Read replicas for browse queries. Streaming replication.
• Redis Cluster: 3 primary shards × 1 replica per shard = 6 nodes across 3 AZs.
• Kafka: 3 brokers, replication factor 3, min.insync.replicas=2.
• Cassandra: Replication factor 3, LOCAL_QUORUM reads and writes.
• Multi-region: Phase 2 evolution (see Step 20). Initially single-region.

Container Layout #

Each service is a separate Kubernetes Deployment:

• Order Service: 6-20 pods (HPA on CPU + pending order queue depth)
• Shopper Service: 4-12 pods (HPA on active shoppers × location ping rate)
• Assignment Service: 3-6 pods (HPA on assignment queue depth)
• Payment Service: 3-6 pods (stateless; PSP calls are the bottleneck)
• Notification Service: 3-6 pods (fan-out workload)
• Outbox Relay: 2 pods (low volume; single-writer per outbox shard)
• Substitution Sweeper: 2 pods (leader-elected; single active at a time)

Step 12 — Consistency Model #

Per-Path Classification #

Step 13 — Scaling Model #

Traffic Estimation #

Scaling Dimensions #

Hotspot Analysis #

• Popular item at single store: stock_count row is a hotspot. At extreme scale (Black Friday), use a reservation queue (Kafka) rather than synchronous CAS — serialize reservation requests per item through a single partition consumer. This is a Phase 2 mitigation.
• Shopper in high-density area: Redis Geo shard by zone; zone is the partition boundary. One zone’s shoppers live on one Redis shard.
• Kafka partition hotspot: Order events partitioned by order_id (random distribution). Location stream partitioned by shopper_id (even distribution by shopper count, not geography).

Step 14 — Failure Model #

Failure Enumeration #

Step 15 — SLOs #

Service Level Objectives #

Error Budget #

• Order service: 43.8 minutes downtime per month.
• Payment service: 21.9 minutes downtime per month.
• Burn rate alerting: if error budget burns > 5× expected rate for 1 hour → page on-call.

Step 16 — Operational Parameters #

Tunable Parameters #

Circuit Breaker Parameters #

Step 17 — Runbooks #

Runbook 1: Inventory Oversell Detection #

Trigger: Alert fires: inventory_negative_stock metric > 0 for any item_id.

Root cause: CAS guard bypassed (bug) OR stock_count initialized incorrectly OR compensating transaction double-applied.

Steps:

1. Query: SELECT item_id, stock_count FROM items WHERE stock_count < 0. Identify affected items.
2. Query: SELECT * FROM inventory_reservations WHERE item_id = :item_id AND status = 'confirmed'. Sum quantities.
3. Compare sum(reservations) with initial_stock (from audit log). Identify discrepancy.
4. If stock_count < 0: immediate lock — set item.active = false to prevent further orders.
5. Identify affected orders (reservations referencing this item_id). Triage: which orders are still in shopping phase vs picked/delivered.
6. For picked/delivered orders: allow completion; adjust stock manually.
7. For shopping orders: contact shoppers; may need to cancel items.
8. Root cause analysis: enable DEBUG logging on item CAS path; replay recent reservations from Kafka topic.
9. Fix stock_count: UPDATE items SET stock_count = max(0, initial_stock - confirmed_reservations).
10. Re-enable item: UPDATE items SET active = true WHERE item_id = :item_id.

Runbook 2: Shopper Lease Stuck (Shopper Permanently in on_order) #

Trigger: Alert: shopper_id has been in on_order status for > 4 hours with no location ping for > 30 minutes.

Steps:

1. Verify: SELECT * FROM shoppers WHERE shopper_id = :id. Check assigned_order_id.
2. Check order status: SELECT status FROM orders WHERE order_id = :assigned_order_id.
3. Check Redis lease: GET shopper:{shopper_id}:claim. If key exists, note TTL.
4. If order is delivered/cancelled but shopper status is still on_order: this is a missed status reset.
   • Check outbox_events for the relevant order transition — was it published? Was the Shopper service consumer lagging?
   • Manual fix: UPDATE shoppers SET status='available', assigned_order_id=NULL WHERE shopper_id=:id.
   • DEL shopper:{shopper_id}:claim if key still exists.
5. If order is in active state but shopper is unreachable: attempt to contact shopper via ops tooling. If genuinely lost, escalate to manual delivery or reassignment.
6. For reassignment: cancel current assignment (system-level), trigger new assignment saga for the order.

Runbook 3: Payment Capture Failure #

Trigger: Alert: payment_capture_failed event, or Payment record in authorized state for > 24h after Order.status = delivered.

Steps:

1. Query: SELECT * FROM payments WHERE order_id = :order_id.
2. Check PSP portal for auth_token status. Is auth still valid?
3. If auth expired: manually trigger re-authorization via internal admin API (POST /admin/payments/:id/reauth). This uses the payment_method_token to issue a new auth.
4. If PSP is degraded: check circuit breaker status in Grafana. If circuit is open, wait for PSP recovery; circuit will auto-retry.
5. If customer card declined during re-auth: flag order for finance team. Send customer notification. Create manual review ticket.
6. If capture succeeds eventually: close ticket.
7. Post-mortem: if multiple orders affected simultaneously → PSP incident. Coordinate with PSP support.

Runbook 4: Substitution Sweeper Backlog #

Trigger: Alert: substitution_deadlines_backlog (ZCARD of substitution:deadlines > 1000 entries with score < now).

Steps:

1. Check sweeper pod health: kubectl get pods -l app=substitution-sweeper.
2. If pod is crashed: kubectl describe pod to see crash reason. Check logs. Restart pod.
3. If sweeper is running but backlog is growing: check Postgres write latency. SubstitutionRequest CAS updates may be slow.
4. Verify no lock contention: SELECT * FROM pg_stat_activity WHERE wait_event_type='Lock'.
5. If backlog is non-critical (< 10 min delay): let sweeper process naturally; it will catch up.
6. If critical (hour+ delay with customer-visible stuck orders): deploy emergency parallel sweeper with a different ZSET range split (e.g., two sweepers each taking half the score range). Coordinate via Redis distributed lock to prevent double-processing — or rely on CAS guard.

Step 18 — Observability #

Metrics (Prometheus) #

Distributed Tracing (Jaeger) #

Every request carries a trace-id propagated via HTTP headers and Kafka message headers. Key trace spans:

• order.place → includes child spans: zone_check, payment.authorize, inventory.reserve[item_id=X] (one per item), order.status_transition
• assignment.run → includes: geo_query, lease.acquire[shopper_id=X], order.update_shopper, shopper.update_status
• substitution.propose → includes: reservation.check, db.insert, deadline.register, notification.publish
• payment.capture → includes: order.verify_delivered, psp.capture_call, payment.status_transition

Sampling: 10% of requests traced by default; 100% for error paths and P99+ latency paths.

Structured Logs (ELK) #

Every log line includes: trace_id, service, pod_id, order_id (where applicable), level, timestamp, message, duration_ms (for external calls).

Key log events:

• inventory_cas_failure: includes item_id, requested_qty, available_qty, attempt_number
• saga_compensation_triggered: includes order_id, step_failed, items_released
• shopper_lease_acquired: includes shopper_id, order_id, fencing_token
• shopper_lease_expired: includes shopper_id, previous_order_id
• payment_capture_attempted: includes order_id, amount_cents, idempotency_key, psp_response_code
• substitution_expired: includes substitution_id, order_id, item_id, delay_seconds

Dashboards #

1. Order Funnel Dashboard: placement rate, acceptance rate, cancellation rate by stage, P50/P95/P99 per stage.
2. Inventory Health Dashboard: items with negative stock (should always be 0), reservation hot spots, CAS retry rates.
3. Shopper Assignment Dashboard: assignment latency, lease acquisition success rate, available shopper count by zone.
4. Payment Dashboard: auth success rate, capture success rate, PSP latency, auth expiry count.
5. Real-time Ops Dashboard: active orders by status, active shoppers, pending substitutions, Kafka consumer lag.

Step 19 — Cost Model #

Infrastructure Cost Estimate (Monthly, AWS us-east-1) #

Variable Costs #

Cost per Order (Infrastructure only) #

At 100K orders/day = 3M orders/month:

• Infrastructure: $9,010 / 3,000,000 = $0.003/order (0.3 cents)
• PSP fees are the dominant variable cost (separate revenue model consideration)

Cost Optimization Levers #

1. Cassandra: Move location pings older than 90 days to S3 (lifecycle policy). Cassandra cluster shrinks by 60% after 6 months.
2. Read replicas: Scale down Postgres read replicas off-peak (scheduled RDS scaling).
3. Kafka: Use S3 tiered storage (MSK Connect) for topics older than 7 days. Reduces broker storage cost by 70%.
4. Item images: Use CloudFront origin shield to reduce S3 request costs.

Step 20 — Evolution Stages #

Stage 1: MVP (Months 0-3) #

Goal: Working system in one city, one delivery zone, ~1,000 orders/day.

What to build:

• Monolithic Order Service (handles placement + assignment + status)
• Postgres single instance (no replicas)
• Redis single node (no cluster)
• No Cassandra — location pings stored in Postgres (time-partitioned table)
• Basic FCM push (no WebSocket)
• Manual payment capture trigger (via internal admin UI)
• No Kafka — synchronous in-process event handling

What to defer:

• Cassandra migration (location pings)
• Kafka (event streaming)
• CDC / Debezium
• Substitution sweeper as a separate service
• Multi-zone, multi-city

Invariants that must hold even in MVP:

• I3 (no oversell) — CAS on stock_count must be implemented from day 1
• I7 (one shopper per order) — must work; use Postgres advisory lock if Redis not available
• I17 (idempotent payments) — idempotency keys on PSP calls from day 1

Stage 2: City Scale (Months 3-9) #

Goal: 5 cities, 10 zones, ~10K orders/day.

What to add:

• Extract Assignment Service from Order Service
• Add Kafka (3-broker cluster) — decouple notification fan-out
• Add Cassandra — migrate location pings from Postgres
• Add Redis Cluster — replace single node
• Add Postgres read replicas — separate browse reads
• Implement Outbox pattern — replace in-process event dispatch
• Add Debezium CDC — payment capture triggered by DB change
• Implement WebSocket for real-time customer updates
• Add circuit breakers on PSP calls

Migrations:

• Postgres location_pings table → Cassandra: dual-write for 2 weeks, then cut over reads, then drop table
• In-process events → Outbox + Kafka: feature-flagged per service, gradual rollout

Stage 3: National Scale (Months 9-24) #

Goal: 50 cities, 500 zones, ~100K orders/day, SLA 99.9%.

What to add:

• Horizontal Postgres sharding by zone_id (Citus or manual application-level sharding)
• Kafka partition expansion (increase to 50 partitions per topic)
• Cassandra cluster expansion to 9 nodes
• Redis Cluster expansion to 9 shards
• CQRS pattern — separate read model (Elasticsearch) for item search with full-text
• Auth expiry reconciliation job (scheduled daily)
• Full observability stack (Prometheus + Grafana + Jaeger + ELK)
• Chaos engineering (Chaos Monkey) — validate failure recovery

Stage 4: Multi-Region (Month 24+) #

Goal: < 100ms latency in each region; regional failure isolation; 99.95% SLA.

Design changes:

• Active-active multi-region with conflict resolution
• Order data: region-pinned (order belongs to the region where it was placed; no cross-region write)
• Shopper data: replicated read-only to other regions; writes go to home region
• Item catalog: replicated globally; writes in home region, CDC to all regions
• Payment: globally replicated Payment table; capture always goes to original auth region (PSP requires it)
• Kafka MirrorMaker 2 for cross-region topic replication
• Global API gateway (Cloudflare or AWS Global Accelerator) for geo-routing

What does NOT need cross-region coordination:

• Inventory reservation (inventory is physical — a store in Seattle doesn’t serve a customer in Austin)
• Shopper assignment (shoppers are local)
• Location pings (local to the order’s region)

What DOES need cross-region:

• Customer profile and payment method tokens (global read; home-region write)
• Item catalog (global read; store-local write)
• Analytics/reporting (global aggregation)

Evolution Decision Points #

Summary: Key Design Decisions and Their Derivations #