Алгоритм HyperLogLog — очень умный алгоритм для аппроксимации количества дедуплицированных элементов. Он внутренне поддерживает 16384 корзины для записи количества элементов в каждой корзине. Когда элемент поступает, он хешируется в одном из сегментов, что с определенной вероятностью влияет на значение счетчика сегмента. Поскольку это вероятностный алгоритм, значение подсчета одного ведра неточное, но если все значения подсчета ведра суммировать по среднему смешиванию, результат будет очень близок к реальному значению подсчета.
Чтобы облегчить понимание алгоритма HyperLogLog, мы сначала упростим его логику подсчета. Поскольку это счетчик дедупликации, если это точная дедупликация, вы должны использовать коллекцию наборов, использовать коллекцию для записи всех элементов, а затем использовать команду scard, чтобы получить размер коллекции, чтобы получить общее количество. Поскольку элементов так много, один набор будет очень большим, поэтому набор разбит на 16384 маленьких набора. Когда элемент поступает, он отправляется в небольшой набор хранилища с помощью алгоритма хэширования, и один и тот же элемент всегда будет хэшироваться в один и тот же небольшой набор. Таким образом, общее количество представляет собой сумму размеров всех небольших коллекций. Точный подсчет таким образом может не только увеличивать элементы, но и уменьшать их.
Описывается в коде Python следующим образом
# coding:utf-8
import hashlib
class ExactlyCounter:
def __init__(self):
# 先分配16384个空集合
self.buckets = []
for i in range(16384):
self.buckets.append(set([]))
# 使用md5哈希算法
self.hash = lambda x: int(hashlib.md5(x).hexdigest(), 16)
self.count = 0
def add(self, element):
h = self.hash(element)
idx = h % len(self.buckets)
bucket = self.buckets[idx]
old_len = len(bucket)
bucket.add(element)
if len(bucket) > old_len:
# 如果数量变化了，总数就+1
self.count += 1
def remove(self, element):
h = self.hash(element)
idx = h % len(self.buckets)
bucket = self.buckets[idx]
old_len = len(bucket)
bucket.remove(element)
if len(bucket) < old_len:
# 如果数量变化了，总数-1
self.count -= 1
if __name__ == '__main__':
c = ExactlyCounter()
for i in range(100000):
c.add("element_%d" % i)
print c.count
for i in range(100000):
c.remove("element_%d" % i)
print c.count
Нет никакой очевидной выгоды от разбиения коллекции, так как общий объем памяти не уменьшается. HyperLogLog определенно не является этим алгоритмом, ему нужно оптимизировать эту небольшую коллекцию, сжать ее пространство для хранения и сделать ее память очень маленькой. Пространство, занимаемое каждым бакетом в алгоритме HyperLogLog, на самом деле составляет всего 6 бит.Естественно, эти 6 бит не могут вместить все элементы в баке.Он записывает логарифм количества элементов в баке.
Чтобы проиллюстрировать, что представляет собой это логарифмическое значение, давайте сначала рассмотрим небольшую задачу. Случайное целочисленное значение, которое с вероятностью 50% имеет 0 в конце, либо 0, либо 1. Точно так же вероятность наличия двух нулей в хвосте равна 25 %, вероятность наличия трех нулей составляет 12,5 % и т. д., вероятность наличия k нулей равна 2^(-k). Если мы рандомизируем множество целых чисел, мы не знаем их количества, но отслеживаем максимальное количество K последовательных нулей в конце целого числа. Мы можем использовать это K для аппроксимации числа целых чисел, равного 2^K.
Конечно, результат будет очень неточным, потому что тогда вы можете рандомизировать множество целых чисел, но максимальное количество K последовательных нулей в конце не изменится, но оценочное значение по-прежнему будет 2^K. Вы можете подумать, что если бы это K было числом с плавающей запятой, оно могло бы немного увеличиваться с каждым случайным новым элементом, и оценка должна быть намного более точной.
HyperLogLog получает среднее максимальное количество завершающих нулей K# путем выделения 16384 сегментов, а затем смешивания и усреднения максимального числа K всех сегментов, где K# — число с плавающей запятой, и использует усредненное значение 2^K# для оценки элементов. будет относительно точным. Однако это всего лишь упрощенный алгоритм.Реальный алгоритм имеет много поправочных коэффициентов.Поскольку задействована математическая теория, она не будет подробно описана здесь.
Давайте взглянем на конкретную реализацию алгоритма Redis HyperLogLog. Мы знаем, что фактическое пространство, занимаемое HyperLogLog, составляет около 13684 * 6 бит / 8 = 12 КБ. Но когда счетчик невелик, у большинства сегментов счетчик равен нулю. Если слишком много байтов в 12 КБ равны нулю, то это пространство можно сохранить соответствующим образом. Redis использует разреженное хранилище, когда значение счетчика относительно невелико, а пространство, занимаемое разреженным хранилищем, намного меньше 12 КБ. По сравнению с разреженным хранилищем это плотное хранилище, которое будет занимать постоянные 12 КБ.
плотная структура хранения
Независимо от того, является ли это разреженным хранилищем или плотным хранилищем, Redis использует внутренние растровые изображения строк для хранения значений счетчика всех сегментов в HyperLogLog. Структура плотного хранилища очень проста и представляет собой растровое изображение строки, состоящее из 16384 последовательных 6 битов.
Итак, учитывая номер ведра, как получить его 6-битное значение счетчика? Эти 6 бит могут находиться внутри байта или могут пересекать границу байта. Нам нужно правильно сдвинуть и соединить эти один или два байта, чтобы получить значение счетчика.
Предполагая, что номер ведра равен idx, смещение позиции начального байта 6-битного значения счетчика представлено как offset_bytes, а смещение позиции начального бита этого байта представлено как offset_bits. У нас есть
offset_bytes = (idx * 6) / 8
offset_bits = (idx * 6) % 8
Первое — это частное, а второе — остаток. Например, смещение в байтах корзины 2 равно 1, что соответствует второму байту. Его битовое смещение равно 4, то есть 5-й бит 2-го байта начинается со значения счетчика корзины 2. Следует отметить, что порядок байтов — младший левый и верхний правый, и обычно байты, которые мы используем, — верхний левый и младший правый, нам нужно инвертировать в уме.
Если offset_bits меньше или равен 2, то эти 6 бит находятся внутри байта, вы можете напрямую использовать следующее выражение, чтобы получить значение счетчика val
val = buffer[offset_bytes] >> offset_bits # 向右移位
Если offset_bits больше 2, то граница байтов пересекается, и двухбайтовые битовые фрагменты необходимо объединить.
# 低位值
low_val = buffer[offset_bytes] >> offset_bits
# 低位个数
low_bits = 8 - offset_bits
# 拼接，保留低6位
val = (high_val << low_bits | low_val) & 0b111111
Однако приведенный ниже исходный код Redis немного более неясен, и кажется, что он рассматривает только случай пересечения границ байтов. Это связано с тем, что если 6 бит находятся в одном байте, значение high_val в приведенном выше коде равно нулю, поэтому этот код может обрабатывать как однобайтовые, так и двухбайтовые значения.
// 获取指定桶的计数值
#define HLL_DENSE_GET_REGISTER(target,p,regnum) do { \
uint8_t *_p = (uint8_t*) p; \
unsigned long _byte = regnum*HLL_BITS/8; \
unsigned long _fb = regnum*HLL_BITS&7; \ # %8 = &7
unsigned long _fb8 = 8 - _fb; \
unsigned long b0 = _p[_byte]; \
unsigned long b1 = _p[_byte+1]; \
target = ((b0 >> _fb) | (b1 << _fb8)) & HLL_REGISTER_MAX; \
} while(0)
// 设置指定桶的计数值
#define HLL_DENSE_SET_REGISTER(p,regnum,val) do { \
uint8_t *_p = (uint8_t*) p; \
unsigned long _byte = regnum*HLL_BITS/8; \
unsigned long _fb = regnum*HLL_BITS&7; \
unsigned long _fb8 = 8 - _fb; \
unsigned long _v = val; \
_p[_byte] &= ~(HLL_REGISTER_MAX << _fb); \
_p[_byte] |= _v << _fb; \
_p[_byte+1] &= ~(HLL_REGISTER_MAX >> _fb8); \
_p[_byte+1] |= _v >> _fb8; \
} while(0)
разреженная структура хранения
Разреженное хранилище полезно, когда многие счетчики равны нулю. На рисунке ниже показано состояние общего значения счетчика разреженной памяти.
Когда несколько последовательных сегментов имеют нулевой счетчик, Redis использует байт, чтобы указать, сколько сегментов, которые следуют, имеют нулевой счетчик: 00xxxxxx. Префикс двух нулей означает, что следующее 6-битное целое значение плюс 1 является количеством счетчиков с нулевым значением.Обратите внимание, что здесь добавляется 1, потому что число бессмысленно, если оно равно нулю. Например, 00010101 означает 22 последовательных нулевых счетчика. 6 бит может представлять только до 64 последовательных счетчиков с нулевым значением, поэтому Redis разработал более 64 последовательных счетчиков с нулевым значением.Он использует два байта для представления: 01xxxxxx yyyyyyyy, последние 14 бит могут представлять до 16384 последовательных счетчиков с нулевым значением A нулевой счетчик. Это означает, что начальное состояние сегментов 16384 в структуре данных HyperLogLog, все счетчики равны нулю и могут быть непосредственно представлены 2 байтами.
Если значение счетчика нескольких последовательных сегментов не равно нулю, оно представляется байтом вида 1vvvvvxx. Средние 5 бит представляют значение счетчика, а хвостовые 2 бита представляют несколько последовательных сегментов. Это означает, что все последовательные (xx +1) отсчеты равны (vvvvv + 1). Например, 10101011 означает, что 4 последовательных значения счета равны 11. Обратите внимание, что оба значения должны быть увеличены на 1, потому что любой ноль означает, что значение счетчика равно нулю, поэтому оно должно быть представлено в виде нулевого значения счетчика. Обратите внимание, что значение счетчика может быть представлено только до 32, в то время как одно значение счетчика плотного хранилища HyperLogLog представлено 6 битами, а максимальное значение может быть представлено до 63. Когда определенное значение счетчика разреженного хранилища необходимо настроить так, чтобы оно было больше 32, Redis немедленно преобразует структуру хранения HyperLogLog, чтобы преобразовать разреженное хранилище в плотное хранилище.
Чтобы облегчить выражение разреженного хранилища, Redis назначает по одной инструкции каждому из представленных выше трехбайтовых представлений.
- ZERO:len Один байт представляет 00[len-1], до 64 последовательных нулевых значений счетчика.
- VAL:value,len Один байт представляет 1[значение-1][len-1], а последовательные значения len представляют собой числовое значение значения
- XZERO: len двухбайтный означает 01[len-1], непрерывный до 16384 нулевых значений счетчика
#define HLL_SPARSE_XZERO_BIT 0x40 /* 01xxxxxx */
#define HLL_SPARSE_VAL_BIT 0x80 /* 1vvvvvxx */
#define HLL_SPARSE_IS_ZERO(p) (((*(p)) & 0xc0) == 0) /* 00xxxxxx */
#define HLL_SPARSE_IS_XZERO(p) (((*(p)) & 0xc0) == HLL_SPARSE_XZERO_BIT)
#define HLL_SPARSE_IS_VAL(p) ((*(p)) & HLL_SPARSE_VAL_BIT)
#define HLL_SPARSE_ZERO_LEN(p) (((*(p)) & 0x3f)+1)
#define HLL_SPARSE_XZERO_LEN(p) (((((*(p)) & 0x3f) << 8) | (*((p)+1)))+1)
#define HLL_SPARSE_VAL_VALUE(p) ((((*(p)) >> 2) & 0x1f)+1)
#define HLL_SPARSE_VAL_LEN(p) (((*(p)) & 0x3)+1)
#define HLL_SPARSE_VAL_MAX_VALUE 32
#define HLL_SPARSE_VAL_MAX_LEN 4
#define HLL_SPARSE_ZERO_MAX_LEN 64
#define HLL_SPARSE_XZERO_MAX_LEN 16384
Приведенный выше рисунок может быть выражен в виде инструкции следующим образом
преобразование памяти
Когда значение счетчика достигает определенного уровня, разреженное хранилище будет необратимо преобразовано в плотное хранилище за один раз. Есть два условия для конвертации, и если хоть одно из них выполнено, то конвертация произойдет немедленно. , то есть любое значение счетчика изменяется с 32 на 33, поскольку инструкция VAL больше не может вмещать максимальное значение счетчика, которое она может представлять, равно 32. Общее количество байтов, занимаемых разреженным хранилищем, превышает 3000 байт, этот порог можно настроить параметром hll_sparse_max_bytes.
подсчет кеша
Как упоминалось выше, общее значение, представленное HyperLogLog, рассчитывается на основе формулы коррекции фактора после гармонического усреднения значений счета 16384 сегментов. Чтобы получить это значение, необходимо обойти все сегменты для вычисления, и в середине задействовано множество операций с плавающей запятой. Эта сумма расчета относительно велика.
Таким образом, Redis использует дополнительное поле для кэширования общего значения. Это поле имеет 64 бита. Если старший бит равен 1, это указывает, истек ли срок действия значения. Если он равен 0, оставшиеся 63 бита являются значением счетчика.
Когда значение счетчика любого сегмента в HyperLogLog изменится, срок действия кэша счетчика будет установлен на истечение срока действия, но вычисление не будет запущено немедленно. Вместо этого он не будет запускать пересчет для очистки кеша, пока пользователь явно не вызовет команду pfcount. Обновление кеша должно пройти через значения счетчика 16384 сегментов для гармонического усреднения в плотном хранилище, но в разреженном хранилище нет такого большого объема вычислений. То есть, только когда значение счета относительно велико, можно произвести большой объем вычислений. С другой стороны, если счетчик велик, большинство операций pfadd вообще не вызовут изменения счетчика в корзине.
Это означает, что частые вызовы инструкции pfcount в сильно изменяющемся счетчике HLL могут иметь незначительные проблемы с производительностью. Опасения по поводу этой производительности также упоминаются в блоге автора Redis antirez. Однако автор провел тщательный стресс-тест и обнаружил, что в этом нет ничего страшного: средняя временная сложность инструкции pfcount составляет O(1).
After this change even trying to add elements at maximum speed using a pipeline of 32 elements with 50 simultaneous clients, PFCOUNT was able to perform as well as any other O(1) command with very small constant times.
заголовок объекта
В дополнение к хранению значения счетчика 16384 сегментов HyperLogLog также имеет некоторые дополнительные поля для хранения, такие как общий кэш счетчика и тип хранилища. Поэтому он использует дополнительный заголовок объекта для его представления.
struct hllhdr {
char magic[4]; /* 魔术字符串"HYLL" */
uint8_t encoding; /* 存储类型 HLL_DENSE or HLL_SPARSE. */
uint8_t notused[3]; /* 保留三个字节未来可能会使用 */
uint8_t card[8]; /* 总计数缓存 */
uint8_t registers[]; /* 所有桶的计数器 */
};
Таким образом, общая внутренняя структура HyperLogLog — это заголовок объекта HLL плюс битовая карта значений счетчика из 16384 сегментов. Его внутреннее представление структуры в Redis представляет собой растровое изображение строки. Вы можете рассматривать объекты HyperLogLog как обычные строки.
127.0.0.1:6379> pfadd codehole python java golang
(integer) 1
127.0.0.1:6379> get codehole
"HYLL\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x80C\x03\x84MK\x80P\xb8\x80^\xf3"
Но вы не можете использовать инструкцию HyperLogLog для манипулирования обычными строками, потому что она должна проверять, является ли магическая строка заголовка объекта «HYLL».
127.0.0.1:6379> set codehole python
OK
127.0.0.1:6379> pfadd codehole java golang
(error) WRONGTYPE Key is not a valid HyperLogLog string value.
Но если строка начинается с "HYLL\x00" или "HYLL\x01", то можно использовать команду HyperLogLog.
127.0.0.1:6379> set codehole "HYLL\x01whatmagicthing"
OK
127.0.0.1:6379> get codehole
"HYLL\x01whatmagicthing"
127.0.0.1:6379> pfadd codehole python java golang
(integer) 1
Возможно, вы почувствуете себя очень странно, потому что HyperLogLog должен проверить формат содержимого перед выполнением команды, чтобы проверить, является ли магическая строка заголовка объекта "HYLL" и является ли поле кодировки HLL_SPARSE=0. или HLL_DENSE=1, чтобы определить, является ли текущая строка счетчиком HyperLogLog. Если это плотное хранилище, также необходимо судить, точно ли длина строки равна длине плотного хранилища счетчика.
int isHLLObjectOrReply(client *c, robj *o) {
...
/* Magic should be "HYLL". */
if (hdr->magic[0] != 'H' || hdr->magic[1] != 'Y' ||
hdr->magic[2] != 'L' || hdr->magic[3] != 'L') goto invalid;
if (hdr->encoding > HLL_MAX_ENCODING) goto invalid;
if (hdr->encoding == HLL_DENSE &&
stringObjectLen(o) != HLL_DENSE_SIZE) goto invalid;
return C_OK;
invalid:
addReplySds(c,
sdsnew("-WRONGTYPE Key is not a valid "
"HyperLogLog string value.\r\n"));
return C_ERR;
}
Связь между HyperLogLog и строками аналогична связи между Geo и zset. Вы также можете использовать любую команду zset для доступа к структуре данных Geo, поскольку внутреннее хранилище Geo использует чистый zset для записи географического местоположения элемента.
Техническая онлайн-брошюра из этого отрывка«Глубокое приключение Редиса», начните читать прямо сейчас«Глубокое приключение Редиса»Бар !