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

LIRS ( Low Inter-reference Recency Set ) — это алгоритм замены страниц с улучшенной производительностью по сравнению с LRU (наименее недавно использованный) и многими другими новыми алгоритмами замены. ^[1] Это достигается за счет использования «расстояния повторного использования». ^[2] в качестве метрики местоположения для динамического ранжирования страниц, к которым осуществляется доступ, для принятия решения о замене.

Краткое содержание

Количественная оценка местности

Хотя все алгоритмы замены страниц для функционирования полагаются на наличие локальности ссылки , основное различие между различными алгоритмами замены заключается в том, как эта локальность оценивается количественно. LIRS использует расстояние повторного использования страницы или количество отдельных страниц, к которым осуществляется доступ между двумя последовательными ссылками на страницу, для количественной оценки локальности. В частности, для этой цели LIRS использует последние и предпоследние ссылки (если таковые имеются). Если к странице обращаются впервые, расстояние ее повторного использования бесконечно. Напротив, LRU использует новизну страницы, которая представляет собой количество уникальных страниц, к которым осуществляется доступ после ссылки на страницу, для количественной оценки местоположения. Чтобы принять во внимание обновленную историю доступа, реализация LIRS фактически использует большее расстояние повторного использования и новизну страницы в качестве метрики для количественной оценки ее локальности, обозначаемой как RD-R. Предполагая, что кэш имеет емкость страниц C, алгоритм LIRS должен ранжировать недавно использованные страницы в соответствии с их значениями RD-R и сохранять страницы C с наиболее высоким рейтингом в кеше.

Концепции расстояния повторного использования и новизны можно визуализировать следующим образом: T1 и T2 — это предпоследнее и последнее опорное время страницы B соответственно, а T3 — текущее время.

 . . . B . . . B . . . . . . . . . . B . . . . . 
               ^----Reuse Distance---^--Recency--^
               T1                    T2          T3

Выбор жертвы на замену

LIRS организует метаданные кэшированных страниц и некоторых некэшированных страниц и выполняет операции их замены, описанные ниже, которые также проиллюстрированы примером. ^[3] в графике.

Кэш разделен на разделы с низкой частотой межссылок (LIR) и с высокой частотой межссылок (HIR). Раздел LIR предназначен для хранения страниц с наиболее высоким рейтингом (страницы LIR), а раздел HIR предназначен для хранения некоторых других страниц (страницы HIR).
Раздел LIR содержит большую часть кеша, и все страницы LIR находятся в кеше.
Все недавно использованные страницы помещаются в очередь FIFO, называемую стеком LIRS (стек S на графике), а все резидентные страницы HIR также помещаются в другую очередь FIFO (стек Q на графике).
Страница, к которой осуществляется доступ, перемещается наверх стека S , а все страницы HIR внизу стека удаляются. Например, график (b) создается после странице B на графике (a). доступа к
Когда осуществляется доступ к странице HIR в стеке S , она превращается в страницу LIR, и, соответственно, страница LIR, находящаяся в настоящее время внизу стека S, превращается в страницу HIR и перемещается на вершину стека Q. Например, график (c) создается после страница E доступна на графике (a).
Когда происходит промах и необходимо заменить резидентную страницу, резидентная страница HIR в нижней части стека Q выбирается в качестве жертвы для замены. Например, графики (d) и (e) создаются после доступа к страницам D и C на графике (a) соответственно.

Развертывание

LIRS развернут в MySQL начиная с версии 5.1. ^[4] и еще ссылка по ссылке . Он также используется в Infinispan . платформе сетки данных ^[5] Аппроксимация LIRS, CLOCK-Pro, ^[6] принят в NetBSD . ^[7] LIRS принят в Apache Jackrabbit , репозитории контента. Кэш LIRS в памяти разработан в системе виртуализации данных Red Hat JBoss . LIRS используется в ядре базы данных H2, которое называется кэшем, устойчивым к сканированию . Кроме того, LIRS используется в Apache Impala , системе обработки данных с помощью Hadoop.

См. также

