Cuckoo Filter

Dlaczego Nie Używać Po prostu Filtra Blooma?

Filtry Blooma odpowiadają na zapytania o przynależność do zbioru, haszując element przy użyciu kilku niezależnych funkcji hashujących i ustawiając odpowiednie bity w współdzielonym tablicy bitów. Sprawdzenie przynależności polega na sprawdzeniu, czy wszystkie te bity są ustawione. Projekt ten jest kompaktowy i szybki, ale ma wadę strukturalną: po ustawieniu bitów filtr nie wie, który element spowodował zmianę tego bitu, ponieważ wiele elementów może współdzielić ten sam bit. Oznacza to, że nigdy bezpiecznie nie można wyczyścić bitu w celu usunięcia jednego elementu, ponieważ czyniąc to, można bezwiednie przerwać testy przynależności dla innych elementów, które przypadkowo polegają na tym samym bicie. Filtry Cuckoo całkowicie omijają ten problem, zmieniając to, co jest przechowywane. Zamiast rozrzucać bity po współdzielonej tablicy, przechowują krótki, wyraźny odcisk palca – krótką ciąg bitów wyprowadzony z haszowania elementu – w konkretnej przegródce w tablicy z podziałem na kontenery (bucketed hash table). Każdy odcisk palca zajmuje własną, identyfikowalną przegródkę zamiast anonimowo przyczyniać się do współdzielonych bitów. Ta różnica strukturalna sprawia, że usunięcie jest wykonalne: aby usunąć element, filtr po prostu musi znaleźć swój odcisk palca w jednym z dwóch kandydatowych kontenerów i wyczyścić tę konkretną przegródkę, bez ryzyka uszkodzenia innych przechowywanych elementów. Nie oznacza to, że filtry Cuckoo są lepsze we wszystkich aspektach. Filtry Blooma są prostsze do wdrożenia, nie wymagają logiki wydalania i mogą być płynnie dostrojone do bardzo niskich błędów fałszywych pozytywnych poprzez dodanie więcej funkcji hashujących i bitów. Filtry Cuckoo, w zamian za obsługę usuwania, potrzebują nieco więcej prowadzenia ksiąg i, w rzadkich przypadkach, mogą nie umieścić elementu, jeśli łańcuchy wydalania nie kończą się w określonej liczbie uderzeń. W praktyce jednak, dla tego samego docelowego poziomu błędów fałszywych pozytywnych, filtry Cuckoo często są bardziej efektywne pod względem zużycia przestrzeni niż filtry Blooma, zwłaszcza przy niskich błędach fałszywych pozytywnych, i dodają wyszukiwanie oraz usuwanie, które zachowują się przewidywalnie w odniesieniu do poszczególnych odcisków palców, zamiast współdzielonych bitów. Wybór między nimi zależy od prostego pytania: czy obciążenie robocze kiedykolwiek wymaga usunięcia elementów ze zbioru? Jeśli tak, to zaleta projektu filtra Cuckoo staje się decydująca.

Wzory Podobieństwa Zamiast Przełączania Bitów

Rdzeń filtra cuckoo to wzorzec: krótka, stałej długości ciąg bitów generowany przez haszowanie oryginalnego elementu i wyprowadzanie z niego zwartego podsumowania poprzez przycięcie lub inne operacje. Typowy wzorzec może mieć od czterech do szesnaściu bitów, znacznie mniejszy niż sam element. Jest to celowe skompresowanie stratne. Filtr nigdy nie przechowuje oryginalnego elementu, tylko ten mały wzorzec, który utrzymuje ogólną strukturę w kompaktowej formie. Ponieważ wzorzec jest tak krótki, wiele różnych elementów może haszować do tego samego wartości wzorca. Jest to źródło fałszywych pozytywów filtra cuckoo: jeśli zapytasz o elemencie, który nigdy nie został wprowadzony, ale jego wzorzec przypadkowo pasuje do jednego z już obecnych w dwóch kandydatowych koszykach, filtr błędnie zgłosi, że element jest obecny. Prawdopodobieństwo tego zdarzenia jest bezpośrednio regulowane przez długość wzorca. Dłuższe wzorce oznaczają mniej kolizji i niższą częstość fałszywych pozytywów, ale również oznaczają, że tabela zużywa więcej pamięci na przechowywany element, więc długość wzorca jest głównym pokrętłem do handlowania między dokładnością a przestrzenią.

