Filtrul CUCKOO vs BLOOM, din perspectiva lui Gopher

În acest articol, încerc să pun în aplicare și să testez eficiența unui filtru cu cuc peste un filtru în floare. (Citiți postarea anterioară pe Chord DHT, punând în aplicare o tabelă de hash distribuită în Golang)

Introducere

Structurile de date probabilistice sunt foarte utile, mai ales atunci când prelucrează seturi mari de date. De cele mai multe ori, în timp ce se lucrează la partea de date a lucrurilor, s-ar dori să se facă o simplă interogare „este elementul care nu este prezent” sau „este elementul deja prezent” în timp ce se procesează datele în timp real. Spuneți că doriți să răspundeți la întrebări în timp real, cum ar fi numărul de ips unici, cei mai frecventi ips, dacă un anunț a fost deja difuzat unui utilizator, folosind structuri de date probabilistice oferă un mod eficient de spațiu pentru a răspunde la aceste întrebări. Abordarea tipică a unor astfel de întrebări ar fi să folosești fie un HashMap, fie un HashTable, sau să stochezi un cache extern (cum ar fi redis), dar problema este cu seturi de date mari, aceste simple structuri de date nu se pot încadra în memorie. Aici intră în joc structurile de date probabilistice datorită avantajelor în spațiu și timp.

Exemplu Utilizați cazuri

  • Google Bigtable, Apache HBase și Apache Cassandra și Postgresql folosesc filtre Bloom pentru a reduce căutările pe disc pentru rânduri sau coloane inexistente. Evitarea căutărilor pe discuri costisitoare crește considerabil performanța unei operațiuni de interogare a bazelor de date.
  • Mediu folosește filtrele Bloom pentru a verifica dacă un articol a fost deja recomandat unui utilizator
  • Ethereum folosește filtrele Bloom pentru a găsi rapid jurnalele pe blockchain-ul Ethereum
  • Navigatorul web Google Chrome a folosit un filtru Bloom pentru identificarea adreselor URL rău intenționate. Orice adresă URL a fost verificată pentru prima dată cu un filtru Bloom local și numai dacă filtrul Bloom a returnat un rezultat pozitiv a fost o verificare completă a adresei URL efectuate (iar utilizatorul a avertizat, dacă și asta a returnat un rezultat pozitiv)

Ce se află într-un „Cuc”?

Am utilizat filtre floare în multe locuri pentru a răspunde la astfel de întrebări pe platforma de date. De curând am dat această hârtie cu filtrul Cuckoo care mi-a atras interesul. Titlul în sine spune: „Cuckoo Filter: Practically Better than Bloom”, așa că am decis să îl verific.

Filtrele cu cuc îmbunătățesc odată cu proiectarea filtrului în floare, oferind ștergerea, numărarea limitată și o probabilitate falsă falsă delimitată, păstrând în același timp o complexitate spațială similară. Folosesc hașa cucului pentru a rezolva coliziunile și sunt, în esență, o masă compactă de hașa cu cuc.

Filtrele cu cuc și floare sunt utile pentru testarea apartenenței atunci când dimensiunea datelor originale este mare. Ambii folosesc doar 7 biți pe intrare. De asemenea, sunt utile când o operație costisitoare poate fi evitată înainte de execuție printr-un test de membru stabilit. De exemplu, înainte de interogarea unei baze de date, se poate face un test de membru stabilit pentru a vedea dacă obiectul dorit este chiar în baza de date.

Algoritmul

Parametrii filtrului:
1. Două funcții Hash: h1 și h2
2. Un tablou B cu n găleți. Galeata I-a se va numi B [i]

Intrare: L, o listă de elemente care trebuie introduse în filtrul cu cuc.

algoritm:
În timp ce L nu este gol:
    Fie x primul element din listă L. Eliminați x din listă.
    Dacă B [h1 (x)] este gol:
        loc x în B [h1 (x)]
    Altfel, Dacă B [h2 (x) este gol]:
        loc x în B [h2 (x)]
    Else:
        Fie y elementul din B [h2 (x)].
        Pregătiți y până la L
        loc x în B [h2 (x)]

