CH08-百亿量级

需求背景

该应用场景为 DMP 缓存存储需求,DMP 需要管理非常多的第三方 id 数据,其中包括各媒体 cookie 与自身 cookie(以下统称 supperid)的 mapping 关系,还包括了 supperid 的人口标签、移动端id(主要是idfa和imei)的人口标签,以及一些黑名单id、ip等数据。

在 hdfs 的帮助下离线存储千亿记录并不困难,然而 DMP 还需要提供毫秒级的实时查询。由于 cookie 这种 id 本身具有不稳定性,所以很多的真实用户的浏览行为会导致大量的新 cookie 生成,只有及时同步 mapping 的数据才能命中 DMP 的人口标签,无法通过预热来获取较高的命中,这就跟缓存存储带来了极大的挑战。

经过实际测试,对于上述数据,常规存储超过五十亿的kv记录就需要1T多的内存,如果需要做高可用多副本那带来的消耗是巨大的,另外kv的长短不齐也会带来很多内存碎片,这就需要超大规模的存储方案来解决上述问题。

缓存内容

人⼝标签主要是 cookie、imei、idfa 以及其对应的 gender(性别)、age(年龄段)、geo(地域)等;mapping 关系主要是媒体 cookie 对 supperid 的映射。以下是数据存储⽰示例:

1、PC端的ID:

媒体编号-媒体 cookie=>supperid

  • supperid => { age=>年龄段编码,gender=>性别编码,geo=>地理位置编码 }

2、Device 端的 ID:

  • imei or idfa => { age=>年龄段编码,gender=>性别编码,geo=>地理位置编码 }

显然 PC 数据需要存储两种 key=>value 还有 key=>hashmap,⽽ Device 数据需要存储一种 key=>hashmap 即可。

数据特点

短 key 短 value:

其中superid为21位数字:比如1605242015141689522;
imei为小写md5:比如2d131005dc0f37d362a5d97094103633;
idfa为大写带”-”md5:比如:51DFFC83-9541-4411-FA4F-356927E39D04;
  • 媒体自身的 cookie 长短不一;
  • 需要为全量数据提供服务,supperid 是百亿级、媒体映射是千亿级、移动 id 是几十亿级;
  • 每天有十亿级别的 mapping 关系产生;
  • 对于较大时间窗口内可以预判热数据(有一些存留的稳定 cookie);
  • 对于当前 mapping 数据无法预判热数据,有很多是新生成的 cookie;

技术挑战

  1. 长短不一容易造成内存碎片;
  2. 由于指针大量存在,内存膨胀率比较高,一般在7倍,纯内存存储通病;
  3. 虽然可以通过cookie的行为预判其热度,但每天新生成的id依然很多(百分比比较敏感,暂不透露);
  4. 由于服务要求在公网环境(国内公网延迟60ms以下)下100ms以内,所以原则上当天新更新的 mapping 和人口标签需要全部 in memory,而不会让请求落到后端的冷数据;
  5. 业务方面,所有数据原则上至少保留35天甚至更久;
  6. 内存至今也比较昂贵,百亿级Key乃至千亿级存储方案势在必行!

解决方案

淘汰策略

存储吃紧的一个重要原因在于每天会有很多新数据入库,所以及时清理数据尤为重要。主要方法就是发现和保留热数据淘汰冷数据。

网民的量级远远达不到几十亿的规模,id 有一定的生命周期,会不断的变化。所以很大程度上我们存储的id实际上是无效的。而查询其实前端的逻辑就是广告曝光,跟人的行为有关,所以一个 id 在某个时间窗口的(可能是一个campaign,半个月、几个月)访问行为上会有一定的重复性。

数据初始化之前,我们先利用 HBase 将日志的id聚合去重,划定TTL的范围,一般是35天,这样可以砍掉近35天未出现的id。另外在 Redis 中设置过期时间是35天,当有访问并命中时,对 key 进行续命,延长过期时间,未在 35 天出现的自然淘汰。这样可以针对稳定 cookie 或 id 有效,实际证明,续命的方法对 idfa 和 imei 比较实用,长期积累可达到非常理想的命中。

