Bird
Raised Fist0

Cache Eviction Policies - LRU, LFU, TTL, ARC and When to Use Each

HLDmediumInterview freq: common
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🎯
Cache Eviction Policies - LRU, LFU, TTL, ARC and When to Use Each
45 min · senior
senior

You are designing a caching layer for a 50M DAU social media platform that serves personalized feeds and user profiles. The cache must maintain low latency (P99 < 200ms) for reads and writes, support encrypted data at rest and in transit, and handle bursty traffic patterns with frequent cache invalidations. The system must support multiple eviction policies (LRU, LFU, TTL, ARC) to optimize for different workload patterns and data freshness requirements.

Constraints
  • Cache data must be encrypted at rest and in transit to comply with privacy regulations
  • P99 latency for cache hits and misses must be under 200ms
  • Cache size is limited to 1TB distributed across multiple nodes
  • Workloads include both read-heavy and write-heavy patterns with bursty traffic
  • Eviction policies must be pluggable and dynamically configurable per data type
  • Cache consistency with backend data must be eventually consistent with TTL-based invalidation
📋
Guided Steps
1/5
Step 1
Choosing the Cache Storage Technology
Which caching technology would you select to support encrypted data, low latency, and pluggable eviction policies at 50M DAU scale?
💡 Hint
Consider mature distributed caches with native eviction support and encryption features.
Key Decision
Use Redis Enterprise with TLS encryption and Redis modules to support multiple eviction policies and data persistence.
Interviewer Expectation
Mid: Names Redis for caching. Senior: Explains Redis Enterprise's native TLS encryption, eviction policy support, and clustering for scale.
⚠️Common Wrong Answer
Using Memcached without encryption support leads to data exposure and inability to enforce eviction policies dynamically.
Step 2
Implementing Multiple Eviction Policies
How would you design the system to support LRU, LFU, TTL, and ARC eviction policies dynamically per data type?
💡 Hint
Think about modular eviction logic and metadata tracking per cache entry.
Key Decision
Implement eviction policies using Redis's built-in LRU and LFU, TTL for expiry, and a custom ARC module for adaptive caching, configurable via Redis key namespaces.
Interviewer Expectation
Mid: Describes LRU and TTL usage. Senior: Details how ARC is implemented as a Redis module and how policies are dynamically switched per namespace or key prefix.
⚠️Common Wrong Answer
Hardcoding a single eviction policy (e.g., only LRU) causes suboptimal cache hit rates for diverse workloads.
Step 3
Handling Cache Consistency and Expiry
How will you ensure cache consistency with backend data and handle TTL expiry notifications for cache invalidation?
💡 Hint
Consider event-driven invalidation and TTL-based expiry mechanisms integrated with backend updates.
Key Decision
Use Redis Keyspace Notifications to emit expiry events, combined with backend event streams (Kafka) to trigger cache invalidations and refreshes asynchronously.
Interviewer Expectation
Mid: Mentions TTL expiry. Senior: Explains Redis Keyspace Notifications integration with Kafka for eventual consistency and cache refresh workflows.
⚠️Common Wrong Answer
Ignoring expiry notifications leads to stale data and inconsistent cache state with backend.
Step 4
Designing Cache API Endpoints
Sketch the 3 core API endpoints for clients to set cache entries with eviction policy, get cached data, and invalidate cache entries.
💡 Hint
Focus on how eviction policy is specified, cache miss handling, and explicit invalidation triggers.
Key Decision
Design endpoints: POST /cache/set with payload including key, value, eviction_policy, TTL; GET /cache/get with key returning cached value or miss; POST /cache/invalidate with key to trigger explicit invalidation.
Interviewer Expectation
Mid: Provides basic set/get APIs. Senior: Includes eviction_policy param in set, explains cache miss fallback, and explicit invalidation endpoint for backend sync.
⚠️Common Wrong Answer
Omitting eviction policy in set API forces uniform policy, reducing flexibility and cache efficiency.
Step 5
Scaling and Monitoring Cache Performance
How would you scale the cache cluster and monitor eviction policy effectiveness and latency SLAs?
💡 Hint
Consider sharding, replication, and telemetry integration for real-time metrics.
Key Decision
Use Redis Enterprise clustering with sharding by key hash, replication for fault tolerance, and integrate Prometheus + Grafana for eviction metrics, hit/miss ratio, and latency monitoring.
Interviewer Expectation
Mid: Mentions sharding and replication. Senior: Details key hash partitioning, replication factor trade-offs, and custom eviction policy metrics for SLA adherence.
⚠️Common Wrong Answer
Ignoring monitoring leads to undetected cache thrashing and SLA violations.
🔌
API Design Challenge
Sketch 3 core API endpoints for the caching layer that support setting cache entries with eviction policy, retrieving cached data, and invalidating cache entries.
Hints
  • How does the client specify the eviction policy when setting a cache entry?
  • How does the client retrieve data and handle cache misses?
  • How does the system support explicit cache invalidation or TTL expiry notifications?
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Selection of a distributed cache with native encryption and eviction support (Redis Enterprise)
  • Support for multiple eviction policies including LRU, LFU, TTL, and ARC with dynamic configuration
  • Use of Redis Keyspace Notifications and Kafka for cache invalidation and backend sync
  • API design that allows specifying eviction policy and TTL per cache entry
  • Scalable cache cluster design with sharding and replication to meet 50M DAU and P99 < 200ms
