LRU-кэш на PHP 8.5 для Identity Map: 13+ млн операций в секунду

LRU на PHP — задача, которую, вроде бы, уже все кому не лень решили вдоль и поперёк.

Классическая схема: O(1)-поиск по ключу + двусвязный список для порядка доступа — работает, читается, всем нравится. Но когда начинаешь мерить, оказывается, что большинство реализаций выдают 2–5 млн ops/sec. Для веба это нормально, а вот для highload — уже нет. Особенно когда LRU — это не «где-то в кэше Redis», а фундамент Identity Map, который сидит прямо в hot path каждого запроса.

Я проектирую собственный слой персистентности поверх Eloquent — с Identity Map, Unit of Work и оптимистической блокировкой. Для этой архитектуры LRU — фундаментальный слой. Если его латентность опускается ниже 2–3 млн ops/sec, оверхед кэша начинает измеряться сотнями наносекунд на запрос. Это сопоставимо со стоимостью полноценного сетевого обращения к БД. В итоге Identity Map перестает окупаться: вместо экономии запросов мы получаем чистую деградацию latency каждого хита.

Я решил, что сделаю LRU, который не будет узким местом вообще.

Задача казалась простой: взять каноничную реализацию (HashMap + doubly linked list), заменить объекты на массивы, учесть особенности JIT. На деле — 10 итераций, каждая с замером. Где-то я терял 50% производительности на property hooks, а где-то, наоборот, разбиение класса на четыре давало +25%.

Итоговая цифра: 15.4 млн ops/sec на touch существующего ключа, и это всё на слабом ноуте, да ещё и в Docker с кучей соседних контейнеров. На проде, правда, пока не тестил.

Интерфейс

<?php declare(strict_types=1);

namespace App\Orm\IdentityMap\Lru;

/**
 * @phpstan-extends \IteratorAggregate<int, non-empty-string>
 */
interface LruCacheInterface extends \Countable, \IteratorAggregate
{
    /**
     * @phpstan-param non-empty-string $key
     * @phpstan-return non-empty-string|null
     */
    public function touch(string $key): ?string;

    /**
     * @phpstan-param iterable<non-empty-string> $keys
     * @phpstan-return list<non-empty-string>
     */
    public function touchMany(iterable $keys): array;

    /**
     * @phpstan-return non-empty-string|null
     * @throws \AssertionError
     */
    public function evict(): ?string;

    /**
     * @phpstan-param string $key
     * @phpstan-return void
     */
    public function remove(string $key): void;

    /**
     * @phpstan-return void
     */
    public function clear(): void;
}

Ключевые моменты:

• touch() — добавляет ключ или обновляет позицию. Возвращает evicted key (если был).

• touchMany() — массовое добавление. Возвращает список вытесненных ключей.

• evict() — принудительное вытеснение самого старого ключа.

• remove() — удаление конкретного ключа.

• clear() — полная очистка всех структур.

Основная реализация

<?php declare(strict_types=1);

namespace App\Orm\IdentityMap\Lru;

/**
 * @implements LruCacheInterface
 */
final class LruCache implements LruCacheInterface
{
    /**
     * @phpstan-var array<non-empty-string, int<0, max>>
     */
    private array $nodes = [];

    /**
     * @phpstan-var int<0, max>
     */
    private int $size = 0;

    /**
     * @phpstan-var LruNodePool
     */
    private readonly LruNodePool $pool;

    /**
     * @phpstan-var LruNodeKeys
     */
    private readonly LruNodeKeys $keys;

    /**
     * @phpstan-var LruNodeLinks
     */
    private readonly LruNodeLinks $links;

    /**
     * @phpstan-param int<1, max> $capacity
     * @throws \InvalidArgumentException
     */
    public function __construct(
        private readonly int $capacity
    ) {
        if ($capacity < 1) {
            throw new \InvalidArgumentException(
                message: 'Capacity must be at least 1.'
            );
        }

        $this->pool = new LruNodePool(
            capacity: $capacity
        );

        $this->keys = new LruNodeKeys();
        $this->links = new LruNodeLinks();
    }

