HyperLogLog : Compter des valeurs uniques dans des téraoctets de données sans les stocker

Imaginez un service à fort trafic qui traite un flux continu de données, telles que des journaux, des adresses IP et des identifiants d'utilisateurs, générant des milliards d'entrées chaque jour. Le défi consiste à déterminer le nombre de visiteurs uniques sur une semaine. Une approche initiale courante pourrait être d'utiliser un HashSet pour stocker ces clés et vérifier la taille à la fin. Bien que cette méthode semble raisonnable, elle devient rapidement impraticable avec des milliards d'entrées en raison de contraintes de mémoire. Chaque adresse IP, nécessitant 4 octets, entraîne des frais généraux significatifs dus aux nœuds, aux pointeurs et aux hachages, ce qui entraîne une consommation de mémoire d'au moins 50 à 100 octets par élément. Par conséquent, suivre un milliard d'entrées uniques pourrait nécessiter près de cent gigaoctets de RAM, ce qui est coûteux et irréaliste avec plusieurs instances. Cependant, il existe un algorithme capable de résoudre ce problème en utilisant environ 1,5 kilo-octets de mémoire avec une marge d'erreur d'environ 2 %, évitant ainsi la nécessité de stocker les données réelles ou de maintenir de grands clusters. C'est là qu'intervient HyperLogLog, un algorithme statistique qui révolutionne la manière dont nous comptons les éléments uniques dans le Big Data. HyperLogLog est utilisé dans des plateformes telles que Redis, BigQuery, ClickHouse et Presto. Cet article explorera le fonctionnement de cet algorithme, son implémentation en C et son contexte historique.