HyperLogLog
HLL часто используется для статистики дедупликации (будут определенные ошибки), например подсчета количества посещений страницы в день (каждое посещение пользователя несколько раз в день может учитываться только один раз, то есть UV), обратите внимание, что здесь УФ,
Если это PV, то с ним проще обращаться, можно назначить независимый счетчик на каждую веб-страницу, добавить суффикс ключа счетчика к дате дня, чтобы каждый раз при приходе запроса выполнять команду incrby один раз , и напрямую увеличивать его, и, наконец, вы можете подсчитать все PV,
Но UV отличается и нуждается в дедупликации.Как правило, дедупликация может рассмотреть возможность использования набора наборов для этого, например, для хранения всех идентификаторов пользователей, посетивших страницу в этот день.Когда приходит запрос, мы можем использовать sadd, чтобы вставить идентификатор пользователя.Scard может вынуть размер этого набора, чтобы увидеть, это число является UV-данными этой страницы, это решение кажется возможным,
Однако, если количество посещений страницы очень велико, а страница может иметь десятки миллионов UV, для статистики требуется большая коллекция наборов, что является пустой тратой места.Если таких страниц много, она будет потреблять больше места для хранения.
Как правило, количество посещений страницы не обязательно должно быть очень точным. Например, разница между 1,05 млн и 1,06 млн невелика. HLL — это решение, которое позволяет исключить дублирование подсчета и сэкономить много места. это не точно, это разница не запредельная, а стандартная ошибка составляет 0,81%.Такая точность обычно может удовлетворить потребности УФ-статистики.
pfadd/pfcount
HLL предоставляет две инструкции pfadd/pfcount, одна для увеличения счетчика, другая для получения счетчика. Использование pfadd и set set такое же, и идентификатор пользователя добавляется напрямую. Использование pfcount такое же, как что шрама, и значение подсчета получено непосредственно.
127.0.0.1:6379> pfadd hll user1 # 给hll可以添加一个 user1 的用户id，下面都一样
(integer) 1
127.0.0.1:6379> pfadd hll user2
(integer) 1
127.0.0.1:6379> pfadd hll user3
(integer) 1
127.0.0.1:6379> pfadd hll user4
(integer) 1
127.0.0.1:6379> pfadd hll user4 # 此处又添加了一个user4，被过滤
(integer) 0
127.0.0.1:6379> pfadd hll user4
(integer) 0
127.0.0.1:6379> pfcount hll # 获取总数，发现是4，说明去重成功
(integer) 4
127.0.0.1:6379> pfadd hll user5 user6 user7 # 新添加三个用户id
(integer) 1
127.0.0.1:6379> pfcount hll # 计数成功
(integer) 7
Из приведенных выше результатов видно, что эффект очень хороший, и результаты правильные. Так называемого коэффициента ошибок нет. Это потому, что наши данные все еще слишком малы. Давайте воспользуемся скриптом, чтобы запустить еще некоторые данные для посмотрите, появится ли частота ошибок.
Видно, что мы добавили 10w данных за один раз, а полученная сумма отличается от ожидаемой на 0,277%, это ошибка, и она будет не такой точной.
Запустив те же данные еще раз, вы обнаружите, что результаты такие же, как и выше, что доказывает, что HLL действительно можно дедуплицировать.
Кодовый адрес:GitHub.com/Joe Dream Сложность…
pfmerge
В дополнение к pfadd/pfcount, HLL также предоставляет инструкцию pfmerge, которая используется для накопления нескольких значений счетчика pf вместе для формирования нового значения pf.
Что оно делает? Например, на веб-сайте есть две страницы с похожим содержанием.Если однажды эти две страницы необходимо объединить, а также необходимо объединить трафик UV, в это время можно использовать pfmerge для подсчета значений. этих двух страниц вместе.
127.0.0.1:6379> pfadd hll1 a b c # hll1 的页面
(integer) 1
127.0.0.1:6379> pfadd hll2 e f g # hll2 的页面
(integer) 1
127.0.0.1:6379> pfcount hll1 # hll1页面的总数
(integer) 3
127.0.0.1:6379> pfcount hll2 # hll2页面的总数
(integer) 3
127.0.0.1:6379> pfmerge hll3 hll1 hll2 # 合并两个页面的总数到hll3中
OK
127.0.0.1:6379> pfcount hll3 # 查看hll3结果
(integer) 6
По демо ниже видно, что при слиянии двух uv они тоже будут дедуплицированы.Например, на обеих страницах есть abc, а при слиянии вместе они тоже будут фильтроваться.
127.0.0.1:6379> pfadd hll1 a b c
(integer) 1
127.0.0.1:6379> pfadd hll2 e f g
(integer) 1
127.0.0.1:6379> pfadd hll2 a b c
(integer) 1
127.0.0.1:6379> pfcount hll1
(integer) 3
127.0.0.1:6379> pfcount hll2
(integer) 6
127.0.0.1:6379> pfmerge hll3 hll1 hll2
OK
127.0.0.1:6379> pfcount hll3
(integer) 6
оккупация космоса
HLL должен занимать 12 КБ дискового пространства. Как правило, когда количество пользователей очень мало, может не быть преимущества в стоимости пространства. Однако, если есть много пользователей, 12 КБ экономят много места для хранения. По сравнению с набором решение для хранения данных, HLL Используемое пространство — капля в море.
Redis оптимизирует хранение HLL. Когда счет относительно невелик, пространство для хранения хранится в разреженной матрице, а занимаемое пространство очень мало. Только когда количество постепенно увеличивается, а занимаемое пространство разреженной матрицы постепенно превышает пороговое значение, он будет одноразовым, он станет плотной матрицей, занимающей 12Кб места.