Filtry Blooma to funkcja analizy danych. Określają one, czy dany element danych, czy też zbiór danych, jest przechowywany w bazie danych, czy w rozproszonym zbiorze danych. Ich główną cechą jest wyjątkowa wydajność w tym zadaniu. Z tego powodu są szeroko stosowane w systemach, w których konieczne jest potwierdzenie istnienia określonego elementu danych w dużym zbiorze danych.
UJednym z najprzydatniejszych narzędzi do analizy informacji probabilistycznych i jednokierunkowych jest filtr Blooma. Filtry Blooma to: narzędzia lub instrumenty ułatwiające nam analizę dużych ilości informacji probabilistycznych. Służy to ustaleniu, czy dany element lub fragment danych należy do zbioru. Funkcja ta jest niezwykle przydatna w przypadku dużych ilości danych, zwłaszcza gdy nie można ich szybko i ręcznie przetworzyć.
Dlatego właśnie dzięki filtrom Blooma kryptowaluty takie jak Bitcoin Mają funkcję Portfele SPVAle tę funkcję widzimy również w kryptowalutach, ponieważ Ethereum gdzie pozwalają na wyszukiwanie informacji w ich blockchain, wydajnie.
Dzieje się tak dlatego, że filtry Blooma pozwalają nam uzyskać tylko dwa wyniki: fałszywie pozytywne lub fałszywie negatywne wynikiInnymi słowy, dzięki zastosowaniu filtrów Blooma można szybko i sprawnie określić, czy dane elementy istnieją w pamięci, czy też na pewno nie. Wyniki fałszywie dodatnie wskazują na możliwość, że dany element lub fragment danych może być częścią zbioru. Natomiast wyniki ujemne jednoznacznie wskazują, że dany element lub fragment danych nie znajduje się w ocenianym zbiorze. Narzędzie pozwala również całkowicie odrzucić wyniki fałszywie ujemne, co znacznie ułatwia analizę danych.
Ale co doprowadziło do powstania filtrów Blooma? Jaki jest ich związek ze światem blockchain? Cóż, o tym przekonamy się później.

