Guida all'algoritmo HyperLogLog in Java

1. Panoramica

La struttura dati HyperLogLog (HLL) è una struttura dati probabilistica utilizzata per stimare la cardinalità di un set di dati .

Supponiamo di avere milioni di utenti e di voler calcolare il numero di visite distinte alla nostra pagina web. Un'implementazione ingenua sarebbe memorizzare ogni ID utente univoco in un set, quindi la dimensione del set sarebbe la nostra cardinalità.

Quando abbiamo a che fare con volumi di dati molto grandi, il conteggio della cardinalità in questo modo sarà molto inefficiente perché il set di dati occuperà molta memoria.

Ma se stiamo bene con una stima entro pochi punti percentuali e non abbiamo bisogno del numero esatto di visite uniche, allora possiamo usare l' HLL , poiché è stato progettato esattamente per questo caso d'uso - stimando il conteggio di milioni o addirittura miliardi di valori distinti .

2. Dipendenza da Maven

Per iniziare dovremo aggiungere la dipendenza Maven per la libreria hll :

 net.agkn hll 1.6.0 

3. Stima della cardinalità utilizzando HLL

Saltando subito dentro: il costruttore HLL ha due argomenti che possiamo modificare in base alle nostre esigenze:

  • log2m (log base 2) - questo è il numero di registri utilizzati internamente da HLL (nota: stiamo specificando la m )
  • regwidth - questo è il numero di bit utilizzati per registro

Se vogliamo una maggiore precisione, dobbiamo impostarli su valori più alti. Una tale configurazione avrà un sovraccarico aggiuntivo perché il nostro HLL occuperà più memoria. Se stiamo bene con una precisione inferiore, possiamo abbassare quei parametri e il nostro HLL occuperà meno memoria.

Creiamo un HLL per contare valori distinti per un set di dati con 100 milioni di voci. Si imposterà la log2m parametro uguale a 14 e regwidth uguale a 5 - valori ragionevoli per un insieme di dati di queste dimensioni.

Quando ogni nuovo elemento viene inserito nell'HLL , deve essere prima sottoposto ad hashing. Useremo Hashing.murmur3_128 () dalla libreria Guava (inclusa con la dipendenza hll ) perché è sia preciso che veloce.

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

La scelta di questi parametri dovrebbe darci un tasso di errore inferiore all'uno percento (1.000.000 di elementi). Lo testeremo tra un momento.

Successivamente, inseriamo i 100 milioni di elementi:

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

Infine, possiamo verificare che la cardinalità restituita dall'HLL rientri nella soglia di errore desiderata :

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

4. Dimensione della memoria di HLL

Possiamo calcolare quanta memoria impiegherà il nostro HLL della sezione precedente utilizzando la seguente formula: numberOfBits = 2 ^ log2m * regwidth .

Nel nostro esempio saranno 2 ^ 14 * 5 bit (circa 81000 bit o 8100 byte). Quindi la stima della cardinalità di un set di 100 milioni di membri utilizzando HLL ha occupato solo 8100 byte di memoria.

Confrontiamo questo con un'implementazione di set ingenua. In un'implementazione di questo tipo, è necessario disporre di un set di 100 milioni di valori Long , che occuperebbe 100.000.000 * 8 byte = 800.000.000 byte .

Possiamo vedere che la differenza è sorprendentemente alta. Usando HLL , abbiamo bisogno solo di 8100 byte, mentre usando l'ingenua implementazione Set avremmo bisogno di circa 800 megabyte.

Quando consideriamo set di dati più grandi, la differenza tra HLL e l' implementazione ingenua di Set diventa ancora maggiore.

5. Unione di due HLL

HLL ha una proprietà benefica quando si eseguono sindacati . Quando prendiamo l'unione di due HLL creati da set di dati distinti e ne misuriamo la cardinalità, otterremo la stessa soglia di errore per l'unione che avremmo se avessimo usato un singolo HLL e calcolato i valori hash per tutti gli elementi di entrambi i dati set dall'inizio .

Nota che quando uniamo due HLL, entrambi dovrebbero avere gli stessi parametri log2m e regwidth per ottenere risultati corretti.

Testiamo quella proprietà creando due HLL: uno è popolato con valori da 0 a 100 milioni e il secondo è popolato con valori da 100 milioni a 200 milioni:

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); } );

Si noti che abbiamo messo a punto i parametri di configurazione degli HLL , aumentando il parametro log2m da 14, come visto nella sezione precedente, a 15 per questo esempio, poiché l' unione HLL risultante conterrà il doppio degli elementi.

Successivamente, uniamo firstHll e secondHll utilizzando il metodo union () . Come puoi vedere, la cardinalità stimata è all'interno di una soglia di errore come se avessimo preso la cardinalità da un HLL con 200 milioni di elementi:

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

6. Conclusione

In questo tutorial, abbiamo esaminato l' algoritmo HyperLogLog .

Abbiamo visto come utilizzare l' HLL per stimare la cardinalità di un insieme. Abbiamo anche visto che HLL è molto efficiente in termini di spazio rispetto alla soluzione ingenua. E abbiamo eseguito l'operazione di unione su due HLL e verificato che l'unione si comporta allo stesso modo di un singolo HLL .

L'implementazione di tutti questi esempi e frammenti di codice può essere trovata nel progetto GitHub; questo è un progetto Maven, quindi dovrebbe essere facile da importare ed eseguire così com'è.