CUCKOO-filter versus BLOOM, vanuit het perspectief van Gopher

In dit artikel probeer ik de efficiëntie van een koekoekfilter over een bloeifilter te implementeren en te testen. (Lees vorige post op Chord DHT, implementatie van een gedistribueerde hashtabel in Golang)

Invoering

Probabilistische gegevensstructuren zijn zeer nuttig, vooral bij het verwerken van grote gegevenssets. Meestal, terwijl je aan de gegevenskant van dingen werkt, zou je een eenvoudige "is het item niet aanwezig" of "is het item al aanwezig" willen zoeken tijdens het verwerken van de real-time gegevens. Stel dat u vragen in realtime wilt beantwoorden, zoals het aantal unieke ips, de meest voorkomende ips, als een advertentie al aan een gebruiker is weergegeven, met behulp van probabilistische gegevensstructuren een ruimte-efficiënte manier om deze vragen te beantwoorden. De typische aanpak voor dergelijke vragen zou zijn om een ​​HashMap of een HashTable te gebruiken, of het is een externe cache (zoals redis), maar het probleem is met grote datasets, deze eenvoudige gegevensstructuren passen niet in het geheugen. Dit is waar probabilistische gegevensstructuren een rol spelen vanwege hun ruimte- en tijdsvoordelen.

Voorbeeld use cases

  • Google Bigtable, Apache HBase en Apache Cassandra en Postgresql gebruiken Bloom-filters om het zoeken naar schijven voor niet-bestaande rijen of kolommen te verminderen. Het vermijden van kostbare zoekopdrachten op schijven verhoogt aanzienlijk de prestaties van een databasequerybewerking.
  • Medium gebruikt Bloom-filters om te controleren of een artikel al aan een gebruiker is aanbevolen
  • Ethereum gebruikt Bloom-filters om snel logs te vinden op de Ethereum-blockchain
  • De Google Chrome-webbrowser gebruikte een Bloom-filter om schadelijke URL's te identificeren. Elke URL werd eerst gecontroleerd aan de hand van een lokaal Bloom-filter, en alleen als het Bloom-filter een positief resultaat retourneerde, werd een volledige controle van de uitgevoerde URL uitgevoerd (en de gebruiker waarschuwde, als dat ook een positief resultaat opleverde)

Wat zit er in een "koekoek"?

We hebben op veel plaatsen Bloom-filters gebruikt voor het beantwoorden van dergelijke vragen op het dataplatform. Onlangs kwam ik dit artikel over het koekoekfilter tegen dat mijn interesse trok. De titel zelf zegt: "Koekoekfilter: praktisch beter dan Bloom", dus besloot ik het te bekijken.

Koekoekfilters verbeteren het ontwerp van het bloeifilter door verwijdering, beperkt tellen en een begrensde vals-positieve waarschijnlijkheid te bieden, met behoud van een vergelijkbare ruimtecomplexiteit. Ze gebruiken koekoekshash om botsingen op te lossen en zijn in wezen een compacte koekoekshashtafel.

Koekoek- en bloeifilters zijn allebei handig voor het testen van een bepaald lidmaatschap wanneer de oorspronkelijke gegevens groot zijn. Ze gebruiken beide slechts 7 bits per invoer. Ze zijn ook handig wanneer een dure operatie kan worden vermeden voorafgaand aan uitvoering door een ingestelde lidmaatschapstest. Voordat u bijvoorbeeld een database opvraagt, kan een ingestelde lidmaatschapstest worden uitgevoerd om te zien of het gewenste object zich zelfs in de database bevindt.

Algoritme

Parameters van het filter:
1. Twee hashfuncties: h1 en h2
2. Een array B met n emmers. De i-de bucket wordt B [i] genoemd

Input: L, een lijst met elementen die in het koekoekfilter moeten worden ingevoegd.

Algoritme:
Terwijl L niet leeg is:
    Laat x het eerste item zijn in de lijst L. Verwijder x uit de lijst.
    Als B [h1 (x)] leeg is:
        plaats x in B [h1 (x)]
    Anders, als B [h2 (x) leeg is]:
        plaats x in B [h2 (x)]
    Anders:
        Laat y het element zijn in B [h2 (x)].
        Zet y voor op L
        plaats x in B [h2 (x)]

