转载

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

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 可供查看(精确或近似的对象级别的)内存消耗。

-- 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函数,是的,安全考虑。

运行:

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

内存查看:

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)已经在代码注释里写了些参考数据,值得一看:

/*
 ...
 * 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
原文  http://thomaslau.xyz/2019/11/20/2019-11-20-on_redis_hyperloglog/
正文到此结束
Loading...