CUCKOO vs BLOOM filter Gopheri vaatenurgast

Selles artiklis üritan kägufiltri tõhusust õitsemisfiltri abil rakendada ja katsetada. (Loe eelmist postitust Chord DHT-st, hajutatud räsitabeli rakendamine Golangis)

Sissejuhatus

Tõenäolised andmestruktuurid on väga kasulikud, eriti suurte andmekogumite töötlemisel. Enamasti, tegeldes asjade andmete poolega, tahaks reaalajas andmete töötlemise ajal teha lihtsat päringut “kas üksust pole olemas” või “on üksus juba olemas”. Oletagem, et soovite vastata päringutele reaalajas, näiteks kordumatute IP-de arv, kõige sagedamini esinevate IP-de korral, kui reklaam on juba kasutajale esitatud, pakkudes tõenäosuslike andmestruktuuride abil ruumipõhist viisi nendele küsimustele vastamiseks. Tüüpiline lähenemisviis sellistele päringutele oleks kas HashMap või HashTable kasutamine või selle salvestamine mõne välise vahemälu abil (näiteks redis), kuid probleem on suurte andmekogumitega, need lihtsad andmestruktuurid ei mahu mällu. See on koht, kus mängivad tõenäosuslikud andmestruktuurid nende ruumi ja aja eeliste tõttu.

Näide Kasutusjuhtumid

  • Google Bigtable, Apache HBase ja Apache Cassandra ning Postgresql kasutavad Bloomi filtreid, et vähendada olematute ridade või veergude kettaotsinguid. Kulukate kettaotsingute vältimine suurendab märkimisväärselt andmebaasipäringu toimingut.
  • Keskmine kasutab Bloomi filtreid, et kontrollida, kas artiklit on juba kasutajale soovitatud
  • Ethereum kasutab Bloomi filtreid, et Ethereumi plokiahelas logid kiiresti üles leida
  • Google Chrome'i veebibrauser kasutas pahatahtlike URL-ide tuvastamiseks Bloomi filtrit. Kõiki URL-e kontrolliti esmalt kohaliku Bloomi filtri abil ja ainult siis, kui Bloomi filter andis positiivse tulemuse, kontrolliti läbiviidud URL-i täies mahus (ja kasutaja hoiatas, kui ka see annab positiivse tulemuse)

Mis on “kägus”?

Oleme andmeplatvormil sellistele päringutele vastamiseks paljudes kohtades õitsemisfiltreid kasutanud. Hiljuti sattusin selle käkitegu käsitleva paberiga tutvuma, mis tekitas minu huvi. Pealkiri ise ütleb: “Kägufilter: praktiliselt parem kui õitsema”, nii et otsustasin seda kontrollida.

Kägufiltrid parandavad õitsemisfiltri disaini, pakkudes kustutamist, piiratud loendamist ja piiratud valepositiivse tõenäosuse säilitamist, säilitades samas sarnase ruumi keerukuse. Nad kasutavad kokkupõrgete lahendamiseks kägu räsimist ja on sisuliselt kompaktne kägu räsitabel.

Kägu- ja õitsemisfiltrid on mõlemad kasulikud liikmelisuse testimisel, kui algsete andmete suurus on suur. Mõlemad kasutavad sisestuse kohta ainult 7 bitti. Need on kasulikud ka siis, kui kallist toimingut saab enne selle sooritamist kindlaksmääratud liikmetesti abil vältida. Näiteks saab enne andmebaasist päringu tegemist teha komplekti kuulumise testi, et näha, kas soovitud objekt on isegi andmebaasis.

Algoritm

Filtri parameetrid:
1. Kaks räsifunktsiooni: h1 ja h2
2. Massiiv B koos n ämbriga. I ämber kannab nime B [i]

Sisend: L, loetelu elementidest, mis tuleb sisestada kägu filtrisse.

Algoritm:
Kuni L pole tühi:
    Olgu x esimene kirje loendis L. Eemaldage x loendist.
    Kui B [h1 (x)] on tühi:
        asetage x punkti B [h1 (x)]
    Muu, kui B [h2 (x) on tühi]:
        asetage x punkti B [h2 (x)]
    Muu:
        Olgu y element B-s [h2 (x)].
        Asendage y L-ni
        asetage x punkti B [h2 (x)]

Rakendamine

