Was ist ein Bloom-Filter?

Bloom-Filter sind eine Informationsanalysefunktion. Dadurch können wir feststellen, ob ein Daten oder Datensatz in einer Datenbank oder einem verteilten Datensatz gespeichert ist. Sein Hauptmerkmal ist seine extreme Effizienz bei dieser Aufgabe. Aufgrund dieser Eigenschaften werden sie häufig in Systemen verwendet, in denen die Existenz bestimmter Daten innerhalb einer großen Datenmenge überprüft werden muss.

UEines der nützlichsten Werkzeuge zur Analyse probabilistischer und unidirektionaler Informationen sind Bloom-Filter. Diese Blütenfilter sind Werkzeuge oder Instrumente, die es uns erleichtern, große Mengen probabilistischer Informationen zu analysieren. Dies dient dazu, festzustellen, ob ein Element oder Daten Teil einer Menge sind. Dies ist eine Funktion, die in Zeiten, in denen wir große Datenmengen verarbeiten müssen, äußerst nützlich ist. Vor allem, wenn diese Informationen manuell nicht schnell verarbeitet werden können.

Deshalb können dank Bloom-Filtern Kryptowährungen wie z.B Bitcoin die Funktion haben SPV-Geldbörsen. Aber wir sehen diese Funktion auch in Kryptowährungen wie Ethereum wo Sie nach Informationen in Ihrem suchen können Blockchain effizient.

Und das ist der Tatsache zu verdanken, dass Bloom-Filter uns nur zwei Ergebnisse ermöglichen: falsch positive oder negative Ergebnisse. Das heißt, durch die Implementierung von Bloom-Filtern können Sie schnell und effizient erkennen, ob bestimmte Elemente möglicherweise im Speicher vorhanden sind oder ob sie definitiv nicht vorhanden sind. Falsch positive Ergebnisse weisen auf die Möglichkeit hin, dass ein Element oder Daten Teil einer Menge sein könnten. Negative Ergebnisse hingegen deuten definitiv darauf hin, dass das Element oder die Daten nicht im ausgewerteten Satz enthalten sind. Gleichzeitig ermöglicht uns das Tool, falsch-negative Ergebnisse vollständig auszuschließen, was die Datenanalyse erheblich erleichtert.

Aber was führte zur Entwicklung von Bloom-Filtern? Welche Beziehung haben sie zur Welt der Blockchain? Nun, das werden wir weiter unten sehen.

Das Design dieser Bloom-Filter ermöglicht es uns daher, große Datenbanken oder Informationen mit hoher Geschwindigkeit zu verarbeiten. Gleichzeitig wird der Lagerraum effizient genutzt. Dies liegt daran, dass Bloom-Filter nicht erfordern, dass die Elemente oder Daten selbst enthalten oder gespeichert werden, sondern lediglich überprüft wird, ob sie innerhalb des Satzes enthalten sind oder nicht. Ein schreibgeschützter Datenvorgang, der hohe Leistung und Informationsverarbeitungsfunktionen ermöglicht.

Wie werden Bloom-Filter konfiguriert?

Bloom-Filter verfügen über eine sogenannte Bloom-Datenstruktur. Eingabearray. Die Länge bzw. Speicherkapazität dieses Arrays ist so groß wie nötig. Das bedeutet, dass Beim Bau eines Bloom-Filters können Sie festlegen, wie groß die Länge des Filters sein soll., nach Bedarf. Definieren, wie viele Einträge zur Basisdatenstruktur hinzugefügt werden und wie viele Hash-Funktionen Sie werden innerhalb des Filters verwendet und verknüpfen sich mit jedem dieser Einträge.

Ebenso muss bei der Gestaltung darauf geachtet werden Der Bereich der Hash-Funktionen muss bei 0 beginnen und bei der Anzahl der vorhandenen Einträge minus 1 enden. Das heißt, wenn ein Bloom-Filter für 10 Einträge ausgelegt ist, beginnt er mit der Zahl 0 und endet bei der Zahl 9. Wenn einer für 20 Einträge ausgelegt ist, beginnt der Bloom-Filter bei der Zahl 0 und endet bei der Zahl 19 Nummer XNUMX. Eine rechnergestützte Entwurfspraxis, die darauf abzielt, die Filterverarbeitungsressourcen zu maximieren.

