FIFO первый пришел первый вышел

Первый пришел первый вышел, первый пришел первый вышел

FIFO отсеивает данные по принципу «First In, First Out», что в точности соответствует характеристикам очереди, а структура данных реализована с использованием очереди Queue.

Недавно полученные данные вставляются в конец очереди FIFO, данные последовательно перемещаются в очередь FIFO, а данные в начале очереди FIFO удаляются;

преимущество:

Простота реализации

недостаток:

Отсутствие оптимизации на основе частоты использования данных, времени и других параметров приведет к более низкой частоте попаданий в кэш.

LRU Наименее недавно использованный

Наименее недавно использовавшийся Не использовавшийся в последнее время, обычно переводится как «наименее недавно использовавшийся».

И B, и A использовались до процесса поэтапного отказа, обновите последнее время использования. C ни разу не использовался, хотя это не самые старые данные, но по мнению LRU, его нужно ликвидировать.

Алгоритм замены наименее недавно использовавшихся страниц, т. е. первыми удаляются страницы, которые не использовались дольше всего.

Суть в том, чтобы посмотреть на продолжительность времени между последним использованием страницы и моментом планирования.

преимущество:

Кэш точки доступа будет постоянно попадать

недостаток:

Когда все кэшированные данные становятся горячими, преимущества LRU теряются.

LFU в последнее время используется реже всего

Наименее часто используемый Наименее часто используемый алгоритм исключения, обычно переводимый как «наименее часто используемый в последнее время».

Всякий раз, когда кэш используется ( CBA ), частота использования увеличивается на 1, а когда выполняется процесс исключения, удаляются наименее часто используемые данные ( E ).

преимущество:

Повышение эффективности обращений к часто используемым данным

недостаток:

Преимущество теряется при частом доступе ко всем данным

Простой LFU будет иметь проблему, которая приведет к аннулированию кеша.Если к недавно добавленному E не было доступа до того, как появится F, он будет удален. Перед тем, как дать E возможность быть посещенной, E исключается. Таким образом, мы можем установить медианную частоту доступа, когда приходит E, чтобы гарантировать, что новые данные не будут удалены немедленно.

Замена адаптивного кэша ARC

Adaptive Replacement Cache — это адаптивный алгоритм замены кэша, сочетающий LRU и LFU.

Суть ARC заключается в увеличении размера соответствующего связанного списка LRU или LFU в соответствии с ситуацией доступа к исключенным данным.

ARC содержит четыре связанных списка. LRU и LRU Ghost, LFU и LFU Ghost, связанный список Ghost — это связанный список записей данных, соответствующий исключению, данные не записываются, записываются только идентификатор и другая информация.

После того, как данные A будут добавлены в LRU, при повторном доступе к A они будут одновременно помещены в связанный список LFU. Следовательно, кэш связанного списка LFU — это данные многократного обращения к связанному списку LRU.

Когда связанный список LRU исключает B, тогда информация B войдет в связанный список LRU Ghost. Если доступ к B осуществляется позже, размер связанного списка LRU увеличивается, а размер связанного списка LFU уменьшается. Связанный список LFU такой же.

Итак, это алгоритм, который динамически настраивается на основе недавнего неиспользования и наименее частого использования.

преимущество:

Динамически настраивайте размеры LRU и LFU в зависимости от использования памяти, чтобы приспособиться к текущим лучшим попаданиям в кэш.

недостаток:

Занять больше места в памяти

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