生日悖论是啥?我用它省了上百G的内存

本文涉及的产品
云数据库 Redis 版,社区版 2GB
推荐场景:
搭建游戏排行榜
简介: <0.0001,p就会小于万分之一。我可以从历史数中统计出n的大小,然后计算出x,再留一定的buff,然后根据n的大小重新设计了redis的key。(因为涉及公司数据,这里不公布中间计算过程)

生日悖论: 是指在不少于 23 个人中至少有两人生日相同的概率大于 50%。例如在一个 30 人的小学班级中,存在两人生日相同的概率为 70%。对于 60 人的大班,这种概率要大于 99%。从引起逻辑矛盾的角度来说,生日悖论并不是一种 “悖论”。但这个数学事实十分反直觉,故称之为一个悖论。


生日悖论是有个有趣的概念,但这和我省上百G的内存有什么关系?


背景

首先介绍下背景,工作中我负责了一个广告数据系统,其中一个功能就是对同一次请求的广告曝光去重,因为我们只需要知道这次请求这个广告的一次曝光就行了,那些同一次请求产生的重复曝光记录下来没有意义,而且还耗会增加我们的存储成本。所以这里就需要有个逻辑去判断每条新到的曝光是否只之前已经记录过的,旧的方案是在redis中存储请求唯一标识(uuid)和广告ID(adid),每次数据过来我们就看redis里有没有uuid+adid这个key,有就过滤掉,没有就不过滤并在redis记录下来已出现。


问题就来了,redis记录的这份数很大(两天数据超过400G),而且随着我们业务的增长,我们的Redis集群快盛不下了…… 当然花钱加机器是最简单的方式,毕竟能用钱解决的问题都不是问题。而优秀的我,为了替公司省钱,走了优化的路。


如何优化?

首先可以肯定的是数据条数不会少,因为业务量就在那里,所以减少数据量的这条路肯定行不通。那是否可以减少每条数据的长度呢?

我们再来看下redis存储的设计,如下图:

aa42067200a599e66cbc869df2e7e7cd_watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpbmRvbw==,size_16,color_FFFFFF,t_70#pic_center.png

这样下来一条记录总共用了45个字节,这个长度能不能缩短? 当然能,我们可以截取部分UUID,但这样又带来一个新的问题,截取UUID会增加重复的概率,所以首先搞清楚怎么截取,截多少?


这里我们用的是随机UUID,这个版本中有效二进制位是122个,所以总共有2 122 2^{122}2

122

个有效的UUID。 因为是随机产生的所以肯定有重复的概率,UUID重复的概率有多少? 要算这个重复概率,光有2 122 2^{122}2

122

这个总数还不行,还得知道你拥有的UUID个数。 我把这个问题具体下,求:在2 36 2^{36}2

36

个UUID中有重复的概率是多少?

p ( n ) ≈ 1 − e − n 2 2 x p(n) \approx 1-e^{-\frac{n^{2}}{2 x}}

p(n)≈1−e

2x

n

2


这不就是生日悖论的数据放大版吗? 当然这个概率可以根据上面公式计算,其中x是UUID的总数2 122 2^{122}2

122

,n是2 36 2^{36}2

36

,引用百度百科的数据,概率为4 ∗ 1 0 − 16 4 *10^{-16}4∗10

−16

 这比你出门被陨石撞的概率还小很多。


n 几率

2^36 4 x 10^-16

2^41 4 x 10^-13

2^46 4 x 10^-10

另外,从上面的公式也可以看出,在n固定的时候,随着有效二进制位的减少,概率p就会增加。 回到我们广告去重的场景下,每天最大请求数n是基本固定的,而且我们也可以忍受一个较小的概率p(小于万分之一),然后就可以反推出这个x有多大。


其实只要n 2 2 x < 0.0001 \frac{n^{2}}{2 x} < 0.0001

2x

n

2

<0.0001,p就会小于万分之一。我可以从历史数中统计出n的大小,然后计算出x,再留一定的buff,然后根据n的大小重新设计了redis的key。(因为涉及公司数据,这里不公布中间计算过程)


新设计

最终有效位我选取了40个有效二进制位(10个16进制位),但我并没有直接截取UUID的前10位,因为UUID的前几位和时间有关,随机性并不强。我选择将整个UUID重新md5散列,然后截取md5的前10位,然后拼接adId形成最终的key,如下图:

4e92ef77cbaf702b030c370c1bce2d31_watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpbmRvbw==,size_16,color_FFFFFF,t_70#pic_center.png

明显看出,key的长度缩小了一半,总体上能节省至少50%的存储空间。备注:但其实我们redis的具体存储实现和上文描述略有差异,为了不喧宾夺主上文特意对实际实现做了简化描述,所以最终实际没有省一半以上的内存,只省了35%左右。


如何进一步优化?

实际优化就到这了,但其实还是不够极致,其实adId中也包含大量的冗余信息也可以截取,其实我们可以承受更高的重复率,其实我们可以把redis数据存储时间设的更短一些……


上面几种方法都可以进一步优化,但存储空间不会有量级级别的减少,而下面一种方式,可以将存储空间减小99%以上。


布隆过滤器(BloomFilter)

