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

You are designing a globally distributed messaging platform with 50 million daily active users (DAU). The system must provide strong consistency guarantees for message delivery while maintaining a P99 latency under 200ms. Users expect near real-time message sync across devices worldwide. The system must encrypt data at rest and in transit, and support offline message delivery with eventual sync once devices reconnect.

Constraints
  • End-to-end encryption required for all messages
  • P99 latency for message delivery and sync must be under 200ms globally
  • Support offline message delivery and eventual consistency on reconnect
  • Global distribution with data centers in multiple continents
  • Strong consistency preferred but must balance latency trade-offs
📋
Guided Steps
1/5
Step 1
Choosing the Data Storage Model
How would you design the data storage layer to balance consistency and latency for global message delivery?
💡 Hint
Consider partitioning keys that enable ordered writes and efficient range queries for sync.
Key Decision
Use Apache Cassandra with conversation_id as the partition key to ensure linearizable writes per conversation and efficient cursor-based range queries for message sync.
Interviewer Expectation
Mid-level: Names Cassandra for scalability. Senior: Explains why conversation_id as partition key ensures ordered writes and why sender_id partitioning causes out-of-order delivery and sync complexity.
⚠️Common Wrong Answer
Using sender_id as partition key causing messages in the same conversation to scatter across partitions, leading to out-of-order delivery and complex client-side reconciliation.
Step 2
Message Ingestion and Ordering
What messaging infrastructure would you use to ingest and order messages globally with low latency?
💡 Hint
Look for a distributed log system that supports partition keys and strong ordering guarantees per partition.
Key Decision
Use Apache Kafka with conversation_id as the partition key to guarantee ordered message ingestion and enable exactly-once processing semantics per conversation partition.
Interviewer Expectation
Mid-level: Identifies Kafka for messaging. Senior: Explains how Kafka partitioning by conversation_id ensures ordering and locality, and why RabbitMQ or SQS would not scale or guarantee ordering at this scale.
⚠️Common Wrong Answer
Using RabbitMQ or SQS without partition keys, resulting in unordered message delivery and inability to scale to 50M DAU with 925K msg/sec.
Step 3
Consistency vs Latency Trade-off
How would you apply the PACELC theorem to decide between consistency and latency during network partitions and normal operation?
💡 Hint
Consider how to tune replication and read/write consistency levels in Cassandra and Kafka to balance latency and consistency.
Key Decision
Configure Cassandra with QUORUM writes and reads to balance consistency and latency, and Kafka with ISR (in-sync replicas) to ensure durability without sacrificing P99 latency under 200ms.
Interviewer Expectation
Mid-level: Mentions consistency vs availability trade-offs. Senior: Explains PACELC trade-offs explicitly, how QUORUM consistency reduces stale reads but increases latency, and how tuning ISR size affects latency during partitions.
⚠️Common Wrong Answer
Choosing ALL consistency level causing high latency spikes above 200ms P99, or ONE causing stale reads violating strong consistency.
Step 4
Offline Delivery and Sync Mechanism
How would you design the offline message delivery and sync mechanism to ensure eventual consistency without violating latency constraints?
💡 Hint
Think about client-side cursors, server-side message retention, and incremental sync using range queries.
Key Decision
Implement client-side cursor tracking with Cassandra range queries on conversation_id partition to fetch missed messages efficiently, combined with Redis TTL-based presence detection to optimize sync triggers.
Interviewer Expectation
Mid-level: Describes cursor-based sync. Senior: Explains why Redis TTL presence reduces unnecessary syncs, how Cassandra range queries enable O(1) incremental fetch, and how this design avoids full data scans.
⚠️Common Wrong Answer
Using HTTP polling for sync causing massive load spikes and latency degradation at 50M DAU.
Step 5
Security and Encryption
How would you ensure end-to-end encryption for messages while maintaining system scalability and latency SLAs?
💡 Hint
Consider encryption at rest, in transit, and client-side encryption to prevent server-side plaintext access.
Key Decision
Use client-side encryption with libsodium for message payloads, TLS 1.3 for in-transit encryption, and Cassandra Transparent Data Encryption (TDE) for at-rest encryption to meet security and latency requirements.
Interviewer Expectation
Mid-level: Mentions TLS and encryption. Senior: Details client-side encryption to prevent server plaintext access, explains TDE overhead and how it fits latency budget, and discusses key management strategies.
⚠️Common Wrong Answer
Relying only on TLS without client-side encryption, exposing plaintext on servers and violating security constraints.
🔌
API Design Challenge
Sketch 3 core API endpoints for the messaging system that handle sending messages, syncing messages on reconnect, and acknowledging message receipt.
Hints
  • How does the client send a message and ensure it is durably stored?
  • How does the client efficiently sync missed messages after offline periods?
  • How does the client acknowledge message receipt to update delivery status?
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Use of conversation_id as partition key in Kafka and Cassandra for ordering and efficient sync
  • Explicit PACELC trade-off reasoning balancing consistency and latency
  • Client-side cursor-based incremental sync design
  • End-to-end encryption including client-side encryption and TLS
