System Design
  • Introduction
  • Design Twitter
  • Design Tiny Url
  • Design Instagram
  • Consistent Hashing
  • NOSQL
    • Dynamo
    • Big Table
  • 在浏览器输入URL
  • RESTful API Design
  • 索引
    • Hash Indexes --- Bitcask
    • B-tree
    • LSM
  • Design Instagram
  • Design KV Store
  • Design Message System
  • Design Localization System
  • Design RSS Reader
  • Design Ticket Master
Powered by GitBook
On this page
  • Design Twitter
  • 1. Service
  • 2.Storage
  • 3.Scale
  • 4. Miscellaneous
  • 5.References

Was this helpful?

Design Twitter

Design Twitter

1. Service

(1) Media Service: upload Photo/Media

(2) Friendship Service: follow/unfollow user

(3) Tweet Service: Post tweet, timeline(一个特定用户的tweet), news feed(自己和别人的tweet)

(4) User Service: Register, login

2.Storage

(1) Pull Model

a. 原理：在用户看news feed的时候，从数据库中读取每个followee的前100条tweet，然后通过merge sort取出前100条。如果用N个followee的话，则有N次DB read和一次DB write

b.缺陷: N次读取DB很慢, 并且是发生在用户查看news feed的时候

c.优化: 利用cache优化读的过程，首先查看cache有没有我们要的数据，有的话直接返回，否则再去查看db，并且写到cache里(如果cache没满的话)

(2) Push Model

a. 原理：对每个用户都建立一个news feed table. 当一个user post tweet的时候，fan out这条tweet到所有他的follower。当user查看news feed的时候，直接从他的news feed table里查看前100条。一次read，n次write

b. 缺陷:

  • 如果一个用户有很多follower(比如明星用户), 则fan out的过程要很久，work load很大

  • 需要更多的空间存储news feed table

3.Scale

(1) Pull Model优化

a. 利用cache优化读的过程，首先查看cache有没有我们要的数据，有的话直接返回，否则再去查看db，并且写到cache里(如果cache没满的话)

(2) Push Model优化

a. 用更多的机器做fan out

b. 根据follower的rank决定fan out的顺序，比如可以先fan out给在线的follower，再fan out剩下的follower。在线的follower可以定义为最近一周内登录的user

c. 对于存储空间问题，我们可以把news feed存到disk里

(3) 明星问题(Celebrities tweet)

a. 针对明星用户，利用Pull + Push Model。当一个用户查询news feed时从他的news feed table读取数据，对于他follow的明星用户，则pull 明星用户(定义: follower > 100M)的timeline,合并到news feed里

b. 特殊情况：如果一个明星用户由于大量掉粉，变为普通用户，这时我们无法读取他的feed。解决方法是当明星用户发tweet时，仍然fan out到follower的news feed table, 用户读取news feeds时， 将关注的明星用户的timeline和自己的合并并展现出来，但不存储在news feed table里 (push已经做了这个事)

(4) Follow/Unfollow User

a.Follow一个用户后，异步地(asynchronously)将该用户的timeline合并到自己的news feed

b.Unfollow一个用户后，异步地将他的tweets从自己的news feed删除

c. 通过的异步，可以让用户觉得follow和unfollow的过程很快，毕竟合并和删除news feed的过程可能比较耗时

d. 利用异步处理的缺陷是，如果用户unfollow后查看news feed,可能仍然看到被unfollow的用户的tweets，但这些tweets最后还是会被删除的

(5) Hot spot(Thundering Herd)问题

a. 定义：就是短时间内读/写请求很多，load很大，即使使用cache, 也会由于过于频繁overwrite cache的数据造成压力大，比如 Lady Gaga发个自拍会怎样?无数人点赞,评论,转发

b. 减少Load的方法是利用Lease机制，简单说就是server对client的数据缓存的有效期。比如server的cache里有client B的数据， server给client B缓存颁发一个lease，在lease到期之间，server承诺client B的缓存是有效的。这里client A发消息要求修改，server收到消息后不会执行A的请求，直到lease过期。

4. Miscellaneous

(1) 什么时候用Pull Model

  1. 单向好友关系（从自己关注的人中get news)

  2. 有明星问题

  3. 资源充足

  4. 实时性要求高

(2) 什么时候用Push Model

  1. 双向好友关系 (fanout时需要知道谁关注了我, check news feed时需要知道我关注了谁)

  2. 没有明星问题

  3. 实时性要求不高(在明星fanout时，可能有些用户收到tweet时出现延迟，如果他在还没收到tweet前check news feed, 明星刚刚发的 tweet不会显示)

  4. 资源少

5.References

http://highscalability.com/blog/2013/7/8/the-architecture-twitter-uses-to-deal-with-150m-active-users.html

一个News Feed Design的总结

Facebook如何利用Lease机制优化Memcache 3.2.1 Leases

Lease机制介绍

"Designing Data-Intensive Applications" Page 11-13

PreviousIntroductionNextDesign Tiny Url

Last updated 5 years ago

Was this helpful?