共计 4813 个字符，预计需要花费 13 分钟才能阅读完成。
本篇内容主要讲解“Redis 百亿级 Key 存储方案怎么实现”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让丸趣 TV 小编来带大家学习“Redis 百亿级 Key 存储方案怎么实现”吧!
1. 需求背景
该应用场景为 DMP 缓存存储需求，DMP 需要管理非常多的第三方 id 数据，其中包括各媒体 cookie 与自身 cookie（以下统称 supperid）的 mapping 关系，还包括了 supperid 的人口标签、移动端 id（主要是 idfa 和 imei）的人口标签，以及一些黑名单 id、ip 等数据。
在 hdfs 的帮助下离线存储千亿记录并不困难，然而 DMP 还需要提供毫秒级的实时查询。由于 cookie 这种 id 本身具有不稳定性，所以很多的真实用户的浏览行为会导致大量的新 cookie 生成，只有及时同步 mapping 的数据才能命中 DMP 的人口标签，无法通过预热来获取较高的命中，这就跟缓存存储带来了极大的挑战。
经过实际测试，对于上述数据，常规存储超过五十亿的 kv 记录就需要 1T 多的内存，如果需要做高可用多副本那带来的消耗是巨大的，另外 kv 的长短不齐也会带来很多内存碎片，这就需要超大规模的存储方案来解决上述问题。
2. 存储何种数据
人⼝标签主要是 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 即可。
3. 数据特点
短 key 短 value：其中 superid 为 21 位数字：比如 1605242015141689522；imei 为小写 md5：比如 2d131005dc0f37d362a5d97094103633；idfa 为大写带”-”md5：比如：51DFFC83-9541-4411-FA4F-356927E39D04；
媒体自身的 cookie 长短不一；
需要为全量数据提供服务，supperid 是百亿级、媒体映射是千亿级、移动 id 是几十亿级；
每天有十亿级别的 mapping 关系产生；
对于较大时间窗口内可以预判热数据（有一些存留的稳定 cookie）；
对于当前 mapping 数据无法预判热数据，有很多是新生成的 cookie；
4. 存在的技术挑战
1）长短不一容易造成内存碎片；
2）由于指针大量存在，内存膨胀率比较高，一般在 7 倍，纯内存存储通病；
3）虽然可以通过 cookie 的行为预判其热度，但每天新生成的 id 依然很多（百分比比较敏感，暂不透露）；
4）由于服务要求在公网环境（国内公网延迟 60ms 以下）下 100ms 以内，所以原则上当天新更新的 mapping 和人口标签需要全部 in memory，而不会让请求落到后端的冷数据；
5）业务方面，所有数据原则上至少保留 35 天甚至更久；
6）内存至今也比较昂贵，百亿级 Key 乃至千亿级存储方案势在必行！
5. 解决方案
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，这个量级太大了，我们需要存储的是百亿级，大约是 33bit，所以我们需要有一种机制计算出合适位数的散列，而且为了节约内存，我们需要利用全部字符类型（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 位能够表示成单字符
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 的个数。
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 更节约。
6. md5 散列桶的方法需要注意的问题
1）kv 存储的量级必须事先规划好，浮动的范围大概在桶个数的十到十五倍，比如我就想存储百亿左右的 kv，那么最好选择 30bit~31bit 作为桶的个数。也就是说业务增长在一个合理的范围（10~15 倍的增长）是没问题的，如果业务太多倍数的增长，会导致 hashset 增长过快导致查询时间增加，甚至触发 zip-list 阈值，导致内存急剧上升。
2）适合短小 value，如果 value 太大或字段太多并不适合，因为这种方式必须要求把 value 一次性取出，比如人口标签是非常小的编码，甚至只需要 3、4 个 bit（位）就能装下。3）典型的时间换空间的做法，由于我们的业务场景并不是要求在极高的 qps 之下，一般每天亿到十亿级别的量，所以合理利用 CPU 租值，也是十分经济的。
4）由于使用了信息摘要降低了 key 的大小以及约定长度，所以无法从 redis 里面 random 出 key。如果需要导出，必须在冷数据中导出。
5）expire 需要自己实现，目前的算法很简单，由于只有在写操作时才会增加消耗，所以在写操作时按照一定的比例抽样，用 HLEN 命中判断是否超过 15 个 entry，超过才将过期的 key 删除，TTL 的时间戳存储在 value 的前 32bit 中。
6）桶的消耗统计是需要做的。需要定期清理过期的 key，保证 redis 的查询不会变慢。
7. 测试结果
人口标签和 mapping 的数据 100 亿条记录。
优化前用 2.3T，碎片率在 2 左右；优化后 500g，而单个桶的平均消耗在 4 左右。碎片率在 1.02 左右。查询时这对于 cpu 的耗损微乎其微。
另外需要提一下的是，每个桶的消耗实际上并不是均匀的，而是符合多项式分布的。
上面的公式可以计算桶消耗的概率分布。公式是唬人用的，只是为了提醒大家不要想当然的认为桶消耗是完全均匀的，有可能有的桶会有上百个 key。但事实并不没有那么夸张。试想一下投硬币，结果只有两种正反面。相当于只有两个桶，如果你投上无限多次，每一次相当于一次伯努利实验，那么两个桶必然会十分的均匀。概率分布就像上帝施的魔咒一样，当你面对大量的桶进行很多的广义的伯努利实验。桶的消耗分布就会趋于一种稳定的值。接下来我们就了解一下桶消耗分布具体什么情况：
通过采样统计
31bit（20 多亿）的桶，平均 4.18 消耗
100 亿节约了 1.8T 内存。相当于节约了原先的 78% 内存，而且桶消耗指标远没有达到预计的底线值 15。
对于未出现的桶也是存在一定量的，如果过多会导致规划不准确，其实数量是符合二项分布的，对于 2^30 桶存储 2^32kv，不存在的桶大概有（百万级别，影响不大）：
Math.pow((1 – 1.0 / Math.pow(2, 30)), Math.pow(2, 32)) * Math.pow(2, 30);
对于桶消耗不均衡的问题不必太担心，随着时间的推移，写入时会对 HLEN 超过 15 的桶进行削减，根据多项式分布的原理，当实验次数多到一定程度时，桶的分布就会趋于均匀（硬币投掷无数次，那么正反面出现次数应该是一致的），只不过我们通过 expire 策略削减了桶消耗，实际上对于每个桶已经经历了很多的实验发生。
到此，相信大家对“Redis 百亿级 Key 存储方案怎么实现”有了更深的了解，不妨来实际操作一番吧！这里是丸趣 TV 网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！
