Advertisement
  1. Code
  2. Redis

Wie man die Magie von Bloom-Filtern mit Node.js & Redis verstehen kann

by
Length:LongLanguages:

German (Deutsch) translation by Alex Grigorovich (you can also view the original English article)

Bei der richtigen Anwendung sind Bloom-Filter wie Magie. Das ist eine kühne Aussage, aber in diesem Tutorial werden wir uns in der merkwürdige Datenstruktur, ihrer besten Verwendung und einigen praktischen Beispielen mit Redis und Node.js auskennen.

Bloom-Filter sind eine Einweg-Datenstruktur. Das Wort "Filter" kann in diesem Zusammenhang verwirrend sein. Es bedeutet, dass es eine aktive Sache ist, ein Verb, aber es könnte einfacher sein, es als Speicher, als Substantiv zu betrachten. Mit einem einfachen Bloom-Filter können Sie zwei Dinge tun:

  1. Fügen Sie einen Artikel hinzu.
  2. Überprüfen Sie, ob zuvor noch kein Artikel hinzugefügt wurde.

Dies sind wichtige Einschränkungen, die Sie verstehen sollten: Sie können weder ein Element entfernen noch die Elemente in einem Bloom-Filter auflisten. Außerdem können Sie nicht mit Sicherheit feststellen, ob dem Filter in der Vergangenheit ein Element hinzugefügt wurde. Hier kommt die Wahrscheinlichkeit eines Bloom-Filters ins Spiel - falsch positive Ergebnisse sind möglich, falsch negative jedoch nicht. Wenn der Filter richtig eingerichtet ist, können Fehlalarme äußerst selten sein.

Es gibt Varianten von Bloom-Filtern, die andere Funktionen wie Entfernen oder Skalieren hinzufügen, aber auch Komplexität und Einschränkungen hinzufügen. Es ist wichtig, zunächst einfache Bloom-Filter zu verstehen, bevor Sie mit den Varianten fortfahren. Dieser Artikel behandelt nur die einfachen Bloom-Filter.

Mit diesen Einschränkungen haben Sie eine Reihe von Vorteilen: feste Größe, Hash-basierte Verschlüsselung und schnelle Suche.

Wenn Sie einen Bloom-Filter einrichten, geben Sie ihm eine Größe. Diese Größe ist festgelegt. Wenn Sie also ein Element oder eine Milliarde Elemente im Filter haben, wird diese niemals über die angegebene Größe hinaus wachsen. Wenn Sie Ihrem Filter weitere Elemente hinzufügen, steigt die Wahrscheinlichkeit eines falsch positiven Ergebnisses. Wenn Sie einen kleineren Filter angegeben haben, steigt diese Falsch-Positiv-Rate schneller an als bei einem größeren Filter.

Bloom-Filter basieren auf dem Konzept des One-Way-Hashing. Ähnlich wie beim korrekten Speichern von Kennwörtern verwenden Bloom-Filter einen Hash-Algorithmus, um eine eindeutige Kennung für die übergebenen Elemente zu ermitteln. Hashes können von Natur aus nicht rückgängig gemacht werden und werden durch eine scheinbar zufällige Zeichenfolge dargestellt. Wenn also jemand Zugriff auf einen Bloom-Filter erhält, wird keiner der Inhalte direkt angezeigt.

Schließlich sind Bloom-Filter schnell. Der Vorgang umfasst weitaus weniger Vergleiche als andere Methoden und kann problemlos im Speicher gespeichert werden, wodurch leistungsschädigende Datenbanktreffer verhindert werden.

Nachdem Sie die Grenzen und Vorteile von Bloom-Filtern kennen, lernen wir einige Situationen kennen, die Sie verwenden können.

Konfiguration

Wir werden Redis und Node.js verwenden, um Bloom-Filter zu veranschaulichen. Redis ist ein Speichermedium für Ihren Bloom-Filter. Es ist schnell, speicherintern und verfügt über einige spezifische Befehle (GETBIT, SETBIT), die die Implementierung effizient machen. Ich gehe davon aus, dass Sie Node.js, npm und Redis auf Ihrem System installiert haben. Ihr Redis-Server sollte auf localhost am Standardport ausgeführt werden, damit unsere Beispiele funktionieren.

In diesem Tutorial implementieren wir keinen Filter von Grund auf. Stattdessen konzentrieren wir uns auf praktische Anwendungen mit einem vorgefertigten Modul in npm: bloom-redis. bloom-redis verfügt über eine sehr präzise Reihe von Methoden: add, contains und clear.

Wie bereits erwähnt, benötigen Bloom-Filter einen Hashing-Algorithmus, um eindeutige Kennungen für ein Element zu generieren. bloom-redis verwendet den bekannten MD5-Algorithmus, der, obwohl er möglicherweise nicht perfekt für einen Bloom-Filter geeignet ist (ein wenig langsam, Overkill bei Bits), gut funktioniert.

Eindeutige Benutzernamen

