Redis Internals - реализация LRU для выборки

Question

Знает ли кто-нибудь о внутренностях выселения / удаления Redis LRU.

Как Redis гарантирует, что старые (менее используемые) ключи удаляются первыми (в случае, если у нас нет энергозависимых ключей и мы не устанавливаем срок действия TTL)?

Я точно знаю, что в Redis есть параметр конфигурации «maxmemory-samples», который определяет размер выборки, который он использует для удаления ключей - поэтому, если вы установите размер выборки 10, тогда он будет выбирать 10 ключей и удаляет самые старые из это.

Что я не знаю, так это то, что он выбирает эти ключи совершенно случайным образом или у него есть механизм, который позволяет ему автоматически выбирать из эквивалента «старшее / менее используемое поколение»?

Answer 1

Это то, что я нашел на antirez.com / post / redis-as-LRU-cache.html - весь смысл использования алгоритма «три примера» заключается в экономии памяти. Я думаю, что это гораздо более ценно, чем точность, тем более что рандомизированные алгоритмы редко бывают понятны. Пример: выборка только с тремя объектами истечет 666 объектов из набора данных 999 с частотой ошибок только 14% по сравнению с идеальным алгоритмом LRU. А в 14% из оставшихся почти нет элементов, которые входят в число очень используемых элементов. Так что прирост памяти окупится за точность без сомнений.

Таким образом, хотя Redis производит выборку случайным образом (подразумевая, что это не фактический LRU .. и, как таковой, алгоритм приближения), точность относительно высока, и увеличение размера выборки еще больше увеличит это. Однако в случае, если кому-то нужен точный LRU (для ошибки нулевой допуск), тогда Redis может оказаться неправильным выбором.

Архитектура ... как говорится ... - это компромиссы ... поэтому используйте этот подход (Redis LRU) для компромисса между точностью и необработанной производительностью.

Answer 2

Начиная с версии 3.0.0 (2014) алгоритм LRU использует пул из 15 ключей, заполненный лучшими кандидатами из различных выборок из N ключей (где N определяется как maxmemory-samples).

Каждый раз, когда необходимо выселить ключ, N новых ключей выбираются случайным образом и сравниваются с пулом.Если они являются более подходящими кандидатами (старые ключи), они добавляются в него, в то время как худшие кандидаты (самые последние ключи) удаляются, сохраняя пул в постоянном размере 15 ключей.

В конце раунда из пула выбирается лучший кандидат на выселение.

Источник: Код и комментарии в файле evict.c из исходного кода Redis