Принцип алгоритма HyperLogLog и то, как Redis его применяет

Автор: Линь Гуаньхун / Призраки под рукой

Самородки:Талант /user/178526…

Блог:www.cnblogs.com/linguanh/

Гитхаб:GitHub.com/afan913337456…

Облачная колонка Tencent:cloud.Tencent.com/developer/U…

Колонка блокчейна червоточины:woohoo.impulsecommunity.com/article/153…

содержание

Прототип проблемы
Условный выбор
HyperLogLog
тест Бернулли
Расчетная оптимизация
втягиваться
- битовая строка
- ведро
- соответствовать
Применение HyperLogLog в Redis
- Принцип HyperLogLog в Redis
Коррекция смещения
плечи гигантов

PS: Моя техническая книга: «Практика разработки блокчейн-приложений Ethereum» опубликована, и ее можно приобрести онлайн.

Прототип проблемы

Если вы хотите добиться такой функции:

Подсчитайте, сколько пользователей нажимают, чтобы войти на страницу приложения или веб-страницу каждый день. Повторные клики одного и того же пользователя засчитываются как 1 раз.

Умный вы можете сразу подумать, сHashMapЭтой структуры данных достаточно, и она также удовлетворяет дедупликации. Действительно, это обходной путь, и есть и другие решения.

Хотя задача несложная, когда переменные, участвующие в задаче, достигают определенного порядка величины, самая простая задача становится сложной. Предположим, что количество ежедневных активных пользователей в приложении достигает百万или千万以上级别, мы используемHashMapЭто приведет к тому, что программа будет занимать много памяти.

Попробуем оценитьHashMapИспользование памяти при решении вышеуказанных проблем. Гипотетическое определениеHashMapсерединаKeyзаstringтип,valueзаbool.keyсоответствующий пользователюId,valueда是否点击进入. Очевидно, когда к нему обращаются миллионы разных пользователей. этоHashMapОтпечаток памяти:100万 * (string + bool).

Условный выбор

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

Кроме тогоB+ 树,Bitmap 位图, а статья в основном знакомитHyperLogLogАлгоритмические решения.

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

HyperLogLog

HyperLogLog, именуемый в дальнейшемHLL,этоLogLogОбновленная версия алгоритма, которая может обеспечивать неточный подсчет дедупликации. Существуют следующие функции:

Реализация кода затруднена.
Может использовать очень мало памяти для подсчета огромных объемов данных, вRedisреализовано вHyperLogLog,нужно всего лишь12KПамять можно считать2^64данные.
Существует определенная ошибка в подсчете, и частота ошибок, как правило, низкая. Стандартная ошибка составляет 0,81%.
ошибка может быть установлена辅助计算因子уменьшить.

Учащимся, которые имеют небольшое представление об использовании памяти для основных типов данных в программировании, достаточно12KПамять можно считать2^64удивлен данными. Почему вы так говорите? Давайте возьмем пример:

ВыбиратьJavaязык, вообщеlongЗанимает 8 байт, а байт имеет 8 бит, то есть: 1 байт = 8 бит, то естьlongНаибольшее число, которое может быть представлено типом данных:2^63-1. соответствующий вышеизложенному2^64число, при условии, что есть2^63-1так много цифр, от0 ~ 2^63-1,в соответствии сlongа также1k = 1024字节Правила подсчета общей памяти таковы:((2^63-1) * 8/1024)K, что является огромным числом, а место для хранения намного больше, чем12K. иHyperLogLogно можно использовать12KСтатистику можно заполнить.

тест Бернулли

зная, почемуHyperLogLogПрежде чем вы сможете использовать очень мало памяти для подсчета огромных объемов данных, вы должны сначала понять伯努利试验.

伯努利试验это математика概率论частью содержания, его аллюзии исходят из抛硬币.

У медали две стороны, одна подбрасывается к другой, и вероятность окончательного появления орла и решки составляет 50%. Предполагая, что монета подбрасывается до тех пор, пока не выпадет орел, мы записываем это как полное испытание с одним броском и четырьмя орлами. Независимо от количества бросков, пока выпадает решка, это записывается как испытание. Этот тест伯努利试验.

Тогда для нескольких伯努利试验, предполагая, что это кратноеnВторосортный. значит естьnследующий фронт. Предположим, каждый раз伯努利试验Количество опытных бросков равноk. первый раз伯努利试验, количество раз установлено наk1, и так далее,nследующий соответствуетkn.

Среди них для этогоnвторосортный伯努利试验, должно быть максимальное количество бросковk, например подбрасывание 12 раз, прежде чем выпадет орел, то назовите это какk_max, что представляет собой максимальное количество бросков.

伯努利试验Нетрудно сделать следующие выводы:

Количество бросков для n процессов Бернулли не превышает k_max.
n процессов Бернулли с хотя бы одним броском, равным k_max

