Linear counting: het aantal unieke waarden schatten

Hoe zouden we het aantal unieke waarden in een bepaalde dataset kunnen tellen als er echt heel veel gegevens zijn? We kunnen bijvoorbeeld een dienst hebben die het aantal unieke gebruikers meet op een grote website, of gerust op het hele .nl/.com/.whatever-domein of iets dergelijks.

De naïeve aanpak

Oké, dat is toch niet moeilijk: we lopen gewoon de gegevens door en slaan elke waarde precies één keer op in een geschikte datastructuur. In Python zouden we het ongeveer zo kunnen schrijven (de code is onnodig breedsprakig, dat is met opzet):

nonunique_values = [1, 2, 3, 2, 2, 4, 1, 1, 3, 5, 2]

def count_unique(values):
    found = set()
    for item in values:
        if item not in found:
            found.add(item)
    return len(found)

print count_unique(nonunique_values) # 5

Het werkt. Prima, maar wat als de gegevens unieke v4-id's van 36 tekens zijn en er bijvoorbeeld tien miljoen van die unieke id's zijn? Nou ja… het programma berekent nog steeds de juiste waarde, maar hoeveel geheugen kost dat? We kunnen het proberen uit te rekenen. Voor de eenvoud nemen we aan dat we de uuid echt als een string van 36 tekens opslaan. Eén uuid neemt dan 36 bytes in, tien miljoen id's nemen 360 MB in (10 000 000 · 36 bytes).

Dat is eerlijk gezegd niet echt weinig. Als er honderd miljoen unieke id's waren, zouden we al in de gigabytes aan gebruikt geheugen belanden. En dan tellen we nog steeds alleen wat de gegevens zelf innemen. Tel er de overhead van bijvoorbeeld Python/JavaScript bij op en je kunt al met tien miljoen id's in de gigabytes terechtkomen:

Dat wil je niet. Hoe komen we daaruit?

We kunnen proberen de id's zelf efficiënter op te slaan, we kunnen in plaats van Python C gebruiken, waardoor het geheugengebruik fors daalt, maar het is nog steeds niet ideaal en zo'n programma zou nog altijd ontzettend veel ruimte innemen. Dan blijft de vraag: moeten we echt tot op de eenheid nauwkeurig weten of er precies 9 563 618 unieke waarden zijn? Zou er iets gebeuren als we met 9 547 666 zouden werken? Als je antwoord is dat dat wel zo is en dat je het precies wilt, ga je gang. Anders laten we werkwijzen zien om het aantal unieke waarden in een dataset zo nauwkeurig mogelijk, zo snel mogelijk en met minimaal geheugengebruik te schatten.

Hashfuncties — onze redding

We bekijken een hashfunctie die als invoer een string neemt en als uitvoer een getal van n bits teruggeeft. Als je gewend bent aan hashfuncties die een string “teruggeven”, stel je dan gewoon voor dat die string vervolgens weer in een getal wordt omgezet, daar is niets aan. Het aantal bits geeft aan hoe groot het getal is. Een 8-bits functie geeft een getal terug dat acht bits inneemt en in acht bits passen 2⁸ verschillende waarden, meestal de gehele getallen van 0 tot en met 255. We werken verder met een 24-bits hashfunctie. Zo'n functie geeft 2²⁴ verschillende waarden terug, dat is 16 777 216.

In plaats van de waarden zelf op te slaan, slaan we hun 24-bits hashes op. Om tien miljoen 24-bits hashes op te slaan hebben we 30 MB nodig (10 000 000 · 24 bit). Dat is een orde van grootte beter dan de eerdere 360 MB. De code zou er zo uit kunnen zien:

def nhash(item, n):
    return hash(item) % (2 ** n)

nonunique_values = [1, 2, 3, 2, 2, 4, 1, 1, 3, 5, 2]

def count_unique_using_nhash(values):
    found = set()
    for item in values:
        checksum = nhash(item, 24)
        if checksum not in found:
            found.add(checksum)
    return len(found)

print count_unique_using_nhash(nonunique_values) # 5

De functie hash is een ingebouwde functie van Python en geeft een geheel getal terug, de functie nhash toont een naïeve implementatie van een n-bits hashfunctie; het is niet belangrijk te begrijpen hoe die werkt, want ze werkt toch niet goed — het resultaat van die functie neemt geen 24 bits in, maar dat maakt nu niet uit, het gaat me om het principe.

Dan volgt de functie count_unique_using_nhash, die de unieke waarden telt. Ze loopt alle waarden door, berekent hun hash en slaat die op in de variabele found, als die waarde daar nog niet in zit.

Het probleem van deze aanpak is dat de hashfunctie voor verschillende strings dezelfde checksum kan teruggeven — er kan een botsing optreden. Hoe meer van zulke botsingen er optreden, hoe onnauwkeuriger het resultaat dat we krijgen. De functie count_unique_using_nhash geeft vrijwel altijd een kleiner aantal unieke waarden terug dan er in werkelijkheid zijn.

En welke hashfunctie kies je? Dat maakt niet zo veel uit, maar in het algemeen wordt een variant van MurmurHash aanbevolen.

