¿Cuál es el algoritmo para expirar elementos en el almacenamiento de valores clave?

10

Estaba pensando en cómo los almacenes de valores clave actuales implementan la "fecha de caducidad" para los artículos. Actualmente tengo 2 variantes para eso en mi mente:

  1. no hacen nada (guardan los datos caducados) y solo verifican cuando lo hace, por ejemplo, OBTENER con alguna tecla. El problema aquí es que si tiene memoria limitada, los elementos caducados no se eliminarán.

  2. mantienen estructuras de datos adicionales para poder llegar a "caducar lo antes posible". Veo que se puede hacer con algo como esto:

    storage_data = dict(key -> [value, expire_timestamp])
expire_tree = SomeBinaryLikeTree(expire_timestamp -> [keys])
algorithms database Kostiantyn Rybnikov
fuente

Respuestas:

6

El problema de eliminar entradas caducadas en la memoria caché es muy equivalente a la recolección de basura , menos toda la complejidad del recuento de referencias.

Las personas en Nasza-Klasa han propuesto el algoritmo O (1) para Memcache de la siguiente manera:

Parece que muchas personas creyeron por alguna razón que liberar entradas caducadas no se puede realizar en O (1), o incluso que requiere operaciones Omega (N). El uso de un montón u otras estructuras de datos de cola prioritarias obviamente puede darle O (log N), pero el parche a continuación apunta a O (1). Esto se logra al tener un cubo por cada segundo, y al colocar cada entrada en un cubo adecuado al observar el tiempo de vencimiento. Luego, en cada segundo, solo liberamos elementos del siguiente cubo. Obviamente, este es el tiempo amortizado O (1), pero puede suceder que tenga muchos elementos que caduquen en el mismo momento, por lo que el parche ofrece un límite fijo para el número de operaciones que está dispuesto a realizar por cada solicitud, para hacer que la recolección de basura sea más fluida.

Ver propuesta completa con código adjunto .

vartec
fuente
Gracias. También pensé en la solución de "cubo" como una forma. Además, no hay problema con "demasiados elementos en el depósito", ya que puede utilizar el algoritmo "tomar los depósitos que no tomó la última vez y volver cuando haya terminado".
Kostiantyn Rybnikov
@k_bx: por eso proponen una lista de doble enlace, para que pueda volver a los grupos anteriores.
vartec
Si los cubos son algo así como segundos, entonces no necesita listas vinculadas en absoluto. Para ir anterior, simplemente disminuyes la clave :)
Kostiantyn Rybnikov
@k_bx: ¿disminuir la clave en cuánto? ¿un segundo? ¿Qué pasa si el cubo anterior no completamente vaciado fue hace 5 minutos? disminuir por paso de 1s 300 veces?
vartec
En el primer inicio del servidor, su variable init se llama current_expire_bucket a algún valor. Luego, ejecuta la limpieza comenzando desde current_expire_bucket, terminando el segundo actual. Después de que termine la limpieza, duermes por un pequeño período. Si el servidor se detiene, volverá a pasar por el mismo "depósito de caducidad", sí, pero debería ocurrir solo en las paradas del servidor.
Kostiantyn Rybnikov
7

Supongo que el almacenamiento de valor clave es demasiado grande para simplemente iterar sobre todos los pares kv para descubrir cuál puede expirar. También supongo que cada acceso de lectura actualiza la marca de tiempo de caducidad, por lo que solo caducan los elementos a los que no se ha accedido durante algún tiempo.

El desafío es encontrar de manera eficiente todos los registros que pueden caducar (cuando sea necesario realizar la limpieza), pero también actualizar de manera eficiente la marca de tiempo de caducidad en cada acceso de lectura (por lo que debemos encontrar la clave en la estructura utilizada para la caducidad).

Mi propuesta: agrupe expiry_timestamps en cubos; por ejemplo, si los artículos viven durante 8 horas, haga un cubo por hora. Esos cubos se mantienen en una lista vinculada; Cuando ocurre la caducidad, el primer depósito se vacía y la lista se reduce. El número de cubos es la vida útil / intervalo de limpieza. Cada depósito contiene un hashSet de todas las claves que deben expirar. La iteración sobre todas las claves en un hashset es lo suficientemente eficiente.

Durante el acceso de lectura, el programa verifica en qué depósito se encuentra actualmente la clave y a qué depósito pertenece ahora. En la mayoría de los casos, es el mismo depósito, por lo que no es necesaria ninguna otra acción. De lo contrario, retire la llave del cubo antiguo (eliminar de un conjunto de hash es eficiente) e insértelo en el nuevo cubo.

   +--------------+   +--------------+   +--------------+
-->+ Expiry 08:00 +-->+ Expiry 09:00 +-->+ Expiry 10:00 +
   | KeySet       |   | KeySet       |   | KeySet       |
   +--------------+   +--------------+   +--------------+
usuario281377
fuente