1. 需要

当初有个需要，须要对立段时间内登陆的用户数量。这一段时间里可能先后登陆了用户 a、b、c、b、c、a、d 这么多人，可能有人反复登陆，咱们在解决时就须要去重而后返回用户数量。

下面的状况就是基数统计：获取一个汇合 S 去重之后的汇合大小。

一种办法就是应用 hashmap，hashmap 的 key 是用户名，value 是它登陆的次数。在 64 位机器中，golang 在一条记录上应用 24 个字节。当用户成千上万乃至上亿的时候，须要的内存空间就十分大了。

为了节俭内存空间，还有其余办法：$B^+$ 树、Bitmap 等，Redis 中应用 HyperLogLog 来进行粗略的统计，12k 内存能够统计 $2^{64}$ 个数据。

2. 伯努利试验

HyperLogLog 的原理和伯努利试验无关。

投掷硬币，侧面和背面呈现的概率都是 50%。那始终投掷硬币直到第 t 次投掷呈现侧面，这个过程就是一次伯努利试验。

如果进行 n 次伯努利试验，第 1 次试验，n=1，对应的投掷次数为 $t_1$；第 n 次试验，对应的投掷次数为 $t_n$。

进行完这么屡次试验之后，必定有一个最大的投掷次数 $t_{max}$

1. n 次伯努利试验的投掷次数都不大于 $t_{max}$
2. n 次伯努利试验中，至多有一次投掷次数等于 $ t_{max}$

n 和 $ t_{max}$ 存在如下估算关系：

$$
n=2^{t_{max}}
$$

具体的推导我就不说了，概率论的相干内容。

通过屡次伯努利试验的 $ t_{max}$ 能够推导失去进行的伯努利试验的次数 n。那么如果把 HyperLogLog 的一次 ADD 当做一次伯努利试验，那么通过计算每次伯努利试验的最大投掷次数 $ t_{max}$ 应该就能够求出 HyperLogLog 统计的元素数量 n 了。这就是 HyperLogLog 的基本原理。

HyperLogLog 的第 i 次 ADD 的投掷次数 $t_i$ 怎么计算呢？每次 ADD 的元素的 hash 值是一系列 0 和 1 组合的字节码，那么就能够通过统计从某个地位、某个方向开始第一个 1 所在的地位来计算 $ t_i$。例如，0b1010 1000，从最低位向最高位计算失去 $t=4$。

3. HyperLogLog

HyperLogLog 基于 LogLogCounting 等算法，它应用一个简直平均的 hash 函数获取须要统计的元素的 hash 值，而后通过分桶均匀打消误差。HLL(之后均代表 HyperLogLog)把 hash 值分成一个一个的桶，并且用 hash 值的前 k 个位来寻找它的桶地位，桶的数量示意成：

$$
m=2^k
$$

如下图，LSB 示意最低位，MSB 示意最高位，这个 hash 值示意为大端字节序。k=6，阐明一共有 64 个桶。而下图的 hash 值示意的桶地位是 0b00 1101=13。

接下来计算上图 hash 值中后 L - k 的序列中第一个 1 呈现的地位：6。因而在索引号为 13 的桶中进行后续操作，如果桶中的数字比 6 小就设置为 6，否则就不变。

统计每个桶中贮存的值的平均数，就能够计算失去估算的基数值。

HLL 中应用和谐平均数进行计算：

$$
H=\frac{n}{\frac{1}{x_1}+\frac{1}{x_2}+…+\frac{1}{x_n}}=\frac{n}{\sum_{i=1}^n\frac{1}{x_i}}
$$

它的基数估算公式就是：

$$
\hat{n}=\frac{\alpha_mm^2}{\sum_{i=0}^m2^{-M[i]}}
$$

其中，M[i]示意第 i 个桶中的数值，示意为该 hash 值下第一个 1 对应的最大地位。

还有：

$$
\alpha_m=(m\int_0^\infty(log_2(\frac{2+u}{1+u}))^mdu)^{-1}
$$

HLL 的执行步骤能够通过这个 HLL 模仿网站进行理解，建设大抵的印象为后续的内容铺垫。

http://content.research.neust…

能够看出，HLL 占用很少的内存来实现十分大的基数统计，相应的实现也必然很简单，下一节就是剖析其在 redis 中的实现。

