Filtri CUCKOO vs BLOOM, nga perspektiva e Gopher

Në këtë artikull, unë jam duke u përpjekur për të zbatuar dhe provuar efikasitetin e një filtri kuku mbi një filtër lulëzimi. (Lexoni postimin e mëparshëm në Akord DHT, duke zbatuar një tabelë të shpërndarë hashash në Golang)

Prezantimi

Strukturat probabilitare të të dhënave janë shumë të dobishme, veçanërisht kur përpunohen grupe të mëdha të të dhënave. Në shumicën e rasteve, ndërsa punoni në anën e të dhënave të gjërave, dikush do të dëshironte të bënte një pyetje të thjeshtë "është artikulli që nuk është i pranishëm" ose "është sendi tashmë i pranishëm" ndërsa përpunon të dhënat në kohë reale. Thuaj se dëshironi të përgjigjeni në pyetjet në kohë reale, si numri i IP-ve unike, IP-të më të shpeshta, nëse një reklamë i është shërbyer tashmë një përdoruesi, duke përdorur strukturat e të dhënave probabiliste, siguroni një mënyrë efikase në hapësirë ​​për t'iu përgjigjur këtyre pyetjeve. Qasja tipike për pyetje të tilla do të ishte përdorimi i një HashMap ose një HashTable, ose ruajtja e tij është disa cache e jashtme (si redis), por problemi është me të dhënat e të dhënave të mëdha, këto struktura të thjeshta të të dhënave nuk mund të futen në memorje. Kjo është ajo ku strukturat e të dhënave të mundshme fillojnë të zbatohen për shkak të avantazheve të tyre në hapësirë ​​dhe kohë.

Shembull Përdorni raste

  • Google Bigtable, Apache HBase dhe Apache Cassandra, dhe Postgresql përdorin filtrat Bloom për të zvogëluar kërkimet në diskut për rreshtat ose kolonat joekzistente. Shmangia e kërkimeve të kushtueshme të diskut në mënyrë të konsiderueshme rrit performancën e një operacioni të pyetjes së bazës së të dhënave.
  • Medium përdor filtra Bloom për të parë nëse një artikull tashmë është rekomanduar për një përdorues
  • Ethereum përdor filtra Bloom për të gjetur shpejt shkrimet në bllokun e Ethereum
  • Shfletuesi i uebit Google Chrome i përdorur për të përdorur një filtër Bloom për të identifikuar URL-të me qëllim të keq. Anydo URL u kontrollua së pari kundër një filtri lokal Bloom, dhe vetëm nëse filtri Bloom ktheu një rezultat pozitiv ishte një kontroll i plotë i URL-së së kryer (dhe përdoruesi paralajmëroi, nëse edhe kjo u kthye një rezultat pozitiv)

Farë është në një "Cuckoo"?

Ne kemi përdorur filtra lulëzimi në shumë vende për t'iu përgjigjur pyetjeve të tilla në platformën e të dhënave. Kohët e fundit kam hasur në këtë letër në filtrin Cuckoo i cili më interesoi. Vetë titulli thotë, "Filter Cuckoo: Praktikisht më mirë se lulëzimi", kështu që vendosa ta kontrolloj.

Filtrat e kukusës përmirësohen në hartimin e filtrit të lulëzimit duke ofruar fshirje, numërim të kufizuar dhe një probabilitet të rremë pozitiv të kufizuar, duke ruajtur ende një kompleksitet të ngjashëm hapësinor. Ata përdorin hashje kuku për të zgjidhur përplasjet dhe në thelb janë një tavolinë kompakte hash kuku.

Filtrat e kungujve dhe të lulëzimit janë të dy të dobishëm për testimin e anëtarësimit, kur madhësia e të dhënave origjinale është e madhe. Ata të dy përdorin vetëm 7 bit për hyrje. Ato janë gjithashtu të dobishme kur një operacion i shtrenjtë mund të shmanget para ekzekutimit nga një test i caktuar anëtarësie. Për shembull, para se të kërkoni një bazë të dhënash, mund të bëhet një test i anëtarësimit i vendosur për të parë nëse objekti i dëshiruar është edhe në bazën e të dhënave.

algoritmi

Parametrat e filtrit:
1. Dy funksione Hash: h1 dhe h2
2. Një grup B me kova n. Kova e i-të do të quhet B [i]

Input: L, një listë e elementeve që duhet të futen në filtrin e kuzhinës.

algoritmi:
Ndërsa L nuk është bosh:
    Le të jetë x pika e parë në listën L. Hiqni x nga lista.
    Nëse B [h1 (x)] është bosh:
        vendoset x në B [h1 (x)]
    Tjetër, Nëse B [h2 (x) është bosh]:
        vendoset x në B [h2 (x)]
    tjetër:
        Le të jetë y elementi në B [h2 (x)].
        Përgatitni y në L
        vendoset x në B [h2 (x)]