Implementatie

De implementatie lijkt vrij eenvoudig, dus ik besloot het te proberen en te vergelijken hoe efficiënt ruimte / tijd is vergeleken met een bloeifilter. Het koekoekfilter bestaat uit een koekoek-hashtabel waarin de ‘vingerafdrukken’ van ingevoerde items worden opgeslagen. De vingerafdruk van een item is een bitstring die is afgeleid van de hash van dat item. Een koekoekshashtabel bestaat uit een reeks emmers waarbij een in te voegen item wordt toegewezen aan twee mogelijke emmers op basis van twee hashfuncties. Elke emmer kan worden geconfigureerd om een ​​variabel aantal vingerafdrukken op te slaan. Een koekoekfilter wordt meestal geïdentificeerd door zijn vingerafdruk en emmergrootte. Een (2,4) koekoekfilter slaat bijvoorbeeld vingerafdrukken van 2 bit lengte op en elke emmer in de koekoekstabel kan maximaal 4 vingerafdrukken opslaan.

Invoeging

Algoritme:

f = vingerafdruk (x);
i1 = hash (x);
i2 = i1 ⊕ hash (f);
als bucket [i1] of bucket [i2] een lege invoer heeft
   voeg f toe aan die emmer;
   terug Klaar;
// moet bestaande items verplaatsen;
i = kies willekeurig i1 of i2;
voor n = 0; n 
// Hashtable wordt als vol beschouwd;
terugkeer mislukt;

Code:

Zoeken

Algoritme:

f = vingerafdruk (x);
i1 = hash (x);
i2 = i1 ⊕ hash (f);
als bucket [i1] of bucket [i2] f heeft
    Waar terug;
return False;

Code:

Delete

Algoritme:

f = vingerafdruk (x);
i1 = hash (x);
i2 = i1 ⊕ hash (f);
als bucket [i1] of bucket [i2] f heeft
   verwijder een kopie van f uit deze emmer;
   Waar terug;
return False;

Code:

Prestatie test

Ik heb de Will Fitzgerald-bibliotheek gebruikt voor de test op het Bloom-filter. Het FPP (False Positive Probability) rantsoen genomen voor koekoekfilter is 0.001

Complexiteit van de ruimte

Met betrekking tot de koekoek- en bloeifilters presteren ze anders met verschillende vals-positieve kansen. Wanneer de vals-positieve waarschijnlijkheid van het filter kleiner is dan of gelijk is aan 3%, heeft het koekoekfilter minder bits per invoer. Als het hoger is, heeft het bloeifilter minder bits per invoer.

Tijd Complexiteit

In koekoekshash lijkt het invoegen van een element in het ergste geval veel slechter dan O (1) omdat er tijdens een botsing veel gevallen kunnen zijn, waarbij we een waarde moeten verwijderen om ruimte te maken voor de huidige waarde. Plus, als er een cyclus is, moet de hele tabel opnieuw worden gewassen.

Een tijdanalyse van beide filters levert de volgende resultaten op:

Gedurende dit experiment (rekening houdend met mijn code die mogelijk niet volledig is geoptimaliseerd), lijken Bloom-filters uitzonderlijk goed te presteren in ruimtecomplexiteit en minder ruimte in te nemen voor een groot aantal items. Koekoekfilter lijkt beter te presteren bij het invoegen van een groot aantal items, maar een beetje langzamer in het opzoeken (zoektijden) vanwege de implementatie ervan.

Gevolgtrekking

Ik zou niet echt een kant kiezen die filter aan te bevelen, ik denk dat ze allebei hun eigen gebruik hebben. Bloom-filters ondersteunen geen verwijderingen omdat hashing verliesgevend en onomkeerbaar is. Hoewel het tellen van bloeifilters dat probleem oplost, zijn koekoekfilters handig in het geval dat je verwijderingen nodig hebt. Natuurlijk geven koekoekfilters een foutmelding wanneer het filter vol is, en dat heeft zijn eigen voordelen, terwijl in een Bloom-filter geen controle over de capaciteit is, het hasht gewoon over de bestaande bitarray.

Code

Referenties

  • 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 Als u iets mis vindt met de tests / implementatie, kunt u uw suggestie / opmerkingen achterlaten.