天天新消息丨布隆过滤器在短视频 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。
布隆过滤器介绍
布隆过滤器的结构如下图示:
简单说下它的使用:
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 大小按照 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,精准的占用存储。
至此,本文就大体结束了,后面有时间了再开一篇布谷鸟过滤器的说明,先鸽一下。
标签:
相关阅读
-
take(a及break)-全球看点
一、题文takeabreak和havearest的区别是什么?二、解答havearest是比较普遍的生活用语,而且它特指休息一下。takeabr
2023-03-11 -
世界微速讯:朱洪武在市综合交通基础设施“十大工程” 调度推进会上强调 加快节奏 提质增效 调优状态 全力冲刺 奋力实现市第六次党代会确定的目标任务
3月10日下午,市委书记朱洪武主持召开市综合交通基础设施“十大工程”调度推进会。市委常委、常务副市长...
2023-03-11 -
capital market(capitaland)_百事通
1、XianisthecapitalofShaanxiprovince,locatedinthesouthernpartoftheG
2023-03-11 -
摔角动态权威媒体爆料院长已同签订多年合同 全球资讯
摔角网讯,北京时间2019年10月12日,权威媒体ESPN独家爆料称,UFC悍将毁容院长凯恩·维拉斯奎兹(cainvel...
2023-03-11 -
每日速读!34+2!新星冉冉升起,感谢交易!4年1亿太香了,对比扎心勇士
谁也想不到全场处于领先的开拓者在最后一节遭遇逆转,最终以119比120一分之差遗憾输掉了比赛。其实开拓...
2023-03-11 -
天天速讯:摔角动态最壮观的50人上绳挑战赛即将上演 葬爷,Y2J有望出席
前不久正式宣布将在北京时间2018年4月28日,在沙特阿拉伯阿卜杜拉国王体育城迎来有史以来最宏大的一场50...
2023-03-11 -
每日热点:恭喜樊振东!大满贯赛连赢2场,男单3-0横扫名将,身体状况良好
北京时间3月11日晚,乒乓球WTT新加坡大满贯赛继续进行,国乒奥运冠军樊振东在混双比赛结束数小时后再次...
2023-03-11
精彩推荐
阅读排行
相关词
- 沃尔沃XC90
- 杏林春满堂(杏林春满)
- 天天关注:最高120公里续航,爱玛欣果电动车低至2799元
- 报道:拉拉是什么意思翻译(拉拉是什么意思 女孩子)
- 新文化运动的两大口号是啥(新文化运动的两大口号是)-头条
- 焦点简讯:春游计划三年级作文(春游计划)
- 李逵怎么去江州(李逵怎么死的)_全球聚看点
- 靓什么时候读jian(靓什么时候读jing)
- 洒水的拼音是什么_洒水的读音|讯息
- 世界快讯:甲功正常,但 TPOAb 、TgAb偏高,需要处理吗?
- 环球即时看!很少说谎,但每一个谎言都不会被人拆穿的3个星座
- 贵南高铁广西段接触网全部贯通
- 新华全媒+丨农机“比武”备春耕-全球聚看点
- 日本民众集会抗议核污染水排放入海计划
- 联合国特别报告员:加拿大原住民寄宿学校历史令人震惊|微资讯
- 天天新消息丨新西兰专家:日本核污染水排海计划漠视太平洋国家主权和自决权
- 世界微资讯!we(are及the及world)
- 【报资讯】母亲节做贺卡(母亲节日快乐)
- 当前速递!扑克牌花色大小(扑克牌花色)
- 摔角动态突然解雇四位NXT选手
- 微会员卡(微会员)
- 焦点简讯:涿鹿之战打一水浒人名(逐鹿之战)
- 总角之宴(总角)
- 每日头条!跖疣这两个字念什么(蚍蜉怎么读)
- 焦点热讯:茱莉亚文斯身高(茱莉亚文斯)
- 摔角动态马特·哈迪说新一天组合头戴假鸡鸡
- 看未来科技?AIGC提示:输入密码01
- 人浮于事的表现(人浮于事) 焦点
- 摔角动态ECW元老级选手去世 享年44岁
- 环球聚焦:轮轴的原理动画_轮轴的原理
- 闯关东中篇影视介绍(闯关东中篇演员表)|世界通讯
- 西江月井冈山ppt教案(西江月井冈山)|环球百事通
- 下列哪一事项不得确定为工作秘密 有关工作内部(下列哪一事项不得确定为工作秘密) 精彩看点
- 新漫评:声声枪响击不穿美国政治虚伪和冷漠 环球播资讯
- 海报 ▏外媒聚焦两会 哪些话题备受关注?_天天亮点
- 前沿热点:中型客车核载多少人数(中型客车核载多少人)
- 中秋节作文开头美句(中秋节作文开头)|每日焦点
- 摔角动态萨摩亚·乔将会《摔角狂热32》后RAW首秀?_天天动态
- 动态焦点:海德堡cd102有几个水箱(海德堡cd102)
- 902000元大写该怎么写(9020)
- 苹果AR头显预计售价20000:将取代iPhone
- 当前看点!北京大兴119个村级医疗机构将纳入医保定点
- 天天快播:摩托罗拉Razr 2023真机曝光:折叠外观变了
- 喜报!陈幸同首战告捷,3-0大胜,晋级大满贯赛次轮!-天天新视野
- 大爆冷!马刺终结2连败,西部第一轰然倒下!冲突爆发,2人被驱逐-天天热议
- 全球最新:兰德尔:视科比为偶像,因老詹离开湖人,成为纽约新王他却后悔了
- 基德表示把持不住欧文,欧文因私人问题偷偷离开独行侠队|滚动
- 即时焦点:卡纳瓦罗评大金子:在国安水因注意力不集中亚平宁人说话总是“意”味深长
- 环球热头条丨CBA常规赛第34轮迎来本赛季第二次京沪大战
- 今日关注:山东高速男篮结束了两连客的征程
- 环球热文:摔角动态夏洛特前往NXT 尚未回应挑战便遭偷袭
- 释的部首是什么偏旁怎么读(释的部首)
- 辽鲁二番战辽篮没有给山东队任何机会-天天讯息
- 孔蒂:热刺得让自己的球迷有耐心这赛季打入前四就像赢了英超冠军 全球通讯
- 周琦再度与CBA擦肩而过,因为他已被逼上梁山,粉丝:他太无辜了
- 滕哈格要求曼联1亿边锋更勇敢!900万悍将或受重用,充当替补奇兵-前沿资讯
- 小经跑两会|服务加力 让更多老人安享幸福晚年 全球球精选
- 天天观点:国青上次赢韩国队还是19年前!但韩国队轻敌,未做打中国队预案
- 环球报道:努比亚Z50 Ultra外观做到了颜值第一
- 全国人大代表孙泽洲:我国探月工程值得期待
- 世界观速讯丨物流保通保畅:民航保障航班量环比增长3.6%
- 泉城“金街”向新而行
- 湖北竹山:羊肚菌点亮“工业兴旺星”-天天播报
- 何买拉苏代表:永远做草原上的“红色文艺轻骑兵”
- 女人40岁后,若有这5种表现,说明快要绝经了,希望你别忽视了
- 牛奶的英文单词怎么写(牛奶的英文)
- 作文六一儿童节500字六年级(六一儿童节优秀作文)-当前关注
- 最强赘婿沈浪最新章(最强赘婿沈浪)|焦点短讯
- 简讯:摔角动态乔·莫斯利首谈到底是如何完美招募到自己的
- 美丽的同义词四个字(美丽的同义词)
- 德赫亚恐步C罗后尘双:红会惨案背锅侠诞生,曼联正在寻找新门将-世界热闻
- 大周去哪大结局?晒海沃德4代高清图,安踏能崛起么?
- 当前看点!总台记者专访丨日本专家:日本政府应担负责任 提高核事故处理信息透明度
- 再见内马尔!巴黎求购1.5亿神锋,为姆总分忧,不补中场令人迷惑|全球热头条
- 世界热议:王曼昱遭进退两难!专注单打被王艺迪压制,混双最佳搭档又被拆分
- 湖北竹山:羊肚菌点亮“产业兴旺星”
- 世界观焦点:女子忽然“齁气”走路费劲竟是肺栓塞,医生:呼吸困难应及时就诊
- 俄外长:西方媒体对“北溪”爆炸新说法“轻率不成熟”-新资讯
- 商务部新闻发言人就美将我多家实体列入“特别指定国民清单”事答记者问_环球播报
- 西部三场事关排名的对决结束|世界观速讯
- 摔角动态罗曼·雷恩斯首度透露自身职业生涯最酷时刻
- 灰熊队结束3连败勇士队吞下3连败
- 三个火一个木(三个火)
- 焦点快报!杜兰特在热身时扭伤脚踝无缘参赛而库明加复刻了杜兰特的这一剧情
- 环球热讯:屏下Touch ID!真全面屏iPhone安排了
- 我国学者发现,m6A甲基化是治疗阿尔茨海默病的潜在新靶点 全球关注
- 下午16点!央视直播计划有变,国青生死战遭无视,球迷骂声一片 世界热资讯
- 王晗赛后甩锅,赛后点名一人,山东输球全怪他?-热点在线
- 天天短讯!经典姿势再现只为了带货?穆里尼奥或再被意大利足协重罚!
- 周琦重返CBA下家有变,曝大魔王将购豪宅,睢冉的选择令人敬佩|微速讯
- 全球观速讯丨中国队档位悬念揭晓!直升一档,洋帅打鸡血:后人会感谢这批国脚
- 因热身时扭伤脚踝库明加本场比赛确认缺阵
- 实时:摔角动态复兴组合一再拒绝报价 布克·T看不下去了
- 环球微动态丨飞猪app怎样查看检票口
- 描写祖国风光的谚语(关于祖国风光的谚语)-天天简讯
- 本赛季NBA西部联盟排名争夺非常有看点
- 毫无疑问克里斯托弗是一名具备不俗潜力的球员
- 天天速递!2-2,54冠王爆冷,68%控球不解渴,迎54年新格局,尤文罗马笑了
- 【新视野】英超官方:曼联将帅包揽二月最佳主帅和最佳球员
- 买断市场最新动态!51分先生联手KD,快船放虎归山,威少静观其变
- 辽宁VS山东男篮,球迷表示这3人不能再用,王晗该决定了
- KK踢球风格与萨拉赫相似斯帕莱蒂:我的执教生涯非常幸运
- 世界今日报丨应该如何准确测量血压呢?看完涨知识啦!
- 消灭幽门螺旋杆菌的植物有哪些?或许是这3种,尤其是最后一种 世界观点
- 全球快资讯:凭证类型
- prefer A to B(prefer)|当前动态
- 全球快资讯丨摔角动态《RAW 2017.02.21 》战报 欧文斯自信满满 对战高柏稳操胜券
- 神魔养殖场作者入狱(神魔养殖场作者坐牢)
- 岁寒然后知松柏之后凋也出自(三军可夺帅也匹夫不可夺志也出自) 通讯
- 当前信息:斩魂辅助(斩魂技能)
- 劳塔罗迪马利亚梅西前三迪巴拉随后阿根廷球员世界杯后进球榜|当前热点
- 凝望村庄:“跟着春风走,就没有错”
- 全球今亮点!这种不起眼的“野草”,全身是宝,可做菜可入药,抗衰老功效显著
- 时隔150天,丁俊晖再进决赛圈,球迷:3年了,这个冠军等太久了!
- 【天天聚看点】大战在即!国青主帅激情演讲:为了中国足球的明天,必须击败韩国
- 李梦22+7大爆发!率队掀翻卫冕冠军,冲队史首冠,杨力维空砍24分 天天报道
- goo结尾的英文名(goojie)
- 灞桥纸的时代和特点(灞桥纸是什么时期的纸)
- 莫言(诺贝尔文学奖奖金)
- 摔角动态鲁瑟夫受伤 与拉娜感情不合?鲁大师本人正式回应
- 当前短讯!位移加速度速度概念(位移加速度公式)
- 新生牛犊腹泻怎么办,老农教你几招民间土方,都是多年经验总结
- 文旅部发布第二批恢复出境团队旅游国家名单
- 刺激,0-2大冷门,63%的控球仍输,拜仁的绊脚石遭倒数第一掀翻
- 【环球播资讯】肯豆詹娜的这个新男友,怎么看怎么像是德文布克的哥哥
- 2023年研考国家线发布 教育部部署复试录取工作 全球即时看
- 生果是饭前吃仍是饭后吃好?不同的人有不同的吃法!
- 环球今头条!商务部回应美将多家中国实体列入“特别指定国民清单”
- UZI伤病加重将无缘2020年春季赛,没有UZI的RNG能否破釜沉舟?-快播报
- 山东助教接管球队,周琦现身看球赛,鄢手骐唯一弱点
- 报告:中国财富家庭拥有的总财富达164万亿元
- 大韩航空客机内发现实弹 韩国警方介入调查
- 摔角动态战神高柏被指必将在沙特巡演上参赛 目前对手待定
- 一件烦心事作文100字(一件烦心事作文)
- 每日视点!不以为然的意思(不以为然的意思)
- 世界热消息:那段快乐的日子500字作文(那段快乐的日子)
- 蓝精灵的歌(蓝精灵的歌)
- 全球速递!农历3月27横财近身, 3生肖运势水涨船高, 收益增多, 升官发财
- 韩国高兴早了,19年不败纪录作古,国青2大核心缺阵逼近世青赛
- 环球百事通!劳塔罗全场数据:1次失点,5次射正,获评6.9分
- 两名35岁大个子球员搭档出奇效,雄鹿1年650万美元签对人了
- 内心非常强大,不会容易玻璃心,总是乐观向上的三个生肖 环球速看料
- 【全球时快讯】快船和掘进记者连续发推破口大骂:是篮网毁了西部
- 三分钟带你了解乒乓球发球规则与技巧!成为国球高手并不难! 世界百事通
- 摔角动态奥顿和塞纳都曾来过NXT 并且与同一位酱油选手发生过剧情
- 我爱学校我爱老师作文(我爱老师作文)
- 摔角动态魔蝎斯汀能否参加《超级秀2020》 外媒最新消息出来了
- 环球新消息丨摔角动态这场众所期待的对决真要发生了?夏洛特遭遇空前叫嚣
- 热推荐:优派27寸4K显示器1459元
- 艾滋病多久能查出来(被自己的儿子上是什么感觉)-天天快消息
- 苹果HomePod 3曝光颠覆设计 国产一屏幕厂商直接涨停 当前速看