Filtr CUCKOO vs. BLOOM, z pohledu Gophera

V tomto článku se snažím implementovat a otestovat účinnost kukačového filtru na květovém filtru. (Přečtěte si předchozí příspěvek o Chord DHT, implementaci distribuované hashovací tabulky v Golangu)

Úvod

Pravděpodobnostní datové struktury jsou velmi užitečné, zejména při zpracování velkých datových souborů. Většinou, při práci na datové straně věcí, jeden by chtěl udělat jednoduchý “je položka není přítomná” nebo “je položka již přítomná” dotaz při zpracování dat v reálném čase. Řekněme, že chcete odpovídat na dotazy v reálném čase, jako je počet jedinečných ips, nejčastějších ips, pokud již byla reklama uživateli zobrazena, pomocí pravděpodobnostních datových struktur je prostorově efektivní způsob, jak na tyto dotazy odpovědět. Typickým přístupem k takovým dotazům by bylo použití buď HashMap nebo HashTable, nebo uložení nějaké externí mezipaměti (jako je redis), ale problém je s velkými datovými sadami, tyto jednoduché datové struktury se nevejdou do paměti. Zde přicházejí do hry pravděpodobnostní datové struktury kvůli jejich prostorovým a časovým výhodám.

Příklad použití

  • Google Bigtable, Apache HBase a Apache Cassandra a Postgresql používají filtry Bloom ke snížení vyhledávání na disku pro neexistující řádky nebo sloupce. Vyhýbání se nákladným vyhledáváním disku výrazně zvyšuje výkon operace dotazu na databázi.
  • Médium používá filtry Bloom ke kontrole, zda již byl některý článek uživateli doporučen
  • Ethereum používá Bloom filtry pro rychlé nalezení logů na blockchainu Ethereum
  • Webový prohlížeč Google Chrome používal k identifikaci škodlivých adres URL filtr Bloom. Jakákoli adresa URL byla nejprve zkontrolována proti místnímu filtru Bloom a pouze v případě, že filtr Bloom vrátil pozitivní výsledek, byla provedena úplná kontrola adresy URL (a uživatel varoval, pokud to také vrátilo pozitivní výsledek)

Co je v „kukačce“?

K zodpovězení takových dotazů na datové platformě jsme použili blokové filtry na mnoha místech. Nedávno jsem narazil na tento dokument na kukačkovém filtru, který mě zaujal. Samotný název říká: „Kukačkový filtr: Prakticky lepší než květ“, tak jsem se rozhodl to zkontrolovat.

Kukační filtry zlepšují konstrukci blokového filtru tím, že nabízejí deleci, omezené počítání a omezenou falešnou pozitivní pravděpodobnost, přičemž si stále zachovávají podobnou prostorovou složitost. Používají kukačky hash k řešení kolizí a jsou v podstatě kompaktní kukačka hash tabulky.

Filtry kukačky a bloom jsou užitečné pro testování členství v sadě, když je velikost původních dat velká. Oba používají pouze 7 bitů na záznam. Jsou také užitečné, když lze nákladným operacím zabránit před provedením testu stanoveného členství. Například před dotazováním na databázi je možné provést test nastavení členství, aby se zjistilo, zda je požadovaný objekt dokonce v databázi.

Algoritmus

Parametry filtru:
1. Dvě hashovací funkce: h1 a h2
2. Pole B s n kbelíky. I-té vědro se bude jmenovat B [i]

Vstup: L, seznam prvků, které mají být vloženy do kukačového filtru.

Algoritmus:
Zatímco L není prázdné:
    Nechť x je první položka v seznamu L. Odebrat x ze seznamu.
    Pokud je B [h1 (x)] prázdné:
        místo x v B [h1 (x)]
    Jinak, pokud B [h2 (x) je prázdný]:
        místo x v B [h2 (x)]
    Jiný:
        Nechť y je prvek v B [h2 (x)].
        Připravte y na L
        místo x v B [h2 (x)]

Implementace

