Каков алгоритм истечения срока действия элементов в хранилище значений ключа?

10

Я думал о том, как текущие хранилища значений ключей реализуют «дату истечения» для элементов. В настоящее время у меня есть 2 варианта для этого:

  1. они ничего не делают (сохраняют данные с истекшим сроком действия), и проверяют, только когда вы делаете, например, GET по некоторому ключу. Проблема здесь в том, что если вы ограничены в памяти, просроченные элементы не будут удалены.
  2. они сохраняют дополнительные структуры данных, чтобы иметь возможность «истечь раньше». Я вижу, что это можно сделать с помощью чего-то вроде этого:

    storage_data = dict(key -> [value, expire_timestamp])
    expire_tree = SomeBinaryLikeTree(expire_timestamp -> [keys])
    
Константин Рыбников
источник

Ответы:

6

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

Сотрудники Nasza-Klasa предложили алгоритм O (1) для Memcache следующим образом:

Кажется, что многие люди почему-то полагали, что освобождение просроченных записей не может быть выполнено в O (1), или даже что это требует операций Omega (N). Использование кучи или других структур данных очереди с приоритетами, очевидно, может дать вам O (log N), но патч ниже нацелен на O (1). Это достигается наличием одного сегмента на каждую секунду и размещением каждой записи в соответствующем сегменте с учетом времени истечения. Затем каждую секунду мы просто освобождаем элементы из следующего сегмента. Очевидно, это амортизированное время O (1), но может случиться так, что у вас будет много элементов, срок действия которых истекает в один и тот же момент, поэтому патч предлагает фиксированный предел для числа операций, которые вы готовы выполнить за один запрос, сделать сборку мусора более гладкой.

Посмотреть все предложение с приложенным кодом .

Vartec
источник
Спасибо. Я также думал о «ведре» решения как один из способов. Также нет проблем с «слишком большим количеством предметов в корзине», так как вы можете использовать алгоритм «взять корзины, которые вы не взяли в прошлый раз, и вернуться, когда закончите».
Константин Рыбников
@k_bx: именно поэтому они предлагают двойной связанный список, так что вы можете вернуться к предыдущим сегментам.
vartec
Если интервалы - что-то вроде секунд, то вам не нужны связанные списки вообще. Чтобы перейти предыдущим, нужно просто уменьшить ключ :)
Константин Рыбников
@k_bx: уменьшить ключ на сколько? одна секунда? Что делать, если предыдущее не полностью опустошенное ведро было 5 минут назад? уменьшить на 1с в 300 раз?
vartec
При первом запуске сервера вы инициируете переменную с именем current_expire_bucket для некоторого значения. Затем вы запускаете очистку, начиная с current_expire_bucket и заканчивая текущей секундой. После окончания уборки вы спите в течение небольшого периода времени Если сервер останавливается, вы снова пройдете тот же период «истечения срока хранения», да, но это должно происходить только на остановках сервера.
Константин Рыбников
7

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

Задача состоит в том, чтобы эффективно найти все записи, срок действия которых может быть истек (при необходимости очистки), а также эффективно обновить отметку времени истечения при каждом доступе к чтению (поэтому мы должны найти ключ в структуре, используемой для истечения срока действия).

Мое предложение: группа expiry_timestamps в ведра; например, если предметы живут в течение 8 часов, сделайте одно ведро в час. Эти корзины хранятся в связанном списке; когда истекает срок действия, первый контейнер очищается, а список сокращается. Количество сегментов - это срок службы / интервал очистки. Каждое ведро содержит хэш-набор всех ключей, срок действия которых должен истечь. Итерация по всем ключам в хэш-наборе достаточно эффективна.

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

   +--------------+   +--------------+   +--------------+
-->+ Expiry 08:00 +-->+ Expiry 09:00 +-->+ Expiry 10:00 +
   | KeySet       |   | KeySet       |   | KeySet       |
   +--------------+   +--------------+   +--------------+
user281377
источник