[PERFORMANCE]: Optimize LRU cache eviction (O(n) → O(1))

[crivetimihai]

Summary

The ResourceCache class in mcpgateway/cache/resource_cache.py uses min() with a key function to find the LRU entry for eviction, which scans all cache keys on every eviction - an O(n) operation. This should use OrderedDict for O(1) LRU tracking.

Impact

• CPU Overhead: Every cache.set() at capacity triggers full scan of all keys
• Latency Spikes: With max_size=1000, each eviction scans 1000 entries
• Scalability: Under high cache churn, eviction becomes a bottleneck

Operation	Current	Optimized
set() (needs eviction)	O(n)	O(1)

Affected Code

File: mcpgateway/cache/resource_cache.py
Line: 183

def set(self, key: str, value: Any) -> None:
    if len(self._cache) >= self.max_size:
        # O(n) SCAN to find LRU!
        lru_key = min(self._cache.keys(), key=lambda k: self._cache[k].last_access)
        del self._cache[lru_key]

Proposed Fix

Use collections.OrderedDict with move_to_end() and popitem(last=False):

from collections import OrderedDict

class ResourceCache:
    def __init__(self, max_size: int = 1000, ttl: float = 300.0):
        self._cache: OrderedDict[str, CacheEntry] = OrderedDict()

    def get(self, key: str) -> Optional[Any]:
        if key not in self._cache:
            return None
        entry = self._cache[key]
        if time.time() > entry.expires_at:
            del self._cache[key]
            return None
        self._cache.move_to_end(key)  # O(1) LRU update
        return entry.value

    def set(self, key: str, value: Any) -> None:
        if key in self._cache:
            self._cache.move_to_end(key)  # O(1)
        elif len(self._cache) >= self.max_size:
            self._cache.popitem(last=False)  # O(1) eviction!
        self._cache[key] = CacheEntry(value=value, expires_at=time.time() + self.ttl)

Acceptance Criteria

• min() scan removed from eviction logic
• Eviction uses OrderedDict.popitem(last=False) - O(1)
• LRU order maintained correctly
• TTL expiration still works
• All existing cache tests pass

Performance Comparison

Cache size 100:   Current=0.005s, Optimized=0.0005s, Speedup=10x
Cache size 1000:  Current=0.05s,  Optimized=0.0005s, Speedup=100x
Cache size 10000: Current=0.5s,   Optimized=0.0005s, Speedup=1000x

References

• Detailed analysis: todo/newperf/optimize-lru-cache-eviction.md
• Python OrderedDict

[brian-hussey]

Created PR #1628 above, using example code from above, it worked as expected.
I fleshed out the tests a bit more and added a __len__ function for the ResourceCache to be sure some of the tests are actually doing what was expected.

I considered a heap as well, but the OrderedDict covers the capacity issue with the queue we can easily manipulate on both ends, originally I was thinking the heap might work better for just the end but adding to it would then be slower.

With this approach the 'last_accessed' parameter of the CacheEntry is removed, but I added the step to update the expires_at parameter.