Benutzernamen, insbesondere solche, die einen Benutzer in einer URL identifizieren, müssen eindeutig sein. Wenn Sie eine App erstellen, mit der Benutzer den Benutzernamen ändern können, möchten Sie wahrscheinlich einen Benutzernamen, der noch nie verwendet wurde, um Verwechslungen und das Löschen von Benutzernamen zu vermeiden.

Ohne einen Bloom-Filter müssen Sie auf eine Tabelle verweisen, in der jeder Benutzername jemals verwendet wurde. In der Größenordnung kann dies sehr teuer sein. Mit Bloom-Filtern können Sie jedes Mal ein Element hinzufügen, wenn ein Benutzer einen neuen Namen annimmt. Wenn ein Benutzer überprüft, ob ein Benutzername verwendet wird, müssen Sie lediglich den Bloom-Filter überprüfen. Sie können mit absoluter Sicherheit feststellen, ob der angeforderte Benutzername zuvor hinzugefügt wurde. Es ist möglich, dass der Filter falsch zurückgibt, dass ein Benutzername verwendet wurde, wenn dies nicht der Fall ist. Dies ist jedoch vorsichtig und kann keinen wirklichen Schaden anrichten (abgesehen davon, dass ein Benutzer möglicherweise nicht in der Lage ist, "k3w1d00d47" zu beanspruchen).

Um dies zu veranschaulichen, erstellen wir mit Express einen schnellen REST-Server. Erstellen Sie zuerst Ihre package.json-Datei und führen Sie dann die folgenden Terminalbefehle aus.

npm install bloom-redis --save

npm install express --save

npm installiere redis --save

Die Standardoptionen für Bloom-Redis haben eine Größe von zwei Megabyte. Dies ist zwar Vorsicht geboten, aber ziemlich groß. Das Einrichten der Größe des Bloom-Filters ist entscheidend: Zu groß und Sie verschwenden Speicher, zu klein und Ihre Falsch-Positiv-Rate ist zu hoch. Die MaThemetik zur Bestimmung der Größe ist ziemlich aufwendig und geht über den Rahmen dieses Tutorials hinaus. Zum Glück gibt es einen Bloom-Filter Größenrechner, mit dem Sie Ihre Arbeit erledigen können, ohne ein Lehrbuch zu knacken.

Erstellen Sie nun Ihre app.js :

So führen Sie diesen Server aus: node app.js. Gehen Sie zu Ihrem Browser und zeigen Sie auf: https://localhost:8010/check?username=kyle. Die Antwort sollte lauten: {"username":"kyle","status":"frei"}.

Speichern Sie nun diesen Benutzernamen, indem Sie Ihren Browser auf http://localhost:8010/save?username=kyle richten. Die Antwort lautet: {"username":"kyle","status":"created"}. Wenn Sie zur Adresse http://localhost:8010/check?username=kyle zurückkehren, lautet die Antwort {"username":"kyle","status":"used"}. Wenn Sie zu http://localhost:8010/save?username=kyle zurückkehren, erhalten Sie {"username":"kyle","status":"not-created"}.

Vom Terminal aus können Sie die Größe des Filters sehen: redis-cli strlen username-bloom-filter.

Im Moment sollte mit einem Element 338622 angezeigt werden.

Versuchen Sie nun, weitere Benutzernamen mit der Route /save hinzuzufügen. Probieren Sie so viele aus, wie Sie möchten.

Wenn Sie dann die Größe erneut überprüfen, stellen Sie möglicherweise fest, dass Ihre Größe leicht gestiegen ist, jedoch nicht bei jeder Hinzufügung. Neugierig, oder? Intern setzt ein Bloom-Filter einzelne Bits (1/0) an verschiedenen Positionen in der Zeichenfolge, die bei Benutzername-Bloom gespeichert wird. Diese sind jedoch nicht zusammenhängend. Wenn Sie also ein Bit auf Index 0 und dann eins auf Index 10.000 setzen, ist alles dazwischen 0. Für den praktischen Gebrauch ist es zunächst nicht wichtig, die genaue Mechanik jedes Vorgangs zu verstehen. Sie müssen lediglich wissen, dass dies normal ist und dass Ihr Speicher in Redis den von Ihnen angegebenen Wert niemals überschreitet.

Aufgefrischter Inhalt

Durch neue Inhalte auf einer Website kommt ein Benutzer immer wieder zurück. Wie können Sie einem Benutzer jedes Mal etwas Neues zeigen? Bei Verwendung eines herkömmlichen Datenbankansatzes können Sie einer Tabelle eine neue Zeile mit der Benutzerkennung und der Kennung der Story hinzufügen und diese Tabelle dann abfragen, wenn Sie sich entscheiden, einen Inhalt anzuzeigen. Wie Sie sich vorstellen können, wächst Ihre Datenbank extrem schnell, insbesondere mit dem Wachstum von Benutzern und Inhalten.

