Ein Cuckoo-Filter ist eine speichereffiziente probabilistische Datenstruktur zur näherungsweisen Prüfung, ob ein Element zu einer Menge gehört. Er wurde 2014 von Bin Fan, David G. Andersen, Michael Kaminsky und Michael Mitzenmacher vorgestellt. Wie ein Bloomfilter kann er fälschlich die Zugehörigkeit eines nicht enthaltenen Elements melden. Ein sicher negatives Ergebnis schließt die Zugehörigkeit dagegen aus. Im Unterschied zum klassischen Bloomfilter unterstützt ein Cuckoo-Filter das Einfügen und Entfernen von Elementen ohne zusätzliche Zähler.
Aufbau Der Filter besteht aus einer Hashtabelle mit mehreren Speicherplätzen pro Bucket. Von jedem eingefügten Element wird nur ein kurzer Fingerabdruck gespeichert. Für ein Element werden der Fingerabdruck und zwei mögliche Bucket-Indizes berechnet:
Dabei bezeichnet eine Hashfunktion und das bitweise Exklusiv-Oder. Durch die Exklusiv-Oder-Verknüpfung kann der jeweils andere Bucket allein aus dem aktuellen Index und dem Fingerabdruck bestimmt werden. Eine Abfrage sucht den Fingerabdruck nur in den beiden möglichen Buckets.
Operationen Beim Einfügen wird der Fingerabdruck zunächst in einem freien Platz eines der beiden Buckets abgelegt. Sind beide Buckets voll, verdrängt der Filter einen zufällig ausgewählten Fingerabdruck und versucht, diesen in dessen alternativen Bucket zu verschieben. Dieser Vorgang entspricht dem Prinzip des Cuckoo Hashing und wird wiederholt, bis ein freier Platz gefunden wurde oder eine festgelegte Zahl von Versuchen überschritten ist. Bei hoher Belegung kann eine Einfügung deshalb scheitern.
Für eine Mitgliedschaftsabfrage genügt die Suche nach dem Fingerabdruck in beiden Buckets. Bei einer Löschung wird ein passender Fingerabdruck aus einem der Buckets entfernt. Da verschiedene Elemente denselben Fingerabdruck besitzen können, darf eine Löschung nur für ein Element erfolgen, von dem bekannt ist, dass es zuvor eingefügt wurde. Andernfalls kann ein kollidierender Eintrag entfernt werden und ein falsch negatives Ergebnis entstehen.
Eigenschaften Die Länge der Fingerabdrücke bestimmt wesentlich die Falsch-positiv-Rate. Längere Fingerabdrücke benötigen mehr Speicher, verringern jedoch die Wahrscheinlichkeit einer Kollision. Größere Buckets verbessern typischerweise den möglichen Belegungsgrad, erhöhen aber zugleich die Zahl der Fingerabdrücke, die bei einer Abfrage verglichen werden.
Die ursprüngliche Untersuchung kam für praktisch relevante Filtergrößen und Falsch-positiv-Raten unter drei Prozent zu einem geringeren Speicherbedarf als bei speicheroptimierten Bloomfiltern. Cuckoo-Filter besitzen außerdem eine bessere Speicherlokalität bei Abfragen. Asymptotisch sind sie jedoch ungünstiger, weil die erforderliche Fingerabdrucklänge mit der Zahl der Einträge wächst.
Verwendung Cuckoo-Filter eignen sich für Datenbanken, Caches und Netzwerksysteme, die schnelle Mengenabfragen mit geringem Speicherbedarf und dynamischen Löschungen benötigen. Redis stellt Cuckoo-Filter als probabilistischen Datentyp mit Befehlen zum Anlegen, Einfügen, Abfragen und Löschen bereit.
Einzelnachweise
Kategorie:Datenstruktur Kategorie:Hash