首先推荐阅读

一：一篇文章就够打通python网络请求，scrapy爬虫，服务器，代理，各种骚操作，真的一篇就够
二：手把手用阿里云服务器搭建袜子工具，从此不再求人，内有福利（内部文章）
三：【Python实战】通过“酸酸”的骚操作，让Scrapy爬虫变得没有国界，真正的硬核为所欲为，想爬啥就爬啥

粉一波自己的小程序

image

正文

最近一段时间，铲屎官正在疯狂的充电中。从今儿开始，准备给大家来总结一下系统设计的一些问题。一方面是给自己留个学习总结，另一方面也可以帮助大家来一起攻克系统设计难题。

学了这么长时间，回过头来看，其实系统设计挺实用的。不论是在实际生产还是面试，都非常有用。学习系统设计，可以开阔思路，能够更轻松的应付实际生产中的一些疑难杂症。如果不懂系统设计，可能在一开始就没有规划好整体项目结构，导致项目后期没法维护和管理，从而有让工程流产的风险；针对面试，大家都知道一般IT岗位面试的时候，都会问一些算法，还有项目经历，一些公司也会简单的考一下面试者的系统设计，如果你事先了解过或者准备过系统设计，那么在这类问题上，你会应答如流，侃侃而谈，对公司而言，如果两个应聘者算法能力相当的基础下，系统设计问题回答优秀的同学，可能就会脱颖而出。而且，系统设计回答的好，加分是非常可观的。总而言之，系统设计其实是抽象编程思维的具象化表现。其重要程度，不言而喻。

如果你还停留在连算法题数据结构都搞不懂，那么可以抱着试试看的心态来看这篇文章，因为系统设计中，你可以结合实例来设计算法和数据结构，不过还是建议你去搞算法和数据结构；如果你的功力已经可以，那么看了铲屎官的文章可以和铲屎官一起讨论交流，大家共同进步。

闲话不多说了，下面我们就来开始这个系列的第一篇：

如果面试官问你Please Design Twitter，你该怎么回答？

在回答所有系统设计问题之前，首先要明白最关键的一步：系统设计第一个步骤就是先要澄清你的问题。

这里是错误的举动，最忌讳技术关键词大师：说一堆关键词，比如load balancer, Memcache, NodeJS, MongoDB，MySQL, Sharding, Consistent Hashing, Master Slave, HDFS, Hadoop...HR会认为只是听说过，并不是真正懂技术的人。真正懂的人，先从少的用户开始分析，然后再扩大到大的问题。

这里要明确一点：系统设计没有标准答案。系统设计是一种宏观设计。

一般来说，系统设计的评分主要有以下几个方面来决定：

• 可行性 Work solution 25%
  能不能抛出一个可以干活的解决方案

• 特定问题 Special Case 20%
  特定的问题出现能不能解决，一般是作为follow up question，系统设计尤为突出

• 分析能力Analysis 25%
  在整体交流过程中，就会有分析能力的体现。

• 权衡Tradeoff 15%
  方法A也可以，方法B也可以，没有哪个好与哪个坏，需要权衡，比如用户使用是否方便？存储是否方便？可扩展性？

• 知识储备Knowledge Base 15%

应对系统设计问题的分析方法：

• Scenario：场景，主要是询问到底Design什么东西，明确目标。Ask/Feature/DAU/QPS/Interface
• Service：当知道设计目标是什么之后，需要明确目标是一个小Feature，还是一个大系统。如果是大系统，就要想办法去拆，拆成一个个小系统。很大的System一定要拆成小的Service。有工程能力的人，一定具备把大东西拆成小东西的。解耦
• Storage：着重问的部分。 怎么存储，怎么访问。 了解数据库，了解table，了解Schema（表的结构），怎么存，存成几张表，数据和数据之间的关系是什么，有些OO Design的味道。可能会写OO Design的class。Schema/Data/SQL/NoSQL/File System。
• Scale：机器宕掉，用户变多。接受越来越多访问，宕机之后怎么损失减小。Sharding/Optimize/Special Case。

