File Cache

Build a cache that holds the contents of recently read files in memory, so repeated reads skip the disk.

Please notice the cache has a fixed capacity; when it is full, the least-recently-used entry is evicted to make room.

Also many threads may read through the cache at once, so the bookkeeping must be thread-safe.

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."""
        ...

So two pieces:

1), LRU policy (track recency, evict the coldest entry)

2), correct concurrency (lookups, inserts, and evictions all mutate shared state).

Also the read also need to stay fresh: if the underlying file changed on disk, the cached copy must be invalidated rather than served stale.

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

• Let's say the entries vary wildly in size. What's the solution? How about cap the cache by total bytes? Fixed entry count?

• TTL: should an entry expire on time even if the file on disk never changed?

• And more followups and more levels...