Le compteur mal connu : l’HyperLogLog 13


Non, ce n’est pas une faute de frappe. l’HyperLogLog est un algo qui permet de compter approximativement des éléments uniques en prenant très peu de mémoire.

Prenez par exemple un compteur d’IP uniques. En Python, on l’implémenterait en mettant les adresses IP dans un set() (puisqu’ils éliminent les doublons) et pour obtenir le nombre d’IP uniques, on ferait len() sur le set.

Une bonne stratégie, performante (les sets sont très rapides pour ce genre d’usage), simple, mais avec un défaut : la taille du set ne va cesser d’augmenter au fur et à mesure qu’on le remplit d’IP puisqu’il nous faut l’historique de toutes celles rencontrées pour éviter les doublons.

L’HyperLogLog répond à cette problématique : il tient un journal probabiliste qui va se remplir au fur et à mesure qu’on rencontre des nouveaus éléments. On peut ensuite demander au journal combien d’éléments uniques il a rencontré, et il répond avec une marge d’erreur.

Avantage : la taille en mémoire est fixe.
Désavantage : le compteur n’est pas parfaitement précis.

La précision obtenue est dépendante de la place en mémoire, par exemple si on on tolère 1% d’erreur, le journal prendra au maximum 12kb, permettant de compter jusqu’à 2^64 items.

Bref, si vous faites juste un compteur à afficher en pied de page de votre site, c’est un très bon compromis. On peut accepter d’avoir un peu plus ou un peu moins de visiteurs que la réalité qui s’affiche, sachant que la stat elle-même n’est pas vraiment réprésentative de la réalité (IP != de visiteurs uniques).

En Python, il existe une lib (uniquement 2.7 il me semble) pour ça :

>>> import hyperloglog, random
>>> hll = hyperloglog.HyperLogLog(0.01)  # on accepte une erreur de 1%
>>> hll.add("119.250.66.95")
>>> print len(hll)  
1
>>> hll.add("119.250.66.95")
>>> print len(hll)  
1
>>> hll.add("219.81.118.147")
>>> print len(hll)  
2
>>> for x in xrange(1000):
... ip = ".".join(str(random.randint(1, 255)) for x in range(4))
... print ip
... hll.add(ip)
114.208.49.91
11.72.239.16
67.56.229.66
191.62.59.163
61.104.232.43
110.58.69.141
246.123.30.234
244.246.65.219
98.93.193.114
185.143.143.69
191.177.161.213
...
>>> print len(hll) # 1000 items unique. Environ :)
1004

Vous pouvez également profiter de l’HyperLogLog via une extension PostGres ou en utilisant une version récente de Redis.

La plupart des compteurs sur les sites sont complètement bidons, alors vous, honnête que vous êtes, embrassez l’approximatif ! C’est presque la vérité. Presque.

13 thoughts on “Le compteur mal connu : l’HyperLogLog

  • Rob

    >>> print len(hll) # 1000 items unique. Environ :)
    10004

    –> Du coup ça devrait être 1004 non ?

  • PocketTiger

    Excusez moi mais, qu’es que putain de quoi ? oO
    C’est quoi un “journal probabiliste” et comment ça le journal “répond avec une marge d’erreur” ?
    L’informatique c’est le domaine du déterminisme et de l’exactitude par excellence.
    Alors il marche comment ce module pifométrique ?
    Question subsidiaire, ou est passé le trombone ='(

    Cordialement

  • Anne O. Nyme

    L’idée c’est d’estimer une approximation. Par exemple, on te donne plein de nombres, tu regarde leur max, et tu regardes où se trouve le premier 1 (en binaire hein). Forcément, si ton entier le plus grand est du genre 11111111 (255 en décimal) bah tu ne peux pas avoir plus de 255 nombres. Et si le min est du genre 00001011 (11 en décimal) bah tu ne peux avoir que les nombres entre 11 et 255, soit 244 nombres. Ces valeurs (min, max, etc.) sont des observables qui sont faciles à calculer (à peu de choses près, vu qu’on n’a pas forcément besoin du plus petit ou plus grand entier pour avoir une borne sup ou inf) et on en déduit un comptage approximatif du nombre d’éléments.

    Bon en fait c’est beaucoup plus compliqué que ça. Ils séparent les flux d’entrées et prennent la moyenne harmonique de chaque résultat obtenu, je saurais pas dire pourquoi sans avoir lu tout le papier (http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf), je risquerais de dire des conneries. Et pour générer de l’aléatoire, ils utilisent une fonction de hachage qu’ils appliquent aux nombres en entrée.

  • Max

    le trombone est mort avec l’ancien serveur, paix à son âme, peut être qu’on essayera de le ressusciter. Un jour…

  • Sam Post author

    @Rob: tout à fait. Fixed.

    @PocketTiger: J’ai même plus besoin de répondre, le blog tourne tout seul :) Le trombonne est sur l’ancien thême du blog.

  • joshuafr

    Euh, si print len(hll) répond 10004 au lieu d’environ 1000, là y’a plus qu’1% d’erreur… ou alors il y a un zéro de trop ;-)
    Je pense que MySQL s’en sert aussi pour compter le nombre de lignes dans ses tables, du moins avec sqlyog

  • Sam Post author

    Après j’irais pas jusqu’à dire que l’implémentation “c’est franchement pas compliqué”. Parce que moi je connais plein de matheux qui trouvent que faire un gratin dauphinois c’est compliqué alors que je trouve ça très simple. Donc je suppose que c’est aussi compliqué que le gratin dauphinois pour quelqu’un qui sait faire des pates.

  • Anne O'Nyme

    @Sam

    Je parlais de la simulation de l’aléatoire, pas de l’implémentation elle-même (qui elle prend 20 pages à expliquer et justifier). Cela dit je ne suis pas un matheux pur et je ne vois rien de franchement insurmontable dans le papier, même si c’est sûr que ça prend du temps à digérer (comme le gratin dauphinois).

  • Sam Post author

    @joshuafr: par “fixed”, je veux dire que la coquille est corrigée.

  • ONU Inc.

    >En Python, il existe une lib pour ça
    Combien de fois n’ai-je pas entendu cette remarque bandante dont la simplicité même fait la force de Python… Manquerait plus qu’une lib qui suce ou qui fait le café.

  • Alex

    Ce ne serait pas une variant du “Bloom filter” ? (Qui est aussi probabiliste et de taille fixe)

  • Sam Post author

    C’est un principe cousin mais le bloom filter permet de savoir si un élément fait partie du set, tandis que l’hyperloglog permet de savoir combien d’éléments uniques ont été ajoutés au set. Donc pas exactement le même usage.

Leave a comment

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <pre> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Des questions Python sans rapport avec l'article ? Posez-les sur IndexError.