LRU/LFU/FIFO Cache Implementation Validator

[
  {
    "op": "put",
    "key": "cfg-001",
    "value": {
      "key": "cfg-1",
      "value": "enabled-0"
    },
    "expected_evicted_key": null
  },
  {
    "op": "put",
    "key": "cfg-002",
    "value": {
      "key": "cfg-2",
      "value": 11
    },
    "expected_evicted_key": null
  },
  {
    "op": "put",
    "key": "cfg-003",
    "value": {
      "key": "cfg-3",
      "value": "enabled-2"
    },
    "expected_evicted_key": null
  },
  {
    "op": "get",
    "key": "cfg-001",
    "expected_result": "hit",
    "expected_value": {
      "key": "cfg-1",
      "value": "enabled-0"
    }
  },
  {
    "op": "put",
    "key": "cfg-004",
    "value": {
      "key": "cfg-4",
      "value": 13
    },
    "expected_evicted_key": "cfg-002"
  },
  {
    "op": "get",
    "key": "cfg-002",
    "expected_result": "miss"
  },
  {
    "op": "get",
    "key": "cfg-003",
    "expected_result": "hit",
    "expected_value": {
      "key": "cfg-3",
      "value": "enabled-2"
    }
  },
  {
    "op": "put",
    "key": "cfg-001",
    "value": {
      "updated": true,
      "marker": "cfg-001-v2"
    },
    "expected_evicted_key": null
  },
  {
    "op": "get",
    "key": "cfg-001",
    "expected_result": "hit",
    "expected_value": {
      "updated": true,
      "marker": "cfg-001-v2"
    }
  },
  {
    "op": "check_store",
    "key": "cfg-002",
    "expected_present": true,
    "expected_value": {
      "key": "cfg-2",
      "value": 11
    }
  },
  {
    "op": "check_store",
    "key": "cfg-never-used",
    "expected_present": false
  }
]

{
  "capacity": 3
}

# write-through cache -- config-value cache, capacity 3
class Cache:
    def __init__(self):
        self._capacity = 3
        self._value = {}
        self._last_used = {}
        self._seq = 0
        self._store = {}  # separate, permanent backing store -- never pruned by eviction

    def _bump(self, key):
        self._seq += 1
        self._last_used[key] = self._seq

    def get(self, key, now):
        if key not in self._value:
            return (False, None)
        self._bump(key)
        return (True, self._value[key])

    def get_from_store(self, key):
        if key not in self._store:
            return (False, None)
        return (True, self._store[key])

    def put(self, key, value, now, ttl_seconds=None):
        self._store[key] = value
        if key in self._value:
            self._value[key] = value
            self._bump(key)
            return None
        evicted = None
        if len(self._value) >= self._capacity:
            evicted = min(self._last_used, key=lambda k: self._last_used[k])
            del self._value[evicted]
            del self._last_used[evicted]
        self._value[key] = value
        self._bump(key)
        return evicted

A config-value cache in front of a slow, centralized config-service call, keyed by config key, for a small backend service.

Write-through cache, capacity 3: identical eviction semantics to LRU (capacity, LRU-ordered, no ties); every put (insert or update) synchronously writes (key, value) into a separate, permanent backing store that a capacity-triggered cache eviction never prunes; get() consults only the in-memory cache layer, never the backing store.