https://wizardforcel.gitbooks.io/gainlo-interview-guide/content/sd1.html

https://github.com/checkcheckzz/system-design-interview 有很多别的公司的博客

百万用户？

数据库多副本读。副本下限的应对措施？发现问题快速扩节点

水平扩容问题。可能需要DHT

另外明星可能有热点问题。需要做特殊处理

CDN cache。不多说。无状态。拉数据。尽可能的扩

估算 BACK-OF-THE-ENVELOPE ESTIMATION

大小

2 ** 10 -> 1KB

2 ** 20 -> 1MB

2 ** 30 -> 1GB

2 ** 40 -> 1TB

2 ** 50 -> 1PB

延迟 2020-ver

L1 cache reference 1ns

branch mispredict 3ns

L2 cache reference 4ns

mutex lock/unlock 17ns

main memory reference 100ns

compress 1k 2000ns - 2us

send 2KB 44ns

SSD 随机读 16us

SSD 顺序读 3us

Data center round trip 500us

硬盘随机读 seek 2ms

硬盘顺序读 800us

SLA

99% 一天15分钟不可用，一年3.65天不可用

99.9% 一天1.5分钟不可用，一年9小时不可用

99.99% 一天8.6秒不可用，一年53分钟不可用

99.999% 一天866毫秒不可用，一年五分钟不可用

一个估算的例子，推特，每个月三亿万活跃用户，50%的用户天天用，平均每个用户两个帖子，10%的帖子包含媒体文件，数据保存五年。估算存储使用

DAU就是150万，qps怎么算 15000W * 2 * 24小时/3600秒 = 3500，最多就7000

推特假设就按照kv来存，key 是64 int id，value可以是140B的文字或者1M的媒体文件

媒体文件那就是15000W * 2 * 10% * 1MB=30TB，每天。五年那就是* 365 * 5 55PB

限流器 rate limiter

客户端没法控制。很难控制api怎么使用，毕竟目的不同

服务端需要考虑这个限流器的规模，是不是全局作用域，以及异常处理

放在服务端可以作为一个中间件来做，放在gateway，也可以做成服务的一个插件

限流算法 这里有个总结非常不错 https://segmentfault.com/a/1190000041548601

  • 令牌桶。不同api/ip/等等分类条件设置不同桶大小。还是很好控制的 主要两个参数，桶大小和token使用速率。这个速率
    • 优点就是实现简单，内存使用不大，也能顶住大量请求，缺点就是这个桶大小和token使用速率怎么调整？更好的适应业务
  • 漏桶，就是FIFO队列，按照固定速率消费。FIFO + batch的感觉。也是两个参数，桶大小和消费速度
    • 优点就是对于后端服务，请求时一直稳定的，也不怎么占用内存。缺点就是参数不好调，以及FIFO导致了请求产生了顺序，有些后来的如果正好遇到队列半满导致排队，可能就影响了延迟
  • 固定窗口计数。把时间分片，每个分片一个计数器。分片内超了指标就拒绝，也就是从根上就做好了稳定速率的效果
    • 优点就是稳定，缺点就是请求暴增的突刺会被完全削峰，失败率上天了，窗口分片的边的请求突刺可能造成请求没完全拦截住，放出去多的请求。
  • 滑动窗口日志，上面的改良。一个窗口，开始时间结尾时间保存好。新的来了就加进来，整个窗口，如果超了就拒绝新的加。加新的同时，旧的过期了(低于窗口的旧的)要淘汰。感觉就是个时间边界控制的FIFO队列 time-bounded fifo queue
    • 时间戳要一直存。占用恐怖
  • 滑动窗口计数。窗口定时移动一下。和固定窗口计数一样的问题。

这里看来看去还是令牌桶顺眼

怎么实现？用数据库夸张了。redis简单的incr expire就可以实现 限流的规则是什么？一个例子

domain: auth descriptors:
- key: auth_type 
- Value: login 
- rate_limit:
    unit: minute 
    requests_per_unit: 5

如果是http，请求太多直接429

分布式限流器怎么做？主要就是竞争问题。上锁明显太慢，redis上如何处理？用zset，zcard判定个数是否超标，时间戳排序就行了。

https://gist.github.com/ptarjan/e38f45f2dfe601419ca3af937fff574d#request-rate-limiter

这种玩法前提是redis快。本来redis也是当cache用，没啥毛病。限流器本身也不是什么重要数据

监控你的rate limiter

这里讨论的是http角度的rate limiter，发散一下？其他角度的ratelimiter？

当然，傻逼客户端别瞎几把用也是也个好建议， 客户端cache，客户端降低调用频率，客户端改善重试策略

一致性HASH设计

hash环。然后节点是range还是slot？要最小化，方便迁移

热点key问题如何处理？让key尽可能均匀

设计kv存储？

这个就不说了。

ID生成器

UUID还是时间相关？时间相关是不是要考虑NTP？

snowflake算法？ticket server？

感觉很多相关资料。这里放个TODO

短网址系统

  • 简单思路 hash，如果长度为 7，包含[A-Z, a-z, 0-9]，则可以提供62 ^ 7 ~= 3500 亿个 URL。一般的长度也就5/6，够用了
  • 考虑数据插入效率 -> 数据库基于hash做分片就行了。hash冲突处理（甚至可以不处理）
  • 分发问题

