Cuckoo Filters
Cuckoo Filter to probabilistyczna struktura danych - podobnie jak Bloom Filter. W poprzednim poście znajdziecie krótki opis czym taka struktura danych się charakteryzuje (fałszywie dodatki wynik zapytania: “czy element zawiera się w danym zbiorze”).
O czym mowa?
Filtr kukułczy jest relatywnie młodą strukturą danych opisaną w 2014 roku przez Fan, Andersen, Kaminsky i Mitzenmacher. Poszerza ona wspomniane filtry bloom’a o usuwanie i zliczanie dodanych elementów, utrzymując przy tym porównywalną złożoność obliczeniową. Minimalizuje ona zasoby przechowując jedynie odcisk (ang. fingerprint) wartości elementu w zbiorze. W rzeczywistości jest to pewnego rodzaju tablica haszująca, która problem kolizji rozwiązuje za pomocą haszowania kukułczego (ang. cuckoo hashing).
Cuckoo hashing
Jak nietrudno się domyślić, nazwa filtra i haszowania wzięła się od kukułek. Kukułki znane są ze składania jaj w obcych gniazdach. Gdy mała kukułka wykluje się, eliminuje ona przybrane rodzeństwo usuwając je z gniazda. Nazywamy to pasożytnictwem lęgowym. Na podobnej zasadzie opiera się właśnie działanie haszowania/filtra kukułczego.
W przypadku haszowania każdy klucz jest haszowany przez dwie różne funkcje haszujące, gdzie każdej przyporządkowujemy tablicę, do której będzie można dodawać elementy. Jeżeli miejsce pod zadanym indeksem w pierwszej tablicy jest puste, możemy tam umieścić zadany element. Jeżeli miejsce to jest zajęte, próbujemy dodać element do tablicy drugiej (haszując drugą funkcją). Gdy to miejsce również jest zajęte, “eksmitujemy” element tam obecny i umieszczamy w to miejsce naszą wartość.
(grafika z https://adriancolyer.files.wordpress.com)
Na chwilę obecną mamy jeden nigdzie nieprzypisany element (ten usunięty z drugiej tablicy w poprzedniej iteracji). Ponieważ istnieją dwie funkcje/tablice, to użyjemy tego faktu do wyliczenia nowego miejsca w tablicy przeciwnej (pierwszej) i tam spróbujemy umieścić element. Gdy nawet w tym przypadku napotkamy na kolizję, dokonamy eksmisji kolejnego elementu i powtórzymy ten proces aż do momentu znalezienia miejsca w którejś z tablic.
Cuckoo filter - zasada działania
Jak już zostało wspomniane, działanie samego filtra opiera się na powyższej strategii i przedstawia się następująco:
Filtr przechowuje “odcisk” każdego dodanego elementu w jednym z wielu “gniazd” (ang. bucket) (odcisk jest ciągiem znaków pochodzącym z wartości hasza). Każde gniazdo posiada swoją wielkość (ang. capacity), czyli ile fingerprintów jest w stanie pomieścić. Przyjęło się identyfikować filtr poprzez rozmiar odcisku oraz wielkość gniazda właśnie. Np. filtr (2,4) przechowuje odciski o długości 2 znaków w 4-elementowych koszach (gniazdach).
Ze wszystkich operacji jakie oferuje filtr (dodawanie, usuwanie, sprawdzanie), dodawanie jest najbardziej skomplikowane. Aby dodać element potrzebujemy dwóch indeksów gniazd na podstawie hasza elementu i jego odcisku.
var hashedElement = Hash(element);
var index1 = GetIndexFromHash(hashedElement);
var fingerprint = GetFingerprint(hashedElement);
// index2 -> index1 XOR index uzyskany z hasza odcisku
var hashedFingerprint = Hash(fingerprint);
var index2 = index1 ^ GetIndexFromHash(hashedFingerprint);
var index2 = index2 % filterCapacity;
Próbujemy dodać element do gniazda spod indeksu 1-szego, a gdy ten jest pełny, to do 2-giego
if (filter.buckets[index1].Insert(fingerprint))
{
filterSize++;
return;
}
if (filter.buckets[index2].Insert(fingerprint))
{
filterSize++;
return;
}
I podobnie jak w opisie wyżej dotyczącym haszowania kukułczego, będziemy próbować przetasowywać elementy w tablicach aż do skutku (ustalonej z góry liczby powtórzeń) lub całkowitego wyczerpania miejsca, gdy próba dodania pod dwa indeksy się nie udała.
b2 próbujemy dodać do bucket[1], ale jest tam element c1, który zostaje wyeksmitowany do bucket[0], ale jest też dla niego wolne miejsce w alternatywnym bucket[2].
Jeżeli nie widać różnicy, to po co przepłacać?
Faworyzowałbym użycie Cuckoo Filter, dopóki aplikacja nie dodaje nowych danych (w dużej ilości) do filtra w krótkich odstępach czasu. Ze względu na rekursywną naturę algorytmu dodającego nowe elementy, która objawia się w momencie przepełnienia filtra, wydajność w porównaniu do Bloom Filtra wypada kiepsko. Autor publikacji dobrze to podsumował:
[…] for reasonably large sized sets, for the same false positive rate as a corresponding Bloom filter, cuckoo filters use less space than Bloom filters, are faster on lookups (but slower on insertions/to construct), and amazingly also allow deletions of keys (which Bloom filters cannot do)
Michael Mitzenmacher (2014)
PS. Pracuję nad implementacją filtra pod .NET Core, więc sprawdzajcie mojego githuba :)