Я думал о том, как текущие хранилища значений ключей реализуют «дату истечения» для элементов. В настоящее время у меня есть 2 варианта для этого:
- они ничего не делают (сохраняют данные с истекшим сроком действия), и проверяют, только когда вы делаете, например, GET по некоторому ключу. Проблема здесь в том, что если вы ограничены в памяти, просроченные элементы не будут удалены.
они сохраняют дополнительные структуры данных, чтобы иметь возможность «истечь раньше». Я вижу, что это можно сделать с помощью чего-то вроде этого:
storage_data = dict(key -> [value, expire_timestamp]) expire_tree = SomeBinaryLikeTree(expire_timestamp -> [keys])
источник
Я предполагаю, что хранилище ключ-значение слишком велико, чтобы просто перебирать все kv-пары, чтобы выяснить, какой из них истек. Я также предполагаю, что при каждом доступе на чтение обновляется отметка времени истечения, поэтому просрочены только те элементы, к которым не было доступа в течение некоторого времени.
Задача состоит в том, чтобы эффективно найти все записи, срок действия которых может быть истек (при необходимости очистки), а также эффективно обновить отметку времени истечения при каждом доступе к чтению (поэтому мы должны найти ключ в структуре, используемой для истечения срока действия).
Мое предложение: группа expiry_timestamps в ведра; например, если предметы живут в течение 8 часов, сделайте одно ведро в час. Эти корзины хранятся в связанном списке; когда истекает срок действия, первый контейнер очищается, а список сокращается. Количество сегментов - это срок службы / интервал очистки. Каждое ведро содержит хэш-набор всех ключей, срок действия которых должен истечь. Итерация по всем ключам в хэш-наборе достаточно эффективна.
Во время доступа к чтению программа проверяет, в какой корзине находится ключ в данный момент и к какой корзине он принадлежит. В большинстве случаев это одно и то же ведро, поэтому никаких дальнейших действий не требуется. В противном случае извлеките ключ из старого ведра (удаление из набора хэшей эффективно) и вставьте его в новое ведро.
источник