Implementierung von Bloom-Filtern in Go für effizientes Caching

In Cache-Designs stoßen wir oft auf ein lästiges Problem: Eine große Anzahl von „ungültigen Abfragen“ übt enormen Druck auf die Datenbank aus. Wenn ein Benutzer beispielsweise Daten anfordert, die nicht existieren, fragen wir in der Regel die Datenbank ab, die „nicht gefunden“ zurückgibt. Wenn es viele solcher Anfragen gibt, ist die Datenbank damit beschäftigt, diese bedeutungslosen Abfragen zu verarbeiten, was die Systemleistung beeinträchtigt. Gibt es also eine Möglichkeit, im Voraus zu wissen, ob Daten „existieren könnten“, bevor eine Abfrage durchgeführt wird? Hier kommen Bloom-Filter ins Spiel.

Probleme in traditionellen Cache-Szenarien

Stellen Sie sich folgendes Szenario vor:

• Unser System hat eine Cache-Schicht (Redis) und eine Datenbankschicht (MySQL).
• Wenn ein Benutzer Daten anfordert, prüfen wir zuerst den Cache. Wenn es ein Cache-Treffer ist, geben wir das Ergebnis direkt zurück.
• Wenn sich die Daten nicht im Cache befinden, fragen wir die Datenbank ab. Wenn die Datenbank sie auch nicht hat, geben wir dem Benutzer „nicht gefunden“ zurück.

Auf den ersten Blick scheint dieses Design vernünftig. In der Praxis kann es jedoch vorkommen, dass eine große Anzahl ungültiger Abfragen auftritt:

Benutzer fordert Daten mit ID=99999999 an
    -> Nicht im Cache gefunden
    -> Datenbank für ID=99999999 abfragen
    -> Datenbank gibt zurück: nicht gefunden

Wenn Benutzer wiederholt Daten anfordern, die einfach nicht existieren, erhalten Sie:

• Cache funktioniert nicht: Jede Anfrage fragt die Datenbank ab, wodurch die Cache-Schicht sinnlos wird.
• Übermäßige Datenbanklast: Zahlreiche ungültige Anfragen verlangsamen die Datenbankantwort.

Eine gängige Optimierung besteht darin, ungültige Abfragen im Voraus herauszufiltern, sodass Daten, von denen wir bereits wissen, dass sie nicht existieren, sofort zurückgegeben werden, ohne die Datenbank abzufragen. Genau hier glänzen Bloom-Filter.

Was ist ein Bloom-Filter?

Ein Bloom-Filter ist ein effizienter Algorithmus zur Abfrage der Mengenmitgliedschaft. Er kann schnell feststellen, ob ein Wert existieren könnte oder definitiv nicht existiert. Einfach ausgedrückt:

• Wenn der Bloom-Filter Ihnen sagt, dass etwas „nicht existiert“, dann existiert es wirklich nicht, und Sie können sofort einen Fehler zurückgeben – Sie müssen die Datenbank nicht abfragen.
• Wenn der Bloom-Filter Ihnen sagt, dass etwas „existieren könnte“, dann fragen Sie die Datenbank zur Bestätigung ab.

Die zugrunde liegende Logik eines Bloom-Filters ist einfach:

• Verwenden Sie mehrere Hash-Funktionen, um Daten in ein Bit-Array fester Größe abzubilden.
• Berechnen Sie bei der Abfrage die gleichen Hashes für die Zieldaten und prüfen Sie, ob alle entsprechenden Bits auf 1 gesetzt sind.
• Wenn eines dieser Bits 0 ist, existieren die Daten definitiv nicht.
• Wenn alle Bits 1 sind, existieren die Daten möglicherweise (mit einer gewissen Falsch-Positiv-Rate).

Vorteile:

• Spart Speicherplatz – belegt weniger Speicherplatz als eine herkömmliche Hash-Tabelle.
• Schnelle Abfragen – Zeitkomplexität nahezu O(1).
• Effiziente Filterung – reduziert die Datenbanklast.

Nachteile:

• Mögliche falsch positive Ergebnisse (die Falsch-Positiv-Rate kann jedoch durch Anpassen der Anzahl der Hash-Funktionen reduziert werden).
• Daten können nicht gelöscht werden (wird im Allgemeinen für Big-Data-Streams oder Cache-Szenarien verwendet).

Die Datenstruktur eines Bloom-Filters

Die Kerndatenstrukturen eines Bloom-Filters bestehen aus zwei Komponenten:

• Bit-Array: Wird verwendet, um aufzuzeichnen, ob ein bestimmter Wert existiert; alle Bits werden mit 0 initialisiert.
• Mehrere Hash-Funktionen: Werden verwendet, um die Bitpositionen zu berechnen, die den Daten entsprechen.

