Deadline-Conscious Stock Trading Agent Design

System Design Onsite / Phone Software Engineer

Problem Statement

Create a stock-trading agent that operates as an intermediary between customers and an external broker API. It needs to:

1. Receive purchase or sale orders that include a deadline supplied by the client.
2. Send those orders to a third-party brokerage.
3. Monitor each order until it reaches a filled or canceled state.
4. Cancel an order automatically when it remains unfilled at its deadline.
5. Tolerate surges in which a large number of orders reach their deadlines together.

Example requests:

BUY NFLX 24 "2024-06-14 14:30:00"
SELL INTC 15 "2024-06-14 11:45:00"

Broker APIs:

1. POST /orders submits a new order.
2. GET /orders/{orderId} retrieves an order's current state.
3. DELETE /orders/{orderId} requests cancellation of an order.

Note: This is an illustrative starting point. During an interview, present your own system and justify the decisions you make, since multiple designs can be valid.

Phase 1: Requirements

Functional Requirements

1. Allow BUY and SELL orders that specify an expiration deadline.
2. Let clients retrieve an order state: pending, filled, canceled, or expired.
3. Support client-initiated cancellation before the deadline passes.
4. Trigger cancellation automatically once the deadline is reached or exceeded.
5. Maintain a reliable audit history for every status transition.

Non-Functional Requirements

• Scale: sustain 2,000 orders per second on average and 10,000 orders per second at peak.
• Latency: the P95 response time for submitting an order must stay below 150ms.
• Availability: order creation and status lookup require 99.9% availability.
• Consistency: the broker remains authoritative, while local data must catch up within minutes.
• Durability: no orders may disappear, including during outages of either the service or broker.

Capacity Estimation

Traffic:
- Typical rate: 2,000 orders/s
- Maximum rate: 10,000 orders/s
- Orders per day: 2,000 * 86,400 = 172.8M orders/day

Storage (each order record is about 600 bytes):
- Storage added daily: ~104 GB/day
- Storage for one year: ~38 TB/year

Broker traffic (using a 90s mean fill duration and 20s polling interval):
- Concurrent active orders: 2,000 * 90 = 180,000
- Status checks: 180,000 / 20 = 9,000 GET/s
- Cancellation volume (25% expire): ~43M/day ~= 500 cancels/s average

Deadline bursts:
- Extreme case: 100,000 orders expire during one second

Make the cancellation burst at peak expiration an explicit design concern; it is frequently the most challenging aspect of this system.

Phase 2: Data Model

Core Entities

Order {
  id: UUID (PK)
  user_id: UUID
  symbol: String
  side: Enum(BUY, SELL)
  quantity: Int
  order_type: Enum(MARKET, LIMIT)
  limit_price: Decimal (optional)
  deadline_at: Timestamp
  status: Enum(SUBMITTED, PENDING, PARTIALLY_FILLED, FILLED, CANCELED, EXPIRED, FAILED)
  broker_order_id: String (nullable until submitted)
  filled_quantity: Int
  created_at: Timestamp
  updated_at: Timestamp
  version: Int
}

OrderEvent {
  id: UUID (PK)
  order_id: UUID (FK)
  event_type: Enum(CREATED, SUBMITTED_TO_BROKER, STATUS_UPDATE, CANCELED, EXPIRED)
  prev_status: Enum
  new_status: Enum
  metadata: JSON
  created_at: Timestamp
}

IdempotencyKey {
  key: String (PK)
  order_id: UUID
  created_at: Timestamp
  expires_at: Timestamp
}

Start with this lean interview schema, and introduce extra attributes only when discussing particular concerns, such as retry handling or reconciliation.

Phase 3: API Design

Protocol Choice

REST works well for the client-facing interface because it maps naturally to order CRUD operations. Use asynchronous events internally so that scheduling and broker communication are not tightly coupled.

Client-Facing Endpoints

POST /v1/orders
Request:
{
  "idempotency_key": "string",
  "user_id": "string",
  "side": "BUY" | "SELL",
  "symbol": "string",
  "quantity": 12,
  "order_type": "MARKET" | "LIMIT",
  "limit_price": 87.25,
  "deadline_at": "2026-04-18T16:30:00Z"
}
Response:
{
  "order_id": "uuid",
  "status": "SUBMITTED",
  "submitted_at": "timestamp"
}

