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
Design and compare cache eviction policies for large-scale systems with 2B DAU
mediumCachingFreq: common
⚙️
Functional Requirements
  • Support multiple cache eviction policies: LRU, LFU, TTL, ARC
  • Allow dynamic selection of eviction policy per cache use case
  • Provide sub-millisecond cache lookup and eviction operations
  • Expose metrics for cache hit ratio and eviction counts
  • Support distributed cache clusters with consistent eviction behavior
  • Enable TTL-based automatic expiration without manual cleanup
📊
Non-Functional Requirements
  • Handle 2 billion daily active users (DAU)
  • Support peak write QPS of 925,000 with 100ms P99 latency for cache operations
  • Achieve 99.99% availability for cache reads and writes
  • Eviction decisions must not block cache reads or writes
  • Cache storage must scale horizontally with linear performance
❓
Clarifying Questions to Ask
  • What is the expected cache size per node and total cluster size?
  • Are eviction policies configurable per cache key namespace or global?
  • What is the typical object size and variability in cache entries?
  • Is the cache read-heavy, write-heavy, or balanced workload?
  • Are there SLAs on eviction latency or maximum staleness?
  • Should the system support multi-tenant isolation for eviction policies?
Out of Scope
✗ Design of the underlying persistent storage or database
✗ Cache warming or preloading strategies
✗ Security and encryption of cached data
✗ Cache coherence protocols for multi-region consistency
📌
Assumptions
  • 2 billion DAU
  • 40 cache operations per user per day (reads + writes)
  • Average cache entry size 100 bytes
  • Retention period for cache entries: 1 day
⚡
QPS Calculation
write qps2B × 40 / 86400 ≈ 925,926 writes/sec
peak write qpsAssuming 3× peak factor: 925,926 × 3 ≈ 2.78M writes/sec
read qpsAssuming 10× reads per write: 9.25M reads/sec
💾
Storage Estimate
daily storage2B × 40 × 100 bytes = 8 TB/day
retention storage8 TB × 1 day = 8 TB
with replication8 TB × 3 replicas = 24 TB total
🖥️
Server Estimate
cache nodesAssuming 64 GB RAM per node, 8 TB / 64 GB ≈ 125 nodes
write frontendTo handle 2.78M writes/sec, assuming 10K writes/sec per node, need ~278 write nodes
🏗️
Architecture Diagram
Architecture Diagram
          +----------------------+
          |   Client Applications |
          +----------+-----------+
                     |
          +----------v-----------+
          |  Cache Write Frontend |
          +----------+-----------+
                     |
          +----------v-----------+
          |  Distributed Cache    |
          |  Cluster (Redis +    |
          |  Custom Eviction)    |
          +----------+-----------+
                     |
          +----------v-----------+
          |  Metrics & Monitoring |
          +----------------------+
🧩
Components
Client Applications
Generate cache read/write requests with policy hints
Why thisClients embed eviction policy hints to optimize cache usage per workload using Redis clients
Why notCentralized policy decision would add latency and complexity; Redis clients allow local hints
Cache Write Frontend
Load balances writes and routes requests to cache nodes
Why thisStateless frontends scale horizontally and isolate clients from cache internals using NGINX or Envoy
Why notDirect client-to-cache node writes cause hot partitions and uneven load; frontends prevent hotspots
Distributed Cache Cluster (Redis + Custom Eviction)
Store cached data with eviction policies: LRU, LFU, TTL, ARC
Why thisRedis supports native TTL and LFU; custom ARC implemented for adaptive eviction
Why notMemcached lacks LFU and TTL support; Cassandra too slow for sub-ms cache
Eviction Policy Manager
Implements eviction algorithms and tracks usage metadata
Why thisSeparates eviction logic from storage for modularity and easier policy updates using custom service
Why notEmbedding eviction in storage layer limits flexibility and complicates scaling
Metrics & Monitoring
Collects cache hit/miss rates, eviction counts, and latency metrics
Why thisPrometheus + Grafana provide real-time observability and alerting
Why notCustom monitoring lacks ecosystem and scalability for 2B DAU scale
🔄
Data Flow
1
Client Applications → Cache Write Frontend
Send cache read/write request with eviction policy hint
Policy hint guides eviction choice per key namespace
2
Cache Write Frontend → Distributed Cache Cluster
Route request to appropriate cache node based on consistent hashing
Ensures even load and data locality
3
Distributed Cache Cluster → Eviction Policy Manager
Update usage metadata (access frequency, recency) for eviction
Supports LRU, LFU, ARC algorithms
4
Eviction Policy Manager → Distributed Cache Cluster
Trigger eviction of stale or low-priority entries
Eviction respects TTL and policy-specific heuristics
5
Distributed Cache Cluster → Metrics & Monitoring
Emit cache hit/miss and eviction metrics
Enables SLA tracking and tuning
6
Distributed Cache Cluster → Client Applications
Return cached data or miss response
Sub-100ms P99 latency target
🗄️
CacheEntries
PK: cache_namespace
cache_namespace (string)cache_key (string)value (blob)last_access_time (timestamp)frequency_count (int)ttl_expiry (timestamp)
Stores cache entries with metadata for eviction policies
🗄️
EvictionMetrics
PK: cache_namespace
cache_namespace (string)metric_timestamp (timestamp)hit_count (int)miss_count (int)eviction_count (int)
Stores periodic metrics for cache performance monitoring
🔌
GET
GetCacheEntry
Request
{
  "parameters": [
    "namespace",
    "key"
  ],
  "headers": [
    "Eviction-Policy-Hint (optional)"
  ]
}
Response
{
  "status": "200 OK or 404 Not Found",
  "body": {
    "value": "cached data or null"
  }
}
Fetches cache entry with optional eviction policy hint for adaptive caching
🔌
PUT
PutCacheEntry
Request
{
  "parameters": [
    "namespace",
    "key"
  ],
  "body": {
    "value": "data to cache"
  },
  "headers": [
    "Eviction-Policy-Hint (optional)",
    "TTL (optional)"
  ]
}
Response
{
  "status": "201 Created or 400 Bad Request"
}
Inserts or updates cache entry with optional TTL and eviction policy hint
🔌
GET
GetCacheMetrics
Request
{
  "parameters": [
    "namespace"
  ]
}
Response
{
  "status": "200 OK",
  "body": {
    "hit_count": "int",
    "miss_count": "int",
    "eviction_count": "int",
    "timestamp": "timestamp"
  }
}
Retrieves cache performance metrics for given namespace

Practice

(1/5)
1. A company needs to store large amounts of unstructured data like images and videos with metadata accessible via HTTP APIs. Which storage type best fits this use case?
easy
A. Object storage, because it stores data as objects with metadata and supports HTTP access.
B. Block storage, because it provides low-latency random access to raw data blocks.
C. File storage, because it offers hierarchical directories and POSIX file system semantics.
D. In-memory storage, because it offers the fastest access to large files.

Solution

  1. Step 1: Identify storage needs for unstructured data with metadata

    Object storage stores data as objects with customizable metadata and supports HTTP APIs, ideal for images/videos.

  2. Step 2: Eliminate other storage types

    Block storage is low-level and lacks metadata support; file storage is optimized for hierarchical file systems but less scalable for massive unstructured data; in-memory storage is volatile and unsuitable for large persistent files.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Object storage = scalable unstructured data + metadata + HTTP [check]
Hint: Object storage = objects + metadata + HTTP access [check]
Common Mistakes:
2. A distributed system needs to enforce a global rate limit of 1000 requests per second across multiple API servers. Which component is best suited to maintain a consistent count of requests in real-time?
easy
A. Use a message queue to buffer requests and count them asynchronously
B. Use a local in-memory counter on each API server and aggregate periodically
C. Use a relational database with row-level locking for counting requests
D. Use a centralized Redis counter with atomic increment operations

Solution

  1. Step 1: Identify the need for a consistent global count

    Local counters aggregated periodically (Use a local in-memory counter on each API server and aggregate periodically) cause stale counts and race conditions, failing real-time enforcement.

  2. Step 2: Evaluate Redis atomic increments

    Redis supports atomic INCR commands ensuring consistent, real-time global counters across distributed servers.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Redis atomic counters ensure global consistency and low latency [check]
Hint: Centralized atomic counters ensure global consistency [check]
Common Mistakes:
3. For billing in a multi-tenant SaaS platform, which architecture best supports accurate usage tracking with minimal latency impact on tenant requests?
medium
A. Asynchronous event-driven usage aggregation via a message queue and batch processing
B. Embedding billing logic directly in the tenant service to update counters in-memory
C. Periodic polling of tenant usage logs by the billing service every hour
D. Synchronous billing updates on every tenant API call to the billing database

Solution

  1. Step 1: Analyze latency and accuracy trade-offs

    Synchronous updates (Synchronous billing updates on every tenant API call to the billing database) add latency; polling (Periodic polling of tenant usage logs by the billing service every hour) delays billing data; in-memory counters (Embedding billing logic directly in the tenant service to update counters in-memory) risk data loss.

  2. Step 2: Evaluate asynchronous event-driven approach

    Asynchronous event-driven usage aggregation via a message queue and batch processing decouples billing from tenant requests, ensuring accurate aggregation with minimal latency impact.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Event-driven async billing -> accurate, low-latency tenant requests [check]
Hint: Async event-driven billing decouples latency [check]
Common Mistakes:
4. At 10x scale, which component in a synchronous quorum replication system is most likely to become the bottleneck and why?
hard
A. Quorum coordinator because it must wait for majority acknowledgments synchronously
B. Storage nodes because disk I/O saturates under high write volume
C. Network links because replication traffic grows linearly with replicas
D. Client-side libraries because they block waiting for acknowledgments

Solution

  1. Step 1: Identify synchronous quorum coordinator role

    Coordinator waits synchronously for majority acks, causing latency and throughput limits.

  2. Step 2: Compare other components' scaling challenges

    Storage nodes and network scale better; client-side blocking is per client, less centralized.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Coordinator sync wait limits throughput at scale [check]
Hint: Coordinator sync wait blocks throughput first at scale [check]
Common Mistakes:
5. At 10x traffic scale, which component in a multi-CDN architecture is most likely to become the first bottleneck, and why?
hard
A. Origin server, because it must serve all cache misses and cannot be horizontally scaled easily
B. Client DNS resolvers, because they cache CDN IPs and cannot update fast enough to reflect CDN health changes
C. Edge caches, because they have limited storage and cannot handle increased request volume
D. Global Traffic Manager, because it maintains stateful health checks and routing decisions for millions of users

Solution

  1. Step 1: Identify scaling challenges of Global Traffic Manager

    It maintains real-time health and routing state for all CDNs and users, which grows with traffic scale.

  2. Step 2: Compare other components

    Origin servers (A) can be scaled horizontally with caching. Edge caches (C) scale by adding nodes. Client DNS (D) caching delays but does not bottleneck traffic flow.

  3. Step 3: Conclude bottleneck

    Global Traffic Manager's centralized stateful routing logic is hardest to shard and scale linearly.

  4. Final Answer:

    Option D -> Option D

  5. Quick Check:

    Global Traffic Manager stateful routing -> first bottleneck at 10x scale [check]
Hint: Global Traffic Manager stateful routing limits scale first [OK]
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