Linear Counting: Wie man die Anzahl eindeutiger Werte schätzt

Wie könnten wir die Anzahl eindeutiger Werte in einem Datensatz zählen, wenn es wirklich sehr viele Daten wären? Wir könnten zum Beispiel einen Dienst haben, der die Anzahl eindeutiger Nutzer auf einer großen Website oder meinetwegen auf einer ganzen .de/.com/.whatever-Domain oder so ähnlich misst.

Der naive Ansatz

Ok, da gibt es doch nichts zu überlegen: Wir gehen einfach die Daten durch und speichern jeden Wert genau einmal in einer geeigneten Datenstruktur. In Python könnten wir das etwa so schreiben (der Code ist unnötig wortreich, das ist Absicht):

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

Es funktioniert. Na gut, aber was ist, wenn die Daten 36 Zeichen lange eindeutige v4-Bezeichner sind und es zum Beispiel zehn Millionen solcher eindeutigen IDs gibt? Nun … das Programm berechnet immer noch den richtigen Wert, aber wie viel Speicher belegt es? Das können wir ausrechnen. Der Einfachheit halber nehmen wir an, dass wir die UUID wirklich als String mit 36 Zeichen speichern. Eine UUID belegt also 36 Byte, zehn Millionen IDs belegen 360 MB.

Das ist, geben wir es zu, nicht gerade wenig. Wären es hundert Millionen eindeutige IDs, kämen wir schon in den Bereich von Gigabyte belegtem Speicher. Und dabei zählen wir noch rein das, was die Daten belegen. Rechne noch den Overhead dazu, den etwa Python/JavaScript belegt, und du kannst schon mit zehn Millionen IDs im Gigabyte-Bereich landen:

Das willst du nicht. Wie kommen wir da raus?

Wir können versuchen, die IDs selbst effizienter zu speichern, wir können statt Python C verwenden und damit den Speicherbedarf deutlich senken, aber das ist immer noch nicht das Wahre, und ein solches Programm würde noch immer unglaublich viel Platz belegen. Bleibt die Frage: Müssen wir wirklich haargenau wissen, ob es gerade 9.563.618 eindeutige Werte sind? Würde etwas passieren, wenn wir mit der Anzahl 9.547.666 arbeiteten? Wenn deine Antwort lautet, dass es etwas ausmacht und du es genau haben willst, dann bitte, wie du meinst. Andernfalls schauen wir uns Verfahren an, mit denen man die Anzahl eindeutiger Werte in einem Datensatz möglichst genau, möglichst schnell und mit minimalem Speicherbedarf schätzen kann.

Hashfunktionen – unsere Rettung

Wir betrachten eine Hashfunktion, die als Eingabe einen String bekommt und als Ausgabe eine n-Bit-Zahl liefert. Wenn du eher Hashfunktionen gewohnt bist, die einen String „zurückgeben“, stell dir einfach vor, dass dieser String anschließend noch in eine Zahl umgewandelt wird, das ist nichts Besonderes. Die Anzahl der Bits gibt dann an, wie groß die Zahl ist. Eine 8-Bit-Funktion liefert eine Zahl, die acht Bit belegt, und in acht Bit lassen sich 2⁸ verschiedene Werte speichern, typischerweise also die ganzen Zahlen von 0 bis 255. Wir arbeiten im Folgenden mit einer 24-Bit-Hashfunktion. Eine solche Funktion liefert 2²⁴ verschiedene Werte, das sind 16.777.216.

Statt die Werte selbst zu speichern, speichern wir ihre 24-Bit-Hashwerte. Für zehn Millionen 24-Bit-Hashwerte brauchen wir 30 MB. Das ist eine Größenordnung besser als die vorherigen 360 MB. Der Code könnte so aussehen:

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

Die Funktion hash ist eine native Python-Funktion und liefert eine ganze Zahl, die Funktion nhash zeigt eine naive Implementierung einer n-Bit-Hashfunktion; es ist nicht wichtig zu verstehen, wie sie funktioniert, denn sie funktioniert ohnehin nicht richtig – das Ergebnis dieser Funktion belegt nicht 24 Bit, aber das ist jetzt egal, mir geht es um das Prinzip.

Dann folgt die Funktion count_unique_using_nhash, die die eindeutigen Werte zählt. Sie geht alle Werte durch, berechnet ihren Hashwert und speichert ihn in der Variable found, falls dieser Wert dort noch nicht vorhanden ist.

Das Problem dieses Verfahrens ist, dass die Hashfunktion für verschiedene Strings dieselbe Checksum liefern kann – es kann zu einer Kollision kommen. Je mehr solche Kollisionen auftreten, desto ungenauer wird das Ergebnis. Die Funktion count_unique_using_nhash liefert fast immer eine kleinere Anzahl eindeutiger Werte, als es in Wirklichkeit gibt.

Und welche Hashfunktion soll man wählen? Das ist gar nicht so wichtig, aber allgemein wird irgendeine Variante von MurmurHash empfohlen.

Bitmaps

Hast du in den Grundlagen der Programmierung in C gut aufgepasst? Wenn ja, dann kennst du Bitmaps. Wie könnte man sie hier nutzen?