Алгоритм замены страниц

Ссылки

^ Цзян, Сун; Чжан, Сяодун (июнь 2002 г.). «LIRS: эффективная политика замены набора с низкой периодичностью между ссылками для повышения производительности буферного кэша». Обзор оценки производительности ACM SIGMETRICS . 30 (1): 31–42. дои : 10.1145/511399.511340 .
^ Мэттсон, РЛ; Гечеи, Дж.; Слуц, ДР; Трейгер, Иллинойс (1970). «Методы оценки иерархий хранения» . IBM Systems Journal . 9 (2): 78–117. дои : 10.1147/sj.92.0078 .
^ Сун Цзян; Сяодун Чжан (2005). «Как сделать LRU дружественным к слабым локальным рабочим нагрузкам: новый алгоритм замены для улучшения производительности буферного кэша» . Транзакции IEEE на компьютерах . 54 (8): 939–952. дои : 10.1109/TC.2005.130 . S2CID 11539061 .
^ svn commit — mysqldoc@docsrva: r6768 — магистраль/ndbapi
^ Выселение Infinispan, пакетное обновление и LIRS
^ Сун Цзян, Фэн Чен и Сяодун Чжан, « CLOCK-Pro: эффективное улучшение замены часов », в материалах ежегодной технической конференции USENIX 2005 г. (USENIX'05), Анахайм, Калифорния, апрель 2005 г.
^ Перекрестная ссылка ядра FreeBSD/Linux sys/uvm/uvm_pdpolicy_clockpro.c

Внешние ссылки

К виртуальной машине O(1) Рика ван Риля о возможном использовании LIRS для балансировки кэша и программной памяти в Linux.
Отчет . о реализации замены страницы CLOCK-Pro
Проекты расширенной замены страниц, созданные командой разработчиков управления памятью Linux.
CLOCK-Pro, Патч разработанный Риком ван Риэлем.
CLOCK-Pro, Патч разработанный Питером Зийлстрой.
CLOCK-Pro упоминается в качестве примера в разделе Linux и академических кругов в книге «Профессиональная архитектура ядра Linux» Вольфгана Мауэрера.
Статья . с подробным описанием различий в производительности LIRS и других алгоритмов «Влияние предварительной выборки ядра на алгоритмы замены буферного кэша» Али Р. Батта, Криса Гниади и Ю. Чарли Ху

[SongJiang1-1] Цзян, Сун; Чжан, Сяодун (июнь 2002 г.). «LIRS: эффективная политика замены набора с низкой периодичностью между ссылками для повышения производительности буферного кэша». Обзор оценки производительности ACM SIGMETRICS . 30 (1): 31–42. дои : 10.1145/511399.511340 .

[:0-2] Мэттсон, РЛ; Гечеи, Дж.; Слуц, ДР; Трейгер, Иллинойс (1970). «Методы оценки иерархий хранения» . IBM Systems Journal . 9 (2): 78–117. дои : 10.1147/sj.92.0078 .

[SongJiang2-3] Сун Цзян; Сяодун Чжан (2005). «Как сделать LRU дружественным к слабым локальным рабочим нагрузкам: новый алгоритм замены для улучшения производительности буферного кэша» . Транзакции IEEE на компьютерах . 54 (8): 939–952. дои : 10.1109/TC.2005.130 . S2CID 11539061 .

[MySqlIntegration-4] svn commit — mysqldoc@docsrva: r6768 — магистраль/ndbapi

[Infinispan-5] Выселение Infinispan, пакетное обновление и LIRS

[SongJiang3-6] Сун Цзян, Фэн Чен и Сяодун Чжан, « CLOCK-Pro: эффективное улучшение замены часов », в материалах ежегодной технической конференции USENIX 2005 г. (USENIX'05), Анахайм, Калифорния, апрель 2005 г.

[NetBSD-7] Перекрестная ссылка ядра FreeBSD/Linux sys/uvm/uvm_pdpolicy_clockpro.c

[1]

[2]

[3]

[4]

[5]

[6]

[7]