Адаптивный кэш замены

Адаптивный кэш замены ( ARC ) — это алгоритм замены страниц с лучшая производительность ^[1] чем LRU (используется реже всего). Это достигается путем отслеживания как часто используемых, так и недавно использованных страниц, а также недавней истории выселений для обеих. Алгоритм был разработан ^[2] IBM в Исследовательском центре в Альмадене . В 2006 году IBM получила патент на политику адаптивной замены кэша .

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

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

ARC улучшает базовую стратегию LRU, разделяя каталог кэша на два списка, T1 и T2, для недавно и часто используемых записей. В свою очередь, каждый из них дополняется призрачным списком (B1 или B2), который прикрепляется к нижней части двух списков. Эти списки призраков действуют как системы показателей, отслеживая историю недавно удаленных записей из кэша, а алгоритм использует призраки для адаптации к недавним изменениям в использовании ресурсов. Обратите внимание, что списки- призраки содержат только метаданные (ключи для записей), а не сами данные ресурса, т. е. при исключении записи из списка- призрака ее данные удаляются. Каталог объединенного кэша организован в четырех списках LRU:

T1 — для последних записей кэша.
T2, для частых записей, упоминается как минимум дважды.
B1 — записи- призраки , недавно удаленные из кэша T1, но все еще отслеживаемые.
B2, аналогичные записи- призраки , но выселены из T2.

T1 и B1 вместе называются L1 и представляют собой объединенную историю недавних одиночных ссылок. Аналогично, L2 представляет собой комбинацию T2 и B2.

Весь каталог кэша можно представить в одной строке:

. . . [   B1  <-[     T1    <-!->      T2   ]->  B2   ] . .
      [ . . . . [ . . . . . . ! . .^. . . . ] . . . . ]
                [   fixed cache size (c)    ]

Внутренние скобки [ ] обозначают реальный кэш, который, хотя и имеет фиксированный размер, может свободно перемещаться по истории B1 и B2.

L1 теперь отображается справа налево, начиная сверху, на что указывает знак ! маркер. ^ указывает целевой размер для T1 и может быть равен, меньше или больше фактического размера (как указано ! ).

Новые записи входят в Т1 слева от ! , и постепенно смещаются влево, в конечном итоге вытесняются из T1 в B1 и, наконец, вообще выпадают.
Любая запись в L1, на которую ссылаются еще раз, получает еще один шанс и входит в L2, сразу справа от центрального ! маркер. Отсюда он снова выталкивается наружу, из Т2 в В2. Записи в L2, получившие еще одно попадание, могут повторять это бесконечно, пока они, наконец, не окажутся в крайнем правом углу B2.

Замена

Записи, (повторно) попадающие в кэш (T1, T2), вызовут ! для перемещения к целевому маркеру ^ . Если в кеше нет свободного места, этот маркер также определяет, будет ли T1 или T2 удалять запись.

Попадание в B1 увеличит размер T1, сдвигая ^ вправо. Последняя запись из T2 вытесняется в B2.
Попадания в B2 уменьшат T1, сдвигая ^ обратно влево. Последняя запись в T1 теперь вытеснена в B1.
Промах в кэше не повлияет на ^ , но ! граница переместится ближе к ^ .

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

В настоящее время ARC используется в контроллерах хранения данных IBM DS6000/ DS8000 .

Sun Microsystems от Масштабируемая файловая система ZFS использует вариант ^[3] ARC как альтернатива традиционному страничному кэшу файловой системы Solaris в виртуальной памяти. Он был изменен, чтобы разрешить блокировку страниц, которые используются в данный момент и не могут быть освобождены.

PostgreSQL какое-то время использовал ARC в своем менеджере буферов (версия 8.0.0), но быстро заменил его другим алгоритмом: сославшись на опасения по поводу патента IBM на ARC. ^[4]

VMware vSAN (ранее Virtual SAN) — это гиперконвергентное программно-определяемое хранилище (SDS), разработанное VMware. Он использует вариант ARC в своем алгоритме кэширования. ^[5]

OpenZFS поддерживает использование ARC и L2ARC в многоуровневом кеше в качестве кеша чтения. В OpenZFS операции чтения с диска часто попадают в дисковый кэш первого уровня в оперативной памяти с помощью ARC. Если SSD настроен для хранения дискового кэша второго уровня, он называется L2ARC. L2ARC использует тот же алгоритм ARC, но вместо хранения кэшированных данных в оперативной памяти L2ARC сохраняет кэшированные данные на быстром SSD. ^[6]^[7]^[8]^[9]^[10]^[11]

См. также

Ссылки

^ One Up на LRU, Usenix: вход; август 2003 г.
^ Нимрод Мегиддо и Дхармендра Модха , архив домашней страницы ARC от 09 марта 2010 г. , со ссылками на несколько статей.
^ комментарии в исходном файле Solaris ZFS arc.c объясняют различия с оригинальной работой.
^ Статья в Postgresql General Bits, «Сага об алгоритме и патенте ARC» , опубликована 6 февраля 2005 г.
^ Справочный документ «Алгоритмы кэширования VMware vSAN» ^{[ постоянная мертвая ссылка ]}
^ «Кэширование ZFS» .
^ "Букварь ZFS" .
^ Джим Солтер. «Постоянный L2ARC может появиться в ZFS в Linux» . 2020.
^ «Кэш: доступ к L2ARC» .
^ Брендан Грегг. «ЗФС Л2АРК» .
^ Ранвир Сингх. «Адаптивный кэш замены (ARC) и L2ARC» .

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

[1] One Up на LRU, Usenix: вход; август 2003 г.

[2] Нимрод Мегиддо и Дхармендра Модха , архив домашней страницы ARC от 09 марта 2010 г. , со ссылками на несколько статей.

[3] комментарии в исходном файле Solaris ZFS arc.c объясняют различия с оригинальной работой.

[4] Статья в Postgresql General Bits, «Сага об алгоритме и патенте ARC» , опубликована 6 февраля 2005 г.

[5] Справочный документ «Алгоритмы кэширования VMware vSAN» ^{[ постоянная мертвая ссылка ]}

[6] «Кэширование ZFS» .

[7] "Букварь ZFS" .

[8] Джим Солтер. «Постоянный L2ARC может появиться в ZFS в Linux» . 2020.

[9] «Кэш: доступ к L2ARC» .

[10] Брендан Грегг. «ЗФС Л2АРК» .

[11] Ранвир Сингх. «Адаптивный кэш замены (ARC) и L2ARC» .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]