streamalism.org

1. Prehľad

V tomto článku sa pozrieme na konštrukciu filtra Bloom z Guava knižnica. Bloom filter je pamäťovo efektívna, pravdepodobnostná dátová štruktúra, pomocou ktorej môžeme odpovedať na otázku či je alebo nie je daný prvok v množine.

Neexistujú žiadne falošné negatívy s filtrom Bloom, takže keď sa vráti nepravdivé, môžeme si byť 100% istí, že prvok nie je v množine.

Avšak Bloomov filter môže vrátiť falošné poplachy, takže keď sa vráti pravda, je vysoká pravdepodobnosť, že sa prvok nachádza v množine, ale nemôžeme si byť stopercentne istí.

Podrobnejšiu analýzu fungovania filtra Bloom nájdete v tomto výučbe.

2. Závislosť od Maven

Budeme používať implementáciu Bloomovho filtra od spoločnosti Guava, pridajme teda guava závislosť:

 com.google.guava guava 29.0-jre 

Najnovšiu verziu nájdete na serveri Maven Central.

3. Prečo používať Bloom filter?

Filter Bloom je navrhnuté tak, aby boli priestorovo efektívne a rýchle. Pri jeho použití môžeme upresnite pravdepodobnosť falošne pozitívnych odpovedí, ktoré môžeme prijať a podľa tejto konfigurácie Bloom filter zaberie čo najmenej pamäte.

Vďaka tejto priestorovej efektívnosti filter Bloom sa ľahko zmestí do pamäte aj pre obrovské množstvo prvkov. Niektoré databázy, vrátane Cassandry a Oracle, používajú tento filter ako prvú kontrolu pred prechodom na disk alebo do medzipamäte, napríklad keď príde požiadavka na konkrétne ID.

Ak filter vráti, že ID nie je k dispozícii, databáza môže zastaviť ďalšie spracovanie žiadosti a vrátiť sa klientovi. V opačnom prípade prejde na disk a vráti prvok, ak sa na disku nachádza.

4. Vytvorenie Bloomovho filtra

Predpokladajme, že chceme vytvoriť Bloom filter až pre 500 Celé čísla a že môžeme tolerovať jednopercentnú (0,01) pravdepodobnosť falošných poplachov.

Môžeme použiť BloomFilter triedy z Guava knižnice, ako to dosiahnuť. Musíme odovzdať počet prvkov, ktoré sa majú vložiť do filtra, a požadovanú pravdepodobnosť falošnej pozitivity:

Filter BloomFilter = BloomFilter.create (Funnels.integerFunnel (), 500, 0,01);

Teraz pridajme do filtra niekoľko čísel:

filter.put (1); filter.put (2); filter.put (3);

Pridali sme iba tri prvky a definovali sme, že maximálny počet vložení bude 500, teda náš Bloom filter by malo priniesť veľmi presné výsledky. Vyskúšajme to pomocou couldContain () metóda:

assertThat (filter.mightContain (1)). isTrue (); assertThat (filter.mightContain (2)). isTrue (); assertThat (filter.mightContain (3)). isTrue (); assertThat (filter.mightContain (100)). isFalse ();

Ako už názov napovedá, nemôžeme si byť stopercentne istí, že daný prvok je po návrate metódy v skutočnosti vo filtri pravda.

Kedy couldContain () vracia pravda v našom príklade si môžeme byť na 99% istí, že sa prvok nachádza vo filtri, a existuje jednopercentná pravdepodobnosť, že výsledok bude falošne pozitívny. Keď sa filter vráti nepravdivé, môžeme si byť 100% istí, že prvok nie je prítomný.

5. Nadsýtený Bloom filter

Keď navrhujeme náš Bloom filter, je dôležité, aby sme poskytli primerane presnú hodnotu pre očakávaný počet prvkov. V opačnom prípade náš filter vráti falošné poplachy oveľa vyššou rýchlosťou, ako je požadované. Pozrime sa na príklad.

Predpokladajme, že sme vytvorili filter s požadovanou falošne pozitívnou pravdepodobnosťou jedného percenta a predpokladaným počtom prvkov rovnajúcim sa piatim, ale potom sme vložili 100 000 prvkov:

Filter BloomFilter = BloomFilter.create (Funnels.integerFunnel (), 5, 0,01); IntStream.range (0, 100_000). ForEach (filter :: put); 

Pretože očakávaný počet prvkov je taký malý, filter zaberie veľmi málo pamäte.

Pretože však pridávame viac položiek, ako sme očakávali, položka filter je nadmerne nasýtený a má oveľa vyššiu pravdepodobnosť návratu falošne pozitívnych výsledkov než požadované jedno percento:

assertThat (filter.mightContain (1)). isTrue (); assertThat (filter.mightContain (2)). isTrue (); assertThat (filter.mightContain (3)). isTrue (); assertThat (filter.mightContain (1_000_000)). isTrue ();

Všimnite si, že couldContatin () metóda vrátený pravda aj za hodnotu, ktorú sme nezadali do filtra predtým.

6. Záver

V tomto rýchlom výučbe sme sa pozreli na pravdepodobnostnú povahu dátovej štruktúry filtra Bloom - s využitím Guava implementácia.

Implementáciu všetkých týchto príkladov a útržkov kódu nájdete v projekte GitHub.

Toto je projekt Maven, takže by malo byť ľahké ho importovať a spustiť tak, ako je.