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.数据特点

  1. 短key短value:其中superid为21位数字:比如1605242015141689522;imei为小写md5:比如2d131005dc0f37d362a5d97094103633;idfa为大写带”-”md5:比如:51DFFC83-9541-4411-FA4F-356927E39D04;
  2. 媒体自身的cookie长短不一;
  3. 需要为全量数据提供服务,supperid是百亿级、媒体映射是千亿级、移动id是几十亿级;
  4. 每天有十亿级别的mapping关系产生;
  5. 对于较大时间窗口内可以预判热数据(有一些存留的稳定cookie);
  6. 对于当前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策略削减了桶消耗,实际上对于每个桶已经经历了很多的实验发生。

总结:信息摘要在这种场景下不仅能节约key存储,对齐了内存,还能让Key按照多项式分布均匀的散列在更少量的key下面从而减少膨胀,另外无需在给key设置expire,也很大程度上节约了空间。

这也印证了时间换空间的基本理论,合理利用CPU租值也是需要考虑的。

Image placeholder
快乐男孩666
未设置
  89人点赞

没有讨论,发表一下自己的看法吧

推荐文章
10分钟搞懂:亿级用户的分布式数据存储解决方案!

来源:IT进阶思维原创,转载请注明原出处内容提供:李智慧,前阿里巴巴技术专家,《大型网站技术架构》作者6月6日晚,林志玲与Akira公布婚讯、徐蔡坤祝福高考同学超常发挥,粉丝们百万的转发和点赞造成微博

深入浅出百亿请求高可用Redis(codis)分布式集群揭秘

摘要:作为noSql中的kv数据库的王者,redis以其高性能,低时延,丰富的数据结构备受开发者青睐,但是由于redis在水平伸缩性上受限,如何做到能够水平扩容,同时对业务无侵入性是很多使用redis

MySQL 亿级数据数据库优化方案测试-银行交易流水记录的查询

作者:逸宸a链接:https://www.jianshu.com/p/cbdef47fb837对MySQL的性能和亿级数据的处理方法思考,以及分库分表到底该如何做,在什么场景比较合适?比如银行交易流水

百亿流量微服务网关的设计与实现

本文从百亿流量交易系统微服务网关(APIGateway)的现状和面临的问题出发,阐述微服务架构与API网关的关系,理顺流量网关与业务网关的脉络,分享API网关知识与经验。API网关概述“计算机科学领域

ElasticSearch 亿级数据检索案例实战

一、前言数据平台已迭代三个版本,刚开始遇到很多常见的难题,终于有时间整理一些已完善的文档了,在此分享一下。希望能帮助大家少走些弯路,在此篇幅中偏重于ES的优化。关于HBase,Hadoop的设计优化估

亿级海量数据的实时读写和复杂查询实践

摘要:本文分享了每日亿级增量数据的实时读写、复杂查询场景实践介绍,涉及MySQL分表分库策略、数据异构、TiDB使用和优化、微服务架构等内容。  作者:黄哲铿  黄哲铿,中通商业CTO,前1号店技术总

Elasticsearch 亿级数据检索性能优化案例实战!

一、前言数据平台已迭代三个版本,从头开始遇到很多常见的难题,终于有片段时间整理一些已完善的文档,在此分享以供所需朋友实现参考,少走些弯路,在此篇幅中偏重于ES的优化,关于HBase,Hadoop的设计

干货 | 每天十亿级数据更新,秒出查询结果,ClickHouse在携程酒店的应用

本文转自 |携程技术中心 作者 |蔡岳毅作者简介蔡岳毅,携程酒店大数据高级研发经理,负责酒店数据智能平台研发,大数据技术创新工作。喜欢探索研究大数据的开源技术框架。一、背景1)携程酒店每天有上千表,累

百分点万亿级大数据平台的建设实践

从互联网、移动互联网到物联网,数据量之巨大已突破想象边界。与此同时,实时数据分析的需求日益增长,那么,当数据量达到亿级、百亿级甚至万亿级规模,实时数据分析如何来做?尤其在ToB/G来说,大多数企业和政

万亿级消息背后: 小米消息队列的实践

目录业务背景架构与关键问题性能与资源优化平台化效率小米消息中间件的规划与愿景前文《消息队列价值思考》讲述了消息中间件在企业IT架构中的重要价值,本文将呈现这些价值在落地小米业务过程中的遇到的问题和实践

搞个大事情,阿里如何实现上亿级数据的精准计数?

