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

You are designing cache invalidation strategies for a high-scale web platform with 50 million daily active users. The system must ensure data freshness with minimal latency impact, support encrypted data at rest and in transit, and handle complex invalidation scenarios such as bulk purges and surrogate key-based invalidations. The cache layer is critical to meet a P99 latency SLA of under 200ms for user-facing requests.

Constraints
  • Cache data must be encrypted at rest and in transit to comply with security policies.
  • P99 latency for cache lookups and invalidations must be under 200ms to maintain user experience.
  • Support TTL-based automatic expiration for most cache entries with configurable durations.
  • Support explicit purge commands to immediately invalidate specific cache keys.
  • Support surrogate key invalidation to efficiently purge groups of related cache entries (e.g., all content tagged with a category).
📋
Guided Steps
1/5
Step 1
Choosing Cache Storage and TTL Mechanism
Which caching technology and TTL strategy would you choose to support 50M DAU with encrypted data and sub-200ms P99 latency?
💡 Hint
Consider a distributed in-memory store with native TTL support and encryption capabilities.
Key Decision
Use Redis Enterprise with built-in TLS encryption and native TTL support for fast, encrypted cache lookups and automatic expiration.
Interviewer Expectation
Mid: Names Redis for caching with TTL. Senior: Explains Redis Enterprise's active-active geo-distribution, TLS encryption, and how TTL expiration is handled internally without impacting latency.
⚠️Common Wrong Answer
Using Memcached without encryption - leads to data exposure and no native TTL enforcement, causing stale data and security risks.
Step 2
Designing Explicit Purge API and Propagation
How would you design the explicit purge mechanism to immediately invalidate cache entries across distributed nodes?
💡 Hint
Think about a message broker that can propagate purge commands reliably and in order.
Key Decision
Use Apache Kafka to publish purge events with cache keys; Redis clients subscribe to purge topics to evict keys immediately across clusters.
Interviewer Expectation
Mid: Mentions Kafka for event propagation. Senior: Details partitioning by cache key hash to ensure ordered purge events and exactly-once processing semantics to avoid stale cache.
⚠️Common Wrong Answer
Directly deleting keys from one Redis node without propagation - causes cache inconsistency and stale reads in distributed setups.
Step 3
Implementing Surrogate Key Invalidation
How would you implement surrogate key invalidation to efficiently purge groups of related cache entries?
💡 Hint
Consider maintaining reverse mappings from surrogate keys to cache keys and efficient invalidation without scanning all keys.
Key Decision
Use Redis Sets to map surrogate keys to cache keys; purge by fetching set members and deleting keys atomically with Lua scripts to maintain consistency.
Interviewer Expectation
Mid: Suggests storing surrogate keys in Redis Sets. Senior: Explains atomic Lua scripts to avoid race conditions and how to handle large sets with batching to maintain latency SLA.
⚠️Common Wrong Answer
Storing surrogate keys as key prefixes and scanning keys with Redis KEYS command - causes blocking operations and latency spikes.
Step 4
Ensuring Consistency and Handling Failures
How do you ensure cache invalidation consistency and recover from failures or partial invalidations?
💡 Hint
Think about idempotency, retries, and monitoring invalidation events end-to-end.
Key Decision
Implement idempotent purge events with unique IDs in Kafka; Redis clients track processed event IDs to avoid duplicate invalidations; use monitoring dashboards and alerting on lag metrics.
Interviewer Expectation
Mid: Mentions retries on failure. Senior: Describes exactly-once processing with Kafka consumer groups, Redis client-side deduplication, and alerting on consumer lag to detect failures early.
⚠️Common Wrong Answer
No deduplication or monitoring - leads to inconsistent cache state and undetected stale data.
Step 5
API Design for Cache Invalidation
Design three core API endpoints for clients and backend services to interact with the cache invalidation system.
💡 Hint
Include endpoints for setting cache entries with TTL and surrogate keys, triggering explicit purges, and acknowledging invalidations.
Key Decision
Define POST /cache/set with payload including key, value, TTL, surrogate keys; POST /cache/purge with keys or surrogate keys; GET /cache/invalidation-status with event IDs for acknowledgement.
Interviewer Expectation
Mid: Provides basic set and purge endpoints. Senior: Includes surrogate key support in set, asynchronous purge acknowledgement, and idempotency tokens in API design.
⚠️Common Wrong Answer
Only providing a simple set and delete API without surrogate key or acknowledgement support - limits invalidation flexibility and observability.
🔌
API Design Challenge
Sketch 3 core API endpoints for the cache invalidation system that clients and backend services will use.
Hints
  • How does a client or service set TTL and surrogate keys when caching data?
  • How does a service trigger an explicit purge or surrogate key invalidation?
  • How does the system confirm or acknowledge that invalidation has been processed?
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Use of Redis Enterprise with encryption and TTL support for caching.
  • Explicit purge event propagation via Kafka with ordered processing.
  • Surrogate key invalidation implemented with Redis Sets and atomic Lua scripts.
  • Idempotent event processing and monitoring for consistency and failure detection.
