File Cache

Overview

Build a cache that holds the contents of recently read files in memory, so repeated reads skip the disk. The cache has a fixed capacity; when it is full, the least-recently-used entry is evicted to make room. Many threads read through the cache at once, so its bookkeeping must be thread-safe.

The two pieces are an LRU policy (track recency, evict the coldest entry) and correct concurrency (lookups, inserts, and evictions all mutate shared state). A read also has to stay fresh: if the underlying file changed on disk, the cached copy must be invalidated rather than served stale.

Interfaces

class FileCache:
    def __init__(self, capacity):
        self._capacity = capacity
        self._map = {}                    # path -> node (value + metadata)
        self._order = DoublyLinkedList()  # recency order, MRU at head
        self._lock = Lock()

    def read(self, path):
        """Return the file's contents, from cache if present and still fresh."""
        ...

    def invalidate(self, path):
        """Drop a path from the cache."""
        ...

    def _evict(self):
        """Remove the least-recently-used entry when over capacity."""
        ...

A hash map gives O(1) lookup; a doubly linked list ordered by recency gives O(1) move-to-front and O(1) eviction of the tail. On a hit, move the node to the head; on a miss, read from disk, insert at the head, and evict the tail if over capacity.

Inputs and outputs

• Input: read(path) calls from many threads, plus a fixed capacity.
• Output: file contents, served from memory on a hit and from disk on a miss; the cache never holds more than capacity entries.

Requirements

• Lookups, inserts, and evictions are all thread-safe.
• Eviction always removes the least-recently-used entry.
• A cached entry is invalidated if the file's modification time changes.
• A cache miss reads the file once and shares the result; concurrent misses for the same path should not each re-read it redundantly.

Examples

cache = FileCache(capacity=2)

cache.read("a.txt")   # miss -> reads disk, caches a.txt
cache.read("b.txt")   # miss -> caches b.txt
cache.read("a.txt")   # hit  -> a.txt is now most-recently-used
cache.read("c.txt")   # miss -> evicts b.txt (least recently used)

Follow-ups

• The single lock is a bottleneck. How would you shard the cache so different paths contend on different locks?

• Entries vary wildly in size. How would you cap the cache by total bytes instead of a fixed entry count?

• How would a TTL change things — should an entry expire on time even if the file on disk never changed?

• And more...