4. redis HLL 实现

4.1. HLL 介绍

redis HLL 代码：

https://github.com/crazyStrom…

redis 应用 register（寄存器）来示意 hash 定位的桶，其中的内容就是统计的 hash 值的 L - k 那一部分中第一个 1 的最大地位。上面是 redis 代码中的 HLL 介绍。

redis 应用 [1] 中提出的 64 位 hash 函数，通过在每个寄存器或桶中减少 1bit，将基数统计的下限进步到 $10^9$ 以上。

[1] Heule, Nunkesser, Hall: HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm.*

redis 应用它的 sds 来贮存 HLL，并不创立新的数据类型。

redis 不对 [1] 中的数据结构进行额定的压缩。redis 应用 [2] 中的 HyperLogLog 的算法，惟一不同的是 redis 应用 64 位 hash 函数。

[2] P. Flajolet, Éric Fusy, O. Gandouet, and F. Meunier. Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm.*

redis 在 HLL 中应用两种不同的数据贮存模式：

1. dense 模式。HLL 的每个 entry（每个寄存器中的内容）应用一个 6 位的数字示意。
2. sparse 模式。当 HLL 中有很多寄存器为 0 时对这些寄存器进行压缩，以进步内存利用率。

4.1.1. HLL header

redis 应用 hllhdr 来持有一个 HLL：

struct hllhdr {char magic[4];      /* "HYLL" */
    // 编码格局：sparse 或者 dense
    uint8_t encoding;   /* HLL_DENSE or HLL_SPARSE. */
    uint8_t notused[3]; /* Reserved for future use, must be zero. */
    // 缓存的基数统计值
    uint8_t card[8];    /* Cached cardinality, little endian. */
    // 理论的寄存器们，dense 有 16384 个 6bit 寄存器
    uint8_t registers[]; /* Data bytes. */};

dense 和 sparse 模式都应用 16 字节的 header。

• 前四个字节是 HYLL，固定不变。
• encoding 占用一个字节，示意 HLL 的编码模式：HLL_DENSE 和 HLL_SPARSE。
• notused 占用三个字节，进行占位用的。
• card 占用八个字节，用小端字节序贮存的 64 位整数，保留最近的基数计算结果。如果从上一次基数计算到当初，数据结构都没有批改过，card 中的内容能够从新应用。redis 应用 card 最高位示意该数据是否可用，如果最高位是 1，表明数据被批改了，就须要从新计算基数并缓存到 card 中。

registers 示意这个 HLL 所持有的 dense 或 sparse 模式的数据。

4.1.2. dense 模式

HLL 的 dense 编码模式应用的寄存器都是 6bit，并且是间断排列。一个字节是 8bit，因而一个字节会同时持有两个寄存器的局部或全副 bit。

dense 模式的寄存器都是从 LSB 到 MSB 进行编码，即从最低位到最高位。如果以后字节不够贮存寄存器的残余 bit，就会依据须要应用下一个字节。

上图中，从左到右有三个字节，蕴含了四个寄存器 0 -3。第 0 个字节的后六位贮存的是 0 号寄存器的内容，第 0 个字节的前两位和第 1 个字节的后四位贮存的是 1 号寄存器的内容，以此类推，这就是 dense 的贮存模式。

4.1.3. sparse 模式

HLL 应用三种操作码实现对其数据结构的 sparse 编码。这三个操作码别离是 ZERO、XZERO 和 VAL，其中两个操作码别离应用一个字节，另一个操作码应用两个字节。

上面介绍这三种操作码。

• ZERO 操作码占用一个字节，示意为 00xxxxxx，后六位 xxxxxx+ 1 示意有 N 个间断的寄存器设置为 0，这个操作码能够示意 1 -64 个间断的寄存器被设置为 0。
• XZERO 操作码占用两个字节，示意为 01xxxxxx yyyyyyyy。xxxxxx 是高位，yyyyyyyy 是低位。这十四位 + 1 示意有 N 个间断的寄存器设置为 0. 这个操作码能够示意 0 -16384 个寄存器被设置为 0。
• VAL 操作码占用一个字节，示意为 1vvvvvxx。它蕴含一个 5bit 的 vvvvv 示意寄存器值，2bit 的 xx+ 1 示意有这么多个间断的寄存器被设置为 vvvvv。这个操作码示意能够示意 1 - 4 个寄存器被设置 1 -32 的值。

