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

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.