背景关系型数据库在执行计数任务时,其执行效率会随着数据量级的增长而降低;当数据量达到亿级别时,计数任务的执行效率已经低到令人不忍直视。在闲鱼团队的关系系统中,我们采用了这样一种方式来实现亿级别数据的毫

腾讯万亿级 Elasticsearch 技术解密

作者: johngqjiang,腾讯TEG云架构平台部研发工程师Elasticsearch(ES)作为开源首选的分布式搜索分析引擎,通过一套系统轻松满足用户的日志实时分析、全文检索、结构化数据分析等多

引领存储新时代——新华三Primera关键业务智能存储

技术的变革,让我们步入数字智能时代。由数据、AI驱动的智能化产业转型正在如火如荼地进行中,金融、工业、医疗、娱乐……智能改变着一切。在IT对于企业已经如此重要的今天,智能也正改变着支撑企业业务运行的底

云原生存储和云存储有什么区别?

作者| 李鹏(壮怀)阿里云智能事业群高级技术专家导读:新的企业负载/智能工作负载容器化、迁云、存储方面遇到的性能、弹性、高可用、加密、隔离、可观测性以及生命周期等方面的问题,不但需要存储产品层次的改进

NAS与对象存储:谁是非结构化数据存储的最佳选择?

非结构化数据是增长最快的数据类型之一。随着企业日积月累地生成、收集和存储越来越多的数据,必然会带来一个问题:什么是存储非结构化数据的最佳方式?直白来说,非结构化数据就是不遵循传统数据库格式的数据,其结

基于内存和文件存储的 queue worker, 不用 Redis 适合单进程使用没有外部依赖

因为最近要做一个简单的并发任务系统,在github上面找了一圈并没有简单可依赖的库,所以自己写了一个。欢迎大家Review贡献代码。项目地址https://github.com/iflamed/mfw

MySQL Batched Key Access (BKA)原理和设置使用方法举例

MySQL5.6版本开始增加了提高表join性能的算法:BatchedKeyAccess(BKA)的新特性。BKA算法原理:将外层循环的行/结果集存入joinbuffer,内存循环的每一行数据与整个b

Onvif/RTSP海康大华网络安防摄像机网页无插件直播方案EasyNVR登陆用户名密码失效问题解决方案

背景分析随着互联网基础设施建设的发展,4G/5G/NB-IoT各种网络技术的大规模商用,视频随时随地可看、可控的诉求越来越多,互联网思维、架构和技术引入进传统监控行业里,成为新形势下全终端监控的基础需

Mac 跑代码报 Illegal key size 错误的解决方法

异常原因:如果密钥大于128,会抛出java.security.InvalidKeyException:Illegalkeysize异常.因为密钥长度是受限制的,java运行时环境读到的是受限的pol

如何通过 Tampermonkey 快速查找 JavaScript 加密入口

在很多情况下,我们可能想要在网页中自动执行某些代码,帮助我们完成一些操作。如自动抢票、自动刷单、自动爬虫等等,这些操作绝大部分都是借助JavaScript来实现的。那么问题来了?在浏览器里面怎样才能方

jquey怎么引用css样式

jquey怎么引用css样式jquery引用css只需要一行代码即可,通过传入一个标签,来创建link标签,传入type、href、以及rel给link标签添加属性,最后再调用appendTo方法,将

GoWeb教程_06.0. session 和数据存储

Web开发中一个很重要的议题就是如何做好用户的整个浏览过程的控制,因为HTTP协议是无状态的,所以用户的每一次请求都是无状态的,我们不知道在整个Web操作过程中哪些连接与该用户有关,我们应该如何来解决

GoWeb教程_06.3. session 存储

上一节我们介绍了Session管理器的实现原理,定义了存储session的接口,这小节我们将示例一个基于内存的session存储接口的实现,其他的存储方式,读者可以自行参考示例来实现,内存的实现请看下

GoWeb教程_09.5 存储密码

过去一段时间以来,许多的网站遭遇用户密码数据泄露事件,这其中包括顶级的互联网企业–Linkedin,国内诸如CSDN,该事件横扫整个国内互联网,随后又爆出多玩游戏800万用户资料被泄露,另有传言人人网

Go 中使用 memcache 存储对象

之于B/S端用http连接,像mysql,redis,memcache这种服务端之间的交流,通常直接采用TCP通信。而对于缓存的内存存储,过期时间是必备,进行必要的对象序列化编码也不可缺。本文用me