Bitmaps

Heb je opgelet bij de basislessen programmeren in C? Zo ja, dan ken je bitmaps. Hoe kunnen we die gebruiken?

We schetsen het idee aan de hand van een array. We hoeven de berekende checksums namelijk niet te bewaren, we kunnen een array van lengte 2²⁴ maken en alle elementen op nul zetten. Zodra we dan een checksum tegenkomen — en dat is een getal! — schrijven we in deze array op index checksum een één, waarmee we noteren dat we deze checksum al hebben gevonden. Het aantal unieke elementen is dan bij benadering gelijk aan het aantal enen in deze array. De code zou er zo uit kunnen zien:

def count_unique_using_array(values):
    # lijst van lengte 2^24, geïnitialiseerd met allemaal nullen
    array = [0] * (2 ** 24) 
    for item in values:
        array[nhash(item, 24)] = 1
    return sum(array)

print count_unique_using_array(nonunique_values)

Een array gebruiken is in dit geval echter erg geheugenintensief, want in elke cel moeten we steeds een één of een nul opslaan. In plaats daarvan kunnen we een bitarray gebruiken. Om het te begrijpen: een geheel getal (integer) kan bijvoorbeeld in 32 bits worden opgeslagen. Als we het getal 354 omzetten naar het tweetallig stelsel, krijgen we 101100010. Het getal 354 zou in de computer als 32-bits integer zo zijn opgeslagen (op de details letten we niet, oké?):

00000000 00000000 00000001 01100010

Dat is een best fijn formaat dat we zouden kunnen gebruiken, toch? We willen in onze functie namelijk alleen enen en nullen opslaan en we hebben net ontdekt dat een gewoon getal eigenlijk niets anders is dan een hoop nullen en enen (net als alles in de computer…). Kortom, met behulp van bitoperatoren kunnen we een één zo opslaan dat hij echt maar één bit inneemt.

We gaan terug naar onze functie met de array. Als we die zouden herschrijven met bitarrays, zou voor een 24-bits hashfunctie een bitarray van 2²⁴ bits volstaan, dat is 2 MiB (2²⁴ bit). Dat is een flinke verbetering!

Bij een 32-bits hashfunctie, die 2³² verschillende uitvoerwaarden heeft, dat is 4 294 967 296, hebben we een bitarray van een halve gigabyte nodig. Dat is niet slecht, want daarmee kunnen we unieke waarden tellen tot ergens in de miljarden.

Linear counting

Ik heb al gezegd dat we met een hashfunctie slechts een schatting van het aantal unieke waarden krijgen. Die schatting is des te onnauwkeuriger naarmate het aantal unieke waarden dichter bij het aantal verschillende uitvoerwaarden van de hashfunctie komt. Het is logisch dat we bij een dataset met vijf miljard unieke waarden dat met een 24-bits hashfunctie gewoon niet kunnen tellen.

De schatting die we met hashfuncties berekenen, kan echter nog verder worden verfijnd. Daarvoor wordt een eenvoudig idee gebruikt — hoe meer unieke waarden er in de dataset zitten, hoe waarschijnlijker het is dat er na verloop van tijd botsingen ontstaan. (Botsing = twee verschillende invoeren hebben dezelfde uitvoer van de hashfunctie, dezelfde checksum.) Nu gaan we een beetje rekenen, daarom voeren we een paar variabelen in:

We werken met een n-bits hashfunctie h.
Het aantal mogelijke uitvoerwaarden van de functie h is dus gelijk aan 2ⁿ. Dat aantal noemen we m, dus: m=2ⁿ.
De bitarray waarin we bijhouden welke checksums we hebben gevonden, noemen we met een hoofdletter A. De array A heeft lengte m.
Als we met ons algoritme de hele dataset doorlopen, zijn sommige waarden in de bitarray nul en sommige één. Wij zijn vooral geïnteresseerd in de verhouding “aantal nullen gedeeld door de lengte van de array”, die ons het relatieve aandeel nullen in de bitarray geeft. Aan het begin is die verhouding gelijk aan 1, omdat de array met allemaal nullen is geïnitialiseerd. Als het fifty-fifty was, zou de verhouding gelijk zijn aan een half enzovoort. Deze waarde noemen we Z en we berekenen haar als Z = aantal nullen / m.

Op dit moment geldt: hoe hoger de waarde van Z, hoe zekerder we zijn dat onze schatting van het aantal unieke waarden nauwkeurig is. Als we bijvoorbeeld een lege dataset doorlopen, blijven er in de bitarray alleen nullen staan en is de waarde van Z gelijk aan één — dan weten we helemaal zeker dat er in onze dataset evenveel unieke elementen zitten als er enen in de bitarray staan — nul.

Als de waarde van Z gelijk is aan 0,99, betekent dat dat de bitarray voor een honderdste met enen is gevuld. 99% van de array bevat nullen. Dat is nog goed, het is waarschijnlijk dat er tijdens de berekening niet al te veel botsingen zijn opgetreden en dat er misschien geen of maar een minimale correctie nodig is. Is de waarde van Z echter gelijk aan 0,05, dan is maar 5% van de array nul gebleven en zijn we tijdens de berekening waarschijnlijk heel veel botsingen tegengekomen — er is dan een grote correctie nodig.

