One Hash Bloom Filters

Overzicht

Een Bloom-filter is een probabilistische datastructuur waarmee je snel en goedkoop de vraag "bevindt sleutel X zich in deze set?" kunt beantwoorden met ofwel "absoluut niet" of "waarschijnlijk wel".

Je kiest een acceptabel percentage fout-positieven (false positive rate) op basis van je werklast en hardware, voegt sleutels toe aan de set en controleert later of ze aanwezig zijn.

Bloom-filters gebruiken een kleine hoeveelheid geheugen in vergelijking met de cardinaliteit van de set en zijn rekentechnisch zeer efficiënt. Om deze redenen worden ze vaak gebruikt in high-performance datasystemen.

Een database kan bijvoorbeeld een Bloom-filter in het geheugen bijhouden en dit raadplegen voordat er daadwerkelijk naar de schijf wordt geschreven bij het opzoeken van rijen. Dit bespaart aanzienlijke hoeveelheden zeer trage disk-IO.

We gebruiken ze ook op grote schaal in de backend van Bluesky. Hiermee kunnen we miljoenen queries per seconde besparen op onze Scylla-database bij het opzoeken van blokkeringen, mutes, labels en meer. We kunnen bijvoorbeeld vaak de vraag "blokkeert gebruiker X gebruiker Y?" beantwoorden zonder zelfs maar de database aan te roepen.

In onze data is te zien dat we een positieve hit-rate van ongeveer 1% hebben. Dit betekent dat we in 99% van de gevallen het bevragen van onze database volledig kunnen overslaan. Dit is cruciaal geweest voor ons vermogen om de site op een goedkope manier te schalen en te exploiteren.

Traditionele Bloom-filters

Een Bloom-filter bestaat uit een array van bits en $k$ hashfuncties. Je kiest vooraf de grootte van de array en de waarde van $k$, waarbij je deze afstemt op je werklast om een specifiek percentage fout-positieven te bereiken.

  • Een sleutel toevoegen: Haal de sleutel door de $k$ hashfuncties en zet de bits op de resulterende locaties op '1'.
  • Controleren of een sleutel in de set zit: Hash de sleutel $k$ keer en controleer elke resulterende locatie in de bit-array. Als een van de bits '0' is, is de sleutel nooit toegevoegd (een definitief negatief resultaat). Als alle bits op '1' staan, bevindt de sleutel zich mogelijk in de set (een potentieel positief resultaat).

Double Hashing

Hoewel het goedkoper is dan toegang tot de schijf, is het berekenen van $k$ onafhankelijke hashes per sleutel nog steeds relatief duur voor systemen met zeer hoge prestaties.

In 2008 schreven Kirsch en Mitzenmacher een paper waarin ze aantoonden dat twee hashes hetzelfde resultaat kunnen opleveren. Als je de $i$-de locatie afleidt als (hash1 + i * hash2) % n, dan is het percentage fout-positieven effectief gelijk aan dat van het gebruik van $k$ onafhankelijke hashes.

De bibliotheek bits-and-blooms/bloom, onderhouden door Daniel Lemire, is een fantastische implementatie van een double hash Bloom-filter geschreven in Go. Deze voert twee keer 128-bit murmur3 uit om vier 64-bit waarden te krijgen, die vervolgens worden gecombineerd om alle $k$ bit-locaties te produceren. We hebben dit lange tijd in productie bij Bluesky gebruikt.

Voor de Bluesky-backend voeren we in feite een SELECT * FROM blocks, mutes, list items, etc. uit telkens wanneer een proces start, en voegen we alle items toe aan het Bloom-filter. Er is ook een real-time atproto firehose-consumer die items in de Bloom-filters invoegt (zelfs tijdens het opstarten van het proces), waardoor er een raceconditie kan ontstaan als je niet voorzichtig bent.

Het probleem met de bits-and-blooms bibliotheek is dat deze intern niet thread-safe is. We moesten daarom alle toegang tot het Bloom-filter omhullen met een mutex om data-races te voorkomen. Uit pprof bleek dat mutex-contention (conflict) de bottleneck was bij het opstarten van het proces. Een enkele deployment duurde hierdoor soms 90 minuten om volledig te worden uitgerold.

Mijn collega Jasmine heeft daarom de bibliotheek geforkt en atomic-bloom gemaakt. Deze gebruikt atomaire CPU-instructies voor dezelfde logica, maar dan veilig en zonder mutexes. Dit leidde tot aanzienlijk minder contention en was massaal sneller. Onze deployment-tijd daalde van 90 minuten naar ongeveer 15 minuten, waardoor we sneller en met meer vertrouwen konden releasen.

