Informatyka i programowanieAlgorytmy — sprytne sposoby rozwiązywania problemów

Filtr Blooma celowo zgadza się na fałszywe trafienia

Filtr Blooma odpowiada na pytanie „czy ten element może należeć do zbioru?” przy użyciu bardzo małej ilości pamięci. Dodanie elementu ustawia kilka bitów wskazanych przez funkcje hashujące. Jeśli podczas sprawdzania choć jeden wymagany bit jest zerem, elementu na pewno wcześniej nie dodano. Jeśli wszystkie są jedynkami, odpowiedź brzmi tylko „prawdopodobnie tak”, ponieważ te same bity mogły zostać ustawione przez inne elementy. Struktura świadomie dopuszcza więc false positives, ale w klasycznej wersji nie daje false negatives dla dodanych elementów. To kontrolowany kompromis: trochę niepewności kupuje ogromną oszczędność przestrzeni.

Zbiór bez przechowywania elementów

Klasyczny problem wygląda niewinnie: mamy wielki zbiór identyfikatorów i chcemy szybko sprawdzać, czy nowy identyfikator był już widziany. Dokładna struktura musiałaby w jakiejś formie przechować informację wystarczającą do rozróżnienia wszystkich elementów. Filtr Blooma wybiera inny kontrakt. Nie próbuje odtwarzać elementów i nie obiecuje perfekcyjnej odpowiedzi „tak”. Utrzymuje jedynie tablicę bitów oraz kilka funkcji hashujących.

Dodając element, obliczamy kilka pozycji i ustawiamy odpowiadające im bity na 1. Przy sprawdzaniu obliczamy te same pozycje. Jeśli choć jedna ma wartość 0, wynik jest rozstrzygający: ten element nie mógł zostać wcześniej dodany, bo jego dodanie ustawiłoby wszystkie wymagane bity. Gdy wszystkie są jedynkami, nie wiemy, czy ustawił je właśnie ten element, czy przypadkowa kombinacja innych wpisów.

Błąd jest częścią specyfikacji, nie awarią

Burton Bloom w pracy z 1970 roku analizował właśnie kompromis pomiędzy pamięcią, czasem odrzucenia elementu nieobecnego oraz dopuszczalną częstością błędów. Pozwolenie, by niewielka część nieobecnych wiadomości została błędnie uznana za członków zbioru, umożliwia znaczące zmniejszenie potrzebnego obszaru pamięci.

To odwraca zwyczajową intuicję programistyczną. „Błędna odpowiedź” nie musi oznaczać błędu implementacji, jeśli jej rodzaj i prawdopodobieństwo są jawnie wpisane w interfejs algorytmu. Filtr Blooma jest użyteczny właśnie dlatego, że błędy są jednostronne: klasyczna wersja może powiedzieć „może jest”, gdy elementu nie ma, ale dla elementu rzeczywiście dodanego nie powinna powiedzieć „na pewno nie ma”, o ile nie wykonujemy operacji nieobsługiwanych przez zwykły filtr, takich jak naiwne usuwanie bitów.

Skąd biorą się fałszywe trafienia

W miarę dodawania elementów coraz więcej bitów zostaje ustawionych. Hashowanie różnych elementów może wskazywać te same pozycje. W końcu nowy, nigdy niewidziany element może trafić zestawem swoich hashy wyłącznie na bity ustawione wcześniej przez innych. Filtr nie ma wtedy informacji pozwalającej odróżnić przypadkowe pokrycie od prawdziwej obecności.

Prawdopodobieństwo false positive zależy od liczby bitów, liczby funkcji hashujących oraz liczby dodanych elementów. Za mało hashy słabo wykorzystuje tablicę; zbyt wiele szybko ustawia prawie wszystko na 1. Istnieje więc optymalny zakres zależny od zaplanowanej pojemności i akceptowanego poziomu błędu. Struktura powinna być projektowana pod przewidywane obciążenie, a nie powiększana bez końca bez świadomości skutków.

Po co pytać „na pewno nie?”

Najciekawsze zastosowanie filtra Blooma polega często na ochronie droższej operacji. Wyobraźmy sobie bazę danych na wolnym nośniku. Zanim wykonamy kosztowny odczyt, filtr może bardzo szybko stwierdzić, że klucza na pewno nie ma. Tylko odpowiedź „może jest” wymaga właściwego sprawdzenia w źródle prawdy. False positive powoduje wtedy dodatkową pracę, ale nie daje użytkownikowi błędnego rekordu, bo drugi etap weryfikuje wynik dokładnie.

To ważny wzorzec architektoniczny: niedokładny algorytm może być częścią dokładnego systemu, jeżeli jego błędy są bezpieczne i wychwytywane w kolejnym kroku. Filtr nie zastępuje bazy danych; działa jak bardzo tani strażnik redukujący liczbę niepotrzebnych zapytań.

Wielkość filtra, liczba elementów i liczba hashy tworzą jeden kompromis

Fałszywe trafienia nie mają stałego prawdopodobieństwa przypisanego do samej nazwy „Bloom filter”. Zależą od rozmiaru tablicy bitowej m, liczby wstawionych elementów n i liczby funkcji hashujących k. Zbyt mało hashy ustawia niewiele bitów i słabo wykorzystuje tablicę; zbyt wiele szybko zapełnia ją jedynkami, przez co przypadkowe zapytania łatwo znajdują wszystkie wymagane bity ustawione. Dla klasycznego modelu można dobrać k do stosunku m/n, minimalizując prawdopodobieństwo fałszywego trafienia. Projektant wybiera więc budżet pamięci i akceptowalny poziom błędu razem. To ważna cecha struktur probabilistycznych: nie oferują po prostu „mniej pamięci za trochę błędu”, lecz pozwalają ilościowo ustawić punkt pracy między tymi zasobami.

#bazy danych#Bloom filter#false positive#hashowanie#pamięć#struktury probabilistyczne
Źródła i weryfikacja
Otrzymuj codzienne losowe ciekawostki