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:

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.
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])
```

algorithms database

— Kostiantyn Rybnikov
źródło

Odpowiedzi:

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 .

— vartec
źródło

Dzięki. Pomyślałem też o rozwiązaniu „wiaderkowym” jako jednym ze sposobów. Nie ma też problemu z „zbyt dużą ilością elementów w wiadrze”, ponieważ możesz użyć algorytmu „weź wiadra, których nie wziąłeś ostatnio, i wróć, gdy skończysz”.

— Kostiantyn Rybnikov

@k_bx: dlatego proponują podwójnie połączoną listę, abyś mógł wrócić do poprzednich segmentów.

— vartec

Jeśli segmenty to coś w rodzaju sekund, nie potrzebujesz wcale połączonych list. Aby przejść do poprzedniej, wystarczy zmniejszyć klawisz :)

— Kostiantyn Rybnikov

@k_bx: zmniejsz klucz o ile? sekundę? co jeśli poprzednie nie całkowicie opróżnione wiadro było 5 minut temu? zmniejszyć o 1 s 300 razy?

— vartec

Przy pierwszym uruchomieniu serwera zmienna init o nazwie current_expire_bucket ma pewną wartość. Następnie uruchamiasz czyszczenie, zaczynając od current_expire_bucket, kończąc na bieżącym drugim. Po zakończeniu sprzątania śpisz przez krótki czas. Jeśli serwer się zatrzyma, przejdziesz ponownie przez to samo „wygaśnięcie segmentu”, tak, ale powinno się to zdarzyć tylko przy zatrzymaniach serwera.

— Kostiantyn Rybnikov

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       |
   +--------------+   +--------------+   +--------------+

— użytkownik 281377
źródło