One Hash

Kunnen we nog verder gaan?

Voor Bluesky was het antwoord 'nee'. Contention was ons oorspronkelijke probleem, niet het aantal hashfuncties. Volgens de wet van Amdahl leverde verdere optimalisatie op dat vlak geen merkbare impact meer op. Toch is het leerzaam om dieper in de materie te duiken.

Tijdens ons onderzoek naar Bloom-filtertechnieken kwamen we een paper van Lu et al. tegen, die aantoont hoe je Bloom-filters kunt implementeren met slechts één enkele hash.

Hoe het werkt:

  1. In plaats van één grote bit-array, wordt deze gesplitst in $k$ array-partities van vaste grootte.
  2. Elke partitie heeft een andere grootte, en al deze groottes zijn pairwise coprime (onderling priem), wat betekent dat geen twee groottes een gemeenschappelijke factor hebben anders dan één.
  3. Je hasht de gegeven sleutel één keer om een hash te verkrijgen.
  4. De bit-positie in partitie $p$ is hash % size_p (de grootte van de partitie).
  5. Omdat je $k$ partities hebt, krijg je uit die ene hash $k$ bit-posities om te controleren.

Je kunt deze $k$ bit-posities vervolgens gebruiken zoals je dat bij andere Bloom-filtertypes zou doen.

Op basis van deze techniek heb ik jcalabro/gloom gemaakt, een One-Hash Bloom Filter (OHBF) implementatie in Go. Deze is inmiddels negen maanden live in de Bluesky-backend en presteert goed. Het wordt ook gebruikt in Jetstream, onze high-performance sync-service.

Voorbeeld van gebruik:

package main

import (
	"fmt"
	"sync"
	"github.com/jcalabro/gloom"
)

func main() {
	// Maak een thread-safe atomaire bloom filter met:
	//    - Verwachte capaciteit van 1 miljoen items
	//    - Benaderd percentage fout-positieven van 1%
	f := gloom.NewAtomic(1_000_000, 0.01)
	var wg sync.WaitGroup
	defer wg.Wait()
	for i := range 8 {
		wg.Go(func() {
			for j := range 100000 {
				str := fmt.Sprintf("key-%d-%d", i, j)
				if f.TestString(str) {
					// Altijd een fout-positief aangezien de sleutel niet in de set zit
					fmt.Printf("found a false positive: %s\n", str)
				}
				f.AddString(str)
			}
		})
	}
}

Werking onder de motorkap

Laten we in detail kijken naar hoe dit intern werkt. Hier is een voorbeeld van Go-code die laat zien hoe we de block-index en h selecteren voor een sleutel die we willen controleren:

hash := xxh3.Hash128(key) // bereken de 128-bit hash
block := hash.Hi % numBlocks // de hoge 64 bits bepalen het block
h := hash.Lo                 // de lage 64 bits zijn de hash die we controleren

Naast het gebruik van een enkele hash, zijn er enkele performance-optimalisaties toegepast:

Cache-optimalisatie We splitsen het Bloom-filter in veel blokken van 64 bytes om aan te sluiten bij de gebruikelijke CPU cache line-grootte. Omdat de allocator van Go niet garandeert dat deze blok-allocaties cache-aligned zijn, alloceren we iets meer geheugen en gebruiken we unsafe om de alignment te forceren. Deze twee technieken samen garanderen dat een Bloom-filter lookup in het slechtste geval slechts één cache miss veroorzaakt.

Vermijden van Modulo Er is een andere optimalisatie van Daniel Lemire die het mogelijk maakt om te selecteren welk blok gecontroleerd moet worden met een enkele MUL (vermenigvuldiging) instructie in plaats van modulo, aangezien modulo een dure divisie-instructie vereist.

ShardedAtomicFilter De laatste interessante optimalisatie is de ShardedAtomicFilter. Bij Bluesky beheerde ik een groot aantal high-end bare metal servers. Om de maximale prestaties uit deze systemen te halen, is het belangrijk om te voorkomen dat meerdere cores strijden om dezelfde data. ShardedAtomicFilter verspreidt schrijfacties over vele achterliggende filter-shards, wat de kans op contention vermindert.

Conclusie

Bloom-filters (en roaring bitmaps) zijn onmisbaar in moderne systemen. Hopelijk was dit een interessante verkenning van hoe ze werken.