海量数据计数的一个方法分析

发表于

intro1：如何存储以及计算一份资源的累积UV/PV？
intro2: 使用 hyperloglog 究竟有多节省内存呢？

现象和问题：

接一需求，一顿抽丝剥茧去干扰取核心后才弄清楚原始的需求：即时的计算资源累积UV，即对uid去重后进行计数，超阈值则上报。

方案

自然想到了Redis的 Hyperloglog[以下简称HLL] 数据结构计数。

Redis的HyperLogLog 每Key只需要12kB就可以统计大到 2^64个的用户，而保持0.81%的误差率。



文末备注几个关于 HLL 的链接，这里简单白话一下HLL，方便阅读本文:
HLL是一种类似bitmap的计数原理，但由于采用了多次高离散的hash函数，使得它比 bitmap 消耗更少的内存，据说Google也在用它计数。
借助于精妙的假设采用时间换空间的思想，关键是这个时间还不大。

对于去重计数，redis提供的就有Set/Bitmap数据结构，这也是最开始考虑几次后对使用HLL有些疑虑原因，我们的资源总量预估十亿，如果仅按三个月过期来算也有数千万：

  1. 如果HLL每个Key计数也是耗费KB甚至最大12KB，那么redis内存可能就要上百GB到10个T这么多
  2. 长尾效应：显然这些资源，可能至少百分80不会过千或过万，这个时候是不是用 保存uid的set结构比HLL更节省内存呢

其实还想过性能足够，支持文件存储HBase、Cassandra、Pegasus等，但都未有提供HLL的数据结构或者操作接口，那么他们是否支持近似，比如自己写一个BloomFilter+计数或者HLL的value值操作？
估算一下Guava BloomFilter 实现对于500万千分之一的误差耗费空间是 80K bit，不比HLL小，而且众所周知，即便实现，也要解决一个大多数分布式存储更新同一个Key面临的问题： 即非同一线程/进程并发处理同一个Key时的原子性问题。而 HBase、Pegasus都有基于CAS原理的 check_and_put/check_and_mutate 类似操作，Cassandra也不同程度支持原子性更新，但实现起来对于耗时/快照空间可能要慎重，而且更新失败之后再获取再重试，即便几率很小也会导致实现的代码本身难看，而 Redis HLL是add操作即单进程封装了所有逻辑，可谓天生原子性，且数据只需存储一份，更且支持 merge另一个 HLL，而Guava的BloomFilter要直到 15.0 版本才支持 merge 另一个BloomFilter，而且另一个问题是 “As of Guava 23.0, this class is thread-safe and lock-free.”，23.0版本后 Guava 的BF才是线程安全的( 意味着，以前很多介绍Guava Bloomfilter的文章，如果没提到最低支持版本就基本上不严谨/不实用的)。
也不会选择Spark，因为这里的问题本身在于持久化存储，而不是计算资源本身。
当然了，单Key的热点问题上述几个选型都是存在的。

所以，用 Redis+HLL，但是我确实想知道是否存在上文的长尾效应问题，也就是，一份资源累积独立访问用户数达到多少时用HLL比Set “划算”？

动手试一下

redis提供了 info memory 和 debug object key 可供查看(精确或近似的对象级别的)内存消耗。

1
2
3
4
5
6
7
8
9
10
11
-- pfadd_sadd.lua
local time = redis.call('time');
local now_micros = tonumber(time[1])*1000000 + tonumber(time[2]);
math.randomseed(now_micros);
local num = math.random(100000000, 10000000000);
for i=10000,1,-1 do
    -- redis.call('sadd',"myset", math.random(1000000000, 10000000000));
    -- redis.call('PFADD',"mypfa", math.random(1000000000, 10000000000));
    redis.call(KEYS[1],ARGV[1], math.random(1000000000, 10000000000));
end
return 1

这个lua脚本就是可以实现 n次随机uid去 sadd myset xxx 和 pfadd myHLL xxx 的操作，简单来说就是通过 lua 随机函数生成10000个随机uid，并sadd或者pfadd到redis里。
需要解释下为什么lua随机数这里代码有点”不走寻常路”

  1. 如果直接用math.random() 初始化，可能会导致每次生成的随机uid 序列是一样的，即多次跑脚本后set数量不增。
  2. 为什么不用 math.randomseed(os.time()) 生成随机数更好看？试过，不过redis lua 编译器禁止调用系统相关的os函数，是的，安全考虑。

运行：

1
2
3
4
5
➜  ztemp redis-cli --eval pfadd_sadd.lua pfadd , "myHLL"
(integer) 1
➜  ztemp redis-cli --eval pfadd_sadd.lua sadd , "myset2"
(integer) 1
➜  ztemp

内存查看:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
127.0.0.1:6379> info memory
# Memory
used_memory:7594672
used_memory_human:7.24M
used_memory_rss:6213632
used_memory_rss_human:5.93M
...
127.0.0.1:6379> debug object myHLL
Value at:0x7fb99e614160 refcount:1 encoding:raw serializedlength:10578 lru:14012310 lru_seconds_idle:15
127.0.0.1:6379> info memory
# Memory
used_memory:7608176
used_memory_human:7.26M
used_memory_rss:6250496
used_memory_rss_human:5.96M
...
127.0.0.1:6379> debug object myset2
Value at:0x7fb9a08e3870 refcount:1 encoding:hashtable serializedlength:499960 lru:14012406 lru_seconds_idle:12
127.0.0.1:6379> info memory
# Memory
used_memory:13981680
used_memory_human:13.33M
used_memory_rss:8421376
used_memory_rss_human:8.03M
...
127.0.0.1:6379> pfcount myHLL
(integer) 99287
127.0.0.1:6379> scard myset2
(integer) 99991

上面是测试 十万次随机(注意不是10万条)uid数据量差，还是蛮大的，分别是在 10KB和 6387KB。
ps. 这里也可以看到 lua 伪随机数效果还是不错的。
对于一千条测试下来 Set耗费是HLL的五倍。
还是蛮意外的。实际上 redis 作者 Salvatore Sanfilippo(Antirez)已经在代码注释里写了些参考数据，值得一看：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/*
 ...
 * The following table shows average cardinality vs bytes used, 100
 * samples per cardinality (when the set was not representable because
 * of registers with too big value, the dense representation size was used
 * as a sample).
 *
 * 100 267
 * 200 485
 * 300 678
 * 400 859
 * 500 1033
 * 600 1205
 * 700 1375
 * 800 1544
 * 900 1713
 * 1000 1882
 * 2000 3480
 * 3000 4879
 * 4000 6089
 * 5000 7138
 * 6000 8042
 * 7000 8823
 * 8000 9500
 * 9000 10088
 * 10000 10591
 *
 * The dense representation uses 12288 bytes, so there is a big win up to
 * a cardinality of ~2000-3000. For bigger cardinalities the constant times
 * involved in updating the sparse representation is not justified by the
 * memory savings. The exact maximum length of the sparse representation
 * when this implementation switches to the dense representation is
 * configured via the define server.hll_sparse_max_bytes.
 */

也就是说其实用户UV达到300就已经比set划算了。

其它

  1. Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm
  2. 神奇的HyperLogLog算法
  3. 走近源码：神奇的HyperLogLog
  4. Memory Optimization