Wie können wir anhand eines Benutzernamens auf einer Benutzerregistrierungsseite feststellen, ob er bereits registriert wurde?

Das Abfragen einer indizierten Datenbank ist zwar hilfreich, aber langsam und verursacht Netzwerkaufrufe.

Um die Dinge zu beschleunigen, können wir die Liste der registrierten Benutzernamen in einem Schlüsselwertspeicher wie Redis zwischenspeichern.

Das bedeutet jedoch, Millionen von Datensätzen zwischenzuspeichern und unseren Speicherbedarf zu verdoppeln.

Wie können wir dieses scheinbar triviale Problem besser lösen?

Der Bloom-Filter könnte die Antwort sein, lass es uns ausprobieren!

Was ist ein Bloomfilter?

Ein Blütenfilter beantwortet eine einfache Frage,

Existiert ein Element in einer gegebenen Menge?

Ein Bloomfilter ist eine probabilistische Datenstruktur. Angesichts der obigen Frage gibt es eine der folgenden Antworten aus

• Wahrscheinlich ja
• 100% Nein

Und sein größter Vorteil ist, dass es dies in KONSTANTER Zeit und Raum tut.

Wie funktioniert es?

Ein Bloomfilter besteht aus zwei Komponenten

• Ein Bitarray der Größe N
• Mehrere Hashing-Funktionen

Es wird zuerst als ein Bitarray der Größe N initialisiert, wobei alle seine Bits auf Null gesetzt sind. Nehmen wir an, die Länge des Arrays sei vorerst 10.

Artikel hinzufügen

Das Hinzufügen eines Elements ist trivial

• Das Element „Tiger“ wird mithilfe einer Hash-Funktion gehasht
• Der generierte Hash wird durch die Arraylänge modifiziert, um einen begrenzten Index zu erhalten
• Der Index des Bitarrays wird dann auf 1 gesetzt

Ähnlich wie beim Hinzufügen eines Elements hashen wir das Element mithilfe einer Hash-Funktion und modifizieren es, um einen begrenzten Index zu erhalten.

Die Ausgabe wird wie folgt ausgewertet,

• Wenn der Indexwert des Bitarrays 0 ist, ist das Element NICHT im Satz.
• Ansonsten ist der Artikel WAHRSCHEINLICH im Set

Aufbewahrung eines Bloomfilters

Anstatt den Bloomfilter als Array zu speichern, können wir seine Bitdarstellung in eine Dezimalzahl umwandeln.

Beispielsweise können wir ein Array mit 1001119 konvertieren und in einem Cache speichern.

Wenn sich die Liste nicht sehr oft ändert, kann der Server die Dezimalzahl an den Client senden, sodass die Validierung auf der Clientseite erfolgen kann.

Können wir es besser machen?

Wenn die Hash-Funktion den Index 1 sowohl für „Tiger“ als auch für „Kuh“ ausgibt, ergibt die Überprüfung, ob „Kuh“ in der Menge enthalten ist, die Antwort Ja , auch wenn dies nicht der Fall ist .

Wir können die Wahrscheinlichkeit von Fehlalarmen durch die folgenden Lösungen reduzieren.

• Erhöhen Sie die Länge des Arrays
• Erhöhen Sie die Anzahl der Hash-Funktionen

Anstelle eines Index können wir mehrere Indizes mit mehreren Hashes erhalten.

Beim Hinzufügen eines Elements werden alle erhaltenen Indizes auf 1 gesetzt.

Es wird nur dann behauptet, dass ein Element wahrscheinlich in der Menge enthalten ist, wenn ALLE Indizes auf 1 gesetzt sind.

Durch die Nutzung dieser Methoden konnten wir die Wahrscheinlichkeit von Fehlalarmen erheblich senken.

Anwendungen

Schauen wir uns einige Beispiele aus dem wirklichen Leben an.

Überprüfen Sie, ob ein Benutzername in einem Benutzerregistrierungsablauf vorhanden ist

• Wenn ein Benutzername erstellt wird, wird der Benutzername einem Bloom-Filter hinzugefügt, der in einem Schlüsselwertspeicher gespeichert ist.
• Wenn ein Benutzer einen Benutzernamen auf einer Benutzerregistrierungsseite eingibt, fragt der Server zuerst den Bloom-Filter ab.
• Wenn der Benutzername NICHT im Bloom-Filter enthalten ist, gibt der Server sofort einen Fehler an den Client zurück.
• Andernfalls führt der Server Abfragen und Gegenprüfungen in der Datenbank durch.

• Medium verwaltet einen Bloom-Filter für jeden Benutzer.
• Bevor ein Artikel empfohlen wird, prüft Medium, ob die Artikel-ID im Bloom-Filter des Benutzers vorhanden ist.
• Dem User werden Artikel empfohlen, die sicherlich NICHT im Bloomfilter sind.

• Beim Zugriff auf eine URL überprüft Chrome zunächst, ob die URL Teil einer bösartigen Liste ist.
• Anstatt den Google-Server jedes Mal abzufragen, baut Google einen Bloom-Filter mit einer vordefinierten Schadliste und sendet ihn an den Browser.
• Der Browser hasht die URL und vergleicht sie mit dem Bloom-Filter, bevor er auf die Website zugreift.

Es kann zwar zu Fehlalarmen kommen, aber ein Bloom-Filter ist praktisch, wenn wir feststellen möchten, ob ein Element definitiv nicht in einer Liste enthalten ist.

Es kann aufgrund seiner zeitlichen und räumlichen Effizienz als erste Filterschicht verwendet werden.

Ich hoffe, Sie finden das hilfreich, und wir sehen uns beim nächsten Mal!