Часть 1: https://habr.com/ru/articles/907408/

До версии 7.4 в redis срок жизни можно было указать срок действия только для конкретного ключа. с версии 7.4 это можно сделать и для поля в хештаблиц(hashes).
Существует 2 способа удаления сущностей с истекшим сроком действия:

• ленивый

• активный

Как это работает? Какие могут быть сложности с точки зрения удаления сущностей с истекшим сроком действия которые надо учесть при проектировании схемы хранения?
Текущая ситуация такова, что для ключей и полей хеш-таблиц это работает по разному.

Удаление ключей с истекшим сроком действия

Как хранятся сроки действия ключей. см. файл 'server.h' структура

typedef struct redisDb {

	kvstore *keys; /* The keyspace for this DB. As metadata, holds keysizes histogram */

	kvstore *expires; /* Timeout of keys with a timeout set */

Как уже показано в предыдущей статье для ключей сроки действия хранятся в отдельном kvstore, в хештаблице: ключ-"срок жизни"

Суть ленивого способа: при любом доступе к ключу проверяется его срок действия. Если ключ протух, то перед получением значения происходит его удаление.

Активный способ

Работа по активной экспирации ключей в файле expire.c
Активный способ активируется в нескольких случаях

• т.н. FAST. Вызывается в event loop. Обрабатывает немного, здесь мы его рассматривать не будем. Длительность цикла активной экспирации и объём обрабатываемых ключей может быть увеличен исходя из параметра конфигурации active-expire-effort - 1 по умолчанию. Как будет видно ниже параметр active-expire-effort позволяет увеличить объём ключей обрабатываемых за итерацию

// прим.
ACTIVE_EXPIRE_CYCLE_FAST_DURATION - 1000 мкс
ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP - 20 шт.
.....
effort = server.active_expire_effort-1, /* Rescale from 0 to 9. */
config_keys_per_loop = ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP +
ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP/4*effort,
config_cycle_fast_duration = ACTIVE_EXPIRE_CYCLE_FAST_DURATION +
ACTIVE_EXPIRE_CYCLE_FAST_DURATION/4*effort

Не отрабатывает, если предыдущая итерация экспирации вышла за временной лимит. (т.е. не загружаем event loop если по объёму неудалённых ключей всё плохо)

• т.н. SLOW. Работает по крону (можно отключить в debug-режиме через set-active-expire 0) с частотой по умолчанию 10 раз в секунду (параметр конфига hz 10).

void databasesCron(void) {
    /* Expire keys by random sampling. Not required for slaves
     * as master will synthesize DELs for us. */
    if (server.active_expire_enabled) {
        if (iAmMaster()) {
            activeExpireCycle(ACTIVE_EXPIRE_CYCLE_SLOW);
        } else {
        как по мне это красная тряпка и этим пользоваться нельзя
        * Expires of keys created in writable slaves
         * This implementation is currently not perfect but a lot better than leaking
 * the keys as implemented in 3.2.
            expireSlaveKeys();
        }
    }

По сути это основной режим с точки зрения удаления ключей с истекшим сроком жизни. Его и рассмотрим далее. Отключить его можно в DEBUG режиме через DEBUG set-active-expire 0

• существует ещё активная экспирация ключей на "writable slaves" но для меня вот такое "интро" перед методом expireSlaveKeys "...Expires of keys created in writable slaves... This implementation is currently not perfect but a lot better than leaking the keys as implemented in 3.2." - красный флаг для использования в прод режиме. Её я рассматривать не вижу смысла.

SLOW режим активного метода удаления ключей с истекшим сроком

По сути отличается от FAST увеличенными лимитами на число ключей и время выполнения. Схема работы кратко:

void activeExpireCycle(int type){
...
        /* сначала удаляем поля хештаблиц-ов*/
        activeExpireHashFieldCycle(type);
...
  for (j = 0; dbs_performed < dbs_per_call && timelimit_exit == 0 && j < server.dbnum; j++) {
  ...
                //потом проходимся по ключам базы
                while (data.sampled < num && checked_buckets < max_buckets) {
                db->expires_cursor = kvstoreScan(db->expires, db->expires_cursor, -1, expireScanCallback, isExpiryDictValidForSamplingCb, &data);
                if (db->expires_cursor == 0) {
                    db_done = 1;
                    break;
                }
                checked_buckets++;
            }
    //подбиваем статистику для мониторинга на основании данных итерации
  }
}

Удаление ключей для каждой базы в redis происходит отдельно. Базы обрабатываются последовательно, начиная с следующей относительно которой завершили предыдущий цикл удаления истекших ключей. Цикл по каждой БД ограничена: количеством ключей для просмотра за итерацию config_keys_per_loop = ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP + ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP/4*effort.
Количество итераций экспирации над базой ограничено:

• допустимым уровнем удалённых ключей от числа просмотренных, т.е. если удалено меньше определённого порога, считаем дальше искать по базе нет смысла, шансов найти ключ с истекшим сроком мало.

//ACTIVE_EXPIRE_CYCLE_ACCEPTABLE_STALE 10%
config_cycle_acceptable_stale = ACTIVE_EXPIRE_CYCLE_ACCEPTABLE_STALE-
effort;
repeat = db_done ? 0 : (data.sampled == 0 || (data.expired * 100 / data.sampled) > config_cycle_acceptable_stale);

процент так же регулируется через параметр active-expire-effort

• лимитом времени отпущенным на цикл итераций по базам. Для SLOW цикла этот период - 25мс по умолчанию. Ниже из формул понятно как управлять этим временем. Лимит времени проверяется каждые 16 итераций по базе данных.

#define ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC 25 /* Max % of CPU to use. */
...
timelimit = config_cycle_slow_time_perc*1000000/server.hz/100;
...
config_cycle_slow_time_perc = ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC +
2*effort

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

Сама итерация по базе проста (если она состоит из 1 таблице, если у нас кластер и 16К слотов и для каждой хеш-таблица или мы в процессе перехеширования - тут сложнее):
Проходимся по бакетам KV хранилища db->expires с того места с которого завершили в прошлый раз (expires_cursor)

while (data.sampled < num && checked_buckets < max_buckets) {
	db->expires_cursor = kvstoreScan(db->expires, db->expires_cursor, -1, expireScanCallback, isExpiryDictValidForSamplingCb, &data);
	if (db->expires_cursor == 0) {
	db_done = 1;
	break;
}
	checked_buckets++;
}

и пытаемся для каждого DictEntry применить функцию проверки ТТЛ, если DictEntry протух, производим стандартное удаление.

int activeExpireCycleTryExpire(redisDb *db, dictEntry *de, long long now) {
    long long t = dictGetSignedIntegerVal(de);
    if (now < t)
        return 0;

    enterExecutionUnit(1, 0);
    sds key = dictGetKey(de);
    robj *keyobj = createStringObject(key,sdslen(key));
    deleteExpiredKeyAndPropagate(db,keyobj);
    decrRefCount(keyobj);
    exitExecutionUnit();
    /* Propagate the DEL command */
    postExecutionUnitOperations();
    return 1;
}

плюсы подхода:

• поиск, вставка и удаление - имеют константную сложность

минусы:

• неэффективный процесс экспирации. Важно понимать, что мы пытаемся последовательно пройтись по бакетам хеш-таблицы и ключи там распределены по факту случайным образом. При этом, если годных ключей для экспирации "в моменте" мало, мы сделаем одну "пробу" и когда она покажет низкий процент экспирации перейдём к следующей базе. Это основная проблема метода.

• операция rперехеширования при хранении времени экспирации в kv-сторе expires требует много времени и памяти

• объём занимаемой памяти: 40 байт на элемент.

Мониторинг процесса

На какие метрики мы можем полагаться при оценке того, как идёт процесс удаления ключей с истекшим сроком жизни

INFO STATS

• avg_ttl - каждые 16 итерации (либо в конце цикла) для каждой базе обновляется средний ttl по просмотренным значениям;

• expired_time_cap_reached_count - факт превышения общего лимита времени на цикл удаления просроченых ключей;

• expire_cycle_cpu_milliseconds - времени потрачено на активную экспирацию

• expired_stale_perc - оценка сколько ключей ожидают экспирации исходя из прогресса в текущем цикле

if (total_sampled) {
	current_perc = (double)total_expired/total_sampled;
} else
	current_perc = 0;
server.stat_expired_stale_perc = (current_perc*0.05)+
(server.stat_expired_stale_perc*0.95);

• expired_keys - всего удалено по причине срока действия с момента сброса статистики по базе.

INFO KEYSPACE

db0:keys=13906244,expires=13906244,avg_ttl=882,subexpiry=0

expires - размер KV expires базы данных

Контроль latency

При превышении длительности порога "latency-monitor-threshold" процесса экспирации выбрасывается событие "expire-cycle".
Контролировать можно:
latency history expire-cycle
пример вывода:

127.0.0.1:16379> latency history expire-cycle
  1) 1) (integer) 1747146747
     2) (integer) 13
  2) 1) (integer) 1747146749
     2) (integer) 10
  3) 1) (integer) 1747146750
     2) (integer) 18
  4) 1) (integer) 1747146751
     2) (integer) 20
  5) 1) (integer) 1747146752
     2) (integer) 17
  6) 1) (integer) 1747146753

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