sparse 无奈示意寄存器值超过 32 的寄存器，然而在 HLL 中超过 32 的寄存器值很少见。当没有这种状况时，sparse 要比 dense 具备更高的内存效率，而如果有寄存器值超过 32 时，HLL 会从 sparse 转换为 dense。

sparse 用来示意某个地位的寄存器内容，它是地位性的。例如，一个空 HLL 示意成 01111111 11111111，这阐明有 16384 个寄存器被设置为 0，记作 XZERO:16384。

再例如，一个 HLL 只有三个寄存器值不是 0，地位别离是 1000，1020，1021，值别离是 2，3，3，这个 HLL 的 sparse 示意为：

XZERO:1000 0-999 号寄存器设置为 0

VAL:2,1 1 个寄存器设置为 2，即 1000 号寄存器

ZERO:19 1001-1019 号寄存器为 0

VAL:3,2 两个寄存器设置为 3，别离是 1020、1021 号寄存器

XZERO:15362 从 1022-16383 号寄存器设置为 0

当基数比拟小的时候，HLL 有很高的的利用率。下面的例子中应用了 7 个字节示意所有的 HLL 寄存器，而 dense 应用 12k 的内存。

然而，sparse 在进行 2000-3000 的基数计算时效率高，然而基数更大时，sparse 转换成 dense 效率更高。通过定义 server.hll_sparse_max_bytes 实现 sparse 切换为 dense 时 sparse 的最大长度。

4.2. redis HLL 实现代码

hllhdr 定义：

struct hllhdr {char magic[4];      /* "HYLL" */
    // 编码格局：sparse 或者 dense
    uint8_t encoding;   /* HLL_DENSE or HLL_SPARSE. */
    uint8_t notused[3]; /* Reserved for future use, must be zero. */
    // 缓存的基数统计值
    uint8_t card[8];    /* Cached cardinality, little endian. */
    // 理论的寄存器们
    uint8_t registers[]; /* Data bytes. */};

4.2.1. 相干定义和宏

redis 运行很快的起因就是应用了大量的宏定义。

后面说到，redis 应用 card 作为缓存进步 HLL 的效率。而 card 是否可用通过其最高位来判断的，当最高位设置为 1 时，阐明 HLL 被批改了，card 的缓存不可用，须要从新计算。

/* The cached cardinality MSB is used to signal validity of the cached value. */
// card 的第八位设置为 1 示意缓存不可用
#define HLL_INVALIDATE_CACHE(hdr) (hdr)->card[7] |= (1<<7)
#define HLL_VALID_CACHE(hdr) (((hdr)->card[7] & (1<<7)) == 0)

残余的就是一些罕用定义和宏。

#define HLL_P 14 /* The greater is P, the smaller the error. */
// HLL 应用 16384 个寄存器：0b 0100 0000 0000 0000
#define HLL_REGISTERS (1<<HLL_P) /* With P=14, 16384 registers. */
// HLL 的掩码用来找地位，0x0011 1111 1111 1111
#define HLL_P_MASK (HLL_REGISTERS-1) /* Mask to index register. */
#define HLL_BITS 6 /* Enough to count up to 63 leading zeroes. */
#define HLL_REGISTER_MAX ((1<<HLL_BITS)-1)
#define HLL_HDR_SIZE sizeof(struct hllhdr)
#define HLL_DENSE_SIZE (HLL_HDR_SIZE+((HLL_REGISTERS*HLL_BITS+7)/8))
#define HLL_DENSE 0 /* Dense encoding. */
#define HLL_SPARSE 1 /* Sparse encoding. */
#define HLL_RAW 255 /* Only used internally, never exposed. */
#define HLL_MAX_ENCODING 1

4.2.2. 位运算的宏

redis 应用一系列的宏简化 HLL 的 dense 和 sparse 模式的相干位运算。

4.2.2.1. dense 运算

HLL 应用 8bit 的字节数组 registers 来贮存 dense 的 6bit 寄存器组。因而须要把 8bit 数组分成 6bit 数组并进行取值和设置值的操作。redis 应用宏来保障运行速度。

