Serien om algoritmer for å anslå antall unike verdier i en multimengde fortsetter med en artikkel om state of the art-algoritmen HyperLogLog. Men alle tankene som ligger bak denne algoritmen, bygger på LogLog som vi beskrev tidligere, så hvis du vil lese videre, bør du forsikre deg om at du kjenner LogLog godt.

Algoritmen LogLog hadde to hovedproblemer:

Uteliggere

Det endelige anslaget fra LogLog er veldig følsomt for uteliggere (outliers), verdier som ligger veldig langt unna de andre verdiene. Det skjer typisk at de fleste maksimale lengdene av nullsuffiksene for hver gruppe er omtrent like, for eksempel mellom 12 og 15, men så — bang — har ett nullsuffiks lengde 27. Denne store forskjellen ødelegger det endelige anslaget på antall unike verdier, for det vanlige aritmetiske gjennomsnittet takler det ikke særlig godt. I bunn og grunn virket det samme prinsippet som når noen få toppledere og direktører løfter gjennomsnittslønnen i landet med de høye lønningene sine.

Forfatterne av algoritmen prøvde å løse det ved å kvitte seg med uteliggerne og ikke ta med noen av de høyeste maksimumene i gjennomsnittet, men det var ikke noen særlig god løsning. Senere prøvde de en annen framgangsmåte — i stedet for det aritmetiske gjennomsnittet brukte de det harmoniske gjennomsnittet, som har langt bedre egenskaper når vi har verdier som ligger langt fra gjennomsnittet.

Veldig dårlige resultater for små kardinaliteter

LogLog har fæle resultater når den skal anslå kardinaliteten til små multimengder. Hvis vi har noen få unike elementer i multimengden, gir LogLog oss et meningsløst stort anslag. Forfatterne løste det på en listig måte — når vi har en multimengde med lav kardinalitet som input, brukes ikke algoritmen LogLog, men en helt annen algoritme, nemlig den gamle kjente Linear counting. Ja, men hvordan finner vi ut at vi har en multimengde med liten kardinalitet som input, når vi nettopp ikke kjenner kardinaliteten?

Vi lar LogLog anslå antall unike elementer, og når vi ser at dette anslaget er relativt lavt, kaster vi anslaget og regner det ut på nytt med algoritmen Linear counting. Vi repeterer raskt hvordan Linear counting fungerer. I begynnelsen allokerer vi en (bit)vektor med nuller i en på forhånd gitt størrelse, typisk en potens av to. Vi går gjennom alle elementene i multimengden, regner ut hashen deres og gjør den om til et heltall i fra intervallet 0 til lengden av vektoren minus 1. På indeksen i lagrer vi så en ener i vektoren. Til slutt teller vi antall nuller og enere i vektoren og anslår kardinaliteten ved hjelp av en enkel formel.

Algoritmen LogLog bruker imidlertid ikke noen bitvektor der den «lagrer» de utregnede hashene. I stedet bruker den en tabell der den lagrer maksimale lengder av suffiksene. Tabellen kan for eksempel se slik ut:

[2, 5, 9, 0, 5, 4, 4, 0]

der hvert tall betegner den maksimale lengden av nullsuffikset i den gitte gruppen av utregnede hasher. En verdi som ikke er null på den i-te posisjonen betyr imidlertid nødvendigvis at det blant verdiene i multimengden finnes et element med (trebits) hash lik i. Med andre ord kan vi gjøre denne tabellen om til en bitvektor for linear counting ved å beholde nullene og gjøre hvert positivt tall om til en ener. Fra den forrige tabellen ville vi dermed fått bitvektoren:

[1, 1, 1, 0, 1, 1, 1, 0]

Nå kan vi bruke algoritmen Linear counting og anslå kardinaliteten med den.

Det er imidlertid en hake ved dette. Vi lagrer det maksimale nullsuffikset i tabellen, men hva om alle hashene i en gruppe av verdier ender på en ener? Hvis vi for eksempel bruker de tre siste bitene som identifikator for gruppen hashen tilhører, ville lengden av nullsuffikset til hashen «01001100» vært null — for vektoren «01001» ender på en ener. I tabellen med maksimumene ville vi dermed lagret null på indeks 4 (100₂=4₁₀). I algoritmen linear counting ville det vist seg slik at vi ikke har funnet noen verdi som har fire som hash, og det er ikke sant.