Punerea în aplicare

Implementarea pare destul de simplă, așa că am decis să mă ocup de ea și să compar cât de eficient este spațiul / timpul în comparație cu un filtru în floare. Filtrul Cuckoo constă dintr-o tabelă de hash Cuckoo care stochează „amprentele” articolelor inserate. Amprenta unui articol este un șir de biți derivat din hașa acelui element. O tabelă de hash cu cuc constă dintr-o serie de găleți în care un element care trebuie inserat este asociat cu două găleți posibile, bazate pe două funcții de hași. Fiecare găleată poate fi configurată pentru a stoca un număr variabil de amprente. De obicei, un filtru Cucu este identificat prin amprenta sa și dimensiunea găleții. De exemplu, un (2,4) filtru Cuckoo stochează amprente digitale de 2 biți și fiecare găleată din tabelul cu hash Cuckoo poate stoca până la 4 amprente.

inserare

algoritm:

f = amprentă (x);
i1 = hash (x);
i2 = i1 ⊕ hash (f);
dacă găleata [i1] sau găleata [i2] au o intrare goală atunci
   se adaugă f la acea găleată;
   întoarceți Done;
// trebuie să mute elementele existente;
i = alegeți aleatoriu i1 sau i2;
pentru n = 0; n 
// Hashtable este considerat plin;
retur Eșec;

Cod:

Căutare

algoritm:

f = amprentă (x);
i1 = hash (x);
i2 = i1 ⊕ hash (f);
dacă găleata [i1] sau găleata [i2] au f atunci
    întoarce Adevărat;
returnare falsă;

Cod:

Șterge

algoritm:

f = amprentă (x);
i1 = hash (x);
i2 = i1 ⊕ hash (f);
dacă găleata [i1] sau găleata [i2] au f atunci
   scoateți o copie f din această găleată;
   întoarce Adevărat;
returnare falsă;

Cod:

Test de performanță

Am folosit biblioteca Will Fitzgerald pentru testul pe filtrul Bloom. Rația FPP (False Positive Probability) pentru filtrul cu cuc este 0,001

Complexitatea spațială

În ceea ce privește filtrele cu cuc și floare, acestea au un comportament diferit la diferite probabilități false pozitive. Când probabilitatea falsă pozitivă a filtrului este mai mică sau egală cu 3%, filtrul cu cuc are mai puțini biți pe intrare. Când este mai mare, filtrul în floare are mai puțini biți pe intrare.

Complexitatea timpului

În hashing cu cuc, introducerea unui element pare a fi mult mai rea decât O (1) în cel mai rău caz, deoarece ar putea exista multe cazuri în timpul coliziunii, unde trebuie să eliminăm o valoare pentru a face loc valorii curente. În plus, dacă există un ciclu, atunci întreaga tabelă trebuie reînnoită.

Făcând o analiză de timp a ambelor filtre, se obțin următoarele rezultate:

Pe parcursul acestui experiment (ținând cont de faptul că codul meu nu poate fi complet optimizat), filtrele Bloom par să funcționeze excepțional de bine în complexitatea spațiului, ocupând o cantitate mai mică de spațiu pentru un număr mare de articole. Filtrul cu cuc pare să funcționeze mai bine la introducerea unui număr mare de articole, dar puțin mai lent în căutare (timpii de căutare) datorită implementării acestuia.

deducție

Nu aș lua cu adevărat o parte a filtrului de recomandat, cred că amândoi au propriile lor cazuri de utilizare. Filtrele cu flori nu acceptă ștergeri, deoarece hashul este pierdut și ireversibil. Deși numărarea filtrelor în floare rezolvă această problemă, filtrele Cuckoo sunt utile în cazul în care ați solicita ștergeri. Desigur, filtrele Cuckoo dau o eroare atunci când filtrul este complet și asta are propriile avantaje, în timp ce într-un filtru Bloom, nu există control asupra capacității, doar reînnoiește asupra gamei de biți existente.

Cod

Referințe

  • 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 Dacă găsiți ceva în neregulă cu testele / implementarea, nu ezitați să lăsați sugestiile / comentariile.