Maar hoe bereken je deze correctie? We nemen de logaritme te hulp, een functie die deze vorm heeft:

Wij kijken naar het rode deel op het interval ⟨0, 1]. Als we op de x-as de waarde Z uitzetten, bereiken we dat de waarde van y nul nadert naarmate Z hoger is. En omgekeerd — hoe kleiner Z, hoe kleiner de waarde van y. De uiteindelijke schatting berekenen we door dit getal met -m te vermenigvuldigen. Merk op dat we voor een voldoende lage waarde van Z een getal krijgen dat zelfs kleiner is dan -1, en als we die waarde met -m vermenigvuldigen, krijgen we een schatting die groter is dan m: we hebben geschat dat het aantal unieke waarden groter is dan het aantal mogelijke checksums dat uit de hashfunctie h kan komen.

De hele formule voor de berekening van het aantal p unieke waarden ziet er zo uit:

$p = - m \cdot \ln Z$

De implementatie (zonder bitarrays, alleen met gewone arrays) zou er zo uit kunnen zien:

from uuid import uuid4
from math import log

number_of_unique_values = 10000
nonunique_values = [uuid4() for _ in xrange(number_of_unique_values)]
nonunique_values += nonunique_values

def nhash(item, n):
    return hash(item) % (2 ** n)

def count_unique_using_array(values, n):
    array = [0] * (2 ** n)
    for item in values:
        array[nhash(item, n)] = 1
    return sum(array)

def linear_counting(values, n):
    estimate = count_unique_using_array(values, n)
    m = 2 ** n
    number_of_zeros = m - estimate
    Z = float(number_of_zeros) / m
    # log is hier de natuurlijke logaritme met grondtal e
    p = (-m) * log(Z)      
    p = int(round(p))
    print "Debug info: estimate=%s, m=%s, number_of_zeros=%s, Z=%s, p=%s" % \
          (estimate, m, number_of_zeros, Z, p)
    return p

print "Cardinality: %s" % linear_counting(nonunique_values, 16)

In de functie linear_counting berekenen we eerst een eerste schatting met het vorige algoritme, dat een n-bits hashfunctie gebruikt. Daarna berekenen we het aandeel nullen in de array en voeren we de correctie volgens de formule uit. De logaritme in de code is de natuurlijke logaritme. De variabele nonunique_values bevat number_of_unique_values unieke strings, in dit voorbeeld staan er dus tienduizend unieke waarden in de lijst nonunique_values. Die vreemde code op de zesde regel zorgt ervoor dat er in de array meer gelijke waarden zitten: we plakken gewoon dezelfde lijst waarden achter de lijst, zodat elke waarde twee keer in de array voorkomt. En dan gaan we tellen. Idealiter zou de functie moeten teruggeven dat de lijst tienduizend unieke waarden bevat. De uitvoer:

Debug info: estimate=9289, m=65536, number_of_zeros=56247, 
Z=0.858261108398, p=10017
Cardinality: 10017

Omdat er telkens een andere lijst nonunique_values wordt gegenereerd, verschillen de resultaten bij elke aanroep. We hebben een 16-bits hashfunctie gebruikt. We zien dat de eerste schatting van de functie count_unique_using_array was dat de lijst 9289 unieke waarden bevat. Die schatting hebben we met de correctie verfijnd tot 10 017, en dat is best behoorlijk: onze schatting is maar 0,17% te groot, terwijl ze eerst 7,11% te klein was — dat is nogal wat.

Als we een “grotere” hashfunctie nemen, bijvoorbeeld een 24-bits, krijgen we een nauwkeuriger resultaat:

Debug info: estimate=9997, m=16777216, number_of_zeros=16767219, 
Z=0.999404132366, p=10000
Cardinality: 10000

De oorspronkelijke schatting zelf was al prima; door de verfijning zijn we op precies tienduizend uitgekomen. Als demonstratie kunnen we een miljoen unieke id's proberen, dus number_of_unique_values = 1000000. Met een 24-bits hashfunctie komen we op deze resultaten:

Debug info: estimate=971033, m=16777216, number_of_zeros=15806183, 
Z=0.94212192297, p=1000267
Cardinality: 1000267

Dat gaat. En als we het als bitarray implementeren, zou de array maar de genoemde twee megabyte moeten opslokken (+ wat de taal erbij neemt). Wat mij betreft best goed. But we can do better! Much better. Maar dat is voor de volgende keer.

Ondertussen kun je het artikel A Linear-Time Probabilistic Counting Algorithm for Database Applications [PDF] lezen. Of je gaat verder met het volgende deel van de serie: het min-value-algoritme.

Hoofdstukken: Linear counting: het aantal unieke waarden schatten, Min value: het aantal unieke waarden schatten, LogLog: het aantal unieke waarden schatten, HyperLogLog: het aantal unieke waarden heel nauwkeurig schatten

« Vorige: Omzetting van een automaat naar een reguliere expressie

Volgende: Min value: het aantal unieke waarden schatten »