Wenn in der Menge der vorhandenen Einträge alle Werte 0 sind, bedeutet dies ebenfalls, dass sich die Daten nicht im Bloom-Filter befinden. Es ist also leer. Sobald Sie also beginnen, Daten oder Elemente zum Filter hinzuzufügen, werden die Informationen durch die entsprechenden Hash-Funktionen geleitet, die diese Informationen an der entsprechenden Stelle im Bloom-Filter platzieren. Daher weisen diese Standorte den Wert 1 auf, was darauf hinweist, dass sie bereits analysierte Elemente enthalten.

Aus diesen Werten baut sich die Funktionsweise der Bloomfilter auf, die wir im Folgenden im Detail erläutern.

Betrieb der Bloom-Filter

Sobald der Bloom-Filter festgelegt wurde, können wir mit der Prüfung beginnen, ob ein Element Teil des Satzes ist oder nicht. Um dies zu erreichen, beginnt der folgende Prozess mit der Übergabe der gewünschten Dateneingabe an den Bloom-Filter-Algorithmus. Das heißt, wir nehmen die Daten aus dem System und verarbeiten sie mithilfe der Hash-Funktionen des Systems. Diese Hash-Funktionen geben als Ergebnis zwei Positionen zurück.

Diese Hashes und die Positionen, die sie als Ergebnis zurückgeben, werden gespeichert und mit den Daten verknüpft, die ihnen ihren Ursprung geben. Somit sammelt der Filter weiterhin Informationen, wendet Hash-Funktionen auf sie an und speichert die Ergebnisse seiner Operation. Dieser Prozess verfügt jedoch über ein zusätzliches Verfahren, das seine Effizienz maximiert und die Reaktionszeit der Systeme verbessert, die diese Art von Filtern auf ihre Strukturen anwenden.

Wenn die an den Filter übergebenen Daten die Hash-Funktionen durchlaufen und Positionen mit anderen Werten als 0 zurückgeben, befindet sich das Element zunächst innerhalb der Menge. Dies wird als positiv bezeichnet und zeigt die Existenz dieses Elements in der Menge an. Es kann auch vorkommen, dass Hashes Ergebnisse mit unterschiedlichen Werten zurückgeben.

Wenn hingegen eine oder beide Positionen den Wert 0 aufweisen, liegt das Element definitiv nicht in der Menge. Eine andere vom Algorithmus vorhergesehene Situation, die als negativ oder falsch positiv bezeichnet wird. Dieses Ergebnis ist endgültig oder schlüssig, da Bloom-Filter niemals zu falsch negativen Ergebnissen führen. Das heißt, wenn der Algorithmus eines Bloom-Filters ein Negativ oder ein Falsch-Positiv erkennt, ist diese Information definitiv nicht im analysierten Datensatz enthalten.

Andererseits ist es bei der Konfiguration eines Bloom-Filters von großer Bedeutung, die Anzahl der anzuwendenden Bits und Hash-Funktionen zu definieren. Nun, je größer die Anzahl der Hash-Funktionen ist, desto geringer ist die Fehlerrate, sodass die Wahrscheinlichkeit falsch positiver Ergebnisse geringer ist. Ebenso können die eingegebenen Daten nicht mehr gelöscht werden, sobald der Bloom-Filter-Bitsatz vollständig gefüllt ist. Dies geschieht, um zu verhindern, dass falsch negative Ergebnisse im Filter angezeigt werden.

Wie wichtig sind falsch positive und negative Ergebnisse bei Bloom-Filtern?

Die Bedeutung falsch positiver und negativer Zustände von Bloom-Filtern liegt in der Effizienz. Wie bereits erwähnt, sind Bloom-Filter so programmiert, dass sie beide Zustände berücksichtigen. Und wenn sie dennoch auftreten, können wir die entsprechenden Maßnahmen ergreifen, um angemessen zu reagieren.