Derfor endrer vi algoritmen slik at den ikke lagrer lengden av det lengste nullsuffikset i tabellen med maksimumene, men indeksen til «den første eneren fra høyre» (for ordens skyld — vi indekserer fra én), og det er det samme som om vi la til én i lengden av nullsuffikset. Slik oppnår vi at en null på indeksen i betyr at ingen verdi har hash lik i, og en slik tabell kan vi da bruke til linear counting.

Implementasjon av HyperLogLog

Fint og pent, steg for steg:

def alpha(num_buckets):
    return (0.7213 / (1 + 1.079 / num_buckets))

Funksjonen alpha returnerer korreksjonen for det utregnede anslaget, det kjenner vi fra forrige gang, bare at alpha i tilfellet HyperLogLog har en annen verdi avhengig av antall grupper.

def trailing_zeroes(number):
    if number == 0: 
        return 0
    zeroes = 0
    while (number & 1) == 0:
        zeroes += 1
        number = number >> 1
    return zeroes

En funksjon som returnerer antall nullbits på slutten av tallet.

def count_maxims(values, k):
    num_buckets = 2 ** k  
    max_zeroes = [0] * num_buckets

    for value in values:
        h = hash(value)
        bucket_index = h & (num_buckets - 1)
        bucket_hash = h >> k
        num_zeros = trailing_zeroes(bucket_hash) + 1
        max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)

    return max_zeroes

En funksjon som går gjennom alle verdiene, deler dem i num_buckets grupper og for hver gruppe regner ut indeksen til den første eneren fra høyre (lengden av det maksimale nullsuffikset pluss én).

def linear_counting(number_of_ones, num_buckets):
    number_of_zeros = num_buckets - number_of_ones
    Z = float(number_of_zeros) / num_buckets
    p = (-num_buckets) * log(Z)
    return p

En lett endret funksjon for å regne ut algoritmen Linear counting.

def estimate_cardinality(values, k): 
    num_buckets = 2 ** k   
    max_zeroes = count_maxims(values, k)
    estimate = float(alpha(num_buckets) * (num_buckets**2)) / sum(2**(-r) for r in max_zeroes)
    number_of_ones = sum(1 if x > 0 else 0 for x in max_zeroes)

    if (estimate <= 2.5 * num_buckets) and (number_of_ones < num_buckets):
        return linear_counting(number_of_ones, num_buckets)
    else:
        return estimate

Hovedfunksjonen som setter alt sammen. Først regner den ut anslaget ved hjelp av den endrede LogLog, og i stedet for det aritmetiske gjennomsnittet bruker den på den fjerde linjen det harmoniske gjennomsnittet, og til slutt bruker den korreksjonen i form av Linear counting hvis det utregnede anslaget er mindre enn 2,5 ganger antall grupper (nå forventer vi at det vanlige anslaget fra LogLog er dårligere enn om vi hadde brukt Linear counting) og hvis det finnes minst én null i tabellen med maksimumene (en tabell som bare har enere, kan vi ikke bruke i Linear counting, se forrige artikkel). Og hva er resultatene til HyperLogLog?

Vi kjører testkode som anslår kardinaliteten til mengder som etter hvert har kardinalitet 10, 100, …, 1 000 000:

for x in range(1, 7):
    num_values = 10**x
    values = (str(uuid4()) for _ in xrange(num_values))
    cardinality = estimate_cardinality(values, 14)
    print "Cardinality: %s, relative error: %s" % (cardinality, num_values / cardinality)

Resultater:

Cardinality: 10.0030530001, relative error: 0.999694793165
Cardinality: 100.306423257, relative error: 0.996945128268
Cardinality: 1003.0892434, relative error: 0.99692027063
Cardinality: 10013.1348931, relative error: 0.998688233677
Cardinality: 100520.045562, relative error: 0.994826449206
Cardinality: 998088.420332, relative error: 1.0019152408

