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) для точности компромисса для сырой производительности.