Die Idee skizzieren wir an einem Array. Wir müssen nämlich die berechneten Checksums gar nicht aufbewahren, wir können ein Array der Länge 2²⁴ anlegen und alle Elemente mit null initialisieren. Wenn wir dann auf irgendeine Checksum stoßen – das ist ja eine Zahl! –, schreiben wir in dieses Array am Index checksum eine Eins und markieren damit, dass wir diese Checksum schon gefunden haben. Die Anzahl der eindeutigen Elemente ist dann ungefähr gleich der Anzahl der Einsen in diesem Array. Der Code könnte so aussehen:

def count_unique_using_array(values):
    # Liste der Laenge 2^24, initialisiert mit lauter Nullen
    array = [0] * (2 ** 24) 
    for item in values:
        array[nhash(item, 24)] = 1
    return sum(array)

print count_unique_using_array(nonunique_values)

Ein Array zu verwenden ist in diesem Fall allerdings sehr speicherintensiv, weil wir in jeder Zelle entweder eine Eins oder eine Null speichern müssen. Stattdessen können wir ein Bit-Array verwenden. Damit du es verstehst: Eine ganze Zahl (Integer) lässt sich zum Beispiel in 32 Bit speichern. Wenn wir die Zahl 354 ins Binärsystem umrechnen, erhalten wir 101100010. Die Zahl 354 wäre im Computer als 32-Bit-Integer also so gespeichert (auf die Details pfeifen wir, ok?):

00000000 00000000 00000001 01100010

Das ist ein ziemlich nettes Format, das wir nutzen könnten, oder? Wir wollen in unserer Funktion nämlich nur Einsen und Nullen speichern, und eben haben wir herausgefunden, dass eine gewöhnliche Zahl nichts anderes ist als ein Haufen Nullen und Einsen (wie eigentlich alles im Computer …). Kurz gesagt: Mit Bitoperatoren können wir eine Eins so speichern, dass sie wirklich nur ein einziges Bit belegt.

Kehren wir zu unserer Funktion mit dem Array zurück. Würden wir sie auf Bit-Arrays umschreiben, genügte uns für eine 24-Bit-Hashfunktion ein Bit-Array der Größe 2²⁴ Bit, das sind 2 MiB. Das ist ein ordentliches Upgrade!

Bei einer 32-Bit-Hashfunktion, die 2³² verschiedene Ausgabewerte hat, also 4.294.967.296, bräuchten wir ein Bit-Array von einem halben Gigabyte. Das ist gar nicht so schlecht, wenn man bedenkt, dass wir damit eindeutige Werte bis irgendwo in die Milliarden zählen können.

Linear Counting

Ich habe schon erwähnt, dass wir bei der Verwendung einer Hashfunktion nur eine Schätzung der Anzahl eindeutiger Werte erhalten. Diese Schätzung ist umso ungenauer, je mehr sich die Anzahl der eindeutigen Werte der Anzahl der verschiedenen Ausgabewerte der Hashfunktion nähert. Es ist logisch, dass wir bei einem Datensatz mit fünf Milliarden eindeutigen Werten diese mit einer 24-Bit-Hashfunktion einfach nicht zählen können.

Die Schätzung, die wir mithilfe von Hashfunktionen berechnen, lässt sich aber weiter verbessern. Dazu dient eine einfache Idee – je mehr eindeutige Werte der Datensatz enthält, desto wahrscheinlicher ist es, dass mit der Zeit Kollisionen entstehen. (Kollision = zwei verschiedene Eingaben haben dieselbe Ausgabe der Hashfunktion, dieselbe Checksum.) Jetzt werden wir ein bisschen rechnen, deshalb führen wir ein paar Variablen ein:

Wir arbeiten mit einer n-Bit-Hashfunktion h.
Die Anzahl aller möglichen Ausgaben der Funktion h ist also gleich 2ⁿ. Diese Anzahl bezeichnen wir mit dem Buchstaben m, also: m=2ⁿ.
Das Bit-Array, in dem wir speichern, welche Checksums wir gefunden haben, bezeichnen wir mit dem Großbuchstaben A. Das Array A hat die Länge m.
Wenn wir mit unserem Algorithmus den ganzen Datensatz durchlaufen haben, sind einige Werte im Bit-Array gleich null und einige gleich eins. Uns interessiert vor allem der Anteil „Anzahl der Nullen geteilt durch die Länge des Arrays“, der den relativen Anteil der Nullen im Bit-Array angibt. Am Anfang ist dieser Anteil gleich 1, weil das Array mit lauter Nullen initialisiert ist. Wäre es fifty-fifty, wäre der Anteil gleich einem Halben usw. Diesen Wert bezeichnen wir mit Z und berechnen ihn als Z = Anzahl der Nullen / m.

Dabei gilt: Je höher der Wert Z, desto sicherer können wir sein, dass unsere Schätzung der Anzahl der eindeutigen Werte genau ist. Wenn wir zum Beispiel einen leeren Datensatz durchlaufen, bleiben im Bit-Array lauter Nullen, und der Wert Z ist gleich eins – wir haben also völlige Sicherheit, dass in unserem Datensatz so viele eindeutige Elemente sind, wie das Bit-Array Einsen enthält – null.

