Bird
Raised Fist0

Cache Invalidation Strategies - TTL, Purge, Surrogate Keys

HLDmediumInterview freq: medium
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
Cache Invalidation Strategies - TTL, Purge, Surrogate Keys
Designing scalable cache invalidation using TTL, purge, and surrogate keys for CDN
mediumContent Delivery NetworkFreq: medium
⚙️
Functional Requirements
  • Support TTL-based automatic expiration of cached content to reduce stale data
  • Allow explicit purge requests to immediately invalidate specific cache entries
  • Implement surrogate keys to group related cache entries for bulk invalidation
  • Provide APIs for cache invalidation operations with authentication and audit logging
  • Ensure cache consistency across distributed CDN edge nodes
  • Support partial cache invalidation for content updates without full cache flush
📊
Non-Functional Requirements
  • Handle 2 billion daily active users generating up to 925K cache invalidations per second at peak
  • Achieve 99.99% availability for cache invalidation APIs and propagation
  • Maintain P99 latency under 100ms for cache invalidation requests
  • Ensure cache invalidation propagation to all edge nodes within 1 second
  • Support retention of invalidation logs for 30 days for audit and debugging
❓
Clarifying Questions to Ask
  • What is the expected cache hit ratio and cache size per edge node?
  • Are invalidations triggered mostly by content updates or user actions?
  • What is the maximum acceptable staleness window for cached content?
  • How many surrogate keys can a single cache entry be associated with?
  • Is the cache invalidation system expected to support multi-region consistency?
  • What is the expected peak QPS for purge and surrogate key invalidations separately?
Out of Scope
✗ Design of the core CDN content delivery and caching mechanisms
✗ Authentication and authorization systems beyond basic API security
✗ Content origin server design and content generation pipelines
✗ Detailed CDN routing and load balancing strategies
📌
Assumptions
  • 2 billion DAU generating 40 cache invalidation messages per user per day
  • Average cache invalidation message size is 100 bytes
  • Peak traffic is 3x average traffic during peak hours
  • Cache retention for invalidation logs is 30 days
⚡
QPS Calculation
write qps2B × 40 / 86400 ≈ 925,926 writes/sec
peak write qps925,926 × 3 ≈ 2,777,778 writes/sec
read qpsAssuming 10 reads per write for cache validation: 9,259,260 reads/sec
💾
Storage Estimate
daily storage2,777,778 writes/sec × 100 bytes × 86400 sec ≈ 24 TB/day
retention storage24 TB/day × 30 days = 720 TB
with replication720 TB × 3 replicas = 2.16 PB total storage
🖥️
Server Estimate
write pathKafka cluster with 100 brokers to handle 2.7M writes/sec (27K writes/sec per broker)
read pathRedis cluster with 500 nodes for sub-millisecond TTL lookups and purge operations
🏗️
Architecture Diagram
Architecture Diagram
       +-------------+
       | Content     |
       | Origin      |
       +------+------+
              |
              v
       +------+-------+
       | Cache Inval  |
       | API Gateway  |
       +------+-------+
              |
              v
       +------+-------+       +----------------+
       | Kafka Topic  |<----->| Invalidation    |
       | (Invalidation|       | Processor      |
       |  Events)     |       +----------------+
       +------+-------+
              |
              v
       +------+-------+
       | Redis Cache  |
       | Cluster     |
       +------+-------+
              |
              v
       +------+-------+
       | CDN Edge     |
       | Nodes       |
       +--------------+
🧩
Components
Cache Invalidation API Gateway
Receives TTL, purge, and surrogate key invalidation requests from clients
Why thisNginx + Envoy for high throughput, TLS termination, and authentication support
Why notDirect Kafka ingestion rejected due to lack of API-level auth and rate limiting
Kafka Invalidation Topic
Durable, ordered log of invalidation events for asynchronous processing
Why thisKafka supports 2.7M writes/sec with partitioning and replication for durability
Why notRabbitMQ rejected due to lower throughput and weaker partitioning at this scale
Invalidation Processor
Consumes Kafka events, applies TTL, purge, and surrogate key logic, updates cache
Why thisStateless microservices in Kubernetes for horizontal scaling and fault tolerance
Why notMonolithic batch jobs rejected due to high latency and poor real-time invalidation
Redis Cluster
Stores cache metadata with TTL support and surrogate key mappings for fast invalidation
Why thisRedis TTL natively expires stale entries without cron jobs; sub-millisecond lookups
Why notMemcached rejected due to lack of native TTL and complex surrogate key support
CDN Edge Nodes
Serve cached content and listen for invalidation signals to purge local cache
Why thisEdge nodes subscribe to invalidation events for near real-time cache consistency
Why notPolling-based invalidation rejected due to high latency and bandwidth waste
🔄
Data Flow
1
Client → Cache Invalidation API Gateway
Send TTL, purge, or surrogate key invalidation request
API Gateway authenticates and rate limits requests
2
API Gateway → Kafka Invalidation Topic
Publish invalidation event asynchronously
Kafka ensures durable, ordered event storage
3
Invalidation Processor → Kafka Invalidation Topic
Consume invalidation events
Processor applies business logic for TTL, purge, surrogate keys
4
Invalidation Processor → Redis Cluster
Update cache metadata and surrogate key mappings
Redis TTL expires stale entries automatically
5
Invalidation Processor → CDN Edge Nodes
Push invalidation signals via pub/sub or HTTP
Edge nodes purge or refresh cached content immediately
6
CDN Edge Nodes → Clients
Serve fresh or purged content
Ensures cache consistency and low latency

