CUCKOO vs BLOOM filter, ó pheirspictíocht Gopher

San alt seo, tá mé ag iarraidh éifeacht scagaire cuach a chur i bhfeidhm agus a thástáil thar scagaire faoi bhláth. (Léigh an post roimhe seo ar Chord DHT, ag cur tábla hash dáilte i bhfeidhm i nGolang)

Réamhrá

Tá struchtúir sonraí dóchúla an-úsáideach, go háirithe nuair a bhíonn tacair mhóra sonraí á bpróiseáil. An chuid is mó de na hamanna, agus iad ag obair ar thaobh na sonraí de rudaí, ba mhaith le ceist shimplí “is é an rud nach bhfuil i láthair” a dhéanamh nó fiosrúchán “an rud atá ann cheana féin” a phróiseáil agus na sonraí fíor-ama á bpróiseáil. Abair gur mhaith leat ceisteanna a fhreagairt i bhfíor-am, cosúil le líon na n-éidí uathúla, na héadanna is minice, má tá ad seirbheáilte cheana féin d'úsáideoir, trí úsáid a bhaint as struchtúir sonraí dóchúla soláthraíonn siad bealach spáis-éifeachtach chun na ceisteanna seo a fhreagairt. Is é an cur chuige tipiciúil maidir le fiosrúcháin den sórt sin ná HashMap nó HashTable a úsáid, nó é a stóráil mar thaisce seachtrach (cosúil le redis), ach tá an fhadhb le tacair shonraí mhóra, ní féidir na struchtúir shimplí sonraí seo a chur i gcuimhne. Seo nuair a thagann struchtúir sonraí dóchúla i bhfeidhm mar gheall ar a gcuid buntáistí spáis agus ama.

Samplaí Úsáid cásanna

• Baineann Google Bigtable, Apache HBase agus Apache Cassandra, agus Postgresql úsáid as scagairí Bloom le háirithintí dioscaí a laghdú do shraitheanna nó colúin nach bhfuil ann. Cuireann seiceálacha costasacha ar dhioscaí go mór le feidhmíocht bunachar sonraí.
• Úsáideann Meánach scagairí Bloom le seiceáil an bhfuil earra molta cheana féin d'úsáideoir
• Úsáideann Ethereum scagairí Bloom chun logaí a aimsiú go tapa ar an Ethereum blockchain
• Úsáideadh brabhsálaí gréasáin Google Chrome chun scagaire Bloom a úsáid chun URLanna mailíseacha a aithint. Seiceáladh aon URL i dtús báire i gcoinne scagaire Bloom áitiúil, agus ní raibh seiceáil iomlán ar an URL a rinneadh (agus thug an t-úsáideoir rabhadh, má thug sé sin toradh dearfach ar ais) má sheol an scagaire Bloom toradh dearfach.

Cad atá i “gCuach”?

Tá scagairí faoi bhláth in a lán áiteanna chun ceisteanna den sórt sin a fhreagairt ar an ardán sonraí. Le déanaí, tháinig mé trasna ar an bpáipéar seo ar scagaire na Cuaiche a ghabh mo spéis. Deir an teideal féin, “Scagaire Cuckoo: Praiticiúil Níos Fearr ná Bloom”, mar sin shocraigh mé é a sheiceáil.

Feabhsaíonn scagairí cuach dearadh an scagaire bhláth trí scriosadh, trí chomhaireamh teoranta, agus trí dóchúlacht dhearfach bhréagach teorantach a thairiscint, agus castacht spáis den chineál céanna a choinneáil ag an am céanna. Baineann siad úsáid as hacaireacht na cuach chun imbhuailtí a réiteach agus go bunúsach is tábla hais cuach dlúth iad.

Tá scagairí cuach agus faoi bhláth úsáideach le haghaidh tástála ballraíochta socraithe nuair a bhíonn méid na sonraí bunaidh mór. Ní úsáideann an bheirt acu ach 7 giotán in aghaidh na hiontrála. Tá siad úsáideach freisin nuair is féidir oibríocht chostasach a sheachaint sula gcuirtear i gcrích í trí thástáil bhallraíochta socraithe. Mar shampla, sula bhfiosraítear bunachar sonraí, is féidir tástáil bhallraíochta socraithe a dhéanamh chun a fháil amach an bhfuil an réad inmhianaithe sa bhunachar sonraí fiú.

Algartam

Paraiméadair an Scagaire:
1. Dhá Fheidhm Hash: h1 agus h2
2. Eagar B le n buicéid. Is é B [i] a thabharfar ar an bhuicéad i-ú

Ionchur: L, liosta de na heilimintí atá le cur isteach sa scagaire cuach.

Algartam:
Cé nach bhfuil L folamh:
    Lig x a bheith ar an gcéad mhír sa liosta L. Bain x as an liosta.
    Má tá B [h1 (x)] folamh:
        áit x i B [h1 (x)]
    Eile, Má tá B [h2 (x) folamh]:
        cuir x i B [h2 (x)]
    Eile:
        Bíodh y mar an eilimint i B [h2 (x)].
        Cosc y go L
        cuir x i B [h2 (x)]

