[OOD] 系统设计 (1)
评分标准
可行解 Work Solution
15%
特定问题 Special Case
20%
分析能力 Analysis
25%
权衡 Trade-off
15%
知识储备 Knowledge
25%
SNAKE分析法
Scenario
哪些功能？Feature/Interface?
Needs
多强的系统？Constrains/Hypothesis/QPS/DAU
Application
主要组成模块？Service/Module
Kilobyte
如何存储数据和访问？Data/Storage/SQL vs. NoSQL/File System/Schema
Evolve
如何进化，解决缺陷，处理问题？Optimize/Special Case
Design a Twitter -- 例子
Scenario
Step 1 -- Enumerate 罗列功能
Register/Login
User Profile Display/Edit
Upload Image/Video
Search
Post/Share a tweet
Timeline/News Feed
Follow/Unfollow a user
Step 2 -- Sort 选出核心功能
Post a tweet
Timeline
News Feed
Follow/Unfollow
Register/Login
Needs
Step 1 -- Ask
DAU -- Daily Active Users -- 日活跃用户数量 -- 评价系统牛逼的标准
Twitter: MAU 320M, DAU ~150M+
Read More: http://bit.ly/1Knl0M7
Step 2 -- Predict
Concurrent Users -- 并发用户
Avg Concurrent Users = 日活跃用户数量 每个用户平均请求次数 / 一天多少秒 = 150M 60 / 86400 ~= 100k
峰值：Peak Users = Avg Concurrent Users * 3 ~ 300k
快速增长的产品：Fast Growing = Peak Users * 2 ~ 600k
Read QPS(Queries Per Second) 读频率：300k
Write QPS(Queries Per Second) 写频率：5k
Application -- Service/Module
Receptionist
User Service: Register/Login
Tweet Service: Post a tweet/News Feed/Timeline
Media Service: Upload Picture/Video
Friendship Service: Follow/Unfollow
Replay -- 重放需求
Merge -- 归并需求
Kilobyte -- Data/Storage
基本知识
关系型数据库 SQL Database：User Table
非关系型数据库 NoSQL Database：Tweets, Social Graph (Followers)
文件系统 File System: Images, Videos, other media files
程序 = 算法 + 数据结构
系统 = 服务 + 数据存储
User Service: SQL
Tweet Service: NoSQL
Media Service: File System
Friendship Service: SQL/NoSQL
Select
- 为每个App/Service选择合适的存储结构
Schema
- 细化Database结构
Please Design Schema
User Table
userId
integer
username
varchar
email
varchar
password
varchar
Friendship Table
relationshipId
integer
from_userId
foreign key
to_userId
foreign key
Tweet Table
tweetId
integer
userId
foreign key
time
timestamp
content
text
News Feed 如何存取？
Pull vs. Push
Pull Model
- 获取每个好友的前k条tweets，合并出k条news feed
K路归并算法：Merge K sorted arrays
- 假设有N个好友，则时间为 ==>
N次DB Read的时间 + K路归并时间（可忽略）
- Post a tweet ==>
1次DB Write的时间
Pull Work Flow 原理图
Client ---->send get News Feed request to----> Server
Server Following from----> Friendship Table
Server Tweets of Followings from----> Tweet Table
Server ---->Merge Tweets and return to----> Client
Pull模型的缺陷
读取慢（N次DB Reads，非常慢）
发生在用户获得News Feed的请求过程中，有延迟
Push Model
算法
为每个用户建一个List存储他的News Feed；
当他post一个tweet的时候，将该推文逐个推送（Fanout）到每个Follower的List中；
当他查看News Feed时，从List中读取最新的100条即可
复杂度
每次News Feed，只用一次DB Read；
每次Post Tweet，会Fanout到N个Follower，需要N次DB Writes；
不过对于Post Tweet，可以用异步任务后台执行，用户无须等待
postTweet(POST, tweet_info) { tweet = DB.insertTweet(userId, tweet_info); //userId对应这个用户的News Feed List AsyncService.fanoutTweet(userId, tweet); return success;}AsyncService::fanoutTweet(userId, tweet) { followers = DB.getFollowers(userId); for (follower: followers) { DB.insertNewsFeed(follower.userId, tweet); }}Push Model的缺陷
postTweet()的异步执行；而fanoutTweet()可能遇到followers数目太大的问题。
Push和Pull的比较
Facebook
Pull
Twitter
Pull
Instagram
Pull + Push
Evolve 优化：Optimize/Maintenance
Step 1: Optimize
Solve Problems: Push vs. Pull; Normalize vs. De-normalize
More Features: Edit; Delete; Media; Ads
Special Cases: 大V，热推，不活跃用户
Step 2: Maintenance
Robust 鲁棒性：如果有一台server/DB挂了怎么处理
Scalability 扩展性：如果有流量暴增，如何扩展
解决Pull的缺陷 DB Reads
在访问DB之前加入Cache；
Cache每个用户的Timeline
N次DB Reads，所以Cache最近的100条
- Cache每个用户的News Feed
最近没有Cache过News Feed的用户：归并N个好友每人最近的100条Tweets，取出前100条；
- 最近Cache过的用户：归并某个时间戳之后的tweets
解决Push的缺陷
- 浪费更多Disk存储空间
与Pull模型存在Memory中相比，虽然Disk很便宜
其实对于实时性要求而言，Push的效果不如Pull
所以对于不活跃用户，可以采用粉丝排序
follower数目远大于following数目时，加几台push任务的机器
如果加server无法解决：针对长期的fast growing，进行评估，转换push模型为pull模型
Tradeoff：对于明星用户，采用pull；对于普通用户，采用push；
关键字：ood, pull, tweet, feed
版权声明
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符，请点击 举报 进行投诉反馈！
