Bloom-Filter

Ein Bloom-Filter ist eine platzsparende, probabilistische Datenstruktur, mit der Sie prüfen können, ob ein Element zu einem Set gehört. Bei dieser Art von Struktur kann es zu Falsch-Positiv-Ergebnissen kommen. Der Filter kann beispielsweise angeben, dass sich ein Element in der Menge befindet, obwohl das nicht der Fall ist. Falsch negative Ergebnisse sind jedoch nicht zulässig. Wenn Sie also ein Element der Menge hinzufügen, muss der Filter angeben, dass das Element in der Menge enthalten ist.

Dazu werden mehrere Hash-Funktionen verwendet, um ein Element mehreren Bits in einem Bit-Array mit fester Größe zuzuordnen. Um die Wahrscheinlichkeit von Falsch-Positiv-Ergebnissen zu steuern, können Sie die Anzahl der Bits im Array und die Anzahl der verwendeten Hash-Funktionen anpassen.

Anwendungsfälle

In diesem Abschnitt werden die folgenden Anwendungsfälle für die Verwendung von Bloom-Filtern beschrieben:

Anzeigen und Ereignisse deduplizieren: Wenn Sie eine E-Commerce-Website, einen Streamingdienst, ein Werbenetzwerk oder eine Marketingplattform haben, können Sie mit Bloom-Filtern ermitteln, ob ein Nutzer eine Anzeige gesehen, eine Werbe-E-Mail oder ‑Benachrichtigung erhalten oder ein Produkt gekauft hat.

Mit einem Bloom-Filter können Sie alle Produkte speichern, die ein Nutzer kauft.
- Wenn ein Produkt nicht im Filter enthalten ist, zeigen Sie die Anzeige dem Nutzer und fügen Sie das Produkt dem Filter hinzu.
- Wenn das Produkt im Filter enthalten ist, hat der Nutzer wahrscheinlich die zugehörige Anzeige gesehen und das Produkt gekauft. Daher wird dem Nutzer eine andere Anzeige präsentiert.
Betrug erkennen: Mit Bloom-Filtern lässt sich erkennen, ob eine Kreditkarte als gestohlen gemeldet wurde. Verwenden Sie dazu einen Filter, der als gestohlen gemeldete Karten enthält. Wenn eine Karte verwendet wird, prüfen Sie, ob sie im Filter angezeigt wird.
- Wenn die Karte nicht im Filter enthalten ist, wird sie nicht als gestohlen markiert.
- Wenn die Karte im Filter ist, können Sie sie mit der Hauptdatenbank abgleichen oder den Kauf ablehnen.
Spam und schädliche Inhalte filtern: Sie können Bloom-Filter verwenden, um Inhalte auf potenzielle Bedrohungen, schädliche Materialien und Spam zu prüfen. Erstellen Sie dazu einen Filter, der schädliche URLs, Spam-E‑Mail-Adressen und Spam-Telefonnummern enthält. Wenn der Nutzer eine URL eingibt oder eine E‑Mail oder SMS erhält, prüfen Sie, ob diese Informationen im Filter angezeigt werden.
- Wenn die URL, E‑Mail-Adresse oder der Text nicht im Filter enthalten ist, erlauben Sie dem Nutzer den Zugriff auf die Website, die durch die URL repräsentiert wird, oder den Empfang der E‑Mail oder des Texts.
- Wenn die URL, E‑Mail-Adresse oder der Text im Filter enthalten ist, verweigern Sie dem Nutzer den Zugriff auf die zugehörige Website oder verhindern Sie, dass der Nutzer die E‑Mail oder SMS erhält.
Doppelte Nutzernamen erkennen: Mit Bloom-Filtern können Sie feststellen, ob ein Nutzername neu ist oder bereits vorhanden ist. Verwenden Sie dazu einen Filter, um jeden Nutzernamen zu erfassen, der sich für Ihre E-Commerce-Website oder Ihren Streamingdienst registriert. Wenn ein neuer Nutzer versucht, sich mit seinem Nutzernamen zu registrieren, prüfen Sie, ob der Nutzername im Filter angezeigt wird.
- Wenn der Nutzername nicht im Filter enthalten ist, erstellen Sie das Konto und fügen Sie den Nutzernamen dem Filter hinzu.
- Wenn der Nutzername im Filter enthalten ist, lehnen Sie ihn ab.

Weitere Informationen zu diesen Anwendungsfällen finden Sie unter Häufige Anwendungsfälle für Bloom-Filter.

Verfügbarkeit

Wenn Sie eine Memorystore for Valkey-Instanz der Version 8.0 oder höher erstellen, ist Version 1.0 des Bloom-Datentyps und der zugehörigen Befehle automatisch verfügbar. Dieser Datentyp ist API-kompatibel mit der Bloom-Filter-Befehlssyntax der folgenden Valkey-Clientbibliotheken:

Bloom-Filtertypen

Es gibt die folgenden Arten von Bloom-Filtern:

