Bird
Raised Fist0

PACELC Theorem - Beyond CAP for Systems That Must Choose Under Latency

HLDmediumInterview freq: medium
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
PACELC Theorem - Beyond CAP for Systems That Must Choose Under Latency
Designing distributed systems with PACELC trade-offs for latency and consistency
mediumCore Distributed Systems ConceptsFreq: medium
⚙️
Functional Requirements
  • Support configurable consistency levels (strong, eventual, causal) per operation
  • Handle network partitions gracefully with defined trade-offs between availability and consistency
  • Optimize for low latency reads and writes under normal operation
  • Provide mechanisms to tune latency vs consistency trade-offs dynamically
  • Support multi-region geo-distributed deployment with replication
  • Expose metrics and logs to observe consistency and latency behavior
📊
Non-Functional Requirements
  • System must support 2 billion daily active users (DAU)
  • End-to-end operation latency P99 must be under 100ms in normal conditions
  • Availability SLA of 99.99% even during network partitions
  • Data durability with replication factor of 3 across regions
  • System must handle peak write throughput of 925K writes/sec
❓
Clarifying Questions to Ask
  • What is the expected network partition frequency and duration?
  • Are consistency requirements uniform or do they vary by operation or data type?
  • What is the expected read-to-write ratio?
  • Is latency more critical for reads or writes?
  • What are the geo-distribution requirements and number of regions?
  • Are there any existing systems or technologies to integrate with?
Out of Scope
✗ Designing specific consensus algorithms like Paxos or Raft in detail
✗ Implementing client-side conflict resolution logic
✗ Security and authentication mechanisms
✗ Detailed UI or frontend design
📌
Assumptions
  • 2 billion DAU
  • Each user generates 40 messages per day on average
  • Average message size is 100 bytes
  • Replication factor of 3 for durability
⚡
QPS Calculation
write qps2B × 40 / 86400 ≈ 925,926 writes/sec
peak write qpsAssuming 3× peak factor: 925,926 × 3 ≈ 2.78M writes/sec
read qpsAssuming 10 reads per write: 925,926 × 10 ≈ 9.26M reads/sec
💾
Storage Estimate
daily storage2B × 40 × 100 bytes = 8 TB/day uncompressed
retention days30
total storage8 TB × 30 = 240 TB
with replication240 TB × 3 = 720 TB total replicated storage
🖥️
Server Estimate
write pathKafka cluster with 100 brokers (each handles ~30K writes/sec)
storage nodesCassandra cluster with 200 nodes (each stores ~3.6 TB data with replication)
🏗️
Architecture Diagram
Architecture Diagram
       +------------+        +------------+        +-------------+
       |  Clients   |        |  API Gate- |        |  Consistency|
       | (Users/   |------->|   way      |------->|  Coordinator|
       |  Services) |        |  (Envoy)   |        | (Custom svc)|
       +------------+        +------------+        +-------------+
                                   |                      |
                                   v                      v
                            +------------+         +------------+
                            |  Kafka     |         |  Cassandra |
                            |  Cluster   |         |  Cluster   |
                            +------------+         +------------+
                                   |                      |
                                   v                      v
                            +------------+         +------------+
                            | Delivery   |         |  Metrics   |
                            | Workers    |         |  & Logging |
                            +------------+         +------------+
🧩
Components
API Gateway (Envoy)
Entry point for client requests, routes based on consistency and latency requirements
Why thisEnvoy supports dynamic routing and can inject headers to indicate consistency levels
Why notNginx lacks native support for dynamic routing based on request metadata and gRPC
Consistency Coordinator Service
Implements PACELC logic to decide consistency vs latency trade-offs per request
Why thisCustom microservice allows flexible policy enforcement and dynamic tuning of PACELC parameters
Why notUsing only Cassandra consistency levels is too coarse-grained and static
Kafka Cluster
Durable, partitioned write-ahead log for writes to enable asynchronous replication and ordering
Why thisKafka scales to millions of writes/sec with partitioning and supports exactly-once semantics
Why notRabbitMQ does not scale linearly to multi-million writes/sec and lacks strong ordering guarantees
Cassandra Cluster
Geo-distributed, eventually consistent storage with tunable consistency per query
Why thisCassandra supports multi-region replication, tunable consistency, and linear write scalability
Why notPostgreSQL requires manual sharding and does not scale linearly to 925K writes/sec
Delivery Workers
Consume Kafka topics to deliver messages asynchronously and update read models
Why thisStateless workers can scale horizontally and handle retries and backpressure efficiently
Why notSynchronous writes block clients and increase latency under load
Metrics & Logging
Collects telemetry on latency, consistency violations, and availability for monitoring and alerting
Why thisPrometheus + ELK stack provide real-time observability and historical analysis
Why notAd-hoc logging lacks structured metrics and alerting capabilities
🔄
Data Flow
1
Client → API Gateway
Send request with desired consistency and latency hints
Client specifies PACELC trade-off preferences
2
API Gateway → Consistency Coordinator
Route request and metadata for consistency decision
Coordinator applies PACELC logic to select read/write path
3
Consistency Coordinator → Kafka Cluster
Write messages asynchronously to Kafka partitions
Kafka ensures durable, ordered writes for replication
4
Delivery Workers → Cassandra Cluster
Consume Kafka and write to Cassandra with tunable consistency
Delivery workers update storage asynchronously to optimize latency