Pochodzenie filtrów Blooma
Filtry Blooma zostały zaprojektowane w latach 70. XX wieku przez dewelopera Burton Howard Bloom. Bloom, absolwent informatyki na MIT, zaprojektował te filtry jako ekonomiczną pod względem przestrzeni probabilistyczną strukturę danych, która pozwala użytkownikom sprawdzić, czy dany element lub fragment danych należy do zbioru. Celem ich stworzenia było stworzenie narzędzia do klasyfikacji danych z wykorzystaniem funkcji skrótu, które zwracają wynik lub identyfikator, a jednocześnie dają jednoznaczną odpowiedź, czy sprawdzany element nie należy do zbioru, lub wskazują, że prawdopodobnie zostanie do niego dołączony.
Dzięki temu konstrukcja filtrów Blooma umożliwia szybką obsługę dużych baz danych lub informacji. Jednocześnie efektywnie wykorzystują one przestrzeń dyskową. Dzieje się tak, ponieważ filtry Blooma nie wymagają przechowywania ani przechowywania samych elementów lub danych, a jedynie sprawdzenia ich obecności w zestawie. Ta operacja na danych tylko do odczytu zapewnia wysoką wydajność i możliwości przetwarzania dużych ilości informacji.
Jak konfiguruje się filtry Blooma?
Filtry Blooma mają strukturę danych zwaną macierz wejściowaTa macierz ma długość lub pojemność pamięci tak dużą, jak potrzeba. Oznacza to, że Podczas konstruowania filtra Blooma możesz określić jego długość.w razie potrzeby. Określając, ile wpisów zostanie dodanych do podstawowej struktury danych i ile funkcje skrótu Będą one używane w filtrze, będąc powiązane z każdym z tych wejść.
Podobnie przy projektowaniu należy wziąć pod uwagę, że Zakres funkcji skrótu musi zaczynać się od 0 i kończyć na liczbie istniejących wpisów pomniejszonej o 1Oznacza to, że jeśli filtr Blooma jest zaprojektowany dla 10 wejść, będzie zaczynał się od numeru 0 i kończył na numerze 9. Jeśli jest zaprojektowany dla 20 wejść, filtr Blooma będzie zaczynał się od numeru 0 i kończył na numerze 19. Jest to praktyka projektowania obliczeniowego, która ma na celu optymalizację zasobów przetwarzania filtra w jak największym stopniu.
Podobnie, gdy zbiór istniejących wpisów ma wszystkie wartości 0, oznacza to, że dane nie znajdują się w filtrze Blooma. Jest on zatem pusty. Zatem po dodaniu danych lub elementów do filtra, informacje zostaną przepuszczone przez odpowiednie funkcje skrótu, które umieszczą je w odpowiednich lokalizacjach w filtrze Blooma. Lokalizacje te będą wówczas odzwierciedlać wartość 1, wskazując, że zawierają elementy, które zostały już przeanalizowane.
Na podstawie tych wartości zbudowane jest działanie filtrów Blooma, które szczegółowo wyjaśnimy poniżej.
Jak działają filtry Blooma
Po skonfigurowaniu filtra Blooma możemy rozpocząć sprawdzanie, czy dany element należy do zbioru, czy nie. Aby to zrobić, proces rozpoczyna się od przekazania żądanych danych wejściowych do algorytmu filtra Blooma. Innymi słowy, pobieramy dane z systemu i przetwarzamy je za pomocą funkcji skrótu systemu. Funkcje skrótu zwrócą w rezultacie dwie pozycje.
Te hasze i zwracane przez nie pozycje są przechowywane i powiązane z danymi, które je wygenerowały. Filtr kontynuuje gromadzenie informacji, stosując do nich funkcje skrótu i zapisując wyniki. Proces ten obejmuje jednak dodatkową procedurę, która maksymalizuje jego wydajność i skraca czas reakcji systemów stosujących ten typ filtra do swoich struktur danych.
Po pierwsze, jeśli dane przekazane do filtra są przetwarzane przez funkcje skrótu i zwracają pozycje o wartościach innych niż 0, oznacza to, że element znajduje się w zbiorze. Jest to tzw. wynik dodatni, wskazujący na istnienie danego elementu w zbiorze. Możliwe jest również, że funkcje skrótu zwracają wyniki o różnych wartościach.
I odwrotnie, jeśli jedna lub obie pozycje wskazują wartość 0, to element z pewnością nie znajduje się w zbiorze. Inną sytuacją przewidywaną przez algorytm jest wynik negatywny lub fałszywie dodatni. Ten wynik jest ostateczny lub rozstrzygający, ponieważ filtry Blooma nigdy nie generują wyników fałszywie ujemnych. Innymi słowy, jeśli algorytm filtra Blooma wykryje wynik negatywny lub fałszywie dodatni, informacja ta z pewnością nie znajduje się w analizowanym zbiorze danych.
Ponadto, podczas konfiguracji filtra Blooma kluczowe jest zdefiniowanie liczby bitów i funkcji skrótu, które mają zostać zastosowane. Większa liczba funkcji skrótu znacznie zmniejsza współczynnik błędów, a tym samym prawdopodobieństwo wystąpienia wyników fałszywie dodatnich. Dodatkowo, po całkowitym zapełnieniu zestawu bitów filtra Blooma, danych wejściowych nie można usunąć. Zapobiega to występowaniu wyników fałszywie ujemnych w filtrze.

