Bloom-filter: Definition, funktion og anvendelser

Bloom-filter: Lær definition, funktion og anvendelser af denne probabilistiske hash-datastruktur — hurtig medlemskabstest, lavt hukommelsesforbrug og håndtering af falske positive.

Et Bloom-filter er en datastruktur, der gør det muligt for computere at se, om et givet element forekommer i et sæt. Bloom-filtre anvender hash-funktioner til dette formål. I en standardimplementering består et Bloom-filter af et bit-array (en række bits) og k uafhængige hash-funktioner. Når et nyt element tilføjes, beregner man k hashværdier; hver hash peger på en position i bit-arrayet, og disse bits sættes til 1. Ved forespørgsel beregner man igen de samme k hashes for elementet og kontrollerer, om alle tilsvarende bits er 1. Hvis mindst én af bitene er 0, er elementet helt sikkert ikke i mængden. Hvis alle bits er 1, svarer filteret derimod "muligvis i mængden" — det kan altså give et falsk positivt svar, men det kan ikke give et falsk negativt svar. Elementer kan tilføjes til mængden, men fjernelse er ikke mulig i et klassisk Bloom-filter (se dog counting Bloom-filter nedenfor). For hvert tilføjet element vokser sandsynligheden for at få et falsk positivt resultat, efterhånden som flere bits sættes til 1.

Historisk kontekst

Edward Bloom foreslog Bloom-filteret i 1970. I artiklen antager Bloom, at der findes en algoritme til at sætte bindestreger på ord i slutningen af en linje. Han observerede, at de fleste ord har enkle bindingsmønstre, men at omkring 10 % kræver langsommere opslag i en tabel for at finde den korrekte regel. Han arbejdede med afbinding af et stort ordforråd og så, at brug af traditionelle, fejlfri hashing-teknikker ville kræve meget hukommelse. Med Bloom-filtre kunne han eliminere langt de fleste opslag: et hash-område, der kun var ca. 15 % af størrelsen af en ideel fejlfri hash, kunne stadig reducere ca. 85 % af disktilgangene i hans eksempel.

Matematikken bag og parametre

Sandsynligheden for et falsk positivt svar afhænger af bit-arrayets størrelse m (antal bits), antallet af indsatte elementer n og antallet af hashfunktioner k. En ofte brugt tilnærmelse for sandsynligheden p for falsk positiv efter n indsættelser er

p ≈ (1 − e^{-kn/m})^k

For et givet forhold m/n (bits pr. element) er den optimale værdi af k omtrent k = (m/n) ln 2. Med velvalgte parametre kræves der i praksis ofte under 10 bits pr. element for at opnå en falsk positiv sandsynlighed på omkring 1 %, uafhængigt af den absolutte størrelse af m eller n.

Varianter og funktioner

• Standard Bloom-filter: Understøtter kun indsættelse og forespørgsel, ikke fjernelse.
• Counting Bloom-filter: I stedet for et enkelt bit-array bruger man tællere pr. position, så man kan fjerne elementer ved at decrementere tællerne. Dette øger hukommelsesforbruget, men muliggør sletning.
• Scalable Bloom-filter: En variant, der kan vokse dynamisk for at holde en begrænset fejlrate, når antallet af elementer ikke kendes på forhånd.
• Compressed/Partitioned Bloom-filtre: Flere optimeringer til at reducere plads eller forbedre hashingegenskaber.

Anvendelser

Bloom-filtre er meget brugt, når man hurtigt ønsker at afvise opslag, som ellers ville kræve dyre disk- eller netværksadgange. Typiske anvendelser:

• Web-caching og proxyer: Undgå opslag i cache eller disk, hvis objektet med sikkerhed ikke er til stede.
• Databaser og store nøgle-værdi-lagre (fx Bigtable, Cassandra): Forhindre unødvendige disk-IO ved at teste for nøglers tilstedeværelse.
• Distribution og synkronisering: Hurtig test for stereo-sæt eller duplikatudtrækning.
• Netværk og routing: Filtrering af pakker eller flows (fx peer-to-peer systemer).
• Søgemaskiner og indeksopslag: Filtrere ikke-eksisterende token-forespørgsler.
• Spelling og hyphenation (historisk eksempel): Som Bloom oprindelig beskrev for at reducere opslag i bindestavningsregler.

Fordele og begrænsninger

• Fordele: Meget plads-effektivt for store mængder, hurtige operationer (bitmanipulation), simpelt at implementere.
• Begrænsninger: Kan give falsk positivt resultat, kan ikke returnere selve elementerne eller antallet af forekomster, og sletning er ikke mulig i den simple variant. Desuden kan dårlige eller kolliderende hashfunktioner forringe ydeevnen, og i visse sikkerhedskritiske sammenhænge kan en modstander udnytte falske positiver.

Praktiske råd

• Vælg m og k ud fra forventet antal elementer n og ønsket fejlsandsynlighed p (brug formlerne ovenfor).
• Brug gode, hurtige hashfunktioner eller kombiner flere hashseedede outputs fra en hurtig hash for at simulere k funktioner.
• Overvåg belastningen af filteret: når en stor del af bits er sat til 1, stiger falsk positiv-sandsynligheden markant.
• Hvis sletning er nødvendig, overvej counting Bloom-filter eller andre datastrukturer.

Sammenfattende er Bloom-filtre en enkel, plads-effektiv og hurtig probabilistisk datastruktur, som i mange praktiske systemer kan eliminere store mængder unødvendige opslag, så længe man accepterer risikoen for falsk positivt svar, men ikke falsk negativt svar.

Spørgsmål og svar

Spørgsmål: Hvad er et Bloom-filter?

Spørgsmål: Hvilken type datastruktur er et Bloom-filter?

Spørgsmål: Hvem foreslog Bloom-filteret?

Spørgsmål: Hvad var Edwards eksempel på brugen af hans teknik?

Spørgsmål: Hvor mange bits pr. element er der behov for for 1 % falsk positiv sandsynlighed?

Spørgsmål: Er det muligt at fjerne elementer fra et bloom-filter, når de først er blevet tilføjet?

Spørgsmål: Øger eller mindsker tilføjelsen af flere elementer sandsynligheden for at få et falsk positivt resultat?

Søg efter bogstav