以上的分析必须是一步一步来的，不能直接跳到Scale。

Please Design Twitter

首先要询问面试官：

1. 需要设计哪些功能
2. 需要承受多大的访问量？

日活用户DAU（Daily Active Users），月活用户MAU是多少？
MAU 和 DAU，关系不是 乘30。是一个月登陆的用户而已。
知道DAU，是因为DAU可以用来计算QPS。
日活跃*每个用户平均访问次数/一天多少秒 = 150M * 60(估算的) / 86400 ~100K
峰值 Peek = Average Concurrent User * 3(估2~9合理) ~ 300K
快速增长的产品 Fast Growing: MAX Peek users in 3 months = Peek users * 2
读频率 Read QPS ~300K
写频率 Write QPS ~5K
在上面的整个过程中，重要的不是计算结果，而是计算过程。

接下来，我们得把需要设计哪些功能：
首先Enumerate，把 Twitter的功能一一列举出来。
Register/login
User Profile Display/Edit
Upload Image/Video
Search
Post/Share tweet
Timeline/ News feed
Follow/Unfollow a user

第二步：Sort：选出核心内容，因为你不可能在这么短的时间之内全部设计。
Post a tweet
Timeline
News Feed
Follow/Unfollow a user
Register/Login（每个App都有，不需要答）
这个时候，只需要回答前几条就行，Login模块人人都有，没必要说。

分析QPS有什么用：

• QPS = 100：用你的笔记本做Web服务器就好了
• QPS = 1K：用一台好一点的Web服务器差不多，需要考虑Single Point Failure，可能某个进程死锁，卡住了什么的。
• QPS = 1m：需要建设一个1000台Web服务器的集群，考虑Maintainance（某一台挂了怎么办）

QPS和Web Server/Database之间的关系：

• 一台Web Server约承受量是1k的QPS（考虑到逻辑处理时间以及数据库查询的瓶颈）
• 一台SQL Database约承受量是1k的QPS（如果JOIN和INDEX query比较多的话，这个值会更小）
• 一台NoSQL Databse（Cassandra）月承受量是10k的QPS
• 一台NoSQL Databse（Memcashed）月承受量是1M的QPS（可以算是一个缓存，在内存中走，不在磁盘走，速度快）

从数据库取数据，会被数据库的性能约束。

将大系统拆成小服务

第一步：Replay：重新过一遍每个需求，为每个需求添加一个服务。
第二部：Merge：归并相同的服务。

Service：可以认为是逻辑处理的整合，同一类问题的逻辑处理归并在一个Service中，把整个System细分为若干个小的Service。

Storage存储

Storage写好，System Design基本就答好了。

首先分析要用什么样的数据库，什么数据存在什么地方：

• 内存：有些数据，没必要持久化，可以存在内存当中，memcache
• 数据库：持久化结构化信息，比如用户信息，存在Database中。
• 文件系统：非机构化的信息，文件系统，直接存在文件系统。Amazon S3

那么，在这道设计题里面存储情况则应该为：

• 关系型数据库SQL Databse：用户信息User Table
• 非关系型数据NoSQL Databse：Tweets，Social Grouph（follows）
• 文件系统：Video，Image，Media Files

非结构化的数据放在File System；
结构化的数据放在Database里面；
丢了没关系的数据放在Cache里面。

设计News Feed（Timeline）

NewsFeed是信息整合，关注和被关注的信息整合。小信息流整合成大信息流。每个人看到的新鲜事都不一样。

Pull Model：

K路归并--在用户查看News Feed时，获取每个好友的前100条Tweets，合并出前100条News Feed。Merge K Sorted Arrays。

复杂度分析：
News Feed => 加入关注了N个好友，那么就要有N次DB Reads的时间，K路归并的时间可以忽略。
（为什么可以忽略，因为归并在内存中发生。DB的IO是3的数量级延迟。）
Post a tweet => 1次DB Write的时间

Pull模型的缺陷：N次DB Reads非常慢

