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
45 min · senior
senior

Design a stock exchange system supporting 50 million daily active users with peak order rates of 1 million orders per second. The system must maintain strict order matching guarantees, provide real-time market data feeds with P99 latency under 200ms, and ensure data encryption at rest and in transit. The exchange operates globally with multiple trading instruments and requires fault tolerance and auditability for regulatory compliance.

Constraints
  • End-to-end encryption of orders and market data (TLS + at-rest encryption)
  • P99 end-to-end latency under 200ms for order matching and market data dissemination
  • Support for 1 million orders per second peak write throughput
  • Strong consistency for order matching to prevent double execution or lost orders
  • Audit logs must be immutable and replayable for regulatory compliance
📋
Guided Steps
1/5
Step 1
Order Ingestion and Validation
How would you design the order ingestion pipeline to handle 1 million orders per second with low latency and strong validation?
💡 Hint
Consider a distributed messaging system that partitions orders by instrument to maintain order and parallelism.
Key Decision
Use Apache Kafka with instrument symbol as the partition key to ensure order affinity and horizontal scalability for ingestion.
Interviewer Expectation
Mid: Names Kafka for ingestion. Senior: Explains partitioning by instrument symbol to guarantee order within an instrument and enable parallel processing.
⚠️Common Wrong Answer
Using a single centralized queue or database for ingestion, causing a bottleneck and increased latency under high load.
Step 2
Order Book and Matching Engine Design
How will you design the order book and matching engine to guarantee strong consistency and low latency matching?
💡 Hint
Think about in-memory data structures combined with persistent logs and how to partition matching by instrument.
Key Decision
Implement per-instrument matching engines using in-memory data structures (e.g., C++ or Rust) with write-ahead logs stored in Apache BookKeeper for durability and replay.
Interviewer Expectation
Mid: Describes in-memory matching engine. Senior: Details per-instrument partitioning, use of BookKeeper for durable logs, and how this supports fault recovery and strong consistency.
⚠️Common Wrong Answer
Using a relational database for matching logic causing high latency and locking contention.
Step 3
Market Data Feed Architecture
How would you design the market data feed to deliver real-time order book updates and trades with P99 latency under 200ms?
💡 Hint
Consider a publish-subscribe system optimized for low latency and high fan-out with backpressure handling.
Key Decision
Use Apache Pulsar with topic partitioning by instrument and tiered storage to deliver real-time market data with low latency and durability.
Interviewer Expectation
Mid: Names a pub-sub system like Pulsar or Kafka. Senior: Explains topic partitioning by instrument, use of Pulsar’s low-latency features, and backpressure mechanisms to maintain SLA.
⚠️Common Wrong Answer
Using HTTP polling for market data causing excessive load and latency spikes.
Step 4
Data Encryption and Compliance
How will you ensure encryption at rest and in transit, and maintain immutable audit logs for regulatory compliance?
💡 Hint
Think about TLS for transport and encryption features of storage systems plus append-only logs for auditability.
Key Decision
Enforce TLS 1.3 for all client-server and inter-service communication; use Apache BookKeeper with server-side encryption for write-ahead logs; store audit logs in Apache HDFS with immutable append-only files.
Interviewer Expectation
Mid: Mentions TLS and encryption. Senior: Details TLS 1.3, server-side encryption in BookKeeper, immutable HDFS audit logs, and replayability for compliance audits.
⚠️Common Wrong Answer
Relying only on network-level encryption without encrypting data at rest, risking data leaks and non-compliance.
Step 5
API Design for Client Interaction
Design 3 core API endpoints: order submission, order status query, and market data subscription. What protocols and data formats would you choose?
💡 Hint
Consider gRPC or REST for order submission/status and WebSocket or gRPC streaming for market data.
Key Decision
Use gRPC with protobuf for order submission and status queries to ensure low latency and strong typing; use WebSocket with JSON or protobuf streaming for market data subscription to support real-time push.
Interviewer Expectation
Mid: Suggests REST or gRPC for APIs. Senior: Explains gRPC benefits for low latency, protobuf for compactness, and WebSocket for efficient real-time streaming.
⚠️Common Wrong Answer
Using only REST with HTTP polling for market data, causing high latency and scalability issues.
🔌
API Design Challenge
Sketch 3 core API endpoints for the stock exchange system: order submission, order status query, and market data subscription.
Hints
  • How does the client submit new orders and receive acknowledgments?
  • How can clients query the status of their orders efficiently?
  • How is real-time market data pushed or streamed to subscribers?
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Use of partitioned distributed messaging system (Kafka) keyed by instrument symbol for order ingestion
  • In-memory matching engine with durable write-ahead logs (BookKeeper) for strong consistency and fault tolerance
  • Low latency pub-sub system (Pulsar) for market data feed with partitioning and backpressure
  • Encryption in transit (TLS 1.3) and at rest (BookKeeper server-side encryption)
  • API design using gRPC for order submission/status and WebSocket for market data streaming
