引言

阅读该文前，应该先具备Hyperloglog的基本知识，如果不具备的话，可以阅读我之前写的一篇通俗易懂的介绍，这里主要分析Redis中HyperLogLog的实现。

文中经常会提到的几个概念：

HyperLogLog能够用一串固定长度的字节统计数据流的基数，而且会把这些字节分为一个个桶，Redis中将每个桶称为一个register。Redis的HyperLogLog结构统一采用16384个register
数据流中不同的数据会根据其hash的前几位分到不同的register里，每个register存储的是数据流中目前为止被分到这个register的数据的最大前导0数目，称之为count

下面都把HyperLogLog简称为HLL。

HyperLogLog的redisObject

上一篇文章说过redisObject的type字段表示对外暴露的类型，encoding代表底层数据结构实现。但是HLL比较奇怪，它的type统一是REDIS_STRING，hyperloglog.c:1114:

    o = createObject(REDIS_STRING,s);
    hdr = o->ptr;
    memcpy(hdr->magic,"HYLL",4);
    hdr->encoding = HLL_SPARSE;

encoding有下面几种：

encoding	含义
HLL_SPARSE	稀疏表示，适合大多数register都为0的情况，但是存储的count不能超过32（<=32）。刚刚创建HLL大多就是这个格式
HLL_DENSE	紧凑表示，老老实实地每个register用6个bit表示（即存储的count不能超过64），总共16384个register，需要12KB内存
HLL_RAW	只是一个临时的存储格式，一个register用8个bit表示，只有在merge两个HLL的时候临时产生一下，之后很快就会消失，或者转换成HLL_DENSE

这几种格式的转换条件如下：

hyperloglog编码转换

HLL_SPARSE每个register最大存储的count不能超过32，看起来很小，其实如果每个register都填满的话（现实中这是不可能的，早就升级成HLL_DENSE了），其代表的基数为2的32次方，即4294967296
HLL_DENSE如果填满的话，则代表基数为2的64次方，即18446744073709551616，已经远远超过地球总人口了，所以可以放心地用它来计算你网页的PV，UV了
HLL_RAW因为只是个临时结构，就没有画在上面，之后将merge几个HLL时会再提它

头

不管是哪种encoding，它们都有统一的头，hyperloglog.c:182：

struct hllhdr {
    /* "HYLL" magic number,所有HLL都是一样的 */
    char magic[4];      
    uint8_t encoding;   /* HLL_DENSE or HLL_SPARSE. */
    uint8_t notused[3]; /* 全0,没有用处 */
    /* 用于缓存上一次计算的基数，如果两次访问之间该HLL没有改动的话，则直接返回缓存
       最高位（即card[0]的最高位）为0表示缓存有效，为1表示缓存失效
    */
    uint8_t card[8];
    /* 具体的数据 */
    uint8_t registers[]; 
};

在registers字段之前的16个字节都是头，而register则是具体的HLL存储的数据，根据encoding的不同，或者是稀疏表示，或者是紧凑表示。

稀疏表示

稀疏表示的registers由一个个元素，这些元素就像积木一样一个个搭在一次，Redis称它们为opcode，有以下几种opcode：

ZERO：占用1个byte，可以表示1~64个连续的存储0的register，格式为00xxxxxx
VAL：占用1个byte，格式为1vvvvvxx，其中v表示register存储的count，x表示连续的存有相同值的register数目，从位数上可以看出，count只能是1~32，而且连续出现的次数只能是1~4
XZERO：占两个字节，格式为01yyyyyy yyyyyyyy，当连续的0太多，ZERO存不下时，使用这个，它有14位可以存储0的数目，即连续出现的次数可以是1~16384

一个刚刚创建的HLL，因为所有register都是0，它采用稀疏表示，只需要两个字节即可（其实就是一个XZERO）:01111111 11111111

