Алгоритмы кэширования
Алгори́тмы кэши́рования (алгоритмы вытеснения, политики вытеснения, а также «алгоритмы/политики замещения») — в информатике это оптимизация инструкций: особая компьютерная программа или аппаратно поддерживаемая структура, способная управлять кэшем информации, хранимой в компьютере. Когда кэш заполнен, алгоритм должен выбрать, что именно нужно удалить из него, чтобы иметь возможность записи (в кэш) новой, более актуальной информации. Аппаратная реализация данных алгоритмов предполагает использование таймера, счётчика или их комбинации.
«Уровень попаданий» в кэш означает то, насколько часто искомые данные обнаруживаются в кэше. Более эффективные политики вытеснения отслеживают обращения к наиболее используемой информации, чтобы улучшить уровень попаданий (при том же размере кэша).
«Латентность» кэша означает, насколько быстро кэш может вернуть запрошенные данные непосредственно после запроса (в случае, если происходит «попадание»). Более быстрые стратегии вытеснения обычно отслеживают наименее используемую информацию — или, в случае кэша прямого отображения (direct-mapped cache), отсутствие информации, чтобы снизить затраты времени на обновление информации.
Каждая стратегия вытеснения является компромиссом между уровнем попаданий и латентностью.
Примеры
Алгоритм Белади
Наиболее эффективное правило вытеснения — отбрасывать из кэша ту информацию, которая не понадобится в будущем дольше всего. Этот оптимальный алгоритм кэширования назвали алгоритмом Белади или алгоритмом предвидения. Так как в общем случае невозможно предсказать, когда именно в следующий раз потребуется именно эта информация, то на практике (опять же, в общем случае) подобная реализация невозможна. Практический минимум может быть вычислен только опытным путём, после чего можно сравнить с ним эффективность текущего алгоритма кэширования.
Least recently used (Вытеснение давно неиспользуемых)
Least recently used (LRU): в первую очередь, вытесняется неиспользованный дольше всех. Этот алгоритм требует отслеживания того, что и когда использовалось, что может оказаться довольно накладно, особенно если нужно проводить дополнительную проверку, чтобы в этом убедиться. Общая реализация этого метода требует сохранения «бита возраста» для строк кэша и за счет этого происходит отслеживание наименее использованных строк (то есть за счет сравнения таких битов). В подобной реализации, при каждом обращении к строке кэша меняется «возраст» всех остальных строк. LRU на самом деле является семейством алгоритмов кэширования, в которое входит 2Q, разработанный Теодором Джонсоном и Деннисом Шаша, а также LRU/K от Пэта О’Нила, Бетти О’Нил и Герхарда Вейкума.
Most Recently Used (Наиболее недавно использовавшийся)
Most Recently Used (MRU): в отличие от LRU, в первую очередь вытесняется последний использованный элемент. В соответствии с источником[1], «Когда файл периодически сканируется по циклической схеме, MRU — наилучший алгоритм вытеснения». В источнике[2] авторы также подчеркивают, что для схем произвольного доступа и циклического сканирования больших наборов данных (иногда называемых схемами циклического доступа) алгоритмы кэширования MRU имеют больше попаданий по сравнению с LRU за счет их стремления к сохранению старых данных. Алгоритмы MRU наиболее полезны в случаях, когда чем старше элемент, тем больше обращений к нему происходит.
Псевдо-LRU
Псевдо-LRU (PLRU): Для кэшей с большой ассоциативностью (обычно более 4 каналов), необходимые ресурсы для реализации LRU становятся слишком большими. Если достаточна политика, что почти всегда нужно отбрасывать наименее используемый элемент, то в этом случае можно использовать алгоритм PLRU, требующий для элемента кэша только один бит.
Сегментированный LRU
Сегментированный LRU (Segmented LRU или SLRU): «SLRU-кэш делится на два сегмента: пробный сегмент и защищенный сегмент. Строки в каждом сегменте упорядочены от часто используемых к наименее используемым. Данные при промахах добавляются в кэш, причем в область последних использованных элементов пробного сегмента. Данные при попаданиях убираются, где бы они не располагались и добавляются в область часто используемых элементов защищенного сегмента. К строкам защищенного сегмента обращения таким образом происходят по крайней мере дважды. Защищенный сегмент ограничен. Такой перенос строки из пробного сегмента в защищенный сегмент может вызвать перенос последней использованной (LRU) строки в защищенном сегменте в MRU-область пробного сегмента, давая этой линии второй шанс быть использованной перед вытеснением. Размер защищенного сегмента — SLRU-параметр, который меняется в зависимости от схемы работы ввода-вывода. Всякий раз когда данные должны быть вытеснены из кэша, строки запрашиваются из LRU-конца пробного сегмента.[3]»
2-Way Set Associative (2-канальная ассоциативность)
2-канальная ассоциативность применяется для высокоскоростного процессорного кэша, где даже PLRU слишком медленный. Адрес нового элемента используется для вычисления одного из двух возможных местонахождений в кэше (в отведенной для этого области). По алгоритму LRU два элемента вытесняются.
Кэш прямого отображения (Direct-mapped cache)
Кэш прямого отображения: для высокоскоростных кэшей процессора, где не хватает быстродействия 2-канального ассоциативного кэширования. Адрес нового элемента используется для вычисления местонахождения в кэше (в отведенной для этого области). Все, что было ранее, — вытесняется.
Least-Frequently Used (Наименее часто используемый)
Least Frequently Used (LFU): LFU подсчитывает как часто используется элемент. Те элементы, обращения к которым происходят реже всего, вытесняются в первую очередь.
Adaptive Replacement Cache (Адаптивная замена)
Adaptive Replacement Cache (ARC):[4] постоянно балансирует между LRU и LFU, что улучшает итоговый результат.
Multi Queue Caching Algorithm (Алгоритм многопоточного кэширования)
Multi Queue (MQ) caching algorithm:[5] (разработанный И. Жу, Дж. Ф. Филбином и Каем Ли).
Учитываются следующие моменты:
- Элементы с различной стоимостью: хранение элементов, запрос которых весьма до́рог, например, такие, получение которых потребует много времени.
- Элементы, требующие больше места в кэше: если элементы имеют разный размер, то контроллер кэша может попытаться вытеснить бо́льший элемент, чтобы сохранить несколько элементов поменьше.
- Элементы, устаревающие с течением времени: Некоторые кэши хранят устаревающую информацию (например, кэш новостей, DNS-кэш или кэш веб-браузера). Компьютер может вытеснить элементы вследствие их устаревания. В зависимости от размера кэша, кэширование новых элементов может потребовать вытеснение старых.
Существуют также различные алгоритмы для обеспечения когерентности кэша. Это применяется в случаях только тогда, когда множество независимых кэшей используется для хранения одной и той же информации (например, множество серверов баз данных обновляют общий файл данных).
См. также
Ссылки
- ↑ Hong-Tai Chou". David J. Dewitt: http://www.vldb.org/conf/1985/P127.PDF Архивная копия от 27 июля 2008 на Wayback Machine
- ↑ Semantic Data Caching and Replacement: http://www.vldb.org/conf/1996/P330.PDF Архивная копия от 16 июня 2011 на Wayback Machine
- ↑ Ramakrishna Karedla, J. Spencer Love, and Bradley G. Wherry. Caching Strategies to Improve Disk System Performance. In Computer, 1994.
- ↑ Архивированная копия. Дата обращения: 1 октября 2009. Архивировано 8 февраля 2010 года.
- ↑ Index of /events/usenix01/full_papers/zhou Архивировано 24 ноября 2005 года.