#highload

Вы почти наверняка знаете про LRU (Last Recently Used) кеш. Давайте на всякий случай вспомним. Мы храним до k некоторых значений, при этом поддерживая время последнего обращения. При появлении в кеше k+1-ого элемента удаляем элемент, к которому обращение было "давнее" всего. Делается это просто: держим лист ключей (в начале самые молодые по времени обращения элементы, в конце самые старые) и мапку из ключа в итератор этого листа. При необходимости удалить, просто кикаем из листа последний элемент. При необходимости обновить время обращения к элементу, получаем из мапки итератор на ноду листа и переставляем её в самое начало. Базово так. У Антона Полухина есть интересный доклад про оптимизацию LRU. Речь о том коде, который является базой для кешей в половине случаев, которые я у нас вижу. Да, вы может видели мнения, что LRU -- неудачник среди кешей, но часто его хватает.

Чуть менее примитивным вариантов является сегментированный LRU. По факту это несколько LRU. Сначала кладём в первый кеш. При запросе элемента из него, перемешаем во второй. И т.д. Эти кеши условно можно называть cold, warm и hot (в случае трёх частей). Как будто поколения в сборщиках мусора.

Прокачаным LRU является 2Q. Тут есть три части. Первая (in) + вторая (out) -- обычная FIFO очередь. При добавлении в кеш элемент кладётся в in. Со временем он переходит в out (который обычно значительно больше in). Третья часть -- hot cache (например LRU). Элементы из in вытесняются в out.
Если запрашивается элемент, который в in, с ним ничего не происходит. Если который в out, он перемещается в hot. Если элемент был вытеснен в out и не запрашивается, он просто удаляется из кеша при достижении какого-то размера.
Юзается в postgres.

Хотя когда-то в postgres использовался ARC (adaptive replacement cache), но там тёрки за патенты с IBM. Суть в том, что у вас есть две части: L1 (для recently used элементов) и L2 (для частоиспользуемых элементов). Каждая L часть состоит тоже из двух частей: из самих элементов кеша (T) и из удалённых из него элементов (B/ghosts lists), которые тем не менее ещё трекаются. Если элемент из B1 опять появляется в кеше, он возвращается в T1. При этом один элемент из T2 вытесняется в B2. И наоборот. Такое взаимодействие вот.

LFU -- least frequently used. У каждого элемента есть счётчик количества обращений. Элемент с наименьшим значением счётчика удаляется. Если элементов с минимальным значением несколько, по порядку FIFO. Понятно, что очень просто сделать такое с помощью std::set, но есть алгоритм, который позволяет вставку, lookup и удаление за O(1) (опять хеш-таблица и связанные списки специфического вида).

Есть ещё несколько разных стратегий:
- MRU: удаляем последний использованный элемент (бережём старые элементы);
- Mid point LRU: сегментированный LRU с двумя частями (cold, hold);
- MQ: сегментированный LRU, в котором запоминается место, из которого элемент вытесняется (если знание о месте из кеша не пропало). При повторном появлении в кеше, он вставляется в это место. Так можно быстрее прогревать кеш при циклической ротации элементов.
- алгоритм Белади: отбрасывать из кеша ту информацию, которая не понадобится в будущем дольше всего. Так как в общем случае невозможно предсказать, когда в следующий раз пригодится именно эта информация, то на практике подобная реализация невозможна (в общем случае). Можно вычислить опытным путём, после чего сравнить такую реализацию с текущим кешом;
- pseudo-LRU: оптимизированный LRU, позволяющий тратить гораздо меньше памяти.

=============================
Заканчиваю вот универ. Чувствую, как появляется больше времени на (пора)ботать, пусть и последние несколько месяцев ничего почти по нему не делал. Хочется наконец найти силы и методично разобрать огромный накопившийся беклог + попробовать в пару начинаний. Непонятно, как оно получится и получится ли вообще, но если будут предприниматься какие-то действия, обязательно поделюсь.