Compter avec HyperLogLog

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.

"111.61.206.114" 0100010011 # 1 "0" initial, 1 chance sur 2 "141.85.172.16" 00100101110 # 2 "0" à la suite, 1 chance sur 4 "97.58.244.235" 0000000000000000110 # 16 "0" à la suite, 1 chance sur 65 536

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 :

1. On calcule le hash de l'identifiant.
2. On utilise les premiers bits du hash pour déterminer le bucket.
3. Sur les bits restants, on compte le nombre de zéros initiaux.
4. Pour chaque bucket, on conserve uniquement la valeur maximale rencontrée.

# Avec 4 bits pour déterminer le bucket "205.150.193.87" 00010010110101010 # On prend les 4 premiers bits pour déterminer le bucket 0001_0010110101010 # Dans le bucket "0001", on a 2 zéros initiaux

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