上图示意的是大端字节序，最高位 (MSB) 在右边。redis 从最低位向最高位顺次遍历。

(1) 取寄存器值

例如，获取在地位 pos= 1 处的寄存器值，寄存器编号从 0 开始。

保留 1 号寄存器局部内容的第一个字节是 b0：1100 0000。

b0 = 6 * pos / 8

1 号寄存器的第一位是这么计算的：

fb = 6 * pos % 8 -> 6

把 b0 右移 fb 位：1100 0000 >> fb = 0000 0011

把 b1 左移 8 -fb 位：2222 1111 << (8-fb) = 2211 1100

将这两个字节进行 OR 操作：0000 0011 | 2211 1100 = 2211 1111

而后将后果和 0011 1111 进行 AND 操作以打消高 2 位：2211 1111 & 0011 1111 = 0011 1111，这就是 1 号寄存器的值。

另一个例子，获取 0 号寄存器的内容。这个状况下，这个寄存器的六位都在一个字节 b0 中：1100 0000。

b0 = 6 * pos / 8 = 0

0 号寄存器的第一位的地位：

fb = 6 * pos % 8 = 0

因而将以后字节 b0 右移 0 位：1100 0000 >> 0 = 1100 0000

下一字节 b1 左移 8 位：2222 1111 << 8 = 0000 0000

挪动后的两个字节进行 OR 操作：1100 0000 | 0000 0000 = 1100 0000

而后将后果和 0011 1111 进行 AND 操作打消高 2 位：1100 0000 & 0011 1111 = 0000 0000

因而寄存器 0 的内容就是 00 0000

(2) 设置寄存器值

设置寄存器的值就比较复杂了，假如 val=0b 00cd efgh 是须要设置的新值。须要两步，第一步革除寄存器的相干位，第二部通过或操作设置新的位。

例如，设置 1 号寄存器的值，它的第一个字节是 b0。

这个例子中，fb=6。

为了生成一个 AND 掩码来革除 b0 的相干位，学生成一个值为 63 的初始掩码 0b0011 1111。左移 fb 位，而后取反码：!(0011 1111 << fb) = 0011 1111。

让新掩码和 b0 进行 AND 操作以革除寄存器 1 的相干位：0011 1111 & 1100 0000 = 0000 0000

把 val 左移 fb 位，和上述后果进行 OR 操作就设置了 b0 的新值：b0 = (val << fb) OR b0 = (00cd efgh << 6) OR 0000 0000 = gh00 0000

接下来就是设置 b1 的相干位。b1 的初始值为 2222 1111。

应用 63 构建 AND 掩码，右移 8 -fb 位，而后翻转：!(0011 1111 >> (8-fb)) = 1111 0000。

将新掩码和 b1 进行 AND 操作以革除相干位：b1 = 1111 0000 & 2222 1111 = 2222 0000

而后将 val = 0b 00cd efgh 右移 8 -fb 位，而后和 b1 进行 OR 操作以设置相干位：b1 = (00cd efgh >> (8-fb)) | b1 = 2222 cdef

(3) redis 实现代码

redis 的实现代码就很简略，有点 C 根底的都能看懂。

/* Store the value of the register at position 'regnum' into variable 'target'.
 * 'p' is an array of unsigned bytes. */
#define HLL_DENSE_GET_REGISTER(target,p,regnum) do { \
    uint8_t *_p = (uint8_t*) p; \
    // 这个寄存器在第_byte 个字节
    unsigned long _byte = regnum*HLL_BITS/8; \
    // 这个寄存器在第_byte 个字节的第_fb 位
    unsigned long _fb = regnum*HLL_BITS&7; \
    unsigned long _fb8 = 8 - _fb; \
    unsigned long b0 = _p[_byte]; \
    unsigned long b1 = _p[_byte+1]; \
    // b0 的高 fb 位、b1 的低 fb8 位
    target = ((b0 >> _fb) | (b1 << _fb8)) & HLL_REGISTER_MAX; \
} while(0)

/* Set the value of the register at position 'regnum' to 'val'.
 * 'p' is an array of unsigned bytes. */
#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)

4.2.2.2. sparse 运算

sparse 模式就不须要查找对应的位了，然而须要辨别它的操作码类型、操作码笼罩的寄存器范畴、以及相应的操作码设置。

ZERO 示意为 00xx xxx，XZERO 示意为 01xx xxxx xxxx xxxx，VAL 示意为 1vvv vvxx。因而通过每个字节的前两位能够判断对应的操作码。

#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)

ZERO 的后六位示意寄存器的长度，XZERO 的后 14 位示意间断寄存器的长度，VAL 的后两位是寄存器的长度，vvvvv 是寄存器值，通过这些特色能够取得这三种操作码的相干信息。

#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)

VAL 的操作码后两位是寄存器长度，两头 5 位 vvvvv 是寄存器值，因而设置 VAL 操作码的 val 和长度 len 的代码如下：

#define HLL_SPARSE_VAL_SET(p,val,len) do { \
    *(p) = (((val)-1)<<2|((len)-1))|HLL_SPARSE_VAL_BIT; \
} while(0)

其余的设置 ZERO、XZERO 的长度也是这个原理：

#define HLL_SPARSE_ZERO_SET(p,len) do { \
    *(p) = (len)-1; \
} while(0)
#define HLL_SPARSE_XZERO_SET(p,len) do { \
    int _l = (len)-1; \
    *(p) = (_l>>8) | HLL_SPARSE_XZERO_BIT; \
    *((p)+1) = (_l&0xff); \
} while(0)

4.2.3. 相干函数

HLL 应用了一个通用的 hash 算法，在不同的计算机架构上都能够应用，这里不再叙述，本文只关注 HLL 的实现算法。

4.2.3.1. ADD

HLL 只有增加数据能力进行统计。redis 实现了两种 ADD，别离利用于 dense、sparse。

(1) hllPatLen

其中，这两种模式都须要一个函数来统计该数据 hash 值的第一个 1 的地位。

int hllPatLen(unsigned char *ele, size_t elesize, long *regp) 

当客户端将一个 string 增加给 HLL 时，这个函数返回其局部 hash 子串的最长 0 綴，也是第一个 1 呈现的地位，而后加 1 返回。

具体如下步骤：

1. 计算增加 HLL 的 string 元素的 64 位 hash 值
2. 通过 hash 值和 0b0011 1111 进行 AND 操作以取得对应的桶索引，上图对应 13 号桶
3. 而后从第 6 位开始统计最长 0 綴：5，将其加一就是第一个 1 所在的地位

(2) hllAdd

/* Call hllDenseAdd() or hllSparseAdd() according to the HLL encoding. */
int hllAdd(robj *o, unsigned char *ele, size_t elesize)

所有要增加给 HLL 的数据都通过 hllAdd 这个函数进行。

这个函数通过 o 指向的 hllhdr 的编码模式不同，别离调用 hllDenseAdd 或 hllSparseAdd。

    switch(hdr->encoding) {case HLL_DENSE: return hllDenseAdd(hdr->registers,ele,elesize);
    case HLL_SPARSE: return hllSparseAdd(o,ele,elesize);
    default: return -1; /* Invalid representation. */

(3) hllDenseAdd

int hllDenseAdd(uint8_t *registers, unsigned char *ele, size_t elesize)

这个函数向 HLL 的 dense 模式寄存器增加元素 ele。

参数 registers 是以 sds 的模式贮存的，因而其长度蕴含 16384 个 6bit 寄存器加上 sds 的 null 终止符。

这个函数的逻辑就很简略了。

1. 应用 hllPatLen 取得 ele 的 hash 值对应的桶索引 index 和最长 0 綴 count
2. 获取 index 地位寄存器的值 oldcount
3. 如果 oldcount < count，就将该地位寄存器设置为 count，返回 1；否则返回 0

(4) hllSparseAdd

int hllSparseAdd(robj *o, unsigned char *ele, size_t elesize)

这个函数向 HLL 的 sparse 模式数据结构中增加元素 ele。

实际上也不会把 ele 增加进去，而是把计算的最长 0 綴增加在 HLL 中。

参数 o 实际上是一个持有 HLL 的 string 对象，这个函数应用这样的对象是有益处的，就是能够在须要的时候扩大这个 string，在它前面增加须要的字节。

在函数中，HLL 可能会从 sparse 转换为 dense 模式贮存数据。起因有两个：须要设置的寄存器值超过了 sparse 反对的范畴；增加之后的 sparse 数据的大小超过了 server.hll_sparse_max_bytes。

首先，计算新元素的索引 index 和最长 0 綴 count。

如果 count > 32，阐明 sparse 无奈应用了，转换为 dense 模式，而后调用 hllDenseAdd 并返回。

如果 count <= 32，进行后续计算。

在增加数据时可能呈现 XZERO 别离成 XZERO-VAL-XZERO 的状况，这也是最简单的状况，因而应用 sdsMakeRoomFor 增加足够的空间。

1. 步骤一：定位须要批改的操作码

XZERO 占用两个字节，ZERO 和 VAL 占用一个字节；通过这些操作码中贮存的长度与 index 比拟以取得须要更新的操作码地位：*p。

2. 步骤二：在另一块内存中更新操作码

通过步骤一的计算后，变量 first 指的是 p 指向的以后操作码中蕴含的第一个寄存器索引地位。

变量 next 和 prev 别离保留前面和后面一个操作码。如果 next 是 null 阐明 p 指向的操作码是最初一个；如果 prev 是 null 阐明 p 指向的操作码是第一个。

变量 span 以后操作码笼罩的寄存器数量。

更新操作码具备不同的状况：

A) 如果以后操作码是 VAL 并且其值 >= count，那就不须要更新以后操作码，函数返回 0 示意没有数据更新