In diesem Fall hat ein falsches Negativ (z.B. kein unsichtbarer Inhalt angezeigt) nur sehr geringe Konsequenzen, was Bloom-Filter zu einer praktikablen Option macht. Auf den ersten Blick denken Sie vielleicht, dass Sie für jeden Benutzer einen Bloom-Filter benötigen. Wir verwenden jedoch eine einfache Verkettung der Benutzerkennung und der Inhaltskennung und fügen diese Zeichenfolge dann in unseren Filter ein. Auf diese Weise können wir einen einzigen Filter für alle Benutzer verwenden.

In diesem Beispiel erstellen wir einen weiteren einfachen Express-Server, auf dem Inhalte angezeigt werden. Jedes Mal, wenn Sie die Route /show-content/any-username besuchen (wobei any-username ein beliebiger URL-sicherer Wert ist), wird ein neuer Inhalt angezeigt, bis die Website keinen Inhalt mehr hat. Im Beispiel ist der Inhalt die erste Zeile der zehn besten Bücher zum Projekt Gutenberg.

Wir müssen ein weiteres npm-Modul installieren. Führen Sie auf dem Terminal Folgendes aus: npm install async --save

Ihre neue app.js-Datei:

Wenn Sie in Dev Werkzeugs sorgfältig auf die Umlaufzeit achten, werden Sie feststellen, dass es umso länger dauert, je mehr Sie einen einzelnen Pfad mit einem Benutzernamen anfordern. Während die Überprüfung des Filters eine feste Zeit in Anspruch nimmt, prüfen wir in diesem Beispiel, ob weitere Elemente vorhanden sind. Bloom-Filter sind in ihren Informationen begrenzt, sodass Sie prüfen, ob die einzelnen Elemente vorhanden sind. In unserem Beispiel ist es natürlich ziemlich einfach, aber das Testen auf Hunderte von Elementen wäre ineffizient.

Verbrauchte Daten

In diesem Beispiel erstellen wir einen kleinen Express-Server, der zwei Aufgaben ausführt: Akzeptieren neuer Daten per POST und Anzeigen der aktuellen Daten (mit einer GET-Anforderung). Wenn die neuen Daten an den Server gesendet werden, überprüft die App, ob sie im Filter vorhanden sind. Wenn es nicht vorhanden ist, fügen wir es einem Satz in Redis hinzu, andernfalls geben wir null zurück. Die GET-Anforderung ruft es von Redis ab und sendet es an den Client.

Dies unterscheidet sich von den beiden vorherigen Situationen darin, dass Fehlalarme nicht in Ordnung wären. Wir werden den Bloom-Filter als erste Verteidigungslinie verwenden. Angesichts der Eigenschaften von Bloom-Filtern wissen wir nur mit Sicherheit, dass sich etwas nicht im Filter befindet. In diesem Fall können wir also die Daten einlassen. Wenn der Bloom-Filter zurückgibt, der sich wahrscheinlich im Filter befindet, überprüfen wir die tatsächliche Datenquelle.

Was gewinnen wir also? Wir gewinnen die Geschwindigkeit, nicht jedes Mal gegen die tatsächliche Quelle prüfen zu müssen. In Situationen, in denen die Datenquelle langsam ist (externe APIs, Pokey-Datenbanken, die Mitte einer Flatfile), ist die Geschwindigkeitssteigerung wirklich erforderlich. Um die Geschwindigkeit zu demonstrieren, fügen wir in unserem Beispiel eine realistische Verzögerung von 150 ms hinzu. Wir werden auch console.time / console.time End verwenden, um die Unterschiede zwischen einer Bloom-Filterprüfung und einer Nicht-Bloom-Filterprüfung zu protokollieren.

In diesem Beispiel verwenden wir auch eine extrem eingeschränkte Anzahl von Bits: nur 1024. Sie füllt sich schnell. Beim Füllen werden immer mehr Fehlalarme angezeigt. Die Antwortzeit erhöht sich, wenn sich die Falsch-Positiv-Rate füllt.

Dieser Server verwendet dieselben Module wie zuvor. Setzen Sie die Datei app.js daher auf:

Da das POSTing auf einem Server mit einem Browser schwierig sein kann, verwenden wir zum Testen curl.

curl --data “your data goes here" --header "Content-Type: text/plain" http://localhost:8012/

Ein schnelles Bash-Skript kann verwendet werden, um zu zeigen, wie das Ausfüllen des gesamten Filters aussieht:

Es ist interessant, eine Füllung oder einen Vollfilter zu betrachten. Da dieser klein ist, können Sie ihn einfach mit redis-cli anzeigen. Wenn Sie redis-cli get stale-filter ausführen, um zwischen dem Hinzufügen von Elementen einen veralteten Filter vom Terminal zu erhalten, werden die einzelnen Bytes erhöht. Ein vollständiger Filter ist \xff für jedes Byte. Zu diesem Zeitpunkt gibt der Filter immer positiv zurück.

Abschluss

Bloom-Filter sind kein Allheilmittel, aber in der richtigen Situation kann ein Bloom-Filter eine schnelle und effiziente Ergänzung zu anderen Datenstrukturen darstellen.

Advertisement
Advertisement
Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.