Beispiel:

Fügen Sie „Leap“ ein; nach Hash-Berechnungen wird es den Positionen 2, 5, 8 und 9 im Bit-Array zugeordnet:
Index:   0  1  2  3  4  5  6  7  8  9
Wert:   0  0  1  0  0  1  0  0  1  1

Bei der Abfrage von „Leap“:

• Berechnen Sie die Hashes für „Leap“ und stellen Sie fest, dass die Positionen 2, 5, 8 und 9 alle 1 sind, was anzeigt, dass es existieren könnte.
• Berechnen Sie die Hashes für „cell“ und stellen Sie fest, dass einige Bits 0 sind, sodass es sofort als „nicht vorhanden“ zurückgegeben wird.

Implementierung eines Bloom-Filters in Go

Im Folgenden finden Sie eine Bloom-Filter-Implementierung mit Go:

• Die BloomFilter-Struktur.
• Der Konstruktor NewBloomFilter, der automatisch die optimale Bit-Array-Größe (m) und die Anzahl der Hash-Funktionen (k) basierend auf der erwarteten Anzahl von Elementen und der akzeptablen Falsch-Positiv-Rate berechnet.
• Der Konstruktor NewBloomFilterWithMK, mit dem Sie m und k direkt angeben können.
• Die Add-Methode zum Hinzufügen von Elementen.
• Die MightContain-Methode zum Überprüfen, ob ein Element vorhanden sein könnte (es kann falsch positive Ergebnisse geben, aber niemals falsch negative).
• Die interne getHashes-Methode, die Double Hashing verwendet, um k Hash-Werte zu generieren. Hier verwenden wir zwei Varianten des FNV-1a-Hash-Algorithmus als Basis-Hashes.

Bloom-Filter-Struktur

package main

import (
  "fmt"
  "hash/fnv"
)

// Bloom-Filter-Struktur
type BloomFilter struct {
  m    uint64 // Größe des Bit-Arrays (Anzahl der Bits)
  k    uint64 // Anzahl der Hash-Funktionen
  bits []byte // Bit-Array
}

// Erstellen eines Bloom-Filters
func NewBloomFilter(expectedN uint64, falsePositiveRate float64) *BloomFilter {
  m, k := estimateParameters(expectedN, falsePositiveRate)
  if m == 0 || k == 0 {
    panic("Ungültige Parameter für Bloom-Filter: m oder k ist Null")
  }
  return NewBloomFilterWithMK(m, k)
}

// estimateParameters berechnet die optimalen m und k basierend auf der erwarteten Anzahl von Elementen n und der Falsch-Positiv-Rate p
// m = - (n * ln(p)) / (ln(2))^2
// k = (m / n) * ln(2)
func estimateParameters(n uint64, p float64) (m uint64, k uint64) {
  if n == 0 || p <= 0 || p >= 1 {
    return 1000, 10
  }
  mFloat := -(float64(n) * math.Log(p)) / (math.Ln2 * math.Ln2)
  kFloat := (mFloat / float64(n)) * math.Ln2

  m = uint64(math.Ceil(mFloat))
  k = uint64(math.Ceil(kFloat))

  if k < 1 {
    k = 1
  }
  return
}

// NewBloomFilterWithMK erstellt einen Bloom-Filter mit den angegebenen m und k
func NewBloomFilterWithMK(m, k uint64) *BloomFilter {
  if m == 0 || k == 0 {
    panic("Ungültige Parameter für Bloom-Filter: m oder k ist Null")
  }
  numBytes := (m + 7) / 8
  return &BloomFilter{
    m:    m,
    k:    k,
    bits: make([]byte, numBytes),
  }
}

// getHashes verwendet Double Hashing, um k Hash-Werte für die Daten zu generieren
func (bf *BloomFilter) getHashes(data []byte) []uint64 {
  hashes := make([]uint64, bf.k)

  // Verwenden Sie zwei verschiedene Versionen (oder Seeds) von FNV-1a als Basis-Hash-Funktionen
  h1 := fnv.New64()
  h1.Write(data)
  hash1Val := h1.Sum64()

  h2 := fnv.New64a()
  h2.Write(data)
  hash2Val := h2.Sum64()

  for i := uint64(0); i < bf.k; i++ {
    if hash2Val == 0 && i > 0 {
      hash2Val = 1
    }
    hashes[i] = (hash1Val + i*hash2Val) % bf.m
  }
  return hashes
}

Daten einfügen