Good to Have - 30%
  • Use of Redis TTL presence detection to optimize sync triggers
  • Tuning Kafka ISR and Cassandra consistency levels for latency SLAs
  • Discussion of global distribution and data center locality impact on latency
Bonus - 10%
  • Detailed key management strategy for client-side encryption keys
  • Consideration of failure modes and recovery sequences under network partitions
Anti-patterns to Avoid
Using sender_id as partition key causing out-of-order delivery and complex sync, which leads to message reordering and client-side reconciliation overhead.
Relying on HTTP polling for offline sync causing load spikes and latency collapse at 50M DAU due to 50 million reconnects per minute just to check for messages, overwhelming servers.
Choosing ALL consistency level in Cassandra causing latency spikes beyond 200ms P99, resulting in poor user experience and SLA violations.
Omitting client-side encryption exposing plaintext on servers, violating end-to-end encryption requirements and increasing security risks.
✅
Model Answer
▼ Reveal

The system uses Apache Kafka and Cassandra partitioned by conversation_id to ensure ordered message ingestion and efficient sync. PACELC theorem guides tuning consistency and latency trade-offs with QUORUM levels and ISR settings. Offline sync uses client-side cursors with Cassandra range queries and Redis TTL presence detection to minimize load. Security is ensured via client-side encryption with libsodium, TLS 1.3 in transit, and Cassandra TDE at rest.

Key Decisions
  • Partition Kafka and Cassandra by conversation_id to guarantee ordering and locality
  • Configure Cassandra with QUORUM consistency for reads and writes to balance latency and consistency
  • Tune Kafka ISR size to maintain durability without exceeding 200ms P99 latency
  • Implement client-side cursors for incremental sync using Cassandra range queries
  • Use Redis TTL-based presence detection to reduce unnecessary sync requests
  • Apply client-side encryption with libsodium to prevent server plaintext access
  • Use TLS 1.3 for secure in-transit encryption
  • Enable Cassandra TDE for at-rest encryption with minimal latency impact
  • conversation_id as Kafka partition key - ensures ordered message ingestion and locality
  • Apache Cassandra with conversation_id partition key - enables efficient range queries for sync
  • Kafka ISR configuration tuned to balance durability and P99 latency under 200ms
  • Client-side cursor tracking with Cassandra range scans for incremental offline sync
  • Redis TTL-based presence detection to minimize unnecessary sync requests
  • Client-side encryption using libsodium to secure message payloads end-to-end
  • TLS 1.3 for in-transit encryption to protect data between clients and servers
  • Cassandra Transparent Data Encryption (TDE) for at-rest encryption without latency penalty

Practice

(1/5)
1. A distributed database requires that every write is confirmed by a majority of replicas before acknowledging success to the client. Which replication strategy best fits this requirement?
easy
A. Asynchronous replication with eventual consistency
B. Single-leader replication without acknowledgments
C. Synchronous replication with quorum writes
D. Master-slave replication with delayed slave updates

Solution

  1. Step 1: Identify replication strategy matching majority confirmation

    Synchronous replication with quorum writes requires majority replicas to acknowledge before success.

  2. Step 2: Eliminate asynchronous and single-leader without ack

    Asynchronous replication and single-leader without acknowledgments do not guarantee majority confirmation before success.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Quorum writes ensure majority ack before success [check]
