Введение
Redis добавил структуру HyperLogLog в версии 2.8.9.
HyperLogLog — это алгоритм, используемый для статистики количества элементов, то есть количества дедуплицированных элементов в наборе.
Когда количество входных элементов не превышает 2^64, а объем памяти, необходимый для расчета кардинальности, не превышает 12 КБ, в структуре используется алгоритм аппроксимации со стандартной ошибкой 0,81%.
Анализ метода расчета кардинальности
Вычислить с использованием общих наборов
С увеличением статистических элементов резко возрастает и потребление памяти, и серьезное потребление ресурсов, что не подходит для статистики больших объемов данных.
bitmap
Битовый массив используется для указания того, появляется ли каждый элемент, каждый элемент соответствует одному биту, а общая требуемая память составляет n бит. Это может значительно уменьшить объем памяти, а битовая операция выполняется быстро.
Если вы хотите подсчитать базовое значение 100 миллионов данных, потребуется около 100000000/8/1024/1024 ≈ 12 МБ памяти, и эффект сокращения памяти значителен. Однако для подсчета кардинального значения объекта требуется 12 МБ, а при подсчете 10 000 объектов требуется около 120 ГБ, что не может широко использоваться в сценариях с большими данными.
Но этот метод является точным расчетом
Вероятностный алгоритм
Вероятностные алгоритмы, используемые в настоящее время для подсчета оснований, включают:
- Линейный подсчет (LC): Алгоритм ранней оценки количества элементов, LC не является превосходным с точки зрения пространственной сложности, на самом деле, пространственная сложность LC такая же, как и у метода простого растрового изображения, описанного выше (но есть снижение уровня постоянный член), оба O (Nmax)
- Подсчет LogLog (LLC): по сравнению с LC, подсчет LogLog экономит больше памяти, а сложность пространства составляет всего O (log2 (log2 (Nmax)))
- HyperLogLog Counting (HLL): HyperLogLog Counting — это оптимизация и улучшение, основанное на LLC.При той же пространственной сложности ошибка оценки кардинальности меньше, чем у LLC.
Народное описание алгоритма
Объяснение популярного момента: Предположим, мы генерируем 8-битную хеш-строку для набора данных, тогда вероятность того, что мы получим 00000111, очень мала, то есть вероятность того, что мы сгенерируем большое количество последовательных нулей, очень мала. Вероятность генерации 5 последовательных нулей равна 1/32, тогда, когда мы получим эту строку, мы можем оценить, что кардинальность этого набора данных равна 32.
Сценарии применения
Применимые функции сцены
- Неточная статистика, HyperLoglog является приближенным алгоритмом с 0,81% стандартной ошибкой
- Объем данных огромен, и нет необходимости использовать его, если он невелик, это излишество и лишняя трата места.
- Вы можете только подсчитать количество элементов набора (дедупликация), но нет возможности узнать конкретное содержимое, и, естественно, нет возможности вернуть элементы набора.
Примеры сценариев применения
- Статистика IP
- Статистика UV
- Подсчитайте количество различных запросов, которые пользователи ищут каждый день.
Описание команды
pfadd
PFADD key element [element ...]
Сложность времени: O(1) для добавления каждого элемента
Описание функции: добавление элементов в пространство вычислений
возвращаемое значение
- Если указаны и ключ, и элемент, то при изменении базы близорукости HyperLogLog после выполнения команды он вернет 1, иначе вернет 0
- Если указан только ключ, то если ключ существует, вернуть 0, иначе создать ключ, вернуть 1
Пример: PFADD hll a b c d e f g
PFCOUNT
PFCOUNT key [key ...]
временная сложность
- Среднее постоянное время O(1) очень короткое при вызове с одним ключом.
- O(N)N — это количество ключей при использовании нескольких ключей, а постоянное время намного больше при вызове с несколькими ключами.
Описание функции: вычислить мощность дедупликации набора элементов, соответствующего всем входящим ключам.
Возвращаемое значение: аппроксимация базового числа (стандартная ошибка около 0,81%).
Пример: pfcount хл хл2
Специальное примечание
В качестве побочного эффекта от вызова этой функции HyperLogLog может быть изменен, поскольку последние 8 байтов кодируют последнюю вычисленную базу для целей кэширования. Так что технически PFCOUNT — это команда записи.
Производительность также превосходна, когда PFCOUNT вызывается с одним ключом, PFCOUNT использует кеш для запоминания ранее вычисленной кардинальности, это изменение редко меняется, поскольку большинство операций PFADD не обновляют какие-либо регистры.
Когда PFCOUNT вызывает несколько ключей, HyperLogLogs необходимо объединять и вычислять, что происходит медленно, а объединенная кардинальность не может быть кэширована, поэтому PFCOUNT может занять время порядка миллисекунды, когда используется несколько ключей, и этим не следует злоупотреблять.
PFMERGE
PFMERGE destkey sourcekey [sourcekey ...]
Временная сложность: O(N) слияния N HyperLogLog, но с постоянным временем
Описание функции: объединить исходный ключ с целевым ключом, если дескриптор не существует, создать пустой HyperLogLog, если дескриптор существует, рассматривать его как один из исходных ключей
Возвращаемое значение: просто верните ok
Пример: PFMERGE hll3 hll1 hll2
Справочная статья
Redis new data structure: the HyperLogLog