Bird
Raised Fist0

CAP Theorem - Consistency, Availability, Partition Tolerance in Real Systems

HLDmediumInterview freq: high
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
CAP Theorem - Consistency, Availability, Partition Tolerance in Real Systems
Designing distributed systems by balancing Consistency, Availability, and Partition Tolerance under real-world constraints
mediumCore Distributed Systems ConceptsFreq: high
⚙️
Functional Requirements
  • Support strong consistency guarantees for critical operations (e.g., financial transactions)
  • Provide high availability for read and write operations during network partitions
  • Ensure partition tolerance to handle network failures without total system downtime
  • Allow configurable consistency levels (e.g., strong, eventual) per use case
  • Expose system health and partition detection metrics for monitoring
  • Support multi-region deployment with geo-replication
📊
Non-Functional Requirements
  • Support 2 billion daily active users (DAU)
  • Handle peak write throughput of approximately 925K writes per second
  • Achieve 99.99% availability SLA
  • Maintain 100ms P99 latency for read and write operations
  • Data durability with replication factor of 3 across data centers
❓
Clarifying Questions to Ask
  • What is the expected read-to-write ratio for the system?
  • Are there specific operations that require strict consistency versus eventual consistency?
  • What is the maximum tolerable downtime or data loss during partitions?
  • Is multi-region geo-replication mandatory or optional?
  • What is the expected message or data size per operation?
  • Are there existing technologies or platforms mandated or preferred?
Out of Scope
✗ Designing specific application-level business logic
✗ Security and authentication mechanisms
✗ Client-side caching strategies
✗ Detailed network infrastructure design
📌
Assumptions
  • 2 billion DAU
  • Each user generates 40 messages/operations per day
  • Average message size is 100 bytes
  • Replication factor is 3 for durability
⚡
QPS Calculation
write qps2,000,000,000 × 40 / 86,400 ≈ 925,926 writes/sec
peak write qpsAssuming 3× peak factor: 925,926 × 3 ≈ 2,777,778 writes/sec
read qpsAssuming read-to-write ratio 5:1: 925,926 × 5 ≈ 4,629,630 reads/sec
💾
Storage Estimate
daily storage2,000,000,000 × 40 × 100 bytes = 8,000,000,000,000 bytes ≈ 7.28 TB/day
retention days30
total storage7.28 TB × 30 = 218.4 TB
with replication218.4 TB × 3 = 655.2 TB total replicated storage
🖥️
Server Estimate
write pathKafka cluster with 100 brokers, each handling ~30K writes/sec
storage nodesCassandra cluster with 200 nodes, each storing ~3.3 TB data with replication
🏗️
Architecture Diagram
Architecture Diagram
          +----------------------+
          |      Clients         |
          +----------+-----------+
                     |
          +----------v-----------+
          |  Load Balancer (NGINX)|
          +----------+-----------+
                     |
          +----------v-----------+
          |  API Gateway (Envoy) |
          +----------+-----------+
                     |
          +----------v-----------+
          |  Write Path: Kafka    |
          |  (Partitioned Topics) |
          +----------+-----------+
                     |
          +----------v-----------+
          |  Storage: Cassandra   |
          |  (Replicated, Tuned) |
          +----------+-----------+
                     |
          +----------v-----------+
          |  Read Path: Cassandra |
          +----------+-----------+
                     |
          +----------v-----------+
          |  Cache Layer: Redis   |
          +----------------------+
🧩
Components
Kafka
Durable distributed log for write operations, enabling partition tolerance and asynchronous replication
Why thisKafka partitions data by key, supports high throughput (millions of writes/sec), and provides strong durability guarantees with configurable replication
Why notRabbitMQ lacks Kafka's horizontal scalability and partitioning, limiting throughput beyond 100K writes/sec
Cassandra
Distributed NoSQL database for storing and serving data with tunable consistency levels
Why thisCassandra supports multi-region replication, tunable consistency (QUORUM, ALL), and linear horizontal scalability to handle petabytes of data
Why notPostgreSQL requires manual sharding and does not scale linearly at 2.7M writes/sec; B-tree writes cause hotspots
Redis
In-memory cache layer to reduce read latency and offload Cassandra for hot keys
Why thisRedis supports TTL natively, sub-millisecond lookups, and pub/sub for cache invalidation, improving read P99 latency
Why notMemcached lacks native TTL and pub/sub, complicating cache invalidation and stale data handling
Load Balancer (NGINX)
Distributes client requests evenly across API gateway instances to ensure availability and fault tolerance
Why thisNGINX supports high concurrency, health checks, and SSL termination with low latency
Why notHAProxy is performant but NGINX offers better integration with HTTP/2 and gRPC protocols used by clients
API Gateway (Envoy)
Handles client authentication, routing, and enforces consistency level per request
Why thisEnvoy supports dynamic routing, retries, circuit breaking, and observability, enabling fine-grained control over consistency and availability trade-offs
Why notCustom proxies lack Envoy's ecosystem and observability, increasing operational complexity at scale
🔄
Data Flow
1
Client → Load Balancer
Client sends read/write request
Load balancer distributes requests to API gateway instances
2
Load Balancer → API Gateway
Forward request with consistency level metadata
API Gateway enforces consistency and routes accordingly
3
API Gateway → Kafka (write path)
Writes are appended to Kafka topic partitions
Kafka ensures partition tolerance and durability
4
Kafka → Cassandra
Kafka consumers asynchronously write data to Cassandra
Cassandra stores data with tunable consistency
5
Client → API Gateway (read path)
Read requests routed to Cassandra or Redis cache
Reads served from Redis cache if available, else Cassandra
6
Cassandra → Redis
Cache updated asynchronously on writes
Cache invalidation ensures consistency with TTL
7
API Gateway → Client
Response returned with requested consistency guarantees
Latency optimized by caching and partitioning

