Was ist der Algorithmus zum Ablaufen von Elementen im Schlüsselwertspeicher?

Ich habe darüber nachgedacht, wie aktuelle Schlüsselwertspeicher das "Ablaufdatum" für Elemente implementieren. Derzeit habe ich 2 Varianten dafür im Kopf:

1. Sie tun nichts (behalten abgelaufene Daten bei) und überprüfen dies nur, wenn Sie beispielsweise mit einem Schlüssel GET ausführen. Das Problem hierbei ist, dass abgelaufene Elemente nicht gelöscht werden, wenn der Speicher begrenzt ist.

2. Sie behalten zusätzliche Datenstrukturen bei, um "frühestens ablaufen zu können". Ich sehe, dass es mit so etwas gemacht werden kann:

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

Das Problem des Löschens abgelaufener Einträge im Cache entspricht weitgehend der Speicherbereinigung abzüglich der gesamten Komplexität der Referenzzählung.

Die Mitarbeiter von Nasza-Klasa haben den O (1) -Algorithmus für Memcache wie folgt vorgeschlagen:

Es scheint, dass viele Leute aus irgendeinem Grund glaubten, dass das Freigeben abgelaufener Einträge in O (1) nicht durchgeführt werden kann oder dass sogar Omega (N) -Operationen erforderlich sind. Die Verwendung eines Heaps oder anderer Datenstrukturen in der Prioritätswarteschlange kann natürlich O (log N) ergeben, aber der folgende Patch zielt auf O (1) ab. Dies wird erreicht, indem für jede Sekunde ein Bucket vorhanden ist und jeder Eintrag durch Betrachten der Ablaufzeit in einen geeigneten Bucket gestellt wird. Dann befreien wir in jeder Sekunde nur Elemente aus dem nächsten Eimer. Dies ist offensichtlich eine amortisierte O (1) -Zeit, aber es kann vorkommen, dass viele Elemente gleichzeitig ablaufen. Daher bietet der Patch eine feste Grenze für die Anzahl der Vorgänge, die Sie pro Anforderung ausführen möchten. um die Speicherbereinigung reibungsloser zu gestalten.

Siehe gesamten Vorschlag mit beigefügtem Code .

Ich gehe davon aus, dass der Schlüsselwertspeicher zu groß ist, um nur alle kv-Paare zu durchlaufen, um herauszufinden, welche abgelaufen werden können. Ich gehe auch davon aus, dass jeder Lesezugriff den Ablaufzeitstempel aktualisiert, sodass nur Elemente abgelaufen sind, auf die seit einiger Zeit nicht mehr zugegriffen wurde.

Die Herausforderung besteht darin, alle Datensätze, die abgelaufen sein können (wann immer eine Bereinigung fällig ist), effizient zu finden, aber auch den Ablaufzeitstempel bei jedem Lesezugriff effizient zu aktualisieren (daher müssen wir den Schlüssel in der für den Ablauf verwendeten Struktur finden).

Mein Vorschlag: gruppiere expiry_timestamps in Eimern; Wenn Gegenstände beispielsweise 8 Stunden lang leben, stellen Sie einen Eimer pro Stunde her. Diese Eimer werden in einer verknüpften Liste gespeichert. Wenn der Ablauf eintritt, wird der erste Bucket geleert und die Liste reduziert. Die Anzahl der Buckets ist das Lebensdauer- / Bereinigungsintervall. Jeder Bucket enthält ein HashSet aller Schlüssel, die abgelaufen sein sollten. Die Iteration über alle Schlüssel in einem Hashset ist effizient genug.

Während des Lesezugriffs prüft das Programm, in welchem ​​Bucket sich der Schlüssel gerade befindet und zu welchem ​​Bucket er jetzt gehört. In den meisten Fällen handelt es sich um denselben Eimer, sodass keine weiteren Maßnahmen erforderlich sind. Entfernen Sie andernfalls den Schlüssel aus dem alten Bucket (das Entfernen aus einem Hash-Set ist effizient) und stecken Sie ihn in den neuen Bucket.

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