稀疏表示在实现HyperLogLog的各种操作时往往比较复杂，涉及到opcode的重组和拆分，比如刚刚创建的HLL就一个XZERO，当有数据到来的时候，为记录count，需要把它拆成XZERO-VAL-XZERO，在一些更加复杂的情况下还涉及后面opcode的后移，以及将多余的opcode合并等等。所以你在看稀疏表示的相关操作源码的时候，一般都非常的长，如果只是弄明白每个命令背后的HyperLogLog算法操作，推荐看紧凑表示的相关源码。

紧凑表示

紧凑表示的长度是固定的，即一个12KB的byte数组，其中每6bit表示一个register，但是因为采用的是小端模式（即低地址放低位），可能不那么符合直觉：

紧凑表示的registers

上图中的两个byte里面有两个register，count分别是100001和000010

紧凑表示的HyperLogLog相关操作代码都是非常简单易懂，下面就来看一看。

PFADD

添加数据流中的最新数据：

PFADD a "aaaa"

紧凑表示的操作代码是hllDenseAdd函数：

int hllDenseAdd(uint8_t *registers, unsigned char *ele, size_t elesize) {
    uint8_t oldcount, count;
    long index;

    //计算出该数据属于第几个register，并赋给index
    //count是当前register中的值
    count = hllPatLen(ele,elesize,&index);
    HLL_DENSE_GET_REGISTER(oldcount,registers,index);
    if (count > oldcount) {
        HLL_DENSE_SET_REGISTER(registers,index,count);
        return 1;
    } else {
        return 0;
    }
}

在hllPatLen函数中会计算出ele该分到第几个register以及该register的当前值。hllPatLen会先对ele求64位的murmurhash，然后去其低14位作为其所属的register编号，之后从第15位开始数0，将数到的0的数目加1作为count：

int hllPatLen(unsigned char *ele, size_t elesize, long *regp) {
    uint64_t hash, bit, index;
    int count;

    hash = MurmurHash64A(ele,elesize,0xadc83b19ULL);
    index = hash & HLL_P_MASK; /* Register index. 取低6位 */
    // 最高位置1
    hash |= ((uint64_t)1<<63); /* Make sure the loop terminates. */
    bit = HLL_REGISTERS; /* First bit not used to address the register. */
    count = 1; /* Initialized to 1 since we count the "00000...1" pattern. */
    while((hash & bit) == 0) {
        count++;  // 数0
        bit <<= 1;
    }
    *regp = (int) index;
    return count;
}

假设ele求hash的结果为000100 000100，其低6位为4，表示该分到第四个register，从7位开始有两个连续的0，所以count应该为2

PFCOUNT

PFCOUNT不仅可以计算单个HLL的基数，还可以计算多个HLL合并后的基数。

PFCOUNT a
PFCOUNT a b c

其实就是HyperLogLog的公式走一遍，在代码中可以看到熟悉求DV公式，hyperloglog.c:998:

    E = (1/E)*alpha*m*m;

在计算多个HLL合并后的基数时，会先创建一个编码为HLL_RAW的临时HLL，之后将要合并的所有HLL中对应的register取最大赋值给临时HLL的对应register，hyperloglog.c:1044：

        // 遍历要合并的HLL的register
        for (i = 0; i < HLL_REGISTERS; i++) {
            // 取出第i个register的值，赋给val
            HLL_DENSE_GET_REGISTER(val,hdr->registers,i);
            // max即临时HLL的register
            if (val > max[i]) max[i] = val;
        }

之后再使用这个临时的HLL计算基数。

PFMERGE

可以将多个HLL合并成一个HLL并存到一个key中，比如将a，b合并成c中：

PFMERGE c a b

操作和上面PFCOUNT合并多个HLL也是类似的，先创建一个编码为HLL_RAW的HLL，之后将要合并的所有HLL中对应的register取最大赋值给临时HLL的对应register，之后将该HLL的编码转成HLL_DENSE，需要注意的是，PFMERGE合产生的key只能是紧凑表示的。