Всем привет! Меня зовут Алексей Майшев, я работаю Go-инженером в Авито. В этой статье рассказываю, как мы с командой независимых разработчиков 9 месяцев проектировали и разрабатывали кэш-библиотеку следующего поколения для Go — otter. 

Вы узнаете, чем нас не устроили текущие кэш-библиотеки в Go, какие подходы и оптимизации мы рассматривали и на каких остановились, как замеряли производительность и потребление памяти и в чём otter превосходит конкурентов. А ещё тут будет много теории — в процессе работы над библиотекой нам приходилось читать много страшных научных статей на тему кэшей.

С этим докладом я уже выступал на Golang Conf X 2025, для тех, кто хочет посмотреть или послушать — вот ссылочка.

Что внутри статьи:

• Зачем нужна еще одна кэш-библиотека?

• Основные понятия теории кэширования

• Выбираем политику вытеснения

• Оптимизируем latency/throughput

• False sharing

• Concurrent Hash Table

• Concurrent eviction

• Буферы событий

• Добиваемся out-of-order consistency

• Оптимизируем производительность

• Выбираем политику экспирации

• Экономим память

• Мораль: как спроектировать и не умереть

Зачем нужна ещё одна кэш-библиотека?

На GitHub уже достаточно много открытых библиотек для работы с кэшами на Go. Но большая часть готовых решений сделаны так себе: 

• имеют кучу issues и багов, которые не чинят годами; 

• используют в качестве eviction policy банальный LRU;

• не реализуют даже малую часть потенциала on-heap-кэшей.

А у нынешнего лидера on-heap-мира — Ristretto — накопились проблемы: например, неудачный релиз v2, который поломал билды куче компаний, или нарушение обратной совместимости ещё в первой версии, из-за которой упал хитрейт. Поэтому мы решили сделать ещё одну библиотеку с учётом опыта предыдущих наработок. В результате получился otter, который вы можете опробовать по ссылке на GitHub.

Основные понятия теории кэширования

On-heap и off-heap кэши. В языках программирования с Garbage Collector (GC) разделяют на два вида: on-heap и off-heap. В on-heap мы храним значения в куче и отдаём управление памятью на откуп GC. В off-heap — выделяем память сами (например, через mmap) и управляем ею вручную; данные при этом живут вне кучи. Сравнение on-heap и off-heap кэшей приведено в таблице ниже. 

В этой статье мы подробно остановимся на on-heap кэшах.

Основные показатели

• Hit rate — доля запросов, при которых данные найдены в кэше.

• Latency — время ответа кэша на один запрос.

• Throughput — количество запросов, которые кэш обрабатывает за единицу времени.

• Memory usage — объём памяти, занимаемый данными в кэше.

Это четыре опоры, вокруг которых обычно крутятся все решения и компромиссы.

Recency и frequency. Ещё два важных понятия кэша, к которым мы будем обращаться.

• Recency — как давно встретился элемент в прошлый раз.

• Frequency — насколько часто встречался элемент.

Обычно политики вытеснения используют при принятии решений о вытеснении только один из этих показателей. Но существуют и политики вытеснения, которые могут учитывать оба этих показателя  — мы увидим это на примере W-TinyLFU и S3-FIFO.

Распределение. Хитрейт зависит от распределения запросов, которые прилетает в кэш. В типичных веб-нагрузках последовательность ключей подчиняется Zipf-распределению, об этом говорят все исследования за последние 20 лет.

Если упрощать — это что-то типа закона «80 на 20»: небольшая доля элементов встречается очень часто, «длинный хвост» — редко. 

Политика вытеснения. Хитрейт также зависит от политики вытеснения. Она решает, какой элемент выкинуть при переполнении. Вот основные политики: 

• LRU;

• LFU;

• ARC;

• LIRS;

• Clock(-Pro) and family;

• W-TinyLFU.

В следующем разделе мы рассмотрим некоторые из них.

Выбираем политику вытеснения

Рассказываю про основные политики вытеснения элементов в кэше и о том, какой выбрали мы.

Обычно к политикам вытеснения предъявляют следующие требования:

• около-оптимальный хитрейт; 

• устойчивость к кэш-атакам (сканирование, «одиночные попадания»);

• адекватный оверхед по памяти;

• реализуемость без страданий. 

Подробно я остановлюсь только на LRU и LFU, поскольку они — строительные кирпичики для всего остального. ARC и LIRS рассматривать не буду. У ARC — лицензия IBM (для многих компаний сейчас это недостаток) и уязвимость к ряду кэш-атак. LIRS теоретически хорош, но сложен в реализации и имеет большой оверхед по памяти.

1. Last Recently Used (LRU) — учитывает только метрику recency, отдаёт предпочтение самому последнему элементу. 

• Сложность: O(1) для всех операций, так как для реализации используются двусвязные списки.

• Уязвим к скану и one-hit wonders — это элементы, к которым обратились всего один раз. Они занимают место в кэше, но не повышают хит-рейт.

• Каждое чтение превращается в запись в общее состояние из-за перемещений в списке, что под конкуренцией ощущается неприятно.

2. Last Frequently Used (LFU) — приоритезирует выселение на основе frequency, отдает предпочтение наиболее часто встречающемуся элементу.

• Сложность: O(log n) для всех операций, так как для реализации используются деревья.

• Не подвержена загрязнению кэша.

3. Window-TinyLFU (W-TinyLFU) — более продвинутая политика вытеснения, которая учитывает обе метрики: и recency, и frequence. 

W-TinyLFU состоит из 3 частей: маленькое LRU-окно, TinyLFU-фильтр и большое сегментированное LRU. LRU до фильтра — recency-biased, после фильтра — frequency-biased. 

Вот, как это работает. Сначала элемент попадает в LRU-окно. Если он вытесняется, то проходит проверку через TinyLFU-фильтр. Если его ожидаемая частота оказывается выше, чем у жертвы из сегментированного LRU, мы меняем жертву на этот элемент. То есть до Segmented LRU допускаются только элементы с предполагаемой частотой выше, чем у жертвы. 

Подробнее про TinyLFU можно прочитать в этой статье.

W-TinyLFU — хорошая политика вытеснения, поскольку учитывает и recency, и frequency, но в ней тоже есть недостаток: LRU-окно по умолчанию очень маленькое — 1%. Поэтому на ворклоадах, склонных к recency (например, OLTP, который распространён в Go), эта политика может показывать себя не очень хорошо. 

Есть модифицированная реализация, в которой LRU-окно динамическое и может увеличиваться вплоть до 100% (тогда W-TinyLFU по сути превращается в LRU), но реализовывать такое сложно, поэтому мы решили посмотреть политики попроще.

4. S3-FIFO — одна из самых свежих политик вытеснения, вышла в 2023 году и является потомком Clock-Pro. Подробнее про S3-FIFO можно прочитать тут.

S3-FIFO состоит из 3 очередей: две «реальные» — для элементов — и одна «призрачная» — для их хэшей, это помогает запоминать большее количество обращений к кэшу, чем ограничено ёмкостью кэша. Сначала элемент вставляется в маленькую очередь. Если выбивается из неё и его частота больше 1 — вставляется в главную очередь. Если же частота = 1 — элемент вытесняется из кэша и его хэш вставляется в призрачную очередь.  

Очень важно, что S3-FIFO не требует записи в общее состояние. При чтении мы обновляем только частоту элемента, что не требует эксклюзивных блокировок. 

В otter мы используем S3-FIFO — этот подход удовлетворял нашим потребностям и был не таким сложным в реализации, как W-TinyLFU. На графиках ниже приведены результаты бенчмарка на типовых нагрузках: Zipf, DS1, P8, OLTP, LOOP, AlibabaBlock. На веб-ворклоадах S3-FIFO показывает себя как минимум не хуже, а часто и лучше LFU-семейства; на чисто frequency-нагрузках LFU ждёт своего звёздного часа — это осознанный компромисс. 

Результаты сравнения otter с другими кэш-библиотеками на Go по хитрейту

Оптимизируем latency/throughput. False sharing

В этом и следующих разделах я расскажу, как мы оптимизировали latency и throughput — как на физическом уровне (работа с CPU cache и false sharing), так и на уровне архитектуры кэша (хэш-таблица, политика вытеснения, буферы событий).

Здесь поговорим про проблему false sharing — ситуацию, когда несколько потоков работают с разными переменными, но попадающими в один и тот же кеш-лайн процессора. 

Данные между кэшем и памятью передаются блоками фиксированного размера по 64 байта, они также называются линиями кэша (англ. cache line).

Если часто изменяемые (горячие) поля разных структур попадают в одну и ту же cache line, процессору приходится постоянно инвалидировать и синхронизировать её между ядрами. В результате возникает лишний contention прямо на уровне железа.

