查看: 1524| 回复: 2
跳转到指定楼层
上一主题 下一主题
收起左侧

[找工就业] 请大牛答疑解惑-关于系统设计 design twitter search, 如何sharding

全局:

2023(10-12月)-CS博士+5-10年 | Other| 码农类General全职@

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
本帖最后由 welcoming123456 于 2023-11-9 23:23 编辑

最近在看grokking the system design interview 这本书,里面有一题design twitter search, 书里提到index (word--> tweetID) 如何sharding 提到:


第一种: Sharding based on Words, 提到有如下两个缺点:


1) What if a word becomes hot? Then there will be a lot of queries on the server holding that word. This high load will affect the performance of our service.
2) Some words can end up storing a lot of TweetIDs compared to others, therefore, maintaining a uniform distribution of words while tweets are growing is quite tricky.

. ----第二种:  Sharding based on the tweet object,  提到 While querying for a particular word, we have to query all the servers, and each server will return a set of TweetIDs. A centralized server will aggregate these results to return them to the user.
. check 1point3acres for more.
我感觉这本书的意思的是第二种 “Sharding based on the tweet object” 没有第一种的两个缺点 “Sharding based on Words”,所以要选第二种。可是我有两个问题:.1point3acres

1)第二种并没有解决 hot word 的问题啊,而且使情况变得更糟糕了,因为比如一个word短时间内有 1 million的search,第一种会使得一个server有 1 million queries, 而第二种会使所有servers 都有 1 million 的queries, 因为第二种每次都要query 所有servers啊。. 1point3acres
2)第二种每次都要query 所有servers,然后合并,速度要比第一种慢很多吧?

请问大牛们,我的理解对吗?
..
我比较倾向于第一种(Sharding based on Words),  但没想好如何处理 hot word 和 不even distributed 的问题,请问大牛们怎么想?

补充内容 (2023-11-11 13:23 +08:00):

补充:design twitter search 的功能是: 根据输入的单词,搜索并返回包含该单词的所有tweets。

上一篇:应该选 买它 MLE II (E4)还是Senior DS (E5)?
下一篇:有人最近投过JnJ intern吗
🔗
mnhg123 2023-11-10 17:07:19 来自APP | 只看该作者
全局:
没读过这本书,大概看了一下两段话,纯靠经验 说错请勿喷

1 看起来,有两种不同的搜索模式,只搜索一个单字或者搜索全部的tweet。
2 看起来,他提到的第一种方式很类似reverse index
3 当使用第一种方式 shard by word的时候,实际上是把tweet按照空格split成单字,每个字都指向原来的tweet id。其实就是简单的k,v。好处是如果search 单字,可以一下定位到对应的shard 但坏处在于,对于有的单字,比如a或者the会很hot 。还有就是,保存开销更大,比如说,一个255个不同单字的tweet,会有255个指向它对索引。这会占更多的资源(比如disk, 或者create index的cpu资源)

4 也许可以通过对每个shard做多个replica的方法来尽可能解决data skew,查询的时候,可以随便找latest version replica
. 1point 3acres
5 第二种方式,类似map reduce 确实可能会慢,但好处在于,节省了很多index的开销。拿之前的tweet举例,不需要每个单字的索引了,节省了255个。

回复

使用道具 举报

全局:
这本书就是很垃圾,几乎所有题目的解法你细想一下都有错误,很多设计的偏重点都莫名其妙,讨论的那些tradeoff都自相矛盾。这本书你就看看有哪些topic看个大概,然后去搜对应的系统设计。把这本书当标准答案就要等死
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表