减少膨胀

Hash 表空间大小和 Key 的个数决定了冲突率(或者用负载因子衡量),再合理的范围内,key 越多自然hash表空间越大,消耗的内存自然也会很大。再加上大量指针本身是长整型,所以内存存储的膨胀十分可观。先来谈谈如何把 key 的个数减少。

大家先来了解一种存储结构。我们期望将 key1=>value1 存储在 redis 中,那么可以按照如下过程去存储。先用固定长度的随机散列md5(key)值作为 redis 的 key,我们称之为 BucketId,而将key1=>value1存储在hashmap结构中,这样在查询的时候就可以让client按照上面的过程计算出散列,从而查询到 value1。

过程变化简单描述为:get(key1) -> hget(md5(key1), key1) 从而得到 value1。

如果我们通过预先计算,让很多key可以在BucketId空间里碰撞,那么可以认为一个BucketId下面挂了多个key。比如平均每个BucketId下面挂10个key,那么理论上我们将会减少超过90%的redis key的个数。

具体实现起来有一些麻烦,而且用这个方法之前你要想好容量规模。我们通常使用的 md5 是 32 位的 hexString(16进制字符),它的空间是 128bit,这个量级太大了,我们需要存储的是百亿级,大约是 33 bit(2的33次方),所以我们需要有一种机制计算出合适位数的散列,而且为了节约内存,我们需要利用全部字符类型(ASCII码在0~127之间)来填充,而不用 HexString,这样 Key 的长度可以缩短到一半。

下面是具体的实现方式:

public static byte [] getBucketId(byte [] key, Integer bit) {
    MessageDigest mdInst = MessageDigest.getInstance("MD5");
    mdInst.update(key);
    byte [] md = mdInst.digest();
    byte [] r = new byte[(bit-1)/7 + 1];// 因为一个字节中只有7位能够表示成单字符,ascii码是7位
    int a = (int) Math.pow(2, bit%7)-2;
    md[r.length-1] = (byte) (md[r.length-1] & a);
    System.arraycopy(md, 0, r, 0, r.length);
    for(int i=0;i<r.length;i++) {
    	if(r[i]<0) r[i] &= 127;    
    }    
    return r;
}

参数 bit 决定了最终 BucketId 空间的大小,空间大小集合是2的整数幂次的离散值。这里解释一下为何一个字节中只有7位可用,是因为 redis 存储 key 时需要是 ASCII(0~127),而不是 byte array。如果规划百亿级存储,计划每个桶分担10个kv,那么我们只需 2^30=1073741824 的桶个数即可,也就是最终 key 的个数。

减少碎片

碎片主要原因在于内存无法对齐、过期删除后,内存无法重新分配。通过上文描述的方式,我们可以将人口标签和mapping数据按照上面的方式去存储,这样的好处就是redis key是等长的。另外对于hashmap中的key我们也做了相关优化,截取cookie或者deviceid的后六位作为key,这样也可以保证内存对齐,理论上会有冲突的可能性,但在同一个桶内后缀相同的概率极低(试想id几乎是随机的字符串,随意10个由较长字符组成的id后缀相同的概率*桶样本数=发生冲突的期望值«0.05,也就是说出现一个冲突样本则是极小概率事件,而且这个概率可以通过调整后缀保留长度控制期望值)。而 value 只存储 age、gender、geo 的编码,用三个字节去存储。

另外提一下,减少碎片还有个很 low 但是有效的方法,将 slave 重启,然后强制的 failover 切换主从,这样相当于给master整理的内存的碎片。

推荐 Google-tcmalloc, facebook-jemalloc 内存分配,可以在 value 不大时减少内存碎片和内存消耗。有人测过大 value 情况下反而libc更节约。