Biorąc pod uwagę nazwę użytkownika na stronie rejestracji użytkownika, jak stwierdzić, czy została już zarejestrowana?

Chociaż wysyłanie zapytań do indeksowanej bazy danych pomaga, jest powolne i powoduje wywołania sieciowe.

Aby przyspieszyć działanie, możemy przechowywać listę zarejestrowanych nazw użytkowników w magazynie klucz-wartość, takim jak Redis.

Oznacza to jednak buforowanie milionów rekordów i podwojenie naszej pamięci.

Jak możemy lepiej radzić sobie z tym pozornie trywialnym problemem?

Rozwiązaniem może być filtr Bloom, sprawdźmy to!

Co to jest filtr Blooma?

Filtr Bloom odpowiada na jedno proste pytanie,

Czy element istnieje w danym zbiorze?

Filtr Bloom to probabilistyczna struktura danych. Biorąc pod uwagę powyższe pytanie, wyświetla jedną z następujących odpowiedzi

• Prawdopodobnie tak
• 100% Nie

A jego największą zaletą jest to, że robi to w STAŁYM czasie i przestrzeni.

Jak to działa?

Filtr Bloom składa się z dwóch elementów

• Tablica bitów o rozmiarze N
• Kilka funkcji haszujących

Najpierw jest inicjalizowany jako tablica bitów o rozmiarze N ze wszystkimi bitami ustawionymi na zero. Załóżmy teraz, że długość tablicy wynosi 10.

Dodanie elementu

Dodanie elementu jest banalne

• Element z napisem „tygrys” jest haszowany za pomocą funkcji haszującej
• Wygenerowany skrót jest modyfikowany przez długość tablicy w celu uzyskania ograniczonego indeksu
• Indeks tablicy bitów jest następnie ustawiany na 1

Podobnie jak w przypadku dodawania elementu, mieszamy element za pomocą funkcji haszującej i modyfikujemy go, aby uzyskać ograniczony indeks.

Dane wyjściowe są oceniane w następujący sposób,

• Jeśli wartość indeksu tablicy bitów wynosi 0, element NIE znajduje się w zestawie.
• W przeciwnym razie przedmiot PRAWDOPODOBNIE jest w zestawie

Przechowywanie filtra Bloom

Zamiast przechowywać filtr bloom w postaci tablicy, możemy przekonwertować jego reprezentację bitową na liczbę dziesiętną.

Na przykład możemy przekonwertować tablicę zawierającą liczbę 1001119 i przechowywać ją w pamięci podręcznej.

Jeśli lista nie zmienia się zbyt często, serwer może wysłać liczbę dziesiętną do klienta, umożliwiając sprawdzenie poprawności po stronie klienta.

Czy możemy zrobić lepiej?

Jeśli funkcja haszująca zwraca indeks 1 zarówno dla „tygrysa”, jak i „krowy”, sprawdzenie, czy „krowa” jest w zestawie, daje odpowiedź Tak , nawet jeśli nie .

Możemy zmniejszyć prawdopodobieństwo fałszywych alarmów za pomocą następujących rozwiązań.

• Zwiększ długość tablicy
• Zwiększ liczbę funkcji haszujących

Zamiast jednego indeksu możemy uzyskać wiele indeksów za pomocą kilku skrótów.

Podczas dodawania elementu wszystkie uzyskane indeksy zostaną ustawione na 1.

Pozycja jest uważana za prawdopodobnie w zestawie, tylko jeśli WSZYSTKIE indeksy są ustawione na 1.

Wykorzystując te metody, możemy znacznie zmniejszyć prawdopodobieństwo fałszywych trafień.

Aplikacje

Rzućmy okiem na kilka przykładów z życia wziętych.

Sprawdź, czy nazwa użytkownika istnieje w procesie rejestracji użytkownika

• Gdy tworzona jest nazwa użytkownika, jest ona dodawana do filtra kwitnienia przechowywanego w magazynie klucz-wartość.
• Gdy użytkownik wprowadzi nazwę użytkownika na stronie rejestracji użytkownika, serwer najpierw wysyła zapytanie do filtra bloom.
• Jeśli nazwa użytkownika NIE znajduje się w filtrze bloom, serwer natychmiast zwraca błąd do klienta.
• W przeciwnym razie serwer wysyła zapytania i kontrole krzyżowe w bazie danych.

• Medium utrzymuje filtr Bloom dla każdego użytkownika.
• Przed poleceniem artykułu Medium sprawdza, czy identyfikator artykułu istnieje w filtrze Blooma użytkownika.
• Artykuły, które z pewnością NIE znajdują się w filtrze bloom, są polecane użytkownikowi.

• Podczas uzyskiwania dostępu do adresu URL Chrome najpierw sprawdza, czy adres URL należy do złośliwej listy.
• Zamiast za każdym razem odpytywać serwer Google, Google tworzy filtr bloom, używając z góry określonej listy złośliwych programów i wysyła go do przeglądarki.
• Przeglądarka haszuje adres URL i sprawdza krzyżowo z filtrem bloom przed uzyskaniem dostępu do witryny.

Chociaż mogą wystąpić fałszywe alarmy , filtr kwitnienia jest przydatny, gdy chcemy stwierdzić, czy elementu na pewno nie ma na liście.

Może być stosowany jako pierwsza warstwa filtrowania ze względu na swoją skuteczność zarówno w czasie, jak iw przestrzeni.

Mam nadzieję, że uznasz to za pomocne i do zobaczenia na następnym!