Как подсчитать дневную активность и месячную активность пользователей - Подробное объяснение Redis HyperLogLog

HyperLogLog — это вероятностная структура данных, используемая для оценки кардинальности данных. Набором данных могут быть IP-адреса посетителей веб-сайта, адреса электронной почты или идентификаторы пользователей.

Мощность относится к количеству различных значений в наборе, Например, мощность a, b, c, d равна 4, а мощность a, b, c, d и a по-прежнему равна 4. Хотя a появляется дважды, он будет оцениваться только один раз.

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

Как правило, существует три способа использования Redis для подсчета мощности коллекции: использование Redis HashMap, BitMap и HyperLogLog. Первые две структуры данных потребляют значительно больше памяти при увеличении размера коллекции, а HyperLogLog — нет.

HyperLogLog от Redis уменьшает потребление памяти за счет снижения точности: ему требуется всего 12 КБ памяти, и он может считать 2^64 данных со стандартной ошибкой 0,81%. Так подходит ли HyperLogLog для сценариев, не требующих высокой точности, таких как статистика ежедневной активности и ежемесячной активности?

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

Использование HyperLogLog в Redis

Redis предоставляетPFADD,PFCOUNTиPFMERGEТри команды для использования HyperLogLog пользователями.

PFADDИспользуется для добавления элементов в HyperLogLog.

> PFADD visitors alice bob carol
(integer) 1
> PFCOUNT visitors
(integer) 3

Если приблизительная кардинальность, оцененная HyperLogLog,PFADDЕсли есть изменение после выполнения команды, то команда возвращает 1 , в противном случае она возвращает 0 . Если данный ключ не существует при выполнении команды, программа создаст пустую структуру HyperLogLog перед выполнением команды.

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

PFMERGEОбъедините несколько HyperLogLog в один HyperLogLog, мощность объединенного HyperLogLog близка к мощности объединения всех входных HyperLogLog.

> PFADD customers alice dan
(integer) 1
> PFMERGE everyone visitors customers
OK
> PFCOUNT everyone
(integer) 4

Сравнительный эксперимент по потреблению памяти

Давайте сравним потребление памяти следующими тремя структурами данных с помощью экспериментов: HashMap, BitMap и HyperLogLog.

Сначала мы используем сценарий Lua для вставки определенного количества чисел в структуру данных, соответствующую Redis, а затем выполняем bgsave и, наконец, используйте команду rdb из redis-rdb-tools, чтобы просмотреть размер памяти, занимаемый каждым ключом.

Ниже приведен сценарий Lua.Студенты, которые не знают, как Redis выполняет сценарии Lua, могут прочитать статью, которую я написал ранее.«Ограничение распределенного тока на основе Redis и Lua».

local key = KEYS[1]
local size = tonumber(ARGV[1])
local method = tonumber(ARGV[2])

for i=1,size,1 do
  if (method == 0)
  then
    redis.call('hset',key,i,1)
  elseif (method == 1)
  then
    redis.call('pfadd',key, i)
  else
    redis.call('setbit', key, i, 1)
  end
end

Мы используем redis-cliscript loadкоманда для загрузки сценария Lua в Redis, а затем используйтеevalshaКоманда вставляет 10 миллионов чисел в три структуры данных HashMap, HyperLogLog и BitMap соответственно, а затем используетrdbКоманда для просмотра потребления памяти каждой структурой.

[root@VM_0_11_centos ~]# redis-cli -a 082203 script load "$(cat HyperLogLog.lua)"
"6255c6d0a1f32349f59fd2c8711e93f2fbc7ecf8"
[root@VM_0_11_centos ~]# redis-cli -a 082203 evalsha 6255c6d0a1f32349f59fd2c8711e93f2fbc7ecf8 1 hashmap 10000000 0
(nil)
[root@VM_0_11_centos ~]# redis-cli -a 082203 evalsha 6255c6d0a1f32349f59fd2c8711e93f2fbc7ecf8 1 hyperloglog 10000000 1
(nil)
[root@VM_0_11_centos ~]# redis-cli -a 082203 evalsha 6255c6d0a1f32349f59fd2c8711e93f2fbc7ecf8 1 bitmap 10000000 2
(nil)


[root@VM_0_11_centos ~]# rdb -c memory dump.rdb 
database,type,key,size_in_bytes,encoding,num_elements,len_largest_element,expiry

0,string,bitmap,1310768,string,1250001,1250001,
0,string,hyperloglog,14392,string,12304,12304,
0,hash,hashmap,441326740,hashtable,10000000,8,

Мы провели два раунда экспериментов, вставив 10 000 чисел и 10 000 000 чисел соответственно, и статистика потребления памяти тремя структурами данных показана ниже.

Из таблицы хорошо видно, что BitMap потребляет меньше всего памяти порядка 10 000, а HyperLogLog потребляет меньше всего памяти порядка 10 000 000. Однако в целом память, потребляемая HyperLogLog, составляет 14392 байта. что у HyperLogLog есть своя уникальность потребления памяти.