Наконец, в сочетании с методом оценки максимального правдоподобия обнаруживается, что вnиk_maxЕсть предполагаемые ассоциации в:n = 2^(k_max). Этот метод оценки характеристик общего потока данных через локальную информацию, по-видимому, находится за пределами нашего базового понимания.Для вывода и проверки этой связи необходимы вероятностные и статистические методы.

Например, это выглядит так:

第一次试验: 抛了3次才出现正面，此时 k=3，n=1
第二次试验: 抛了2次才出现正面，此时 k=2，n=2
第三次试验: 抛了6次才出现正面，此时 k=6，n=3
第n 次试验：抛了12次才出现正面，此时我们估算， n = 2^12

Предполагая, что в приведенном выше примере есть 3 экспериментальные группы, тогда k_max = 6 и, наконец, n = 3, мы подставляем это в формулу оценки, очевидно: 3 ≠ 2^6 . То есть, когда количество испытаний невелико, ошибка этого метода оценки очень велика.

Расчетная оптимизация

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

Так можно ли делать несколько раундов? Например, провести 100 и более раундов испытаний, затем взять k_max каждого раунда, а затем взять среднее значение, а именно:k_mx/100. Наконец, оценивается n. НижеLogLogФормула оценки для:

вышеприведенной формулыDVLLсоответствуетn,constantявляется поправочным коэффициентом, его конкретное значение не определено и может быть разветвлено и установлено в соответствии с реальной ситуацией.mпредставляет количество раундов испытания. крест на головеRэто среднее:(k_max_1 + ... + k_max_m)/m.

Это достигается за счет увеличения количества тестовых раундов, а затем взятияk_maxАлгоритм оптимизации среднегоLogLogспособ сделать. иHyperLogLogиLogLogОтличие в том, что он использует не平均数, но调和平均数.调和平均数Сравнивать平均数Преимущество состоит в том, что на него не так легко воздействуют большие значения. Вот пример:

Найдите среднюю заработную плату:

А - 1000 в месяц, Б - 30000 в месяц. Как использовать среднее значение: (1000 + 30000) / 2 = 15500

Способ использования среднего гармонического: 2/(1/1000 + 1/30000) ≈ 1935,484.

очевидно,调和平均数Сравнивать平均数Эффект должен быть лучше. Ниже调和平均数метод расчета,∑является символом накопления.

втягиваться

Мы уже знаем из вышеизложенного, что в примере с подбрасыванием монеты она может пройти опыт Бернулли.k_maxчтобы оценитьn.

Так как же этот метод оценки относится к следующему вопросу?

Подсчитайте, сколько пользователей нажимают, чтобы войти на страницу приложения или веб-страницу каждый день. Повторные клики от одного и того же пользователя засчитываются как 1.

HyperLogLogэто сделать. Для входных данных выполните следующие действия:

1. Битовая строка

пройти черезhashфункция преобразования данных в比特串, например, введите 5, оно будет преобразовано в: 101. Зачем так конвертировать?

Это потому, что это соответствует подбрасыванию монеты,比特串, 0 представляет решку, а 1 представляет решку, если данные окончательно преобразованы10010000, то справа налево, снизу вверх, мы можем думать, что первое появление 1 положительно.

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

2. Ведро

Ведро делится на сколько раундов. Абстрагировавшись в память компьютера, он хранит большой массив S с единицей измерения бит (бит) и длиной L. Разделим S в среднем на m групп, обрати внимание на эту m группу, скольким раундам она соответствует, и затем количество раундов в каждой группе.Количество занятых битов является средним и устанавливается равным P. Легко вывести следующую зависимость:

L = S.length
L = m * p
В K память, занятая S = L/8/1024

существуетRedisсередина,HyperLogLogНастройки: m=16834, p=6, L=16834*6. Занятая память = 16834 * 6/8/1024 = 12К

визуализируется как:

  第0组     第1组                       .... 第16833组
[000 000] [000 000] [000 000] [000 000] .... [000 000]

3. Переписка

Теперь вернемся к вопросу подсчета пользователей на нашей исходной странице приложения.

Установите ключ домашней страницы приложения как: main
Идентификатор пользователя: idn , n->0,1,2,3....

В этой статистической задаче разные идентификаторы пользователей идентифицируют пользователя, тогда мы можем использовать идентификатор пользователя в качестве пользователя.hashввод. который:

хэш (идентификатор) = битовая строка

Разные идентификаторы пользователей должны иметь разные比特串. Каждый比特串, также должна быть хотя бы одна позиция 1. Мы сравниваем каждый比特串однажды伯努利试验.

в настоящее время分轮, это,分桶. Таким образом, мы можем установить, что каждый比特串После преобразования первого числа цифр в десятичное его значение соответствует метке корзины. Предположение比特串Нижние два бита используются для вычисления флага под ведром, в это время есть идентификатор пользователя比特串Да: 1001011000011. Его индекс ведра:11(2) = 1*2^1 + 1*2^0 = 3, в третьем ведре, третий тур.

