HyperLogLog comptait des milliards d'éléments distincts en quelques kilo-octets

La cardinalité exacte — combien d'utilisateurs, d'adresses IP ou de requêtes de recherche distincts sont apparus — exige normalement une mémoire proportionnelle au nombre d'éléments distincts, ce qui est impossible à l'échelle d'Internet. En 2007, Philippe Flajolet et ses collègues de l'INRIA ont publié HyperLogLog, une esquisse probabiliste qui estime des cardinalités supérieures à un milliard avec une précision d'environ 2 pour cent en utilisant environ 1,5 kilo-octet de mémoire.

L'astuce repose sur une intuition de lancer de pièce : hacher chaque élément en un nombre aléatoire uniforme et observer la plus longue série de zéros de tête. Une série de n zéros est rare — probabilité 2^-n — donc lorsqu'elle apparaît, l'ensemble est probablement assez grand pour l'avoir produite, et 2^n est une bonne estimation de la cardinalité. HyperLogLog divise le flux en de nombreux sous-ensembles, conserve un registre par sous-ensemble contenant sa plus longue série de zéros, et les combine avec une moyenne harmonique afin que les valeurs aberrantes ne faussent pas l'estimation.

La méthode descend de l'algorithme de Flajolet-Martin de 1984 et de l'algorithme LogLog. L'ingénierie qui l'a rendue prête pour la production est venue de l'article de 2013 « HyperLogLog in Practice » de Heule, Nunkesser et Hall chez Google, qui a corrigé les problèmes de biais et de parcimonie pour les grandes et les petites cardinalités.

Redis a fait d'HyperLogLog une fonctionnalité produit : ses commandes PFADD, PFCOUNT et PFMERGE estiment jusqu'à 2^64 éléments distincts avec jusqu'à 12 Ko de mémoire par clé et une erreur standard de 0,81 pour cent, et les esquisses fusionnent de sorte que les comptages quotidiens se combinent sans relire le flux brut.

Estimer des comptages à partir des zéros de tête d'un hachage

Un hachage transforme des données arbitraires en un nombre aléatoire uniforme de même cardinalité

La plus longue série de zéros de tête est une estimation naturelle et observable de la taille de l'ensemble

La division en registres plus une moyenne harmonique annule le bruit

Les esquisses fusionnent, de sorte que les comptages quotidiens se combinent sans stocker le flux brut

Lorsque la réponse n'a besoin d'être qu'approximative, cessez de stocker les données — stockez une minuscule esquisse dont le caractère aléatoire révèle la taille, et échangez une erreur bornée contre une échelle illimitée.

HyperLogLog est devenu un élément de construction standard dans l'analyse et les bases de données : Redis le fournit comme type de données, et les améliorations de l'article de Google de 2013 sont ce qui l'a rendu utilisable à grande échelle dans les systèmes de production. La logique de l'esquisse — conserver un petit enregistrement de preuves, pas les données — ancre également des structures ultérieures comme MinHash et Count-Min Sketch.