The Duplicate-Key Cache
A service stores user profiles in a hash map keyed by user ID, with a least-recently-used eviction policy capped at 10,000 entries. It also keeps a separate sorted list of user IDs for range queries. On profile update, code writes the hash map, then removes and reinserts the ID in the sorted list, then updates the database. Under load, two bugs appear: (1) occasionally a profile read returns stale data, and (2) the sorted list and hash map disagree -- some IDs appear in the list but not the map. The update path is not atomic and runs on multiple threads. A proposed fix is to wrap the whole update in one global lock. Profiling shows updates are 30% of traffic and reads are 70%, and the service is read-latency sensitive.
1. Explain how the two data structures can diverge and why reads can be stale, then evaluate the global-lock proposal.
Read the worked answer
The two structures are updated as separate steps with no atomicity, so any interleaving or failure between steps leaves them inconsistent. If a thread removes an ID from the sorted list and is preempted before reinserting, a concurrent reader sees the list without the ID while the map still has it -- or the reverse depending on order. A crash or exception mid-update leaves a permanent divergence. The 'in list but not in map' symptom points to ordering: the list is updated before the map (or eviction removes from the map without touching the list). Eviction is a likely culprit: when the LRU cap evicts an entry, does the code also remove it from the sorted list? If not, the list accumulates ghost IDs.
Stale reads come from the same non-atomicity plus the database write being last. A reader can hit the cache after the map is updated but before the database write commits, or read a value that a concurrent update is midway through replacing. Without a version number or read-your-writes guarantee, readers see torn state.
A single global lock makes every operation mutually exclusive, which does fix the races -- but it serializes 100% of traffic, including the 70% that are reads, on one mutex. At read-latency-sensitive load this becomes the bottleneck and can be worse than the bug. It also does not fix eviction/list consistency unless the eviction path also takes the lock.
Better: use a read-write lock so reads proceed concurrently; make the map and list update under the write lock as one critical section; fix eviction to remove from both structures; and add a version or timestamp so readers can detect and reject stale entries. Alternatively, derive the sorted view from the map rather than maintaining two copies, eliminating the divergence class entirely.
2. The LRU cap is 10,000 but the working set is estimated at 40,000 active users. What are the consequences and what would you change?
Read the worked answer
With a 10,000-entry cap and a 40,000-user working set, the cache can hold at most a quarter of active users at once. Under LRU, a scan or a burst across many users evicts entries that will be needed again soon, so hit rate collapses toward the ratio of cap to working set -- roughly 25% at best, lower under skewed access. The result is a high miss rate, more database load, and higher read latency, which is exactly what the service is sensitive to. It also means the cache is doing little work for its complexity.
Consequences to check:
- Measure the actual hit rate and miss latency; do not assume. If access is heavily skewed (a few hot users dominate), a small cache can still do well -- but 10,000 vs 40,000 with uniform access will not.
- Eviction churn increases write-lock contention on the update path, worsening the race symptoms.
- Ghost IDs in the sorted list become more likely as eviction runs more often.
Changes:
- Size the cache from measurement: target a hit rate (e.g. 90%+) and set capacity from the working-set distribution, not a round number.
- Consider a better eviction policy for skewed access (e.g. segmented LRU or a frequency-aware policy) so hot entries survive scans.
- Reduce the working set by caching only profiles that are actually read repeatedly, or by adding a short-TTL layer for the rest.
- Ensure eviction updates both structures atomically, as above.
Document the assumption: if the 40,000 estimate is wrong, re-measure before resizing, since memory cost scales with capacity.