Rakendamine tundub üsna lihtne, nii et otsustasin proovida seda võrrelda ja võrrelda ruumi / aja efektiivsust õitsemisfiltriga. Kägu filter koosneb käo räsitabelist, kuhu salvestatakse sisestatud esemete sõrmejäljed. Üksuse sõrmejälg on bitine string, mis on saadud selle elemendi räsi järgi. Kägu räsitabel koosneb mitmest ämbrist, kuhu sisestatav objekt kaardistatakse kaheks räsifunktsioonil põhinevaks kaheks võimalikuks ämbriks. Iga ämber on konfigureeritav muutuva arvu sõrmejälgede salvestamiseks. Tavaliselt identifitseeritakse Kägu filter selle sõrmejälje ja ämbri suuruse järgi. Näiteks (2,4) kägufilter salvestab 2-bitise pikkusega sõrmejälgi ja iga käk Kägu räsitabelis võib hoida kuni 4 sõrmejälge.

Sisestamine

Algoritm:

f = sõrmejälg (x);
i1 = räsi (x);
i2 = i1 ⊕ räsi (f);
kui kopp [i1] või kopp [i2] on tühi kirje, siis
   lisage sellele ämbrile f;
   tagasi Valmis;
// peab olemasolevad üksused ümber paigutama;
i = valib juhuslikult i1 või i2;
n = 0; n 
// hashtable peetakse täielikuks;
tagastamise rike;

Kood:

Otsing

Algoritm:

f = sõrmejälg (x);
i1 = räsi (x);
i2 = i1 ⊕ räsi (f);
kui kopp [i1] või kopp [i2] on f, siis
    return True;
tagastama vale;

Kood:

Kustuta

Algoritm:

f = sõrmejälg (x);
i1 = räsi (x);
i2 = i1 ⊕ räsi (f);
kui kopp [i1] või kopp [i2] on f, siis
   eemaldage f-koopia sellest ämbrist;
   return True;
tagastama vale;

Kood:

Jõudlustesti

Olen Bloomi filtril testimiseks kasutanud Will Fitzgeraldi teeki. Kägufiltri jaoks kasutatud FPP (valepositiivse tõenäosuse) suhe on 0,001

Ruumi keerukus

Kägu- ja õitsemisfiltrite osas toimivad need erinevatel valepositiivsetel tõenäosustel. Kui filtri valepositiivne tõenäosus on alla 3% või sellega võrdne, on kägufiltris vähem kandeid bitti. Kui see on kõrgem, on õitsemisfiltril kande kohta vähem bitti.

Aja keerukus

Kägu räsimisel tundub elemendi sisestamine halvimal juhul palju hullem kui O (1), kuna kokkupõrke ajal võib esineda palju juhtumeid, kus peame väärtuse eemaldama, et praegusele väärtusele ruumi anda. Plus, kui on tsükkel, siis tuleb kogu tabel uuesti üle vaadata.

Mõlema filtri ajaanalüüs annab järgmised tulemused:

Selle katse vältel (pidades meeles, et minu koodi ei pruugita täielikult optimeerida) näivad Bloomi filtrid toimivat ruumi keerukuses erakordselt hästi, hõivates suure hulga üksuste jaoks vähem ruumi. Tundub, et kägufilter toimib suure hulga üksuste sisestamisel paremini, kuid selle rakendamise tõttu on otsingu aeg (otsinguajad) pisut aeglasem.

Järeldused

Ma ei võtaks tegelikult seda külge, mida filtrit soovitada, ma arvan, et neil mõlemal on oma kasutusjuhtumid. Õitsemisfiltrid ei toeta kustutusi, sest räsimine on kadudeta ja pöördumatu. Kuigi õitsemisfiltrite lugemine lahendab selle probleemi, on kägu filtrid kasulikud juhul, kui vajate kustutamist. Muidugi annavad kägu filtrid vea, kui filter on täis, ja sellel on ka omad eelised, samas kui Bloomi filtris puudub mahu kontroll, see lihtsalt kordab olemasolevat bitimassiivi.

Kood

Viited

  • https://brilliant.org/wiki/cuckoo-filter/
  • https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf
  • https://en.wikipedia.org/wiki/Cuckoo_hashing
  • https://blog.fastforwardlabs.com/2016/11/23/probabilistic-data-structure-showdown-cuckoo.html

P.S Kui leiate testides / juurutamises midagi valesti, jätke palun oma ettepanek / kommentaarid.