Redis源码剖析--基数统计hyperloglog

Redis源码剖析–基数统计

基数统计

算法思路

hyperloglog实现

hyperloglog小结

Update 2016-12-9

Redis中hyperloglog是用来做基数统计的，其优点是：在输入元素的数量或者体积非常非常大的时候，计算基数所需的空间总是固定的，并且是很小的。在Redis里面，每个Hyperloglog键只需要12Kb的大小就能计算接近2^64个不同元素的基数，但是hyperloglog只会根据输入元素来计算基数，而不会存储元素本身，所以不能像集合那样返回各个元素本身。

基数统计

什么是基数呢？基数是指一个集合中不同元素的个数。假设有一组数据{1，2，3，3，4，5，4，6}{1，2，3，3，4，5，4，6}，除去重复的数字之后，该组数据中不同的数有6个，则该组数据的基数为6。

那什么是基数统计呢？基数统计是指在误差允许的情况下估算出一组数据的误差。

从上述的概念中，我们可以很容易想到基数统计的用途，假设需要计算出某个网站一天中的独立ip访问量，相同ip访问多次的话值算作一次。这个问题即可转换成求一天内所有访问该网站的ip数组的基数。关键在于如何求这个基数？下面我就以最易懂的方法来给大家讲一下。

算法思路

伯努利过程

投掷一次硬币出现正、反两面的概率均为\(¹⁄₂\)。如果我们不断的投掷硬币，直到出现一次正面，在这样的一个过程中，投掷一次得到正面的概率为\(¹⁄₂\)，投掷两次才得到正面的概率为\(¹⁄₂^{2}\)….依次类推，投掷k次才得到一次正面的概率为\(¹⁄₂^{k}\)。这个过程在统计学上称为伯努利问题。

有了以上的分析后，我们继续来思考下面两个问题：

• 进行n次伯努利过程，所有投掷次数都小于k的概率
• 进行n次伯努利过程，所有投掷次数都大于k的概率

针对第一个问题，在一次伯努利过程中，投掷次数大于k的概率为\(¹⁄₂^{k}\)，也就是投了k次反面的概率。因此，在一次过程中投掷次数不大于k的概率为\(1-¹⁄₂^{k}\)。因此n次伯努利过程所有投掷次数都不大于k的概率为 $$ P(x \leq k)=(1-¹⁄₂^{k})^{n}$$

很显然，第二个问题，n次伯努利过程，所有投掷次数都不小于k的概率为 $$ P(x \geq k)=(1-¹⁄₂^{k-1})^{n}$$

从上述公式中可得出结论：当n远小于2k2k当成n的一个粗糙估计。

基数统计

将上述伯努利过程转换到比特位串上，假设我们有8位比特位串，每一位上出现0或者1的概率均为\(¹⁄₂\)，投掷k次才得到一次正面的过程可以理解为第k位上出现第一个1的过程。

那么针对一个数据集来说，我们用某种变换将其转换成一个比特子串，就可以根据上述理论来估算出该数据集的技术。例如数据集转换成00001111，第一次出现1的位置为4，那么该数据集的基数为16。

于是现在的问题就是如何将数据集转换成一个比特位串？很明显，哈希变换可以帮助我们解决这个问题。

选取一个哈希函数，该函数满足一下条件：

• 具有很好的均匀性，无论原始数据集分布如何，其哈希值几乎服从均匀分布。这就保证了伯努利过程中的概率均为1/2
• 碰撞几乎忽略不计，也就是说，对于不同的原始值，其哈希结果相同的概率几乎为0
• 哈希得出的结果比特位数是固定的。

有了以上这些条件，就可以保证”伯努利过程“的随机性和均匀分布了。

接下来，对于某个数据集，其基数为n，将其中的每一个元素都进行上述的哈希变换，这样就得到了一组固定长度的比特位串，设f(i)f(i)的最大值，这样，我们就可以得出以下结论：

• 当n远小于2fmax2fmax为当前值的概率为0

这样一来，我们就可以将2fmax2fmax作为n的一个粗糙估计。当然，在实际应用中，由于数据存在偶然性，会导致估计量误差较大，这时候需要采用分组估计来消除误差，并且进行偏差修正。

所谓分组估计就是，每一个数据进行hash之后存放在不同的桶中，然后计算每一个桶的fmaxfmax。

hyperloglog实现

数据结构

每个hyperloglog键由一下结构体组成：

struct hllhdr {
    char magic[4];      // 固定‘HYLL’，用于标识hyperloglog键
    uint8_t encoding;   // 编码模式，有密集标识Dence和稀疏模式sparse
    uint8_t notused[3]; // 未使用字段，留着日后用
    uint8_t card[8];    // 基数缓存，存储上一次计算的基数
    uint8_t registers[]; // 桶个数，用来存放数据，Redis中大小为16384
};

添加元素

Redis提供一下命令来向hyperloglog键中添加数据。

PFADD key element [element ...]

其源码实现如下：

