S3-FIFO в Node.js: кэш с 15.5M ops/sec без GC

Почему LRU может тормозить ваш Node.js-бэкенд

Когда нам нужен кэш в памяти в Node.js, 99% из нас делают одно и то же: npm install lru-cache. Это мышечная память. LRU (Least Recently Used) — индустриальный стандарт десятилетиями, и не зря: он интуитивен и работает. Но если вы обслуживаете высоконагруженный бэкенд, опора на LRU может незаметно снижать производительность и ухудшать процент попаданий в кэш.

Недавно я углубился в кроличью нору после прочтения знаменитой статьи 2023 года с конференции SOSP: «FIFO queues are all you need for cache eviction». В статье доказывается, что новый алгоритм S3-FIFO (использующий три простых очереди FIFO) полностью превосходит сложные гибриды LRU/LFU. Он решает главный недостаток LRU: загрязнение кэша, вызванное «одноразовыми запросами» (например, массовый обход БД или трафик веб-краулера выбивают все горячие данные).

Высокопроизводительные движки хранилищ и CDN уже внедрили S3-FIFO. Но экосистема Node.js подозрительно молчала из-за отсутствия готовой, оптимизированной реализации. Поэтому я решил создать s3fifo. Но я не просто портировал алгоритм — я хотел выжать из движка V8 абсолютный максимум.

Вот как я выжал 15.5M операций/сек из JavaScript и почему вам стоит пересмотреть свои пакеты для кэширования.

Проблема: высокоуровневые абстракции убивают производительность

Если реализовать кэш в Node.js с помощью наивных объектов или массивов, накладные расходы движка V8 уничтожат пропускную способность. Типичные реализации LRU выделяют объект узла { key, value, prev, next } при каждой операции set() для управления двусвязным списком. При высоконагруженном трафике создание миллионов временных объектов-обёрток вызывает частые дорогие паузы сборщика мусора (GC).

Чтобы построить кэш, превосходящий стандартные решения, мне пришлось опуститься до системных паттернов работы с памятью внутри JavaScript.

Гиковские оптимизации V8 и системные трюки

1. Плоские параллельные массивы с нулевым GC и переработка слотов

s3fifo не выделяет ни одного объекта-узла во время выполнения. Вместо этого используются плоские параллельные массивы:

• #keys: (string | undefined)[]
• #values: (V | undefined)[]
• #meta: Uint32Array (флаги и ID поколения)
• #starts / #ttls: Float64Array

Доступные слоты отслеживаются и перерабатываются с помощью непрерывного стека Uint32Array (#freeSlots). Вставка и удаление — это простые O(1) сдвиги индексов в плоских массивах. Ноль динамических выделений объектов = ноль давления на GC.

// Переработка слота через стек индексов: O(1) без GC
const slot = this.#freeSlots[this.#freeSlotTop--]!;
this.#keys[slot] = key;
this.#values[slot] = value;

2. Упаковка метаданных в биты и отслеживание поколений (32-битные целые)

Вместо хранения флагов состояния в объектах JS метаданные каждого слота упаковываются в одно 32-битное целое внутри #meta (Uint32Array):

• Младшие 5 бит: флаги состояния (счётчик FREQ 0-3, RESIDENT, STALE, FREED)
• Старшие 27 бит: ID поколения (увеличивается при каждом переиспользовании слота)

const META_FREQ_MSK = 0b00011;
const META_STALE_MSK = 0b00100;
const META_RESI_MSK = 0b01000;
const META_FREED_MSK = 0b10000;

// Чтение счётчика частоты через побитовое И
const freq = meta & META_FREQ_MSK;

Это упаковывает всё рабочее состояние в 4 байта на слот, оставаясь невосприимчивым к изменениям скрытых классов V8.

3. O(1) детекция «зомби» через 64-битную упаковку

В S3-FIFO очередь-призрак (#G) отслеживает элементы, вытесненные из основного кэша, чтобы дать им второй шанс при повторном обращении. Но что, если слот переиспользуется для нового ключа, пока старая ссылка всё ещё находится в очереди-призраке (проблема ABA)?

Вместо указателей или хеш-таблиц s3fifo упаковывает slot_index И generation_id в одно 64-битное число с плавающей точкой в кольцевом буфере Float64Array:

// Упаковка ID поколения и индекса слота в один Float64
const packedForG = gen * SHIFT_ADDR + evictedSlot;

// При извлечении из очереди-призрака:
const ghostOrZombie = packed % SHIFT_ADDR;
const poppedGen = Math.floor(packed / SHIFT_ADDR);
const currentGen = (this.#meta[ghostOrZombie]! >> 5) & GEN_MASK;

// Если поколения не совпадают — это «зомби» (переиспользованный слот) -> отбрасываем за O(1)!
const isZombie = poppedGen !== currentGen;

4. Побитовые операции вместо модульной арифметики

Кольцевые буферы требуют обёртывания индексов: (index + 1) % capacity. Однако оператор % вычислительно дорог в горячих циклах. s3fifo принудительно задаёт размеры внутренних кольцевых буферов как степень двойки. Это позволяет заменить деление по модулю на молниеносное побитовое И (&):

// Стандартный кольцевой буфер (медленный %)
this.tail = (this.tail + 1) % this.capacity;

// Кольцевой буфер S3-FIFO (быстрая битовая маска)
this.tail = (this.tail + 1) & this.mask;

5. Кэширование временных меток для TTL

Вызов performance.now() или Date.now() при каждом попадании в цикле с миллионами операций добавляет измеримые накладные расходы системных вызовов. s3fifo поддерживает внутреннюю метку времени #cacheNow, обновляемую через setInterval с настраиваемым разрешением (ttlResolution, по умолчанию 100 мс) и .unref(), что полностью исключает блокировку цикла событий и устраняет накладные расходы системных вызовов.

Бенчмарки: процент попаданий и пропускная способность vs lru-cache

Тестирование на распределении Зипфа (скошенность 0.99, рабочий набор из 100 000 ключей) сравнивает s3fifo v1.0 с популярным пакетом lru-cache:

Средний процент попаданий (%)

Средняя пропускная способность (операций/сек)

Готово к продакшену и интеграция с Keyv

Вам не нужно переписывать приложение, чтобы попробовать. Я создал keyv-s3fifo, который официально включён в экосистему Keyv как адаптер первого класса. Если вы уже используете Keyv, вы можете переключить движок кэша на S3-FIFO одной строкой кода!

Вывод

LRU не мёртв, но использовать его по умолчанию без бенчмарков — значит оставлять на столе значительную производительность. Если ваше Node.js-приложение обрабатывает крупномасштабный трафик, веб-краулеры или высокообъёмные запросы к БД, S3-FIFO защитит ваши горячие данные от загрязнения кэша, одновременно обеспечивая более высокую пропускную способность.

Хватит использовать по умолчанию. Начинайте бенчмаркать.

Посмотрите код, запустите бенчмарки на своей машине и, если найдёте полезным, поставьте ⭐️ на GitHub!

👉 GitHub: s3fifo
👉 npm: s3fifo
👉 npm: keyv-s3fifo