Jak duże znaczenie mają wyniki fałszywie dodatnie i fałszywie ujemne w filtrach Blooma?
Znaczenie stanów fałszywie dodatnich i fałszywie ujemnych w filtrach Blooma leży w ich skuteczności. Jak już wspomnieliśmy, filtry Blooma są zaprogramowane tak, aby uwzględniać oba te stany. A jeśli wystąpią, możemy podjąć odpowiednie działania, aby zapewnić odpowiednią reakcję.
Na przykład, jeśli pracujemy z systemem przechowywania danych w celu wygenerowania pamięci podręcznej, filtr Blooma jest niezwykle pomocny. Dzieje się tak, ponieważ za każdym razem, gdy system odbiera dane, sprawdza, czy nie znajdują się one już w pamięci podręcznej. Jeśli więc wprowadzimy te dane, a filtr Blooma zwróci wynik negatywny lub fałszywie pozytywny, możemy być pewni, że dane nie znajdują się w zbiorze danych, który przetwarzamy. W takim przypadku możemy zapisać te nowe dane w pamięci podręcznej, aby móc uzyskać do nich szybki i wydajny dostęp później.
Jeśli natomiast filtr Blooma zwróci wynik pozytywny, możemy po prostu zrezygnować z przechowywania informacji i pracować z tym, co mamy w pamięci podręcznej. Umożliwi to lepszy dostęp do informacji, a tym samym pozwoli zaoszczędzić cenne zasoby obliczeniowe.
Tego typu operacje nie są rzadkością w oprogramowaniu, z którego korzystamy na co dzień. Na przykład przeglądarki internetowe korzystają z danych buforowanych na naszych dyskach twardych, aby zapewnić nam szybszy dostęp do niektórych zasobów w porównaniu z dostępem do tych danych online. Bazy danych serwerów i inne systemy przetwarzające ogromne ilości danych również wykorzystują filtry Blooma lub podobne algorytmy, aby zwiększyć wydajność swoich reakcji i przetwarzania danych.
Funkcje skrótu w filtrach Blooma
Podczas konfigurowania filtra Blooma należy użyć niezależnych i równomiernie rozłożonych funkcji skrótu. Funkcje skrótu pozwalają na przypisanie identyfikatora dowolnemu typowi danych, który następnie można wykorzystać do indeksowania lub porównywania tych danych w zestawie.
Mówiąc o funkcjach skrótu, mamy na myśli te dobrze znane, takie jak SHA-256, MD5 czy CRC32. Należy jednak zachować ostrożność podczas korzystania z filtrów Blooma. Chociaż korzystanie z wielu funkcji skrótu zwiększa bezpieczeństwo, to jednocześnie sprawia, że proces jest bardziej złożony i wolniejszy, dlatego funkcje należy dobierać tak, aby maksymalizować ich możliwości.
Jednokierunkowa natura funkcji skrótu pozwala na utworzenie lub ustalenie identyfikatora na podstawie danego elementu lub fragmentu danych, ale uniemożliwia proces odwrotny. W związku z tym, jeśli użytkownik odkryje identyfikator, nie będzie w stanie określić, które dane lub elementy są z nim powiązane.
Zalety i wady stosowania filtra Blooma
Zaleta
- Filtry Blooma, ponieważ nie przechowują zestawu danych jako takiego, Są bardziej wydajne pod względem wykorzystania przestrzeni dyskowejPonieważ przechowują one jedynie informację, czy informacja lub element znajduje się w filtrze Blooma.
- Podobnie ta funkcja pozwala na to, że Weryfikację danych lub elementów można przeprowadzić znacznie szybciej i sprawniej.Należy jednak pamiętać, że im większa liczba funkcji skrótu, tym dłużej filtr Blooma będzie potrzebował na sprawdzenie istnienia elementów lub danych.
- Podobnie jak Filtry Blooma wykorzystują koncepcję haszowania jednokierunkowego. Jeśli użytkownik uzyska do nich dostęp, nie będzie mógł bezpośrednio poznać żadnych informacji zawartych w tych filtrach.
Wady
- Te narzędzia Nie zwracają danych. zweryfikowane. Zamiast tego pozwalają jedynie sprawdzić, czy istnieją, czy nie.
- W przypadku uzyskania wyników pozytywnych można jedynie założyć, że są one prawdopodobnie poprawne. Nie ma pewności ani pełnego zapewnienia, że dane pozytywne stanowią część całościowego obrazu. Inaczej jest w przypadku wyników negatywnych, gdzie można uzyskać ostateczną odpowiedź lub ostateczny wynik.
- Podczas projektowania filtra Blooma należy określić jego rozmiar, niezależnie od tego, czy jest to kilka czy miliony bitów. Po ustaleniu rozmiaru nie można go już zmniejszyć ani zwiększyć ponad wartość ustaloną wcześniej. Dlatego, aby filtr Blooma był wydajny, konieczne jest wcześniejsze zdefiniowanie lub wyraźne określenie, ile danych zostanie dodanych. Bez tych informacji, filtr Blooma prawdopodobnie zostanie zaprojektowany ze zbyt małą liczbą elementów, co sprawi, że będzie nieskuteczny w przetwarzaniu żądanych informacji. Alternatywnie, można zaprojektować bardzo duży filtr Blooma, wymagający znacznej ilości miejsca na dane, które musi przetworzyć, co prowadzi do marnotrawstwa przestrzeni.
Przykłady zastosowań filtrów Blooma
Kryptowaluty: Bitcoin i Ethereum
System Bitcoin wykorzystuje filtry Blooma do przyspieszenie synchronizacji portfeli SPVTe filtry pozwalają węzłom określić tylko te transakcje, dla których chcą otrzymywać aktualizacje systemu. Tworzy to zestaw transakcji, który może zostać przesłany do wszystkich węzłów sieci. Tam transakcje mogą zostać zweryfikowane za pomocą tych filtrów i otrzymane zostanie potwierdzenie, czy dany zestaw transakcji został dodany do łańcucha. Eliminuje to potrzebę zarządzania pełną kopią blockchaina. W Bitcoinie ta funkcjonalność jest zastępowana przez bloki kompaktowe (Compact Blocks), o których mowa w... BIP-158.
Sieć Ethereum ze swojej strony wykorzystuje filtry Blooma jako mechanizm, dzięki któremu możesz znaleźć logi w swoim blockchainieDzięki wdrożeniu tych filtrów można łatwo wyszukiwać zdarzenia, które miały miejsce w systemie Ethereum, bez przeciążania go nadmiarem danych. Pozwala to aplikacjom na znacznie wydajniejsze zarządzanie tymi informacjami, a jednocześnie zmniejsza zapotrzebowanie na dużą ilość miejsca na dysku, ponieważ filtry Blooma eliminują konieczność przechowywania potencjalnie zduplikowanych danych w systemie.
W Ethereum, gdy blok jest generowany i weryfikowany, adres kontraktu i indeksowane pola rekordów są dodawane do filtra Blooma. Filtr ten znajduje się w nagłówku bloku. Dzięki temu, jeśli aplikacja chce znaleźć wszystkie wpisy w rekordzie, węzeł musi jedynie przeskanować nagłówek. Pozwala to ustalić, czy wymagane dane są obecne. Elementy te nie są dodawane do samego bloku, aby zaoszczędzić miejsce na dysku.
Sieci i kanały informacyjne
Inną ważną implementacją filtrów Blooma jest możliwość rekomendowania użytkownikom artykułów przez sieci informacyjne lub kanały, co zapobiega ich powtarzaniu. Innymi słowy, Możesz zobaczyć, które artykuły przeczytał dany użytkownik, aby polecić mu artykuły, których jeszcze nie czytał..
Podobnie duże centra danych i sieci dostarczania treści (CDN) stosują filtry Blooma, aby zmaksymalizować wydajność przechowywania danych i wykorzystania sieci, zapobiegając przeciążaniu systemów przez zduplikowane lub rzadko używane elementy. Dotyczy to firm takich jak Akamai, Namecheap CDN, Fastly i Cloudflare.
Autor


