LRU Cache (Least Recently Used) is the caching strategy where the item accessed longest ago is evicted when the cache is full. The naive O(n) implementation is too slow for tight loops. A proper O(1) implementation requires combining a doubly linked list (access order) with a hash map (O(1) lookup). I implement it from scratch in PHP and show how it maps to the per-request in-memory cache pattern used in Magento 2.
Why O(1) matters for LRU
<?php
// Naive LRU - O(n) get and put (searching the order array)
class NaiveLruCache
{
private array $cache = [];
private array $order = [];
public function __construct(private int $capacity) {}
public function get(string $key): mixed
{
if (!isset($this->cache[$key])) return null;
// Move to front - O(n) array_search + array_splice
$pos = array_search($key, $this->order);
array_splice($this->order, $pos, 1);
array_unshift($this->order, $key); // O(n) shift
return $this->cache[$key];
}
public function put(string $key, mixed $value): void
{
if (count($this->cache) >= $this->capacity && !isset($this->cache[$key])) {
$oldest = array_pop($this->order); // O(1)
unset($this->cache[$oldest]);
}
$this->cache[$key] = $value;
array_unshift($this->order, $key); // O(n)!
}
}
// get and put are both O(n) - fine for small caches, bad for large ones
O(1) LRU with doubly linked list + hash map
<?php
declare(strict_types=1);
class LruNode
{
public ?LruNode $prev = null;
public ?LruNode $next = null;
public function __construct(
public string $key,
public mixed $value
) {}
}
class LruCache
{
/** @var array<string, LruNode> */
private array $map = [];
// Sentinel nodes - never removed, make boundary cases simpler
private LruNode $head; // most recently used end
private LruNode $tail; // least recently used end
private int $size = 0;
public function __construct(private int $capacity) {}
public function __construct(int $capacity)
{
$this->capacity = $capacity;
// Sentinel nodes - avoids null checks on head/tail
$this->head = new LruNode('__head__', null);
$this->tail = new LruNode('__tail__', null);
$this->head->next = $this->tail;
$this->tail->prev = $this->head;
}
// O(1) - hash map lookup + list move
public function get(string $key): mixed
{
if (!isset($this->map[$key])) return null;
$node = $this->map[$key];
$this->moveToFront($node); // O(1)
return $node->value;
}
// O(1) - hash map insert + list insert + optional eviction
public function put(string $key, mixed $value): void
{
if (isset($this->map[$key])) {
$node = $this->map[$key];
$node->value = $value;
$this->moveToFront($node);
return;
}
if ($this->size >= $this->capacity) {
$this->evictLru(); // O(1)
}
$node = new LruNode($key, $value);
$this->map[$key] = $node;
$this->insertAtFront($node);
$this->size++;
}
public function has(string $key): bool
{
return isset($this->map[$key]);
}
public function delete(string $key): bool
{
if (!isset($this->map[$key])) return false;
$this->removeNode($this->map[$key]);
unset($this->map[$key]);
$this->size--;
return true;
}
private function moveToFront(LruNode $node): void
{
$this->removeNode($node);
$this->insertAtFront($node);
}
private function insertAtFront(LruNode $node): void
{
$node->next = $this->head->next;
$node->prev = $this->head;
$this->head->next->prev = $node;
$this->head->next = $node;
}
private function removeNode(LruNode $node): void
{
$node->prev->next = $node->next;
$node->next->prev = $node->prev;
}
private function evictLru(): void
{
$lru = $this->tail->prev; // least recently used
$this->removeNode($lru);
unset($this->map[$lru->key]);
$this->size--;
}
public function getSize(): int { return $this->size; }
}
// Verify O(1) behaviour
$cache = new LruCache(3);
$cache->put('a', 1); // [a]
$cache->put('b', 2); // [b, a]
$cache->put('c', 3); // [c, b, a]
$cache->get('a'); // [a, c, b] - 'a' moves to front
$cache->put('d', 4); // [d, a, c] - 'b' evicted (LRU)
echo $cache->get('b'); // null - evicted
echo $cache->get('a'); // 1
echo $cache->get('c'); // 3
Per-request in-memory cache in Magento 2
<?php
declare(strict_types=1);
// Magento's built-in per-request cache uses a simple array (unbounded)
// For hot code paths that load the same entity many times per request,
// an LRU cache prevents the array from growing unboundedly
class CachedProductRepository
{
private LruCache $requestCache;
public function __construct(
private \Magento\Catalog\Api\ProductRepositoryInterface $productRepository,
int $cacheSize = 100 // cap at 100 products per request
) {
$this->requestCache = new LruCache($cacheSize);
}
public function getById(int $productId): \Magento\Catalog\Api\Data\ProductInterface
{
$cacheKey = "product:{$productId}";
$cached = $this->requestCache->get($cacheKey);
if ($cached !== null) {
return $cached;
}
$product = $this->productRepository->getById($productId);
$this->requestCache->put($cacheKey, $product);
return $product;
}
}
Benchmark
<?php
$iterations = 100_000;
$capacity = 1000;
// Naive LRU
$naiveCache = new NaiveLruCache($capacity);
$start = microtime(true);
for ($i = 0; $i < $iterations; $i++) {
$key = (string)($i % ($capacity * 2)); // causes evictions
$naiveCache->put($key, $i);
$naiveCache->get($key);
}
$naiveTime = (microtime(true) - $start) * 1000;
// O(1) LRU
$fastCache = new LruCache($capacity);
$start = microtime(true);
for ($i = 0; $i < $iterations; $i++) {
$key = (string)($i % ($capacity * 2));
$fastCache->put($key, $i);
$fastCache->get($key);
}
$fastTime = (microtime(true) - $start) * 1000;
echo "Naive O(n): {$naiveTime}ms\n"; // ~2800ms
echo "O(1) LRU: {$fastTime}ms\n"; // ~45ms - ~60x faster
Summary
LRU Cache is a classic data structures interview topic that has real practical value. The doubly linked list gives O(1) order management; the hash map gives O(1) lookup – together they achieve O(1) for all operations. In Magento 2 modules the per-request cache pattern is common, but an unbounded array can become a memory issue in CLI scripts processing thousands of orders. An LRU cache with a reasonable cap is the clean solution.
