Imaginez-vous travailler chez YouTube : on vous demande de compter le nombre de vues d'une vidéo, comment feriez-vous ?
Intuitivement, on penserait à enregistrer tous les utilisateurs qui consultent la vidéo puis à compter la taille de la liste. Mais, pour une vidéo avec plusieurs millions de vues, stocker chaque identifiant utilisateur peut rapidement coûter cher en mémoire. C'est là qu'HyperLogLog intervient : en se basant sur les probabilités, il peut fournir un compteur avec une faible empreinte mémoire, en échange d'une petite marge d'erreur.
Le problème du comptage distinct
Pour l'exemple, prenons un compteur de vues qui doit compter le nombre d'IP différentes qui consultent un site. La première solution consiste à stocker chaque IP rencontrée dans un tableau ou un ensemble. C'est exact, mais la mémoire utilisée grandit avec le nombre d'éléments. Si on doit conserver 10 millions d'IP distinctes, cela représente déjà environ 40 Mo pour des IPv4 stockées sur 4 octets.
À l'inverse, un simple compteur est très économique en mémoire, mais il ne sait pas gérer les doublons : si la même IP revient plusieurs fois, elle sera comptée plusieurs fois. Il faut donc trouver un compromis entre précision et consommation mémoire.
L'idée d'HyperLogLog
HyperLogLog repose sur une intuition probabiliste : certains motifs sont rares dans un nombre aléatoire. Si on rencontre ces éléments rares souvent, c'est qu'on a rencontré beaucoup de nombres. Pour fonctionner, HyperLogLog aura besoin d'un système de hashage capable de convertir nos éléments sous forme de nombres répartis de manière uniforme.
Ensuite, dans le hash obtenu, on regardera le nombre de 0 initiaux dans la représentation binaire pour juger de la rareté du nombre.
Si, parmi les IP observées, on tombe sur un hash qui commence par beaucoup de zéros, on peut estimer qu'il a probablement fallu voir beaucoup d'éléments pour rencontrer ce cas. Malheureusement, on peut s'imaginer un cas où, dans les premiers visiteurs que l'on rencontre, une personne a une IP avec de nombreux 0 initiaux. Dans ce cas-là, on pensera avoir rencontré beaucoup de visiteurs, alors qu'on a juste eu de la chance...
Grouper pour réduire la marge d'erreur
Se baser uniquement sur le hash le plus rare serait trop fragile. On pourrait très bien rencontrer par hasard une IP dont le hash commence par beaucoup de zéros alors que le nombre réel de visiteurs est faible. Pour limiter cet effet, HyperLogLog découpe les données en plusieurs buckets.
Le principe est le suivant :
- On calcule le hash de l'identifiant.
- On utilise les premiers bits du hash pour déterminer le bucket.
- Sur les bits restants, on compte le nombre de zéros initiaux.
- Pour chaque bucket, on conserve uniquement la valeur maximale rencontrée.
Par exemple, si on utilise 4 bits pour choisir le bucket, on obtient 16 buckets possibles. Une IP peut tomber dans le bucket 1 avec un zéro initial, une autre dans le bucket 2 avec deux zéros initiaux, puis une troisième à nouveau dans le bucket 1 avec plus de zéros. Dans ce cas, on met à jour uniquement le maximum du bucket concerné.
On ne stocke donc pas les IP elles-mêmes, mais une petite série de compteurs qui représentent les observations les plus rares rencontrées dans chaque bucket (aussi nommés registres).
Estimer le nombre d'éléments
Une fois tous les buckets remplis, HyperLogLog utilise une moyenne harmonique pour produire une estimation du nombre d'éléments distincts. Cette moyenne a l'avantage de réduire l'influence des valeurs extrêmes : si un bucket contient une valeur exceptionnellement grande, elle ne va pas déséquilibrer toute l'estimation.
On utilise ensuite le résultat de cette moyenne avec la formule suivante
\alpha _{m} est une constante précalculéem est le nombre de bucketsZ est la moyenne harmonique
Le résultat n'est pas exact, mais avec suffisamment de buckets la marge d'erreur devient acceptable. Avec 14 bits utilisés pour déterminer les buckets, on obtient une marge d'erreur autour de 1 %, ce qui est largement acceptable dans le cadre d'un compteur de vues ou de visiteurs par exemple.
Une taille mémoire fixe
Le point fort d'HyperLogLog est que la mémoire utilisée ne dépend pas du nombre d'éléments observés, mais du nombre de buckets configurés. Avec un hash sur 64 bits et 14 bits réservés au choix du bucket, on obtient :
Il reste alors 50 bits pour compter les zéros initiaux. Chaque bucket doit donc stocker une valeur comprise entre 0 et 50, ce qui tient sur 6 bits. On arrive ainsi à environ 12 Ko pour représenter le compteur. Et ce compteur occupe la même place pour une vidéo à 300 vues que pour une vidéo à 500 millions de vues. C'est ce qui rend cette structure très pratique pour les gros volumes de données.
Précision et compromis
On peut améliorer la précision d'HyperLogLog, mais cela implique des compromis :
- augmenter le nombre de buckets réduit l'erreur, mais augmente la mémoire utilisée.
- utiliser plusieurs fonctions de hashage peut permettre de croiser davantage de données, mais demande plus de calcul à chaque élément traité.
HyperLogLog est donc particulièrement adapté aux situations où une estimation est suffisante : statistiques, analytics, comptage de visiteurs uniques ou traitement de grands volumes de données. On le retrouve notamment dans Redis et dans des systèmes de données comme BigQuery. C'est aussi un algorithme relativement simple à implémenter, à condition d'avoir un bon algorithme de hashage en amont.
Fusionner plusieurs compteurs
Un autre avantage d'HyperLogLog est la facilité de fusion. Si deux serveurs calculent chacun leur compteur, on peut produire un compteur global en fusionnant les buckets. Pour chaque index de bucket, il suffit de garder la valeur maximale :
Une fois les buckets fusionnés, on relance le calcul d'estimation sur cette nouvelle structure (c'est très pratique lorsque les données sont réparties sur plusieurs machines).
Conclusion
Je trouve HyperLogLog particulièrement intéressant parce qu'il part d'un problème qui semble simple au départ : compter des éléments distincts. Mais dès que l'on ajoute la contrainte de la mémoire, la solution naïve montre rapidement ses limites. Ce qui est assez élégant avec cet algorithme, c'est qu'il accepte de perdre l'exactitude parfaite pour gagner énormément en espace mémoire.
C'est aussi le genre d'algorithme qui montre bien l'intérêt des approches probabilistes : on ne cherche pas toujours la réponse exacte, mais une réponse suffisamment fiable avec un coût beaucoup plus faible. Pour aller plus loin, vous pouvez consulter l'article original HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm.