世界新消息丨布隆过滤器在短视频 feeds 系统中的妙用

深度 >
腾讯云
分享

大家平时刷抖音、视频号、快手时,几乎总能刷到最新的视频。那这里是怎么实现的呢?


(资料图)

上述场景,可以简单抽象为曝光去重,就是用户看过的 feeds1、feeds2、feeds3 ...... 等,如何保证在用户下次进入系统时不会再次出现呢?今天,我们就来探讨下几种实现方案吧。

方案一 :Set

这个方案简单粗暴,就是每个用户用一个集合,存储看过的所有 feedsid。每次推荐系统要出新的 feeds 时,去 set 中 check 一下是否存在,如果存在的话,就过滤掉这条 feeds。

一般来说,像是短视频推荐的场景下,对 feeds 的实时性要求相对较高,一般会使用 Redis 作为曝光打击的载体。

不了解 Redis Set 的同学可以参考下:https://redis.io/commands/set/,简而言之就是一个字典。

这种方案的问题是,在海量用户的场景下,1是成本会很高(像 Redis 是纯内存数据库);2是随着 feeds 数量越来越多,set 查询会随之变慢(像短视频的场景下,1晚上刷个上百条还是不成问题的)。

我们来简单试算一下,假设国民级 App 的日活跃用户在 3kw,每人每天平均刷 200 条视频 feeds,每条 feeds 的 id 长度为 32B。

如果以 Redis Set 的方案来计算:3kw * 200 * 32 * 1.5(Redis 数据结构自身存储) ~ 288G,每天需要消耗存储 288G,1个月呢?8.6T,1年呢?103T。以腾讯云 keewiDB 的持久内存来估计 64元/GB/月,1月成本大约 55w,有钱也不能这么造啊。

那有没有更优惠的实现方案呢?这就要说到本文的主角,布隆过滤器了。

方案二:Bloom Filter

布隆过滤器,本质上是一个高阶 Bitmap,最适合的场景就是海量数据的过滤了。

不了解 Bitmap 的同学可以参考 https://www.cnblogs.com/dragonsuc/p/10993938.html。

布隆过滤器介绍

布隆过滤器的结构如下图示:

bloom filter

简单说下它的使用:

1. 写入:对数据 data 进行 k 次 hash 运算(hash 函数可选择,本文不具体较少),得到结果后,对 bit 数组相应位置置1。

2. 检查:对数据 data 同样进行 k 次 hash 运算,得到结果后,检测 bloom bit 数组中相应位置是否全为1,如全是1,则表示该 data 存在于 bloom 中;否则,表示该数据不在 bloom 中。

结合上述描述,我们可以得出如下结论:

1. bloom 中存的摘要,而不是原始数据 data,所以空间占用远远低于 set 的占用。

2. bloom 无法删除数据,如上图示 x、y 都对 bit 数组中 bits[2] 置1了,如果删除 x,则 bits[2]为0,y判定时,也判定失败了。

3. bloom 无法动态扩展大小,如上图示,bit 数组是固定的,如果 bits 数组长度调整了,那么同样的 x、y hash 后的 bits 索引也会发生变化。

4. bloom 存在误判的可能,例如 x、y hash 后得到的 bits 数组索引都是 1、3、5,那么即使 bloom 中只添加了 x,当 y 来判定时,也会判定为存在。

误判率计算公式

这里不细究它的推导过程了,感兴趣的同学可以自行研究。

布隆过滤器实现曝光打击

由上述布隆过滤器的特性所知:必须合理选择 bloom 过滤器的规格,bloom bit 数组太小,则误判率过高;bloom bit 数组太大,则过于浪费存储。

还是以相同的条件来试算,

假设国民级 App 的日活跃用户在 3kw,每人每天平均刷 200 条视频 feeds,每条 feeds 的 id 长度为 32B。

如果以 Redis bloom 的方案来计算:400B * 3kw ~ 12G,相比 set 方案的 288G,节约了 96% 的存储成本。1月可以节约 52.8w 成本,降本增效杠杠的。

当设置 bloom 容量为 200 时,每人每天1个key,可以保证当天看到不重复的 feeds,BF 规格如下:

采用 Redis Bloom 插件计算,https://redis.io/docs/stack/bloom/。

bloom filter 规格

进一步优化

上述场景下,Bloom 大小按照 200 计算,那活跃用户呢?总有一些高活用户,每天会刷大几百条视频,这部分用户不做特殊处理的话,体验会非常差,后面总是看到重复的视频。还有就是一些特殊场景,例如业务希望用户1月内都不要看到重复的 feeds。这种,如果仅仅以每天每人作为 bloom 的 key,那么实现1个月内不重复,1个用户要查询30个 bloom,有点夸张。