Good to Have - 30%
  • Batching and rate limiting of surrogate key invalidations to maintain latency SLA.
  • API design supporting TTL, surrogate keys, purge commands, and acknowledgement.
  • Geo-distributed cache deployment to reduce latency for global users.
Bonus - 10%
  • Detailed failure mode analysis of purge event loss and recovery.
  • Use of Redis client-side deduplication to avoid duplicate invalidations.
Anti-patterns to Avoid
Using Redis KEYS command for surrogate key invalidation causes blocking operations and latency spikes under scale, severely impacting P99 latency SLA.
Directly deleting keys on a single cache node without event propagation leads to stale cache in distributed environment, causing inconsistent user experiences.
Ignoring encryption requirements exposes sensitive cached data, violating security policies and risking data breaches.
✅
Model Answer
▼ Reveal

This design uses Redis Enterprise for encrypted, low-latency caching with native TTL support, Apache Kafka for reliable and ordered purge event propagation, and Redis Sets with Lua scripts for atomic surrogate key invalidation. Idempotent event processing and monitoring ensure consistency and failure recovery. The API supports setting cache entries with TTL and surrogate keys, explicit purge commands, and invalidation acknowledgements.

Key Decisions
  • Use Redis Enterprise for caching to leverage built-in TLS encryption and native TTL expiration, ensuring secure and fast cache lookups.
  • Use Apache Kafka to propagate explicit purge events reliably and in order, partitioned by cache key hash to maintain event ordering and exactly-once semantics.
  • Implement surrogate key invalidation by storing mappings in Redis Sets and using atomic Lua scripts to delete all related cache keys efficiently without blocking.
  • Ensure idempotent purge event processing by assigning unique event IDs and tracking processed events on Redis clients to avoid duplicate invalidations.
  • Design API endpoints that allow clients to set cache entries with TTL and surrogate keys, trigger explicit purges by keys or surrogate keys, and acknowledge invalidation processing asynchronously.
  • Redis Enterprise with TLS encryption and native TTL for secure, low-latency caching.
  • Apache Kafka for ordered, reliable propagation of explicit purge events across distributed cache nodes.
  • Redis Sets combined with Lua scripts for atomic surrogate key to cache key mappings and efficient group invalidations.
  • Idempotent purge event processing with unique IDs and consumer-side deduplication to ensure consistency.
  • Monitoring Kafka consumer lag and Redis eviction metrics to detect and alert on invalidation failures.
  • API design including POST /cache/set with TTL and surrogate keys, POST /cache/purge for explicit invalidations, and GET /cache/invalidation-status for acknowledgement.
  • Batching surrogate key invalidations to avoid latency spikes and maintain P99 SLA under heavy load.
  • Use of Redis Enterprise active-active geo-distribution to reduce latency for global user base.

Practice

(1/5)
1. A food delivery system must efficiently match nearby drivers to new orders in real-time, minimizing latency and ensuring fairness. Which component is best suited to handle this driver assignment under high load?
easy
A. A relational database with spatial indexing to query nearest drivers synchronously
B. A simple REST API that queries all drivers and filters by distance on the client side
C. A batch job that runs every 5 minutes to assign drivers to pending orders
D. A distributed in-memory geospatial index with pub/sub notifications for driver availability