Попробуем пощупать проблему руками

Имеем в БД 0 два вида ключей (https://github.com/xelavopelk/redis-go-test): 30 млн с протуханием в сутки и 2 млн с протуханием в течении минуты (далее будет использоваться та же схема для сравнения). Смотрим скорость отрабатывания экспирации.

• Посмотрим на темп экспирации case1, все ключи в одной БД . Как видно, за 3 минуты удалено всего порядка 3 тыс ключей. Если база будет наполняться, то по сути они будут удалены, когда начнётся активное удаление суточных ключей либо при перехешировании связанном с увеличением объёма хранения.

ts: 02:01:30 PM info: # Keyspace db0:keys=31999999,expires=31999999,avg_ttl=81010601,subexpiry=0
 ...
 ts: 02:04:40 PM info:  # Keyspace
 db0:keys=31997626,expires=31997626,avg_ttl=86082556,subexpiry=0

• Если вынести "минутные" ключи отдельно - case2 - они будут обрабатываться быстро

ts: 02:35:27 db1:keys=2000000,expires=2000000,avg_ttl=41059,subexpiry=0
...
ts: 02:36:27 PM info:  # Keyspace db1:keys=268836,expires=268836,avg_ttl=3407,subexpiry=0
//далее пусто

т.о. за 1 минуту ушло 2 млн ключей.

Вывод: если не хочешь, чтобы болела голова не стоит мешать не только водку с пивом, но и ключи с разным сроком жизни в одной БД redis

Удаление полей hashes с истекшим сроком действия

Механика организации срока жизни для полей hashes отличается радикально. Причин на то много, например с точки зрения применения hashes если организоваться экспирацию так же их придётся бить на несколько по разным базам (см. описание проблематики выше), что резко усложнит применение структуры, т.к. как таковой единой структуры hashes-а уже не будет.

Особенности ленивого способа для hashes

Теоретически каждый раз при обращении к объекту согласно концепции lazy expiration необходимо удалять все поля с истекшим сроком. Такой подход имеет существенный недостаток: он может надолго приостановить работу основного потока, если за короткий срок истечёт действие значительного количества элементов. В качестве альтернативы для каждой команды определено своё поведение lazy expiration

• HGET, HMGET, HINCRBY(FLOAT), HEXISTS - произойдёт "ленивое удаление"

• HRANDFIELD - удалит все поля и истекшим временем перед выбора случайного поля

• HLEN - выдаст размер без учёта полей с истекшим сроком

• HGETALL - отфильтрует поля с истекшим сроком. может выдать пустой массив как KEYS

• HSCAN - отфильтрует поля и истекшим сроком (аналогично SCAN)

Активный способ для hashes

Хранение сроков жизни полей hashes в ebuckets-структурах
Расшифровывается как "expirity-buckets" - корзина содержащая элементы с определённым сроком жизни. Реализация основана на RAX-дереве (https://en.wikipedia.org/wiki/Radix_tree). У реализации есть api (например - выбери лист с минимальным значением) по добавлению, удалению и активной экспирации элемента. Время экспирации (ограничено длиной 6 байт) используется как ключ для перемещения по RAX-дереву, т.о. предельная глубина RAX-дерева - 6 уровней. Т.о. фактически мы можем принять что, работаем с деревом за константное время.

Структура корзин

Структура корзин организована иерархически следующим образом:

• ebuckets - структура верхнего уровня, основанная на RAX. Каждый лист в дереве RAX представляет собой корзину.

• корзина(bucket) - каждая корзина представляет собой интервал времени и содержит один или несколько сегментов. Ключ в дереве RAX для каждой корзины представляет собой минимальное времени истечения срока действия для элементов этой корзины,а ключ следующей корзины представляет собой максимальное время истечения срока действия. Под корзиной по сути считается ссылка на её первый сегмент - FirstSegHdr.

• segment - каждый сегмент в корзине может содержать до EB_SEG_MAX_ITEMS (в настоящее время 16) элементов в связанном списке. Если необходимо добавить в заполненный сегмент, произойдёт попытка разделения сегмента. Для экономии памяти список сегментов в корзине представляет собой обычный связанный список. Каждый сегмент может содержать до EB_SEG_MAX_ITEMS (16) элементов. При вставке нового элемента если он достиг максимальной вместимости произойдёт либо разделение сегмента либо разделение корзины на более мелкие диапазоны. Определяющий критерий: если сегмент заполнен до максимума и все элементы имеют одинаковый ключ истечения срока действия, то мы не разделяем корзину, а создаём сегмент расширения (NextSegHdr) и привязывая его к предыдущему (в пределе к первому сегменту) в корзине. В этом смысле extended сегменты корзины будут содержать только элементы с одним сроком действия.

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

Иерархия показана на диаграмме:

Пример:
Имеем 4 интервала:

Имеем следующее rax-дерево c корзинами на листовом уровне

Виды ebuckets

Существует глобальная структура ebuckets. В ней расположены ключи hashes а в качестве времени экспирации используется минимальное время экспирации в hashes-структуре
Данные по сроку действия полей хеш-таблиц лежат в структуре ebuckets hexpires базы данных:

...
	kvstore *expires; /* Timeout of keys with a timeout set */
	ebuckets hexpires; /* Hash expiration DS. Single TTL per hash (of next min field to expire) */
...
} redisDb;

Локальные структуры. Для экономии памяти hashes может существовать в 2х ипостасях listpack - если количество элементов меньше hash-max-listpack-entries (512 по умолчанию) и dictionary. При хранении в dictionary для каждой создаётся своя структура ebuckets:

/* Each dict of hash object that has fields with time-Expiration will have the

* following metadata attached to dict header */
typedef struct dictExpireMetadata {
	ExpireMeta expireMeta; /* embedded ExpireMeta in dict.
		To be used in order to register the hash in the
		global ebuckets (i.e db->hexpires) with next,
		minimum, hash-field to expire. TTL value might be
		inaccurate up-to few seconds due to optimization
		consideration. */
	ebuckets hfe; /* DS of Hash Fields Expiration, associated to each hash */
	sds key; /* reference to the key, same one that stored in db->dict. */
} dictExpireMetadata;

Кратко алгоритм удаления полей hashes

Попробуем пощупать руками

С точки зрения мониторинга пока всё плохо, есть только subkeys в 'info keyset', которая показывает количество ключей в глобальной ebucket структуре, для которых выставлено время экспирации. Для оценки я решил пойти косвенным путём выбрав длину по 1 тыс случайных hashs (как указано выше команда hlen не производит ленивого удаления).

• Темп экспирации case4 - для формата dictionary (1000 полей в hash) - 2 млн. полей ушло за 2 минуты. Разница с case2, где по сути проходим по массиву вынесенному в отдельную базу с высокой вероятностью удалить ключ, всего в 2 раза.

ts: 01:13:57 PM avgLen(after): 999.167
...
ts: 01:15:48 PM avgLen(after): 932.718

• Темп экспирации case3 для listpack (500 полей в hash) - на 2 миллиона полей ушло 5,5 минут

ts: 05/13/25 01:26:07 PM avgLen(after): 499.938
...
ts: 05/13/25 01:31:47 PM avgLen(after): 466.332

Вывод: Работа по экспирации полей для формата listpack намного менее эффективна, как если бы поля были бы разложены в хештаблицы. Ebuckets эффективная структура с точки зрения производительности при её применении к содержимому hash по производительности не намного уступающая выведению ключей одного срока экспирации в отдельную БД.

Оценка использования памяти ebuckets

Оптимальное использование памяти происходит когда у множества элементов одно и то же время экспирации, поскольку они будут храниться в одной корзине утилизируя механизм extended segments организованных в виде связанного списка. Сначала проигнорируем это и предположим, что каждый элемент имеет свой expiration time. в результате все сегменты будут работать вне концепции расширенных сегментов.
Замечания:

• каждый элемент содержит дополнительные 16 байт метаданных Expire Meta;

• заголовок сегмента составляет 16 байт;

• объём метаданных RAX на лист/сегмент/корзину примерно 40 байт (ключ корзины всего 6 байт)

Сценарий 1: корзины содержат мало элементов, не более EB_LIST_MAX_ITEMS
Когда ebucketы содержат не более EB_LIST_MAX_ITEMS 16 элементов они оптимизированы не аллоцировать дополнительную память. Он просто использует собственную expiremeta для поддержки собственной структуры данных в виде списка. Т.о. затраты памяти составляют 16 байт на элемент
Сценарий 2: большинство элементов удаляются при помощи активного метода экспирации
Если большая часть элементов удаляется по истечении срока действия, то размеры сегментов(корзин) будут определены в результате разделения и содержать как минимум 8 элементов и не более чем EB_LIST_MAX_ITEMS (=16). Он использует собственную структуру Expire Meta для поддержания собственной структуры в виде связанного списка. Таким образом расход памяти составляет 16 байт на элемент
Сценарий 3: Элементы удаляются не только методом активной экспирации
Если ожидается много "не последовательных удалений" элементов из корзин, то корзины могут сократиться до менее чем 4 элемента в корзине. Соответсвенно ebucket попытаемcя объединить соседние корзины. Т.о. ожидается что в среднем в сегменте корзины будет около 10 элементов.
Расчёт:

• в среднем 10 элементов в корзине: 16+16/10+40/10 = 21.6 байт на элемент

• в худшем случае 4 элемента в корзине: 16+16/4+40/4 = 30 байт на элемент

Сценарий 4: у всех элементов одно и то же время экспирации В этом случае в ebuckets будет только одна корзина с большим количеством расширенных сегментов. ExpireMeta становится доминирующей и на каждый сегмент будет выделяться указатель NextSegHdr размером 24 байта. Считая размер каждого сегмента 16 элементов мы получим: 16+24/16 = 17.5 байт. Т.о. даже худший случай лучше, чем если бы мы хранили данные экспирации ключей в хеш-таблице.