系统设计总结

如何处理一个系统面试题---基本套路：

4S分析法：Scenario场景、Service、Storage、Scale：

程序 = 算法 + 数据结构
系统 = 服务 + 数据存储

核心思想：trade-off分析，用这种设计有什么不好，有什么好

三大步骤

向面试官提问：分析功能／需求／QPS／存储容量
画图：根据分析结果设计可行方案：Service + Storage
优化：研究可能遇到的问题，怎么样scale

过程
- Scenario 场景
  - 和面试官讨论
  - 搞清楚需要设计哪些功能
  - 并分析出所设计的系统大概所需要支持的 Concurrent Users / QPS / Memory / Storage 等
- Service 服务
  - 合并需要设计功能，相似的功能整合为一个Service
- Storage 存储
  - 对每个 Service 选择合适的存储结构
  - 细化数据表单
  - 画图展示数据存储和读取的流程
- 得到一个 Work Solution 而不是 Perfect Solution
- 这个Work Solution 可以存在很多待解决的缺陷

1.Scenario ：描述使用场景，约束和假设

问清楚自己要做哪些功能
问清楚或者说清楚自己要handle多大用户量，面试官起码得给你确认这么几个信息，否则聊不下去。
- 一个是你平均每天handle多少用户
- 一个是你峰值（最多？不太精确但是形容一下）每天handle多少用户
自己把自己要算的东西都算出来:
- QPS 、存储size，不非得一口气全部算完，但是记住最基本的用户量，然后再说然后的。

分析出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 Database (Cassandra) 约承受量是 10k 的 QPS
• 一台 NoSQL Database (Memcached) 约承受量是 1M 的 QPS

2.创建设计概要

使用所有重要的组件来描绘出一个概要设计。搭架子，我的系统要干嘛，为了做这件事情，我们需要什么组件，怎么安排。这里一切最简单，保证这个东西可以work，不要有明显的优化还不做。

这里可以说出要设计哪些服务Service，比如设计一个音乐播放系统，则需要这几个服务：

User Service
Channel Service
Music Service

3.设计核心组件：Service、Storage服务和存储

将大系统划分为小服务
为每个服务选择合适的存储结构，以及设计数据库的表结构

4.Scale度量你的设计

确认和处理瓶颈以及一些限制。举例来说就是你需要下面的这些来完成拓展性的议题吗？

负载均衡
水平扩展
缓存
数据库分片

题目1：设计一个用户系统，实现功能包括注册、登陆、用户信息查询、好友关系存储：

询问需求、场景：估算QPS
设计可行解：有哪些Service 和Storage，数据流流向是怎样？
- (1) AuthService : 负责登录注册
  - 用户是如何实现登陆和保持登陆的？
    会话表Session，将session_key作为cookie返回给浏览器 => 浏览器保存cookie => 之后用户每次向服务器发送访问，都会自动带上cookie => 此时服务器会检测到请求中的cookie中的session_key，得到这个用户信息.
    数据库中存有一个Session_Table
  - Cache-Aside和Cache-Through:
    - Memcached 是一个 Cache-aside 型的 Database
    服务器分别与 DB 和 Cache 进行沟通 DB 和 Cache之间不直接沟通业界典型代表：Memcached + MySQL
    - Redis 是读写操作都很快的 Cache-through 型 Database
    服务器只和 Cache 沟通 Cache 负责 DB 去沟通，把数据持久化业界典型代表：Redis（可以理解为 Redis 里包含了一个 Cache 和一个 DB）
- (2) UserService : 负责用户信息存储与查询
- (3) FriendshipService: 负责好友关系存储
  - 怎么存？SQL vs NOSQL
  SQL一条数据以row为单位；
  NOSQL的column是动态的，可以无限大，可以随意添加；一条数据以grid为单位, row_key + column_key + value = 一条数据
  - 以Cassandra为例剖析典型的NoSQL数据结构
优化
- how to scale？
  - 单点失效：数据库sharding和replication
    - sharding:
    - 纵向切分：直接不同的表存在不同的机器上
    - 横向切分：粗暴的方法直接按照user_id % 10 进行拆分；好的方法：一致性Hash算法

题目2: 设计一个TinyURL

询问需求、场景：估算QPS （一天有24 * 60 * 60 = 86400秒）
- 询问面试官日活跃用户,假设100m
- 推算写一条TinyRUL的QPS：
  - 假设每个用户每天发0.1条带tinyUrl的微博，则100M * 0.1 / 86400 ~ 10M / 100k ~ 约等于100
  - 峰值Peak QPS: 100 * 2 ~ 200 （假设峰值大概是平时的2倍）
- 推算读一条TinyURL的QPS：
  - 假设每个用户每天点击1条带tinyUrl的微博，则100M * 1 / 86400 ~ 1k
  - 峰值Peak QPS: 2k （假设峰值大概是平时的2倍）
- 推算每天产生的TinyURL所占的存储：
  - 100M * 0.1 ~ 10M条，每条url长度100算，一共1G

可以看出来这题流量并不是很大，所以不需要考虑很多的高性能，只要设计出可行解，主要是说明出Service，是怎么存的，怎么取的.