Лечится это добавлением padding к горячим переменным (например, счётчикам попаданий/промахов), чтобы они обновлялись независимо и спор за них не происходил. 

При добавлении padding производительность в случае contention резко растёт, это видно на графике ниже.

Оптимизируем latency/throughput. Concurrent Hash Table

Concurrent Hash Table — важный компонент, влияющий на latency и throughput. Под конкурентной нагрузкой простое шардирование через map + RWMutex перестаёт работать эффективно. 

Проблема в том, что некоторые бакеты используются значительно чаще других — они становятся «горячими». Если к такому бакету одновременно обращаются несколько потоков, то они все вынуждены ждать освобождения одной и той же блокировки. В итоге именно эти горячие бакеты превращаются в точки серьёзного contention, что увеличивает задержки и снижает общую пропускную способность.

В этом разделе я покажу, как в otter устроена CLHT (Cache-Line Hash Table), какие приёмы позволяют минимизировать блокировки при чтении и записи, и почему это критично для высокой производительности кэша.

Основные идеи CLHT такие: 

• чтения — lock-free; 

• при вставке/обновлении блокируется только один бакет; 

• конкуретное расширение блокирует только записи, но не останавливает чтения. 

Подробнее про CLHT можно посмотреть в этом докладе.

По схеме ниже видно, почему CLHT так называется. Бакеты выровнены в соответствии с размером кэш-линии, состоят из мьютекса, 3 хэшей, 3 нод и указателя и на следующий бакет. 

Большинство чтений происходит примерно так: используем пару лоад-операций, если находим совпадающие хеши — проверяем ноды. Если всё совпало — возвращаем ответ. Это видно в сниппете ниже.

for i := 0; i < entriesPerMapBucket; i++ {

   h := atomic.LoadUint64(&b.hashes[i])

   if h == uint64(0) || h != hash {

      continue

   }

   eptr := atomic.LoadPointer(&b.entries[i])

   if eptr == nil {

      continue

   }

   e := (*entryOf[K, V])(eptr)

   if e.key == key {

      return e.value, true

   }

}

Оптимизируем latency/throughput. Concurrent eviction

Concurrent eviction — это процесс вытеснения элементов из кэша в условиях многопоточной нагрузки, когда несколько потоков одновременно обращаются к кэшу и могут попытаться удалить или обновить одни и те же элементы.

Это ещё одно узкое горлышко для latency и throughput. При классическом LRU вытеснение требует обновления двусвязного списка, что под конкурентной нагрузкой вызывает блокировки и contention. Давайте разберёмся, как можно решать эту проблему. 

Один из вариантов — использовать clock-based политики вытеснения. Основная идея в том, что мы при чтении не требуем обновления общего состояния. А при вытеснении можно использовать lock-free структуры данных, поскольку мы используем очереди. 

Однако если у вас много очередей и происходит много перемещений, это даже хуже, чем взятие блокировок. Также такая архитектура заставляет жить в lock-free архитектуре, поэтому, например, добавить политику экспирации, будет трудно: они обычно требуют блокировок.

Ещё идея — использовать сэмплирование. При чтении обновляем локальную частоту, а при вытеснении берём k случайных элементов и удаляем элемент с минимальной частотой. Но из-за рандома хитрейт получается низким. 

Наш выбор пал на BP-Wrapper. Эту технику придумали авторы PostgreSQL, когда решали похожую задачу. Идея в том, чтобы добавить log-based структуры данных к кэшам. Как это работает: 

1. Сразу применяем операцию к хэш-таблице.

2. Записываем событие (read/insert/update) в буфер.

3. Применяем события асинхронно батчами под одной блокировкой к политике вытеснения.

Подробнее про BP-Wrapper можно почитать здесь.

Таким образом любая политика становится contention-free. 

Оптимизируем latency/throughput. Буферы событий

Для масштабируемой работы кэша в otter используются два типа буферов событий: Read и Write. Они позволяют минимизировать блокировки.

Read Buffer в otter— это набор шардированных кольцевых буферов. Шардирование теоретически должно происходить по pid, но в Go он недоступен, поэтому мы выбираем рандомно. 

Если замечаем contention (CAS-конфликты), добавляем дополнительные буферы. Важно, что read-буфер может терять события, если заполнен и произошло слишком много ретраев вставки — но это допустимо: политике вытеснения нужно понять часто/не часто встречается элемент, а не точную частоту элемента. Обработка запускается, как только какой-то из буферов заполнится. 

