Guide de l'algorithme HyperLogLog en Java

1. Vue d'ensemble

La structure de données HyperLogLog (HLL) est une structure de données probabiliste utilisée pour estimer la cardinalité d'un ensemble de données .

Supposons que nous ayons des millions d'utilisateurs et que nous souhaitions calculer le nombre de visites distinctes sur notre page Web. Une implémentation naïve serait de stocker chaque identifiant d'utilisateur unique dans un ensemble, puis la taille de l'ensemble serait notre cardinalité.

Lorsque nous traitons de très gros volumes de données, compter la cardinalité de cette manière sera très inefficace car le jeu de données prendra beaucoup de mémoire.

Mais si nous sommes d'accord avec une estimation de quelques pour cent et que nous n'avons pas besoin du nombre exact de visites uniques, alors nous pouvons utiliser le HLL , car il a été conçu exactement pour un tel cas d'utilisation - estimer le nombre de millions, voire de milliards. de valeurs distinctes .

2. Dépendance de Maven

Pour commencer, nous devons ajouter la dépendance Maven pour la bibliothèque hll :

 net.agkn hll 1.6.0 

3. Estimation de la cardinalité à l'aide de HLL

Sauter directement - le constructeur HLL a deux arguments que nous pouvons modifier en fonction de nos besoins:

  • log2m (log base 2) - c'est le nombre de registres utilisés en interne par HLL (note: nous spécifions le m )
  • regwidth - c'est le nombre de bits utilisés par registre

Si nous voulons une précision plus élevée, nous devons les définir sur des valeurs plus élevées. Une telle configuration aura une surcharge supplémentaire car notre HLL occupera plus de mémoire. Si nous allons bien avec une précision inférieure, nous pouvons réduire ces paramètres et notre HLL occupera moins de mémoire.

Créons un HLL pour compter des valeurs distinctes pour un ensemble de données avec 100 millions d'entrées. Nous définirons le paramètre log2m égal à 14 et regwidth égal à 5 - valeurs raisonnables pour un ensemble de données de cette taille.

Lorsque chaque nouvel élément est inséré dans le HLL , il doit être préalablement haché. Nous utiliserons Hashing.murmur3_128 () de la bibliothèque Guava (inclus avec la dépendance hll ) car il est à la fois précis et rapide.

HashFunction hashFunction = Hashing.murmur3_128(); long numberOfElements = 100_000_000; long toleratedDifference = 1_000_000; HLL hll = new HLL(14, 5);

Le choix de ces paramètres devrait nous donner un taux d'erreur inférieur à un pour cent (1 000 000 éléments). Nous allons tester cela dans un instant.

Ensuite, insérons les 100 millions d'éléments:

LongStream.range(0, numberOfElements).forEach(element -> { long hashedValue = hashFunction.newHasher().putLong(element).hash().asLong(); hll.addRaw(hashedValue); } );

Enfin, nous pouvons tester que la cardinalité renvoyée par le HLL est dans notre seuil d'erreur souhaité :

long cardinality = hll.cardinality(); assertThat(cardinality) .isCloseTo(numberOfElements, Offset.offset(toleratedDifference));

4. Taille de la mémoire de HLL

Nous pouvons calculer la quantité de mémoire que prendra notre HLL de la section précédente en utilisant la formule suivante: numberOfBits = 2 ^ log2m * regwidth .

Dans notre exemple, ce sera 2 ^ 14 * 5 bits (environ 81000 bits ou 8100 octets). Ainsi, estimer la cardinalité d'un ensemble de 100 millions de membres à l'aide de HLL n'occupait que 8100 octets de mémoire.

Comparons cela avec une implémentation d'ensemble naïve. Dans une telle implémentation, nous avons besoin d'un ensemble de 100 millions de valeurs Long , qui occuperait 100 000 000 * 8 octets = 800 000 000 octets .

Nous pouvons voir que la différence est étonnamment élevée. En utilisant HLL , nous n'avons besoin que de 8100 octets, alors qu'en utilisant l' implémentation naïve de Set, nous aurions besoin d'environ 800 mégaoctets.

Lorsque nous considérons des ensembles de données plus volumineux, la différence entre HLL et l' implémentation naïve de Set devient encore plus grande.

5. Union de deux HLL

HLL a une propriété bénéfique lors de l'exécution des unions . Lorsque nous prenons l'union de deux HLL créés à partir d'ensembles de données distincts et mesurons sa cardinalité, nous obtiendrons le même seuil d'erreur pour l'union que nous obtiendrions si nous avions utilisé un seul HLL et calculé les valeurs de hachage pour tous les éléments des deux données définit depuis le début .

Notez que lorsque nous réunissons deux HLL, les deux doivent avoir les mêmes paramètres log2m et regwidth pour obtenir des résultats corrects.

Testons cette propriété en créant deux HLL - l' un est rempli avec des valeurs de 0 à 100 millions, et le second est rempli avec des valeurs de 100 millions à 200 millions:

HashFunction hashFunction = Hashing.murmur3_128(); long numberOfElements = 100_000_000; long toleratedDifference = 1_000_000; HLL firstHll = new HLL(15, 5); HLL secondHLL = new HLL(15, 5); LongStream.range(0, numberOfElements).forEach(element -> { long hashedValue = hashFunction.newHasher() .putLong(element) .hash() .asLong(); firstHll.addRaw(hashedValue); } ); LongStream.range(numberOfElements, numberOfElements * 2).forEach(element -> { long hashedValue = hashFunction.newHasher() .putLong(element) .hash() .asLong(); secondHLL.addRaw(hashedValue); } );

Veuillez noter que nous avons réglé les paramètres de configuration des HLL , augmentant le paramètre log2m de 14, comme vu dans la section précédente, à 15 pour cet exemple, car l' union HLL résultante contiendra deux fois plus d'éléments.

Ensuite, réunissons les firstHll et secondHll en utilisant la méthode union () . Comme vous pouvez le voir, la cardinalité estimée se situe dans un seuil d'erreur comme si nous avions pris la cardinalité d'un HLL avec 200 millions d'éléments:

firstHll.union(secondHLL); long cardinality = firstHll.cardinality(); assertThat(cardinality) .isCloseTo(numberOfElements * 2, Offset.offset(toleratedDifference * 2)); 

6. Conclusion

Dans ce didacticiel, nous avons examiné l' algorithme HyperLogLog .

Nous avons vu comment utiliser le HLL pour estimer la cardinalité d'un ensemble. Nous avons également vu que HLL est très peu encombrant par rapport à la solution naïve. Et nous avons effectué l'opération d'union sur deux HLL et vérifié que l'union se comporte de la même manière qu'un seul HLL .

L'implémentation de tous ces exemples et extraits de code se trouve dans le projet GitHub; il s'agit d'un projet Maven, il devrait donc être facile à importer et à exécuter tel quel.