Redis 虽然能抗,但假设用户刷视频的频率是 10w/s,扩散后,对 Redis 的压力就是300w/s

怎么优化呢?有几种思路。

1. 最简单,让 Redis 抗,单机扛不住,分片还扛不住吗?分片扛不住,读写分离还扛不住吗?反正肯定能抗住。

2. 记录1个总数量的 bloom key,分级,递增设置容量。例如起始 bf0 容量是 1000,当 bf0 满了,新建一个 bf1,容量是 10000,bf1 满了,再新建一个 bf2,容量是 10w。这种方案有两个好处,1是递进的增加 bf 容量,减少 Redis 的 key 访问次数,减轻 Redis 的压力;2是不浪费存储,大部分用户都是非活跃用户,可能看到的 feeds 量在 1w 以内,只有真正活跃的用户才会分配 10w 以上的大 bf,精准的占用存储。

分级 BF

至此,本文就大体结束了,后面有时间了再开一篇布谷鸟过滤器的说明,先鸽一下。

标签:

THE END
广告、内容合作请点击这里 寻求合作
免责声明:本文系转载,版权归原作者所有;旨在传递信息,不代表中国财投网的观点和立场。

相关热点

资讯播报

世界新消息丨布隆过滤器在短视频 feeds 系统中的妙用
每日关注!迎接植树节 沪上高校师生共栽橘树建橘园
世界热消息:河南太昊陵庙会“41万黄金摊位”半月已回本,摊主:明年能否拔得头筹不在意
天天实时:全国人大代表、天合光能董事长高纪凡:促进农村分布式光伏发展,助力乡村振兴
世界消息!逃离字节,我回县城开店,没人看好,月入10万
努力干饭,呆萌可爱……来柳州十年,两只大熊猫备受市民喜爱
视点!3月11日起,南宁地铁这3个车站出入口正常投入使用
今日快看!5921元/月! 2022年度广西人才网薪酬报告出炉
当前短讯!冷空气来杀回马枪!广西将迎来降温+大风+短暂降雨天气
环球看热讯:“委员通道”上响起广西“好声音” 来看看她说了啥
美国2月失业率上升 离停止加息还有多远?
焦点信息:科创板业绩快报有哪些亮点?
周丽淇_说一说周丽淇的简介
环球今亮点!餐饮单位餐厨垃圾逾期未报 松江新桥综合行政执法队两次上门普法
展望会展业发展新格局 2023国际会展业CEO上海峰会将于六月举行
当前资讯!织密未成年人保护的“法网”
当前动态:达成“长江禁渔”共识,沪太联合跨省巡航打击非法捕捞
今亮点!上海半程马拉松将于4月16日开跑
世界最新:读错字!黄磊女儿黄多多道歉
【当前热闻】联储“钝刀割肉”还是 “大刀阔斧”?
泰晶科技登顶A股晶振行业2022年利润榜单| 财时代
开出40000多家店的快餐之王被“卖身”,赛百味兴也加盟,衰也加盟
4000k色温对眼睛好吗_4000k色温是什么光
天天速看:感冒引起的咳嗽一直好不了怎么办_感冒引起的咳嗽吃什么药好得快
【天天快播报】3月12日起,冷空气将自北向南影响广西
岳阳林纸:2022年度归母净利润增长106.51%至6.16亿元
天天消息!南宁车站加开重联一批动车,涉及这些方向
信息:广西实现高速公路服务区充电桩100%全覆盖
焦点快看:带动产值100亿元 广西实现建制村“村村通快递”
全球信息:这些企业上榜 !2022年广西智能制造标杆企业名单公布
两会灼见丨欧余军委员:扶持民族地区创新发展民族医药
【两会整点报·8点档】履新记⑧丨苏海珍:深耕边疆文化 守护民族根脉
全球通讯!2022年广西租赁住房职工公积金提取超33亿元
微资讯!美国财政部正对几家银行进行监控 耶伦再次呼吁对债务上限采取行动
焦点讯息:购物车中的广告促进健康的购买
今日快看!硅谷银行(SIVB.US)引发美股银行股动荡前 “聪明钱”早已嗅到危险信号
世界讯息:烤箱烤牛肉的做法孩子吃_烤箱烤牛肉的做法
天天头条:不论男女,早上空腹吃点它,用不了多久,失眠就改善了!
新增40国!第二批出境游试点国家名单出炉,越南热度第一,机票甚至低至908元
电视面板的春天来了?中大尺寸短期有望超预期上涨
每日热点:没钱、没人、没资质 园城黄金跨界追锂遭市场冷遇
天天亮点!3月12至14日受较强冷空气影响 广西将有降温大风天气
柳州市本级2022年度灵活就业社会保险补贴开始申报
全球即时看!拍到了!多种“奇珍异兽”现身广西木论国家级自然保护区
天天百事通!筑起边民“幸福路”!广西这条重要的互市贸易点公路通车
那个首家复牌的出险房企
每日报道:喜忧参半!美国2月非农就业人数新增31.1万但失业率上升
全球快看:半合成机油全合成机油的区别_半合成机油和全合成机油有什么区别
为什么美国监管华尔街大行而不监管硅谷银行(SIVB.US)?
【天天聚看点】为什么说轻医美仍处于红利期?谁将拿下红利?|对话蛋壳肌因
当前快报:美银行股爆雷 推高外汇期权隐含波动率
全球简讯:崔东树:2月新能源车厂商批发渗透率30.6%
【聚看点】香港金管局与香港证监会就场外衍生工具交易规定展开联合咨询
实时焦点:硅业分会:本周市场信心不足 硅价弱势运行
雾芯科技公布2022年全年业绩 净营收53.3亿元
环球短讯!银行业“黑马”迭出,看江苏银行成色几何?
每日看点!上百行征信的后果
火车只停靠站台两分钟,民警争分夺秒抓获两名嫌疑人
环球今热点:2023年1月末央行外汇占款环比增加1536.97亿元
天天看点:不动产私募基金试点启动,“金融支持租赁17条”出台|2月住房租赁市场月报
全球热文:央行:2月广义货币(M2)余额同比增长12.9% 人民币贷款增加1.81万亿元
世界即时:不要惊讶!股票型ETF可能正对短期美债造成流动性冲击
【环球快播报】祝贺!广西云数字媒体集团荣获“2022年度广西十大互联网企业”称号
环球微资讯!菜心、芥蓝、水芹等春鲜上市,百姓菜篮子装满春的味道
环球今头条!小学英语发言稿_小学英语优秀教师发言稿
3月12日起美国进入夏令时 美股开盘收盘均提前一小时
校园之风流霸主
焦点!A股日报 | 3月10日沪指收跌1.40%,两市成交额达8096亿元
环球资讯:2月我国动力电池装车量21.9GWh 同比增长60.4%
环球观天下!上海人注意!九亭站公交枢纽择日开放
前沿热点:将追思祈福服务搬到线上 福寿园京东"春祭"上线
美原油交易策略:全球股市普遍下跌,油价延续跌势
每日聚焦:美国页岩油巨头:油价现已触底 可能在今年夏季上涨17%
现货黄金交易策略:非农来袭,警惕季节性波动减弱拖累数据
每日速读!欧盟拟将天然气需求削减措施延长至明年
全球报道:艾罗能源答复科创板二轮问询,实控人及其控制企业大额负债等被关注
全球最资讯丨明星基金经理的隐形重仓股曝光!冯明远加仓福达股份
世界资讯:IDC:2022年中国腕戴设备市场销量为4455万台 同比下降13%
视点!宁王年报出炉!净利大增 罕见推出高送转 影响多大?
每日热闻!穿旗袍学茶艺、赏民乐写书法……这所大学这样欢度妇女节
快消息!Cellinia Texas × Lappland Saluzzo(转载自Pixiv,已注明画师,侵删)
环球快报:肉鸡养殖市场高景气!超强鸡周期来临?
世界通讯!全面注册制加速进行 首批主板平移拟IPO企业下周上会
焦点观察:长三角G60科创走廊智慧供应链产业合作示范园区揭牌
热头条丨长三角G60科创走廊智慧供应链产业合作示范园区揭牌
当前热讯:一天两班!春秋航空上海至济州航线复航
股票休市钱能取出来吗?元旦股市放假安排2022年一览表
银行上班时间几点到几点下班?银行上班时间中午休息还是不休息?
量化私募的含义是什么?量化私募的优势主要体现在哪些方面?
美国国债持有国排名有哪些国家?我们为什么要买美国的国债?
如何进入建设银行积分兑换商城?建设银行积分兑换步骤是什么?
世界即时:原创歌曲《团结成钢》MV重磅发布 中华民族同声共振
世界观察:三菱汽车计划在2035年实现100%电气化
移动花卡宝藏版怎么样?移动花卡宝藏版多少钱一张?
如何网上买基金?在哪里买基金最安全可靠?基金开户流程是怎样的?
投资理财公司可信吗?理财公司倒闭了怎么办?
养殖贷款找哪个银行?养殖业贷款咋办理?养殖业贷款申请流程介绍
股票黄线是什么意思?如何看股票分时图上的白线和黄线?
【环球快播报】头像国旗怎么弄的?具体操作步骤是什么?
环球微速讯:世界人口指的是什么?全球有多少亿人口?

相关推荐

精彩推送

3