System Design Class 1

Class 1:

Macro Design，宏观设计方式：

Crack a design in 5 steps:  "SNAKE"模式

1. Scenario: case / interface 场景 需求分析
   1. 枚举所有的需求
   2. 对所有的需求排序
2. Necessary: constrain / hypothesis 限制：用户、流量、内存
   1. 询问日访问量users (一般公司 100w，google 或者 facebook 可以上1000w 或者 上亿)
   2. 预测同时在线用户量，一般users / 5
   3. 预测高峰在线用户量，一般users * 3
   4. 可扩展性 预测三个月以后的日访问量，一般users * 10
   5. 流量的预测
   1. 请求频率 比如 1 message  / min
   2. 每次请求的流量大小 一首歌可能是3 Mb，facebook的话可以用浏览器调试工具来ka
   3.  峰值流量 = 用户在线峰值 * 3Mb * 1 / 60 = *** Mb / s
   6. 内存的预测
3. Application: service / algorithm
   1. Replay the case, add a service for each request
   2. merge the services: （比如豆瓣fm可以把 用户登录(user service) 频道请求(channel service) 播放请求(music service) 三个服务给合并）
4. Kilobit: data 选择合适的存储方式
   1. 把每个服务和数据集对应
   2. 选择合适的数据集：这里user service因为添加固定，修改和删除都很少，所以可以用mysql存储；channel service列表数量很多可以用MongoDB；music service 可以直接用文件(File)
   3. 附加阅读：
      • https://www.zhihu.com/question/23602133
      • https://www.zhihu.com/question/20059632
5. Evolve
   1. Analyze
      1. 把constrain提高，比如提供400Gb/s 怎么保障
      2. 新功能开发
      3. 内容更详细，比如用户想要注册登录注销屏蔽等功能
      4. 性能提升
      5. 鲁棒性，应急方案，比如服务器挂了怎么办，比如没有双机备份怎么办。
   2. 然后根据反馈再 具体进行改进。

Micro Design：微观设计模型：

1. 具体细节模块设计：
用户推荐模型：设计一个用户听歌的推荐系统：

已知：每个用户都有自己喜欢的歌曲,比如 u1:{m1,m2,m3}; u2:{m1,m2,m3,m4,m5,m6,m7} 那么就有三首歌的相似度

求：找出相似度最高的用户：

1. 设计出一个接口。class Recommender { public int findSimilarUser(int UserID); }
2. 考虑性能问题。一秒要进行多少次运算。
1. 比如高峰在线用户量 Up , 假设6,000,000
2. 假设我们每十分钟对一个用户进行一次相似用户推荐。
3. 考虑 参与比 ：我们只需要对登录的用户进行推荐。也就是我们Up中并不是所有都是登录的用户。我们假设其中5%的是登录的，也就是需要进行用户推荐的那部分。
4. 预测QPS(Query pre second)： QPS = 6,000,000 * 5% / 10 / 60 = 500 次/s
3. 算法实现。
   

    算法：倒排索引 (Inverted index)

    tip: 一般在实际情况中O(n^3) 可以估成秒级别，O(n^2)百毫秒级别， O(n)十毫秒级别，O(1)毫秒级别
附加阅读:

• https://www.ibm.com/developerworks/cn/web/1103_zhaoct_recommstudy1/
• http://blog.csdn.net/hguisu/article/details/7962350

2. 提高scalability
根据预测的QPS是500，然而优化过的单个设计直邮50qps。这个并不是说要10台这样的机器来做运算。这里的瓶颈并不是磁盘IO，而是CPU运算。所以可以由多线程解决。比如一个10核或者8核的机器就能满足需求。

3. 最后架构图

• 这里并不需要把这五部分分别放在五台机器上。完全可以放在同一台物理机上。今后扩展可以放在多机。中间的dispatcher其实应该也有多个备份，防止down。
• Dispatcher 相当于一个message queue，负责各个部分相互通信。
• Recommender 和 Database 之间靠socket长链接，比如Mysql 链接。
• 各个服务之间向Logger，发送心跳信号。来知道对方是否正常。

系统瓶颈：
1. Dispatcher 如果这个挂了，整个系统全down了。
2. Web Service 如果挂了，用户也无法访问了。

4. 代码实现
可能会考察，用生产者消费者线程安全的实现一个Dispatcher。