Practice

(1/5)
1. For a stock exchange system requiring low-latency order matching and high availability, which architecture is best suited to handle failover without losing in-flight orders?
medium
A. Use a distributed matching engine with partitioned order books per stock symbol and asynchronous replication
B. Use a single centralized matching engine with synchronous replication to a hot standby
C. Use multiple independent matching engines with eventual consistency and conflict resolution
D. Use a cloud-managed database with built-in failover and no dedicated matching engine

Solution

  1. Step 1: Analyze architecture requirements

    Low latency and high availability require partitioning to avoid bottlenecks and asynchronous replication to avoid blocking on failover.

  2. Step 2: Evaluate options

    Use a single centralized matching engine with synchronous replication to a hot standby blocks on synchronous replication causing latency; Use multiple independent matching engines with eventual consistency and conflict resolution risks conflicts and inconsistent order books; Use a cloud-managed database with built-in failover and no dedicated matching engine lacks dedicated matching engine causing latency and complexity.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Partitioned matching engine + async replication -> low latency + availability [check]
Hint: Partition and async replication for low latency failover [check]
Common Mistakes:
2. If the metrics aggregation service fails to update the error budget in real time, what is the most likely failure observed by the alerting system?
medium
A. Alerts trigger randomly due to inconsistent error count aggregation across nodes
B. Alerts never trigger because the error budget appears full and no burn rate is detected
C. Alerts trigger too frequently due to stale error budget values being reset to zero
D. Alerts show delayed notifications but eventually catch up after service recovery

Solution

  1. Step 1: Understand failure impact on error budget updates

    If aggregation service fails partially, inconsistent error counts across nodes cause alerting to behave erratically.

  2. Step 2: Eliminate other failure modes

    Resetting to zero (A) is unlikely without explicit reset; no alerts (B) implies total failure, not partial inconsistency; delayed alerts (D) imply buffering, not aggregation failure.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Aggregation failure -> inconsistent counts -> random alert triggers [check]
Hint: Aggregation failure causes inconsistent counts, leading to random alerts [OK]
Common Mistakes:
3. At 10x scale, which component is most likely to fail first due to stateful connection limits, and why?
hard
A. The chat servers, because WebSocket connections are stateful and cannot be resharded easily
B. The message queue, because partition count limits throughput
C. The database cluster, because query volume exceeds CPU capacity
D. The load balancer, because it cannot distribute traffic evenly at high scale

Solution

  1. Step 1: Identify stateful bottleneck

    Chat servers maintain WebSocket connections bound to server memory, limiting horizontal scaling and resharding.

  2. Step 2: Compare other components

    Database (A) can be scaled with sharding; message queue (C) partitions can be increased; load balancer (D) scales horizontally.

  3. Step 3: Explain failure mechanism

    WebSocket statefulness causes connection limits per server, leading to failure under 10x load.

  4. Final Answer:

    Option A -> Option A

  5. Quick Check:

    Stateful WebSocket limits -> chat servers fail first at scale [check]
Hint: Stateful WebSockets limit scaling; stateless scale easier [check]
Common Mistakes:
4. At 10x scale, which component is most likely to become the bottleneck first when handling millions of concurrent video streams and progress updates, and why?
hard
A. The relational database storing user progress, due to write contention on user records
B. The WebSocket servers maintaining live connections, due to stateful connection limits
C. The Progress Worker service, due to single-threaded processing of progress update events
D. The CDN edge servers, due to bandwidth limits serving video content globally

Solution

  1. Step 1: Analyze stateful connection scaling

    WebSocket servers maintain stateful connections per user, limiting horizontal scaling due to connection affinity.

  2. Step 2: Compare other components' scalability

    Relational DB (The relational database storing user progress, due to write contention on user records) can be sharded; CDN (The CDN edge servers, due to bandwidth limits serving video content globally) scales horizontally; Progress Worker (The Progress Worker service, due to single-threaded processing of progress update events) can be parallelized.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    WebSocket servers hit stateful connection limits first [check]
Hint: Stateful WebSocket servers limit scaling first [OK]
Common Mistakes:
5. At 10x scale, which component in an async messaging chat system fails first and why?
hard
A. The database, because increased writes cause lock contention
B. The message queue brokers, due to partition leader overload
C. The chat servers, because WebSocket connections are stateful and cannot be resharded easily
D. The delivery workers, because retry queues grow exponentially

Solution

  1. Step 1: Analyze stateful components and scaling challenges

    Databases (The database, because increased writes cause lock contention) can be scaled with sharding and replicas. Message queue brokers (The message queue brokers, due to partition leader overload) scale horizontally with partitions. Delivery workers (The delivery workers, because retry queues grow exponentially) can be scaled with backpressure.

  2. Step 2: Identify chat servers as stateful WebSocket connection holders

    Chat servers maintain persistent WebSocket connections bound to server memory, making resharding or migration difficult at scale.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Stateful WebSocket servers -> first bottleneck at 10x scale [check]
Hint: Stateful WebSocket servers limit horizontal scaling first [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