Wenn der Wert Z gleich 0,99 ist, bedeutet das, dass das Bit-Array zu einem Hundertstel mit Einsen gefüllt ist. 99 % des Arrays enthalten Nullen. Das ist noch gut, es ist wahrscheinlich, dass während der Berechnung nicht allzu viele Kollisionen aufgetreten sind und es vielleicht keine oder nur eine minimale Korrektur braucht. Ist der Wert Z aber gleich 0,05, sind nur 5 % des Arrays null geblieben, und wir sind während der Berechnung wahrscheinlich auf sehr, sehr viele Kollisionen gestoßen – es braucht eine große Korrektur.

Wie berechnet man aber diese Korrektur? Wir helfen uns mit dem Logarithmus, einer Funktion, die diese Form hat:

Uns interessiert der rote Teil auf dem Intervall ]0; 1]. Wenn wir auf der x-Achse den Wert Z auftragen, erreichen wir, dass sich der Wert y der Null umso mehr nähert, je höher Z ist. Und umgekehrt – je kleiner Z, desto kleiner wird der Wert y. Die endgültige Schätzung berechnen wir, indem wir diese Zahl mit -m multiplizieren. Beachte, dass wir für ein ausreichend kleines Z eine Zahl erhalten, die sogar kleiner als -1 ist, und wenn wir diesen Wert mit -m multiplizieren, erhalten wir eine Schätzung, die größer als m ist: Wir haben geschätzt, dass die Anzahl der eindeutigen Werte größer ist als die Anzahl aller möglichen Checksums, die aus der Hashfunktion h herauskommen können.

Die ganze Formel zur Berechnung der Anzahl p eindeutiger Werte würde so aussehen:

$p = - m \cdot \ln Z$

Eine Implementierung (ohne Bit-Arrays, nur mit gewöhnlichen Arrays) könnte so aussehen:

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 ist hier der natuerliche Logarithmus zur Basis 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 der Funktion linear_counting berechnen wir zuerst mit dem vorherigen Algorithmus, der eine n-Bit-Hashfunktion verwendet, eine erste Schätzung. Dann berechnen wir den Anteil der Nullen im Array und führen die Korrektur nach der Formel durch. Der Logarithmus im Code ist der natürliche Logarithmus. Die Variable nonunique_values enthält number_of_unique_values eindeutige Strings, in diesem Beispiel stehen in der Liste nonunique_values also zehntausend eindeutige Werte. Der seltsame Code in der sechsten Zeile sorgt dafür, dass im Array mehr gleiche Werte sind: Wir hängen einfach dieselbe Liste von Werten ans Ende der Liste an, und jeder Wert ist damit zweimal im Array. Und dann rechnen wir. Die Funktion sollte idealerweise zurückgeben, dass die Liste zehntausend eindeutige Werte enthält. Die Ausgabe:

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

Da jedes Mal eine andere Liste nonunique_values erzeugt wird, unterscheiden sich die Ergebnisse bei jedem Aufruf. Wir haben eine 16-Bit-Hashfunktion verwendet. Wir sehen, dass die erste Schätzung aus der Funktion count_unique_using_array lautete, dass die Liste 9289 eindeutige Werte enthält. Diese Schätzung haben wir durch die Korrektur auf 10.017 verbessert, was schon ziemlich passabel ist: Unsere Schätzung ist nur um 0,17 % größer, während sie vorher um 7,11 % kleiner war – das ist ziemlich viel.

Wenn wir eine „größere“ Hashfunktion nähmen, zum Beispiel eine 24-Bit-Funktion, bekämen wir ein genaueres Ergebnis:

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

Schon die ursprüngliche Schätzung war OK, die Verbesserung brachte uns auf genau zehntausend. Zur Demonstration können wir es mit einer Million eindeutiger IDs versuchen, d. h. number_of_unique_values = 1000000. Mit der 24-Bit-Hashfunktion erhalten wir diese Ergebnisse:

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

Das geht. Wenn wir es dabei als Bit-Array implementieren, würde uns das Array nur die erwähnten zwei Megabyte fressen (+ was die Sprache selbst frisst). Meiner Meinung nach ziemlich gut. But we can do better! Much better. Aber erst beim nächsten Mal.

In der Zwischenzeit kannst du den Artikel A Linear-Time Probabilistic Counting Algorithm for Database Applications [PDF] lesen. Oder du machst mit dem nächsten Teil der Serie weiter: Algorithmus Min-Value.

Kapitel: Linear Counting: Wie man die Anzahl eindeutiger Werte schätzt, Min Value: So schätzt du die Anzahl eindeutiger Werte, LogLog: So schätzt du die Anzahl eindeutiger Werte, HyperLogLog: Wie man die Anzahl eindeutiger Werte sehr genau schätzt

« Zurück: Umwandlung eines Automaten in einen regulären Ausdruck

Weiter: Min Value: So schätzt du die Anzahl eindeutiger Werte »