千万用户推荐去重算法

2018-04-29 23:57:49 +08:00
luger1990  luger1990

先不考虑推荐算法。如果我有 1KW 个用户,需要把一百万个短视频推荐给用户,并且不能重复推荐。我该用什么方法来达到这个目的。

reids 的 bitmap 去重的话确实很省空间,但是一个用户如果只看了一个视频我就得给用户在 redis 中分配一个固定大小的存储,那 1KW 个对象也是很大的存储空间,布隆过滤器同样如此

或者说我给用户推荐过的放到一个 set 里面或者 hash 里面,每次推荐的时候从推荐池子里拿 1000 个通过和 redis 中已推荐过的内容对比如果没有推荐那么推荐 推荐过的就 continue 感觉这样很 low 呀。。。

还有没有更好的解决方案!!

9801 次点击
所在节点   算法  算法
23 条回复
murmur
murmur
2018-04-30 00:00:20 +08:00
我扯一点跟技术无关的
在国内如果做推荐的话先学着怎么活下去
比如今天 b 站音乐区热榜第一的是个什么呢
https://www.bilibili.com/video/av22697648/
真的见证历史
luger1990
luger1990
2018-04-30 00:01:31 +08:00
@murmur 哈哈哈 牛逼
orangeade
orangeade
2018-04-30 00:05:07 +08:00
是不是建一个 MySQL 的视频-用户关系表比较合适,之后就直接 SQL 查就行了,redis 还是缓存热点数据比较好吧



@murmur 跑题了,不过共青团中共确实令人作呕
murmur
murmur
2018-04-30 00:09:37 +08:00
@orangeade 虽然有点跑题
但是上一枪打的就是快手
现在快手的推荐跟红色专区没区别了吧
楼主恰恰也提到了短视频这个热点
算法总归是得跟着需求来的

那从算法角度来看直接每个用户一个访问计数器而已 每次顺着随机初始位置+计数器*每次推荐个数往后走就行
他这个一看就是想做一个看上去随机的随机么 又不是要把这 100 个视频均匀推给 1000 个用户
如果我理解错了那楼主还要完善他的需求描述
luger1990
luger1990
2018-04-30 00:14:15 +08:00
@murmur 是给所有用户随机推荐全部的视频,和抖音类似 但是不能重复推荐 最终所有人都能看到全部视频
kslr
kslr
2018-04-30 03:56:31 +08:00
@luger1990 那些就简单多了直接见到做交集
kslr
kslr
2018-04-30 04:09:47 +08:00
我又申了下题,如果用 hash 不就几百 m 内存吗?
yidinghe
yidinghe
2018-04-30 07:14:15 +08:00
重复推荐是什么意思,比如你有一万用户,每人推荐 100 条,不重复推荐,就得要一百万条视频啊。
mumbler
mumbler
2018-04-30 09:23:04 +08:00
拉模式

建个表储存用户已看内容的 ID,推荐的时候用 left join 去重,内容一定有时间属性,只给用户推最近一段时间的内容,也只储存最近一段时间的已看记录,计算量和储存空间都会大大减少
murmur
murmur
2018-04-30 09:28:51 +08:00
@mumbler 比如一个用户只看一万个内容 他有 1kw 用户就是 1kww 个数据 这不分区或者说分区了我都不知道咋设计
mumbler
mumbler
2018-04-30 10:14:30 +08:00
@murmur 首先用户不可能一天看一万个内容, 大多数内容的生产和消费都和时间相关,假设平均每个用户每天看 50 条(已经很多了),先给用户推荐最近一天生产的内容,如果看完了,再推荐一周内的内容,最多只储存用户最近一周的观看记录用于去重. 1KW 用户就算全部都是铁杆活跃用户,数据总量也就 30 亿级别,且可以按用户 ID 分区,内容按时间分区
murmur
murmur
2018-04-30 10:16:52 +08:00
@mumbler 楼主的需求是推荐不重样 虽然我感觉楼主对推荐算法理解差太多 那考虑一页推荐 20 个 刷个几次就够了
luger1990
luger1990
2018-04-30 10:21:46 +08:00
@yidinghe 不是 是总共一百万条视频 单个人能刷完这 100W 条视频 每次刷到的都是自己以前没看过的
luger1990
luger1990
2018-04-30 10:23:10 +08:00
@murmur 我是想怎么存储用户看过的如果用 redis 的 set 或者 hash 存储用户看过的那么占用的内存太大了,因为用户基数大
luger1990
luger1990
2018-04-30 10:23:49 +08:00
@kslr 但是还得记录每个用户看过的视频 用户基数大 就会导致占用内存太大
murmur
murmur
2018-04-30 10:26:44 +08:00
@luger1990 单纯从业务角度来想 #11 楼的反倒是对的 即便是不推荐 要不每年网易云这种是拿啥出的年终报告。。
mumbler
2018-04-30 10:38:09 +08:00
@luger1990 所以不建议你用推模式啊,不用 nosql,直接关系数据库储存用户最近一周的观看记录来去重即可。就算用推的,也不需要给每个用户储存 100W 的队列,因为实际场景中,用户一辈子都不可能看到 100W 个视频. 如果内容与时间无关,也没有新内容进来,每天固定 500 个给所有人建队列就行了,第二天把前一天的数据删除了再来 500 个,真有人看完就单独给他拉内容。把问题缩小到一个封闭空间内,一下就非常简单了
googlefans
2018-05-01 21:51:26 +08:00
@luger1990 我表示在抖音经常看到重复的推荐。。。
luger1990
2018-05-01 23:16:35 +08:00
@googlefans 我还没看到 看来我看的还不够多
LenonZeng
2018-05-17 21:11:37 +08:00
大概这个思路:可以用 bitmap 处理,用户用 1KW 个 bit 表示~ 1.25M; 100W bit ~ 0.125M,实际上每个用户不可能吧 100 万的视频都看完,可以假定每个用户看 1000 个视频~0.125KB;每一个 bit 后面跟 0.125KB, 大于要维护 1.25MB *0.125K~156.25M 的空间。
每次分配的时候,取个 hash 值映射到 1000 个里面,相同的值会碰撞就是看过了;

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/450968

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX