Marketplace, Dispatch, and Logistics System Design Questions

For real-time nearest-neighbor (NN) with out-of-order or delayed location updates, you balance correctness (assignment fidelity) against latency. Here's how the four techniques help and their trade-offs.

Watermarking

• What: Stream engine estimates an event-time progress point; events older than the watermark are considered late.
• Effect: Lowers state retention and makes results stable once watermark advances. Improves throughput and bounded latency.
• Trade-off: If watermark is aggressive (fast), late events are dropped → potential incorrect NN assignments. If conservative, latency increases.

Windowing

• What: Group events into event-time windows (sliding/tumbling/session) for localized NN computation.
• Effect: Controls computation scope and enables aggregation and periodic re-evaluation.
• Trade-off: Window size impacts freshness vs. tolerance for reordering: larger windows absorb more out-of-order data (better correctness) but increase result latency and state size.

Event TTLs / Late-arrival policy

• What: Keep per-entity state for a defined TTL; accept/reject or reprocess late events within TTL.
• Effect: TTL lets you correct assignments when moderately late updates arrive; you can emit tentative assignments and correct them if needed.
• Trade-off: Longer TTL improves correctness but increases memory and potential churn (retractions/compensations), hurting tail latency and storage.

Vector Clocks / Causal Metadata

• What: Attach logical clocks (or sequence numbers) per device/partition to detect ordering and causality.
• Effect: Enables precise reconciliation (apply only newer updates, detect duplicates), improving correctness without long windows.
• Trade-off: Requires distributed coordination or per-source monotonic counters; adds metadata and complexity but keeps latency low compared to large windows.

Practical pattern (recommendation)

• Combine: Use event-time watermarking + modest sliding windows for batchable NN, keep per-entity TTL for reconciliation, and attach source sequence numbers/vector clocks to resolve conflicts deterministically. Emit tentative NN quickly (low-latency) and emit correction events when late but within TTL. Tune watermark lateness and TTL based on observed network jitter and SLA for acceptable correction rate.

Metrics to monitor: late-event rate, correction frequency, average and p95 latency, state size. Tune trade-offs to meet customer SLAs for correctness vs. responsiveness.

Requirements & constraints:

• Mobile drivers must accept/complete jobs while offline; actions must queue locally, survive app restarts, and reconcile safely when online.
• Server is authoritative for assignment; avoid duplicate assignment when many drivers reconnect.
• Provide clear UI states (pending/confirmed/failed) without exposing inconsistency.

High-level approach:

• Local durable operation log + persistent queue (SQLite/Realm/LevelDB) per driver.
• Each user action becomes an append-only op: {op_id: UUID, driver_id, job_id, type: accept|complete, client_seq, created_at, payload, retry_count}.
• Sync protocol: client pushes ops in order to server; server applies ops idempotently, responds with authoritative job state and op results; client reconciles local state.

Core components & responsibilities:

1. Mobile client

• Local store for jobs + operation queue.
• UI shows authoritative_state + pending overlay per job (tentative UI).
• Sync worker: exponential backoff, network change listener, background sync (WorkManager/iOS background tasks).

2. Server

• Ingestion API supporting idempotency keys (op_id) and client_seq.
• Authoritative job-state store with version (job_version) and assignment metadata.
• Conflict resolution & assignment logic (CAS/transactional).

3. Assignment coordinator

• Single-source assignment: in DB transaction or via lightweight distributed lock (Redis SETNX with short lease) or use database row-level optimistic locking (UPDATE ... WHERE version = X).
• On accept: server verifies job state = available; APPLY: update job.assigned_to = driver_id, job_version++; record op_id as applied.
• On complete: validate job.assigned_to == driver_id; allow idempotent replay.

Idempotent reconciliation design:

• Server keeps a table of applied op_ids (or per-job last_applied_client_seq per driver) to detect duplicates and avoid reapplying.
• When an op arrives:
  • If op_id seen -> return previous result (idempotent).
  • Else attempt to apply in a DB transaction:
    • Read job row (current_version).
    • Validate preconditions (e.g., available or assigned to this driver).
    • Perform CAS update: UPDATE jobs SET assigned_to=?, status=?, version=version+1 WHERE job_id=? AND version=curr_version;
    • If update succeeds -> persist op_id -> publish update to other systems and return success.
    • If fails due to version mismatch -> recompute outcome (job already assigned) and return authoritative state.
• Use strict ordering per-client using client_seq to detect missed prior ops and either reject out-of-order or queue them server-side until earlier seqs arrive.

Prevent duplicate assignments when many reconnect:

• Rely on server-side atomicity, not client coordination.
• Use database atomic CAS or transactional locking to ensure only one accept can change job from available -> assigned.
• For high scale, use optimistic concurrency on primary DB or a partitioned assignment service:
  • Shard jobs by id; assignment requests for same job route to same shard/leader.
  • Alternatively, use a lightweight consensus (e.g., leader per shard) or Redis-based atomic SET with NX plus lease to temporarily reserve while commit completes.
• For race cases where multiple offline accepts replay nearly simultaneously: first successful DB transaction wins; others receive authoritative state showing job already assigned and client must mark local op as failed and surface appropriate UI.

UI & UX considerations (safe pending states):

• Show authoritative_job_state combined with local optimistic overlays:
  • pending_accept: show "Accepted (pending sync)" but distinct color and actions disabled (no further accepts).
  • pending_complete: show "Completing..." with spinner; allow undo/cancel only if local op not yet sent.
• Attach TTL/expiry to pending ops: if not reconciled in N minutes, show "Syncing — tap to retry" to avoid permanent confusion.
• Never show a job as definitively assigned to other drivers until server confirms; if a server response says conflict, show clear failed state and next actions (refresh, reassign).
• Provide audit trail: show last sync time, pending ops count.

Edge cases & operational details:

• Clock skew: use server timestamps as authoritative; client uses created_at only for ordering; server records apply_time.
• Network duplication & retries: idempotency via op_id prevents double application.
• App restarts: persist queue and client_seq; resume in-flight uploads safely.
• Partial sync: ensure server returns job_version and last_applied_seq so clients can reconcile.
• Security: authenticate ops with tokens; validate driver ownership.
• Offline job visibility: prevent drivers from performing actions on stale jobs by showing last-known version and warning when stale.

Scaling & trade-offs:

• Simplicity: single DB CAS works well; scales to many jobs with sharding. Redis leases lower latency but requires careful lease/commit race handling.
• Strong consistency vs availability: this design favors consistency for assignment correctness—some accept latency when DB contention occurs.
• CRDTs not ideal for exclusive assignment (requires single-writer semantics).

Example flow (accept while offline -> reconnect):

1. Driver taps Accept -> client enqueues op {op_id=UUID, client_seq=5}.
2. UI shows "Accepted (pending)".
3. On reconnect, client POSTs ops [seq5] to /sync.
4. Server sees op_id new; reads job.version=10 and status=available; attempts CAS -> succeeds -> records op_id, sets assigned_to=driver_id, version=11 -> returns success + job state.
5. Client marks op confirmed; UI updates to "Assigned" (confirmed). Other drivers receive push update for job removed.

This design guarantees no double-assignment (server atomicity), idempotent reconciliation (op_id + server op log), safe pending UI (optimistic with clear status and TTL), and robust scale via sharding or DB transactions.

Requirements (clarify): core SLA — always return matching & assignment decisions within X ms even if downstream (billing, notifications, analytics) are slow; avoid cascading failures; preserve eventual consistency for non-critical work.

High-level approach: isolate blocking calls, fail fast, degrade non-essential features to preserve core path.

Resiliency patterns

• Timeouts: enforce conservative timeouts per downstream (e.g., billing 200ms, notifications 100ms, analytics 50ms). Use client-side deadlines so matching completes within total request budget.
• Retries + jitter: retry idempotent calls (analytics) with exponential backoff and jitter; limit retries (max 2) and respect overall request deadline. Do NOT retry blocking synchronous billing in the hot path.
• Circuit breakers: per-downstream circuit breakers (error-rate & latency thresholds) to short-circuit calls when downstream unhealthy; use half-open probes to detect recovery.
• Bulkheads: isolate thread pools / connection pools per downstream and separate the core matching thread-pool. Limit concurrency to downstreams so slow services don’t exhaust resources needed for matching.
• Degraded flows / fallbacks:
  • Billing: for assignment, allow temporary “deferred-billing” mode — accept assignment and enqueue billing event to a durable queue (Kafka/SQS) if billing unavailable or CB open. Mark assignment state “billing-pending”.
  • Notifications: if notification delivery slow, enqueue messages to a delivery queue processed asynchronously with backpressure and DLQ; immediately respond to client that assignment succeeded.
  • Analytics: make analytics fire-and-forget; buffer to local queue and batch-send; if queues grow beyond threshold, drop non-critical analytics with sampling.
• Async queuing & durable buffer: all non-critical downstream interactions go through durable queues with retention; background workers handle retries with rate limiting.
• Backpressure & throttling: apply rate limits at ingress and per-caller to protect matching core under load.
• Observability & automation: instrument latencies, queue depth, circuit state, and SLA violations. Auto-open circuit and route to degraded flow. Alerting and runbooks.
• Consistency & reconciliation: background reconciler consumes billing-pending and DLQ to reconcile state; expose status endpoints to clients.

Trade-offs: immediate degraded assignment trades guaranteed synchronous billing for availability; design must document SLOs and business acceptance. This pattern preserves matching/assignment availability while ensuring downstream work is eventually consistent and non-blocking.

Requirements & constraints:

• Three client types (drivers, customers, partners) with different SLAs, auth modes, rate limits, and payload transformations. High availability, low latency, observability, extensibility.

High-level architecture:

• Global edge (CDN + regional API gateway cluster) -> Auth service (OAuth2.0 server, API-key service) -> Routing layer -> Microservices. Observability, WAF, and caching between gateway and services.

Authentication & Authorization:

• OAuth 2.0 + JWT for user-facing (drivers/customers): Authorization Code (mobile apps) with refresh tokens; ID token for identity, access token for resource access. Token introspection and short-lived JWT signed by auth service; public key via JWKS endpoint cached at gateways.
• API keys + mTLS for partners: partner issued long-lived API key bound to client id + optional mutual TLS for high-trust partners. Keys hashed and validated at gateway. Fine-grained scopes mapped to RBAC policies in an Authorization Service (OPA/Envoy RBAC) for per-endpoint checks.

Rate limiting & quotas:

• Two-layer limits: global (per-second) in gateway (token-bucket, distributed via Redis or in-memory with consistent hashing) and long-term quotas (daily/monthly) stored in central quota DB (Redis + persistent store).
• Per-client policies: default consumer (customers) e.g., 100 rps burst 200, drivers higher priority and lower latency (200 rps), partners configurable via contract (SLA: guaranteed rps, burst, concurrency).
• Priority queuing: when overloaded, throttle lowest-priority (public customers) first; partners with SLA get reserved tokens.

Routing & transformation:

• Use Envoy as gateway proxy with routing rules per hostname/header/client-id. Transformations via Lua/Filters for:
  • Protocol translation (HTTP/1.1 ↔ gRPC)
  • Payload shaping: remove PII for partners, enrich driver requests with geo headers
  • Versioning: route by Accept or x-api-version, defaulting to stable
• Canary and A/B routing via weighted clusters.

Caching strategies:

• Edge CDN for static or semi-static responses (fare estimates cache for short TTLs).
• Gateway-level response cache for idempotent GETs with per-client cache keys (vary by Authorization header for user-specific).
• Stale-while-revalidate for latency-sensitive reads; use cache-control headers set by services.
• Invalidate on events via message bus (Kafka) to invalidate caches for partner-specific data.

Exposing different SLAs:

• Contract-driven policy engine: partner profiles store SLA (SLA rps, latency SLO, availability). Gateway enforces:
  • Dedicated capacity pools or reserved tokens
  • SLA tracking: synthetic probes + per-request tracing to measure latency, error rates
  • Compensation: circuit-breakers and graceful degradation for non-SLA clients
• Provide partner portal with keys, metrics, usage dashboards and alerts.

Security & observability:

• WAF at edge, request signing for partners, rate-limit logs, distributed tracing (trace-id propagated), metrics (Prometheus) and dashboards/alerts for SLA breaches. Audit logs for auth events.
• Secrets rotated via Vault, API keys hashed, JWKS rotated.

Trade-offs:

• Centralized quota store (strong consistency) vs local caches (lower latency). Recommendation: hybrid: local for short-term, central for billing/quotas.
• Envoy + OPA offers policy flexibility; adds complexity.

This design gives low-latency edge enforcement, flexible auth, contract-based SLAs, and operational visibility.

Overview: RESTful JSON ETA API (HTTPS) for rider & driver clients. Versioned via URI (e.g., /v1/eta). TLS required, responses gzip/JSON.

Request (POST /v1/eta)

• client_id (string, required): SDK or app identifier
• client_timestamp (ISO8601, required): device time for latency analysis
• origin {lat (float), lon (float), accuracy_m (int, optional)}
• destination {lat, lon} (required for trip ETA; optional for nearby-driver ETA)
• mode (enum: "ride","bike","walk","transit", required)
• requested_accuracy (enum: "best","balanced","fast", optional default "balanced")
• context {platform:"rider"|"driver", device_id, session_id, debug:boolean}
• hints {cached_response_ok:boolean}

Response (200)

• eta_seconds (int)
• confidence_interval {low_seconds, high_seconds}
• model_version (string)
• computation_time_ms (int)
• cache_hint {ttl_seconds, source:"cache"|"model"|"hybrid"}
• currency_estimate {amount, currency} optional
• server_timestamp (ISO8601)

Errors (consistent structure: code, message, details)

• 400 INVALID_INPUT – missing/invalid fields
• 401 UNAUTHORIZED – invalid API key
• 403 FORBIDDEN – quota exceeded
• 404 NO_ROUTE – no path found
• 429 RATE_LIMIT – rate limit exceeded (Retry-After header)
• 500 INTERNAL_ERROR – transient, include error_id for support

Versioning strategy

• Major in URI (/v1/...), minor via headers: Accept: application/json;v=1.1 for non-breaking additions. Deprecation notices via response header X-API-Deprecation.

Rate limits & guidance

• Default: 60 req/min/client_id for riders, 30 req/min for drivers (background updates). Burstable: 120 for 10s. Provide tiered plans for partners. Return 429 with Retry-After.

SLA expectations

• 99.9% availability (excl. maintenance)
• P95 latency < 150ms for cached responses, < 400ms for model-computed
• Error budget and status page; provide bulk /batch endpoint for high-volume partners with negotiated SLAs.

Telemetry & best practices

• Clients send client_timestamp and device accuracy to improve reliability.
• Prefer client-side caching using cache_hint.ttl_seconds.
• Use client SDK to handle retries with exponential backoff and jitter; avoid retrying 4xx except 429.
• Include model_version in telemetry for A/B analysis.