В приведенном выше примере после расчета номера ведра оставшаяся часть比特串Да: 10010110000, от младшего к старшему, первое вхождение 1 равно 5. То есть третий ствол в это время, в третьем раунде испытаний,k_max = 5. 5 соответствует двоичному коду: 101, опять же, потому что в каждой корзине есть p бит. Когда p>=3, можно сохранить 101.

Имитируя описанный выше процесс, несколько разных идентификаторов пользователей разбросаны по разным корзинам, и каждая корзина имеет свой k_max. Потом, когда статистикаmianКогда количество кликов пользователя на странице является оценочным. Наконец, объединив k_max во всех сегментах и подставив его в формулу оценки, можно получить оценочное значение.

НижеHyperLogLogФормула оценки, которая сочетает в себе гармоническое среднее, переменную интерпретацию иLogLogтакой же как:

Применение HyperLogLog в Redis

Во-первых, в Redis HyperLogLog — это одна из высокоуровневых структур данных. Есть две команды, включая, но не ограничиваясь следующими:

значение ключа pfadd, сохраните значение, соответствующее ключу в
ключ pfcount, подсчитайте, сколько значений ключа есть

Напомним, что исходная страница APP подсчитывает проблемы пользователей. Если ключ соответствует имени страницы, значение соответствует идентификатору пользователя. Тогда проблема правильная.

Принцип HyperLogLog в Redis

Ранее мы узнали, что в его реализации имеется 16384 корзины, то есть: 2^14 = 16384, каждая корзина имеет 6 бит, и максимальное число, которое может выражать каждая корзина, равно: 2^5+2^4+.. .+1 = 63 в двоичном формате:111 111.

Для команды:pfadd key value

При сохранении значение будет хэшировано в 64 бита, то есть в 64-битную строку, первые 14 бит используются для группирования, а первые 14 бит двоичного кода преобразуются в десятичное число, которое является меткой сегмента.

Почему выбирают14位Причина для выражения числа ведра состоит в том, что 16384 ведра разделены, и 2^14 = 16384, в самый раз, ведро может быть израсходовано за максимальное время, не вызывая потерь. Предположим, что первые 14 цифр строки: 00 0000 0000 0010, а ее десятичное значение равно 2. Затем индекс будет преобразован и помещен в корзину номер 2.

Правило преобразования для индекса:

Во-первых, поскольку полная строка битов значения находится в 64-битной форме, после вычитания 14 остается бит 50. В крайнем случае позиция, где появляется 1, находится на 50-й позиции, то есть позиция равна 50. . На данный момент индекс = 50. На этом этапе сначала преобразуйте индекс в двоичный, то есть: 110010.

Из-за 16384 сегментов каждый сегмент состоит из 6 бит. Так уж получилось, что 110010 было установлено на ведро номер 2. Обратите внимание, что 50 — это уже наихудший случай, и все это приспособлено. Тогда остальные точно можно разместить не задумываясь.

Потому что ключ fpadd может устанавливать несколько значений. Например следующий пример:

pfadd lgh golang
pfadd lgh python
pfadd lgh java

В соответствии с описанным выше методом разные значения будут установлены для разных сегментов.Если они появляются в одном и том же сегменте, первое 14-битное значение будет одинаковым, но позиция, в которой 1 появится позже, будет другой. Затем сравните, больше ли исходный индекс, чем новый индекс. Если да, замените. Нет, никаких изменений.

Наконец, 16384 корзины, соответствующие ключу, имеют множество значений, и каждая корзина имеетk_max. При вызове pfcount в это время по описанному выше методу оценки можно вычислить, сколько раз установлено значение ключа, то есть статистическое значение.

Значение преобразуется в 64-битную строку и, наконец, записывается в каждую корзину в соответствии с описанным выше методом. Преобразование 64 бит в десятичное: 2 ^ 64,HyperLogLogИспользуется только:16384 * 6 /8 / 1024 KМесто для хранения может насчитывать до 2^64 чисел.

Коррекция смещения

В предполагаемой расчетной формулеconstantПеременная не является фиксированным значением, она будет разветвляться в зависимости от фактической ситуации, как показано ниже.

Допущения: m — количество ведер, p — логарифм по основанию 2 от m.

// m 为桶数
switch (p) {
   case 4:
       constant = 0.673 * m * m;
   case 5:
       constant = 0.697 * m * m;
   case 6:
       constant = 0.709 * m * m;
   default:
       constant = (0.7213 / (1 + 1.079 / m)) * m * m;
}

плечи гигантов

Простой эксперимент с подбрасыванием монеты может привести к такому шокирующему алгоритму, силе математики.

Благодарим за руководство в следующих двух сообщениях в блоге:

Все изображения в этой статье взяты из:

woo woo Краткое описание.com/afraid/55 разработали 6-е…

Содержание этой статьи относится к:

woohoo.дождливый лук E.com/blog/2017/0…

Ручное визуальное наблюдениеLogLogиHyperLogLogИзмененный сайт:

content.research.u star.author/blog/hualala.Contract...