网页爬虫

  • 过滤不想要的
  • 大部分网页是重复的，hash去重
  • 下载可能需要大规模无状态下载小服务
  • 一些对抗措施

这个其实是个糙活

推送通知系统/邮件系统

其实和后端服务没啥区别，几个特别注意的点

  • 推送别太频繁，不然用户可能直接取消订阅/关了，要有个限流
  • 重试机制。单点故障容易导致用户丢失信息。要有整个流程ack，用户真正的消费到
  • 整个流程监控

消息流/推特

感觉和上面的差不太多？？

fan-out设计？信息是在加载的时候分发还是一开始就分发。一开始就分发，优点就是直白，缺点就是如果是朋友关系链大的，比如大V，很费时间，比如僵尸粉太多的，这种简直就是浪费CPU 拉取的时候做过滤就简单的多。毕竟很多用户使用时间错开，还有很多僵尸用户，用户拉取的时候再过滤分发，就减轻了很多CPU压力，但是加载会慢，但是省，就避免了前面的大V热key问题

这俩就是料理包和现做菜的区别。料理包，如果大量搞，浪费，但是直接。现做菜，如果客人要多菜多，慢，这个比方我觉得挺直白

数据存储问题。用户的信息要有个postid -content对应。要有个postid-userid对应，用来表达发送消息

cache。很多很多cache，要cache内容，要cache id对应关系，多种kv映射

这里也有类似的介绍 https://wizardforcel.gitbooks.io/gainlo-interview-guide/content/sd8.html

聊天系统

私聊/小群组/在线/多终端/推送通知

如何实现

肯定不是直连的。有个chat server接受服务

  • 拿到消息以及通知的对端
    • 在线就发，不在线就存下来等上线再发
      • 要有个信号通知机制/订阅机制/推送机制 总之是一个玩意儿
    • 问题，如何拿到新的返回的消息？最快收到对方的应答？
      • 轮训？短连接/长连接？websocket？ws更简单一些

消息定义

  • message_id - message_from - message_to - content - create_at 还是比较简单的
  • 如果是群聊，就是这样 channel_id message_id user_id content create_at
  • 然后就是交换message id 消费message id了。没啥说的
    • 问题： 下线后的消息分发处理，这个场景和上面的消息流/推特的场景是相同的，提前准备好还是离线用户上线再准备消息的区别，一个浪费资源一个相应慢，看这个人是不是有大量好友收发消息

实际上，这种用户应该走一遍图分析，大量聊天交互的用户，诈骗/招嫖的/HR招聘都有可能。值得分析一波

其他问题

  • 媒体文件怎么搞？
  • 客户端缓存消息数据
  • 端到端加密？用户数据安全，比如一键删除所有数据
  • 加载时间
  • 错误处理。服务掉线影响客户端，服务发现要稳定，要立即切换
  • 消息重发

还是有挺多细节的

搜索引擎提示补全？trending？

实际上就是一个前缀查匹配最热的搜索结果

要求

  • 最快响应
  • 强相关（前缀查肯定相关，也有可能不前缀查？？）
  • 结果排序
  • 高可用
  • 扩容能力，要能扛得住大流量搜索

数据简单估算

一千万DAU，每个人搜十次，也就是一个亿，每次搜20个字节的ascii

简单算一下qps

10 000 000 * 10 * 20 / 24 / 36000 两万四，顶天48000

假设20%的搜索是新的，那也就是说每天增加 10 000 000 * 10 * 20 * 20% = 0.4G

简单说，两个服务，一个数据采集，一个查询

数据采集要存一个倒排，内容-查询次数

查询就搜相关字符串的查询次数最高的

这个问题就变成了根据结果构造trie以及维护/分发trie的问题

问题

  • 数据库不适合构建这种数据模型。这种前缀类型数据用trie保存合适，但是每个子树更新频率？复杂。解决方案可能就是加cache cache一下trie树

周期性收集数据构造trie树，trending也是同样的套路

youtube？netflix？

youtube为例子

简单估计

两亿月活

五亿日播放量

五千万创作者

2019年广告收入15亿万美元

咱们退化一下

5百万日活 DAU

每个用户看五个视频

10%的用户每天传一个视频

每个文件300MB，也就是说每天数据增长150T

考虑CDN成本

美国的CDN，CF，每GB 2美分

看视频，5百万 * 5个 * 0.3G * 0.02 每天15万美元。这么玩不得亏死？

视频上传相关技术？编解码？优化上传？好多技术细节。数据DRM？

错误处理也有很多细节

上传失败？编码失败？

其他推流相关，上面有些重复了

云盘？

简单估算 五千万用户，一千万日活，每人10G，每人每天传两个文件，每个文件500K

总空间500PB，qps也就500

实现简单，就是webserver，提供上传下载借口就行

数据库记录用户信息，给个id，根据id找目录，文件要存hash，方便同步校验冲突

文件做不做压缩？支不支持在线预览？

多客户端修改可以退化成聊天系统的同步问题

上传也可以走视频网站上传那个方案的优化，拆分

实际上存储大概率是S3这种磁盘，问题就退化成S3设计？