Wzorce nie zachowują żadnej użytecznej informacji o oryginalnym elemencie. Nie można zrekonstruować elementu ze swojego wzorca, a filtr nigdy w tym nie potrzebuje, ponieważ każda operacja, wstawianie, wyszukiwanie i usuwanie, potrzebuje jedynie wartości wzorca i dwóch indeksów koszyków, w których może potencjalnie znajdować się. Jest to celowe ograniczenie projektowe, które utrzymuje strukturę zarówno kompaktową, jak i samowystarczalną: wszystko, czego filtr potrzebuje do przeniesienia lub zweryfikowania wzorca, można wyprowadzić z niego na bieżąco, pochodząc z samego wzorca, nigdy nie z przechowywanego kopii oryginalnych danych.

Dwa-Zbiornikowa Sztuczka: Znajdowanie Wzoru Podpisowego

Klasyczne cuckoo hashing przechowuje pełne klucze lub pary klucz-wartość, a alternatywny zbiór dla każdego klucza jest zwykle obliczany przez hashowanie klucza samodzielnie przy użyciu drugiej funkcji hashującej. Cuckoo filter nie może tego zrobić bezpośrednio, ponieważ celowo odrzuca oryginalny element po obliczeniu podpisu, pozostawiając tylko krótki podpis w tabeli. Jak więc wie, gdzie znajduje się alternatywny zbiór podpisu, jeśli już go nie ma do ponownego haszowania? Odpowiedź to mała matematyczna elegancja. Podczas pierwszego wprowadzania elementu filtr oblicza swój pierwszy indeks zbioru za pomocą hashowania elementu bezpośrednio, oznaczmy go jako i1. Następnie oblicza się podpis f elementu zgodnie z zasadą. Drugi kandydacki zbiór, i2, jest obliczany nie przez ponowne hashowanie elementu, ale przez XORowanie i1 z hashem f. Ta formuła ma piękny samowiązujący się właściwość: zastosowanie tej samej operacji ponownie, XORowanie i2 z hashem f, zwraca cię do i1. Innymi słowy, z każdego indeksu zbioru lub plus podpis siedzący w nim filtr zawsze może przekalkulować drugi kandydacki zbiór bez potrzeby posiadania oryginalnego elementu.

To dokładnie to umożliwia działanie łańcuchów wykluczających. Podczas wprowadzania, jeśli oba kandydatowe zbiory nowego podpisu są już pełne, filtr wybiera poddany element z jednego z zajętych slotów, wyklucza go i musi znaleźć ten poddany element nowy dom. Ponieważ poddany element jest tylko podpisem siedzącym w zbiorze, filtr odzyskuje swój alternatywny zbiór za pomocą formuły XOR, a następnie próbuje umieścić go tam, potencjalnie powodując kolejne wykluczenie. To rozchodzi się, zbiór po zbiorze, aż do znalezienia pustego slotu lub osiągnięcia maksymalnej liczby prób relokacji. Jest to dokładnie ta sama idea przesunięcia używana w cuckoo hashing, działająca na kompaktowych podpisach zamiast pełnych kluczy.

Wstawianie, Wyszukiwanie i Płynący Łańcuch Ewidencji

Wstawianie elementu do filtru cuckoo rozpoczyna się od obliczenia jego odciska palca oraz dwóch kandydackich koszyków, i1 i i2, przy użyciu hasha elementu i relacji XOR opisanej powyżej. Jeśli którykolwiek z tych koszyków ma wolne miejsce, a kosze zwykle zawierają kilka miejsc, aby poprawić współczynnik obciążenia, odcisk palca jest po prostu umieszczany tam i wstawianie jest zakończone. Ciekawe jest jednak, gdy oba kandydackie kosze są całkowicie pełne. Filtr wybiera jeden z dwóch koszyków, losowo wybiera jedno z zajętych miejsc w nim i wypycha ten odcisk palca, zapisując nowy odcisk palca w uwolnionym miejscu. Wypchnięty odcisk palca nie jest odrzucany; filtr oblicza jego alternatywny koszyk za pomocą tej samej sztuczki XOR i próbuje go umieścić, prawdopodobnie wypychając kolejny odcisk palca. Ta łańcuch przesunięć trwa do momentu, aż któryś z koszyków ma miejsce, lub do momentu, gdy wyczerpano skonfigurowaną maksymalną liczbę uderzeń, w tym momencie filtr jest uważany za zbyt pełny i wstawianie zawodzi, sygnalizując, że należy go przekształcić lub zbudować z większej tabeli. Wyszukiwanie jest porównywalnie proste i zawsze kończy się szybko. Aby sprawdzić, czy element może być w zestawie, filtr oblicza jego odcisk palca oraz oba indeksy kandydackich koszyków, a następnie sprawdza, czy ten odcisk palca występuje w którymkolwiek z tych koszyków. Jeśli tak, filtr zgłasza element jako obecny, co może być fałszywym pozytywem; jeśli nie, filtr zgłasza element jako nieobecny, a to negatywna odpowiedź jest zawsze poprawna, ponieważ prawdziwie wprowadzony odcisk palca musi koniecznie nadal znajdować się w jednym z jego dwóch kandydackich koszyków. Usuwanie odbiera od wyszukiwania prawie dokładnie, co jest sensem struktury. Filtr oblicza odcisk palca i dwa kandydackie kosze, szuka w obu pasującego odciska palca i jeśli go znajduje, czyści to konkretne miejsce. Ponieważ odcisk palca zajmuje identyfikowalne miejsce zamiast współdzielonych bitów, ta operacja jest całkowicie bezpieczna i nie może uszkodzić statusu członkostwa jakiegokolwiek innego przechowywanego elementu, coś, czego Bloom filter fundamentalnie nie może zagwarantować.

