Bird
Raised Fist0

Design a Stock Exchange - Order Book, Matching Engine, Market Data Feed

HLDhardInterview freq: medium
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
Design a Stock Exchange - Order Book, Matching Engine, Market Data Feed
Design a high-throughput, low-latency stock exchange system with order book, matching engine, and market data feed
hardFinancial and Real-Time SystemsFreq: medium
Prerequisites:Order BookMatching Engine
⚙️
Functional Requirements
  • Accept and process limit and market orders for multiple stock symbols concurrently.
  • Maintain a real-time order book per stock symbol with price-time priority sorting.
  • Match buy and sell orders in the matching engine with atomicity and consistency guarantees.
  • Publish real-time market data feed including order book snapshots and trade executions to subscribers.
  • Support order amendments and cancellations with immediate effect on the order book and matching engine.
  • Provide APIs for order submission, cancellation, and market data subscription.
📊
Non-Functional Requirements
  • System must handle at least 2 billion daily active users (DAU) with an average of 40 orders/messages per user per day.
  • End-to-end order processing latency must be under 100ms P99 to meet market fairness requirements.
  • System availability must be 99.99% to avoid trading disruptions.
  • Market data feed must have sub-50ms latency from order execution to subscriber delivery.
  • Data durability with replication and retention for at least 30 days for audit and compliance.
❓
Clarifying Questions to Ask
  • What is the expected peak orders per second (write QPS) and peak market data feed subscribers (read QPS)?
  • Are orders strictly limit and market types or do we support advanced types like stop-loss?
  • What consistency guarantees are required between order book state and matching engine?
  • Is the system expected to support multiple geographic regions or a single data center?
  • What is the expected retention period for order and trade data?
  • Are there SLAs for order cancellation and amendment latencies?
Out of Scope
✗ Clearing and settlement systems post-trade.
✗ User authentication and authorization mechanisms.
✗ Regulatory reporting and compliance beyond data retention.
✗ Support for derivatives or complex order types like options or futures.
📌
Assumptions
  • 2 billion DAU placing 40 orders/messages per user per day.
  • Average order message size is 100 bytes.
  • Peak trading hours generate 10x average QPS.
  • Retention period for order and trade data is 30 days with 3x replication.
⚡
QPS Calculation
write qps2B × 40 / 86400 ≈ 925,926 writes/sec
peak write qps925,926 × 10 = 9,259,260 writes/sec
read qpsAssuming 10M subscribers each receiving 10 updates/sec = 100M reads/sec
💾
Storage Estimate
daily storage925,926 writes/sec × 100 bytes × 86400 sec ≈ 8 TB/day
retention storage8 TB/day × 30 days = 240 TB
with replication240 TB × 3 replicas = 720 TB total storage
🖥️
Server Estimate
order ingestionKafka cluster with 50 brokers, each handling ~200K writes/sec to support 9.25M peak writes/sec
matching engineCluster of 100 low-latency servers with FPGA acceleration or high-performance CPUs to process 9.25M orders/sec with <100ms latency
🏗️
Architecture Diagram
Architecture Diagram
          +----------------------+
          |  Client Order Submit  |
          +----------+-----------+
                     |
                     v
          +----------------------+
          | Kafka Order Ingestor  |
          | (Apache Kafka 3.0)    |
          +----------+-----------+
                     |
                     v
          +----------------------+
          | Matching Engine       |
          | (Custom C++ Service)  |
          +----------+-----------+
                     |
                     v
          +----------------------+
          | Order Book Store      |
          | (Apache Cassandra)    |
          +----------+-----------+
                     |
                     v
          +----------------------+
          | Market Data Publisher |
          | (Apache Pulsar)       |
          +----------+-----------+
                     |
                     v
          +-----------------------+
          | Market Data Subscribers|
          +-----------------------+
🧩
Components
Kafka Order Ingestor
Ingests all incoming order messages reliably and durably with partitioning by stock symbol
Why thisApache Kafka 3.0 provides high-throughput, partitioned, durable log with exactly-once semantics and strong ordering guarantees per partition
Why notRabbitMQ lacks Kafka's throughput and partitioning scale; Redis Streams does not guarantee durable storage at this scale
Matching Engine
Processes orders from Kafka, matches buy and sell orders atomically, updates order book state
Why thisCustom C++ service optimized for low-latency, single-threaded event processing with lock-free data structures to meet <100ms P99 latency
Why notGeneral-purpose databases or JVM-based services introduce GC pauses and higher latency unsuitable for real-time matching
Order Book Store
Stores persistent order book state and trade history with fast read/write for multiple stock symbols
Why thisApache Cassandra offers linear write scalability, tunable consistency, and time-series data model suitable for high write QPS and retention
Why notPostgreSQL requires complex manual sharding at 9M writes/sec; B-tree writes do not scale linearly
Market Data Publisher
Publishes real-time market data feed (order book snapshots, trades) to subscribers with low latency
Why thisApache Pulsar supports multi-tenant, geo-replicated, low-latency pub-sub with message retention and backpressure handling
Why notKafka lacks native support for low-latency fan-out to millions of subscribers and geo-replication at this scale
Market Data Subscribers
Consume real-time market data feed for trading clients, brokers, and analytics
Why thisClients use WebSocket or gRPC streaming to receive sub-50ms latency updates from Pulsar topics
Why notPolling REST APIs introduce high latency and load; MQTT lacks enterprise-grade scalability for millions of subscribers
🔄
Data Flow
1
Client Order Submit → Kafka Order Ingestor
Client submits order via API; order serialized and published to Kafka topic partitioned by stock symbol
Partitioning ensures order sequence per symbol for matching engine
2
Kafka Order Ingestor → Matching Engine
Matching engine consumes orders from Kafka partitions, processes matching logic atomically
Single-threaded processing per partition ensures order consistency and low latency
3
Matching Engine → Order Book Store
Matching engine updates order book state and trade history in Cassandra with tunable consistency
Writes are idempotent to handle retries without inconsistency
4
Matching Engine → Market Data Publisher
Matching engine publishes trade executions and order book snapshots to Pulsar topics
Market data feed is partitioned by stock symbol for scalability
5
Market Data Publisher → Market Data Subscribers
Subscribers receive real-time updates via WebSocket or gRPC streaming
Backpressure and message retention handled by Pulsar to ensure delivery guarantees

