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

You are designing a globally distributed messaging system for a startup with 50 million daily active users (DAU). The system must deliver messages with P99 latency under 200ms, ensure end-to-end encryption, and support offline message delivery. Network partitions are expected due to global scale. Your design must explicitly address the CAP theorem trade-offs and justify consistency, availability, and partition tolerance choices.

Constraints
  • End-to-end encryption mandatory for all messages
  • Offline message delivery with guaranteed eventual consistency
  • P99 message delivery latency under 200ms
  • Global distribution with expected network partitions
  • Support for 50 million DAU with peak message throughput ~1 million msg/sec
📋
Guided Steps
1/5
Step 1
Choosing the Data Store and Partitioning Strategy
Which database technology and partition key will you choose to balance consistency and availability under partitions?
💡 Hint
Consider a distributed NoSQL store with tunable consistency and partition keys that enable ordered message retrieval.
Key Decision
Use Apache Cassandra with partition_key=conversation_id to ensure all messages in a conversation are stored on the same node, enabling efficient range queries and tunable consistency levels.
Interviewer Expectation
Mid: Names Cassandra for scalability. Senior: Explains why conversation_id as partition key ensures ordered writes and range scans, and why sender_id partitioning causes out-of-order delivery.
⚠️Common Wrong Answer
Using sender_id as partition key causing messages to scatter across nodes, leading to out-of-order delivery and complex reconciliation.
Step 2
Handling Network Partitions and CAP Trade-offs
How will your system behave during network partitions? Which CAP property will you prioritize and why?
💡 Hint
Decide between strong consistency with reduced availability or eventual consistency with high availability during partitions.
Key Decision
Prioritize availability and partition tolerance by using Cassandra's eventual consistency with configurable consistency levels, enabling writes during partitions and reconciling conflicts asynchronously.
Interviewer Expectation
Mid: States availability over consistency during partitions. Senior: Explains how Cassandra's tunable consistency allows balancing read/write consistency and how conflict resolution is handled.
⚠️Common Wrong Answer
Choosing strong consistency with synchronous replication globally, causing high latency and unavailability during partitions.
Step 3
Ensuring End-to-End Encryption and Secure Message Delivery
How will you implement end-to-end encryption while maintaining system scalability and offline delivery?
💡 Hint
Consider client-side encryption and how encrypted payloads are stored and delivered without server-side decryption.
Key Decision
Implement client-side encryption with keys managed on clients; store encrypted blobs in Cassandra and deliver messages without server decryption, preserving privacy and enabling offline delivery.
Interviewer Expectation
Mid: Mentions encryption at rest and in transit. Senior: Details client-side encryption, key management, and how encrypted messages are stored and synchronized without server access to plaintext.
⚠️Common Wrong Answer
Encrypting only in transit or server-side encryption, exposing plaintext on servers and violating end-to-end encryption guarantees.
Step 4
Designing Message Delivery and Offline Synchronization
How will your system deliver messages with P99 < 200ms latency and support offline clients syncing messages upon reconnect?
💡 Hint
Use a message queue with partitioning aligned to conversation_id and a cursor-based sync mechanism for offline clients.
Key Decision
Use Apache Kafka with conversation_id as partition key for ordered message delivery and cursor-based offset sync for offline clients to efficiently catch up on missed messages.
Interviewer Expectation
Mid: Names Kafka for messaging. Senior: Explains partition key choice for ordering, how offset-based sync reduces data transfer, and how Kafka integrates with Cassandra for durability.
⚠️Common Wrong Answer
Using HTTP polling for offline sync causing excessive load and high latency at 50M DAU.
Step 5
API Design Reflecting CAP Trade-offs
Design 3 core API endpoints that reflect your CAP trade-offs and system design decisions.
💡 Hint
Include endpoints for sending encrypted messages, syncing offline messages, and acknowledging receipt to maintain consistency.
Key Decision
Define SendMessage (POST /messages) for encrypted message submission, SyncMessages (GET /messages?cursor=) for cursor-based offline sync, and AckMessage (POST /messages/{id}/ack) for client acknowledgments enabling conflict resolution.
Interviewer Expectation
Mid: Provides basic REST endpoints. Senior: Explains how each endpoint supports CAP trade-offs, encryption, and offline delivery with concrete request/response semantics.
⚠️Common Wrong Answer
Designing endpoints without support for offline sync or acknowledgments, leading to inconsistent state and poor user experience.
🔌
API Design Challenge
Sketch 3 core API endpoints for the messaging system that reflect your CAP trade-offs and system design.
Hints
  • How does the client send a message securely and efficiently?
  • How does the client synchronize messages after offline periods?
  • How does the recipient acknowledge message receipt to ensure consistency?
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Explicit choice of data store with partition key reasoning (e.g., Cassandra with conversation_id)
  • Clear CAP trade-off prioritization with justification (availability over consistency during partitions)
  • Client-side end-to-end encryption design preserving privacy and offline delivery
  • Use of Kafka for ordered message delivery and offline sync
  • API design reflecting CAP trade-offs and offline support
Good to Have - 30%
  • Discussion of tunable consistency levels and conflict resolution
  • Latency considerations with P99 < 200ms justification
  • Integration details between Kafka and Cassandra for durability
  • Security considerations including TLS and encryption at rest
Bonus - 10%
  • Innovative conflict resolution strategies
  • Detailed offline sync optimization
  • Thoughtful key management design
Anti-patterns to Avoid
Using sender_id as partition key causing out-of-order delivery and complex reconciliation due to message scattering across nodes
Choosing strong consistency with synchronous global replication causing high latency and unavailability during network partitions
HTTP polling at 50M DAU: 50M reconnects/min just to check for messages - collapses under load
✅
Model Answer
▼ Reveal

This design uses Apache Cassandra with conversation_id as the partition key to ensure ordered, scalable writes and efficient range queries. It prioritizes availability and partition tolerance by leveraging Cassandra's tunable eventual consistency, allowing writes during network partitions and asynchronous conflict resolution. End-to-end encryption is implemented client-side, with encrypted blobs stored in Cassandra, preserving privacy and enabling offline delivery. Apache Kafka is used with conversation_id partitioning for ordered message delivery and cursor-based offline synchronization, ensuring P99 latency under 200ms. The REST API includes SendMessage, SyncMessages, and AckMessage endpoints reflecting CAP trade-offs and offline support.

Key Decisions
  • Use Apache Cassandra with partition_key=conversation_id for ordered writes and range queries
  • Prioritize availability and partition tolerance during network partitions using Cassandra's eventual consistency
  • Implement client-side end-to-end encryption to protect message privacy and enable offline delivery
  • Use Apache Kafka with conversation_id partition key for ordered message delivery and efficient offline sync
  • Design REST API endpoints that support encrypted message sending, cursor-based offline sync, and receipt acknowledgments
  • Apache Cassandra with conversation_id partition key for ordered, scalable writes and range queries
  • Apache Kafka with conversation_id as partition key for ordered message delivery and offline sync
  • Client-side end-to-end encryption ensuring privacy and offline message storage without server decryption
  • Tunable consistency levels in Cassandra to prioritize availability and partition tolerance during network splits
  • Cursor-based synchronization mechanism enabling efficient offline message catch-up with minimal data transfer
  • REST API endpoints designed to reflect CAP trade-offs: SendMessage, SyncMessages, AckMessage
  • Conflict resolution via client acknowledgments and asynchronous reconciliation in Cassandra
  • Use of TLS for transport security combined with encryption at rest in Cassandra

Practice

(1/5)
1. A web application needs a cache that automatically removes entries after a fixed time regardless of access frequency. Which cache eviction policy best fits this requirement?
easy
A. Least Frequently Used (LFU) eviction, which removes items accessed least often
B. Least Recently Used (LRU) eviction, which removes the oldest accessed items first
C. Time-To-Live (TTL) eviction, which expires entries after a set duration
D. Adaptive Replacement Cache (ARC), which balances recency and frequency

Solution

  1. Step 1: Identify eviction based on time expiration

    TTL eviction removes cache entries strictly after a fixed time, independent of access patterns.

  2. Step 2: Eliminate other policies

    LRU and LFU depend on access recency or frequency, not fixed time. ARC adapts between recency and frequency but does not enforce fixed expiration.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    TTL evicts by fixed time, ignoring usage patterns [check]