关于布隆过滤器的原理,可以参考我之前写的一篇文章布隆过滤器(BloomFilter)原理 实现和性能测试。 布隆过滤器完全就是为了去重场景设计的,保守估计我们广告去重的场景切到布隆过滤器,至少节省90%的内存。


那为什么我没有用布隆过滤器,其实还是因为实现复杂。redis在4.0后支持模块,其中有人就开发设计了布隆过滤器的模块RedisBloom,但无奈我们用的redis 还是3.x版本 !我也考虑过应用端基于redis去实现布隆过滤器,但我们应用端是个集群,需要解决一些分布式数据一致性的问题,作罢。


结语

其实我们redis的具体存储实现和上文描述略有差异,为了不喧宾夺主上文特意对实际实现做了简化描述,所以最终实际没有省一半以上的内存,只省了35%左右。


最终400G+优化后能减少100多G的内存,其实也就是一台服务器,即便放到未来也就是少扩容几台服务器。对公司而言就是每个月节省几千的成本,我司这种大厂其实是不会在乎这点钱的。不过即便这几千的成本最终不会转化成我的工资或者奖金,但像这种优化该做还是得做。如果每个人都本着 用最低的成本做同样事 的原则去做好每一件事,就我司这体量,一个月上千万的成本还是能省下来的。


参考资料

百度百科 生日悖论

百度百科 UUID

布隆过滤器(BloomFilter)原理 实现和性能测试

RedisBloom 基于redis的布隆过滤器实现

相关实践学习
基于Redis实现在线游戏积分排行榜
本场景将介绍如何基于Redis数据库实现在线游戏中的游戏玩家积分排行榜功能。
云数据库 Redis 版使用教程
云数据库Redis版是兼容Redis协议标准的、提供持久化的内存数据库服务,基于高可靠双机热备架构及可无缝扩展的集群架构,满足高读写性能场景及容量需弹性变配的业务需求。 产品详情:https://www.aliyun.com/product/kvstore &nbsp; &nbsp; ------------------------------------------------------------------------- 阿里云数据库体验:数据库上云实战 开发者云会免费提供一台带自建MySQL的源数据库&nbsp;ECS 实例和一台目标数据库&nbsp;RDS实例。跟着指引,您可以一步步实现将ECS自建数据库迁移到目标数据库RDS。 点击下方链接,领取免费ECS&amp;RDS资源,30分钟完成数据库上云实战!https://developer.aliyun.com/adc/scenario/51eefbd1894e42f6bb9acacadd3f9121?spm=a2c6h.13788135.J_3257954370.9.4ba85f24utseFl
目录
相关文章
|
6天前
|
存储
浮点数在内存中的存储
浮点数在内存中的存储
26 0
|
6天前
|
存储
数据在内存中的存储之整数存储
数据在内存中的存储之整数存储
21 0
|
6天前
|
存储 C语言
C语言第二十九弹---浮点数在内存中的存储
C语言第二十九弹---浮点数在内存中的存储
|
3天前
|
存储 算法 关系型数据库
实时计算 Flink版产品使用合集之在Flink Stream API中,可以在任务启动时初始化一些静态的参数并将其存储在内存中吗
实时计算Flink版作为一种强大的流处理和批处理统一的计算框架,广泛应用于各种需要实时数据处理和分析的场景。实时计算Flink版通常结合SQL接口、DataStream API、以及与上下游数据源和存储系统的丰富连接器,提供了一套全面的解决方案,以应对各种实时计算需求。其低延迟、高吞吐、容错性强的特点,使其成为众多企业和组织实时数据处理首选的技术平台。以下是实时计算Flink版的一些典型使用合集。
17 4
|
5天前
|
存储 小程序 编译器
数据在内存中的存储(探索内存的秘密)
数据在内存中的存储(探索内存的秘密)
11 0
|
6天前
|
存储 监控 NoSQL
Redis处理大量数据主要依赖于其内存存储结构、高效的数据结构和算法,以及一系列的优化策略
【5月更文挑战第15天】Redis处理大量数据依赖内存存储、高效数据结构和优化策略。选择合适的数据结构、利用批量操作减少网络开销、控制批量大小、使用Redis Cluster进行分布式存储、优化内存使用及监控调优是关键。通过这些方法,Redis能有效处理大量数据并保持高性能。
26 0
|
1天前
|
存储 弹性计算 监控
【阿里云弹性计算】深入阿里云ECS配置选择:CPU、内存与存储的最优搭配策略
【5月更文挑战第20天】阿里云ECS提供多种实例类型满足不同需求,如通用型、计算型、内存型等。选择CPU时,通用应用可选1-2核,计算密集型应用推荐4核以上。内存选择要考虑应用类型,内存密集型至少4GB起。存储方面,系统盘和数据盘容量依据应用和数据量决定,高性能应用可选SSD或高效云盘。结合业务特点和预算制定配置方案,并通过监控应用性能适时调整,确保资源最优利用。示例代码展示了使用阿里云CLI创建ECS实例的过程。
31 5
|
6天前
|
存储 编译器 程序员
C语言:数据在内存中的存储
C语言:数据在内存中的存储
15 2
|
6天前
|
存储
整数和浮点数在内存中存储
整数的2进制表⽰⽅法有三种,即原码、反码和补码。
18 0
|
6天前
|
存储 算法 编译器
整形和浮点型是如何在内存中的存储
整形和浮点型是如何在内存中的存储