如何设计Twitter?

系统设计第一篇,如何设计Twitter?此问题同样也可以推广到如何设计Facebook、微博、微信朋友圈等。

Twitter

Motivation

写这篇博文的目的很简单,陆续看了太阁和九章算法对Twitter的讲解后,对这个系统设计问题有了比较深入的理解,特此做一个记录,以后若遇到同类的设计问题,举一反三,融会贯通。
从系统设计4SE原则着手,开始设计Twitter。

Scenario

Twitter的功能如下:

  • 注册/登录
  • 用户信息显示/修改
  • 加载图片/视频
  • 搜索
  • 发送/共享Tweet
  • Timeline/News Feed
  • 关注/取消关注

系统设计中,我们往往关注系统的核心功能,Twitter的核心功能可以总结如下:

  • 发送Tweet
  • Timeline
  • NewsFeed
  • 关注/取消关注

Suppose

这部分主要估计系统的QPS,根据QPS决定整个系统的架构。
首先假设Twitter的 DAU=150m+, 每天的Tweet数为400m(这部分不清楚可以直接问面试官)。
QPS = 150m * 60 / 86400 ~ 100k
Peak QPS = QPS * 3 ~ 300k
对于Twitter这种增长比较快的系统,考虑QPS可以适当的加2倍或者3倍。
基于以上的估算结果我们大致可以得出:
Read Timeline QPS = 300k
Write Timeline QPS = 5k


Service

把Twitter的主要功能拆分成几个服务模块,Twitter系统的架构如下:
Architecture
Twitter架构内部实现可以分为Push和Pull模型。

Push

Push模型的流程如下:
Push
Push模型中,用户发送一条Tweet后Tweet服务将这个Tweet插入到关注该用户的News Feed中,是一个主动服务的过程。
问题:Push模型存在的问题是Lady Gaga的风暴问题,如果某个用户被关注的人数太多,生成这些用户的News Feed会占用比较长的时间,可以缓解这个问题的一个办法是先通知在线的用户,再去处理离线用户的News Feed。

Pull

Pull模型的流程如下:
Pull
Pull模型中,用户发送一条Tweet后立即存储在DB中,当用户需要自己的News Feed的时候,读取用户关注者的Tweet,然后根据时间戳合成该用户的News Feed,是一个用户主动请求的工程。
问题:上帝视角,如果某个用户关注非常多的其他用户,合并过程会比较慢。

Push vs. Pull

Push和Pull模型各有各的问题,到底哪一个模型好呢?实际应用中Twitter和Facebook使用的是Pull模型,Instagram使用Pull和Push结合的模型,Pull模型相对于Push模型的好处有:逻辑比较简单,实现起来比较容易;上帝视角的问题较Lady Gaga的风暴问题来说出现的概率很低。
当然也可以将Push和Pull模型结合起来:
Push and Pull
问题:摇摆问题,比如邓超有100k的粉丝,发了一条比较作的微博,一下子掉了好几十万的粉丝,不发微博又涨了几十万粉丝,这样处于中间不停的摇摆,系统会切换来切换去,可以采取的一个策略是,对于大于100k的使用Pull模型,只有当粉丝掉到90k以下是才是用Push模型。设置一个缓冲地带,可以缓解摇摆问题带来的影响。


Storage

不管什么样的系统,本质上都是用户对数据的读取,所以存储这部分的设计比较关键。一般来说我们选择的存储类型有以下三个:

  • 关系型数据库 SQL Database:用户信息 - MySQL
  • 非关系型数据库 NoSQL Database:社交图谱 - MongoDB
  • 文件系统 File System:图片、视频 - Amazon S3

Storage


Evolve

如何加速?

加速的第一个思路就是Cache,将所有的内容都放在内存中,加速访问。
仅仅Cache一周之内访问Twitter的用户,并只Cache最新的800条Tweet。
Assumption:

  • Weekly active users: 300 million
  • Average news feed size: 80 tweets
  • Average timeline size: 500 tweets
  • Tweet size: 200B
  • Average follower : 20

Momory need:

  • Size of timeline = 300 million * 500 * 200 = 30T
  • Size of news feed = 300 million * 80 * 200 = 4.8T
  • Size of social graph = 300 million * 20 * 2 * 8 = 64G

如何节省空间?

将Tweet内容隔离出来,Timline只存Tweet的ID,这样可以去掉很多重复的Tweet。
Assumption:

  • Tweet size: 20B = userID(8)+tweetID(8)+Indicators(4)

Momory need:

  • Size of timeline = 300 million * 500 * 20 = 3T
  • Size of news feed = 300 million * 80 * 20 = 480G

参考资料:
冯沁原:How to design Feed/Chat System
东邪:Introducing System Design & News Feed System