布隆过滤器在短视频 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,精准的占用存储。
至此,本文就大体结束了,后面有时间了再开一篇布谷鸟过滤器的说明,先鸽一下。
相关文章
- Java项目毕业设计:基于springboot+vue的电影视频网站系统「建议收藏」
- 第三章·Linux系统入门-Bash初识
- 智慧加油站视频监控行为识别分析系统
- 园区视频监控智能分析系统
- java和vue视频点播系统视频弹幕系统
- 5分钟搭建一个粗粒度「视频去重」系统
- 某地园区视频监控系统项目施工组织方案,值得视频监控类项目参考,文末附下载!
- 全景AR增强监视系统对接SkeyeIVMS视频云管控系统实现软硬件资源的健康状态管理(二)
- 煤矿电子封条视频监控系统
- linux系统安装msf的过程详解
- 嵌入式Linux系统中视频下载技术研究(嵌入式linux视频下载)
- 微软推送 Win10 21H1 系统 Build 19043.1147 发布预览版本
- [视频]3D扫描系统可以简化买鞋过程
- Linux系统调用:开启程序的精准通道(linux什么是系统调用)
- 分析开启Linux系统源代码探索之旅(linux系统的源代码)
- 微软发现恶意 npm 软件包,可从 UNIX 系统窃取数据
- 学习Linux系统,看这个视频!(linux系统使用视频)
- Linux 系统种类大比拼,哪个更适合你?(linux有什么系统)
- 深入探究:体验深度 Linux 系统的魅力(深度linux系统怎么样)
- 入门系列:Linux系统视频教程(linux系统入门学习视频)
- Linux系统容器的建立和简单管理
- IMX 6 Linux: 赋能嵌入式系统的可靠性与灵活性(imx6linux)
- Linux系统安装视频:快速搞定!(linux 安装 视频)
- Oracle强势登陆Linux系统(linu下oracle)