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

深度解析某头条的一道面试题

  •  1
     
  •   codehole ·
    pyloque · 2018-03-31 09:13:12 +08:00 · 6566 次点击
    这是一个创建于 2189 天前的主题,其中的信息可能已经有所发展或是发生改变。

    首先,某头条的文章量、用户量都是很大的,点击量那就更恐怖了。 请问,如果实时展现热门文章,比如近 8 小时点击量最大的文章前 100 名。 如果是你来开发这个功能,你怎么做?

    这个好办啊,redis 一个 sortedset 搞定啊,score 计数,key 是文章 ID,不就 ok 了么?

    回答的不错,你可以走了!

    要听清题目,说好的 8 小时动态时间窗口,计数是会过期的。还有,头条的量有这么小么,一个 redis 就搞定了?同学啊,我告诉你,文章的量你起码得估计个几十万,用户你得估计几个亿,点击量你至少得估计个 1M/s 吧。

    数据接收

    1M/s 的点击并发量,肯定是需要分布式了。客户端可能会为了减轻服务器的压力而选择延迟合并点击请求进行批量发送。简单起见,这里就使用 HTTP 协议吧。我们先不考虑恶意用户刷点击的行为。

    服务器肯定会有多台机器多进程部署来接受点击请求,接收到的请求在进行参数解析后,被发送到存储单元。为了减轻存储的压力,每个进程可能会使用小窗口聚合数据,每隔一小段时间将窗口内的数据聚合起来一起发给存储单元。

    数据存储

    点击数据是很重要的数据,用户的兴趣偏好就靠它了。这么大的点击数据如果全部用内存装的话,成本太高。所以别指望完全使用 redis 了。

    拿 kafka 存是一个好办法,ZeroCopy 机制并发量很高,数据持久化在磁盘里成本低。不过 kafka 的数据一般是有过期时间的,如果想完全记住用户的点击以便做长期的数据分析,少不了要使用 hdfs 了。

    但是因为要做准实时统计,hdfs 可不适合干这个,hdfs 适合做离线统计的数据源。所以还得靠 kafka 接数据,然后消费者一边入 hdfs,一边做实时统计。

    实时统计可以使用 spark stream、storm 接受 kafka 的输入,也可以自己手写。

    分布式 TopN 算法

    用户太多,用户表按用户 ID 哈希分成了 1024 张子表。用户表里有一个字段 score,表示这个用户的积分数。现在我们要计算前 100 名积分最多的用户以及积分数,该怎么查询?

    如果是单个表,一个 SQL 也就搞定了

    select id, score from user order by score desc limit 100
    

    如果是多个子表,你得在每个子表上都进行一次 TopN 查询,然后聚合结果再做一次 TopN 查询。下面是伪代码

    candidates = []
    for k in range(1024):
        # 每个表都取 topn
        rows = select id, score from user_${k} order by score desc limit 100
        # 聚合结果
        candidates.extend(rows)
    # 根据 score 倒排
    candidates = sorted(candidates, key=lambda t: t[1], reverse=True)
    # 再取 topn
    candidates[:100]
    

    子表查询可以多线程并行,提高聚合效率。

    滑动窗口

    8 小时的滑动窗口,意味着新的数据源源不断的进来,旧的数据时时刻刻在淘汰。严格来说,精准的 8 小时滑动窗口要求每条数据要严格的过期,差了 1 秒都不行,到点了就立即被淘汰。

    精准的代价是我们要为每条点击记录都设置过期时间,过期时间本身也是需要存储的,而且过期策略还需要定时扫描时间堆来确认哪些记录过期了。量大的时候这些都是不容小嘘的负担。

    但是在业务上来讲,排行版没有必要做到如此的精准,偏差个几分钟这都不是事。

    业务上的折中给服务的资源优化带来了机遇。我们对时间片进行了切分,一分钟一个槽来进行计数。下面是伪代码

    class HitSlot {
        long timestamp; # earlies timestamp
        map[int]int hits;  # post_id => hits
        
        void onHit(int postId, int hits) {
            this.hits[postId] += hits;
        }
    }
    
    class WindowSlots {
        HitSlot currentSlot;  # current active slots
        LinkedList<HitSlot> historySlots;  # history unactive slots
        map[int]int topHits; # topn posts
        
        void onHit(int postId, int hits) {  # 因为上游有合并点击,所以有了 hits 参数
            long ts = System.currentTimeMillis();
            if(this.currentSlot == null) { # 创建第一个槽
                this.currentSlot == new HitSlot(ts);
            } elif(ts - this.currentSlot.timestamp > 60 * 1000) {  # 创建下一个槽,一分钟一个槽
                this.historySlots.add(this.currentSlot);
                this.currentSlot = new HitSlot(ts);
            }
            this.currentSlot.onHit(postId, hits);
        }
        
        void onBeat() {  # 维护窗口,移除过期的槽,然后统计 topn,30s~60s 调用一次
            if(historySlots.isEmpty()) {
                return;
            }
            HitSlot slot = historySlots[0];
            long ts = System.currentTimeMillis();
            if(ts - slot.timestamp > 8 * 60 * 60 * 1000) {  # 过期了 8 小时,移掉第一个
                historySlots.remove(0);
                topHits = topn(aggregateSlots(historySlots));  # 计算 topn 的帖子
            }
        }
    }
    
    

    上面的代码代表着每个分布式子节点的逻辑,因为是伪代码,所以加锁问题就不细写了。 它的目标就是定时维持一个 8 小时的统计窗口,并汇聚 topn 的热帖放在内存里。 这个 topn 的数据并不是特别实时,有一个大约 1 分钟的短暂的时间窗口。

    定时任务

    每个子节点都会有一个定时任务去负责维持统计窗口,过期失效的统计数据,计算局部的 topn 热帖。

    现在每个子节点都有了各自的局部 topn 热帖,那么还需要一个主节点去汇总这些局部热点,然后计算去全局热帖。

    主节点也没必要特别实时,定期从子节点拉取 topn 数据即可,也可以让字节点主动汇报。

    class HotPostsAggregator {
        map[int]map[int]int localTopnPosts;  # nodeId => topn posts
        map[int]int globalTopnPosts;
        
        void onBeat() {
            // do aggregate
            // save globalTopnPosts to redis
        }
        
        void onLocalReport(int nodeId, map[int]int topnPosts) {
            // 子节点上报局部热帖
        }
    }
    

    散列

    按照头条的文章至少几十万篇,如果每个子节点都要对所有的文章统计点击数,似乎也会占用不少内存,聚合和排序热帖也会有不少计算量。最好的想法是每个子节点只负责一部分文章的统计,这样可以明显节省计算资源。

    我们将 kafka 的分区数设置为字节点的数量,这样每个节点负责消费一个分区的数据。在 kafka 生产端,对点击记录的帖子 ID 进行散列,保证相同文章 ID 的点击流进入相同的分区,最终流向同一个统计子节点。

    消费者挂了

    当机器增多时,节点挂掉的概率也会增大。硬件可能损坏,电源可能掉电,人为操作失误。如果没有做任何防范措施,当一个字节点挂掉时,该节点上 8 个小时时间窗口的统计数据将会丢失。该节点所管理的局部热点文章就丧失了进入全局热帖的机会。

    这可能不会对产品和体验上带来很大的伤害,节点重启 8 小时之后也就完全恢复了。而且这 8 小时之内,丧失了部分文章的热点投票权也不会对整体业务带来巨大影响。

    但是我们都希望系统可以更加完美一点不是么?当节点挂掉时,我们希望可以快速恢复状态,这也是可以做到的,难度也不是很大,不过是定时做一下 checkpoint,将当前的状态持久化到本地文件或者数据库中。因为每个子节点管理的文章不会太多,所以需要序列化的内容也不会太大。当节点重启时,从持久化的 checkpoint 中将之前的状态恢复出来,然后继续进行消费和统计。

    如果你使用的是 spark-stream,它内置的 checkpoint 功能会让你实现备份和恢复会更加简单,更加安全。

    如果你不想做 checkpoint,办法还是有的,就是可能耗时旧一点。那就是对 hdfs 中的存储的所有的点击流数据进行一次 mapreduce,将 8 小时窗口内的点击流的点击量统计出来,然后想办法导入到字节点进程中去。

    这要求 hdfs 的数据也是散列存储的,和 kafka 对应,这样可以快速圈出需要统计的数据范围。也许会因为 mapreduce 本身会耗时一点时间,最终导致恢复的数据没有那么准确,不过这关系也不大,我们用这样粗糙的方法,能对得起那 9.5 成的数据已经做的很不错了。

    点击去重

    上面讲了一堆堆,代码敲了不少图画了不少,似乎很有道理。但是还有个重要的没提到,那就是点击去重。如果一个用户反复点击了很多次,那该如何计数比较合理。

    一篇好的文章如果它不是太短的话,一般会吸引读者反复阅读很多次。这个计数如果完全去重了记为一次似乎也不太合理。但是如果是故意被人反复点击而被记了太多次明显也不好。那该如何选择呢?

    首先要从客户端下手,客户端本身可以过滤一部分无效点击。同一篇文章在太短的时间内被当前用户反复点击,这个模式还是很好发现的。如果间隔时间比较长,那就是读者的回味点击,属于文章的正向反馈,应该记录下来。

    客户端做好了,然后再从服务器端下手,服务器端下手就比较困难了。要探测用户的行为模式意味着要对用户的行为状态化,这样就会大量加重服务器的存储负担。

    服务器还需要防止用户的防刷行为。如果缺失防刷控制,一个头条号可以通过这种漏洞来使得自己的文章非法获得大量点击,进入热门文章列表,打上热门标签,被海量的用户看到,就会获得较大的经济效益,即使这篇文章内容本身吸引力并不足够。

    当用户发现这样差劲的内容也能上热门榜单时,无疑会对产品产生一定的质疑。如果这种行为泛滥开来,那就可能对产品造成比较致命的负面影响。

    防刷是一门大型课题,本篇内容就不做详细讲解了,笔者在这方面也不是什么专家。简单点说放刷本质上就是提取恶意行为的特征。常见的策略就是同一篇文章被来自于同一个 IP 或者有限的几个 IP 的频繁点击请求,这时就可以使用封禁 IP 的招数来搞定。还可以使用用户反馈机制来识别非正常的热门内容,然后人工干预等。业界还有一些更高级的如机器学习深度学习等方法来防刷,这些读者都可以自行搜索研究。

    阅读相关文章,关注公众号 [码洞]

    23 条回复    2018-04-02 16:46:43 +08:00
    contmonad
        1
    contmonad  
       2018-03-31 10:13:37 +08:00 via iPhone
    第一步随机采样,后面想怎么做怎么做。流式数据统计有各种近似算法,事实上,文中的 Top-k 也不能保证结果绝对正确
    codehole
        2
    codehole  
    OP
       2018-03-31 10:31:08 +08:00 via Android
    @contmonad 随机采样,好方法!
    farseeraliens
        3
    farseeraliens  
       2018-03-31 10:58:09 +08:00 via iPhone
    还真是一个 redis 就能搞定的事。
    类型 string 过期时间 8 小时 key 是时间戳,value 是文章 id 定长二进制,用 redis 的原子 append,后台单进程定期统计后发给前端 nginx 就行。
    vegito2002
        4
    vegito2002  
       2018-03-31 11:00:21 +08:00 via iPad
    文章内容本身还是不错的。 这种系统设计一般针对几年经验?
    farseeraliens
        5
    farseeraliens  
       2018-03-31 11:00:44 +08:00 via iPhone
    做项目都像楼主这思路迭代得多慢啊,而且很多功能是试水性质的,小流量验证效果不好的话都不一定全流量上线。
    GtDzx
        6
    GtDzx  
       2018-03-31 11:06:01 +08:00
    请教一下 “客户端可能会为了减轻服务器的压力而选择延迟合并点击请求进行批量发送。” 是什么意思?
    Umix
        7
    Umix  
       2018-03-31 11:08:11 +08:00 via Android
    几个亿用户可以分成多个主服务器来推送,节省汇总消耗,而且更符合地域偏好
    Umix
        8
    Umix  
       2018-03-31 11:09:16 +08:00 via Android
    @GtDzx 客户端进行初步统计,再定时把结果发给服务器
    seancheer
        9
    seancheer  
       2018-03-31 11:18:00 +08:00
    @GtDzx 根据伪代码,可能是指同一个文章的多次点击,合并为一次发送,所有伪代码有 int hits 这个参数
    cdwyd
        10
    cdwyd  
       2018-03-31 11:20:48 +08:00 via Android
    既然量那么大,只计算其中一部分也不影响排名
    moult
        11
    moult  
       2018-03-31 11:25:33 +08:00 via iPhone   ❤️ 2
    其实有一个很坑的办法。如果单纯为了得到点击量前几个的话,不需要统计实际的点击量的话,可以直接来一个 1-100 的随机数,如果随机值是 1 的话,才进行入库统计,直接将数据库压力缩小 100 倍了,毕竟头条的热门文章点击量都是十万百万级别的,对实际的排行结果几乎没有影响。
    codehole
        12
    codehole  
    OP
       2018-03-31 11:31:57 +08:00 via Android
    @moult 看第一个评论😊
    feverzsj
        13
    feverzsj  
       2018-03-31 11:37:16 +08:00
    哈哈,扯这么多,信不信一个 c/c++服务端就能搞定
    leeg810312
        14
    leeg810312  
       2018-03-31 11:51:19 +08:00 via Android
    持续大流量,#1 的统计采样方法我觉得应该是最合适的,数据精度不需要也不可能到真正的准确值,也就不必真的把每个文章的点击全部计数
    geelaw
        15
    geelaw  
       2018-03-31 12:57:26 +08:00
    类似问题 抄送 /t/415626
    wdlth
        16
    wdlth  
       2018-03-31 13:50:15 +08:00
    新采集 100 篇文章,把点击量 UPDATE 成最高……
    binux
        17
    binux  
       2018-03-31 14:06:24 +08:00
    这个设计太 “面向面试设计” 了。
    点击以及用户点击这些数据不仅仅是为了 topN 服务的,不是说推给你一个消费者就完了的。
    反过来,这些数据反正是要记录的,那么根本不需要实时处理。先存在某个地方,定时再聚合就完了。
    jinya
        18
    jinya  
       2018-03-31 16:49:49 +08:00 via Android
    m
    liprais
        19
    liprais  
       2018-03-31 17:03:03 +08:00 via Android
    闭门造车
    sumu
        20
    sumu  
       2018-03-31 17:42:00 +08:00 via iPhone
    其实吧,这些问题都很简单,真的,只要对海量服务有一些了解和意识,会有很多类似的思路,说白了,只要你设计的架构与 cpu、内存成线性,就是正确的思路,只是你堆的好,我堆得差,没本质区别。我想讲的是:大公司面试要求各种高,按超人标准来招聘,但进去后做的都是蓝翔毕业生都能做的事
    xuanyuanaosheng
        21
    xuanyuanaosheng  
       2018-03-31 19:34:55 +08:00 via Android
    mark
    swulling
        22
    swulling  
       2018-03-31 20:00:15 +08:00
    简单问题复杂化
    CallFold
        23
    CallFold  
       2018-04-02 16:46:43 +08:00
    赞一个
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1124 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 71ms · UTC 22:56 · PVG 06:56 · LAX 15:56 · JFK 18:56
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.