1. Обзор
Структура данных HyperLogLog (HLL) — это вероятностная структура данных, используемая для оценки кардинальности набора данных .
Предположим, что у нас есть миллионы пользователей, и мы хотим подсчитать количество отдельных посещений нашей веб-страницы. Наивной реализацией было бы хранить каждый уникальный идентификатор пользователя в наборе, и тогда размер набора был бы нашей кардинальностью.
Когда мы имеем дело с очень большими объемами данных, подсчет кардинальности таким образом будет очень неэффективным, поскольку набор данных будет занимать много памяти.
Но если нас устраивает оценка в пределах нескольких процентов и нам не нужно точное количество уникальных посещений, то мы можем использовать HLL , так как он был разработан именно для такого варианта использования — оценки количества миллионов или даже миллиардов. различных значений .
2. Зависимость от Maven
Для начала нам нужно добавить зависимость Maven для библиотеки hll :
<dependency>
<groupId>net.agkn</groupId>
<artifactId>hll</artifactId>
<version>1.6.0</version>
</dependency>
3. Оценка количества элементов с использованием HLL
Перейдем сразу к делу: у конструктора HLL есть два аргумента, которые мы можем настроить в соответствии с нашими потребностями:
log2m (логарифмическая база 2) —это количество регистров, используемых внутриHLL(примечание: мы указываемm)regwidth —это количество битов, используемых в регистре.
Если нам нужна более высокая точность, нам нужно установить для них более высокие значения. Такая конфигурация будет иметь дополнительные накладные расходы, потому что наш HLL будет занимать больше памяти. Если нас устраивает более низкая точность, мы можем уменьшить эти параметры, и наш HLL будет занимать меньше памяти.
Давайте создадим HLL для подсчета различных значений для набора данных со 100 миллионами записей. Мы установим параметр log2m равным 14 и regwidth равным 5 — разумные значения для набора данных такого размера.
Когда каждый новый элемент вставляется в HLL , его необходимо предварительно хэшировать. Мы будем использовать Hashing.murmur3_128() из библиотеки Guava (включенной в зависимость hll ), потому что она точна и быстра.
HashFunction hashFunction = Hashing.murmur3_128();
long numberOfElements = 100_000_000;
long toleratedDifference = 1_000_000;
HLL hll = new HLL(14, 5);
Выбор этих параметров должен дать нам частоту ошибок ниже одного процента (1 000 000 элементов). Мы проверим это через мгновение.
Далее давайте вставим 100 миллионов элементов:
LongStream.range(0, numberOfElements).forEach(element -> {
long hashedValue = hashFunction.newHasher().putLong(element).hash().asLong();
hll.addRaw(hashedValue);
}
);
Наконец, мы можем проверить, что число элементов, возвращаемое HLL , находится в пределах нашего желаемого порога ошибки :
long cardinality = hll.cardinality();
assertThat(cardinality)
.isCloseTo(numberOfElements, Offset.offset(toleratedDifference));
4. Объем памяти HLL
Мы можем рассчитать, сколько памяти займет наш HLL из предыдущего раздела, используя следующую формулу: numberOfBits = 2 ^ log2m * regwidth .
В нашем примере это будет 2 ^ 14 * 5 бит (примерно 81000 бит или 8100 байт). Таким образом, оценка мощности набора из 100 миллионов элементов с использованием HLL заняла всего 8100 байт памяти.
Давайте сравним это с наивной реализацией множества. В такой реализации нам нужно иметь Set из 100 миллионов значений Long , который бы занимал 100 000 000 * 8 байт = 800 000 000 байт .
Мы видим, что разница поразительно велика. При использовании HLL нам нужно всего 8100 байт, тогда как при использовании простой реализации Set нам потребуется примерно 800 мегабайт.
Когда мы рассматриваем большие наборы данных, разница между HLL и наивной реализацией Set становится еще больше.
5. Объединение двух HLL
HLL имеет одно полезное свойство при выполнении союзов . Когда мы возьмем объединение двух HLL, созданных из разных наборов данных, и измерим его кардинальность, мы получим тот же порог ошибки для объединения, который мы получили бы, если бы использовали один HLL и вычислили хеш-значения для всех элементов обоих данных. устанавливает с самого начала .
Обратите внимание, что когда мы объединяем два HLL, оба должны иметь одинаковые параметры log2m и regwidth , чтобы получить правильные результаты.
Давайте проверим это свойство, создав два HLL — один заполняется значениями от 0 до 100 миллионов, а второй — значениями от 100 миллионов до 200 миллионов:
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);
}
);
Обратите внимание, что мы настроили параметры конфигурации HLL , увеличив параметр log2m с 14, как показано в предыдущем разделе, до 15 для этого примера, поскольку результирующее объединение HLL будет содержать в два раза больше элементов.
Затем объединим firstHll и secondHll с помощью метода union() . Как видите, расчетная мощность находится в пределах порога ошибки, как если бы мы взяли мощность от одного HLL с 200 миллионами элементов:
firstHll.union(secondHLL);
long cardinality = firstHll.cardinality();
assertThat(cardinality)
.isCloseTo(numberOfElements * 2, Offset.offset(toleratedDifference * 2));
6. Заключение
В этом уроке мы рассмотрели алгоритм HyperLogLog .
Мы увидели, как использовать HLL для оценки мощности множества. Мы также увидели, что HLL очень экономичен по сравнению с простым решением. И мы выполнили операцию объединения на двух HLL и убедились, что объединение ведет себя так же, как и один HLL .
Реализацию всех этих примеров и фрагментов кода можно найти в проекте GitHub ; это проект Maven, поэтому его легко импортировать и запускать как есть.