B) 如果以后操作码是 VAL 并且长度是 1，阐明以后操作码只笼罩一个寄存器，那间接更新这个操作码的值为 count

C) 如果以后操作码是 ZERO 并且长度是 1，那间接把这个操作码改成 VAL 并且更新值为 count，长度为 1

D) 剩下的就是更广泛的状况了。例如，以后操作码是长度大于 1 的 VAL、长度大于 1 的 ZERO 或者一个 XZERO。这种状况下，原来的操作码须要决裂成多个操作码。最简单的就是 XZERO 决裂成 XZERO-VAL-XZERO，这将须要 5 个字节贮存。

redis 将新的操作码序列写到一个额定的缓冲区 new，长度是 newlen。之后这个新序列会替换就序列。新序列可能会比旧序列长，因而在插入新序列时可能要将原操作码右侧的字节向后挪动。

3. 步骤三：应用新序列替换旧操作码序列，具体看代码。
4. 步骤四：如果间断的操作码值雷同的话，合并这些操作码。

hllSparseAdd 的代码太长了，不适宜在博客中贴出来，能够看我在文章结尾提交到 github 的代码。

4.2.3.2. count

(1) hllCount

uint64_t hllCount(struct hllhdr *hdr, int *invalid)

这个函数返回 HLL 的近似基数统计值，基于所有寄存器的和谐平均数。如果这个 HLL 对象的 sparse 是有效的，invalid 会设置为非零值。

hllCount 反对一个非凡的外部编码：HLL_RAW。HLL_RAW 应用 8bit 寄存器而不是 HLL_DENSE 的 6bit 寄存器，这样会减速 PFCOUNT 的计算。

在函数中，为了减速计算，redis 提前构建了一个表 PE，长度为 64，$$PE[i] = \frac{1}{2^i}$$。这样之后就能够查表进行计算。

    static int initialized = 0;
    static double PE[64];
    // 应用 initialized 来初始化一次 PE
    if (!initialized) {PE[0] = 1; /* 2^(-reg[j]) is 1 when m is 0. */
        for (j = 1; j < 64; j++) {/* 2^(-reg[j]) is the same as 1/2^reg[j]. */
            PE[j] = 1.0/(1ULL << j);
        }
        /**
         * PE[1] = 1/2
         * PE[2] = 1/4
         * PE[3] = 1/8
         * ...
         */
        initialized = 1;
    }

接下来，依据 HLL 的编码模式抉择 hllDenseSum、hllSparseSum 或 hllRawSum 计算 $SUM(2^{-register[0..i]})$，记为 E。

