文档章节

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

o
 osc_i2zebhtf
发布于 07/05 11:55
字数 1800
阅读 15
收藏 0

行业解决方案、产品招募中!想赚钱就来传!>>>

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

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

背景

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

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

如何优化?

首先可以肯定的是数据条数不会少,因为业务量就在那里,所以减少数据量的这条路肯定行不通。那是否可以减少每条数据的长度呢?
我们再来看下redis存储的设计,如下图:
在这里插入图片描述
这样下来一条记录总共用了45个字节,这个长度能不能缩短? 当然能,我们可以截取部分UUID,但这样又带来一个新的问题,截取UUID会增加重复的概率,所以首先搞清楚怎么截取,截多少?


这里我们用的是随机UUID,这个版本中有效二进制位是122个,所以总共有$2^{122}$个有效的UUID。 因为是随机产生的所以肯定有重复的概率,UUID重复的概率有多少? 要算这个重复概率,光有$2^{122}$这个总数还不行,还得知道你拥有的UUID个数。 我把这个问题具体下,求:在$2^{36}$个UUID中有重复的概率是多少?
$$
p(n) \approx 1-e{-\frac{n{2}}{2 x}}
$$
这不就是生日悖论的数据放大版吗? 当然这个概率可以根据上面公式计算,其中x是UUID的总数$2{122}$,n是$2{36}$,引用百度百科的数据,概率为$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有多大。

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

新设计

最终有效位我选取了40个有效二进制位(10个16进制位),但我并没有直接截取UUID的前10位,因为UUID的前几位和时间有关,随机性并不强。我选择将整个UUID重新md5散列,然后截取md5的前10位,然后拼接adId形成最终的key,如下图:
在这里插入图片描述
明显看出,key的长度缩小了一半,总体上能节省至少50%的存储空间。备注:但其实我们redis的具体存储实现和上文描述略有差异,为了不喧宾夺主上文特意对实际实现做了简化描述,所以最终实际没有省一半以上的内存,只省了35%左右。

如何进一步优化?

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

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

布隆过滤器(BloomFilter)

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

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

结语

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

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

参考资料

  1. 百度百科 生日悖论
  2. 百度百科 UUID
  3. 布隆过滤器(BloomFilter)原理 实现和性能测试
  4. RedisBloom 基于redis的布隆过滤器实现

本文来自https://blog.csdn.net/xindoo

o
粉丝 0
博文 62
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
在多个浏览器上运行脚本--Queen

假设你想和朋友们玩这么个游戏:你写下某个数字,然后让朋友们猜你写的是什么数字。你的朋友们将不断的给你一些猜测的数字,直到猜中为止。 现在想象你的朋友都是使用的浏览器,这个游戏就相...

匿名
2013/01/24
4.4K
1
高效率的nio框架--nio java raptor

设计初衷是提供方便易用,且高效率的nio框架,一部分实现上参考了mina。还包括线程池,编解码,内存池等机制,以便于开发高性能tcp程序。 文档后续会慢慢的补上。 整体实现上尽量少的使用锁,...

齐楠
2012/12/12
3.3K
0
C多线程网络库--xs

基于C多线程网络库,欢迎大家使用,例子在代码example目录下,以后我会再增加一些例子。 文档暂时没有,有问题请邮件我:-) 获取代码:https://github.com/xueguoliang/xs xs致力于1)多线程网...

薛国良
2013/05/01
4.4K
0
使用IBPP在C++中操作FireBird/Interbase数据库

FireBird是一种小巧的关系型数据库,它有多种版本,包括服务器版(象MySQL),单机版(象Access)以及嵌入式(象SQLite)。而且不管是服务器版还是嵌入式版它都完整支持视图、触发器、存储过程等...

Waiting4you
2009/07/26
3.8K
2
想看看大家是怎么实现百鸡百钱问题的

RT,如果大家有兴趣,可以用任何语言把百鸡百钱的问题实现下。

只会百度的程序员
2013/04/15
858
8

没有更多内容

加载失败,请刷新页面

加载更多

Java中使用OpenSSL生成的RSA公私钥进行数据加解密

当前使用的是Linux系统,已经按装使用OpenSSL软件包, 一、使用OpenSSL来生成私钥和公钥 1、执行命令openssl version -a 验证机器上已经安装openssl openssl version -a 运行结果: 2、生成...

osc_1psr53ow
28分钟前
7
0
计算机毕业设计之springboot+vue.js点餐小程序 点餐系统

功能 后台: 1. 超级管理员(具有该系统所有权限)登录 查看系统所有管理员 操作:可新添加管理员并分配系统已有角色; 可对已有管理员进行信息编辑; 可对除超管外的其他管理员账号禁用/启用...

osc_x4ot1joy
29分钟前
10
0
MATLAB数学建模

链接:https://pan.baidu.com/s/1WA2ltwyMZuKeo7OC9XAIvw 提取码:tmy2 记录matlab参加建模比赛时所用的书籍,避免忘记 链接:https://pan.baidu.com/s/1WA2ltwyMZuKeo7OC9XAIvw 提取码:tmy...

osc_oa6qrgun
30分钟前
6
0
Python中可以使用静态类变量吗? - Are static class variables possible in Python?

问题: Is it possible to have static class variables or methods in Python? Python中是否可以有静态类变量或方法? What syntax is required to do this? 为此需要什么语法? 解决方案:...

技术盛宴
今天
17
0
如何在Android中以像素为单位获取屏幕尺寸 - How to get screen dimensions as pixels in Android

问题: I created some custom elements, and I want to programmatically place them to the upper right corner ( n pixels from the top edge and m pixels from the right edge). 我创建......

javail
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部