LRU Cache – O(1) implementacja z HashMap + lista dwukierunkowa, per-request cache

LRU (Least Recently Used) Cache to jeden z klasycznych problemów algorytmicznych z rozmów rekrutacyjnych, ale też realna struktura danych używana w systemach produkcyjnych. Redis domyślnie używa wariantu LRU do eksmisji kluczy. PHP OPcache stosuje LRU. Pokazuję jak zaimplementować LRU Cache w O(1) dla get i put, używając hashmapy i listy dwukierunkowej – i gdzie to ma zastosowanie w e-commerce.

Problem który rozwiązuje LRU Cache

Masz ograniczoną pamięć i chcesz cachować wyniki kosztownych operacji. Gdy cache jest pełny i musisz dodać nowy element – który usunąć? LRU usuwa element który był najdawniej używany. Intuicja: jeśli czegoś nie użyłeś od dawna, prawdopodobnie nie użyjesz wkrótce.

Naiwna implementacja – O(n) dla get

<?php

declare(strict_types=1);

// Naiwna implementacja - prosta ale wolna O(n) przy eviction
class SimpleLruCache
{
    private array $cache = []; // [key => value]
    private array $order = []; // klucze w kolejności użycia

    public function __construct(private int $capacity) {}

    public function get(string $key): mixed
    {
        if (!isset($this->cache[$key])) {
            return null;
        }

        // Przenieś na koniec (najnowszy) - O(n) przez array_search
        $this->moveToEnd($key);
        return $this->cache[$key];
    }

    public function put(string $key, mixed $value): void
    {
        if (isset($this->cache[$key])) {
            $this->cache[$key] = $value;
            $this->moveToEnd($key);
            return;
        }

        if (count($this->cache) >= $this->capacity) {
            // Usuń najstarszy (pierwszy w kolejności) - O(1)
            $oldest = array_shift($this->order);
            unset($this->cache[$oldest]);
        }

        $this->cache[$key]  = $value;
        $this->order[] = $key;
    }

    private function moveToEnd(string $key): void
    {
        // O(n) - wyszukanie i przesunięcie elementu w tablicy
        $pos = array_search($key, $this->order, true);
        if ($pos !== false) {
            array_splice($this->order, $pos, 1);
            $this->order[] = $key;
        }
    }
}

Optymalna implementacja – O(1) dla get i put

Kluczowa obserwacja: HashMap daje O(1) lookup, lista dwukierunkowa daje O(1) insert i delete przy znajomości węzła. Połączone: HashMap przechowuje wartość + wskaźnik do węzła listy, lista utrzymuje kolejność LRU.

<?php

declare(strict_types=1);

// Węzeł listy dwukierunkowej
class LruNode
{
    public ?LruNode $prev = null;
    public ?LruNode $next = null;

    public function __construct(
        public string $key,
        public mixed $value
    ) {}
}

// LRU Cache O(1) dla get i put
class LruCache
{
    /** @var array<string, LruNode> HashMap: key -> node */
    private array $map = [];

    // Sentinel nodes - eliminują sprawdzenie null przy operacjach na liście
    private LruNode $head; // najstarszy (LRU) - tuż za head
    private LruNode $tail; // najnowszy (MRU) - tuż przed tail

    public function __construct(private int $capacity)
    {
        // Sentinel nodes nie przechowują danych - upraszczają insert/delete
        $this->head = new LruNode('__head__', null);
        $this->tail = new LruNode('__tail__', null);

        $this->head->next = $this->tail;
        $this->tail->prev = $this->head;
    }

    // GET - O(1)
    public function get(string $key): mixed
    {
        if (!isset($this->map[$key])) {
            return null; // cache miss
        }

        $node = $this->map[$key];
        $this->moveToFront($node); // oznacz jako najnowiej używany
        return $node->value;
    }

    // PUT - O(1)
    public function put(string $key, mixed $value): void
    {
        if (isset($this->map[$key])) {
            // Aktualizuj istniejący
            $node = $this->map[$key];
            $node->value = $value;
            $this->moveToFront($node);
            return;
        }

        if (count($this->map) >= $this->capacity) {
            // Evict LRU - węzeł za head sentinel
            $lru = $this->head->next;
            $this->removeNode($lru);
            unset($this->map[$lru->key]);
        }

        // Dodaj nowy węzeł przed tail sentinel (najnowszy)
        $node = new LruNode($key, $value);
        $this->addBeforeTail($node);
        $this->map[$key] = $node;
    }

    public function has(string $key): bool
    {
        return isset($this->map[$key]);
    }

    public function delete(string $key): bool
    {
        if (!isset($this->map[$key])) {
            return false;
        }

        $node = $this->map[$key];
        $this->removeNode($node);
        unset($this->map[$key]);
        return true;
    }

    public function size(): int { return count($this->map); }

    // Przenieś węzeł na pozycję "najnowszy" (tuż przed tail)
    private function moveToFront(LruNode $node): void
    {
        $this->removeNode($node);
        $this->addBeforeTail($node);
    }

    // Odłącz węzeł z listy
    private function removeNode(LruNode $node): void
    {
        $node->prev->next = $node->next;
        $node->next->prev = $node->prev;
    }

