最近一大厂SD题目design twitter search实战反馈讨论贴

design twitter search，已知什么user信息，twitter的数据库和服务都存在的基础上，要求实现几个关键字Or在一起的twitter搜索，返回list of twitter。我的理解就是只要Twitter里有其中之一的关键字就是符合条件的twitter。

以下是我当时的表演过程：

1. 考虑到这个feature太显而易见了就没讨论feature细节，上来我就开始说workload，假设twitter有1billion注册用户，一半日活就是500M，再假设twitter用户习惯刷timeline，很少会search，所以就随口来了个1Msearch request一天，相当于58个request per second（后来想来只有0.2%的转化率是有点低的离谱啊），然后我说因为workload太小了，其实一个machine就能搞定，但考虑到twitter用户是遍布全球各地的，再加上想fault tolerate，我还是想按照distributed system的架构来设计，我心里想这么说也算是justify我为什么要为一个workload这么小的feature设计一个分布式架构，要不然说单机搞定我一会儿该怎么表演呢。之后我又提了两点要考虑的地方，一是low latency，二是availability。所以我之后的表演都是围绕架构以及如何实现low latency和availability来展开的。

面试官质疑1：
request per day咋这么低？我说依据我使用twitter的经验我都是看twitter timeline啊，八辈子也不会使用search，其实我几乎不用twitter，就是照搬微信使用体验，算是用自己的使用体验justify了为什么0.2%用户会做search。

再就是我说一台machine就够用好像不太准确，其实我想说一台application server就够用，但还有许多machine要用来存放从word到twitter的对应关系的server，毕竟word的数量和twitter的数量巨大应该一台machine是不够存的，再有就是我把存对应关系的machine和database混为一谈说的，但面试官不知是如何理解，当时感觉他面部表情不太对，估计以为我index server和存twitter的database分不清吧。

2. 完事我就从back end如何handle一个query开始说了，主要是想讲一下back end handle一个query的逻辑。我先说data都是按照关键字和含有关键字的twitter对应存放的，这样在搜索时可以直接通过关键字找到所有含有此关键字的twitter，而不用遍历所有twitter去找。然后回来再merge在一起返回。

面试官质疑2：
如何merge？我就说既然是or的关系，那就通通放在一起然后去重按relevant权重返回就完了。又问具体如何算更relevant，我就说如果一个twitter里有更多关键字就算更高relevant。面试官不置可否。

3. 完事我又具体讲了下如何存放对应关系，说用consistent hash，说这样可以保证存储的负载均衡。

面试官质疑3：
consistent hash具体是怎么放数据的？我说画一个圆，把machine都哈希了map到上面，然后把每个word也都哈希了map到上面，然后word都存到顺时针或逆时针遇到的第一个machine里，面试官不置可否。这里吐槽下VO时代面SD写板书太难了，google draw根本不知道自由画笔在哪，也不知道怎么在圆这种shape的边上加文本，反正最后板书写是一塌糊涂，我自己都看不下去了。

面试官质疑4：
数据库具体怎么放对应关系的？我按照关系数据库说的，一行是一个对应关系，首列是word的哈希值，然后是word本身，然后是list of twitter id。面试官不置可否。

4. 然后我说用memcache，这样对于有些query就不需要走整个逻辑了。

面试官质疑4：
memcache放在哪？我说可以放在两个地方，一是client和application server之间，这样如果memcache里有以前一样的query那么application server就可以直接返回了；二是放在application server和database（其实我是想说index server）之间，这样在applicaiton server问某一个关键字的时候就可以直接返回了，不需要真的到硬盘去找。面试官不置可否。

5. 完事我又说application server和database之间我想用个message queue，这样主要考虑是在存储的负载均衡的基础上来解决对热门搜索关键字的负载均衡，因为message queue后面可以有好多replication的database来subscribe对于某一个词的搜索，而且也解决了availability的问题。说到这里我忘了consistent hash的事了，所以跟面试官说message queue的topic是按照a-c,d-f这样连续的，结果被面试官抓住，问不是consistent hash了吗，我一惊，对啊，但不想承认自己脑子抽筋，硬着头皮说是database内部排序，为了方便索引，但自己知道自己是在胡说八道。我估计这是我暴雷的地方。

