CUCKOO vs BLOOM sía, frá sjónarhóli Gopher

Í þessari grein er ég að reyna að útfæra og prófa skilvirkni kúkasíu yfir blómasíu. (Lestu fyrri færslu um Chord DHT, útfærðu dreift kjötkássatöflu í Golang)

Kynning

Líkindagagnaskipan er mjög gagnleg, sérstaklega þegar unnið er með stór gagnasöfn. Oftast, þegar unnið er að gagna hlið hlutanna, myndi maður vilja gera einfalda „er hluturinn ekki til staðar“ eða „er hluturinn sem er þegar til staðar“ fyrirspurn meðan unnið er úr rauntíma gögnum. Segja að þú viljir svara fyrirspurnum í rauntíma, eins og fjöldi einstaka ips, algengustu ips, ef auglýsing hefur þegar verið birt fyrir notanda, með því að nota líkindagagnaskipan er það skilvirk leið til að svara þessum fyrirspurnum. Dæmigerð aðferð við slíkar fyrirspurnir væri að nota annaðhvort HashMap eða HashTable eða geyma það einhvern ytri skyndiminni (eins og endurtekningu), en vandamálið er með stóra gagnapakka, þessi einföldu gagnagerð getur ekki passað inn í minni. Þetta er þar sem líkindagagnaskipan kemur til leiks vegna rýmis og tímabóta þeirra.

Dæmi Notaðu mál

  • Google Bigtable, Apache HBase og Apache Cassandra, og Postgresql nota Bloom síur til að draga úr leit á diskum fyrir raðir eða dálka sem ekki eru til. Að forðast dýrt leit í diskum eykur umtalsvert árangur aðgerða gagnagrunnsins.
  • Medium notar Bloom síur til að athuga hvort grein hafi þegar verið mælt með notanda
  • Ethereum notar Bloom síur til að finna fljótt logs á Ethereum blockchain
  • Google Chrome vefskoðarinn notaði til að nota Bloom síu til að bera kennsl á illgjarn vefslóð. Allar vefslóðir voru fyrst skoðaðar á staðnum Bloom síu, og aðeins ef Bloom sían skilaði jákvæðri niðurstöðu var full athugun á slóðinni sem framkvæmd var (og notandinn varaði við því, ef það líka skilaði jákvæðri niðurstöðu)

Hvað er í „kúkur“?

Við höfum notað blómasíur víða til að svara slíkum fyrirspurnum á gagnapallinum. Nýlega rakst ég á þetta blað á Cuckoo síu sem vakti áhuga minn. Titillinn sjálfur segir: „Cuckoo Filter: Practically Better Than Bloom“, svo ég ákvað að athuga það.

Gökusíur bæta hönnun blómasíunnar með því að bjóða upp á eyðingu, takmarkaða talningu og afmarkaða rangar jákvæðar líkur, en halda samt svipuðu rýmisflækju. Þeir nota hökukökur til að leysa árekstra og eru í raun og veru samningur töfra hassi.

Góku- og blómasíur eru bæði gagnlegar til að stilla aðildarprófanir þegar stærð upprunalegu gagna er stór. Þeir nota báðir aðeins 7 bita á hverja færslu. Þau eru einnig gagnleg þegar hægt er að forðast dýra aðgerð áður en það er sett með aðildarprófi. Til dæmis, áður en þú spyrð um gagnagrunn, er hægt að gera sett aðildarpróf til að sjá hvort viðkomandi hlutur sé jafnvel í gagnagrunninum.

Reiknirit

Breytur síunnar:
1. Tvær Hash aðgerðir: h1 og h2
2. Fylki B með n fötu. I-th fötu verður kölluð B [i]

Inntak: L, listi yfir þætti sem á að setja í kúkasíuna.

Reiknirit:
Meðan L er ekki tómt:
    Láttu x vera fyrsta atriðið á listanum L. Fjarlægðu x af listanum.
    Ef B [h1 (x)] er tómur:
        setjið x í B [h1 (x)]
    Annars, ef B [h2 (x) er tómur]:
        setjið x í B [h2 (x)]
    Annar:
        Láttu y vera frumefnið í B [h2 (x)].
        Bættu y við L
        setjið x í B [h2 (x)]

