# 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的总结](http://yuanyuanzhangcs.blogspot.com/2017/02/news-feed-design.html)

[Facebook如何利用Lease机制优化Memcache](http://www.cs.utah.edu/~stutsman/cs6963/public/papers/memcached.pdf) 3.2.1 Leases

[Lease机制介绍](http://www.zenlife.tk/lease.md)

"Designing Data-Intensive Applications" Page 11-13