Good to Have - 30%
  • Implementation details of ARC eviction as a Redis module
  • Monitoring setup with Prometheus and Grafana for eviction and latency metrics
  • Discussion of trade-offs between eviction policies for different workload patterns
Bonus - 10%
  • Advanced failure handling for cache node failures and fallback strategies
  • Security considerations for encryption key management in Redis Enterprise
Anti-patterns to Avoid
Using Memcached without encryption leads to data exposure and non-compliance with privacy regulations, risking user data leaks.
Hardcoding a single eviction policy reduces cache hit rates and adaptability to workload changes, causing inefficient caching.
Ignoring TTL expiry notifications causes stale cache data and inconsistent user experience due to outdated information.
Omitting eviction policy parameter in API reduces flexibility and forces uniform caching strategy, limiting optimization.
Lack of monitoring leads to undetected cache thrashing and SLA violations, impacting system reliability.
✅
Model Answer
▼ Reveal

This design uses Redis Enterprise for a scalable, encrypted caching layer supporting multiple eviction policies (LRU, LFU, TTL, ARC). It integrates Redis Keyspace Notifications with Kafka for cache invalidation and backend sync, and exposes APIs allowing clients to specify eviction policies and TTL per cache entry. The system scales via Redis clustering with sharding and replication, monitored by Prometheus and Grafana to ensure latency SLAs and eviction effectiveness.

Key Decisions
  • Use Redis Enterprise for native TLS encryption, clustering, and eviction policy support
  • Implement LRU and LFU using Redis built-in policies; TTL via Redis expiry; ARC via custom Redis module
  • Configure eviction policies dynamically per key namespace or prefix to optimize for workload patterns
  • Leverage Redis Keyspace Notifications to emit expiry events, consumed by Kafka to trigger cache invalidations
  • Design APIs to accept eviction_policy and TTL parameters to allow flexible cache entry management
  • Scale horizontally with Redis clustering using key hash sharding and replication for fault tolerance
  • Monitor cache metrics including hit/miss ratio, eviction rates, and latency with Prometheus and Grafana
  • Redis Enterprise with TLS encryption supports encrypted data at rest and in transit, meeting compliance.
  • Redis built-in LRU and LFU eviction policies provide mature, low-latency eviction mechanisms.
  • TTL eviction leverages Redis native expiry with Keyspace Notifications for event-driven invalidation.
  • Custom ARC eviction implemented as a Redis module enables adaptive caching for mixed workloads.
  • Redis clustering with key hash sharding scales horizontally to handle 50M DAU traffic with P99 < 200ms.
  • Kafka event streams integrate backend data changes with cache invalidation for eventual consistency.
  • API design includes eviction_policy parameter to dynamically select eviction per cache entry.
  • Prometheus and Grafana monitor cache hit ratios, eviction rates, and latency to maintain SLAs.