Practice

(1/5)
1. In a digital wallet system handling millions of transactions per second, which component is best suited to ensure atomicity and durability of each transaction while decoupling the write load from downstream processing?
easy
A. Use a relational database with immediate synchronous commits for every transaction
B. Use an in-memory cache like Redis to store transaction states temporarily before final commit
C. Use a distributed log system like Kafka to record transaction events with partition keys for ordering
D. Use a NoSQL document store with eventual consistency guarantees for transaction writes

Solution

  1. Step 1: Identify Kafka's role in durability and ordering

    Kafka provides a durable, append-only log with partition keys ensuring ordering per wallet or transaction, enabling atomicity and replayability.

  2. Step 2: Eliminate other options based on constraints

    Relational DB synchronous commits (A) cause high latency and throughput bottlenecks; Redis (C) lacks durability guarantees; NoSQL eventual consistency (D) risks inconsistent ledger states.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Kafka partitions with transaction keys -> durable, ordered event log [check]
Hint: Distributed log with partition keys ensures durable ordering [OK]
Common Mistakes:
2. A system needs to serve AI code completions with sub-100ms latency while ensuring up-to-date code context. Which component is best suited to provide fast, low-latency retrieval of relevant code snippets?
easy
A. A relational database with complex SQL queries for code indexing
B. An in-memory vector search engine with approximate nearest neighbor (ANN) indexing
C. A distributed file system storing raw code files for batch processing
D. A message queue to buffer code snippet requests before processing

Solution

  1. Step 1: Identify low-latency retrieval need

    Relational DBs (A) have high query latency for vector similarity; distributed file systems (C) are for storage, not fast retrieval; message queues (D) buffer requests but don't serve retrieval.

  2. Step 2: Recognize vector search role

    ANN-based in-memory vector search engines (B) provide fast approximate nearest neighbor lookups, ideal for sub-100ms latency code snippet retrieval.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    ANN vector search enables fast similarity queries [check]
Hint: Vector search engines excel at fast similarity retrieval [check]
Common Mistakes:
3. A distributed messaging system must handle 1 million writes per second and guarantee message durability despite node failures. Which component best handles this requirement?
easy
A. Use a distributed log system like Apache Kafka with replication and partitioning
B. Use an in-memory cache like Redis without persistence to speed up writes
C. Use a relational database with synchronous writes for durability
D. Use a simple message queue with no replication to reduce latency

Solution

  1. Step 1: Identify durability and high write throughput needs

    Redis without persistence (A) cannot guarantee durability on failure. Relational DB (C) cannot handle 1M writes/sec synchronously without bottlenecks. Simple queue without replication (D) risks message loss.

  2. Step 2: Recognize Kafka's replication and partitioning

    Kafka provides durable, replicated logs with partitioning for high throughput and fault tolerance.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Kafka replication + partitioning -> durability and scale [check]
Hint: Kafka replicates logs for durability and scales with partitions [check]
Common Mistakes:
4. If the Kafka broker cluster loses ZooKeeper coordination, what exactly breaks in the message delivery process?
medium
A. Messages are lost immediately as brokers cannot write to logs
B. Producers can still write, but partition leadership cannot be elected, causing delivery stalls
C. Consumers receive duplicate messages due to offset corruption
D. The entire cluster shuts down automatically to prevent data loss

Solution

  1. Step 1: Role of ZooKeeper in Kafka

    ZooKeeper manages partition leadership and consumer offsets; losing it affects coordination but not immediate message loss.

  2. Step 2: Failure impact on delivery

    Without ZooKeeper, offset metadata can become inconsistent, causing consumers to re-read messages and receive duplicates (C); producers may still write (B is partially true but leadership election stalls eventually); cluster does not shut down automatically (D).

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    ZooKeeper loss -> offset inconsistency -> duplicate consumer messages [check]
Hint: ZooKeeper loss corrupts offsets causing duplicates, not immediate loss [check]
Common Mistakes:
5. At 10x scale, which component in a gRPC internal service communication system is most likely to fail first and why?
hard
A. gRPC server's streaming connection handler due to stateful HTTP/2 streams per client
B. Protocol Buffers serialization CPU bottleneck due to large message sizes
C. Load balancer because it cannot handle increased TCP connections
D. Service registry because of increased service instance churn

Solution

  1. Step 1: Identify stateful components at scale

    gRPC streaming uses HTTP/2 streams bound to server memory per client, limiting horizontal scaling.

  2. Step 2: Compare bottlenecks

    Protocol Buffers serialization is CPU intensive but parallelizable. Load balancers and service registries scale better with standard techniques. Stateful streaming handlers are the first to hit resource limits.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Stateful HTTP/2 streams -> server connection handler bottleneck [check]
Hint: Stateful streams -> server connection handler bottleneck 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