Wenn wir beispielsweise mit einem Datenspeichersystem arbeiten, um einen Cache zu generieren, ist ein Bloom-Filter für uns eine große Hilfe. Dies liegt daran, dass wir jedes Mal, wenn das System Daten empfängt, überprüfen müssen, ob diese Daten nicht in den Daten enthalten sind, die wir im Cache gespeichert haben. Wenn wir also diese Daten eingeben und der Bloom-Filter ein negatives oder falsch positives Ergebnis zurückgibt, können wir sicher sein, dass diese Daten nicht zu den von uns verarbeiteten Informationen gehören. Und dann können wir diese neuen Daten im Cache speichern, damit wir später schnell und effizient darauf zugreifen können.

Wenn der Bloom-Filter hingegen ein positives Ergebnis liefert, können wir die Speicherung der Informationen einfach verwerfen und mit dem arbeiten, was wir im Cache haben, was einen besseren Zugriff auf die Informationen ermöglicht und dadurch wertvolle Rechenressourcen spart.

Diese Art von Vorgang ist für die Software, die wir täglich verwenden, nicht fremd. Beispielsweise nutzen Webbrowser den auf unseren Festplatten gespeicherten Cache-Speicher, um uns im Vergleich zur Online-Abfrage dieser Daten einen schnellen Zugriff auf bestimmte Ressourcen zu ermöglichen. Serverdatenbanken und andere Systeme, die riesige Datenmengen verarbeiten, verwenden ebenfalls Bloom-Filter oder ähnliche Algorithmen, um die Effizienz ihrer Antworten und Datenverarbeitung zu verbessern.

Hash-Funktionen innerhalb von Bloom-Filtern

Bei der Konfiguration eines Bloom-Filters müssen unabhängige und gleichmäßig verteilte Hash-Funktionen verwendet werden. Mit diesen Hash-Funktionen können Sie jedem Datentyp einen Bezeichner zuweisen, der zum Indizieren oder Vergleichen dieser Daten innerhalb eines Satzes verwendet werden kann.

Wenn wir über Hash-Funktionen sprechen, sprechen wir über die bekannten Funktionen SHA-256, MD5 oder andere Funktionen wie CRC32. Allerdings muss man bei Bloomfiltern vorsichtig sein. Die Verwendung vieler Hash-Funktionen erhöht die Sicherheit, macht sie aber auch komplexer und langsamer. Daher müssen die Funktionen so ausgewählt werden, dass ihre Fähigkeiten voll ausgeschöpft werden.

Die unidirektionale Eigenschaft von Hash-Funktionen ermöglicht es ihrerseits, aus einem Element oder Daten einen Bezeichner zu ermitteln bzw. zu erstellen, der umgekehrte Vorgang ist jedoch nicht möglich. Wenn ein Benutzer also eine Kennung entdeckt, kann er nicht wissen, um welche Daten oder Elemente es sich handelt.

Vor- und Nachteile der Verwendung von Bloom-Filtern

Vorteil

• Bloom-Filter, indem sie einen Datensatz nicht als solchen speichern, Sie sind hinsichtlich der Nutzung des Lagerraums effizienter. Denn sie speichern nur, ob eine Information oder ein Element innerhalb des Bloom-Filters existiert oder nicht.
• Ebenso ermöglicht diese Funktion Die Überprüfung von Daten oder Elementen kann wesentlich schneller und effizienter durchgeführt werden. Allerdings muss auch berücksichtigt werden, dass je größer die Anzahl der Hash-Funktionen ist, desto größer ist die Zeit, die der Bloom-Filter benötigt, um die Existenz der Elemente oder Daten zu überprüfen.
• als Bloom-Filter nutzen das Konzept des Einweg-Hashings. Wenn ein Benutzer Zugriff darauf erhält, kann er die in diesen Filtern enthaltenen Informationen nicht direkt einsehen.

Nachteile