zbatim

Zbatimi duket mjaft i drejtpërdrejtë, kështu që vendosa të bëj një kontroll në të dhe të krahasoj sesa hapësirë ​​/ kohë efikase është krahasuar me një filtër lulëzimi. Filtri Cuckoo përbëhet nga një tabelë hash Cuckoo që ruan "gjurmët e gishtërinjve" të sendeve të futura. Gjurmët e gishtave të një sendi janë pak varg që rrjedhin nga hash-i i këtij sendi. Një tavolinë hash kucku përbëhet nga një grup kovash ku një artikull që duhet të futet është hartësuar në dy kova të mundshme bazuar në dy funksione hash. Eachdo kovë mund të konfigurohet për të ruajtur një numër të ndryshueshëm të shenjave të gishtërinjve. Në mënyrë tipike, një filtër Cuckoo identifikohet nga gjurmët e gishtave dhe madhësia e kovës. Për shembull, një filtër (2,4) Cuckoo ruan gjurmët e gishtërinjve me dy gjatësi dhe secila kovë në tryezën e hashashit Cuckoo mund të ruajë deri në 4 gjurmët e gishtërinjve.

futje

algoritmi:

f = gjurmët e gishtit (x);
i1 = hash (x);
i2 = i1 ⊕ hash (f);
nëse kova [i1] ose kova [i2] ka një hyrje të zbrazët, atëherë
   shtoni f në atë kovë;
   kthimi Bërë;
// duhet të zhvendosë sendet ekzistuese;
i = marr rastësisht i1 ose i2;
për n = 0; n 
// Hashtable konsiderohet e plotë;
kthimi Dështimi;

Code:

Kërko

algoritmi:

f = gjurmët e gishtit (x);
i1 = hash (x);
i2 = i1 ⊕ hash (f);
nëse kova [i1] ose kova [i2] ka f atëherë
    kthimi i Vërtetë;
kthimi i rremë;

Code:

fshini

algoritmi:

f = gjurmët e gishtit (x);
i1 = hash (x);
i2 = i1 ⊕ hash (f);
nëse kova [i1] ose kova [i2] ka f atëherë
   hiqni një kopje të f nga kjo kovë;
   kthimi i Vërtetë;
kthimi i rremë;

Code:

Testi i Performancës

Kam përdorur bibliotekën Will Fitzgerald për provën në filtrin Bloom. Racioni i FPP (Problemi Falas Pozitiv Falas) i marrë për filtrin e gjelit është 0.001

Kompleksiteti hapësinor

Për sa i përket filtrave të kukut dhe lulëzimit, ato performojnë ndryshe me probabilitet të ndryshëm pozitiv të rremë. Kur probabiliteti i rremë pozitiv i filtrit është më pak se ose i barabartë me 3%, filtri i gjelit ka më pak copa për hyrje. Kur është më i lartë, filtri i lulëzimit ka më pak copa për hyrje.

Kompleksiteti kohor

Në hashjen e kurorës, futja e një elementi duket si shumë më e keqe se O (1) në rastin më të keq sepse mund të ketë shumë raste gjatë përplasjes, ku duhet të heqim një vlerë në mënyrë që të bëjmë vend për vlerën aktuale. Plus, nëse ekziston një cikël, e gjithë tabela duhet të rihapet.

Bërja e një analize kohore të të dy filtrave jep rezultatet e mëposhtme:

Gjatë këtij eksperimenti (duke mbajtur parasysh kodin tim mund të mos jetë plotësisht i optimizuar), filtrat e Bloom duket se performojnë jashtëzakonisht mirë në kompleksitetin hapësinor, duke zënë më pak hapësirë ​​për një numër të madh artikujsh. Filtri Cuckoo duket se funksionon më mirë në vendosjen e një numri të madh artikujsh, por pak më i ngadalshëm në kërkim (kohët e kërkimit) për shkak të zbatimit të tij.

konkluzion

Nuk do të merrja vërtet një anë në të cilin filtri të rekomandojë, unë mendoj se të dy kanë rastet e përdorimit të tyre. Filtrat e Bloom nuk mbështesin fshirjet sepse hashashi është i humbur dhe i pakthyeshëm. Megjithëse numërimi i filtrave të lulëzimit e zgjidh atë problem, filtrat e Cuckoo janë të dobishëm në rastin kur do të kërkonit fshirje. Sigurisht që filtrat Cuckoo japin një gabim kur filtri është i plotë, dhe kjo ka avantazhet e veta, ndërsa në një filtër Bloom, nuk ka kontroll mbi kapacitetin, ai thjesht rindezet mbi grupin ekzistues.

kod

Referencat

  • 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 Nëse keni ndonjë gabim me testet / zbatimin, ju lutem mos ngurroni të lini sugjerimin / komentet tuaja.