void pfaddCommand(client *c) {
    robj *o = lookupKeyWrite(c->db,c->argv[1]);
    struct hllhdr *hdr;
    int updated = 0, j;
    // 客户端交互部分，此处可以放着以后理解
    if (o == NULL) { 
        // 创建一个hyperloglog键
        o = createHLLObject();
        dbAdd(c->db,c->argv[1],o);
        updated++;
    } else {
        // 判断是否是一个hyperloglog键，判断前四个字节是否为'HYLL'
        if (isHLLObjectOrReply(c,o) != C_OK) return;
        o = dbUnshareStringValue(c->db,c->argv[1],o);
    }
    // 调用hllAdd函数来添加元素
    for (j = 2; j < c->argc; j++) {
        int retval = hllAdd(o, (unsigned char*)c->argv[j]->ptr,
                               sdslen(c->argv[j]->ptr));
        switch(retval) {
        case 1:
            updated++;
            break;
        case -1:
            addReplySds(c,sdsnew(invalid_hll_err));
            return;
        }
    }
    hdr = o->ptr;
    if (updated) {
        signalModifiedKey(c->db,c->argv[1]);
        notifyKeyspaceEvent(NOTIFY_STRING,"pfadd",c->argv[1],c->db->id);
        server.dirty++;
        HLL_INVALIDATE_CACHE(hdr);
    }
    // 客户端交互部分，此处可以放着以后理解
    addReply(c, updated ? shared.cone : shared.czero);
}

上述代码包含了很多与客户端交互的部分，此处可以先不看，添加元素主要由hllAdd函数实现。

int hllAdd(robj *o, unsigned char *ele, size_t elesize) {
    struct hllhdr *hdr = o->ptr;
    switch(hdr->encoding) {
    case HLL_DENSE: return hllDenseAdd(hdr->registers,ele,elesize);  // 密集模式添加元素
    case HLL_SPARSE: return hllSparseAdd(o,ele,elesize); // 稀疏模式添加元素
    default: return -1; // 非法模式
    }
}

以hllDenseAdd为例，首先计算待添加元素的第一次出现“1”的位置count和该元素添加到第index个桶内，然后查看registers部分，第index个桶内此时存放的第一次出现“1”的最大的位数oldcount，比较oldcount和count，如果前者大，则不处理；如果后者大，更新oldcount为count。

// 密集模式添加元素
int hllDenseAdd(uint8_t *registers, unsigned char *ele, size_t elesize) {
    uint8_t oldcount, count;
    long index;
<span style="color:#75715e">// 计算该元素第一个1出现的位置

count = hllPatLen(ele,elesize,&index);
// 得到第index个桶内的count值
HLL_DENSE_GET_REGISTER(oldcount,registers,index);
if (count > oldcount) {
// 如果比现有的最大值还大，则添加该值到数据部分
HLL_DENSE_SET_REGISTER(registers,index,count);
return 1;
} else {
// 如果小于现有的最大值，则不做处理，因为不影响基数
return 0;
}
}
// 用于计算hash后的值中，第一个出现1的位置
int hllPatLen(unsigned char ele, size_t elesize, long regp) {
uint64_t hash, bit, index;
int count;
// 利用MurmurHash64A哈希函数来计算该元素的hash值
hash = MurmurHash64A(ele,elesize,0xadc83b19ULL);
// 计算应该放在哪个桶
index = hash & HLL_P_MASK;
// 为了保证循环能够终止
hash |= ((uint64_t)1<<63);
bit = HLL_REGISTERS;
// 存储第一个1出现的位置
count = 1;
// 计算count
while((hash & bit) == 0) {
count++;
bit <<= 1;
}
*regp = (int) index;
return count;
}

计算基数

Redis提供了下面的命令来计算数据集的基数。

PFCOUNT key [key ...]

如果只有一个key则计算其基数即可；如果存在多个键，则需要合并所有的键（求并集），然后计算其基数。

上述讲到了分桶统计来消除误差，hyperloglog在误差方面对上述只取最大值平均的方法做了很多优化，具体优化部分可以参考解读Cardinality Estimation算法（第四部分：HyperLogLog Counting及Adaptive Counting）。

合并hyperloglog键

Redis提供了下面的命令来合并多个hyperloglog键。（源码部分就省略了）

PFMERGE destkey sourcekey [sourcekey ...]

hyperloglog小结

一开始以为hyperloglog是Redis的日志部分的实现，后来才发现，跟日志半毛钱的关系都没有。对于密集存储和稀疏存储，能够大大节约内存，后续有时间还是要详细的理一理实现思路。关于基数统计，各位可以参考下面几篇博客。 + 解读Cardinality Estimation算法（第一部分：基本概念） + 解读Cardinality Estimation算法（第二部分：Linear Counting） + 解读Cardinality Estimation算法（第三部分：LogLog Counting）

Update 2016-12-9

** 为什么一个hyperloglog键的大小固定为12KB？**

Redis的hyperloglog结构中，card数组为64位bit，理论上可以存储近264264个值。以密集表示模式为例：

Redis规定分桶个数为16384个，每一个桶内的数据采用6bit大小来存放

注意：Redis此处存放的不是该元素，而是存放第一次出现“1”的位置的值，6bit可以表示0~64位，即可以支持264264个基数。

registers部分占用内存为（16384*6+7）/8 = 12288个字节，另外加上HLL结构的头占用了16个字节，加起来一共12304个字节，也就是说一个hyperloglog键占用了12KB左右的大小，最多可以计算264264个不同元素的基数。

• Redis
• SourceCode