Vi ser at resultatene alltid avviker fra det riktige resultatet med mindre enn én prosent. Og det er bra!

Flere forbedringer av HyperLogLog

HyperLogLog har fått flere andre interessante forbedringer. Et av de gjenværende problemene er høy minnebruk. Det høres ganske rart ut, siden vi forrige gang priste minnebruken til skyene og regnet ut at 768 byte er nok til å lagre tabellen med maksimumene. Men problemet oppstår hvis du vil telle kardinaliteten ikke til én enorm multimengde, men parallelt til flere millioner små multimengder, eller hvis du vil beholde disse utregnede tabellene med maksimumene i en database for litt triksing senere.

Hvis vi for eksempel regnet ut kardinaliteten til én milliard multimengder samtidig, ville vi med den nåværende implementasjonen trengt 1 000 000 000 ganger 768 byte, som er 768 GB. På den ene siden er ikke det dårlig … men på den andre siden kan vi implementere HyperLogLog bedre.

Sparse representasjon

La oss tenke oss at vi setter k=12, altså bruker 12 bits til å identifisere grupper og dermed får 2¹² ulike grupper av hasher. I begynnelsen av algoritmen må vi allokere en tabell med lengde 4096 (se linje 3 i funksjonen count_maxims). La oss si at multimengden vår har tre ulike elementer. Det betyr at vi setter en verdi på tre ulike steder i tabellen, og de resterende 4093 verdiene i tabellen forblir null, de resterende 4093 har vi rett og slett ikke brukt til noe. Det er ikke særlig effektivt, ikke sant?

For å unngå å ha en tabell som for det meste er null og ubrukt, men som likevel tar opp en verdifull del av minnet, kan vi i begynnelsen lagre verdiene som par [indeks, verdi]. Et eksempel for bedre forståelse. Denne tabellen

[7, 0, 0, 0, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

kan vi representere langt mer minneeffektivt som to par:

[0, 7], [4, 12]

I stedet for å ha en haug med ubrukt plass allokert i minnet kan vi etter hvert allokere bare den plassen vi virkelig trenger. Denne representasjonen kaller vi sparse. Men på et tidspunkt ville denne representasjonen vært mer minnekrevende enn å lagre i en tabell — da kan vi gjøre den sparse representasjonen om til en vanlig tabell uten tap av informasjon.

Offset

Praksis har vist at alle verdiene i tabellen er omtrent like. Tabellen med maksimumene ser vanligvis for eksempel slik ut:

[12, 13, 11, 13, 15, 12, 14, 11, 12, ...,  13, 14, 11]

Alle verdiene ligger et sted rundt tallet 13. En annen strategi for å gjøre en slik tabell mindre er å trekke en fast verdi fra hvert element og huske den. Vi kan for eksempel trekke fra åtte:

[4, 5, 3, 5, 7, 4, 6, 3, 4, ..., 5, 6, 3]

Nå bruker hver verdi i tabellen mindre minne — i den første tabellen må vi lagre tall fra 0 til 15, og til det trenger vi 4 bits, mens vi for den andre tabellen klarer oss med 3 bits, for vi lagrer bare tall fra 0 til 7. Det forutsetter selvfølgelig at tabellen implementeres på nivå med enkeltbits. Når vi skal lese verdiene fra tabellen, må vi legge den noterte verdien til dem igjen.

…og en haug med andre forbedringer. Forskningen på dette området pågår fortsatt, så vi kan sikkert glede oss til flere interessante ideer. Neste gang skal vi snakke om union og snitt av HyperLogLog-vektorer, og en gang i nær framtid skal vi snakke om hvorfor det kan lønne seg å lagre milliarder av HyperLogLog-vektorer.

Lenker og kilder

• Hele implementasjonen min kan du se på GitHub.
• HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm [PDF] — den opprinnelige artikkelen der HyperLogLog ble presentert.
• HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm [PDF] — en forbedret versjon av den opprinnelige HyperLogLog, for eksempel med den nevnte sparse representasjonen.