• Diese Werkzeuge Sie geben die Daten nicht zurück verifiziert. Stattdessen ermöglichen sie Ihnen lediglich die Überprüfung, ob sie möglicherweise existieren oder nicht.
• Wenn Sie positive Ergebnisse haben, können Sie nur davon ausgehen, dass diese wahrscheinlich richtig sind. Man kann nicht sicher oder völlig sicher sein, dass die positiven Daten Teil der Menge sind. Im Gegensatz zu dem, was bei negativen Ergebnissen passiert. Wo Sie eine Antwort oder ein endgültiges entscheidendes Ergebnis erhalten können.
• Beim Entwurf des Bloom-Filters muss ihm eine Größe zugewiesen werden, unabhängig davon, ob es sich um einige Bits oder Millionen Bits handelt. Sobald eine Größe festgelegt ist, schrumpft oder wächst sie nicht stärker als zuvor festgelegt. Damit der Bloom-Filter effizient ist, ist es daher notwendig, im Voraus zu definieren oder klar zu sein, wie viele Daten hinzugefügt werden. Wenn diese Informationen nicht bekannt sind, ist es daher wahrscheinlich, dass ein Bloom-Filter mit sehr wenigen Elementen entworfen wird, die bei der Verwaltung der gewünschten Informationen nicht so effektiv sind. Oder es kann der Fall eintreten, dass ein sehr großer Bloom-Filter entworfen wird, der einen sehr großen Speicherplatz für die kleine zu verwaltende Informationsmenge erfordert. Was zu Platzverschwendung führen würde.

Anwendungsfälle für Bloom-Filter

Kryptowährungen: Bitcoin und Ethereum

Das Bitcoin-System verwendet Bloom-Filter für Beschleunigen Sie die Synchronisierung von SPV-Wallets oder Geldbörsen; Dadurch können sie nur die Transaktionen angeben, für die sie Systemaktualisierungen erhalten möchten. Bilden einer Reihe von Transaktionen, die an die gesamten Netzwerkknoten übertragen werden können. Dort können Sie über diese Filter überprüfen. Anschließend erhalten Sie eine Bestätigung darüber, ob dieser Satz von Transaktionen zur Kette hinzugefügt wurde oder nicht. Ohne die Notwendigkeit, eine vollständige Kopie der Blockchain zu verwalten. In Bitcoin wird diese Funktionalität durch den im erwähnten Compact Block geändert BIP-158.

Das Ethereum-Netzwerk nutzt seinerseits Bloom-Filter Mechanismus, mit dem Sie Protokolle in Ihrer Blockchain finden können. Durch die Implementierung dieser Filter können Sie daher problemlos nach Ereignissen suchen, die im Ethereum-System aufgetreten sind. Ohne es durch den Umgang mit übermäßig vielen Informationen zu überlasten. Dadurch können Anwendungen diese Informationen wesentlich effizienter verwalten. Gleichzeitig ist kein großer Speicherplatzbedarf erforderlich. Denn bei Bloom-Filtern besteht keine Notwendigkeit, Daten zu speichern, die innerhalb des Systems dupliziert werden könnten.

Wenn in Ethereum ein Block generiert und überprüft wird, werden die Vertragsadresse und die indizierten Felder der Datensätze einem Bloom-Filter hinzugefügt. Dieser Filter befindet sich im Blockheader. Wenn eine Anwendung also alle Registrierungseinträge finden möchte, muss der Knoten nur den Header scannen. So können Sie erkennen, ob die benötigten Daten vorhanden sind oder nicht. Daher werden diese Elemente nicht als solche zum Block hinzugefügt, um Speicherplatz zu sparen.

Netzwerke und Informationskanäle

Eine weitere wichtige Implementierung von Bloom-Filtern ermöglicht es Netzwerken oder Informationskanälen, den Benutzern Artikelempfehlungen zu geben. Damit sich diese nicht wiederholen. Das heißt, Sie können sehen, welche Artikel ein Benutzer gelesen hat, um diejenigen zu empfehlen, die er noch nicht gesehen hat.

Ebenso nutzen große Daten- und Content-Distributionszentren (CDN) Bloom-Filter, um die Effizienz der Datenspeicherung und Netzwerknutzung zu maximieren und zu verhindern, dass wiederholte oder selten genutzte Elemente Teil ihrer Systeme werden und diese überlasten. Dazu gehören Unternehmen wie Akamai, Namecheap CDN, Fastly oder Cloudflare.