Вот, как примерно происходит добавление в буфер:

func (r *ring[K, V]) add(n node.Node[K, V]) Status {

   head := r.head.Load()

   tail := r.tail.Load()

   size := tail - head

   if size >= bufferSize {

      return Full

   }

   if r.tail.CompareAndSwap(tail, tail+1) {

      atomic.StorePointer(&r.buffer[tail&mask], n.AsPointer())

      return Success

   }

   return Failed

}

Write Buffer в otter — тоже кольцевой и ограниченный, но умеет расширяться до максимума. Он не теряет события, поскольку операции записи критичны. Полный буфер — редкость: для этого нужно, чтобы write rate ≫ replay rate. Применение событий из write-буфера начинается сразу. 

Как это работает? Пока не кончилась выделенная память, воспринимаем её как обычный кольцевой буфер. Если память закончилась, выделяем в два раза больше и разматываем буфер.

А вот, как примерно происходит добавление в буфер: 

func (g *Growable[T]) Push(item T) {

   g.mutex.Lock()

   for g.count == g.maxCap {

      g.notFull.Wait()

   }

   g.push(item)

   g.mutex.Unlock()

}

func (g *Growable[T]) push(item T) {

   g.grow()

   g.buf[g.tail] = item

   g.tail = g.next(g.tail)

   g.count++

   g.notEmpty.Signal()

}

Это одна из самых медленных реализаций, как вы можете видеть на графике ниже. Но тем не менее выбрали мы её осознанно.

Дело в том, что каналы требуют заранее указывать размер буфера записи, а lock-free реализации хоть и быстрее, но при участии сборщика мусора картинка становится печальнее, поскольку такие структуры аллоцируют память и нагружают GC. 

Добиваемся out-of-order consistency 

В условиях высокой нагрузки события кэша (чтения, записи, удаления) могут приходить и обрабатываться в неправильном порядке. Это приводит к ошибкам — например, может удалиться элемент, который только что был удалён и снова добавлен.

В otter для борьбы с этой проблемой мы используем состояния для нод: 

• Alive — элемент живёт и в хэш-таблице, и в политике; 

• Retired — удалён из таблицы, но не удалён из политики; 

• Died — удалён и из таблицы, и из политики. 

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

Оптимизируем производительность

Для оптимизации конкуретных обновлений мы использовали подход Read-Copy-Update (RCU). 

Фактически мы считаем, что update = delete + insert. В кэше нас интересует «достаточная» скорость вытеснения/записи, проигрыша в скорости insert точно не будет. 

Если система способна выкидывать миллион+ элементов в секунду под нагрузкой, этого обычно достаточно большинству пользователей: промахи всё равно ограничены скоростью «медленного» хранилища. В RCU-подходе обновление — это удаление старого и вставка нового; проигрыша к insert нет, а если используете Cost(bytes), update очень вероятно превратится в insert.

Затем мы замерили производительность otter на фоне других библиотек, для этого собрали микро-бенчмарк. В нём используются следующие идеи:

• применяем Zipf distribution;

• минимизируем вспомогательную работу во время исполнения. Использует только index increment, slice lookup и loop; 

• заполняем кеш элементами заранее. Это важно, потому что в бенчмарках корректно симулировать «медленное» хранилище не получится: промахи становятся слишком быстрыми, так как не требуется обращаться к внешнему источнику и обновлять политику вытеснения. При этом у разных кэшей хитрейт может сильно отличаться, и если у конкретного кэша он низкий, то на таких синтетических бенчмарках он получает непропорционально большое преимущество.

Результаты сравнения приведены на графике ниже.

Как видно на графике, по производительности otter опережает существующие библиотеки при 75% чтения и 25% записи. Ну и давайте не забывать, что в theine в последних версиях использует позаимствованный буфер чтения.

Выбираем политику экспирации

В этом разделе расскажу, какие существуют политики эскпирации элементов в кэше и какой выбрали мы. Всего существует 3 подхода к эспирации:

1. Lazy. Полагаемся на вытеснение: просто выкидываем просроченные элементы, когда до них дошли. Например, так делал когда-то Redis. Плюс — простота, минус — кэш может «засоряться» мёртвыми значениями; 

2. Fixed. У всех элементов одинаковый TTL. Легко реализуется, имеет сложность O(1). Единственный минус — если нужны разные TTL для разных элементов, такой подход не подходит;

