iGeni Apr 15 2013 at 15:05

Алгоритм HyperLogLog: Оценка мощности множеств при условии ограниченности памяти в реальном времени

Medium

3 min

14K

Tutorial

Предположим, у вас есть сайт с очень большим количеством посетителей и вы хотите показывать вновь зашедшим актуальное количество уникальных визитов с высокой достоверностью. Количество посетителей в измеряется сотнями миллионов в день, вы используете множество серверов и балансировки нагрузки и при этом, вы не можете себе позволить заставлять посетителей ждать, пока будет рассчитано новое значение счетчика. При этом, вы не можете себе позволить держать все данные в оперативной памяти, потому, что они просто туда не влезают. Вот как раз для решения подобных задач и был разработан изящный алгоритм HyperLogLog.

Для интересующихся математикой и формальным описанием алгоритма доступно его полное описание в статье «HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm» опубликованной коллективом авторов Philippe Flajolet, Éric Fusy, Olivier Gandouet, и Frédéric Meunier, но мы здесь попробуем объяснить его простыми словами.

Главная цель алгоритма — подсчет кардинальности (т.е. количества уникальных элементов множества с использованием структуры данных, которая позволяет использовать незначительное количество памяти по сравнению с размером самого множества и в реальном времени, что особенно важно при работе с потоковыми данными.

Алгоритм HyperLogLog использует весьма эффективную структуру данных, позволяющую с высокой (и управляемой) точностью оценить количество уникальных элементов, минимизируя при этом использование памяти. Это особенно полезно в ситуациях, когда точность подсчета не является критической задачей, и вам достаточно результата оценки с заранее известной погрешностью. Примерами таких задач могут быть анализ логов и запросов, вычисление распределенной статистики в реальном времени, оценка количества посетителей в социальных сетях, обнаружение аномалий в сетевом трафике и другие задачи, связанные с большими данными в реальном времени.

Алгоритм HyperLogLog построен на использовании битового массива (или вектор) для хранения данных и вычисления количества уникальных элементов. Ключевым аспектом, лежащим в его базисе является использование хеш-функций, которые преобразующих элементы, встречающиеся в потоке данных, в индексы внутри бытового массива.

Шаги алгоритма

Хэширование: Каждый элемент мультимножества хэшируется в битовую строку;
Разделение на потоки: Битовая строка разделяется на две части: первые p бит определяют индекс потока, а оставшиеся биты используются для вычисления количества ведущих нулей;
Обновление потоков:Для каждого элемента обновляется соответствующий поток, если количество ведущих нулей в оставшейся части битовой строки больше текущего значения в потоке;
Оценка кардинальности:На основе значений в потоках вычисляется оценка количества уникальных элементов.

import hashlib
import math


class HyperLogLog:
    def __init__(self, p=14):
        self.p = p
        self.m = 1 << p  # Количество регистров
        self.registers = [0] * self.m
        self.alpha = self._calculate_alpha()

    def _calculate_alpha(self):
        if self.m == 16:
            return 0.673
        elif self.m == 32:
            return 0.697
        elif self.m == 64:
            return 0.709
        else:
            return 0.7213 / (1 + 1.079 / self.m)

    def _hash(self, value):
        return int(hashlib.md5(value).hexdigest(), 16)

    def _count_leading_zeros(self, hash_value):
        return (hash_value & 0xFFFFFFFFFFFFFFFF).bit_length()

    def add(self, value):
        hash_value = self._hash(value)
        index = hash_value & (self.m - 1)
        hash_value >>= self.p
        leading_zeros = self._count_leading_zeros(hash_value)
        if leading_zeros > self.registers[index]:
            self.registers[index] = leading_zeros

    def count(self):
        harmonic_mean = sum(2 ** -register for register in self.registers)
        estimate = self.alpha * self.m * self.m / harmonic_mean

        if estimate <= 2.5 * self.m:
            zeros = self.registers.count(0)
            if zeros != 0:
                estimate = self.m * math.log(self.m / float(zeros))
        elif estimate > (1 << 32) / 30.0:
            estimate = -(1 << 32) * math.log(1 - estimate / (1 << 32))
        return int(estimate)

Преимущества

Экономия памяти: Алгоритм использует незначительное количество памяти по сравнению с объемом потока данных;
Высокая скорость работы: HyperLogLog способен обрабатывать потоки данных в реальном времени;
Погрешность: Алгоритм допускает небольшую погрешность, но эта погрешность контролируемая и зависит от конфигурации от размера выбранного нами битового вектора и количества потоков;
Параллельность: Алгоритм легко параллелится, в связи с чем мы можем разбить поток данных на несколько частей и затем просто объединить результаты.

Ограничения

Погрешность: Алгоритм возвращает не точное количество уникальных элементов, а дает вероятностную оценку с заданной точностью, что может быть неприемлемым в ряде случаев.

Заключение
В заключение скажем, что HyperLogLog является мощным и гибким инструментом для решения задачи оценки кардинальности на потоках данных в реальном времени, что часто делает его идеальным решением для крупных систем, связанных с большими потоковыми данными.

Hubs:

Algorithms