Redis 大数据量（百亿级）Key 存储需求如何解决？试试这个思路

2021-05-12 16:20:32

近我在思考实时数仓问题的时候，想到了巨量的 Redis 的存储的问题，然后翻阅到这篇文章，与各位分享

一、需求背景

该应用场景为 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；

四、存在的技术挑战

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

五、解决方案

5.1 淘汰策略

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

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

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

5.2 减少膨胀

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=;i<r.length;i++) {
    if(r[i]<) r[i] &= 127;    }    return r;}

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

5.3 减少碎片

碎片主要原因在于内存无法对齐、过期删除后，内存无法重新分配。通过上文描述的方式，我们可以将人口标签和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更节约。

来源：juejin.cn/post/6956147115286822948