    // Wstaw węzeł tuż przed tail (pozycja "najnowszy")
    private function addBeforeTail(LruNode $node): void
    {
        $node->prev = $this->tail->prev;
        $node->next = $this->tail;

        $this->tail->prev->next = $node;
        $this->tail->prev = $node;
    }

    // Debug: zwróć kolejność kluczy od LRU do MRU
    public function getKeysInOrder(): array
    {
        $keys = [];
        $current = $this->head->next;

        while ($current !== $this->tail) {
            $keys[] = $current->key;
            $current = $current->next;
        }

        return $keys;
    }
}

Testy i wizualizacja zachowania

<?php

// Demonstracja działania LRU Cache z capacity = 3
$cache = new LruCache(3);

$cache->put('a', 1);
echo implode(', ', $cache->getKeysInOrder()) . "\n"; // a

$cache->put('b', 2);
echo implode(', ', $cache->getKeysInOrder()) . "\n"; // a, b

$cache->put('c', 3);
echo implode(', ', $cache->getKeysInOrder()) . "\n"; // a, b, c

// Dostęp do 'a' - przesuwa na koniec (MRU)
$cache->get('a');
echo implode(', ', $cache->getKeysInOrder()) . "\n"; // b, c, a

// Dodaj 'd' - pojemność przekroczona, usuwa 'b' (LRU)
$cache->put('d', 4);
echo implode(', ', $cache->getKeysInOrder()) . "\n"; // c, a, d

var_dump($cache->get('b')); // NULL - wyeksmitowany
var_dump($cache->get('a')); // int(1) - nadal w cache

Praktyczne zastosowanie – cache wyników zapytań produktów

<?php

declare(strict_types=1);

// In-process cache dla wyników Repository - eliminuje powtarzające się zapytania
// w obrębie jednego requestu HTTP
class CachedProductRepository
{
    // Cache na poziomie procesu PHP - zniknie po zakończeniu requestu
    // Pojemność: max 500 produktów w pamięci jednocześnie
    private LruCache $requestCache;

    public function __construct(
        private \Magento\Catalog\Api\ProductRepositoryInterface $repository
    ) {
        $this->requestCache = new LruCache(500);
    }

    public function getById(int $id): \Magento\Catalog\Api\Data\ProductInterface
    {
        $cacheKey = "product_id_{$id}";

        $cached = $this->requestCache->get($cacheKey);
        if ($cached !== null) {
            return $cached; // hit - zero zapytań do bazy
        }

        $product = $this->repository->getById($id);
        $this->requestCache->put($cacheKey, $product);

        return $product;
    }

    public function getBySku(string $sku): \Magento\Catalog\Api\Data\ProductInterface
    {
        $cacheKey = "product_sku_{$sku}";

        $cached = $this->requestCache->get($cacheKey);
        if ($cached !== null) {
            return $cached;
        }

        $product = $this->repository->get($sku);

        // Cache pod oboma kluczami
        $this->requestCache->put($cacheKey, $product);
        $this->requestCache->put("product_id_{$product->getId()}", $product);

        return $product;
    }
}

// Scenariusz: renderowanie strony kategorii z 100 produktami
// Bez cache: 100 wywołań getById = 100 zapytań SQL
// Z LRU: pierwsze 100 trafień to miss, kolejne wywołania (np. related products)
// dla tych samych produktów = hit, zero dodatkowych zapytań

Benchmark – LRU vs SplFixedArray vs Magento ObjectCache

<?php

declare(strict_types=1);

$iterations = 100_000;
$capacity   = 1000;
$cache      = new LruCache($capacity);

// Wypełnij cache
for ($i = 0; $i < $capacity; $i++) {
    $cache->put("key_{$i}", "value_{$i}");
}

// Benchmark get (mixed hit/miss pattern)
$start = microtime(true);
for ($i = 0; $i < $iterations; $i++) {
    $key = "key_" . ($i % ($capacity * 2)); // 50% hit rate
    $cache->get($key);
}
$getTime = (microtime(true) - $start) * 1000;

// Benchmark put z eviction
$start = microtime(true);
for ($i = 0; $i < $iterations; $i++) {
    $cache->put("new_key_{$i}", "value_{$i}"); // zawsze eviction
}
$putTime = (microtime(true) - $start) * 1000;

echo "LRU get (100k ops): {$getTime}ms\n";   // ~20-30ms
echo "LRU put (100k ops): {$putTime}ms\n";   // ~25-35ms
echo "Średni get: " . round($getTime / $iterations * 1000, 2) . "μs\n"; // ~0.2μs

Podsumowanie

LRU Cache to algorytm który elegancko łączy dwie struktury danych – HashMap i listę dwukierunkową – w rozwiązanie O(1) dla obu operacji. Implementacja od zera jest klasycznym ćwiczeniem algorytmicznym, ale w praktyce PHP dla per-request cache wystarczy prosta tablica asocjacyjna z array_shift(). LRU wchodzi do gry gdy masz tysiące różnych kluczy w jednym procesie (CLI importer, długo działający worker) i chcesz kontrolować zużycie pamięci bez ręcznego zarządzania. Dla cache między requestami – Redis z polityką allkeys-lru robi to za Ciebie na poziomie infrastruktury.