    /**
     * @phpstan-param non-empty-string $key
     * @phpstan-return non-empty-string|null
     */
    #[\NoDiscard]
    public function touch(string $key): ?string
    {
        $node = $this->nodes[$key] ?? null;

        if ($node !== null) {
            if ($node !== $this->links->tail) {
                $this->links->touch(node: $node);
            }

            return null;
        }

        $evicted = $this->size >= $this->capacity
            ? $this->evict()
            : null;

        $node = $this->pool->allocate();
        
        $this->keys->set(node: $node, key: $key);
        $this->nodes[$key] = $node;
        $this->links->push(node: $node);

        $this->size++;

        return $evicted;
    }

    /**
     * @phpstan-param iterable<non-empty-string> $keys
     * @phpstan-return list<non-empty-string>
     */
    #[\NoDiscard]
    public function touchMany(iterable $keys): array
    {
        $evicted = [];

        foreach ($keys as $key) {
            $result = $this->touch(key: $key);

            if ($result !== null) {
                $evicted[] = $result;
            }
        }

        return $evicted;
    }

    /**
     * @phpstan-return non-empty-string|null
     * @throws \AssertionError
     */
    #[\NoDiscard]
    public function evict(): ?string
    {
        if ($this->links->head === LruNodePool::NIL) {
            return null;
        }

        /** @phpstan-var int<0, max> $node */
        $node = $this->links->head;
        $key = $this->keys->get(node: $node);

        if ($key === null) {
            throw new \AssertionError(
                message: 'LRU head has null key.'
            );
        }

        $this->links->detach(node: $node);

        unset($this->nodes[$key]);

        $this->pool->release(node: $node);
        $this->size--;

        return $key;
    }

    /**
     * @phpstan-return \Generator<int, non-empty-string>
     * @throws \AssertionError
     */
    public function getIterator(): \Generator
    {
        $node = $this->links->head;

        while ($node !== LruNodePool::NIL) {
            /** @phpstan-var int<0, max> $node */
            $key = $this->keys->get(node: $node);

            if ($key === null) {
                throw new \AssertionError(
                    message: 'LRU list node has null key.'
                );
            }

            $next = $this->links->next[$node]
                ?? LruNodePool::NIL;

            yield $key;

            $node = $next;
        }
    }

    /**
     * @phpstan-return int<0, max>
     */
    public function count(): int
    {
        return $this->size;
    }

    /**
     * @phpstan-param string $key
     * @phpstan-return void
     */
    public function remove(string $key): void
    {
        $node = $this->nodes[$key] ?? null;

        if ($node === null) {
            return;
        }

        $this->links->detach(node: $node);

        unset($this->nodes[$key]);

        $this->pool->release(node: $node);
        $this->size--;
    }

    /**
     * @phpstan-return void
     */
    public function clear(): void
    {
        $this->links->clear();
        $this->pool->clear();
        $this->keys->clear();

        $this->nodes = [];
        $this->size = 0;
    }
}

Архитектурные решения:

• Разделение ответственности: LruNodePool, LruNodeKeys, LruNodeLinks — каждый класс отвечает за свою плоскую структуру данных. Это не «больше классов = медленнее», а быстрее благодаря JIT inlining. Мелкий final-метод JIT инлайнит целиком, а большой метод со сложной логикой трассирует долго.

• Плоские индексированные массивы (Integer ID maps): $nodes хранит соответствие строкового ключа целочисленному ID узла ($keyString => $nodeId), а не объекты. Меньше аллокаций GC, лучше locality данных для CPU-кэша.

• Предварительный пул (Object Pooling): LruNodePool выдаёт ID из пула освобожденных индексов, а не создаёт новые структуры. Результат — 0 аллокаций памяти после initial population.