Implementace se zdá docela přímočará, a tak jsem se rozhodl jít na to a porovnat, jak je časově a časově efektivní ve srovnání s blokovým filtrem. Filtr Cuckoo se skládá z tabulky hashů Cuckoo, která ukládá „otisky prstů“ vložených položek. Otisk prstu položky je bitový řetězec odvozený od hashe této položky. Tabulka s kukačkou hash se skládá z řady kbelíků, kde je položka, která má být vložena, mapována do dvou možných kbelíků na základě dvou hašovacích funkcí. Každý kbelík může být nakonfigurován tak, aby ukládal proměnný počet otisků prstů. Filtr Kukačka je obvykle identifikován podle otisku prstu a velikosti kbelíku. Například (2,4) kukačový filtr ukládá otisky prstů o délce 2 bitů a každý kbelík v hašovací tabulce Cuckoo může uložit až 4 otisky prstů.

Vložení

Algoritmus:

f = otisk prstu (x);
i1 = hash (x);
i2 = i1 ⊕ hash (f);
pokud má kbelík [i1] nebo kbelík [i2] prázdný záznam, pak
   přidat f do tohoto kbelíku;
   návrat Hotovo;
// musí přemístit existující položky;
i = náhodně vybrat i1 nebo i2;
pro n = 0; n 
// Hashtable je považován za plný;
vrácení selhání;

Kód:

Vyhledávání

Algoritmus:

f = otisk prstu (x);
i1 = hash (x);
i2 = i1 ⊕ hash (f);
pokud má kbelík [i1] nebo kbelík [i2] f
    návrat True;
return False;

Kód:

Odstranit

Algoritmus:

f = otisk prstu (x);
i1 = hash (x);
i2 = i1 ⊕ hash (f);
pokud má kbelík [i1] nebo kbelík [i2] f
   vyjměte kopii f z tohoto kbelíku;
   návrat True;
return False;

Kód:

Zkouška výkonu

K testu filtru Bloom jsem použil knihovnu Will Fitzgerald. Poměr FPP (falešná pozitivní pravděpodobnost) odebraný pro kukační filtr je 0,001

Vesmírná složitost

Pokud jde o kukačkové a květové filtry, působí odlišně při různých falešně pozitivních pravděpodobnostech. Když je falešná pozitivní pravděpodobnost filtru menší nebo rovna 3%, má kukačkový filtr méně bitů na vstup. Pokud je vyšší, má bloomový filtr méně bitů na položku.

Časová složitost

Při hašování kukačky se vkládání prvku jeví jako mnohem horší než O (1) v nejhorším případě, protože během kolize může nastat mnoho případů, kdy musíme odstranit hodnotu, abychom vytvořili prostor pro aktuální hodnotu. Navíc, pokud existuje cyklus, musí být celý stůl znovu naředěn.

Provedení časové analýzy obou filtrů přinese následující výsledky:

Během tohoto experimentu (mějte na paměti, že můj kód nemusí být plně optimalizován) se zdá, že Bloom filtry fungují mimořádně dobře ve složitosti vesmíru a zabírají menší množství místa pro velký počet položek. Zdá se, že kukačový filtr má lepší výkon při vkládání velkého počtu položek, ale díky pomalému vyhledávání (doba vyhledávání) je díky implementaci trochu pomalejší.

Odvození

Opravdu bych se nechtěl postarat o to, na kterém filtr doporučit, myslím, že oba mají své vlastní případy použití. Bloomové filtry nepodporují odstranění, protože hashování je ztrátové a nevratné. Ačkoli tento problém spočívá v počítání blokových filtrů, jsou kukačkové filtry užitečné v případě, že byste vyžadovali odstranění. Kuckoo filtry samozřejmě dávají chybu, když je filtr plný, a to má své vlastní výhody, zatímco u Bloom filtru neexistuje žádná kontrola nad kapacitou, pouze se znovu nacvičuje přes existující bitové pole.

Kód

Reference

  • 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 Pokud zjistíte něco špatného s testy / implementací, neváhejte a zanechte svůj návrh / připomínky.