// Daten in den Bloom-Filter einfügen
func (bf *BloomFilter) Add(data []byte) {
  hashes := bf.getHashes(data)
  for _, h := range hashes {
    byteIndex := h / 8                     // Finden des Byte-Index
    bitOffset := h % 8                     // Finden des Bit-Offsets innerhalb des Bytes
    bf.bits[byteIndex] |= (1 << bitOffset) // Setzen der entsprechenden Position auf 1
  }
}

Daten abfragen

// Prüfen, ob Daten vorhanden sein könnten
func (bf *BloomFilter) MightContain(data []byte) bool {
  hashes := bf.getHashes(data)
  for _, h := range hashes {
    byteIndex := h / 8
    bitOffset := h % 8
    if (bf.bits[byteIndex] & (1 << bitOffset)) == 0 {
      // Wenn ein Bit, das einem Hash entspricht, 0 ist, existiert das Element definitiv nicht
      return false
    }
  }
  // Wenn alle Bits, die Hashes entsprechen, 1 sind, könnte das Element existieren
  return true
}

Zurücksetzen des Bloom-Filters

// Reset löscht den Bloom-Filter (setzt alle Bits auf 0)
func (bf *BloomFilter) Reset() {
  for i := range bf.bits {
    bf.bits[i] = 0
  }
}

Testcode

func main() {
  // Beispiel: Erwarte 1000 Elemente, Falsch-Positiv-Rate 1 %%
  expectedN := uint64(1000)
  falsePositiveRate := 0.01

  m, k := estimateParameters(expectedN, falsePositiveRate)
  fmt.Printf("Geschätzte Parameter: m = %d, k = %d\n", m, k)

  bf := NewBloomFilter(expectedN, falsePositiveRate)
  // Oder bf := NewBloomFilterWithMK(m, k)

  // Einige Elemente hinzufügen
  item1 := []byte("apple")
  item2 := []byte("banana")
  item3 := []byte("cherry")

  bf.Add(item1)
  bf.Add(item2)

  fmt.Printf("MightContain 'apple': %t\n", bf.MightContain(item1))           // true
  fmt.Printf("MightContain 'banana': %t\n", bf.MightContain(item2))          // true
  fmt.Printf("MightContain 'cherry': %t\n", bf.MightContain(item3))          // false (sollte false sein, da es nicht hinzugefügt wurde)
  fmt.Printf("MightContain 'grape': %t\n", bf.MightContain([]byte("grape"))) // false (sollte auch false sein)

  bf.Reset()
  fmt.Println("Nach dem Zurücksetzen:")
  fmt.Printf("MightContain 'apple': %t\n", bf.MightContain(item1)) // false
}

Zusammenfassung

Ein Bloom-Filter kann uns in Cache-Systemen helfen, indem er:

• Reduzierung ungültiger Datenbankabfragen: Zuerst beurteilen, ob die Daten vorhanden sein könnten, um den direkten Zugriff auf die Datenbank zu vermeiden.
• Sparen von Speicherplatz: Verbraucht weniger Speicher als Hash-Tabellen und ist für große Datenmengen geeignet.
• Verbesserung der Abfrageeffizienz: O(1) Zeitkomplexität für Abfragen, keine Notwendigkeit, den gesamten Datensatz zu durchlaufen.

Wir haben Go verwendet, um einen einfachen Bloom-Filter zu implementieren und ihn auf Cache-Szenarien anzuwenden, um die Datenbanklast zu optimieren.

---

Wir sind Leapcell, Ihre erste Wahl für das Hosten von Go-Projekten.

Leapcell ist die Serverless-Plattform der nächsten Generation für Webhosting, asynchrone Aufgaben und Redis:

Multi-Language-Unterstützung

• Entwickeln Sie mit Node.js, Python, Go oder Rust.

Unbegrenzte Projekte kostenlos bereitstellen

• Zahlen Sie nur für die Nutzung – keine Anfragen, keine Gebühren.

Unschlagbare Kosteneffizienz

• Pay-as-you-go ohne Leerlaufgebühren.
• Beispiel: 25 US-Dollar unterstützen 6,94 Millionen Anfragen bei einer durchschnittlichen Antwortzeit von 60 ms.

Optimierte Entwicklererfahrung

• Intuitive Benutzeroberfläche für mühelose Einrichtung.
• Vollständig automatisierte CI/CD-Pipelines und GitOps-Integration.
• Echtzeitmetriken und -protokollierung für umsetzbare Erkenntnisse.

Mühelose Skalierbarkeit und hohe Leistung

• Automatisches Skalieren zur einfachen Bewältigung hoher Parallelität.
• Kein operativer Aufwand – konzentrieren Sie sich einfach auf das Erstellen.

Erfahren Sie mehr in der Dokumentation!

Folgen Sie uns auf X: @LeapcellHQ