伪代码如下：

getNewsFeed(request):  
    following = DB.getFollowings(use = request.user)
    news_feed = empty
    for follow in following:
        tweets = DB.getTweets(follow.to_user, 100)
        news_feed.merge(tweets)
    sort(news_feed)
    return news_feed
    
postTweet(requst, tweet):
    DB.insertTweet(request.user, tweet)
    return success

Push Model

为每个用户建一个List，来存储News Feed。
用户发布一个Tweet之后，将推文逐个发送到每个用户的News Feed Listzhong [关键词Fanout]
用户需要查看News Feed的时候，只要从改News Feed List中读取100条就可以。

复杂度分析：
News Feed => 1次DB Read
Post a tweet => N个粉丝，需要N次DB Writes。（但是后台可以异步处理，无序用户等待）
有一个News Feed Table，存储 id/owner_id/tweet_id/create_at

通过队列的形式来处理Asyn Tasks。

PushModel 缺陷：
不及时，粉丝多的话，时效性会保证不了

伪代码如下：

getNewsFeed(request):
    return DB.getNewsFeed(request.user)
    
postTweet(request, tweet_info): [异步操作]  
    tweet = DB.insertTweet(request.user, tweets_info)
    AsyncService.fanoutTweet(request.user, tweet)
    return success
    
AsyncService::fanoutTweet(user, tweet): [followers 的数目可能过大]
    follows = DB.getFollow(user)
    for follower in follows:
        DB.insertNewsFeed(tweet, follower)

Push和Pull那个好？

Facebook - Pull
Instagram - Push & Pull
Twitter - Pull

这个就体现Tradeoff能力，两个方法哪里好，哪里不好，不好的地方可否优化。
TradeOff点：用户体验很重要；僵尸粉的问题等

Scale扩展

第一步： Optimize：优化

解决Pull模型的缺陷：

• 读取数据库很慢，在用户请求的时候（用户需要等待时间）
• 在DB访问之前加入Cache，
• cache每个用户的timeline
  N次DB请求 -> N次Cache请求（N是你的关注好友个数）

Trade off：可以cache最近的1000条, Cache每个用户的News Feed：

• 没有cache news feed的用户，归并N个用户最近100条tweets，然后取出前100条
• 有cache news feed的用户：归并N个用户在某个时间段内的所有tweets

解决Push模型的缺陷：

• 浪费过多存储空间Disk：Disk is cheep
• 不活跃用户Inactive Users：粉丝排序Rank followers by weight(for example last login time)
• 粉丝数目 >> 关注数目

一切的优化：尝试现在的模型下面做最小的改动来优化：比如多加几台机器用于做Push任务机器, 对长期增长进行估计，并且估算是否值得转化模型。

Social app一般都是push，因为push简单，后来慢慢的变成pull

Push结合Pull的优化方案：

• 普通用户用Push
• 明星用户标记
• 对于明星用户，不push到news feed中
• 当用户需要的时候，取明星的Timeline中取，合并到News feed中

问题：明星定义，掉粉问题。
解决方法：定义明星是regular做的。将明星的Timeline于自己的News feed结合后展示。

什么时候用Push：
资源少；
想偷懒，代码少；
实时性要求不高；
用户发帖比较少；
双向关系，没有明星问题（比如朋友圈）

什么时候用Pull：
资源充足；
实时性要求高；
用户发帖很多；
单向好友关系，有明星问题。

剩下的其他Twitter功能设计，大家可以自己想想。以上就是这一期的系统设计总结。很杂，但是很有用，我相信很多人都没看到这里，可能一看是纯文字的，就关闭了。不过还是要给看到此处的同学一个小福利，那就是，DailyProject的地址！！里面会把每天更新的帖子都集合在一起，炒鸡方便。大概长这个样子：

image
获取方式，关注公众号『皮克啪的铲屎官』，回复『Daily』即可获取最新地址。回复『代码』，会给你极致撸码体验。

这么硬核的公众号，还不关注一波啊？

底部二维码.png