Кэш - это временное хранилище для данных, которые с наибольшей вероятностью могут быть повторно запрошены. Загрузка данных из кэша осуществляется быстрее, чем из хранилища с исходными данными, но и его объём существенно ограничен.
Алгоритмы кэширования
Алгоритмы кэширования - это подробный список инструкций, который указывает, какие элементы следует отбрасывать в кэш. Их еще называют алгоритмами вытеснения или политиками вытеснения.
Когда кэш заполнен, алгоритм должен выбрать, какую именно запись следует из него удалить, чтобы записать новую, более актуальную информацию.
Least recently used - LRU (Вытеснение давно неиспользуемых)
LRU - это алгоритм, при котором вытесняются элементы, которые дольше всего не запрашивались. Соответственно, необходимо хранить время последнего запроса к элементу. И как только кэш становится заполненным, необходимо вытеснить из него элемент, который дольше всего не запрашивался.
Общая реализация этого алгоритма требует сохранения «бита возраста» для элемента и за счет этого происходит отслеживание наименее используемых элементов. В подобной реализации, при каждом обращении к элементу меняется его «возраст».
LRU на самом деле является семейством алгоритмов кэширования, в которое входит 2Q, а также LRU/K.
Для реализации понадобятся две структуры данных:
- Хеш-таблица, которая будет хранить закэшированные значения.
- Очередь, которая будет хранить приоритеты элементов и выполнять следующие операции:
- Добавить пару значение и приоритет.
- Извлечь (удалить и вернуть) значение с наименьшим приоритетом.
Пошаговый алгоритм:
- Проверяем, есть ли значение в кэше:
- Если значение уже есть, то обновляем время последнего к нему запроса и возвращаем значение.
- Если значения нет в кэше - вычисляем его.
- Проверяем размер кэша:
- Если кэш заполнен, то вытесняем самый старый элемент.
- Добавляем значение в хеш-таблицу и в очередь.
Достоинства:
- константное время выполнения и использование памяти.
Недостатки:
- алгоритм не учитывает ситуации, когда к определенным элементам обращаются часто, но с периодом, превышающим размер кэша (т.е. элемент успевает покинуть кэш).
Псевдо-LRU - PLRU
PLRU - это алгоритм, который улучшает производительность LRU тем, что использует приблизительный возраст, вместо поддержания точного возраста каждого элемента.
Most Recently Used - MRU (Наиболее недавно использовавшийся)
MRU - алгоритм, который удаляет самые последние использованные элементы в первую очередь. Он наиболее полезен в случаях, когда чем старше элемент, тем больше обращений к нему происходит.
Least-Frequently Used - LFU (Наименее часто используемый)
LFU - алгоритм, который подсчитывает частоту использования каждого элемента и удаляет те, к которым обращаются реже всего.
В LFU каждому элементу присваивается counter - счётчик. При повторном обращении к элементу его счётчик увеличивается на единицу. Таким образом, когда кэш заполняется, необходимо найти элемент с наименьшим счётчиком и заменить его новым элементом. Если же все элементы в кэше имеют одинаковый счётчик, то в этом случае вытеснение осуществляется по методу FIFO: первым вошёл - первым вышел.
Недостатки:
- много обращений к элементу за короткое время накручивает счётчик и в результате элемент зависает в кэше.
- алгоритм не учитывает “возраст” элементов.
Multi queue - MQ (Алгоритм многопоточного кэширования)
MQ - алгоритм, использующий несколько LRU очередей - Q0, Q1, …, Qn, между которыми элементы ранжируются/перемещаются в зависимости от частоты обращения к ним.
В дополнение к очередям используется буфер “истории” - Qout, где хранятся все идентификаторы элементов со счётчиками (частота обращения к элементу). При заполнении Qout удаляется самый старый элемент.
Элементы остаются в LRU очередях в течение заданного времени жизни, которое динамически определяется специальным алгоритмом.
Если к очереди не ссылались в течение её времени жизни, то её приоритет понижается с Qi до Qi-1 или удаляется из кэша, если приоритет равен 0 - Q0.
Каждая очередь также имеет максимальное количество обращений к её элементам. Поэтому если к элементу в очереди Qi обращаются более 2i раз, то этот элемент перемещается в очередь Qi+1.
При заполнении кэша, будет вытеснен элемент из очереди Q0, который дольше всех не использовался.
Картинка для наглядности:
Другие алгоритмы
Алгоритмов кэширования достаточно много, поэтому на данный момент не все здесь рассмотрены. С полным списком можно ознакомиться здесь.
Со временем буду дополнять.
Полезные ссылки
Алгоритмы кэширования - статья на wiki.
LRU (Least Recently Used) - подробная статья о LRU с примерами реализации на C, C++, Java.
LRU, метод вытеснения из кэша - статья о том, как быстро реализовать алгоритм LRU.
Least Frequently Used (LFU) Cache Implementation - статья о LFU с примером на C++.
LFU cache in O(1) in Java - пример реализации LFU на Java.
Алгоритмы кэширования - что-то вроде презентации некоторых алгоритмов кэширования в формате PDF.