V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
luger1990
V2EX  ›  算法

千万用户推荐去重算法

  •  
  •   luger1990 · 2018-04-29 23:57:49 +08:00 · 9725 次点击
    这是一个创建于 2411 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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

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

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



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

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

    建个表储存用户已看内容的 ID,推荐的时候用 left join 去重,内容一定有时间属性,只给用户推最近一段时间的内容,也只储存最近一段时间的已看记录,计算量和储存空间都会大大减少
    murmur
        10
    murmur  
       2018-04-30 09:28:51 +08:00
    @mumbler 比如一个用户只看一万个内容 他有 1kw 用户就是 1kww 个数据 这不分区或者说分区了我都不知道咋设计
    mumbler
        11
    mumbler  
       2018-04-30 10:14:30 +08:00
    @murmur 首先用户不可能一天看一万个内容, 大多数内容的生产和消费都和时间相关,假设平均每个用户每天看 50 条(已经很多了),先给用户推荐最近一天生产的内容,如果看完了,再推荐一周内的内容,最多只储存用户最近一周的观看记录用于去重. 1KW 用户就算全部都是铁杆活跃用户,数据总量也就 30 亿级别,且可以按用户 ID 分区,内容按时间分区
    murmur
        12
    murmur  
       2018-04-30 10:16:52 +08:00
    @mumbler 楼主的需求是推荐不重样 虽然我感觉楼主对推荐算法理解差太多 那考虑一页推荐 20 个 刷个几次就够了
    luger1990
        13
    luger1990  
    OP
       2018-04-30 10:21:46 +08:00
    @yidinghe 不是 是总共一百万条视频 单个人能刷完这 100W 条视频 每次刷到的都是自己以前没看过的
    luger1990
        14
    luger1990  
    OP
       2018-04-30 10:23:10 +08:00
    @murmur 我是想怎么存储用户看过的如果用 redis 的 set 或者 hash 存储用户看过的那么占用的内存太大了,因为用户基数大
    luger1990
        15
    luger1990  
    OP
       2018-04-30 10:23:49 +08:00
    @kslr 但是还得记录每个用户看过的视频 用户基数大 就会导致占用内存太大
    murmur
        16
    murmur  
       2018-04-30 10:26:44 +08:00
    @luger1990 单纯从业务角度来想 #11 楼的反倒是对的 即便是不推荐 要不每年网易云这种是拿啥出的年终报告。。
    mumbler
        17
    mumbler  
       2018-04-30 10:38:09 +08:00   ❤️ 1
    @luger1990 所以不建议你用推模式啊,不用 nosql,直接关系数据库储存用户最近一周的观看记录来去重即可。就算用推的,也不需要给每个用户储存 100W 的队列,因为实际场景中,用户一辈子都不可能看到 100W 个视频. 如果内容与时间无关,也没有新内容进来,每天固定 500 个给所有人建队列就行了,第二天把前一天的数据删除了再来 500 个,真有人看完就单独给他拉内容。把问题缩小到一个封闭空间内,一下就非常简单了
    googlefans
        18
    googlefans  
       2018-05-01 21:51:26 +08:00 via iPad
    @luger1990 我表示在抖音经常看到重复的推荐。。。
    luger1990
        19
    luger1990  
    OP
       2018-05-01 23:16:35 +08:00 via iPhone
    @googlefans 我还没看到 看来我看的还不够多
    LenonZeng
        20
    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 个里面,相同的值会碰撞就是看过了;
    luger1990
        21
    luger1990  
    OP
       2018-06-09 11:36:13 +08:00
    解决问题了,最后选用的是布隆过滤器。
    kalman03
        22
    kalman03  
       2018-11-15 17:30:39 +08:00
    @luger1990 详细点的流程呢?
    qicmsg
        23
    qicmsg  
       2020-01-21 20:57:09 +08:00
    @luger1990 能详细说下怎样取数据的逻辑吗?如何从库里取出未浏览数据呢?
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5786 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 33ms · UTC 03:25 · PVG 11:25 · LAX 19:25 · JFK 22:25
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.