引言


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

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

下面都把HyperLogLog简称为HLL。

HyperLogLog的redisObject


上一篇文章说过redisObject的type字段表示对外暴露的类型,encoding代表底层数据结构实现。但是HLL比较奇怪,它的type统一是REDIS_STRINGhyperloglog.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编码转换


不管是哪种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:

一个刚刚创建的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分别是100001000010

紧凑表示的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只能是紧凑表示的。