„CUCKOO vs BLOOM“ filtras iš „Gopher“ perspektyvos

Šiame straipsnyje aš bandau įdiegti ir išbandyti gegutės filtro efektyvumą per žydėjimo filtrą. (Perskaitykite ankstesnį pranešimą apie „Chord DHT“, įgyvendindami paskirstytos maišos lentelę Golange)

Įvadas

Tikimybinės duomenų struktūros yra labai naudingos, ypač tvarkant didelius duomenų rinkinius. Dažniausiai dirbdami su duomenų duomenų puse, norėdami atlikti duomenis realiuoju laiku, norėtumėte atlikti paprastą užklausą „ar prekės nėra“ arba „ar prekės jau nėra“. Tarkime, kad norite atsakyti į užklausas realiu laiku, pvz., Unikalių IP skaičių, dažniausiai pasitaikančių IP, jei skelbimas jau buvo pateiktas vartotojui, tikimybinių duomenų struktūrų naudojimas yra efektyvus erdvės būdas atsakyti į šias užklausas. Įprastas tokių užklausų būdas būtų naudoti „HashMap“ arba „HashTable“ arba laikyti tam tikrą išorinę talpyklą (pvz., Perdaryti), tačiau problema kyla dėl didelių duomenų rinkinių, šios paprastos duomenų struktūros negali tilpti į atmintį. Čia tikimybinės duomenų struktūros yra svarbios dėl jų erdvės ir laiko pranašumų.

Pavyzdys Naudojimo atvejai

  • „Google Bigtable“, „Apache HBase“ ir „Apache Cassandra“ ir „Postgresql“ naudoja „Bloom“ filtrus, kad sumažintų neegzistuojančių eilučių ar stulpelių paiešką diske. Vengiant brangių disko paieškų žymiai padidėja duomenų bazės užklausos operacija.
  • Jei norite patikrinti, ar straipsnis vartotojui jau buvo rekomenduotas, terpė naudoja „Bloom“ filtrus
  • „Ethereum“ naudoja „Bloom“ filtrus, kad greitai rastų žurnalus „Ethereum“ grandinėje
  • „Google Chrome“ žiniatinklio naršyklė naudojo „Bloom“ filtrą kenksmingiems URL nustatyti. Bet kuris URL pirmiausia buvo patikrintas naudojant vietinį „Bloom“ filtrą ir tik tada, jei „Bloom“ filtras pateikė teigiamą rezultatą, buvo atliktas visas URL patikrinimas (ir vartotojas perspėjo, jei taip pat buvo gautas teigiamas rezultatas).

Kas yra „gegutė“?

Atsakydami į tokias užklausas duomenų platformoje daugelyje vietų naudojome žydėjimo filtrus. Neseniai susidūriau su šiuo dokumentu apie gegutės filtrą, kuris sudomino. Pats pavadinimas sako: „Gegutės filtras: praktiškai geriau nei žydi“, todėl nusprendžiau patikrinti.

Gegutės filtrai pagerina žydėjimo filtro dizainą, nes juos galima ištrinti, ribotai suskaičiuoti ir apriboti klaidingai teigiama tikimybe, išlaikant panašų erdvės sudėtingumą. Jie naudoja kaukių maigymą, kad išspręstų susidūrimus, ir iš esmės yra kompaktiškas gegutės maišos stalas.

Gegutės ir žydėjimo filtrai yra naudingi atliekant narystės testus, kai pradinių duomenų dydis yra didelis. Jie abu naudoja tik 7 bitus viename įraše. Jie taip pat yra naudingi, kai prieš atliekant nustatytą narystės testą galima išvengti brangios operacijos. Pvz., Prieš pateikdami užklausą duomenų bazėje, galite atlikti nustatytą narystės testą, norėdami pamatyti, ar norimas objektas yra net duomenų bazėje.

Algoritmas

Filtro parametrai:
1. Dvi maišos funkcijos: h1 ir h2
2. Masyvas B su n kaušais. I-asis kaušas bus vadinamas B [i]

Įvestis: L, elementų, kuriuos reikia įterpti į gegutės filtrą, sąrašas.

Algoritmas:
Nors L nėra tuščias:
    Tegul x yra pirmasis elementas sąraše L. Pašalinkite x iš sąrašo.
    Jei B [h1 (x)] tuščias:
        padėkite x į B [h1 (x)]
    Kita, jei B [h2 (x) tuščias]:
        padėkite x į B [h2 (x)]
    Kitas:
        Tegul y yra elementas B [h2 (x)].
        Pridėkite y iki L
        padėkite x į B [h2 (x)]

Įgyvendinimas

Įdiegimas atrodo gana nesudėtingas, todėl nusprendžiau pasidairyti ir palyginti, koks yra vietos / laiko efektyvumas, palyginti su žydėjimo filtru. Kaukazo filtrą sudaro gegutės maišos lentelė, kurioje saugomi įterptų daiktų „pirštų atspaudai“. Prekės pirštų atspaudas yra šiek tiek eilutės, gautos iš to daikto maišos. Gegutės maišos lentelę sudaro daugybė kibirų, kur įdėtas daiktas yra susiejamas su dviem įmanomais kibirėliais, remiantis dviem maišos funkcijomis. Kiekvieną kibirą galima sukonfigūruoti taip, kad būtų saugomas kintamas pirštų atspaudų skaičius. Paprastai gegutės filtras identifikuojamas pagal jo pirštų atspaudus ir kaušo dydį. Pvz., (2,4) gegutės filtruose saugomi 2 bitų ilgio pirštų atspaudai, o kiekvienas kaušas kaukės maišos lentelėje gali būti iki 4 pirštų atspaudų.

Įterpimas

Algoritmas:

f = pirštų atspaudas (x);
i1 = maišos (x);
i2 = i1 ⊕ maišos (f);
jei kibiras [i1] arba kibiras [i2] turi tuščią įrašą, tada
   pridėkite f į tą kibirą;
   grįžti Atlikta;
// turi perkelti esamus elementus;
i = atsitiktinai pasirenka i1 arba i2;
kai n = 0; n 
// „Hashtable“ laikomas pilnu;
grąžinimo gedimas;

Kodas:

Paieška

Algoritmas:

f = pirštų atspaudas (x);
i1 = maišos (x);
i2 = i1 ⊕ maišos (f);
jei kaušas [i1] arba kibiras [i2] turi f, tada
    grąžinti Tiesa;
return False;

Kodas:

Ištrinti

Algoritmas:

f = pirštų atspaudas (x);
i1 = maišos (x);
i2 = i1 ⊕ maišos (f);
jei kaušas [i1] arba kibiras [i2] turi f, tada
   išimkite f kopiją iš šio kibiro;
   grąžinti Tiesa;
return False;

Kodas:

Našumo testas

„Bloom“ filtro testui naudojau Willo Fitzgeraldo biblioteką. Gegutės filtrui naudojamas FPP (False Positive Probability) santykis yra 0,001

Erdvės sudėtingumas

Su gegutės ir žydėjimo filtrais jie veikia skirtingai, esant skirtingoms klaidingoms teigiamoms tikimybėms. Kai klaidingai teigiama filtro tikimybė yra mažesnė arba lygi 3%, gegutės filtre yra mažiau bitų viename įraše. Kai jis aukštesnis, žydėjimo filtras turi mažiau bitų viename įraše.

Laiko sudėtingumas

Maišant gegutę, blogesniu atveju įterpti elementą atrodo daug blogiau nei O (1), nes susidūrimo metu gali būti daug atvejų, kai turime pašalinti vertę, kad būtų vietos dabartinei vertei. Be to, jei yra ciklas, tada visa lentelė turi būti atnaujinta.

Atlikus abiejų filtrų laiko analizę, gaunami šie rezultatai:

Viso šio eksperimento metu (turint omenyje, kad mano kodas gali būti nevisiškai optimizuotas), atrodo, kad „Bloom“ filtrai ypač gerai atlieka erdvės sudėtingumą, užimdami mažiau vietos daugybei elementų. Atrodo, kad gegutės filtras geriau veikia įdedant daug daiktų, tačiau dėl įdiegimo jis yra šiek tiek lėtesnis (paieškos laikas).

Išvada

Aš tikrai nesiimčiau pusės, kurį filtrą rekomenduoti, manau, kad jie abu turi savo naudojimo atvejus. Žiedų filtrai nepalaiko trynimų, nes maišos yra nuostolingos ir negrįžtamos. Nors skaičiavimas žydėjimo filtrų išsprendžia šią problemą, gegutės filtrai yra naudingi tuo atveju, jei jums reikėtų ištrinti. Kaukazo filtrai, be abejo, pateikia klaidą, kai filtras yra pilnas, ir tai turi savų pranašumų, tuo tarpu „Bloom“ filtruose nekontroliuojama talpa, jis tiesiog perskaito esamą bitų masyvą.

Kodas

Nuorodos

  • 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 Jei pastebite, kad bandymuose / įgyvendinime yra kažkas negero, nedvejodami palikite savo pasiūlymą / komentarus.