Practice

(1/5)
1. In a graph database request flow, at step 4 the query engine evaluates the traversal depth limit. What happens if the depth limit is reached before finding the target node?
easy
A. The traversal stops immediately and returns partial results up to that depth
B. The query engine throws an error and aborts the entire query
C. The query engine restarts traversal from the root node with a higher limit
D. The query engine continues traversing all remaining edges ignoring the limit

Solution

  1. Step 1: Understand traversal depth limit role

    The depth limit caps how far the traversal explores to avoid excessive computation.

  2. Step 2: Behavior at limit

    When the limit is reached, traversal stops and returns partial results found so far, not an error or restart.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Traversal depth limit stops traversal and returns partial results [check]
Hint: Traversal stops at depth limit, returns partial results [check]
Common Mistakes:
2. A system requires handling 1 million writes per second with guaranteed durability and ordered processing per user session. Which database technology best fits this requirement?
easy
A. Use a distributed log-based system like Kafka partitioned by user session
B. Use a relational database with row-level locking to ensure order and durability
C. Use an in-memory key-value store like Redis without persistence enabled
D. Use a NoSQL document store with eventual consistency and no ordering guarantees

Solution

  1. Step 1: Identify ordering and durability needs

    Relational DBs with row-level locking can't handle 1M writes/sec efficiently; Redis without persistence loses durability; NoSQL eventual consistency lacks ordering guarantees.

  2. Step 2: Recognize Kafka's partitioning for ordering

    Kafka partitions by user session ensure ordered processing and durability at high throughput.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Kafka partitions -> ordered, durable, high-throughput writes [check]
Hint: Kafka partitions preserve order and durability at scale [check]
Common Mistakes:
3. A live video streaming service requires minimal latency and can tolerate occasional packet loss. Which transport protocol is most appropriate?
easy
A. UDP, because it provides low latency without retransmission delays
B. SCTP, because it supports multi-streaming and multi-homing
C. TCP, because it guarantees packet delivery and ordering
D. HTTP over TLS, because it ensures secure and reliable delivery

Solution

  1. Step 1: Identify latency and loss tolerance requirements

    Live video streaming prioritizes low latency and can tolerate some packet loss, so retransmission delays are undesirable.

  2. Step 2: Match protocol characteristics

    UDP provides minimal overhead and no retransmission, fitting low latency needs. TCP guarantees delivery but adds delay due to retransmissions and congestion control.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    UDP suits low-latency, lossy streaming [check]
Hint: UDP trades reliability for speed in latency-sensitive apps [check]
Common Mistakes:
4. At 10x scale, which Kafka component is most lik
medium
A. Broker
B. Consumer
C. Producer
D. Zookeeper

Solution

  1. Step 1: Identify scaling bottleneck

    Consumers handle message processing and scale with load.

  2. Step 2: Assess component impact

    At 10x scale, consumers need to scale out to handle increased throughput.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Consumers scale with load; brokers and producers less impacted [check]
Hint: Consumers scale most at high load [OK]
Common Mistakes:
5. If the event queue that propagates write updates to read replicas fails, what is the immediate failure mode observed in the system?
medium
A. Writes to the primary database fail due to backpressure from the queue
B. Read replicas stop receiving updates and serve stale data indefinitely until manual intervention
C. The system automatically switches to synchronous replication to maintain consistency
D. Clients receive errors on read requests due to read replica unavailability

Solution

  1. Step 1: Identify role of event queue

    The event queue asynchronously propagates updates to read replicas.

  2. Step 2: Trace failure impact

    If the queue fails, read replicas stop receiving updates and serve stale data indefinitely.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Queue failure causes stale reads, no automatic failover [check]
Hint: Event queue failure -> stale reads until fixed manually [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