美文网首页
系统设计面试题 - 设计 Twitter 时间线和搜索 (或者

系统设计面试题 - 设计 Twitter 时间线和搜索 (或者

作者: 专职跑龙套 | 来源:发表于2018-04-26 13:18 被阅读111次

    引用:
    系统设计入门

    设计 Twitter 时间线和搜索 (或者 Facebook feed 和搜索)

    解答

    第一步:通过讨论,明确限制及用例,确定Scope

    支持的用例:

    • 用户发一条tweet
      • 系统将该tweet推送给该用户的followers,并发送通知
    • 用户查看自己的user timeline
    • 用户查看别人的home timeline(follow 的人)
    • 用户通过关键词搜索
    • 系统高可用 high availability

    不支持的用例:

    • 系统不支持将该tweet推送给第三方系统,例如Firehose。
    • 系统不支持隐藏tweet功能。
    • 系统不支持统计Analytics功能。

    Constraints and assumptions:

    • 访问不均匀
    • 发送及推送tweet要快
    • 100 million 用户
    • 平均每个用户有 10 个 followers
    • 每天 500 million 新tweet,乘以10,等于每天 5 billion 个推送,每秒60,000次
    • 每月 15 billion 写请求 = 500 million * 30,每秒6,000次
    • 每月 250 billion 读请求,每秒100,000次
    • 每月 10 billion 搜索请求,每秒4次

    计算规模:
    对于每一个tweet:

    • tweet_id:8 bytes
    • user_id:32 bytes
    • text:140 bytes
    • media:10 KB average
    • 总共: ~10 KB

    对于每一个月:

    • 新tweet内容:150 TB = 10 KB * 500 million * 30
    • 三年:~5.4 PB = 150 TB * 36

    第二步:高层次设计

    设计 Twitter 时间线和搜索 (或者 Facebook feed 和搜索)

    第三步:设计核心组件

    Tweet基本信息存储在关系型数据库MySQL中。
    Tweet包含的图片及视频等内容存储在 Object Store 中,可以是 Amazon S3,或者文档型的NoSQL,例如 MongoDB。

    对于Write API:设计为一个REST API

    • 将Tweet基本信息存储在关系型数据库MySQL中。
    • 图片及视频等内容存储在 Object Store 中。
    • 使用 Fan Out Service:
      • 使用 User Graph Service 来查询该用户的followers,随后在Memory Cache中更新对应每一个follower的home timeline。
      • 使用Search Service来存储这个tweet,用来支持快速查询。
      • 使用Notification Service来推送给该用户的followers。

    使用Redis作为Memory Cache,并使用list结构,例如:

               tweet n+2                   tweet n+1                   tweet n
    | 8 bytes   8 bytes  1 byte | 8 bytes   8 bytes  1 byte | 8 bytes   8 bytes  1 byte |
    | tweet_id  user_id  meta   | tweet_id  user_id  meta   | tweet_id  user_id  meta   |
    

    对于Read API:设计为一个REST API

    • 使用Tweet Info读取tweet详细信息。
    • 使用User Info读取user详细信息。
    • 从 Memory Cache 中读取 user timeline 和 home timeline,找不到,则查询数据库。

    对于Search API:设计为一个REST API

    • 解析输入字符串:
      • 去除标记 markup
      • 分词
      • Fix 输入错误 typo
      • 规范化大小写
    • 使用Search Service进行搜索。包括结果的 merges, ranks, sorts 等等。

    第四步:扩展设计

    设计 Twitter 时间线和搜索 (或者 Facebook feed 和搜索)
    • 为了服务不同区域的用户,加快访问的速度,使用CDN加速,并缓存静态内容,例如图片,视频等等。
    • 为了同时响应更多请求,对服务器水平扩展,并使用Load Balancer做负载均衡。
    • 由于是读多写少,可以采用主从复制的数据库模式。主库同时负责读取和写入操作,并复制写入到一个或多个从库中,从库只负责读操作。

    其他一些优化思想:

    • Memory Cache 只保留活跃用户(最近30天上线过)的timeline,且只保留最近的100条tweet。
    • Tweet Info Service 只保留最近一个月的Tweet。
    • User Info Service 只保留活跃用户的信息。

    相关文章

      网友评论

          本文标题:系统设计面试题 - 设计 Twitter 时间线和搜索 (或者

          本文链接:https://www.haomeiwen.com/subject/pwbplftx.html