Katkat
Back

Plan Eviction and Cleanup for a Production Cache

NetflixSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

This problem tests the design of an in-memory caching system, focusing on memory management, eviction strategies, and concurrency control to ensure high performance and stability.

Problem Statement

You are tasked with building a thread-safe, process-local cache component in Java or Python. The cache must support put(key, value, ttl) and get(key). To ensure the application remains stable under high load and limited memory, design the component to be production-ready.

Requirements:

  1. Bounded Memory: Prevent OutOfMemory errors by strictly limiting the total number of entries.
  2. Eviction: When the cache reaches its capacity, implement an eviction policy to remove entries.
  3. Cleanup: Expired items must be cleaned up without blocking incoming requests.
  4. Concurrency: Multiple threads will read and write to the cache simultaneously.

Example Interface:

class BoundedCache:
    def __init__(self, capacity: int):
        # Initialize cache with max entries
        pass

    def put(self, key: str, value: Any, ttl_seconds: int):
        # Store value with a time-to-live
        pass

    def get(self, key: str) -> Any:
        # Return value if present and not expired, else None
        pass

Considerations:

  • How do you handle the trade-off between LRU (Least Recently Used) and LFU (Least Frequently Used) eviction?
  • What is the impact of using a global lock versus fine-grained locking or lock-free data structures?
  • How will you handle the background task for cleanup (e.g., active scanning vs. passive removal)?

Edge Cases:

  • A burst of writes filling the cache instantly.
  • High contention on specific keys.
  • Keys with very short vs. very long TTLs.

Hints

Hint 1

Consider using a combination of a Hash Map for O(1) lookups and a Doubly Linked List for tracking access order.

Hint 2

Instead of a global lock, explore using ConcurrentHashMap or striping locks to reduce contention during high-throughput scenarios.

Hint 3

For cleanup, evaluate the performance implications of a dedicated background thread versus a probabilistic approach that triggers during write operations.

Follow-up questions

  • How would you measure the cache's performance in production? Which metrics (e.g., hit rate, eviction rate, latency) are most critical?
  • If this cache needs to be distributed across multiple instances, how would you handle cache consistency or cache stampede (thundering herd) issues?
  • What changes are required if the cache needs to support a 'write-through' or 'write-back' strategy to an underlying database?