Framkvæmd

Útfærslan virðist nokkuð einföld, svo ég ákvað að fara í það og bera saman hversu rúm / tíma duglegur það er borið saman við blóma síu. Cuckoo sían samanstendur af tösku frá Cuckoo sem geymir „fingraför“ hlutanna sem settir eru inn. Fingrafar hlutar er hluti strengur fenginn úr hassi þess hlutar. Kökubasstöfluborð samanstendur af fjölda fötu þar sem hluturinn sem á að setja er kortlagður í tvær mögulegar fötur byggðar á tveimur kjötkássaaðgerðum. Hægt er að stilla hverja fötu til að geyma breytilegan fjölda fingraföra. Venjulega er Cuckoo sía auðkennd með fingrafar og stærð fötu. Til dæmis geymir (2,4) Cuckoo sía 2 bita lengd fingraför og hver fötu í Cuckoo kjötkássatöflunni getur geymt allt að 4 fingraför.

Innsetning

Reiknirit:

f = fingrafar (x);
i1 = kjötkássa (x);
i2 = i1 ⊕ hass (f);
ef fötu [i1] eða fötu [i2] er með tóma færslu þá
   bæta f við þá fötu;
   aftur Lokið;
// verður að flytja hluti sem fyrir eru;
i = velja i1 eða i2 af handahófi;
fyrir n = 0; n 
// Hashtable er talið fullt;
aftur Bilun;

Kóði:

Leitaðu

Reiknirit:

f = fingrafar (x);
i1 = kjötkássa (x);
i2 = i1 ⊕ hass (f);
ef fötu [i1] eða fötu [i2] hefur f þá
    aftur True;
koma aftur Ósatt;

Kóði:

Eyða

Reiknirit:

f = fingrafar (x);
i1 = kjötkássa (x);
i2 = i1 ⊕ hass (f);
ef fötu [i1] eða fötu [i2] hefur f þá
   fjarlægðu afrit af f úr þessari fötu;
   aftur True;
koma aftur Ósatt;

Kóði:

Árangurspróf

Ég hef notað Will Fitzgerald bókasafn í prófinu á Bloom síu. FPP (False Positive Probability) skammturinn sem tekinn var fyrir kúkasíu er 0,001

Rými flókið

Hvað varðar gökusíurnar og blómasíurnar, þá standa þær sig misjafnlega með mismunandi rangar jákvæðar líkur. Þegar rangar líkur á síunni eru minni eða eða jafnar og 3%, hefur gókusían færri bita á hverja færslu. Þegar það er hærra hefur blómasían færri bita á hverja færslu.

Tími flókið

Í kökukuklingum virðist það vera verra að setja inn frumefni en O (1) í versta tilfelli vegna þess að það gætu verið mörg tilvik við árekstur, þar sem við verðum að fjarlægja gildi til að gera pláss fyrir núverandi gildi. Plús, ef það er hringrás, verður að endurtaka allt borðið.

Að gera tímagreiningu á báðum síunum skilar eftirfarandi niðurstöðum:

Í allri þessari tilraun (með það í huga að kóðinn minn er hugsanlega ekki að fullu hámarkaður) virðast Bloom filters virka einstaklega vel í flóknu rúmi og taka minna pláss fyrir stóran fjölda hluta. Cuckoo sía virðist skila betri árangri við að setja inn fjölda af hlutum, en aðeins hægari í leit (leitartímar) vegna útfærslu þess.

Ályktun

Ég myndi ekki taka neina hlið á hvaða síu ég ætti að mæla með, ég held að þau hafi bæði sín eigin mál. Síur Bloom styðja ekki eyðingu vegna þess að hass er taplaust og óafturkræft. Þó að telja blómasíur leysi þetta vandamál, eru gókusíur gagnlegar ef þú þarft að eyða. Auðvitað gefa gökusíur villu þegar sían er full, og það hefur sína kosti, en í Bloom síu er engin stjórn á afkastagetu, hún endurtekur aðeins yfir núverandi hluti.

Kóði

Tilvísanir

  • 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 Ef þér finnst eitthvað athugavert við prófin / útfærsluna skaltu ekki hika við að láta tillögur þínar / athugasemdir fylgja.