3. Variable. Позволяет использовать разные TTL для разных элементов — это гибко. Но обычно использует дерево, поэтому сложность O(log n). Также при масштабировании такой подходы может быть медленным.

В otter мы решили предоставить возможность использовать как Fixed Expiration, так и Variable Expiration. При создании кэша библиотека требует указать TTL для записей. TTL будет изменять порядок при каждой операции записи.

Переменный TTL тоже можно задать, но в таком случае под капотом будет работать механизм Timer Wheels, он позволяет экспирировать элементы с амортизированной сложностью O(1). Каждое колесо представляет приблизительный промежуток времени (секунда, минута, час, день, неделя). Стрелка часов тикает, когда бакеты экспирируются и их можно зачищать. Перемещение большего колеса может приводить к вставкам в меньшее колесо.

Подробнее про Timer Wheels можно почитать в этой статье.

Экономим память

Даже при высокой скорости работы кэш может стать узким местом, если потребляет слишком много памяти. В otter мы оптимизируем использование памяти на нескольких уровнях. Для этого мы применяем следующие приёмы: 

• динамический рост буферов — их размеры увеличиваются под текущую нагрузку, чтобы экономить память, когда нагрузка невысока;

• выравнивание горячих полей — контролируем расположение часто используемых полей, чтобы уменьшить false sharing и лишние аллокации;

• облегчённые ноды под конкретные конфигурации — каждая нода хранит ключ, значение, служебные поля и дополнительные метаданные для выбранных функций. Если, например, в конфигурации не используется политика экспирации, поле expiration не создаётся, что экономит порядка 24 байт на элемент.

type BEС[K comparable, V any] struct {

   key        K

   value      V

   prev       *BEC[K, V]

   next       *BEC[K, V]

   prevExp    *BEC[K, V]

   nextExp    *BEC[K, V]

   expiration int64 // не будет использована, если не нужна экспирация

   cost       uint32

   state      uint32

   frequency  uint8

   queueType  uint8

}

На графиках ниже видно, что otter в сравнении с конкурентами потребляет меньше всего памяти и на маленьких (1000), и на больших (1000000) кэшах. 

Сравнение otter с кэш-библиотеками на Go по потреблению памяти на маленьких и больших кэшах

У Ristretto плохие показатели просто потому, что они используют большой захардкоженный буфер записи. 

Мораль: как спроектировать и не умереть

1. Декомпозируйте проблемы, чтобы оптимизировать их по отдельности: отдельно думать про хэш-таблицу, отдельно — про политику вытеснения, про буферы событий, про экспирацию. 

2. Комбинируйте простые структуры при создании сложных фич. Например, лучше использовать один аккуратный лок под батч операций, чем десяток хрупких CAS по всему коду. 

3. Проверяйте корректность системы целиком, а не кусочков по отдельности. 

4. Используйте 6 мантр оптимизации (мне они очень помогли):
   — Не делай это.
   — Делай это, но не делай это снова.
   — Делай это дешевле.
   — Делай это реже.
   — Делай это позже.
   — Делай это параллельно. 

Полезные ссылки

• Кэш-библиотека для Go — otter (GitHub)

• Мой доклад про otter на Golang Conf X 2025 (YouTube).

• Статья про Zipf-распределение. Web Caching and Zipf-like Distributions: Evidence and Implications (PDF).

• Статья про TinyLFU. TinyLFU: A Highly Efficient Cache Admission Policy (PDF)

• Сайт с визуализаций S3-FIFO.

• Доклад Андрея Печкурова с подробностями о CLHT. Is it time to re-sync? (YouTube)

• Статья про BP-Wrapper. BP-Wrapper: A System Framework Making Any Replacement Algorithms (Almost) Lock Contention Free (PDF)

• Статья про Clock Wheels. Hashed And Hierarchical Timing Wheels: Efficient Data Structures For Implementing A Timer Facility (PDF)

Спасибо вам за уделенное статье время! Интересно узнать ваше мнение о otter, что вам понравилось, что нет, что нужно улучшить? Отзывы очень жду в комментариях. Там же призываю рассказывать о вашей любимой кэш-библиотеке и том, почему она так хороша.

Больше о том, что мы делаем в команде AvitoTech — по этой ссылке. Вакансии вы найдете вот здесь, рекомендую также глянуть наш Telegram-канал, там интересно. До встречи!