LRU cache

A least recently used (LRU) cache evicts the entry whose last access was longest ago when it needs room for a new one. A cache hit returns the stored value and makes that entry the most recently used. In a pricing service, this can save repeated fits of the same volatility surface while bounding how many surfaces are kept. When the stored values are function results, LRU is one way to bound a memoisation cache. Python’s lru_cache documentation

Start with an empty cache that holds two entries. A pricing service requests surfaces for three fictional market snapshots in the order A, B, A, C, B. Assume every miss loads and stores a value and entries can leave only through capacity eviction. The first two requests fill the cache. The third hits A and moves it to the most recently used end. C then displaces B, even though A entered the cache first. The last request must load B again and evicts A, leaving C then B in order of last use.

One exact implementation combines a hash table from key to node with a doubly linked list of those nodes in recency order. On a hit, the table locates the node and the list moves it to the newest end by changing a few links. When space runs out, the oldest node is already at the other end. Remove it from both structures. The list work takes $O(1)$ per move or eviction. With well-distributed hashes, a bounded load factor and constant-cost key hashing and comparison, the combined bookkeeping is expected amortised $O(1)$ per request. Loading or computing a value on a miss adds its own cost. The bounded cache in CPython 3.14 uses this dictionary-and-list design. CPython 3.14 implementation

In Python, functools.lru_cache(maxsize=2) limits a decorated function to two cached results. That setting counts entries, so two large surfaces may still use substantial memory. Redis provides a different implementation. Its allkeys-lru policy uses a memory threshold and samples candidates, so it can evict a key other than the globally least recently used one. Python’s lru_cache documentation · Redis key eviction

If the input quotes are corrected, a frequently requested fit keyed only by instrument can stay in cache and serve the old result repeatedly. LRU ranks access times. A time to live (TTL) makes an entry expire after a configured interval. Invalidation discards a result when its inputs change, which can happen before that interval elapses. Another design includes the market-data snapshot revision and the fitting configuration in the key. A corrected snapshot gets a new revision, so its request misses and computes a new fit while the older revision can still be retrieved by its own key. Redis EXPIRE documentation · Python’s lru_cache documentation