алгоритм кэширования
Алгоритм кэширования - это алгоритм, используемый для управления кэшем или группой данных. Когда кэш заполнен, он решает, какой элемент следует удалить из кэша. Слово хиты описывает, как часто запрос может быть обработан из кэша. Термин задержка описывает, как долго может быть получен кэшируемый элемент. Алоритмия в кэше - это компромисс между хит-рейтом и латентностью.
- Наиболее эффективным алгоритмом кэширования будет всегда отбрасывать информацию, которая не будет нужна долгое время в будущем. Этот оптимальный результат называется оптимальным алгоритмом 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 или кэш веб-браузера). Компьютер может отбрасывать предметы по причине их истечения. В зависимости от размера кэша может не потребоваться дополнительный алгоритм кэширования для отбрасывания элементов.
Также существуют различные алгоритмы для поддержания когерентности кэша. Это относится только к ситуации, когда несколько независимых кэшей используются для одних и тех же данных (например, несколько серверов баз данных обновляют один общий файл данных).
Какие ячейки памяти можно кэшировать, с помощью каких ячеек кэша
Вопросы и ответы
В: Что такое алгоритм кэширования?
О: Алгоритм кэша - это алгоритм, используемый для управления кэшем или группой данных. Он решает, какой элемент должен быть удален из кэша, когда он заполнен.
В: Что такое частота попаданий?
О: Коэффициент попадания описывает, как часто запрос может быть обслужен из кэша.
В: Что описывает латентность?
О: Латентность описывает, как долго элемент кэша может быть получен.
В: Что такое оптимальный алгоритм Белади?
О: Оптимальный алгоритм Белади, также известный как алгоритм ясновидящего, является эффективным алгоритмом кэширования, который всегда отбрасывает информацию, которая не будет нужна в течение самого длительного времени в будущем. Этот результат, как правило, не может быть реализован на практике, потому что он требует предсказания того, что понадобится далеко в будущем.
В: Как работает принцип Least Recently Used (LRU)?
О: LRU удаляет в первую очередь наименее недавно использованные элементы и требует отслеживания того, что когда использовалось, используя "биты возраста" для каждой кэш-линии и отслеживая, какая из них была использована последней на основании битов возраста. Каждый раз, когда используется кэш-линия, возраст всех остальных кэш-линий изменяется соответствующим образом.
В: Как работает функция Most Recently Used (MRU)?
О: MRU удаляет в первую очередь наиболее недавно использованные элементы, и этот механизм кэширования обычно используется для кэшей памяти баз данных.
В: Какие еще алгоритмы существуют для поддержания когерентности кэша?
О: Существуют различные алгоритмы для поддержания согласованности кэша, когда несколько независимых кэшей используются для общих данных, например, несколько серверов баз данных обновляют один общий файл данных.
