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

В информатике под алгоритмами кэширования (часто называемыми алгоритмами вытеснения или политиками вытеснения, а также «алгоритмами/политиками замещения») понимают оптимизацию инструкций — алгоритмы — особая компьютерная программа или аппаратно поддерживаемая структура, способная управлять кэшем информации, хранимой в компьютере. Когда кэш заполнен, алгоритм должен выбрать, что именно нужно удалить из него, чтобы иметь возможность записи (в кэш) новой, более актуальной информации.

«Уровень попаданий» кэша означает то, насколько часто искомые данные обнаруживаются в кэше. Более эффективные политики вытеснения отслеживают обращения к наиболее используемой информации, чтобы улучшить уровень попаданий (при том же размере кэша).

«Латентность» кэша означает, насколько быстро кэш может вернуть запрошенные данные непосредственно после запроса (в случае, если происходит «попадание»). Более быстрые стратегии вытеснения обычно отслеживают наименее используемую информацию — или, в случае кэша прямого отображения (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 два элемента вытесняются. Это требует одного бита для пары строк кэша ^{[источник не указан 1113 дней]} для указания которые из них использовались последними.

Кэш прямого отображения (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-кэш или кэш веб-браузера). Компьютер может вытеснить элементы вследствие их устаревания. В зависимости от размера кэша, кэширование новых элементов может потребовать вытеснение старых.

Существуют также различные алгоритмы для обеспечения когерентности кэша. Это применяется в случаях только когда множество независимых кэшей используется для хранения одной и той же информации (например, множество серверов баз данных обновляют общий файл данных).

См. также

• Кэш
• Нетребовательный к кэшу алгоритм
• Кэш процессора
• Алгоритм вытеснения страниц
• Компактность ссылок

Ссылки

1. ↑ Hong-Tai Chou". David J. Dewitt: http://www.vldb.org/conf/1985/P127.PDF
2. ↑ Semantic Data Caching and Replacement: http://www.vldb.org/conf/1996/P330.PDF
3. ↑ Ramakrishna Karedla, J. Spencer Love, and Bradley G. Wherry. Caching Strategies to Improve Disk System Performance. In Computer, 1994.
4. ↑ http://www.usenix.org/events/fast03/tech/full_papers/megiddo/megiddo.pdf
5. ↑ Index of /events/usenix01/full_papers/zhou

Дополнительные источники

• Описание различных алгоритмов кэширования
• Полностью ассоциативный кэш
• n-канальная ассоциативность
• Кэш с прямым отображением