• Readonly-свойства: $pool, $keys, $links, $capacity объявлены как readonly. JIT-оптимизатор агрессивнее выполняет девиртуализацию, потому что точно знает — поле не изменится после конструктора.

• Финальный класс: запрещает наследование, убирая проверки виртуальной таблицы методов (vtable check). Это позволяет JIT компилятору выполнить полный инлайнинг горячих путей ($this->links->touch(…)).

Вспомогательные классы

LruNodeKeys

<?php declare(strict_types=1);

namespace App\Orm\IdentityMap\Lru;

/**
 * @internal
 */
final class LruNodeKeys
{
    /**
     * @phpstan-var array<int<0, max>, non-empty-string|null>
     */
    private array $keys = [];

    /**
     * @phpstan-param int<0, max> $node
     * @phpstan-param non-empty-string $key
     *
     * @phpstan-return void
     */
    final public function set(int $node, string $key): void
    {
        $this->keys[$node] = $key;
    }

    /**
     * @phpstan-param int<0, max> $node
     * @phpstan-return non-empty-string|null
     */
    final public function get(int $node): ?string
    {
        return $this->keys[$node] ?? null;
    }

    /**
     * @phpstan-param int<0, max> $node
     * @phpstan-return void
     */
    final public function reset(int $node): void
    {
        $this->keys[$node] = null;
    }

    /**
     * @phpstan-return void
     */
    final public function clear(): void
    {
        $this->keys = [];
    }
}

Отдельный класс для маппинга node_id → key. Крошечный final-класс = JIT инлайнит вызов до одного MOV-инструкции при доступе к массиву. Если бы этот код был внутри основного LruCache, JIT трассировал бы весь объем родительского класса ради одной строчки — лишние ветвления, лишние проверки типов.

LruNodeLinks

<?php declare(strict_types=1);

namespace App\Orm\IdentityMap\Lru;

/**
 * @internal
 */
final class LruNodeLinks
{
    /**
     * @phpstan-var int<0, max>|int<-1, -1>
     */
    public int $head = LruNodePool::NIL;

    /**
     * @phpstan-var int<0, max>|int<-1, -1>
     */
    public int $tail = LruNodePool::NIL;

    /**
     * @phpstan-var array<int<0, max>, int<0, max>|int<-1, -1>>
     */
    private array $prev = [];

    /**
     * @phpstan-var array<int<0, max>, int<0, max>|int<-1, -1>>
     */
    private array $next = [];

    /**
     * @phpstan-param int<0, max> $node
     * @phpstan-return void
     */
    final public function touch(int $node): void
    {
        if ($node === $this->tail) {
            return;
        }

        $prev = $this->prev[$node] ?? LruNodePool::NIL;
        $next = $this->next[$node] ?? LruNodePool::NIL;

        if ($prev !== LruNodePool::NIL) {
            $this->next[$prev] = $next;
        } else {
            $this->head = $next;
        }

        if ($next !== LruNodePool::NIL) {
            $this->prev[$next] = $prev;
        } else {
            $this->tail = $prev;
        }

        $this->prev[$node] = $this->tail;
        $this->next[$node] = LruNodePool::NIL;

        if ($this->tail !== LruNodePool::NIL) {
            $this->next[$this->tail] = $node;
        } else {
            $this->head = $node;
        }

        $this->tail = $node;
    }

    /**
     * @phpstan-param int<0, max> $node
     * @phpstan-return void
     */
    final public function detach(int $node): void
    {
        $prev = $this->prev[$node] ?? LruNodePool::NIL;
        $next = $this->next[$node] ?? LruNodePool::NIL;

        if ($prev !== LruNodePool::NIL) {
            $this->next[$prev] = $next;
        } else {
            $this->head = $next;
        }

        if ($next !== LruNodePool::NIL) {
            $this->prev[$next] = $prev;
        } else {
            $this->tail = $prev;
        }
    }

