Алгоритм кэширования - это алгоритм, используемый для управления кэшем или группой данных. Когда кэш заполнен, он решает, какой элемент следует удалить из кэша. Слово хиты описывает, как часто запрос может быть обработан из кэша. Термин задержка описывает, как долго может быть получен кэшируемый элемент. Алоритмия в кэше - это компромисс между хит-рейтом и латентностью.
- Наиболее эффективным алгоритмом кэширования будет всегда отбрасывать информацию, которая не будет нужна долгое время в будущем. Этот оптимальный результат называется оптимальным алгоритмом Belady или ясновидящим алгоритмом. Поскольку, как правило, невозможно предсказать, насколько далеко в будущем будет требоваться информация, то на практике это, как правило, не реализуемо. Практический минимум можно рассчитать только после экспериментов, а эффективность фактически выбранного алгоритма кэширования можно сравнить с оптимальным минимумом.
- Least Recent Recent Used (LRU): сначала удаляет наименее используемые элементы. Этот алгоритм требует отслеживания того, что было использовано, когда. Это дорого, если хочется убедиться, что алгоритм всегда отбрасывает наименее последний использованный элемент. Общая реализация этой техники требует сохранения "возрастных битов" для строк кэша и отслеживания "наименее свежеиспользованной" кэш-линии на основе возрастных битов. В такой реализации каждый раз при использовании кэш-линии меняется возраст всех остальных строк кэша. LRU на самом деле является семейством алгоритмов кэширования с включением членов: 2Q от Теодора Джонсона и Денниса Шаши и LRU/K от Пата О'Нила, Бетти О'Нила и Герхарда Вайкума.
- Последнее использование (MRU): Этот алгоритм сначала удаляет самые последние использованные элементы. Этот механизм кэширования обычно используется для кэширования памяти базы данных.
- Псевдо-РЛРУ (PLRU): Есть определенные случаи, когда LRU очень сложно реализовать. В таких случаях может быть достаточно знать, что в большинстве случаев удаляется один из наименее часто используемых элементов. Там можно использовать алгоритм PLRU, так как для его работы требуется всего один бит на каждый элемент кэша.
- 2-позиционный набор ассоциативный: для высокоскоростных кэшей процессора, где даже PLRU слишком медленный. Адрес нового элемента используется для вычисления одного из двух возможных мест в кэше, куда он разрешен. LRU этих двух элементов отбрасывается. Для этого требуется один бит на пару строк кэша, чтобы указать, какая из двух строк использовалась меньше всего в последнее время.
- Кэш с прямым отображением: для высокоскоростных процессорных кэшей, где даже 2-полосные ассоциативные кэши слишком медленные. Адрес нового элемента используется для вычисления одного места в кэше, куда он разрешен. Что бы там ни было раньше, оно отбрасывается.
- Наименее часто используемый (LFU): LFU подсчитывает, как часто необходим элемент. Те, которые используются реже всего, сначала выбрасываются.
- Адаптивный кэш замены (ARC): постоянный баланс между LRU и LFU для улучшения комбинированного результата.
- Алгоритм кэширования Multi Queue (MQ): (И. Чжоу Дж.Ф. Филбин и Кай Ли).
Другие вещи для рассмотрения:
- Товары с разной стоимостью: храните предметы, которые дорого стоят, например, те, которые требуют много времени.
- Предметы занимают больше кэша: Если элементы имеют разные размеры, кэш может захотеть отбросить большой элемент для хранения нескольких меньших.
- Предметы, срок годности которых истекает со временем: Некоторые кэши хранят информацию, срок действия которой истекает (например, кэш новостей, кэш DNS или кэш веб-браузера). Компьютер может отбрасывать предметы по причине их истечения. В зависимости от размера кэша может не потребоваться дополнительный алгоритм кэширования для отбрасывания элементов.
Также существуют различные алгоритмы для поддержания когерентности кэша. Это относится только к ситуации, когда несколько независимых кэшей используются для одних и тех же данных (например, несколько серверов баз данных обновляют один общий файл данных).