Фундаментальный

HyperLogLog — это вероятностная структура данных, в которой используется вероятностный алгоритм для подсчета приблизительной кардинальности коллекции. И самым источником его алгоритма является процесс Бернулли.

Процесс Бернулли — это эксперимент с подбрасыванием монеты. Подбросьте обычную монету, она может выпасть орлом или решкой с вероятностью 1/2. Процесс Бернулли состоит в том, чтобы продолжать подбрасывать монету до тех пор, пока не появится положение решки, когда она приземлится, и записать количество подбрасываний k. Например, если монета подбрасывается один раз и выпадает орел, в этот момент k равно 1; при первом подбрасывании монеты выпадет решка, затем продолжайте подбрасывать, пока в третий раз не выпадет орел, в этот момент k равно 3.

Для n процессов Бернулли мы получаем n значений количества подбрасываний орла k_1, k_2 ... k_n , где максимальное значение здесь равно k_max.

По математическому выводу можно сделать вывод: $2^{k_ max}$ как оценка n. Другими словами, вы можете аппроксимировать количество процессов Бернулли на основе максимального количества бросков.

Далее давайте объясним, как HyperLogLog моделирует процесс Бернулли и, наконец, подсчитывает кардинальность множества.

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

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

HyperLogLog в Redis имеет в общей сложности 2 ^ 14 сегментов, что составляет 16384 сегмента. Каждое ведро представляет собой 6-битный массив, как показано на рисунке ниже.

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

Перед настройкой необходимо установить, больше ли введенное в ведро значение, чем старое значение в ведре, если оно больше, установить его, иначе не устанавливать. Пример показан ниже.

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

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

Анализ исходного кода Redis

Давайте сначала посмотрим на определение объекта HyperLogLog.

struct hllhdr {
    char magic[4];      /* 魔法值 "HYLL" */
    uint8_t encoding;   /* 密集结构或者稀疏结构 HLL_DENSE or HLL_SPARSE. */
    uint8_t notused[3]; /* 保留位, 全为0. */
    uint8_t card[8];    /* 基数大小的缓存 */
    uint8_t registers[]; /* 数据字节数组 */
};

в объекте HyperLogLogregistersМассив — это ведро.У него есть две структуры хранения: плотная структура хранения и разреженная структура хранения.Эти две структуры включают только представление хранилища и ведер.Из этого мы видим, что Redis в конечном итоге преследует цель экономии памяти.

Давайте сначала посмотрим на относительно простую плотную структуру хранения, которая также очень проста и понятна.Так как есть 2^14 6-битных сегментов, то я действительно использую достаточноuint8_tБайт для представления, но на этот раз включает преобразование позиции байта и сегмента, потому что байт имеет 8 бит, а сегменту требуется только 6 бит.

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

Когда offset_bits меньше или равен 2, это означает, что ведро находится внутри байта, и значение ведра можно получить только путем инверсии.

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

Разреженная структура хранения HyperLogLog предназначена для экономии потребления памяти.В отличие от режима плотного хранения, он действительно находит так много байтовых массивов для представления 2 ^ 14 сегментов, но использует специальную структуру байтов для выражения.

Чтобы облегчить выражение разреженного хранилища, Redis присваивает вышеуказанные трехбайтовые представления инструкции.

НОЛЬ: Один байт, указывающий, сколько сегментов считается как 0 в строке, первые два бита — это флаг 00, последние 6 бит указывают, сколько существует сегментов, а максимальное значение равно 64.
XZERO : Два байта, указывающие, сколько последовательных сегментов считается равным 0, первые два бита — это флаг 01, последние 14 бит указывают количество сегментов, максимальное значение равно 16384.
VAL: Один байт, указывающий, сколько последовательных сегментов подсчитывается, первый бит — это флаг 1, а четыре бита представляют количество последовательных сегментов, поэтому максимальное количество сегментов равно 32. Последние две цифры показывают, сколько ведер в ряду.

Таким образом, объект HyperLoglog в начальном состоянии требует всего 2 байта, что равно нулю для хранения своих данных без использования 12 КБ памяти. Когда HyperLoglog вставляется в несколько элементов, можно использовать только небольшое количество Xzero, Val и Zero, как показано ниже.

Условия перехода Redis из разреженного хранилища в плотное:

Любое значение счетчика изменяется с 32 на 33, поскольку инструкция VAL больше не может вмещать максимальное значение счетчика, которое она может представлять, равно 32.
Общее количество байтов, занимаемых разреженным хранилищем, превышает 3000 байт, этот порог можно настроить параметром hll_sparse_max_bytes.

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

Ссылаться на

подумал bot.com/blog/… и Perl… nuggets.capable/post/684490… nuggets.capable/post/684490…