Qual è l'algoritmo per gli elementi in scadenza nell'archiviazione dei valori-chiave?

Question

Qual è l'algoritmo per gli elementi in scadenza nell'archiviazione dei valori-chiave?

#1 da (6 voti)
#2 da (6 voti)

9

Stavo pensando a come gli attuali archivi di valori-chiave implementano la "data di scadenza" per gli articoli. Attualmente ho 2 varianti per questo nella mia mente:

non fanno nulla (mantengono i dati scaduti) e controllano solo quando lo fai, ad esempio, OTTIENI con qualche chiave. Il problema qui è che se la memoria è limitata, gli elementi scaduti non verranno eliminati.
mantengono strutture dati aggiuntive per essere in grado di "non scadere" prima. Vedo che può essere fatto con qualcosa di simile:
```
storage_data = dict(key -> [value, expire_timestamp])
expire_tree = SomeBinaryLikeTree(expire_timestamp -> [keys])
```

database algorithms

posta Kostiantyn Rybnikov 30.05.2012 - 11:13

fonte

2 risposte

6

Suppongo che l'archiviazione dei valori-chiave sia troppo grande per iterare su tutte le coppie k-v per scoprire quale può essere scaduto. Suppongo inoltre che ogni accesso in lettura aggiorni il timestamp della scadenza, quindi sono scaduti solo gli elementi che non sono stati acceduti per un certo periodo di tempo.

La sfida consiste nel trovare in modo efficiente tutti i record che possono essere scaduti (ogni volta che la pulizia è in scadenza), ma anche aggiornare in modo efficiente il timestamp di scadenza su ogni accesso in lettura (quindi dobbiamo trovare la chiave nella struttura utilizzata per la scadenza).

La mia proposta: gruppo expiry_timestamps in bucket; per esempio, se gli articoli vivi per 8 ore, fai un secchio all'ora. Questi bucket sono tenuti in una lista collegata; quando scade la scadenza, il primo bucket viene svuotato e l'elenco ridotto. Il numero di bucket è l'intervallo di durata della vita / pulizia. Ogni bucket contiene un hashSet di tutte le chiavi che dovrebbero essere scadute. L'iterazione su tutte le chiavi in un hashset è sufficientemente efficiente.

Durante l'accesso in lettura, il programma controlla su quale bucket è attualmente inserita la chiave e su quale bucket ora appartiene. Nella maggior parte dei casi, è lo stesso bucket, quindi non è necessaria alcuna ulteriore azione. Altrimenti, rimuovi la chiave dal vecchio bucket (la rimozione da un set di hash è efficiente) e inseriscila nel nuovo bucket.

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

risposta data 30.05.2012 - 12:00

fonte

Leggi altre domande sui tag database algorithms

Esiste un algoritmo noto per pianificare i matchup dei tornei? Perché Quicksort è chiamato "Quicksort"?

score 6 · Accepted Answer

Il problema dell'eliminazione delle voci scadute nella cache è un equivalente di raccolta dei rifiuti , meno intero complessità del conteggio dei riferimenti.

Le persone di Nasza-Klasa hanno proposto l'algoritmo O (1) per Memcache come segue:

It seems that many people believed for some reason that freeing expired entries can not be performed in O(1), or even that it requires Omega(N) operations. Using a heap, or other priority queue data structures can obviously give you O(log N), but the patch below aims at O(1). This is achieved by having one bucket for each second, and by putting each entry in a proper bucket by looking at the expiration time. Then at each second we just free elements from the next bucket. This is obviously O(1) amortized time, but it can happen that you have a lot of elements that expire at the very same moment, so the patch offers a fixed limit for number of operations that you are willing to perform per one request, to make the garbage collection run smoother.

Vedi intera proposta con codice allegato .