设计可行解：有哪些Service 和Storage，数据流流向是怎样？
- (1) UrlService:
  - UrlService.encode(long_url)
  - UrlService.decode(short_url)
  - 访问端口设计：首先将长网址encode为短网址，然后用户输入这个短网址，浏览器会重定向才到decode后的真正的url
- (2) Storage数据存取：
  - SQL vs NoSQL
  • 是否需要支持 Transaction？——不需要。NoSQL +1
  • 是否需要丰富的 SQL Query？——不需要。NoSQL +1
  • 是否想偷懒？——Tiny URL 需要写的代码并不复杂。NoSQL+1
  • 对QPS的要求有多高？—— 经计算，2k QPS并不高，而且2k读可以用Cache，写很少。SQL +1
  • 对Scalability的要求有多高？—— 存储和QPS要求都不高，单机都可以搞定。SQL+1
  • 是否需要Sequential ID？—— 取决于你的算法是什么
- (3) long2short hash算法：
  - 算法1: 进制转换：Base62,根据数据库的自增id来, 将这个整数id转化成6位的62进制的数(0-9, a-z, A-Z)
  - 算法2: 随机生成: 随机生成一个6位的shortURL,在数据库查一遍，如果没用过，则使用；
优化：
(1）缓存memchache：
(2) sharding
知识点：

一致性Hash算法
- 在横向扩展时，减少数据的移动
- 原理：
  - 一个简单的一致性Hash算法：
  • 将 key 模一个很大的数，比如 360
  • 将 360 分配给 n 台机器，每个机器负责一段区间
  • 区间分配信息记录为一张表存在 Web Server 上
  • 新加一台机器的时候，在表中选择一个位置插入，匀走相邻两台机器的一部分数据
  - Consistent Hashing —— 更实用的方法 :
    思想：就是将机器看成1000个虚拟节点，利用key的hash值找key在的机器
    具体算法：
    
    • 将整个 Hash 区间看做环
    • 这个环的大小从 0~359 变为 0~2 64 -1
    • 将机器和数据都看做环上的点
    • 引入 Micro shards / Virtual nodes 的概念
    - • 一台实体机器对应 1000 个虚拟点 Micro shards / Virtual nodes
    • 每个 virtual node 对应 Hash 环上的一个点
    • 每新加入一台机器，就在环上随机撒 1000 个点作为 virtual nodes
    • 需要计算某个 key 所在服务器时
    - • 计算该key的hash值——得到0~2 64 -1的一个数，对应环上一个点
      • 顺时针找到第一个virtual node
      • 该virtual node 所在机器就是该key所在的数据库服务器
    • 新加入一台机器做数据迁移时
    - • 1000 个 virtual nodes 各自向顺时针的一个 virtual node 要数据
数据库备份 -- Replica 数据备份
- Replica
  • 是实时的，在数据写入的时候，就会以复制品的形式存为多份
  • 当数据丢失的时候，可以马上通过其他的复制品恢复
  • Replica 用作在线的数据服务，分摊读
- MySQL Replica
Master-Slave模式：Master 负责写，Slave负责读

题目3：设计一个推特

询问需求、场景：
- (1) 估算QPS
  - 日活用户:150M，每个用户每天平均请求次数：60，则QPS = 150M * 60 / 86400 ~ 100k
  - 峰值Peak = 100k * 3 ~ 300k
  - 读频率：300k
  - 写频率：5k
- (2) 设计功能
  - Post / Share a tweet
  - Timeline / News Feed
  - Follow / Unfollow a user
  - Register / Login
  - User Profile Display / Edit
设计可行解：有哪些Service 和Storage，数据流流向是怎样？将大系统拆分为小服务
- (1) Service
  - User Service
  - Tweet Service
  - Media Service
  - Friendship Service
- (2) Storage
  - Pull Model: 获得每个关注对象发的推特，然后在内存中merge
    复杂度：O(N) N为关注的好友，为N次DB Reads时间
    - 缺点：查询O(N)哥个关注对象的过程是阻塞的，会非常慢
  - Push Model: 为每个用户见一个news feed list，用户发一个帖子时，将帖子推送到关注该用户的news feed list中；关键词： Fanout；所以那个用户get的时候直接从news feed list中取就行了，不用再查数据库了；
    - 优点：可以将Post tweet到news feed list中的过程变为异步的：不再用户发帖的过程中执行，无需用户等待；
    - 缺点：不及时，fanout执行可能带来延迟，
    - 数据表设计：News Feed Table
```
id、owner_id、tweet_id、created_time
```
    - push模型系统结构图：
优化
- (1)加Cache：最慢的部分发生在用户读请求时（需要耗费用户等待时间）,在 DB 访问之前加入Cache :Cache 每个用户的 Timeline

系统设计总结

如何处理一个系统面试题---基本套路：

1.Scenario ： 描述使用场景，约束和假设

2.创建设计概要

3.设计核心组件：Service、Storage服务和存储

4.Scale度量你的设计

题目1： 设计一个用户系统，实现功能包括注册、登陆、用户信息查询、好友关系存储：

题目2: 设计一个TinyURL

一致性Hash算法

数据库备份 -- Replica 数据备份

题目3： 设计一个推特

1.Scenario ：描述使用场景，约束和假设

题目1：设计一个用户系统，实现功能包括注册、登陆、用户信息查询、好友关系存储：

题目3：设计一个推特