Hint: TTL evicts by time, not usage frequency or recency [OK]
Common Mistakes:
2. For a system tracking SLO error budgets with high write volume and low latency requirements, which architecture is best suited to ensure accurate, near real-time error budget updates?
medium
A. Batch processing error logs every hour using Hadoop MapReduce
B. Polling a relational database every minute for error counts and updating budgets
C. Stream processing with Apache Flink to compute error budgets continuously
D. Using a time-series database with hourly rollups for error budget calculation

Solution

  1. Step 1: Analyze latency and accuracy requirements

    Near real-time updates require continuous stream processing rather than batch or polling.

  2. Step 2: Evaluate each architecture against these requirements

    Batch processing (A) and hourly rollups (D) are too slow; polling (C) introduces latency and load spikes; stream processing (B) provides continuous, low-latency computation.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Stream processing -> continuous, low-latency error budget updates [check]
Hint: Stream processing fits low latency and high write volume best [OK]
Common Mistakes:
3. For a system requiring globally unique IDs with high throughput and low latency, which approach is best considering the trade-offs of coordination overhead and ID ordering?
medium
A. Use a distributed consensus protocol (e.g., Paxos) to assign IDs synchronously
B. Use a database auto-increment primary key with sharding
C. Use a centralized Ticket Server allocating ID blocks to clients for local use
D. Use client-generated UUIDs combined with a timestamp prefix

Solution

  1. Step 1: Evaluate coordination overhead

    Consensus (A) ensures strong consistency but adds latency and limits throughput; DB auto-increment with sharding (D) risks collisions and complex coordination.

  2. Step 2: Assess ordering and uniqueness

    UUIDs (C) are unique but unordered and can cause issues in ordered systems; Ticket Server (B) balances uniqueness, ordering, and throughput by allocating ID blocks.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Ticket Server -> high throughput, low latency, ordered IDs [check]
Hint: Centralized block allocation beats consensus and UUIDs for throughput [check]
Common Mistakes:
4. At 10x scale, which component in the CI/CD pipeline is most likely to become the bottleneck first, and why?
hard
A. Artifact Registry, because storage and retrieval latency increase with artifact volume
B. Test Runner, because parallel test execution saturates CPU and memory resources
C. Deployment Orchestrator, because coordinating thousands of concurrent deployments causes state management overhead
D. Rollback Manager, because tracking and reverting large numbers of deployments requires heavy database writes

Solution

  1. Step 1: Analyze artifact registry scaling challenges

    At 10x scale, artifact volume grows massively, increasing storage needs and retrieval latency, stressing the registry's throughput and storage backend.

  2. Step 2: Compare other components

    Test runner scales with parallelism; orchestrator is stateless or sharded; rollback manager writes are less frequent and can be batched.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Artifact registry storage and latency bottleneck at scale [check]
Hint: Artifact registry storage grows fastest, bottleneck first [check]
Common Mistakes:
5. At 10x scale, which component in the food delivery system is most likely to fail first and why?
hard
A. The restaurant discovery cache, because memory limits prevent caching all restaurants in all regions
B. The relational database storing orders, because write throughput exceeds disk I/O capacity
C. The driver assignment service, because maintaining stateful WebSocket connections for all drivers prevents horizontal scaling
D. The notification service, because push notification providers throttle requests at high volume

Solution

  1. Step 1: Identify stateful components at scale

    Driver assignment maintains WebSocket connections, which are stateful and tied to server memory.

  2. Step 2: Analyze scaling bottlenecks

    WebSocket connections cannot be easily sharded or moved; adding servers doesn't migrate existing connections, causing resource exhaustion.

  3. Step 3: Compare other components

    Databases (A) can be sharded; caches (C) can evict; notification services (D) can batch or retry.

  4. Final Answer:

    Option C -> Option C

  5. Quick Check:

    Stateful WebSocket connections -> driver assignment service bottleneck [check]
Hint: Stateful WebSocket connections block driver service scaling [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