LRU and TTL Caching in Python Using Cachetools

This article examines how the Python cachetools library internally implements Least Recently Used (LRU) and Time-to-Live (TTL) caching algorithms. It covers the underlying data structures—including hash maps, doubly linked lists, and time-ordered tracking—that power LRUCache and TTLCache, explaining how each handles cache hits, cache misses, and key eviction in constant or near-constant time.

Core Architecture: MutableMapping

All cache implementations in cachetools derive from collections.abc.MutableMapping. This allows cache objects to behave like standard Python dictionaries while intercepting operations such as __getitem__, __setitem__, and __delitem__ to enforce capacity limits and eviction policies.

How LRUCache Implements Least Recently Used

The Least Recently Used (LRU) algorithm discards the items that have not been accessed for the longest duration when the cache reaches its maximum size (maxsize).

Data Structures

LRUCache maintains \(O(1)\) time complexity for lookups, insertions, and updates by combining two core structures:

1. A Hash Map: A standard Python dictionary maps cache keys directly to their values, providing constant-time lookups.
2. A Doubly Linked List: An internal chain of link objects tracks usage order. Each link references its previous and next siblings, as well as the cache key. A root sentinel node connects the head (least recently used) and tail (most recently used).

State Transitions

• On Cache Hit (__getitem__): The key is retrieved from the dictionary. Concurrently, the corresponding link node is unlinked from its current position in the doubly linked list and spliced immediately before the root node, marking it as the most recently used.
• On Insert/Update (__setitem__): If the key exists, its value is updated, and its link moves to the tail. If the key is new, a new link node is appended to the tail.
• On Eviction: Before or after insertion, LRUCache checks if the current size exceeds maxsize. If capacity is exceeded, it initiates popitem(). The algorithm removes the node immediately following the root sentinel (the LRU head) from both the linked list and the internal dictionary.

How TTLCache Implements Time-to-Live

The Time-to-Live (TTL) algorithm evicts entries that exceed a defined lifespan (ttl), while also enforcing a maximum capacity limit using an LRU-like fallback.

Data Structures

TTLCache builds on the foundations of LRUCache but introduces temporal tracking:

1. Value Mapping: Stores the key-value pairs.
2. Access Order Tracking: Tracks access recency using a doubly linked list, similar to LRUCache.
3. Expiration Queue: Maintains a secondary doubly linked list or ordered chain of expiration records tracking (key, expires_at) pairs, ordered monotonically by expiration time.
4. Monotonic Timer: Uses time.monotonic (or a custom timer function) to avoid issues caused by system clock adjustments.

State Transitions and Expiration Mechanics

TTLCache applies both proactive and lazy eviction strategies to minimize overhead while keeping memory usage bounded:

• Clock Evaluation: Every read and write operation evaluates the current time against stored expiration timestamps using timer().
• Lazy Eviction on Read (__getitem__): When a key is requested, TTLCache checks whether current_time >= expires_at. If the item has expired, it is deleted immediately, and a KeyError is raised (resulting in a cache miss). If valid, its access order is refreshed.
• Proactive Purging on Write (__setitem__): Before adding a new item, TTLCache calls an internal expire() routine. This walks the expiration queue starting from the oldest timestamp, removing all keys where expires_at <= current_time.
• Capacity Eviction: If the cache remains full after purging expired keys, it falls back to the access-order links and evicts the least recently used valid item, ensuring the collection never exceeds maxsize.

Basic Usage Example

The following code illustrates how to instantiate and use both cache types:

import time
from cachetools import LRUCache, TTLCache

# LRU Cache: capacity of 2 items
lru = LRUCache(maxsize=2)
lru["a"] = 1
lru["b"] = 2
_ = lru["a"]      # "a" becomes most recently used
lru["c"] = 3      # Evicts "b"
assert "b" not in lru
assert "a" in lru

# TTL Cache: capacity of 2 items, 1-second lifetime
ttl = TTLCache(maxsize=2, ttl=1)
ttl["x"] = 100
assert ttl["x"] == 100
time.sleep(1.1)   # Wait for expiration
assert "x" not in ttl

Both classes guarantee predictable memory bounds and algorithmic efficiency by pairing Python's native hash tables with managed pointer chains.