Good to Have - 30%
  • Immutable audit logs stored in HDFS for regulatory compliance and replayability
  • Clear partitioning strategy across components for scalability and fault isolation
  • Use of protobuf for compact and strongly typed API payloads
Bonus - 10%
  • Discussion of failure modes and recovery strategies for matching engine crashes
  • Consideration of multi-region deployment and latency optimization
  • Use of backpressure and flow control in market data feed to maintain SLA
Anti-patterns to Avoid
Single centralized queue or database for order ingestion causing bottlenecks and increased latency under high load, which limits scalability and increases latency.
Using relational databases for matching engine leading to locking contention and slow matching, resulting in high latency and potential order processing delays.
HTTP polling for market data feed causing excessive load and latency spikes due to frequent reconnects and redundant data transfer, which can collapse the system under high user load.
Encrypting only in transit without encrypting data at rest risks data leaks and non-compliance with regulatory requirements.
✅
Model Answer
▼ Reveal

This design outlines a scalable, low-latency stock exchange system supporting 50M DAU and 1M orders/sec peak. It uses partitioned Kafka for order ingestion, per-instrument in-memory matching engines with durable logs in BookKeeper, and Pulsar for real-time market data feeds. TLS 1.3 ensures encryption in transit; server-side encryption and immutable audit logs in HDFS ensure compliance. APIs use gRPC with protobuf for order submission/status and WebSocket streaming for market data.

Key Decisions
  • Partition orders by instrument symbol in Kafka to maintain order and enable horizontal scaling
  • Use in-memory matching engines per instrument for low latency with durable logs in BookKeeper for fault tolerance and replay
  • Employ Apache Pulsar for market data feed to achieve low latency, high fan-out, and backpressure handling
  • Enforce TLS 1.3 for all network communication and server-side encryption in BookKeeper for data at rest
  • Store immutable audit logs in HDFS with append-only files to meet regulatory compliance and enable replay
  • Design APIs with gRPC and protobuf for efficient, strongly typed communication and WebSocket streaming for real-time market data
  • Apache Kafka with instrument symbol as partition key to scale order ingestion and maintain order
  • In-memory matching engine per instrument with durable write-ahead logs in Apache BookKeeper for fault tolerance
  • Apache Pulsar for real-time market data feed with topic partitioning and backpressure control
  • TLS 1.3 enforced for all network communication ensuring encryption in transit
  • Server-side encryption in BookKeeper and immutable audit logs stored in Apache HDFS for compliance
  • gRPC with protobuf for order submission and status APIs enabling low latency and strong typing
  • WebSocket streaming for market data subscription to support real-time push with minimal overhead
  • Partitioning by instrument symbol across all components to enable horizontal scalability and fault isolation

Practice

(1/5)
1. In a file storage system, at step 3 the client requests a file write. What happens inside the metadata server at this step?
easy
A. The metadata server sends the file data to object storage for persistence.
B. The metadata server writes the file data blocks directly to disk.
C. The metadata server updates the file's inode and directory entries to reflect the new write.
D. The metadata server caches the entire file in memory without updating disk metadata.

Solution

  1. Step 1: Understand metadata server role in file write

    The metadata server manages file metadata like inodes and directory entries, not the actual data blocks.

  2. Step 2: Trace what happens at step 3

    On a write request, the metadata server updates the inode and directory metadata to reflect changes; data blocks are handled separately by storage nodes.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Metadata server updates inode, not data blocks [check]
