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%.

Итоговая цифра: 13.1 млн. ops/sec на touch существующего ключа (лучший прогон — 15.4 млн), и это всё на слабом ноуте, да ещё и в 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.

• Замеры через Pest benchmark.

Результаты:

Тест	ops/sec	ns/op	Аллокации
Warm touch (100% hits)	13.1 млн.	76 нс.	0 B
Cold insert + eviction	7.89 млн.	126 нс.	+2.00 MB allocated
Random access (100% hits)	9.92 млн.	100 нс.	0 B
Hot-set access (100% hits)	11.66 млн.	85 нс.	0 B

Итог

LRU-кэш получился не как «ещё одна реализация», а именно как то, чем он и должен быть в Identity Map — несущий слой, который держит всю конструкцию и при этом не стоит ничего.

На обычном ноутбуке, в Docker с кучей соседних контейнеров, warm touch укладывается в 76 наносекунд, а в лучших прогонах — в 63. Это не «нормально для PHP» — это уровень, на котором кэш перестаёт быть тем, о чём вообще думаешь в hot path. На bare metal будет быстрее, но это уже прогноз, а не измерение, и строить на нём архитектурные решения я бы не стал. Воспроизводимой базы достаточно: 13+ млн ops/sec на ноутбуке, 0 аллокаций в горячем пути, предсказуемое поведение на всех сценариях.

Что здесь по-настоящему важно — не отдельная цифра, а то, что структура ведёт себя ровно на всём диапазоне нагрузок. Warm touch, cold insert, random access, hot-set — везде один порядок величины, без обрывов и сюрпризов. В hot path именно предсказуемость решает: Identity Map не должен заставлять тебя думать, окупится он на этом запросе или нет. И вот это как раз получилось — LRU работает ровно там, где должен, и не мешает там, где не должен.