Cur i bhfeidhm

Is cosúil go bhfuil an cur i bhfeidhm simplí go leor, mar sin shocraigh mé air dul i ngleic leis agus comparáid a dhéanamh idir an éifeachtúlacht spáis / ama a chuirtear i gcomparáid le scagaire faoi bhláth. Is éard atá i gceist le scagaire na Cuaiche ná tábla haca Cuckoo a stórálann na ‘méarloirg’ a cuireadh isteach. Is teaghrán giotán é méarlorg earra a dhíorthaítear as hais na míre sin. Is éard atá i dtábla hash cuach ná raon buicéid ina ndéantar mír atá le cur isteach a mhapáil go dtí dhá bhuicéad fhéideartha bunaithe ar dhá fheidhm hash. Is féidir gach buicéad a chumrú chun líon athraitheach méarlorg a stóráil. De ghnáth, aithnítear scagaire Cuckoo de réir a mhéarloirg agus a mhéid buicéad. Mar shampla, is féidir le (2,4) siopaí scagaire Cuach 2 mhéarloirg fad giotán agus gach buicéad i dtábla haca na Cuaiche suas le 4 mhéarlorg a stóráil.

Cuir isteach

Algartam:

f = méarlorg (x);
i1 = hash (x);
i2 = i1 sh hash (f);

má tá iontráil folamh ag buicéad [i1] nó buicéad [i2] ansin
   cuir leis an bhuicéad sin;
   tuairisceán Arna dhéanamh;

Ní mór // míreanna atá ann cheana a athlonnú;
i = roghnaigh i1 nó i2 go randamach;
le haghaidh n = 0; n 
// Meastar go bhfuil Hashtable lán;
tuairisceán Teip;
Cód:
Cuardaigh
Algartam:
f = méarlorg (x);
i1 = hash (x);
i2 = i1 sh hash (f);
má bhíonn buicéad [i1] nó buicéad [i2] ansin
    tuairisceán Fíor;
ar ais Bréagach;
Cód:
Scrios
Algartam:
f = méarlorg (x);
i1 = hash (x);
i2 = i1 sh hash (f);
má bhíonn buicéad [i1] nó buicéad [i2] ansin
   bain cóip de f ón bhuicéad seo;
   tuairisceán Fíor;
ar ais Bréagach;
Cód:
Tástáil Feidhmíochta
Bainim úsáid as leabharlann Will Fitzgerald don tástáil ar Bloom filter. Is é 0.001 an chandam FPP (Dóchúlacht Bréagach Dearfach) a ghlactar le haghaidh scagaire na cuach
Coimpléascacht Spáis
Maidir leis an gcuach agus le scagairí faoi bhláth, déanann siad ar bhealach difriúil ag dóchúlachtaí dearfacha bréige éagsúla. Nuair a bhíonn an dóchúlacht dhearfach bréagach atá ag an scagaire níos lú ná 3% nó cothrom leis, tá níos lú giotán in aghaidh na hiontrála ag scagaire na cuach. Nuair a bhíonn sé níos airde, tá níos lú giotán in aghaidh na hiontrála sa scagaire faoi bhláth.
Coimpléascacht Ama
I hashú na cuach, is cosúil go bhfuil eilimint a chur isteach i bhfad níos measa ná O (1) sa chás is measa mar d'fhéadfadh go leor cásanna le linn imbhuailte, áit a gcaithfimid luach a bhaint chun spás a dhéanamh don luach reatha. Chomh maith leis sin, má tá timthriall ann caithfear an tábla iomlán a athshamhlú.
Mar thoradh ar anailís ama a dhéanamh ar an dá scagaire tá na torthaí seo a leanas:
Le linn an turgnaimh seo (ag cuimhneamh nach féidir mo chód a bharrfheabhsú go hiomlán), is cosúil go ndéanann scagairí Bloom go han-mhaith i gcoimpléasc spáis, rud a fhágann nach bhfuil mórán spáis ann do líon mór míreanna. Is cosúil go bhfeidhmíonn scagaire na cuach níos fearr nuair a chuirtear líon mór míreanna isteach, ach beagán níos moille i gcuardach (amanna cuardaigh) mar gheall ar a chur i bhfeidhm.
Tátal
Ní dhéanfainn taobh le scagaire le moladh, ní dóigh liom go bhfuil a gcásanna úsáide féin ag an mbeirt acu. Ní thacaíonn scagairí Bloom le scriosadh de bharr go bhfuil an t-amú ag cailliúint agus nach féidir teacht leis. Cé go réitíonn scagairí bloom an fhadhb sin, tá scagairí cuach úsáideach sa chás go dteastódh tú a scriosadh. Ar ndóigh, cuireann scagairí Cuach earráid ar fáil nuair a bhíonn an scagaire lán, agus tá buntáistí ag baint leis sin, ach i scagaire Bloom, níl aon smacht ar an acmhainn, ach déanann sé an t-eagar a athrú.
Cód
Tagairtí
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 Má fhaigheann tú aon rud cearr leis na tástálacha / cur i bhfeidhm, bíodh leisce ort do mholadh / do thuairimí a fhágáil.