Hint: Metadata server updates metadata, not file data blocks [check]
Common Mistakes:
2. A hotel booking system must prevent double bookings when multiple users try to reserve the same room simultaneously. Which component is best suited to enforce this constraint reliably?
easy
A. Use a distributed lock service like ZooKeeper to coordinate reservation attempts
B. Use a relational database with unique constraints on room and date columns to prevent duplicates
C. Use an eventually consistent NoSQL store with last-write-wins conflict resolution
D. Use client-side validation to check room availability before submitting reservations

Solution

  1. Step 1: Identify the need for strong coordination

    Preventing double booking requires distributed synchronization to ensure only one reservation succeeds for a room at a given time.

  2. Step 2: Evaluate coordination mechanisms

    Relational DB unique constraints (Use a relational database with unique constraints on room and date columns to prevent duplicates) can help but may cause high contention and deadlocks at scale. NoSQL with last-write-wins (Use an eventually consistent NoSQL store with last-write-wins conflict resolution) allows conflicts and can cause double bookings. Client-side validation (Use client-side validation to check room availability before submitting reservations) is unreliable due to race conditions. Distributed lock service (Use a distributed lock service like ZooKeeper to coordinate reservation attempts) provides strong consistency and coordination across distributed components.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Distributed locks coordinate concurrent reservations reliably [check]
Hint: Distributed locks ensure exclusive access to shared resources [check]
Common Mistakes:
3. In a rate limiting system, at Step 3 the Service Layer checks the user's request count against its local cache. What happens if the cache TTL expires before the database updates the count?
easy
A. The service rejects all requests until the cache refreshes
B. The service allows requests assuming zero usage, risking over-limit breaches
C. The service blocks requests permanently due to stale data
D. The service queries the database synchronously for every request

Solution

  1. Step 1: Understand cache TTL impact

    When the cache expires, the service assumes no prior usage until refreshed, allowing requests that may exceed limits.

  2. Step 2: Evaluate other options

    Rejecting all requests or blocking permanently is too harsh; synchronous DB queries per request cause latency and overload.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Expired cache -> assume zero usage -> risk over-limit [check]
Hint: Expired cache means zero usage assumed, risking breaches [check]
Common Mistakes:
4. For a global web service requiring low latency and high availability, which load balancing strategy is best suited to handle user requests across multiple data centers?
medium
A. Use DNS round-robin to distribute requests evenly across data centers
B. Use a global load balancer with health checks and geo-routing capabilities
C. Use client-side load balancing with hardcoded server IPs in the client app
D. Use a single centralized load balancer in one data center to route all traffic

Solution

  1. Step 1: Evaluate DNS round-robin limitations

    DNS round-robin (Use DNS round-robin to distribute requests evenly across data centers) lacks real-time health checks and can send traffic to unhealthy data centers, causing poor availability.

  2. Step 2: Assess global load balancer benefits

    A global load balancer (Use a global load balancer with health checks and geo-routing capabilities) performs health checks and routes users to the nearest healthy data center, optimizing latency and availability.

  3. Step 3: Consider client-side and centralized load balancing drawbacks

    Client-side load balancing (Use client-side load balancing with hardcoded server IPs in the client app) is hard to update and lacks global awareness. A single centralized load balancer (Use a single centralized load balancer in one data center to route all traffic) creates a single point of failure and latency bottleneck.

  4. Final Answer:

    Option B -> Option B

  5. Quick Check:

    Global load balancer with geo-routing optimizes latency and availability [check]
Hint: Global load balancer routes by health and geography [check]
Common Mistakes:
5. At 10x scale, which component in your design explanation is most likely to fail first due to stateful connection bottlenecks, and why?
hard
A. Stateful WebSocket servers because connections are bound to server memory and cannot be easily resharded
B. Stateless API servers because CPU usage spikes with more requests
C. Load balancers because they cannot handle increased DNS queries
D. Databases because they run out of disk space first

Solution

  1. Step 1: Identify stateful components at scale

    WebSocket servers maintain persistent connections bound to server memory, limiting horizontal scaling.

  2. Step 2: Compare with stateless components

    Stateless API servers and load balancers scale horizontally more easily; databases fail later due to storage.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Stateful WebSocket servers bottleneck first due to connection affinity [check]
Hint: Stateful WebSocket servers bottleneck first 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