Solution

  1. Step 1: Identify driver assignment requirements

    Real-time, low-latency matching requires fast spatial queries and event-driven updates.

  2. Step 2: Evaluate component suitability

    Relational DBs with spatial indexes (A) are too slow for high write/read concurrency; batch jobs (C) introduce unacceptable delay; client-side filtering (D) is inefficient and inconsistent.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Distributed in-memory geospatial index with pub/sub -> real-time, scalable driver assignment [check]
Hint: In-memory geospatial + pub/sub for real-time driver matching [check]
Common Mistakes:
2. A distributed task scheduler must support millions of scheduled jobs with varying priorities and ensure tasks are executed exactly once. Which component is best suited to manage task ordering and priority under these constraints?
easy
A. A distributed priority queue with partitioned shards
B. A relational database with indexed priority columns
C. A simple FIFO message queue like RabbitMQ without priority support
D. A cron job scheduler running independently on each node

Solution

  1. Step 1: Identify priority and scale requirements

    A relational DB (A) struggles with high write throughput and priority ordering at scale; simple FIFO queues (C) lack priority support; cron jobs (D) do not coordinate distributed execution or priority.

  2. Step 2: Evaluate distributed priority queue

    A distributed priority queue with partitioned shards (B) can scale horizontally, maintain priority ordering per shard, and support exactly-once execution semantics.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Distributed priority queue shards scale and preserve ordering [check]
Hint: Distributed priority queues scale and order tasks by priority [check]
Common Mistakes:
3. In the network recovery process after a BGP misconfiguration, at step 4 the network operator applies a route withdrawal. What is the immediate effect observed by the BGP routers in the affected region at this step?
easy
A. Routers immediately drop all traffic to the withdrawn prefixes without rerouting
B. Routers mark the withdrawn routes as unreachable and start selecting alternative paths
C. Routers send ICMP unreachable messages to all clients connected
D. Routers buffer incoming packets until the route is restored

Solution

  1. Step 1: Trace BGP route withdrawal effect

    When a route is withdrawn, routers remove it from their routing table and send ICMP unreachable messages to notify clients that the destination is unreachable.

  2. Step 2: Eliminate incorrect options

    Routers do not buffer packets (C), nor do they drop traffic silently (A). Marking routes unreachable and selecting alternatives (B) happens but only after receiving withdrawal; immediate effect is ICMP signaling.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Route withdrawal triggers ICMP unreachable notifications [check]
Hint: Route withdrawal triggers ICMP unreachable messages [check]
Common Mistakes:
4. For the restaurant discovery feature, you must support millions of users searching by location with low latency. Which architecture is best suited given the constraint that restaurant data updates happen frequently (every few minutes)?
medium
A. Use a relational database with geospatial indexes and query directly for each user search
B. Use a distributed cache with geospatial indexing that asynchronously syncs updates from the primary database
C. Use a batch ETL pipeline to rebuild a search index every hour and serve queries from it
D. Use client-side filtering by downloading all restaurants in the city and filtering locally

Solution

  1. Step 1: Analyze read/write pattern for restaurant discovery

    High read volume with frequent writes requires low-latency reads and near-real-time updates.

  2. Step 2: Evaluate architectures

    Relational DB (A) can't handle query volume with low latency; batch ETL (C) is too stale; client filtering (D) is impractical for large data.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Distributed cache with async sync -> low latency + fresh data [check]
Hint: Async cache sync balances freshness and query speed [check]
Common Mistakes:
5. If the message queue (e.g., Kafka) between the upload service and transcoding pipeline fails, what exactly breaks in the video processing flow?
medium
A. Uploaded videos are accepted but never reach transcoding, so no processed versions are generated
B. Upload service blocks until transcoding completes, causing upload timeouts
C. Videos are transcoded multiple times causing duplicate outputs
D. View counts increment incorrectly due to missing transcoding metadata

Solution

  1. Step 1: Trace failure impact of message queue outage

    The queue decouples upload and transcoding. Without it, upload service cannot enqueue transcoding jobs. Uploads succeed but transcoding workers receive no tasks, so no processed videos are generated. Blocking upload (B) is incorrect because upload is asynchronous. Duplicate transcoding (A) is unrelated. View count errors (D) happen downstream, not due to queue failure.

  2. Step 2: Confirm exact failure mode

    Uploads accepted but stuck before transcoding is the precise failure.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Queue failure causes transcoding jobs to be lost, no processed videos [check]
Hint: Queue failure means no transcoding jobs dispatched [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