总体感觉就是我太注重设计distributed system的一些通用问题了，包括availability，low latency，consistency等，但对于twitter search这个feature本身的逻辑没有想清楚；再就是我之前从没有准备过system design，就是因为某大厂要面就花了1周时间准备，看了太多内容但对于应用场景肯定是不知道的，就想着把自己懂得都给招呼上，不知道以上有些技术是不是用的不妥或者overkill了，还请地里各位大神斧正。

三篇 Twitter 官方技术文章解答这个问题，希望能帮到楼主

https://blog.twitter.com/enginee ... te-tweet-index.html
https://blog.twitter.com/enginee ... ure-at-twitter.html
https://blog.twitter.com/enginee ... -index-formats.html

Traffic问题

• traffic会远比这个大，因为Twitter作为一个open api的平台，会有很多第三方的脚本或爬虫来访问search API。以及对于同一个geo location，search的traffic会相对比较集中，所以rps峰值也会很高。
• 楼主所说的一台"application server"应该指的是用来承接search traffic的stateless的service，可以被称为search系统的front-end。我认为在楼主应该把系统框图画出来，来表明FE和storage的关系。
  

如何merge & 数据如何存放
按照楼主的描述，我理解是想做成倒排索引（inverted index），结构类似于{"cat" => [1000, 999, 300], "food" => [1001, 999, 200]}，就是由关键词指向tweets id list。面试官应该期待能够讲出用什么方法去具体进行merge。一个常见merge的方法是倒排索引里的文档列表保持顺序的链表（最好是跳表），然后使用跳表合并。
consistent hash在这个场景下是可以接受的，肯定需要sharding，暂时没有从回答中看出什么问题。

Cache

• client和application server中的cache指的是什么？如果我的本地网页版twitter是client的话，在到达application server前的cache我只能当做本地浏览器缓存利用或CDN来理解。但是CDN应该不太适合这个场景
  

没有看懂message queue在这里的意图，题主可以再elaborate一下。

my 2 cents, 楼主的主要问题是：

• 沟通不通畅：楼主对于很多问题是理解的，但是并没有让面试官充分理解。楼主可以试着用一些办法来加强面试官的认知，比如画图、系统分层；
• 某些地方的设计比较vague，不够具体。
  

感觉总体答得还算可以。。。
一点点我的想法：

多个词or的话，好像要用一个算法算score，具体不记得了，一般是越短content的score越高，hit的词越多的越高，还有就是几个词距离越近score越高。

还有memcache好像不能放在client和app server之间吧，一般是直接在app server里面用 in memory cache（guava这种）？

mq放在search path会不会增加search的latency？感觉这里加mq有点多此一举啊，加一个coordinator来按照hashing直接dispatch search request就行了吧？ mq一般放在write path里

最后就是write的部分好像没有cover到，不知道是不是时间不够，感觉search service，写比较复杂，读真的还好，因为每次写都要update 各种 indexing table

楼主写的好详细呀，怎么做到边输出边记忆这么仔细的……先加个分再仔细读一下

楼主是几年经验的哇

WIwindson 发表于 2020-11-3 10:47
三篇 Twitter 官方技术文章解答这个问题，希望能帮到楼主

https://blog.twitter.com/engineering/en_us/ ...

谢谢分享，有时间我去看看

Andy_Wang 发表于 2020-11-3 11:36
楼主是几年经验的哇

我是转专业的，可以说没有业界经验，就做过几个side project

从楼主的回答可以看出几乎没啥相关经验吧，都是在堆资料的感觉，看似好像说了一堆其实跟问题相关性都不大，而且你说的这些你真的懂吗😂

Airaly 发表于 2020-11-9 06:08
从楼主的回答可以看出几乎没啥相关经验吧，都是在堆资料的感觉，看似好像说了一堆其实跟问题相关性都不大， ...

扎心了老铁，还在摸索中

liuyang5832 发表于 2020-11-02 21:32:38
我是转专业的，可以说没有业界经验，就做过几个side project

我也转专业 可以私信分享是哪家大厂嘛 已加米

地里希望能多看到大家发SD的表演。以我的水平，也就能把你说的这些丢出去。如果面试官碰巧也知道Grokking the System Design Interview, 就知道咱们都是业余师出同门。下下周就要面试了。最近越学越觉得系统设计有料，比刷题更见功力。