Practice

(1/5)
1. A system needs to quickly check membership of millions of items with minimal memory and can tolerate some false positives but no false negatives. Which component best handles this requirement?
easy
A. A simple hash set stored in memory
B. A relational database with indexed lookups
C. A distributed cache with strong consistency guarantees
D. A Bloom filter implemented with multiple hash functions and a bit array

Solution

  1. Step 1: Identify membership check requirements

    The system requires fast membership queries with minimal memory and can tolerate false positives but not false negatives.

  2. Step 2: Match component capabilities

    Bloom filters use multiple hash functions and a bit array to provide space-efficient membership checks with false positives but no false negatives, fitting the scenario.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Bloom filter trades memory for false positives, no false negatives [check]
Hint: Bloom filters trade memory for false positives [check]
Common Mistakes:
2. A system must track millions of concurrent video playbacks and update user progress in near real-time without blocking the video stream. Which component is best suited to handle progress updates asynchronously?
easy
A. Use a message queue to buffer progress update events for asynchronous processing
B. Use a relational database with synchronous writes on every video event
C. Use a CDN edge cache to store progress state temporarily
D. Use client-side local storage exclusively to track progress

Solution

  1. Step 1: Identify asynchronous progress update requirement

    Relational DB synchronous writes (Use a relational database with synchronous writes on every video event) block video playback and don't scale well for millions of concurrent updates.

  2. Step 2: Evaluate buffering and decoupling

    Message queue (Use a message queue to buffer progress update events for asynchronous processing) decouples video playback from progress persistence, enabling scalable asynchronous processing.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Message queue buffers progress updates for async processing [check]
Hint: Buffer updates asynchronously with message queue [OK]
Common Mistakes:
3. In the photo feed generation flow, at step 4 the Feed Worker fetches stories from the Stories Service cache. What happens if the cache TTL for a user's stories has expired at this step?
easy
A. The Feed Worker asynchronously refreshes the cache but returns an empty stories section immediately
B. The Feed Worker triggers a synchronous fetch from the Stories DB and blocks until fresh stories are retrieved
C. The Feed Worker returns stale stories from a backup cache without fetching fresh data
D. The Feed Worker skips stories for that user and proceeds with only photo posts in the feed

Solution

  1. Step 1: Trace Feed Worker behavior at cache miss

    When TTL expires, the cache is stale. The Feed Worker must avoid blocking feed generation.

  2. Step 2: Understand asynchronous cache refresh

    To maintain low latency, the Feed Worker returns empty stories immediately and triggers async cache refresh. Blocking fetch (B) would increase latency. Returning stale data (A) risks outdated content. Skipping stories silently (C) loses user experience.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Async cache refresh avoids blocking feed generation [check]
Hint: Async cache refresh avoids blocking feed generation [OK]
Common Mistakes:
4. A load balancer must detect unhealthy backend servers and reroute traffic without client impact. Which component is primarily responsible for detecting server health status?
easy
A. Health check module that periodically probes backend servers
B. Client-side retry logic to avoid failed servers
C. Load balancer's session persistence cache to track server availability
D. DNS resolver that removes unhealthy servers from DNS responses

Solution

  1. Step 1: Identify health detection responsibility

    The health check module actively probes backend servers to determine their health status.

  2. Step 2: Eliminate other options

    DNS resolver changes are slow and indirect; session persistence caches track sessions, not health; client-side retries do not detect server health.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Health check module probes servers directly for health [check]
Hint: Health checks probe servers directly to detect failures [check]
Common Mistakes:
5. For a system launching with unpredictable hot keys, which cache warming strategy balances freshness and resource usage best?
medium
A. Use a hybrid approach combining historical access logs with real-time monitoring to selectively warm keys
B. Preload all possible keys regardless of traffic patterns to ensure zero misses
C. Only warm keys that were hot in the previous launch period, ignoring recent changes
D. Rely solely on lazy loading to avoid unnecessary warming overhead

Solution

  1. Step 1: Analyze warming strategies for unpredictable hot keys

    Hybrid approach uses historical and real-time data to adaptively warm relevant keys.

  2. Step 2: Eliminate extremes

    Preloading all keys wastes resources; ignoring recent changes misses new hot keys; lazy loading causes latency.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Hybrid warming adapts to traffic changes balancing freshness and cost [check]
Hint: Hybrid warming adapts to traffic changes balancing freshness and cost [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