Hint: Quorum writes wait for majority acks before success [OK]
Common Mistakes:
2. A machine learning platform needs to provide low-latency access to precomputed features for online inference at 100K requests per second. Which component is best suited to serve these feature requests efficiently?
easy
A. A relational database with complex SQL queries for feature retrieval
B. A distributed file system like HDFS storing raw feature data
C. A key-value store with in-memory caching like Redis or Memcached
D. A batch processing system like Apache Spark for on-demand feature computation

Solution

  1. Step 1: Identify low-latency requirement for online inference

    Online inference demands sub-millisecond feature retrieval, which batch systems or heavy SQL queries cannot provide efficiently.

  2. Step 2: Evaluate component suitability

    Distributed file systems and batch processing are optimized for throughput, not low latency. Relational DBs struggle with scale and latency at 100K QPS. In-memory key-value stores like Redis provide fast, scalable lookups ideal for this use case.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    In-memory key-value stores enable low-latency feature serving [check]
Hint: In-memory key-value stores excel at low-latency lookups [check]
Common Mistakes:
3. A system must efficiently handle millions of concurrent calendar availability updates from hosts worldwide, ensuring low latency and eventual consistency. Which component is best suited to buffer and process these updates asynchronously?
easy
A. Use a relational database with strong ACID transactions for immediate consistency
B. Use a cache like Redis with TTL to store availability states temporarily
C. Use direct synchronous API calls to update availability in the main database
D. Use a distributed message queue like Kafka to decouple update ingestion from processing

Solution

  1. Step 1: Identify the need for asynchronous buffering

    Millions of concurrent updates require decoupling ingestion from processing to avoid bottlenecks.

  2. Step 2: Evaluate component suitability

    Relational DB (A) causes high contention and latency; Redis (C) is volatile and not durable; synchronous API calls (D) block and reduce throughput. Kafka (B) provides durable, ordered, and scalable buffering.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Kafka buffers high-throughput writes asynchronously with durability [check]
Hint: Buffer high-write updates asynchronously with durable queues [check]
Common Mistakes:
4. If the commit metadata database becomes unavailable, what is the immediate failure observed when a user tries to create a new branch?
medium
A. The system creates the branch but marks it as unverified until metadata is restored
B. The branch creation request fails immediately with an error indicating metadata service unavailability
C. The system queues the branch creation request and retries later without user notification
D. The branch is created locally on the client but not persisted to the server

Solution

  1. Step 1: Understand role of commit metadata DB

    Commit metadata DB stores branch pointers; without it, server cannot persist new branches.

  2. Step 2: Trace branch creation failure

    Client may create branch locally, but server cannot persist it, so branch is effectively lost or inconsistent.

  3. Step 3: Eliminate other options

    Queuing without notification hides failure; immediate error is possible but not typical if client allows local ops; marking unverified branches requires metadata DB access.

  4. Final Answer:

    Option D -> Option D

  5. Quick Check:

    Metadata DB down -> branch created locally but not persisted [check]
Hint: Metadata DB down -> local branch only, no server persistence [check]
Common Mistakes:
5. For a video calling system targeting mobile clients with intermittent connectivity, which architecture best balances latency and reliability for media delivery?
medium
A. Use a multipoint control unit (MCU) media server that mixes all streams into one
B. Use a fully peer-to-peer WebRTC connection with no media server relay
C. Use a selective forwarding unit (SFU) media server to relay streams only when needed
D. Use HTTP Live Streaming (HLS) for media delivery to ensure reliability

Solution

  1. Step 1: Evaluate architectures for mobile intermittent connectivity

    Pure peer-to-peer (A) suffers from connectivity issues; MCU (C) adds latency and CPU overhead; HLS (D) is high latency and not real-time.

  2. Step 2: SFU (B) relays streams selectively, reducing latency and handling network variability well.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    SFU balances latency and reliability for mobile intermittent networks [check]
Hint: SFU relays selectively, best for mobile intermittent connectivity [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