/* Compute SUM(2^-register[0..i]). */
    if (hdr->encoding == HLL_DENSE) {E = hllDenseSum(hdr->registers,PE,&ez);
    } else if (hdr->encoding == HLL_SPARSE) {
        E = hllSparseSum(hdr->registers,
                         sdslen((sds)hdr)-HLL_HDR_SIZE,PE,&ez,invalid);
    } else if (hdr->encoding == HLL_RAW) {E = hllRawSum(hdr->registers,PE,&ez);
    } else {redisPanic("Unknown HyperLogLog encoding in hllCount()");
    }

依据 E 的范畴采取不同的算法：当基数统计小于 HLL 桶的四分之一时应用 LINEARCOUNTING 算法；当基数统计更大时，通过一个 bias 变量调节计算误差。

    if (E < m*2.5 && ez != 0) {E = m*log(m/ez); /* LINEARCOUNTING() */} else if (m == 16384 && E < 72000) {
        /* We did polynomial regression of the bias for this range, this
         * way we can compute the bias for a given cardinality and correct
         * according to it. Only apply the correction for P=14 that's what
         * we use and the value the correction was verified with. */
        double bias = 5.9119*1.0e-18*(E*E*E*E)
                      -1.4253*1.0e-12*(E*E*E)+
                      1.2940*1.0e-7*(E*E)
                      -5.2921*1.0e-3*E+
                      83.3216;
        E -= E*(bias/100);
    }

(2) hllDenseSum

double hllDenseSum(uint8_t *registers, double *PE, int *ezp)

这个函数是计算 dense 模式下各个寄存器的 $SUM(2^{-register[0..i]})$。

最简略的就是通过之前的宏定义在 16384 次循环中获取每个寄存器的值，并通过传入的 PE 表计算总和。而在 redis 中，一次循环计算 16 个寄存器，循环 1024 次以减速计算。在计算时，PE 表中的元素是 double 值，redis 将每个寄存器值映射在 PE 表中的后果两两相加以打消误差。

/* Additional parens will allow the compiler to optimize the
             * code more with a loss of precision that is not very relevant
             * here (floating point math is not commutative!). */
            // 两两相加减小误差
            E += (PE[r0] + PE[r1]) + (PE[r2] + PE[r3]) + (PE[r4] + PE[r5]) +
                 (PE[r6] + PE[r7]) + (PE[r8] + PE[r9]) + (PE[r10] + PE[r11]) +
                 (PE[r12] + PE[r13]) + (PE[r14] + PE[r15]);

(3) hllSparseSum

double hllSparseSum(uint8_t *sparse, int sparselen, double *PE, int *ezp, int *invalid) 

这个函数就是将 sparse 指向的每个字节进行辨认，判断是哪一种操作码，而后通过查 PE 表计算总和返回。

(4) hllRawSum

double hllRawSum(uint8_t *registers, double *PE, int *ezp) 

这个函数和之前的思路一样，它应用 8bit 寄存器贮存内容，并且在一次循环中计算 8 个寄存器的内容。

4.2.3.3. sparse to dense

int hllSparseToDense(robj *o) 

这个函数用来将 sparse 转换为 dense，转换条件是：新元素的最长 0 綴 > 32 或以后 sparse 模式的数据长度超过了 server.hll_sparse_max_bytes。

HLL 中，redis 应用 sds 来贮存 sparse 和 dense 模式的数据。

该函数的实现逻辑也比较简单，前提是本文之前对于 dense、sparse 以及各种操作码的内容都了解了。

1. 应用 sdsnewlen 调配 HLL_DENSE_SIZE 大小的内存 dense，初始化 index 索引为 0

2. 遍历参数 o 指向的 sparse 数据，并以此设置 index 指向的 dense 寄存器内容：

   • 如果是 ZERO 和 XZERO，间接设置该操作码笼罩的寄存器为 0，实际上也没有设置，间接跳过这些寄存器了，减少 index 相应的值。
   • 如果是 VAL，取出该操作码的值和长度，将其笼罩的 dense 寄存器设置为该值，减少 index。
3. 开释 sparse 数据占用的内存。

5. 总结

乍一开始可能感觉 HyperLogLog 好难，还要学概率，还有什么伯努利过程，然而它就是单纯的一个公式就解决了，急躁看上来还是很有播种的，下一步能够依据这些内容应用 golang 实现一个本人的 HyperLogLog 来加深了解。