В 2021 году мы в команде неделями обсуждали, какую политику вытеснения поставить в кэш одного сервиса, — и так и не выбрали: на нормальное исследование не было времени. В 2026-м я написал библиотеку, которая избавляет от этого спора. Кэш запускает несколько политик параллельно, меряет их hit rate на реальном трафике и сам переключается на лучшую с помощью Thompson Sampling.
Под катом — история о том, как статья Алексея Миловидова про разжатие LZ4 через пять лет превратилась в Go-библиотеку as-cache, короткий ликбез по политикам вытеснения, устройство shadow-кэшей, три стратегии миграции данных и честная глава про грабли конкурентности, которые я собрал по дороге.
И сразу дисклеймер, чтобы не тратить ваше время зря: чуда не случилось. Адаптивный выбор не обогнал ни лучшую фиксированную политику на синтетике, ни otter с theine в лобовом сравнении. Зато по дороге выяснилось кое-что поинтереснее — например, что на реальных трейсах лучшая политика меняется от трейса к трейсу, а один из моих замеров полгода показывал бы чужую победу, которой не было. Про это в главе «Что показали замеры»; там же цифры, которые можно перепроверить одной командой.
Обычная история. Сервис, перед ним кэш, за ним — дорогие запросы к базе. Кэш переполняется, надо кого-то выгонять. Кого?
Один в команде топит за LRU: рабочая лошадка, все так делают, hashicorp/golang-lru в двух строчках. Второй — за LFU: у нас же явные горячие ключи, зачем их выгонять только потому, что последние десять минут спрашивали про другое. Третий приносит в тред статью про ARC и предлагает «сделать по-взрослому».
Правильный ответ на этот спор известен и скучен: собрать трейс реального трафика, прогнать его через симуляторы всех политик-кандидатов, сравнить hit rate, выбрать по цифрам. Это отдельное маленькое исследование — дни, если повезёт, недели, если нет. А у нас спринт, фичи и прод. Поэтому кончилось как у всех: «берём LRU и расходимся».
LRU, к слову, работал нормально. Но осадочек остался: решение, влияющее на нагрузку базы, мы приняли по сути броском монетки. И этот вопрос — «как выбирать алгоритм, когда на исследование нет времени» — засел у меня в голове.
Ответ я нашёл не в литературе про кэши, а в статье про распаковку LZ4.
В том же 2021-м мне попалась статья Алексея Миловидова 2019 года — «Как ускорить разжатие LZ4 в ClickHouse» (есть и видео доклада с HighLoad++ Siberia 2018).
Коротко, если вы её пропустили. У команды ClickHouse получилось четыре варианта горячего цикла разжатия: копировать байтовые последовательности по 8 или по 16 байт, с SIMD-инструкцией pshufb или без. И выяснилось, что лучший вариант зависит одновременно от данных (коэффициента сжатия) и от модели процессора. Захардкодить выбор нельзя: ClickHouse крутится у сотен компаний на каком угодно железе и каких угодно данных, и любой фиксированный выбор кого-то замедлит.
Вместо этого выбор отдали многорукому бандиту. Каждый блок данных (от 64 КБ) — независимый вызов разжатия. Время работы измеряется почти бесплатно на фоне самой распаковки и служит наградой. Вариант для каждого блока разыгрывается через Thompson Sampling поверх оценок среднего времени. Итог: минус 12–20% времени разжатия на современных x86, причём адаптивный вариант в среднем обгонял даже лучший заранее выбранный фиксированный — потому что «лучший фиксированный» на разных данных разный.
Меня тогда зацепила не сама оптимизация, а форма задачи:
Несколько взаимозаменяемых алгоритмов. Лучший зависит от контекста. Контекст заранее неизвестен и меняется.
Это же в точности наш спор про кэш! Политики вытеснения взаимозаменяемы — интерфейс у всех одинаковый. Лучшая зависит от нагрузки. Нагрузка у каждого сервиса своя, заранее неизвестна, да ещё и дрейфует во времени.
Идея «скрестить бандита с кэшем» отправилась в ящик. Реализовывать её вечерами было дорого: несколько политик, сбор статистики, фоновое переключение, миграция данных между политиками — по-хорошему пара недель плотной работы. Которых, как вы помните из первой главы, не нашлось даже на исследование.
Достал я её из ящика, когда порог входа в прототипирование резко упал. С ИИ-агентами каркас библиотеки — интерфейсы, обёртки над готовыми кэшами, фоновая горутина с тикером эпох — собрался за несколько вечеров вместо пары недель. В репозитории до сих пор лежит CLAUDE.md с инструкциями для агента — считайте его артефактом эпохи.
Сразу оговорюсь про роль ИИ, чтобы снять предсказуемый вопрос из комментариев. Агент отлично пишет каркас и рутину. Но все по-настоящему интересные ошибки в этой задаче — конкурентные, и их агент вносит так же уверенно, как пишет докстринги про потокобезопасность. Дизайн, инварианты миграции и отладка гонок остались ручной работой — про это будет отдельная глава. Прототипирование подешевело; инженерия — нет.
Так появился as-cache — adaptive selection cache. Прежде чем показывать устройство, — короткий ликбез, чтобы дальше говорить на одном языке.
Политика вытеснения отвечает на один вопрос: кого выгнать, когда место кончилось. Разные политики — это разные ставки на будущее.
| Политика | Ставка | Где сильна | Где ломается |
|---|---|---|---|
| LRU | кто давно не нужен — не нужен | временна́я локальность, интерактивный трафик | одно сканирование вымывает весь кэш |
| LFU | кто редко нужен — не нужен | стабильное «горячее» множество ключей | загрязнение кэша: бывшие чемпионы не уходят |
| 2Q | LRU с испытательным сроком | защита от сканов | параметры очередей надо тюнить |
| ARC | recency/frequency, баланс подбирается сам | смешанные нагрузки | сложнее, историческая патентная возня |
| W-TinyLFU | частотный фильтр на входе + LRU-окно | почти всё, близко к оптимуму | нетривиальная реализация |
Классика по ссылкам: 2Q — Johnson & Shasha (VLDB '94); ARC — Megiddo & Modha (FAST '03); TinyLFU — Einziger, Friedman, Manes (arXiv:1512.00727). Из живых реализаций W-TinyLFU: Caffeine в Java (его wiki — золотая жила по теме), в Go — Ristretto, Otter, Theine.
Есть и отдельная академическая ветка, где политику выбирает алгоритм: LeCaR (HotStorage '18) переключается между LRU и LFU через онлайн-обучение с минимизацией сожаления и обыгрывает ARC на небольших кэшах; CACHEUS (FAST '21) развивает идею. То есть научная база под «пусть выбирает машина» давно есть. Не хватало библиотеки, которую можно просто go get.
Если лучшая политика зависит от нагрузки, а нагрузку мы заранее не знаем, — вывод один: кэш должен выяснить её сам, в проде, на реальном трафике. Осталось понять, как это сделать, не устроив в проде пожар.
Конструкция держится на трёх частях.
Shadow-кэши. Активная политика обслуживает запросы и хранит реальные значения. Остальные политики работают «в тени»: получают тот же поток Get/Add, но вместо значений им кладутся нули. Теневой политике значения и не нужны — ей нужен только паттерн доступа, чтобы честно вести свой учёт попаданий и промахов. Память на тени уходит на ключи и метаданные, а не на данные.
flowchart LR
R["Get / Add"] --> A["Активная политика — LRU<br/>реальные значения"]
R --> S["Shadow-политика — LFU<br/>те же ключи, значения — нули"]
A --> V["ответ пользователю"]
S -.-> H["собственный hit/miss"]
Эпохи. Раз в EpochDuration фоновая горутина снимает hit/miss с каждой теневой политики, сбрасывает счётчики и отдаёт статистику бандиту. Есть и второй вариант часов — EpochRequests: эпоха заканчивается каждые N вызовов Get, а не по таймеру (появился в релизе v0.3.0). Он появился не для красоты: на настенных часах то, как часто кэш переоценивает себя, зависит от скорости машины, и один и тот же трейс на загруженном ноутбуке даёт другой hit rate. В замерах ниже это стоило 12 пунктов разброса между двумя прогонами одного и того же сравнения.
Бандит. Пара (hits, misses) — это готовые параметры бета-распределения: Beta(hits+1, misses+1) — апостериорное распределение «истинного» hit rate политики. Дальше Thompson Sampling в чистом виде: сэмплируем по числу из каждого распределения, побеждает лучший сэмпл. Уверенный лидер выигрывает почти всегда; тёмной лошадке с широким распределением изредка выпадает шанс показать себя. Это и есть баланс exploration/exploitation, за который бандитов любят.
flowchart LR
subgraph E["Эпоха N"]
ACT["активная LRU — обслуживает запросы"]
SH1["shadow LFU: 830 hit / 170 miss"]
SH2["shadow 2Q: 790 hit / 210 miss"]
end
SH1 --> B1["Beta(831, 171)"]
SH2 --> B2["Beta(791, 211)"]
B1 --> TS["Thompson Sampling:<br/>сэмпл из каждого распределения"]
B2 --> TS
TS --> W["победитель: LFU"]
W --> M["эпоха N+1:<br/>переключение + миграция"]
Здесь важно проговорить, чем задача отличается от кликхаусовской, — это объясняет, почему нельзя было просто скопировать подход один в один. У ClickHouse награда (время на блок) измеряется бесплатно, а решения независимы: любой блок можно разжать любым вариантом, состояния нет. У кэша решение — это состояние. Сменить политику — значит что-то сделать с данными, а это дорого. Отсюда три отличия as-cache: эпохи вместо решения на каждый вызов, shadow-кэши вместо прямого замера и целый отдельный механизм миграции.
Начну с главного продуктового решения: публичный API — надмножество hashicorp/golang-lru/v2. Add, Get, Contains, Peek, Remove, Purge, Keys, Values, Len, Resize ведут себя так же, как в привычном LRU, — меняется только конструктор. Сверху добавлены Stats(), ActivePolicy() и Close() для наблюдения за бандитом. Хотелось, чтобы «попробовать» стоило одну замену конструктора, а не переучивание.
Общая схема:
flowchart TD
AC["AdaptiveCache"] --> AP["Активная политика<br/>CacheWrapper → hashicorp LRU<br/>реальные значения"]
AC --> SP["Shadow-политики<br/>CacheWrapper → нативный LFU<br/>нулевые значения"]
AC --> BD["Bandit<br/>Thompson Sampling, адаптер над stitchfix/mab"]
AC --> GR["Фоновая горутина"]
GR --> T["тикер эпох"] --> ST["сбор статистики"] --> SW["переключение"] --> MG["миграция"]
CacheWrapper — тонкая обёртка над любой реализацией: добавляет тип политики, ёмкость и счётчики hit/miss. LRU берётся из hashicorp, LFU написан свой — с O(1) на все операции. Бандит спрятан за интерфейсом из двух методов, поэтому Thompson Sampling легко заменить хоть на UCB, хоть на ε-greedy:
type Bandit interface {
// RecordStats принимает hit/miss теневой политики за эпоху.
RecordStats(stats ShadowStats)
// SelectPolicy возвращает политику, которая станет активной.
SelectPolicy() PolicyType
}Писать этот интерфейс самому больше не нужно — это была самая муторная часть внедрения. В модуле as-cache/bandit лежат готовые: NewThompson (бета-апостериоры с забыванием) и NewGreedy как контроль. Там же — распределённый бандит, про него ниже.
Одно правило про этот интерфейс стоит знать, если будете писать свой: оба метода вызываются под write-локом кэша. RWMutex в Go ставит новых читателей в очередь за ожидающим писателем, поэтому бандит, который сходил в сеть на секунду, — это не «медленно», это секундная недоступность каждого Get в процессе. Всё I/O — на своей горутине, наружу только буфер.
Использование (упрощено; полный рабочий пример с HTTP-сервером и адаптером над stitchfix/mab — в examples/basic):
cache, _ := ascache.NewAdaptiveCache(policies, bandit, &ascache.Settings{
EpochDuration: time.Minute,
MigrationStrategy: ascache.MigrationGradual,
})
defer cache.Close()
cache.Add("user:42", profile)
v, ok := cache.Get("user:42")
log.Println(cache.ActivePolicy()) // кто сейчас у руляБандит выбрал новую политику. В ней сейчас лежат нули — она же была тенью. Что делать с данными? Три стратегии на выбор:
| Стратегия | Поведение | Цена |
|---|---|---|
MigrationCold |
новая политика стартует пустой | простота; временный всплеск промахов |
MigrationWarm |
все пары ключ-значение копируются в момент переключения | нет всплеска; O(n) работы разом |
MigrationGradual |
ключи доезжают лениво: продвижение на промахе Get, плюс по одному ключу на каждый Add |
цена размазана; окно закрывается к следующей эпохе |
Gradual — то место, где я провёл больше всего времени. Схема такая: при переключении снимается снапшот ключей старой политики; дальше, если Get промахнулся в новой активной политике, ключ подтягивается из старой (Peek + Add); каждый Add заодно дотаскивает один ключ из очереди — чтобы миграция гарантированно двигалась даже без промахов.
sequenceDiagram
participant C as Клиент
participant AC as AdaptiveCache
participant N as Новая активная — LFU
participant O as Старая LRU — теперь shadow
C->>AC: Get(k)
AC->>N: Get(k)
N-->>AC: промах
AC->>O: Peek(k)
O-->>AC: v
AC->>N: Add(k, v) — ключ «доехал»
AC-->>C: v
Note over O: shadow-Add(k, 0) может затереть v в источнике —<br/>такой ключ помечается «испорченным»<br/>и не продвигается
И тут прячется ловушка. Старая политика после переключения становится тенью — а тени на каждый Add получают нули. То есть shadow-Add может затереть нулём реальное значение прямо в источнике миграции. Такие ключи надо помечать «испорченными» и исключать из продвижения — иначе кэш однажды отдаст пользователю ноль вместо данных, и ищи потом этот баг. Это самый неочевидный инвариант библиотеки, и именно на нём тесты отловили первые проблемы.
Ловушка была не последней — дальше начались грабли поинтереснее.
Всё нижеописанное — реальные баги, которые жили в коде и были найдены уже после того, как «всё работало».
Гонка на переключении. Смена политики жила в фоновой горутине: выяснить победителя (под локом), потом мигрировать данные и записать activePolicy — уже без лока. При том что докстринг функции миграции честно требовал write lock — рука, писавшая вызов, докстринг не читала. А публичные методы читают activePolicy под RLock'ом. Классический data race, который стабильно воспроизводится стресс-тестом, гоняющим Get/Add через границу эпохи под go test -race.
Потерянные инкременты. Счётчики hit/miss инкрементились обычным ++ под RLock'ом. RLock пускает читателей параллельно — значит, инкременты гонятся и теряются. Само по себе не падает, но бандит учится на заниженной статистике — тихо и незаметно. Лечится atomic.Int64.
Слепое пятно бандита. Статистику бандиту отдавали только тени. Активная политика копила счётчики, но никому их не отдавала и не сбрасывала — её «плечо» не получало свежих наблюдений, пока она у руля. А при разжаловании весь накопленный за активный срок хвост вываливался в первый же теневой отчёт, смещая апостериор. Починка: отдавать бандиту статистику всех политик и сбрасывать счётчики при смене роли.
Про ИИ-агентов обещанный пункт: все три гонки агент написал уверенно — вместе с комментарием «all methods are safe for concurrent use». go test -race придерживался другого мнения. Агенты сняли стоимость набора кода, но не стоимость инвариантов — их по-прежнему держит в голове человек.
Сэмплирование оказалось главным рычагом и по времени: Get на прогретом кэше — 34 ns/op у одиночного LRU, 681 у адаптивного без сэмплирования и 87 с ним. Стоимость перестаёт расти с числом теней, и это превращает идею из дорогой игрушки в инструмент. Одна тонкость, на которой легко обмануть себя: сэмплированные счётчики не домножаются обратно на 1/rate. Это вернуло бы масштаб, но выдумало бы уверенность — бандит получил бы бета-апостериор с двадцатикратно завышенным объёмом наблюдений. Вместо этого по той же выборке меряется и активная политика, чтобы у всех рук был одинаковый вес доказательств.
Сразу главный вывод, чтобы не держать интригу: адаптивный выбор ни на одной синтетической нагрузке не обогнал лучшую фиксированную политику. Дальше — цифры и объяснение, почему я всё равно считаю результат полезным.
Всё воспроизводится через make evidence (около 70 секунд); полный конвейер — прогон, графики и PNG для публикации — собирает скрипт build-assets.sh рядом со статьёй. Полная фактура одного прогона — стенд, команды, сырые таблицы — вынесена в benchmarks.md; здесь только выводы.
Кэш на 500 записей, 200 000 запросов на нагрузку.
| Нагрузка | as-cache | Лучшая фиксированная | Худшая | Разница с лучшей |
|---|---|---|---|---|
| zipf | 73.21% | LFU 73.47% | 62.51% | −0.26 п.п. |
| uniform | 9.97% | W-TinyLFU 12.33% | 9.99% | −2.36 п.п. |
| loop | 72.76% | W-TinyLFU 93.79% | 0.00% | −21.03 п.п. |
| scan | 37.74% | LFU 39.95% | 30.00% | −2.21 п.п. |
| phase-shift | 77.26% | W-TinyLFU 82.86% | 34.50% | −5.60 п.п. |
Читать это надо по колонке «худшая». На loop — циклическом проходе чуть больше кэша — LRU и LFU дают ровно ноль: каждый ключ вытесняется прямо перед тем, как он снова понадобится. as-cache даёт 72.8%. Это и есть продукт: не выигрыш гонки, а гарантия, что вы не окажетесь в нуле, не зная заранее, какую политику выбрать.
240 000 запросов, 12 фаз, чередование zipf и loop.
доля времени активной: LRU 2%, LFU 1%, TwoQueue 3%, ARC 2%, TinyLFU 91%
Бандит ведёт себя ровно как задумано: первую фазу исследует, перебирая LRU, 2Q, LFU и ARC, находит W-TinyLFU и держит его 91% времени. И не мечется на границах фаз — не потому, что сломан, а потому, что не на что переключаться: на этой нагрузке W-TinyLFU лучший в обоих режимах.
Отсюда вывод, который стоит запомнить всем, кто собирается мерить адаптивность на синтетике: чередование режимов само по себе не создаёт кроссовера. Чтобы адаптивность выиграла, нужны две политики, каждая из которых лучше в своём режиме. В моей синтетике такой пары не нашлось — и это дефект синтетики, а не бандита.
Настоящий аргумент нашёлся там, где я его не планировал: на опубликованных трейсах (Twitter Twemcache, ARC из FAST '03, LIRS). Скачиваются скриптом, в репозитории не лежат.
| Трейс | Лучшая фиксированная | Худшая | as-cache |
|---|---|---|---|
| Twitter Twemcache cluster052 | 2Q 59.6% | LFU 41.4% | 59.4% |
| ARC OLTP | 2Q 68.3% | LFU 45.4% | 67.1% |
| ARC P3 | W-TinyLFU 11.7% | LRU 1.9% | 12.7% |
| LIRS 2_pools | W-TinyLFU 54.8% | Random 50.1% | 54.4% |
| LIRS loop | W-TinyLFU 45.9% | LRU/LFU 0.0% | 42.5% |
Лучшая политика меняется от трейса к трейсу. 2Q выигрывает на Twitter и OLTP, W-TinyLFU — на P3 и LIRS. Причём на OLTP W-TinyLFU, эталон современных кэшей, оказывается вторым с конца. Вот это и есть ответ на спор из первой главы: универсально правильного выбора нет, и «возьмём то, что хвалят в интернете» — это ставка, а не решение.
Заодно синтетика получила по щам: классический LFU — лучшая политика на синтетическом zipf (73.5%) и худшая на обоих больших реальных трейсах (41.4% и 45.4%). Синтетический zipf держит популярность неподвижной — ровно то допущение, на котором стоит LFU. Реальный трафик дрейфует, и устаревшие счётчики частот намертво держат в кэше давно мёртвые ключи.
Все таблицы выше сравнивают мои политики между собой. Для человека, который выбирает кэш, это не тот вопрос: он выбирает не алгоритм, а пакет. Поэтому я прогнал те же нагрузки через те библиотеки, к которым в Go реально тянутся, — otter v2, theine, ristretto и sturdyc.
Тот же прогон make evidence; кэш 500, для этой части эпохи считаются по запросам (EpochRequests: 2000), поэтому её hit rate детерминирован и от машины не зависит.
| Нагрузка | otter v2 | theine | ristretto | sturdyc | as-cache |
|---|---|---|---|---|---|
| zipf | 73.13% | 72.39% | 69.83% | 62.02% | 72.65% |
| uniform | 9.97% | 10.71% | 9.96% | 9.51% | 10.01% |
| loop | 86.70% | 88.66% | 89.18% | 44.99% | 70.57% |
| scan | 39.85% | 39.88% | 39.86% | 30.01% | 39.20% |
| phase-shift | 77.82% | 80.97% | 71.88% | 53.07% | 76.12% |
as-cache не выигрывает ни одной. На трёх из пяти он в пределах пункта от лучшей библиотеки, на phase-shift отстаёт на 4.9 пункта, на loop — почти на 19. И он в 4–16 раз медленнее на операцию. Если вы выбираете кэш и у вас нет причин ждать смены формы трафика, честный ответ — otter или theine, и притворяться иначе в собственной статье было бы странно.
Чего это сравнение не показывает — нагрузки, на которой фиксированная библиотека проваливается. Все пять к ним добры: loop придуман против LRU, а кэши на базе W-TinyLFU с ним справляются. Аргумент за «померяйте свой трафик» держится на реальных трейсах, где лучшая политика меняется, а не на этой таблице.
Обе стоит рассказать, потому что вляпаться в них может кто угодно, кто меряет кэши.
otter в первом прогоне выиграл, потому что тайком держал в четыре раза больше данных. На uniform он показал 44.31% там, где все остальные давали свои законные ~10%. Выглядело как разгром. На самом деле otter принимает записи на горутине вызывающего, а вытесняет на фоновом проходе обслуживания: если писать в него без пауз, приём убегает вперёд вытеснения. Замер: 5000 ключей, записанных в кэш с MaximumSize: 500, оставили 1916 доступными. То есть сравнивался кэш вчетверо большего размера. После принудительного CleanUp те же 44.31% превращаются в 9.99%. Теперь в харнессе стоит тест, который валится, если любая библиотека уходит далеко за свою ёмкость.
Тот же эффект работает и в мою пользу — в моём же W-TinyLFU-плече. Под read-through нагрузкой оно держит 514 записей на zipf, 533 на loop и 611 на uniform при номинале 500. И вот на uniform это объясняет вообще всё: плечо удержало 611 ключей из пространства в 5000 и показало 12.33% — а 611/5000 это 12.2%. Та самая строка «uniform: лучшая фиксированная — W-TinyLFU 12.33%» в таблице выше — не про качество вытеснения, а про лишнюю ёмкость. На read-heavy нагрузках перебор — единицы процентов, и там сравнение честное.
Второй прогон того же сравнения разошёлся с первым на 12 пунктов. Потому что эпохи были привязаны к таймеру, а машина под нагрузкой переоценивает политики реже. Из-за этого и появился EpochRequests: с эпохами по запросам повторные прогоны сходятся в пределах половины пункта. Остаток расхождения — это W-TinyLFU-плечо, которое невоспроизводимо by design: otter вытесняет асинхронно и сообщает приблизительный размер.
Семь политик, 50 000 записей по 256 байт:
| Конфигурация | Память | Множитель | Get |
|---|---|---|---|
| одиночный LRU | 18.5 MiB | 1.00x | 34 ns |
| адаптивный, 7 политик | 48.8 MiB | 2.64x | 681 ns |
адаптивный + ShadowSampleRate: 0.05 |
24.5 MiB | 1.33x | 87 ns |
Ноль аллокаций на Get во всех трёх конфигурациях.
Цифры выше довольно однозначно говорят: как «кэш, который всех обгонит» библиотеку продавать нечестно. Зато они же подсказали, чем она на самом деле полезна.
Режим советника. Если самое ценное — не переключение, а измерение, то переключение можно просто выключить. ObserveOnly: true — и кэш ведёт себя ровно как та политика, которую вы дали первой, но все остальные продолжают меряться на вашем трафике. Advice() отвечает на вопрос, ради которого в первой главе не нашлось недели:
On this traffic TwoQueue beats LRU by 3.28 points of hit rate, over 240 epochs.
policy hit rate hits misses
TwoQueue 59.62% 596200 403800
*LRU 56.34% 563400 436600
Риска — ноль: поведение кэша не меняется вообще. Бандит в этом режиме можно не писать вовсе, его аргумент допускает nil. Мне кажется, это и есть главный продукт: спор из 2021 года закрывается за неделю цифрами, а дальше вы деплоите победителя статически и живёте без всякой адаптивности.
Флот. У режима «пусть решает бандит» есть неприятная граница: реплика, которая видит мало трафика, не может различить свои руки — апостериоры перекрываются, и выбор становится почти случайным. Пятьдесят реплик за балансировщиком — это ровно такой случай: каждая видит одну пятидесятую доказательств. Модуль as-cache/bandit умеет складывать поэпохальные счётчики через Valkey или Redis: реплики публикуют числа, одна из них за координационную эпоху читает агрегат, выбирает и публикует решение для остальных.
Замеры и здесь получились с двумя сторонами. Когда реплики реально голодают (около восьми запросов на эпоху каждая), пул даёт +2.3…3.9 пункта против «каждый решает сам», и механика видна невооружённым глазом: голодающие реплики расползаются по пяти разным политикам, пулящийся флот держит одну. Когда реплики не голодают — пул проигрывает: около пункта на однородном трафике и около пяти пунктов на флоте, где реплики обслуживают разные нагрузки и одно общее решение оказывается компромиссом, который не нужен никому.
Отдельно стоит сказать про то, чего в этих числах нет: координация в замерах бесплатная, потому что стор в памяти процесса. В проде за неё платят сетью, и самая выгодная в таблице настройка — самая дорогая в реальности.
Брать:
- Кэш перед дорогим бэкендом — тяжёлые SQL, внешние API, кросс-региональные вызовы. Когда промах стоит десятки миллисекунд, микросекунды оверхеда на тени невидимы, а лишние проценты hit rate — это ощутимая разгрузка базы.
- Нагрузка со сменой режимов — днём интерактив (территория LRU), ночью батчи и сканы (территория LFU/2Q). Ровно тот случай, где переключение целых политик даёт больше, чем внутренняя адаптация одной.
- Режим советника — самый безопасный вход, и, судя по замерам, самый ценный: погонять в staging или в проде на реальном трафике, посмотреть
Advice(), задеплоить победителя статически. Ноль рантайм-риска. - Флот из голодающих реплик — если каждая реплика видит слишком мало трафика, чтобы различить политики, но вместе они видят достаточно.
Не брать:
- Наносекундные in-process кэши на горячем пути — там O(N политик) на операцию и глобальный лок убивают идею; берите otter или theine. И по замерам выше — берите их и в куче обычных случаев тоже.
- Вы уже померяли свой трафик и знаете победителя. Тогда просто возьмите эту политику: лучшее, на что здесь можно рассчитывать, — сравняться с ней.
- Системы с жёстким p99 — эпохальные переключения дают предсказуемые всплески промахов.
- Память впритык — множитель 2.64x (или 1.33x с сэмплированием) никто не отменял.
- Флот, где реплики обслуживают разные нагрузки, — общее решение будет хуже, чем у каждой своё.
И главное про статус: это pre-1.0. Не «эксперимент, которому нельзя верить» — всё, что написано выше, воспроизводится одной командой, конкурентность гоняется под -race и разобрана враждебным ревью, — но API ещё может поменяться, и в проде эту библиотеку, насколько я знаю, пока никто не крутил.
Тот роадмап, который был в первой версии этой статьи, закрыт целиком: конкурентность починена, сэмплированные тени сделаны и измерены, 2Q, ARC, TTL, Random и W-TinyLFU приехали, прогоны на публичных трейсах есть, advisor mode есть. Сверху добавился распределённый бандит. Всё это опубликовано как v0.2.0 — восемь модулей, каждый со своей лицензией; до этого релиза ни один подмодуль ни разу не был затегирован, так что go get на policies у постороннего человека честно падал с unknown revision v0.0.0. Следом вышел v0.3.0 (модулей стало девять): эпохи по запросам (EpochRequests), модуль benchclient — адаптер под чужие бенчмарк-стенды вроде maypok86/benchmarks, сравнение с otter/theine/ristretto/sturdyc из главы про замеры и починка Thompson-бандита, который игнорировал собственный seed: сэмплы раздавались рукам в порядке обхода map, так что seed фиксировал последовательность чисел, но не то, кому они достаются.
Что осталось и что я осознанно не делаю:
- Чтение всё ещё под локом. Lock-free путь я померял и отложил: на политике, которая сама берёт эксклюзивный лок на
Get(а так делает любой LRU — чтение двигает recency), потолок выигрыша около 25% на операцию, а цена — протокол ретраев на все шесть делегирующих чтений, ломающийся публичный интерфейс иMigrationGradual, который вообще не умеет lock-free, потому что продвигает ключи изнутриGet. - Эпохи по настенным часам нельзя прошагать в тестах.
EpochRequestsзакрыл это для замеров, но нормального тестового шва всё ещё нет. - Адаптивного размера кэша нет. Адаптируется выбор политики, а ёмкость — какую поставили.
- Продакшена нет. И это, пожалуй, единственный пункт, который сейчас реально нужен: одна реальная нагрузка полезнее любой следующей фичи.
Если хочется поучаствовать — самое понятное место входа теперь не обёртки над политиками (они написаны), а обёртка над theine как ещё одним плечом бандита: по замерам выше она единственная из чужих библиотек, которая обыгрывает или повторяет otter на трёх нагрузках из пяти.
А спор из 2021 года я, кажется, наконец могу закрыть. Правильный ответ был не «LRU» и не «LFU». Правильный ответ — «спросите у бандита».
Вдохновение:
- А. Миловидов, «Как ускорить разжатие LZ4 в ClickHouse» (Хабр, 2019) + видео доклада, HighLoad++ Siberia 2018
- Introducing Ristretto — адаптивность в кэшах Go
Политики вытеснения:
- Johnson, Shasha — 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm (VLDB '94)
- Megiddo, Modha — ARC: A Self-Tuning, Low Overhead Replacement Cache (FAST '03)
- Einziger, Friedman, Manes — TinyLFU: A Highly Efficient Cache Admission Policy (arXiv:1512.00727)
- Caffeine wiki: Efficiency
Адаптивный выбор политики (academia):
- Vietri et al. — Driving Cache Replacement with ML-based LeCaR (HotStorage '18)
- Rodriguez et al. — Learning Cache Replacement with CACHEUS (FAST '21)
- Yang et al. — A Large Scale Analysis of Hundreds of In-memory Cache Clusters at Twitter (OSDI '20), twitter/cache-trace
Код:
- sshaplygin/as-cache — сама библиотека
- hashicorp/golang-lru, stitchfix/mab
- Кэши, с которыми сравнивался: maypok86/otter, Yiling-J/theine-go, dgraph-io/ristretto, viccon/sturdyc
- maypok86/benchmarks — чужой стенд для сравнения Go-кэшей; конфигурация ristretto и theine в моих замерах взята оттуда, чтобы числа можно было читать рядом с опубликованными там