Practice

(1/5)
1. In a system where a client writes a user profile update to DynamoDB, then a cache invalidation message is sent to Redis at step 4, what happens if the cache invalidation fails at step 4?
easy
A. DynamoDB write is rolled back automatically to maintain consistency
B. Redis automatically retries invalidation and blocks client until success
C. The cache remains stale until TTL expires or manual refresh
D. Client receives an error and retries the entire update operation

Solution

  1. Step 1: Trace cache invalidation at step 4

    Cache invalidation is asynchronous and best-effort; failure does not rollback DB writes.

  2. Step 2: Understand failure impact on cache state

    If invalidation fails, Redis cache remains stale until TTL expiry or next explicit refresh.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Failed cache invalidation -> stale cache until TTL or manual refresh [check]
Hint: Failed cache invalidation -> stale cache, DB write persists [check]
Common Mistakes:
2. A public API receives millions of requests per minute from diverse clients. To prevent abuse, which layer should primarily enforce a global rate limit that blocks excessive requests before reaching internal services?
easy
A. Apply rate limiting exclusively inside each microservice to control business logic
B. Implement rate limiting only at the database layer to prevent overload
C. Enforce rate limiting at the API Gateway to block abusive traffic early
D. Use client-side rate limiting to reduce server load

Solution

  1. Step 1: Identify the role of API Gateway

    The API Gateway acts as the first entry point and can block abusive traffic before it reaches internal services or databases.

  2. Step 2: Evaluate other layers

    Database-level rate limiting is too late and risks overload; service-level limits are per-service and don't prevent global abuse; client-side limits are unreliable as clients can be malicious.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    API Gateway blocks abusive requests early [check]
Hint: Block abusive traffic earliest at API Gateway [check]
Common Mistakes:
3. In a system where a stateless API Gateway forwards requests to stateful backend services, at step 4 the backend service checks the user's session cache. What happens if the session cache has expired?
easy
A. The backend service fetches session data from a centralized session store before processing
B. The backend service rejects the request immediately with an authentication error
C. The API Gateway retries the request to a different backend service
D. The backend service creates a new session and processes the request as a guest

Solution

  1. Step 1: Trace backend session cache check

    If session cache expired, backend must retrieve fresh session data to maintain stateful context.

  2. Step 2: Understand fallback mechanism

    Fetching from centralized session store ensures consistent session state before processing request.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Expired cache triggers centralized session fetch -> consistent state [check]
Hint: Expired cache -> fetch centralized session before processing [check]
Common Mistakes:
4. If the Bloom filter component is removed from a Cassandra-like system, what exact failure occurs during a read request for a non-existent key?
medium
A. The system returns stale data from cache without checking disk
B. Every read request for a non-existent key triggers a costly disk lookup, increasing latency and load
C. Writes block until the Bloom filter is rebuilt, causing backpressure
D. The system incorrectly returns key-not-found errors for existing keys due to missing filters

Solution

  1. Step 1: Understand Bloom filter role in reads

    Bloom filters prevent unnecessary disk reads for non-existent keys but do not affect correctness of existing keys.

  2. Step 2: Trace failure without Bloom filters

    Without Bloom filters, reads for non-existent keys cause disk lookups, increasing latency but do not cause incorrect key-not-found errors for existing keys; however, missing Bloom filters can cause stale data to be returned if caching is mismanaged.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Removing Bloom filters risks incorrect key-not-found errors due to stale cache [check]
Hint: No Bloom filter -> stale cache causes wrong misses [check]
Common Mistakes:
5. At 10x scale, which component is most likely to become the bottleneck first in the typeahead system, and why?
hard
A. The front-end API servers, because they cannot handle the increased number of concurrent connections
B. The personalization data store, because user profile reads increase linearly and cannot be sharded easily
C. The ranking service, because ranking computations grow exponentially with candidate suggestions
D. The Trie cache servers, because maintaining low-latency prefix lookups requires large in-memory state that is hard to shard further

Solution

  1. Step 1: Analyze component scalability

    Personalization stores can be sharded; ranking computations scale linearly; front-end servers can be horizontally scaled.

  2. Step 2: Identify Trie cache bottleneck

    Trie caches hold large in-memory prefix trees; sharding by prefix has limits due to prefix overlap and memory footprint, causing latency and memory bottlenecks.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Trie cache memory and shard limits -> first bottleneck at 10x scale [check]
Hint: Trie cache memory limits cause first bottleneck at scale [check]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard