Top K 问题 - Top K Problem

题目

这类型的题目大多都是设计一个类似排行榜的系统，通过对海量数据的聚合处理最后获得排名前K的东西，比如：

• 系统设计，一个music app，选出 top 10 songs。
• 实现前5分钟，1小时，24小时内分享最多的post的系统
• Design Twitter Trend, Determine trending topics(twitter)
• 一个K recent contact 的service，就是当用户把鼠标点到chat对话框的时候，自动弹出K个最近的联系人。follow-up是如果要弹出K个最熟悉的人怎么设计，以及资源估计（需要多少台机器来做数据存储，多少个处理request等等）
• Desgin an Advertisement (AD) statistic system
• 一个大型系统中Top K个 Exception

总结

特点是写频繁， 不用完全精确（精确程度需要和面试官确认）

由于是海量数据，推荐异步操作（message queue）

核心就是三个service，

• DataCollection (不用实时记录，累计一段时间的结果一起记录，比如每100个click 记录一次）
• DataAggregation (loosy counting, sticky sampling，目的是去掉count 1的东西)
• Query (分成不同的颗粒度granularity来存储，五分钟，一小时，一天)

具体设计 (以下部分待完成）

需求分析 （Collect Requirement)

下面以设计热门话题、标签（比如推特/微博上的 #NBA ）为例

写频繁

分为几个部分：数据采集，数据处理，数据查询

用户每次发帖，带上话题hashtag #，记录为一次

知道某个话题总共多少次被提及

知道最近的x小时/x天/x月/x年的热门话题

Number: 1 bln DAU, 1 click/user/day, 10K QPS, 50K QPS

假设是存储热门词汇, 就要给每个词存count, 100M words in english, 100M \* \(10 Byte + 8 Byte\) = 200MB ，不需要很大空间

但是考虑到QPS， 依然需要很多机器

服务设计 (Service Design)

DataCollection

Q：加入我们用一台机器来统计数据，每次用户发帖都要记录到该机器上，机器负载过大

A：首先在server 中进行一次缓存，服务器每台机器上可以专门开一个进程来统计数据，这个进程一直在后台运行，比如每次用户发送带有话题 #NBA 的帖子，就呼叫统计进程来进行+1操作，可以使用一个hashMap。然后每台机器，每隔10秒把数据发送给统计节点。这样子通过10s的延时缓存，解决了统计节点负载过高问题。

CollectionService发过来的信息还是比较多，而且有很多词汇/post share/likes count 只有一个，这些东西完全没有必要统计，所以可以用两个策略：

Query Service