    /**
     * @phpstan-param int<0, max> $node
     * @phpstan-return void
     */
    final public function push(int $node): void
    {
        $this->prev[$node] = $this->tail;
        $this->next[$node] = LruNodePool::NIL;

        if ($this->tail !== LruNodePool::NIL) {
            $this->next[$this->tail] = $node;
        } else {
            $this->head = $node;
        }

        $this->tail = $node;
    }

    /**
     * @phpstan-return void
     */
    final public function reset(): void
    {
        $this->head = LruNodePool::NIL;
        $this->tail = LruNodePool::NIL;
    }

    /**
     * @phpstan-return void
     */
    final public function clear(): void
    {
        $this->head = LruNodePool::NIL;
        $this->tail = LruNodePool::NIL;
        
        $this->prev = [];
        $this->next = [];
    }
}

Doubly linked list на массивах ($prev, $next). Никаких объектов, только integer IDs. Это ключевое решение всей архитектуры: объекты в PHP — это дорогая аллокация и косвенный доступ через указатель, а обращение к $this->prev[$node] JIT превращает в прямой оффсетный доступ к памяти.

LruNodePool

<?php declare(strict_types=1);

namespace App\Orm\IdentityMap\Lru;

/**
 * @internal
 */
final class LruNodePool
{
    /**
     * @phpstan-var int<-1, -1>
     */
    public const int NIL = -1;

    /**
     * @phpstan-var list<int<0, max>>
     */
    private array $releasedIds = [];

    /**
     * @phpstan-var int<0, max>
     */
    private int $nextNewId = 0;

    /**
     * @phpstan-param int<1, max> $capacity
     * @throws \InvalidArgumentException
     */
    public function __construct(
        private readonly int $capacity
    ) {
        if ($capacity < 1) {
            throw new \InvalidArgumentException(
                message: 'Capacity must be at least 1.'
            );
        }
    }

    /**
     * @phpstan-return int<0, max>
     * @throws \RuntimeException
     */
    final public function allocate(): int
    {
        return match (true) {
            $this->releasedIds !== []
                => array_pop(array: $this->releasedIds),

            $this->nextNewId < $this->capacity
                => $this->nextNewId++,

            default => throw new \RuntimeException(
                message: sprintf(
                    'LruNodePool exhausted: capacity %d.',
                    $this->capacity
                )
            ),
        };
    }

    /**
     * @phpstan-param int<0, max> $node
     * @phpstan-return void
     */
    final public function release(int $node): void
    {
        $this->releasedIds[] = $node;
    }

    /**
     * @phpstan-return void
     */
    final public function clear(): void
    {
        $this->releasedIds = [];
        $this->nextNewId = 0;
    }
}

Пул ID для узлов. Сначала выдает освобождённые ID из стека $releasedIds, затем выделяет новые $nextNewId. Когда емкость исчерпана — исключение. Ключевая оптимизация: 0 аллокаций после заполнения пула. Операции array_pop() и запись в конец массива [] работают за O(1) без создания каких-либо сущностей. Использование match(true) вместо цепочки if/elseif/else дает ту же скорость (JIT компилирует их одинаково), но делает правила выдачи ID визуально очевидными.

Бенчмарки

Среда:

• Простенький ноутбук (самый обычный).

• Docker + highload (куча контейнеров).

• PHP 8.5-FPM + JIT 1255 + 64M buffer.

Результаты:

Итог

15+ млн. ops/sec на обычном ноутбуке в тяжелом окружении Docker. На bare metal железо сервера уберет оверхед виртуализации, огромные L3-кэши процессора проглотят ваши flat-массивы без промахов, а настроенные Huge Pages ускорят работу JIT-компилятора в OPCache. Прогнозируемый throughput на продакшене — 25–30+ млн. ops/sec. Этот уровень латентности выводит сам механизм кэширования из уравнения производительности приложения: бутылочным горлышком снова становится база данных, а не ваш Identity Map.