Jaki jest algorytm wygasania przedmiotów w pamięci kluczy?

Myślałem o tym, w jaki sposób obecne magazyny klucz-wartość wdrażają „datę ważności” artykułów. Obecnie mam na myśli 2 warianty:

1. nic nie robią (przechowują wygasłe dane) i sprawdzają tylko wtedy, gdy robisz, na przykład GET przez jakiś klucz. Problem polega na tym, że jeśli masz ograniczoną pamięć, wygasłe elementy nie zostaną usunięte.

2. przechowują dodatkowe struktury danych, aby „najwcześniej wygasły”. Widzę, że można to zrobić za pomocą czegoś takiego:

   storage_data = dict(key -> [value, expire_timestamp])
   expire_tree = SomeBinaryLikeTree(expire_timestamp -> [keys])
   

Problem usuwania wygasłych wpisów w pamięci podręcznej jest w dużej mierze równoznaczny z odśmiecaniem , pomniejszonym o całą złożoność liczenia referencji.

Ludzie w Naszej-Klasie zaproponowali następujący algorytm O (1) dla Memcache:

Wydaje się, że wiele osób wierzyło z jakiegoś powodu, że uwolnienia wygasłych wpisów nie można wykonać w O (1), a nawet że wymaga to operacji Omega (N). Użycie sterty lub innych struktur danych kolejki priorytetowej może oczywiście dać O (log N), ale poniższa łatka ma na celu O (1). Osiąga się to poprzez posiadanie jednego wiadra na sekundę i umieszczenie każdego wpisu w odpowiednim wiadrze, patrząc na czas wygaśnięcia. Następnie w każdej sekundzie uwalniamy elementy z następnego wiadra. Jest to oczywiście amortyzowany czas O (1), ale może się zdarzyć, że masz wiele elementów, które wygasają w tym samym momencie, więc łatka oferuje stały limit liczby operacji, które chcesz wykonać na jedno żądanie, sprawiając, że zbieranie śmieci działa płynniej.

Zobacz całą ofertę z dołączonym kodem .

Zakładam, że pamięć klucz-wartość jest zbyt duża, aby iterować po wszystkich parach kv, aby dowiedzieć się, które mogą wygasnąć. Zakładam również, że każdy dostęp do odczytu odświeża znacznik czasu wygaśnięcia, dlatego wygasają tylko te elementy, które nie były dostępne przez pewien czas.

Wyzwanie polega na wydajnym znalezieniu wszystkich rekordów, które mogą wygasnąć (za każdym razem, gdy konieczne jest czyszczenie), ale także efektywnym odświeżeniu znacznika czasu wygaśnięcia przy każdym dostępie do odczytu (więc musimy znaleźć klucz w strukturze używanej do wygaśnięcia).

Moja propozycja: grupuj datownik_czasowy w znaczniki; na przykład, jeśli przedmioty żyją przez 8 godzin, zrób jedno wiadro na godzinę. Wiadra te są przechowywane na połączonej liście; gdy nastąpi utrata ważności, pierwsze wiadro jest opróżniane, a lista zmniejszana. Liczba segmentów to okres użytkowania / interwał czyszczenia. Każdy segment zawiera hashSet wszystkich kluczy, które powinny wygasnąć. Iteracja wszystkich kluczy w zestawie skrótów jest wystarczająco wydajna.

Podczas dostępu do odczytu program sprawdza, w którym segmencie znajduje się obecnie klucz i do którego segmentu należy teraz. W większości przypadków jest to to samo wiadro, więc nie są wymagane żadne dalsze działania. W przeciwnym razie wyjmij klucz ze starego wiadra (usuwanie z zestawu skrótów jest skuteczne) i włóż go do nowego wiadra.

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