Алгоритмы кэширования

На досуге решил поразбираться с алгоритмами кеширования, и узнал что кроме всем известных LFU и LRU есть целый зоопарк различных алгоритмов со своими достоинствами и недостатками. Некоторые из них я изучил более подробно, написал свои реализации и сравнил эффективность. В качестве данных использовался лог запросов в базу данных картинок одного высоконагруженного сайта. Запросы не обладают свойством локальности, но обладают свойством частотности. То есть запрошенный элемент, как правило, запрашивается только по прошествию какого-то времени. Поэтому для такого потока данных лучше всего подходят алгоритмы кэширования обладающие ствойством LFU кэша. Это и будет видно на графиках.

OPT

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

FIFO

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

LFU

Каждый элемент имеет счётчик обращений. Новый элемент вставляется в кэш со значением счётчика равным 1. При попадании в кэш счётчик найденного элемента увеличивается на 1. Если нужно освободить место, нужно найти элемент с самым маленьким значением счётчика. Таким образом вытесняется тот элемент, которые запрашивался реже всего.
Главный недостаток LFU состоит в том, что некогда частотные элементы могут присутствовать в кэше очень долго, даже если они уже давно не запрашивались.
Реализация.

LRU

Новый элемент вставляется в голову списка. При попадании в кэш элемент перемещается в голову списка. Если нужно освободить место, вытесняется элемент из хвоста списка. Таким образом вытесняется тот элемент, которые не запрашивался дольше всех.
Главный недостаток LRU состоит в том, что он не устойчив к линейному чтению, т.к. оно вымывает все "прогретые" данные.
Реализация.

Сегментный LRU (SNLRU)

Один из недостатков LRU в том, что если мы вставили новый элемент в кэш, и этот элемент больше не будет никогда запрошен, ему придётся пройти через весь список, пока он не будет вытеснен. Сегментный LRU решает эту проблему. Кэш организован ввиде нескольких (N) LRU кэшей. Новый элемент вставляется в нулевой LRU кэш. При попадании в кэш элемент перемещается в следующий LRU кэш, либо на MRU (Most Recently Used) позицию последнего LRU кэша, если выше уже идти некуда. При вытеснении элемента из k-го LRU кэша он перемещается в k-1 LRU кэш. По достижению нулевого LRU кэша элемент удаляется.
Алгоритм устойчив к линейному чтению, т.к. новые элементы не могут вытеснить прогретые. При этом он обладает свойством LFU алгоритма - элементы перемещается в следующий список при каждом попадании в кэш. Более того, если взять N достаточно большим, то получится LFU кэш. При этом сегментный LRU обладает тем же недостатком LFU - частотные в прошлом элементы будут долго сидеть в кэше прежде чем вымоются оттуда.
Реализация.

Mid point LRU

Является вариацией сегментного LRU, в котором количество сегментов - 2, и эти два сегмента делят кэш не пополам, а в некоторой пропорции. Размеры сегментов подбирается эмпирически и зависит от характера потока данных. Этот алгоритм очень просто реализуется и на деле показывает один из лучших результатов. Обладает всеми достоинствами сегментного LRU.
Реализация.

2Q

Кэш разделяется на три части:

• In - FIFO кэш, в который попадают все новые элементы;
• Out - FIFO кэш, в который попадают элементы, вытесненные из In. При этом этот кэш хранит ключ и не хранит значение, поэтому его можно сделать достаточно большим;
• Main - главный LRU кэш, в который попадают новые элементы найденные в Out. При вытеснении элемента из главного кэша он удаляется.

Алгоритм устойчивость к линейному чтению.

Оригинальная статья с описанием, реализация.

MQ

По сути является сегментным LRU но с некоторыми существенными улучшениями.

Для каждого элемента ведётся счётчик его запросов. Номер LRU кэша, в который стоит поместить элемент вычисляется используя некоторую функцию от этого счётчика, например логарифм.

Возможна ситуация, когда элемент, который вытесняется из кэша, в ближайшем будущем может стать очень популярным, поэтому имеет смысл как-то запоминать позицию, с которой он был вытеснен, и при следующем добавлении в кэш этого элемента сразу ставить его на позицию с учётом его "прошлых заслуг". Для этого по аналогии с 2Q алгоритмом заводится FIFO кэш, который хранит ключ элемента и позицию, с которой элемент был вытеснен. Если новый добавляемый элемент находится в этом FIFO кэше, он сразу добавляется в позицию, с который был вытеснен в прошлом.

Алгоритм обладает также свойсвами LFU. Чтобы решить проблему элементов, которые часто запрашивались в прошлом, а сейчас просто занимают место, каждый элемент хранит время, когда к нему было обращение. Далее в какие-то моменты времени проверяются элементы на LRU позиции всех сегментов, и если к этим элементам давно не было оращения, они перемещаются в сегмент нижнего уровня, либо удаляются из кэша если находятся на нулевом сегменте.

Оригинальная статья с описанием, реализация.

Графики:

В легенде алгоритмы отсортированы от лучшего к худшему.
MQ* - MQ алгоритм, в котором не выполняется проверка времени жизни объекта в кэше.
На графике видно, что все существующие алгоритмы можно ещё оптимизировать, т.к. до теоретически оптимального есть ещё около 10%.