Bloom-filter: vad det är, hur det fungerar och användning

Bloom-filter: Lär dig vad det är, hur det fungerar och praktiska användningar. Förstå probabilistiska egenskaper, falska positiva och när Bloom-filter är rätt val.

Ett Bloom-filter är en datastruktur som gör det möjligt för datorer att avgöra om ett visst element förekommer i en mängd eller inte, med mycket låg minnesåtgång. Bloom-filter använder hash-funktioner för att kartlägga element till positioner i en bitvektor (en array med ettor och nollor). För varje element som läggs till beräknas flera hashvärden och motsvarande bitar i bitvektorn sätts till 1. När ett element kontrolleras beräknas samma hashvärden och om någon av de kontrollerade bitarna är 0 så kan elementet definitivt inte finnas i mängden; om alla är 1 så är svaret möjligen i mängden. Ett Bloom-filter är alltså en probabilistisk datastruktur: det kan ge falskt positiva resultat (säger att ett element finns när det inte gör det), men inte falskt negativa resultat (säger att ett element saknas när det faktiskt finns). Element kan läggas till, men inte tas bort med ett enkelt Bloom-filter – varje nytt element ökar sannolikheten för falska positiva resultat.

Hur det fungerar i praktiken

I ett typiskt Bloom-filter finns en bitvektor av storlek m och man använder k olika hashfunktioner. När ett element x läggs till beräknas hashfunktionerna h1(x), h2(x), …, hk(x) som ger k positioner i intervallet [0, m−1]; dessa bitar sätts till 1. För att fråga om x finns beräknas samma k positioner. Om någon av bitarna är 0 vet vi att x inte finns; om alla är 1 svarar filtret att x möjligen finns.

Matematiskt kan sannolikheten för ett falskt positivt svar approximeras som

p ≈ (1 − e^{−k n / m})^k,

där n är antalet insatta element, m är antalet bitar i filteret och k är antalet hashfunktioner. För en given m och n är det optimala antalet hashfunktioner k ≈ (m / n) ln 2, vilket minimerar p. Med detta val blir p ungefär (0.6185)^{m/n}.

Dimensionering och minnesbehov

Valet av m (bitstorlek) och k (antal hashfunktioner) är en kompromiss mellan minne, hastighet och önskad falskpositiv-frekvens. Ett välkänt uttryck för antalet bitar per element för en målsannolikhet p är

m / n = − (ln p) / (ln 2)^2.

Detta innebär exempelvis att för p = 1 % krävs mindre än 10 bitar per element (ungefär 9,6 bitar), oberoende av den totala storleken m eller antalet element n i uppsättningen — förutsatt att parametrarna väljs enligt formeln.

Praktiska detaljer och implementation

• Hashfunktioner: Man behöver flera oberoende hashvärden. I praktiken används ofta dubbel-hashning: generera två oberoende hashvärden och kombinera dem för att få k funktioner, vilket är snabbare än att köra k helt separata hashfunktioner.
• Bitarray-implementation: Använd en effektiv bitset- eller bitmap-struktur för att spara minne och snabba upp operationer.
• Prestanda: Insättning och kontroll är mycket snabba (O(k) hashar och bit-åtkomster). Bloom-filter är CPU- och cachevänliga vid rätt implementation.
• Borttagning: Vanliga Bloom-filter stödjer inte borttagning. För att tillåta borttagning finns varianter som counting Bloom filter, där varje position är en liten räknare istället för en enda bit (kräver mer minne).

Variationer och alternativ

Det finns flera varianter och relaterade datastrukturer:

• Counting Bloom filter: Använder räknare per position och tillåter borttagning av element.
• Scalable Bloom filter: Kan växa när antalet element ökar för att bibehålla en given falskpositiv-nivå.
• Compressed Bloom filter: För att spara bandbredd vid överföring mellan system.
• Cuckoo filter: Ett alternativ som ofta ger lägre minnesåtgång för samma falskpositiv-sannolikhet och stödjer borttagning utan räknare.

Användningsområden

Bloom-filter används i många system där minne är begränsat och man snabbt vill utesluta att ett element finns, till exempel:

• Databaser och cachningssystem (t.ex. snabbt avgöra om en post inte finns i en cache).
• Webb- och söktjänster (t.ex. URL-filter för att undvika dyra uppslag).
• Distributionssystem och nätverk (t.ex. för att reducera mängden överförd data vid synkronisering).
• Spamfiltrering och säkerhet (snabb filtrering av kända skräppostmönster).
• Bioinformatik (t.ex. k-mer-indexering i stora sekvensdatabaser).

Begränsningar och praktiska råd

Viktiga begränsningar att ha i åtanke:

• Inga falska negativa svar: Ett korrekt byggt Bloom-filter ger inte falska negativa svar, men felaktig användning (t.ex. försöka ta bort element utan räknare) kan leda till fel.
• Ökande falskpositivitet: Ju fler element som läggs till desto högre blir sannolikheten för falska positiva svar om filtret inte dimensionerats eller skalats.
• Ingen återhämtning: Om du behöver exakt medlemskap med möjlighet att ta bort objekt kan andra strukturer (t.ex. räknande Bloom-filter eller cuckoo filter) vara bättre.
• Hashkvalitet: Dåliga hashfunktioner (kollisioner, bristande spridning) försämrar prestanda och ökar falskpositiv-frekvensen. Använd beprövade hashmetoder och/eller dubbel-hashning.

Historik

Edward Bloom föreslog Bloom-filtret 1970. I sin artikel antog Bloom att det finns en algoritm för att skilja ord i slutet av en rad med bindestreck. Enligt exemplen har de flesta ord enkla bindningsmönster men ungefär 10 % av orden krävde tidskrävande sökningar för att hämta rätt regel i en stor ordlista (hans fall gällde bindestreckning av cirka 500 000 ord). Bloom insåg att det skulle krävas mycket minne för att lagra reglerna med en "felfri" hash-teknik, men med hans probabilistiska metod kunde man eliminera majoriteten av dyra sökningar; ett hashområde som bara är en bråkdel (t.ex. 15 %) av storleken för en ideal felfri hash kunde ändå avlägsna en stor del av åtkomstkostnaderna.

Sammanfattningsvis är Bloom-filter en effektiv och minnessnål metod för snabb medlemskapskontroll när man kan acceptera en definierad sannolikhet för falska positiva svar. Valet av parametrar (m, n, k) och variant (t.ex. counting eller scalable) avgör om Bloom-filter är rätt verktyg för ett givet problem.

Frågor och svar

F: Vad är ett Bloom-filter?

F: Vilken typ av datastruktur är ett Bloom-filter?

F: Vem föreslog Bloom-filtret?

F: Vad var Edwards exempel på hur han använde sin teknik?

F: Hur många bitar per element krävs för att sannolikheten för falskt positiva resultat ska vara 1 %?

F: Är det möjligt att ta bort element från ett Bloom-filter när de väl har lagts till?

F: Ökar eller minskar sannolikheten för att få ett falskt positivt resultat om man lägger till fler element?

Sök med bokstav