Praktyczne Kompromisy i Zastosowania w Realnym Świecie

Filtry Cuckoo wyróżniają się w systemach, które potrzebują przybliżonych testów przynależności do zbiorów, które zmieniają się w czasie, a nie tylko rosną. Klasyczne przypadki użycia filtrów Bloom, takie jak szybkie odrzucanie błędnego trafienia pamięci podręcznej przed dostępem do wolnego dysku lub sieciowego wyszukiwania, sprawdzanie, czy URL znajduje się na znanym blokierze, lub filtrowanie duplikatów elementów roboczych w strumieniu, często wymagają również usuwania wpisów, gdy dane wygasają lub stają się nieaktualne. Bazy danych, routery sieciowe monitorujące przepływ ruchu i warstwy buforowania przyjęły filtry Cuckoo ze względu na to, że ich zbiory robocze kurczą się wraz z rozwojem, a częste przebudowywanie całego filtra Bloom od zera tylko po usunięciu kilku nieaktualnych elementów jest często zbyt kosztowne. Istnieją jednak realne kompromisy. Filtry Cuckoo generalnie muszą utrzymywać swój współczynnik obciążenia poniżej pewnego progu, zwykle około 90-95 procent w zależności od rozmiaru koszyka, aby skrócić łańcuchy wykluczeń i zminimalizować prawdopodobieństwo niepowodzenia wprowadzania. Przesunięcie tabeli zbyt blisko pełnej może spowodować, że wprowadzenia zaczną się niepowodzeniem, nawet jeśli w zasadzie jest gdzieś miejsce w tabeli; filtr po prostu nie może znaleźć drogi do niego w ramach budżetu prób i błędów. Oznacza to, że planowanie pojemności ma większe znaczenie dla filtrów Cuckoo niż dla filtrów Bloom, które degradują bardziej łagodnie, z rosnącym współczynnikiem fałszywych pozytywów, gdy wypełniają się. Istnieje również subtelna uwaga dotycząca poprawności, którą warto wziąć pod uwagę: usuwanie elementu, który nigdy nie był wprowadzony, jest niebezpieczne. Jeśli wyszukiwanie zwraca fałszywy wynik dla jakiegoś elementu, a kod błędnie go usunie, to usunięcie to może usunąć odcisk palca, który w rzeczywistości należy do innego, legalnie wprowadzonego elementu o tym samym współczynniku odcisków palców, ponieważ odcisk palca nie jest unikalnym identyfikatorem. Prawidłowe użytkowanie wymaga, aby usunięcia były wydawane tylko dla elementów, które aplikacja może niezależnie potwierdzić, że zostały wprowadzone, dyscyplina, z której filtry Bloom, nie posiadając możliwości usuwania, nigdy się nią nie przejmowały. Wybór między filtrem Bloom, filtrem Cuckoo i bardziej złożonymi strukturami, takimi jak liczące filtry Bloom, w ostatecznym rozrachunku zależy od uwzględnienia budżetu pamięci, potrzeb dotyczących zmienności oraz tego, jak starannie otaczająca aplikacja może śledzić, które elementy zostały faktycznie wprowadzone.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Cuckoo Filter i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.