Skalierung: Dieser Filtertyp hat keine feste Kapazität, sodass der Filter wachsen kann. Wenn der Filter seine Kapazität erreicht und Sie ihm ein neues, eindeutiges Element hinzufügen, wird er skaliert und ein neuer Unterfilter wird erstellt. Dieser Unterfilter hat eine größere Kapazität als der Filter.
Nicht skalierbar: Dieser Filtertyp hat eine feste Kapazität. Es gibt also eine Begrenzung für die Anzahl der Elemente, die Sie dem Filter hinzufügen können. Wenn der Filter seine Kapazität erreicht und Sie versuchen, ein neues, eindeutiges Element hinzuzufügen, wird eine Fehlermeldung angezeigt.

Weitere Informationen zu den Unterschieden zwischen diesen Arten von Bloom-Filtern finden Sie unter Skalierbare und nicht skalierbare Bloom-Filter.

Bloom-Filtereigenschaften

Ein Bloom-Filter hat die folgenden Eigenschaften:

Kapazität: Die Anzahl der Elemente, die ein Bloom-Filter aufnehmen kann, bevor er entweder skaliert wird (bei einem skalierbaren Filter) oder das Hinzufügen weiterer Elemente ablehnt (bei einem nicht skalierbaren Filter).
Rate falsch positiver Ergebnisse: Die Rate, die die Wahrscheinlichkeit von Operationen für Bloom-Filter steuert, die zu falsch positiven Ergebnissen führen. Wenn Sie beispielsweise einen Vorgang verwenden, um zu prüfen, ob sich ein Element im Filter befindet, wird angegeben, dass sich das Element im Filter befindet, obwohl dies nicht der Fall ist.
Erweiterung: Diese Eigenschaft ist mit der Skalierung von Bloom-Filtern verknüpft. Damit wird das Wachstum der Gesamtkapazität gesteuert, wenn der Filter skaliert wird, weil er seine Kapazität erreicht.
Skalierung oder keine Skalierung: Gibt an, ob es sich bei einem Bloom-Filter um einen Filter mit oder ohne Skalierung handelt.

Weitere Informationen zu den Eigenschaften von Bloom-Filtern finden Sie unter Bloom-Eigenschaften.

Bloom-Filterobjekte

Ein Bloom-Filter-Objekt kann maximal 128 MB Arbeitsspeicher belegen. Um zu prüfen, wie viel Speicher ein Bloom-Filter belegt, verwenden Sie den Befehl BF.INFO key SIZE. Dabei ist key der Schlüsselname für den Filter und SIZE die Anzahl der Bytes, die der Filter belegt.

Bloom-Kategorien

Verwenden Sie die Kategorie @bloom, um den Zugriff auf Bloom-Befehle und Daten zu verwalten. Neben dieser Kategorie werden Bloom-Befehle auch in den folgenden Kategorien verwendet: @read, @write und @fast.

In der folgenden Tabelle sehen Sie, ob Sie Bloom-Befehle den Kategorien @read, @write, @fast und @bloom zuordnen können.

Bloom-Befehl	`@bloom`	`@read`	`@write`	`@fast`
`BF.ADD`	J	N	J	J
`BF.CARD`	J	J	N	J
`BF.EXISTS`	J	J	N	J
`BF.INFO`	J	J	N	J
`BF.INSERT`	J	N	J	J
`BF.MADD`	J	N	J	J
`BF.MEXISTS`	J	J	N	J
`BF.RESERVE`	J	J	N	J

Bloom-Befehle

In diesem Abschnitt werden die Bloom-Befehle aufgeführt und beschrieben, mit denen Sie Bloom-Vorgänge für den Bloom-Datentyp ausführen können.

Befehl	Beschreibung
`BF.ADD`	Ein einzelnes Element einem Bloom-Filter hinzufügen Wenn der Filter nicht vorhanden ist, wird er durch den Befehl erstellt.
`BF.CARD`	Gibt die Kardinalität eines Bloom-Filters zurück.
`BF.EXISTS`	Ermittelt, ob ein Bloom-Filter das angegebene Element enthält.
`BF.INFO`	Gibt Nutzungsinformationen und Eigenschaften eines Bloom-Filters zurück.
`BF.INSERT`	Erstellen Sie einen Bloom-Filter mit null oder mehr Elementen oder fügen Sie einem vorhandenen Filter Elemente hinzu.
`BF.MADD`	Fügen Sie einem Bloom-Filter ein oder mehrere Elemente hinzu. Wenn der Filter nicht vorhanden ist, wird er mit dem Befehl erstellt.
`BF.MEXISTS`	Ermitteln, ob der Bloom-Filter ein oder mehrere Elemente enthält.
`BF.RESERVE`	Erstellt einen leeren Bloom-Filter mit den von Ihnen angegebenen Attributen.

Bloom-Filter prüfen

Sie können die folgenden Informationen zu Bloom-Filtern prüfen:

Arbeitsspeichernutzung: Prüfen Sie, ob ein Filter das Limit für die Arbeitsspeichernutzung erreicht. Mit dem Befehl BF.INFO können Sie prüfen, wie viel Arbeitsspeicher ein Filter verwendet.
Kapazität: Prüfen Sie, ob ein Filter ein Skalierungsfilter ist. Wenn ja, skalieren Sie den Filter so, dass er seine Kapazität erreicht, und führen Sie dann eine horizontale Skalierung durch.

Weitere Informationen zum Prüfen der Speichernutzung und ‑kapazität für Bloom-Filter finden Sie unter Große Bloom-Filter verarbeiten.