In-memory cache

The Problem

Your application hammers the database with the same 50 queries every second. Response times creep above 200ms, the DB connection pool saturates, and users start seeing timeouts. Profiling reveals 80% of reads hit the same 5,000 rows.

An in-memory cache eliminates redundant database round-trips by storing recently accessed data in a fast HashMap lookup. The cache holds a bounded number of entries, evicts the least useful ones when full, expires stale data after a configurable TTL, and tracks hit/miss statistics so operators know whether the cache is actually helping.

Design the core classes for an in-memory key-value cache that supports pluggable eviction policies (LRU, LFU), per-entry TTL, thread-safe concurrent access, capacity limits, and hit-rate monitoring.

Requirements

Clarifying Questions

Before jumping into class design, ask questions to turn the vague prompt into a concrete specification. Cover four areas: core actions, error handling, boundaries, and future extensions.

You: "What eviction policies should we support? Just LRU, or others like LFU?"

Interviewer: "Start with LRU. Design it so adding LFU or any custom policy is a one-class change."

Pluggable eviction. That screams Strategy pattern. The cache delegates eviction decisions to a policy object behind an interface.

You: "Should entries support per-entry TTL, a global TTL, or both?"

Interviewer: "Per-entry TTL. Some entries are valid for 30 seconds, others for 10 minutes. If no TTL is specified, the entry lives until evicted."

Per-entry TTL means each cache entry wraps the value with an expiration timestamp. We need both lazy checks (on access) and a background cleanup to prevent memory leaks from entries nobody reads.

You: "How should expired entries be removed? Lazily on access, eagerly via a background thread, or both?"

Interviewer: "Both. Lazy removal on get() keeps the happy path fast. A background sweeper catches entries that nobody reads before they expire."

Two expiry paths: synchronous on read, asynchronous via a scheduled thread. The sweeper interval should be configurable.

You: "Does the cache need to be thread-safe for concurrent reads and writes?"

Interviewer: "Yes. Multiple threads call get() and put() concurrently. Reads should not block each other."

Thread safety with concurrent reads. That points to a ReadWriteLock: shared read lock, exclusive write lock. ConcurrentHashMap alone is not enough because LRU ordering requires atomic read-then-reorder.

You: "Should the cache support a loader function for read-through semantics? For example, if a key is missing, automatically fetch from the database and cache the result."

Interviewer: "Not in the core design. Mention it as an extension."

Good. We keep the core simple: get returns Optional.empty() on miss. Read-through is an extension.

You: "Is capacity measured by entry count or memory footprint?"

Interviewer: "Entry count. Memory-based sizing is an extension."

Count-based capacity simplifies things. We track the number of entries and trigger eviction when size exceeds capacity.

You: "Should we expose cache statistics like hit rate, miss rate, and eviction count?"

Interviewer: "Yes. Operators need to know if the cache is effective."

Perfect. You have now clarified scope and ruled out unnecessary complexity.

Final Requirements

Functional Requirements:

1. get(key) returns the cached value or empty if absent/expired
2. put(key, value) and put(key, value, ttl) insert or update entries
3. invalidate(key) removes a single entry; clear() removes all entries
4. Evict the least valuable entry when capacity is exceeded (pluggable policy)
5. Expire entries after their TTL via lazy check on access and background sweep
6. Track hits, misses, and evictions for monitoring

Non-Functional Requirements:

1. Thread-safe for concurrent get/put from multiple threads
2. O(1) time complexity for get and put operations
3. Pluggable eviction via Strategy pattern (new policy = new class, no existing code changes)

Out of Scope:

• Read-through / write-through loader (extension)
• Memory-based capacity (entry count only)
• Distributed caching / network layer
• Persistence to disk

30-Second Design Summary

ConcurrentCache<K, V> owns the public API and delegates recency or frequency decisions to an EvictionPolicy. CacheEntry owns TTL metadata, while CacheStats owns observability counters. The LRU implementation combines a hash map with a doubly linked list for constant-time lookup and reordering. A ReadWriteLock protects compound store-plus-policy operations, System.nanoTime() makes expiry monotonic, and a background sweeper removes expired entries that are never read.

5-Minute Walkthrough

1. Set the boundary. The core is an in-process, count-bounded cache with get, put, invalidation, TTL, eviction, and statistics. Loaders, persistence, memory weighting, and distribution are extensions.
2. Separate state. CacheEntry answers whether a value is expired; the eviction policy answers which key should leave; configuration and statistics remain independent value/services.
3. Trace a read. Acquire the read-side protection needed for a consistent lookup, check TTL, record a hit or miss, and notify the policy of access. Expired entries are removed through the write path.
4. Trace a write. Insert or replace the entry, update policy metadata, then evict until the hard entry-count limit is satisfied. Replacing a key must not leave duplicate policy nodes.
5. Explain operations. Lazy expiry keeps reads simple, the sweeper bounds stale memory, and a new policy implements the same strategy contract. The lock scope is the important correctness boundary, not the choice of ConcurrentHashMap alone.

Example Inputs and Outputs

Scenario 1: Basic put and get

• Input: cache.put("user:42", userData) then cache.get("user:42")
• Expected: Returns Optional.of(userData) and increments hit counter
• Why: Validates the core store-and-retrieve path

Scenario 2: TTL expiration

• Input: cache.put("session:abc", session, Duration.ofSeconds(30)), wait 31 seconds, cache.get("session:abc")
• Expected: Returns Optional.empty() and increments miss counter
• Why: Validates per-entry TTL with lazy expiration on access

Scenario 3: LRU eviction at capacity

• Input: Cache capacity is 3. Put keys A, B, C. Get A (moves it to most-recent). Put D (triggers eviction).
• Expected: Key B is evicted (least recently used). Keys A, C, D remain.
• Why: Validates LRU ordering where get() counts as "use"

Scenario 4: Cache statistics

• Input: 80 hits and 20 misses
• Expected: stats.hitRate() returns 0.80
• Why: Validates hit-rate calculation for monitoring dashboards

Try It Yourself

---

Step 1: Identify Core Entities

Start by asking: what are the main "things" in this system? Look at your requirements for nouns. A cache stores entries, enforces a capacity limit, uses an eviction policy, and reports statistics. Each noun maps to a class with a single, clear responsibility.

A common mistake is stuffing everything (eviction logic, TTL checks, stats tracking, thread safety) into one giant Cache class. That works for a toy example, but the design benefits from clear separation of concerns. Each class should have one reason to change.