GET /v1/orders/{order_id}
Response:
{
  "order_id": "uuid",
  "status": "PENDING",
  "filled_quantity": 0,
  "deadline_at": "timestamp",
  "updated_at": "timestamp"
}

DELETE /v1/orders/{order_id}
Response:
{
  "order_id": "uuid",
  "status": "CANCELED"
}

Internal Events

order.created
order.submitted_to_broker
order.status_updated
order.canceled

Idempotency keys are essential for retry-safe submission. Persist each key with a TTL, and when the same key is submitted again, return its existing order_id.

Phase 4: High-Level Design

High-Level System Architecture

Broker API

Asynchronous Services

Message Transport

Data Stores

Application Layer

Edge Layer

Clients

Client A

Client B

Client N

Load Balancer

Order API Authentication + Rate Limiting

PostgreSQL Orders + Events

Redis Cache + ZSET

Kafka or SQS Order Events

Broker Integration

Status Poller

Deadline Scheduler

Reconciliation Job

POST /orders

GET /orders/{id}

DELETE /orders/{id}

Request Flow

1. A client sends POST /v1/orders along with an idempotency key.
2. The API performs validation, persists the Order and OrderEvent in Postgres, then places order.created onto the queue.
3. The API adds the order_id to a Redis ZSET whose score is deadline_at.
4. Broker Integration reads order.created, invokes broker POST /orders, and changes the order state to PENDING.
5. The Status Poller regularly invokes broker GET /orders/{id}, records the returned state, and removes completed orders from the ZSET.
6. The Deadline Scheduler searches the ZSET for due orders, then uses broker DELETE /orders/{id} to cancel them.

Why This Works

1. Postgres stores durable and consistent order records.
2. Redis ZSET supports efficient range lookups for deadline-based expiration processing.
3. A message queue separates spiky broker activity from client request handling.
4. Separate polling and scheduling services can each be scaled on their own.

Apply the outbox pattern so saving an order and emitting its event occur atomically. This avoids losing events if a process crashes.

Phase 5: Scaling and Trade-offs

Handling Deadline Spikes

Approach:

1. Divide Deadline Scheduler work by a hash of order_id so the load is distributed.
2. Read soon-to-expire orders through a rolling interval, such as from the current time through the next 60 seconds.
3. Use a worker pool with a firm cancellation rate limit so the broker is not overwhelmed.
4. Spread cancellation timing with a few seconds of jitter rather than issuing every cancel at one instant.

Broker API Failures

1. Put a circuit breaker around broker requests, with quick failure behavior and a retry queue.
2. Route repeatedly unsuccessful work to a dead-letter queue that can be replayed manually.
3. Stop accepting new order requests when the broker's error rate crosses a configured threshold.

Avoid retrying cancellation requests forever. During a broker outage, unlimited retries can overwhelm the broker and delay recovery.

Consistency Model

• Local state converges eventually with the broker's state.
• The broker is authoritative for an order's final outcome.
• An hourly reconciliation process rechecks and synchronizes stale orders.

Polling Strategy

• Adjust polling frequency according to remaining time before the deadline.
• High priority: under 1 minute remaining; check every 5 to 10 seconds.
• Medium priority: 1 to 5 minutes remaining; check every 20 seconds.
• Low priority: more than 5 minutes remaining; check every 60 seconds.

Data Scaling

• Split Orders into partitions based on creation date to support write-intensive traffic.
• Send status reads and analytics workloads to read replicas.
• Retain OrderEvent as an append-only log for auditing and replay.

Trade-offs

Common Pitfalls

Omitting idempotency can create duplicate orders when clients retry. Require a client idempotency key in every case.

Failing to account for partial fills can result in invalid cancellation attempts. Check the latest state immediately before issuing a cancellation.

Interview Checklist

• Confirmed functional requirements and the intended cancellation behavior.
• Calculated expected volume and the worst-case deadline burst.
• Specified a minimal schema along with an idempotency approach.
• Defined external APIs and internal event types.
• Described Redis ZSET-based deadline processing.
• Addressed broker outage scenarios and reconciliation.
• Covered polling rules and cancellation throttling.
• Called out key trade-offs and likely bottlenecks.

Summary