В вычислительной технике политики замены кэша (также известные как алгоритмы замены кэша или алгоритмы кэширования ) оптимизируют инструкции или алгоритмы , которые компьютерная программа или поддерживаемая оборудованием структура могут использовать для управления кэшем информации. Кэширование повышает производительность, сохраняя недавние или часто используемые элементы данных в областях памяти, которые быстрее или вычислительно дешевле для доступа, чем обычные хранилища памяти. Когда кэш заполнен, алгоритм должен выбрать, какие элементы отбросить, чтобы освободить место для новых данных.
Среднее время обращения к памяти составляет [1]
где
Кэш имеет два основных показателя качества: задержка и коэффициент попадания. Ряд вторичных факторов также влияют на производительность кэша. [1]
Коэффициент попадания кэша описывает, как часто находится искомый элемент. Более эффективные политики замены отслеживают больше информации об использовании, чтобы улучшить частоту попаданий для заданного размера кэша. Задержка кэша описывает, как долго после запроса нужного элемента кэш может вернуть этот элемент при наличии попадания. Более быстрые стратегии замены обычно отслеживают меньше информации об использовании — или, в случае кэша с прямым отображением, никакой информации — чтобы сократить время, необходимое для обновления информации. Каждая стратегия замены является компромиссом между частотой попаданий и задержкой.
Измерения коэффициента попаданий обычно выполняются на эталонных приложениях, и коэффициент попаданий варьируется в зависимости от приложения. Приложения потокового видео и аудио часто имеют коэффициент попаданий, близкий к нулю, поскольку каждый бит данных в потоке считывается один раз (обязательный промах), используется и затем никогда не считывается и не записывается снова. Многие алгоритмы кэширования (особенно LRU ) позволяют потоковым данным заполнять кэш, выталкивая информацию, которая вскоре будет использована снова ( загрязнение кэша ). [2] Другими факторами могут быть размер, продолжительность времени получения и истечение срока действия. В зависимости от размера кэша может не потребоваться дополнительный алгоритм кэширования для удаления элементов. Алгоритмы также поддерживают согласованность кэша , когда несколько кэшей используются для одних и тех же данных, например, несколько серверов баз данных обновляют общий файл данных.
Наиболее эффективным алгоритмом кэширования было бы отбрасывание информации, которая не понадобится в течение длительного времени; это известно как оптимальный алгоритм Белади , оптимальная политика замены или алгоритм ясновидящего . Поскольку, как правило, невозможно предсказать, насколько далеко в будущем понадобится информация, на практике это неосуществимо. Практический минимум можно рассчитать после эксперимента, а эффективность выбранного алгоритма кэширования можно сравнить.
При возникновении ошибки страницы набор страниц находится в памяти. В этом примере последовательность 5, 0, 1 доступна для кадров 1, 2 и 3 соответственно. При доступе к 2 она заменяет значение 5 (которое находится в кадре 1, предсказывая, что значение 5 не будет доступно в ближайшем будущем. Поскольку операционная система общего назначения не может предсказать, когда будет доступно значение 5, алгоритм Белади не может быть реализован там.
Случайная замена выбирает элемент и отбрасывает его, чтобы освободить место, когда это необходимо. Этот алгоритм не требует сохранения истории доступа. Он использовался в процессорах ARM из-за своей простоты, [3] и позволяет эффективное стохастическое моделирование. [4]
При использовании этого алгоритма кэш ведет себя как очередь FIFO : он удаляет блоки в том порядке, в котором они были добавлены, независимо от того, как часто или сколько раз к ним обращались ранее.
Кэш ведет себя как стек , и в отличие от очереди FIFO. Кэш вытесняет блок, добавленный последним, первым, независимо от того, как часто или сколько раз к нему обращались ранее.
SIEVE — это простой алгоритм вытеснения, разработанный специально для веб-кэшей, таких как кэши типа «ключ-значение» и сети доставки контента. Он использует идею ленивого продвижения и быстрого понижения. [5] Поэтому SIEVE не обновляет глобальную структуру данных при попадании в кэш и откладывает обновление до времени вытеснения; в то же время он быстро вытесняет вновь вставленные объекты, поскольку рабочие нагрузки кэша, как правило, демонстрируют высокие коэффициенты «один удар — чудо», и большинство новых объектов не стоит хранить в кэше. SIEVE использует одну очередь FIFO и использует движущуюся руку для выбора объектов для вытеснения. Объекты в кэше имеют один бит метаданных, указывающих, был ли объект запрошен после поступления в кэш. Рука вытеснения указывает на конец очереди в начале и со временем перемещается к голове. По сравнению с алгоритмом вытеснения CLOCK, сохраненные объекты в SIEVE остаются в старой позиции. Поэтому новые объекты всегда находятся в начале, а старые объекты всегда находятся в конце. По мере того, как рука движется к голове, новые объекты быстро вытесняются (быстрое понижение), что является ключом к высокой эффективности алгоритма вытеснения SIEVE. SIEVE проще, чем LRU, но достигает удивительно меньших коэффициентов промахов, чем LRU, наравне с современными алгоритмами вытеснения. Более того, на стационарных перекошенных рабочих нагрузках SIEVE лучше, чем существующие известные алгоритмы, включая LFU. [6]
Сначала удаляет наименее недавно использованные элементы. Этот алгоритм требует отслеживания того, что и когда использовалось, что обременительно. Он требует «битов возраста» для строк кэша и отслеживает наименее недавно использованную строку кэша на основе этих битов возраста. Когда используется строка кэша, возраст других строк кэша изменяется. LRU — это семейство алгоритмов кэширования , которое включает 2Q Теодора Джонсона и Денниса Шаши [7] и LRU/K Пэта О'Нила, Бетти О'Нил и Герхарда Вайкума. [8] Последовательность доступа для примера — ABCDEDF:
Когда ABCD устанавливается в блоки с порядковыми номерами (увеличение на 1 для каждого нового доступа) и осуществляется доступ к E, это промах и его необходимо установить в блок. С алгоритмом LRU E заменит A, поскольку A имеет самый низкий ранг (A(0)). На предпоследнем шаге осуществляется доступ к D, и порядковый номер обновляется. Затем осуществляется доступ к F, заменяя B, который имел самый низкий ранг (B(1)).
Time-aware, least-recently-used (TLRU) [9] — это вариант LRU, разработанный для случаев, когда содержимое кэша имеет допустимый срок службы. Алгоритм подходит для приложений сетевого кэша, таких как информационно-ориентированные сети (ICN), сети доставки контента (CDN) и распределенные сети в целом. TLRU вводит термин: TTU (время использования), временная метка контента (или страницы), которая определяет время использования контента на основе его местоположения и издателя контента. TTU предоставляет локальному администратору больше контроля при регулировании сетевого хранилища.
Когда поступает контент, подлежащий TLRU, узел кэша вычисляет локальное значение TTU на основе TTU, назначенного издателем контента. Локальное значение TTU вычисляется с помощью локально определенной функции. Когда вычисляется локальное значение TTU, замена контента выполняется на подмножестве общего контента узла кэша. TLRU гарантирует, что менее популярный и недолговечный контент заменяется входящим контентом.
В отличие от LRU, MRU сначала отбрасывает самые последние использованные элементы. На 11-й конференции VLDB Чжоу и Девитт сказали: «Когда файл многократно сканируется в [циклическом последовательном] эталонном шаблоне, MRU является лучшим алгоритмом замены ». [10] Исследователи, выступавшие на 22-й конференции VLDB, отметили, что для шаблонов случайного доступа и повторных сканирований больших наборов данных (также известных как шаблоны циклического доступа) алгоритмы кэширования MRU имеют больше попаданий, чем LRU, из-за их тенденции сохранять более старые данные. [11] Алгоритмы MRU наиболее полезны в ситуациях, когда чем старше элемент, тем больше вероятность доступа к нему. Последовательность доступа для примера — ABCDECDB:
ABCD помещаются в кэш, так как есть свободное место. При пятом доступе (E) блок, содержащий D, заменяется на E, так как этот блок использовался последним. При следующем доступе (к D) заменяется C, так как это был блок, к которому обращались непосредственно перед D.
Кэш SLRU делится на два сегмента: испытательный и защищенный. Строки в каждом сегменте упорядочены от наиболее часто используемых к наименее часто используемым. Данные из промахов добавляются в кэш в конце испытательного сегмента, к которому чаще всего обращались. Попадания удаляются из того места, где они находятся, и добавляются в конец защищенного сегмента, к которому чаще всего обращались; строки в защищенном сегменте были доступны по крайней мере дважды. Защищенный сегмент конечен; миграция строки из испытательного сегмента в защищенный сегмент может вызвать миграцию строки LRU в защищенном сегменте в конец испытательного сегмента, к которому чаще всего обращались, что дает этой строке еще один шанс на доступ перед заменой. Ограничение размера защищенного сегмента — это параметр SLRU, который изменяется в зависимости от шаблонов рабочей нагрузки ввода-вывода . Когда данные должны быть удалены из кэша, строки берутся из конца LRU испытательного сегмента. [12]
LRU может быть дорогим в кэшах с более высокой ассоциативностью . Практическое оборудование обычно использует приближение для достижения аналогичной производительности при более низкой стоимости оборудования.
Для кэшей ЦП с большой ассоциативностью (обычно > четырех путей) стоимость реализации LRU становится непомерной. Во многих кэшах ЦП достаточно алгоритма, который почти всегда отбрасывает один из наименее недавно использованных элементов; многие разработчики ЦП выбирают алгоритм PLRU, которому для работы требуется только один бит на элемент кэша. PLRU обычно имеет немного худший коэффициент промахов, немного лучшую задержку , потребляет немного меньше энергии, чем LRU, и имеет меньшие накладные расходы, чем LRU.
Биты работают как двоичное дерево однобитовых указателей, которые указывают на менее недавно использованное поддерево. Следование цепочке указателей к листовому узлу определяет кандидата на замену. При доступе все указатели в цепочке от листового узла пути, к которому осуществляется доступ, до корневого узла устанавливаются так, чтобы указывать на поддерево, которое не содержит путь, к которому осуществляется доступ. Последовательность доступа в примере — ABCDE:
Если есть доступ к значению (например, A), а его нет в кэше, оно загружается из памяти и помещается в блок, на который указывают стрелки в примере. После размещения этого блока стрелки переворачиваются, чтобы указывать в противоположном направлении. Размещаются A, B, C и D; E заменяет A по мере заполнения кэша, потому что именно туда указывали стрелки, а стрелки, которые вели к A, переворачиваются, чтобы указывать в противоположном направлении (на B, блок, который будет заменен при следующем промахе кэша).
Алгоритм LRU не может быть реализован на критическом пути компьютерных систем, таких как операционные системы , из-за его высоких накладных расходов; вместо него обычно используется Clock , приближение LRU. Clock-Pro является приближением LIRS для недорогой реализации в системах. [13] Clock-Pro имеет базовую структуру Clock с тремя преимуществами. Он имеет три «стрелки часов» (в отличие от одной «стрелки» Clock) и может приблизительно измерять расстояние повторного использования доступа к данным. Как и LIRS, он может быстро вытеснять элементы данных с однократным доступом или низкой локальностью . Clock-Pro такой же сложный, как Clock, и его легко реализовать при низких затратах. Реализация замены буферного кэша в версии Linux 2017 года объединяет LRU и Clock-Pro. [14] [15]
Алгоритм LFU подсчитывает, как часто требуется элемент; те, которые используются реже, отбрасываются в первую очередь. Это похоже на LRU, за исключением того, что сохраняется, сколько раз блок был доступен, а не как давно. При выполнении последовательности доступа блок, который использовался меньше всего раз, будет удален из кэша.
Алгоритм наименее частого недавно использованного (LFRU) [16] сочетает в себе преимущества LFU и LRU. LFRU подходит для приложений сетевого кэша, таких как ICN , CDN и распределенных сетей в целом. В LFRU кэш делится на два раздела: привилегированный и непривилегированный. Привилегированный раздел защищен, и если контент популярен, он помещается в привилегированный раздел. При замене привилегированного раздела LFRU вытесняет контент из непривилегированного раздела; помещает контент из привилегированного в непривилегированный раздел и вставляет новый контент в привилегированный раздел. LRU используется для привилегированного раздела, а приближенный алгоритм LFU (ALFU) — для непривилегированного раздела.
Вариант, LFU с динамическим старением (LFUDA), использует динамическое старение для учета сдвигов в наборе популярных объектов; он добавляет фактор возраста кэша к счетчику ссылок, когда новый объект добавляется в кэш или существующий объект повторно ссылается. LFUDA увеличивает возраст кэша при вытеснении блоков, устанавливая его равным значению ключа вытесненного объекта, и возраст кэша всегда меньше или равен минимальному значению ключа в кэше. [17] Если объект часто использовался в прошлом и стал непопулярным, он останется в кэше в течение длительного времени (предотвращая его замену новыми или менее популярными объектами). Динамическое старение уменьшает количество таких объектов, делая их пригодными для замены, а LFUDA уменьшает загрязнение кэша, вызванное LFU, когда кэш небольшой.
Это новый алгоритм вытеснения, разработанный в 2023 году. По сравнению с существующими алгоритмами, которые в основном основаны на LRU (least-recently-used), S3-FIFO использует только три очереди FIFO: малую очередь, занимающую 10% пространства кэша, основную очередь, которая использует 90% пространства кэша, и очередь призраков, которая хранит только метаданные объектов. Малая очередь используется для фильтрации one-hit-wonders (объектов, к которым обращаются только один раз за короткий промежуток времени); основная очередь используется для хранения популярных объектов и использует повторную вставку для их удержания в кэше; а очередь призраков используется для перехвата потенциально популярных объектов, которые вытесняются из малой очереди. Объекты сначала вставляются в малую очередь (если они не найдены в очереди призраков, в противном случае вставляются в основную очередь); при вытеснении из малой очереди, если объект был запрошен, он повторно вставляется в основную очередь, в противном случае он вытесняется, и метаданные отслеживаются в очереди призраков. [18]
S3-FIFO демонстрирует, что очереди FIFO достаточны для разработки эффективных и масштабируемых алгоритмов вытеснения. По сравнению с LRU и алгоритмами на основе LRU, S3-FIFO может достичь в 6 раз большей пропускной способности. Кроме того, при рабочих нагрузках веб-кэша S3-FIFO достигает самого низкого коэффициента промахов среди 11 современных алгоритмов, с которыми сравнивали авторы. [19]
Политики в стиле RRIP являются основой для других политик замены кэша, включая Hawkeye. [20]
RRIP [21] — это гибкая политика, предложенная Intel , которая пытается обеспечить хорошую устойчивость к сканированию, позволяя при этом вытеснять старые строки кэша, которые не использовались повторно. Все строки кэша имеют прогнозируемое значение RRPV (прогнозируемое значение повторной ссылки), которое должно коррелировать с тем, когда ожидается повторное использование строки. RRPV обычно высок при вставке; если строка не будет повторно использована в ближайшее время, она будет вытеснена, чтобы предотвратить заполнение кэша сканированиями (большие объемы данных, используемые только один раз). Когда строка кэша используется повторно, RRPV устанавливается в ноль, указывая, что строка была повторно использована один раз и, вероятно, будет повторно использована снова.
При промахе кэша строка с RRPV, равным максимально возможному RRPV, вытесняется; при 3-битных значениях вытесняется строка с RRPV 2 3 - 1 = 7. Если ни одна строка не имеет этого значения, все RRPV в наборе увеличиваются на 1, пока одна из них не достигнет его. Необходим решающий фактор, и обычно это первая строка слева. Увеличение необходимо для того, чтобы гарантировать, что старые строки будут должным образом устаревать и будут вытеснены, если они не будут повторно использоваться.
SRRIP вставляет строки со значением RRPV maxRRPV; строка, которая только что была вставлена, с наибольшей вероятностью будет удалена при промахе кэша.
SRRIP обычно работает хорошо, но страдает, когда рабочий набор намного больше размера кэша, и вызывает пробуксовку кэша . Это исправляется вставкой строк со значением RRPV maxRRPV большую часть времени и вставкой строк со значением RRPV maxRRPV - 1 случайным образом с низкой вероятностью. Это приводит к тому, что некоторые строки «застревают» в кэше, и помогает предотвратить пробуксовку. Однако BRRIP ухудшает производительность при доступе без пробуксовки. SRRIP работает лучше всего, когда рабочий набор меньше кэша, а BRRIP работает лучше всего, когда рабочий набор больше кэша.
DRRIP [21] использует дуэль наборов [22] для выбора, использовать ли SRRIP или BRRIP. Он выделяет несколько наборов (обычно 32) для использования SRRIP и еще несколько для использования BRRIP, а также использует счетчик политик, который отслеживает производительность наборов, чтобы определить, какая политика будет использоваться остальной частью кэша.
Алгоритм Белади — это оптимальная политика замены кэша, но она требует знания будущего, чтобы вытеснять строки, которые будут повторно использоваться дальше всего в будущем. Было предложено несколько политик замены, которые пытаются предсказать будущие расстояния повторного использования из прошлых моделей доступа, [23] что позволяет им аппроксимировать оптимальную политику замены. Некоторые из наиболее эффективных политик замены кэша пытаются имитировать алгоритм Белади.
Hawkeye [20] пытается эмулировать алгоритм Белади, используя прошлые доступы ПК, чтобы предсказать, генерируют ли производимые им доступы дружественные к кэшу (используемые позже) или недружественные к кэшу доступы (не используемые позже). Он выбирает несколько невыровненных наборов кэша, использует историю длины и эмулирует алгоритм Белади для этих доступов. Это позволяет политике определять, какие строки должны были быть кэшированы, а какие нет, предсказывая, является ли инструкция дружественной к кэшу или недружественной к кэшу. Затем эти данные подаются в RRIP; доступы из дружественных к кэшу инструкций имеют более низкое значение RRPV (вероятно, будут вытеснены позже), а доступы из недружественных к кэшу инструкций имеют более высокое значение RRPV (вероятно, будут вытеснены раньше). Решения о вытеснении принимает бэкэнд RRIP. Генератор выборочного кэша и OPT устанавливает начальное значение RRPV вставленных строк кэша. Hawkeye выиграл чемпионат по кэшированию CRC2 в 2017 году [24] , а Harmony [25] является расширением Hawkeye, которое повышает производительность предварительной выборки.
Mockingjay [26] пытается улучшить Hawkeye несколькими способами. Он отказывается от двоичного предсказания, что позволяет ему принимать более детальные решения о том, какие строки кэша следует вытеснять, и оставляет решение о том, какие строки кэша следует вытеснять, на тот случай, когда будет доступно больше информации.
Mockingjay хранит кэш выборки уникальных доступов, ПК, которые их произвели, и их временные метки. Когда к строке в кэше выборки снова обращаются, разница во времени будет отправлена в предиктор расстояния повторного использования. RDP использует обучение на основе временной разницы, [27] где новое значение RDP будет увеличено или уменьшено на небольшое число для компенсации выбросов; число вычисляется как . Если значение не было инициализировано, наблюдаемое расстояние повторного использования вставляется напрямую. Если кэш выборки заполнен и строку необходимо отбросить, RDP получает указание, что ПК, который последним обращался к нему, производит потоковые доступы.
При доступе или вставке предполагаемое время повторного использования (ETR) для этой строки обновляется, чтобы отразить прогнозируемое расстояние повторного использования. При промахе кэша строка с наибольшим значением ETR вытесняется. Mockingjay имеет результаты, близкие к оптимальному алгоритму Белади.
В ряде политик были предприняты попытки использовать персептроны , цепи Маркова или другие типы машинного обучения для прогнозирования того, какую строку следует исключить. [28] [29] Алгоритмы дополненного обучения также существуют для замены кэша. [30] [31]
LIRS — это алгоритм замены страниц с лучшей производительностью, чем LRU и другие, более новые алгоритмы замены. Расстояние повторного использования — это метрика для динамического ранжирования запрашиваемых страниц для принятия решения о замене. [32] LIRS устраняет ограничения LRU, используя новизну для оценки межссылочной новизны (IRR) для принятия решения о замене.
На диаграмме X указывает, что к блоку обращаются в определенное время. Если к блоку A1 обращаются в момент времени 1, его новизна будет равна 0; это первый доступный блок, а IRR будет равен 1, поскольку он предсказывает, что к A1 снова будут обращаться в момент времени 3. В момент времени 2, поскольку обращаются к A4, новизна станет равной 0 для A4 и 1 для A1; A4 является последним доступным объектом, а IRR станет равным 4. В момент времени 10 алгоритм LIRS будет иметь два набора: набор LIR = {A1, A2} и набор HIR = {A3, A4, A5}. В момент времени 10, если есть доступ к A4, происходит пропуск; LIRS вытеснит A5 вместо A2 из-за его большей новизны.
Адаптивный замещающий кэш (ARC) постоянно балансирует между LRU и LFU для улучшения объединенного результата. [33] Он улучшает SLRU, используя информацию о недавно удаленных элементах кэша для регулировки размера защищенных и испытательных сегментов, чтобы наилучшим образом использовать доступное пространство кэша. [34]
Часы с адаптивной заменой (CAR) объединяют преимущества ARC и Clock . CAR работает сопоставимо с ARC и превосходит LRU и Clock. Как и ARC, CAR является самонастраивающимся и не требует никаких параметров, указанных пользователем.
Алгоритм замены нескольких очередей (MQ) был разработан для повышения производительности кэша буфера второго уровня, такого как кэш буфера сервера, и был представлен в статье Чжоу, Филбина и Ли. [35] Кэш MQ содержит m очередей LRU: Q 0 , Q 1 , ..., Q m -1 . Значение m представляет иерархию, основанную на времени жизни всех блоков в этой очереди. [36]
Pannier [37] — это механизм флэш-кэширования на основе контейнеров, который идентифицирует контейнеры, блоки которых имеют переменные шаблоны доступа. Pannier имеет структуру очереди выживания на основе приоритетов для ранжирования контейнеров на основе их времени выживания, которое пропорционально живым данным в контейнере.
Статический анализ определяет, какие обращения являются попаданиями или промахами в кэш, чтобы указать наихудшее время выполнения программы. [38] Подход к анализу свойств кэшей LRU заключается в том, чтобы дать каждому блоку в кэше «возраст» (0 для последнего использованного) и вычислить интервалы для возможных возрастов. [39] Этот анализ можно усовершенствовать, чтобы различать случаи, когда одна и та же точка программы доступна по путям, которые приводят к промахам или попаданиям. [40] Эффективный анализ может быть получен путем абстрагирования наборов состояний кэша с помощью антицепей , которые представлены компактными бинарными диаграммами решений . [41]
Статический анализ LRU не распространяется на псевдо-LRU политики. Согласно теории вычислительной сложности , проблемы статического анализа, поставленные псевдо-LRU и FIFO, находятся в более высоких классах сложности, чем для LRU. [42] [43]
