0. System Design Basics
单位换算表
2.5 million seconds per month
86400 seconds per day
1B = 8 bit byte
1KB = 1000bytes Kilobyte
1MB = 1000KB Megabyte //百万字节 兆
1GB = 1000MB Gigabyte //亿字节,又称“千兆”
1TB = 1000GB Terabyte //万亿字节,太字节
1PB = 1000TB Petabyte // 千万亿字节,拍字节
1EB = 1000PB Exabyte //百亿亿字节,艾字节
...
1GB = 10^9 bytes
Estimation 估算
搜集需求
大家都知道,系统设计的第一步是搜集需求,所以本文也不对收集需求做太多的介绍。系统设计很多时候题目都是模糊的,即使同一个题目(比如设计 timeline 时间线),不同的面试官考察的侧重点也可能不同,所以一定要花时间和面试官讨论设计的系统具体要支持哪些功能。
搜集需求的过程一般是从最常见的,使用最频繁的功能开始说,然后发散到其他辅助型的功能,也不能过于详细,比如说面试官需要你支持登录功能,一般情况下就不需要再发散下去问要不要记住登录状态功能。
在搜集完需求之后,我们就需要通过适当的估算来给系统定性,并且通过数据来支持设计决定,为后面的设计指明方向,下面就介绍一些常见的数据估算方法和常用的数字。
Numbers Everyone Should Know
在总结数据估算方法之前,先附上一些重要的数字,这是Jeff Dean 在他的演讲中首次提到的,也是目前网上被引用最多的数据之一。
L1 cache reference | 0.5 ns |
---|---|
Branch mispredict | 5 ns |
L2 cache reference | 7 ns ~14x L1 cache |
Mutex lock/unlock | 25 ns |
Main memory reference | 100 ns ~20x L2 cache, 200x L1 cache |
Compress 1K bytes with Zippy | 3,000 ns = 3 us |
Send 1K bytes over 1 Gbps network | 10,000 ns = 10 us |
Read 4K randomly from SSD* | 150,000 ns = 150 us ~1GB/sec SSD |
Read 1 MB sequentially from memory | 250,000 ns = 250 us |
Round trip within same datacenter | 500,000 ns = 500 us |
Read 1 MB sequentially from SSD* | 1,000,000 ns = 1,000 us = 1 ms ~1GB/sec SSD, 4X memory |
Disk seek | 10,000,000 ns = 10,000 us =10ms ~20x datacenter roundtrip |
Read 1 MB sequentially from disk | 20,000,000 ns = 20,000 us = 20 ms ~80x memory, 20X SSD |
Send packet CA->Netherlands->CA | 150,000,000 ns = 150,000 us = 150 ms |
1 ns = 10^-9 seconds
1 us = 10^-6 seconds = 1,000 ns
1 ms = 10^-3 seconds = 1,000 us = 1,000,000 ns
1 ms = 10^-3 seconds = 1,000 us = 1,000,000 ns
常见估算
我认为系统设计中一般有两种估算,一种是从这个系统的角度来做估算,比如计算你系统的 QPS,数据库的 QPS,通过估算这些数据,你可以大致知道你需要多少台机器,选择怎样的数据库等等。还 有一种估算是细节的估算,比如说系统要求某项服务延时小于 100ms,这时候可能就需要用到上面的数据,计算数据传输,读取分别需要多少时间,通过这样的估算同样也可以帮助你做出正确的选择。
估算的结果不需特别精确,只要数量级正确即可,比如使用到 2^10 (1024)的时候,为了计算方便可以用 1000 来计算。比如算 QPS 的时候要算 24*60*60 = 86400,你用 80k 或者 100k 都是可以的。
对于第一种估算方式,我们以 QPS 为例做一个简单的讲解,有的时候面试官不会直接说你算算 QPS 是多少,而是会从侧面来说假设我们有 X 个用户,你能告诉我需要多少台机器?
题目: 设计一个类似 twitter 或者 facebook 的 newsfeed/timeline ,假设 100M 日活用户(DAU),估算 QPS
- 100M DAU, 根据 80-20 法则,我们假设 20%的人会发帖,那就是 20M 的帖子
- 如果 20M 的帖子是平均在 24 小时之内发的,QPS = 20M / 24*60*60, 大约 200 QPS
- 但是我们都知道发帖时间分布是不均匀的,比如今晚有比赛,比赛那个期间发帖会高很多,峰值可能是 5 倍,1k peak QPS。(5 倍的数字是随便说的,说 10 倍也行,但是不要太离谱说个 1000 倍),所以写入的 QPS 大致为几百到一千
- 100M 的用户假设平均每天刷一次脸书/推特,那就是 100M 的读请求(其实很多时候每个读请求背后会有更多的读请求来聚合信息,这里我们就不做具体计算),QPS = 100M / 24*60*60, 大约 1k QPS,和写同理,读也有高峰时段,算 5k QPS
- 综上所述,我们发现系统读的请求比写的请求多。
通过这样的计算,可以很好地了解系统的特性,比如上面例子给出的时间线系统,就是一个读多写少的的系统。在系统设计面试中,搜集完需求然后判断系统特性是最重要的一步,之后才能根据系统的特性做更深入, 如果这一步判断错误,那就是刚出发就走错了方向,后面讲的再好也于事无补了。在你出现方向性的错误的时候,一般面试官会暗示你,让你重新思考某个环节是不是真的如你所想,这种时候就要顺着面试官的思路再思考一遍,然后做出判断(以防面试官故意误导)。
第二种是细节的估算,Jeff Dean 的演讲中也给出了例子。
How long to generate image results page (30 thumbnails)?
Design 1: Read serially, thumbnail 256K images on the fly
30 seeks * 10 ms/seek + 30 * 256K / 30 MB/s = 560 ms
Design 2: Issue reads in parallel:
10 ms/seek + 256K read / 30 MB/s = 18 ms (Ignores variance, so really more like 30-60 ms, probably)
但是无论是哪一种估算,它们都是为了做设计决定而服务的,千万不要本末倒置。网络上一些教程常常说系统设计第一步就是收集需求估算 QPS,导致某些面试者在面试的时候收集完需求就就各种计算,写了一白板的各种数字,其实有时候面试官根本不在意这些数字,他们只是想让你先大致画出一个架构,支持两三个人用就好,这样给面试官留下的第一印象就不是很好了。
所以我个人的建议是面试者在面试的时候还是看碟下菜,先问清楚设计的系统要多大规模,如果得到的回答是没事这个先不管,你就别做计算。如果得到的回答是用户很多,我的建议是不要一下把所有东西都算了,**刚开始可以做一个简单的计算,判断系统的某些特性,比如是读多还是写多(read heavy/write heavy),以便确定设计的大方向。**剩下的具体的计算可以再画架构的时候 再完成,然后根据计算结果作出决定(譬如每个请求 request 都会导致 5 次数据库读写,service QPS 是 10k,数据库是 50k,考虑到我们存的是非结构化数据,又有 50k 的 QPS,所以我们使用 NoSQL 比较好),这样体现出你在每一步设计都考虑到了 scalebility,通过计算来证明你的设计决定是正确的。
其他数字
还有一些其他的数字,属于江湖经验,很多数字受具体情况和系统性能影响变化比较大,所以在这里给出来做一些参考,了解一下数量级和快慢,请不要把他们当做标准数字。
- 缓存 Cache 的 QPS(例如 Memcache)可以有数十万,计算是可以使用 100k,缓存(分布式缓存)单机响应时间很快,一般小于 10ms
- NoSQL 的 QPS 大概在几万左右,计算的时候使用 10k
- 用 SQL 去取数据一般要几百毫秒,完全取决于表怎么设计,索引,SQL Query 写的好不好等等,做的不好几秒也有可能,优化得很好几十毫秒也能达到,一般来说取 200ms 是合理的。SQL 单台机器 QPS 一般在几千左右,计算的时候可以用 1k/5k
- 单机端口 Http Port 数量 65535
- 一般单机服务器,比如 Tomcat,性能比较好的 QPS 可以达到 5k
概念
QPS & TPS
- QPS(Query Per Second) :服务器每秒可以执行的查询次数
- TPS(Transaction Per Second) :服务器每秒处理的事务数(这里的一个事务可以理解为客户发出请求到收到服务器的过程)
吞吐量
吞吐量指的是系统单位时间内系统处理的请求数量。
一个系统的吞吐量与请求对系统的资源消耗等紧密关联。请求对系统资源消耗越多,系统吞吐能力越低,反之则越高。 TPS、QPS 都是吞吐量的常用量化指标。
- QPS(TPS) = 并发数/平均响应时间(RT)
- 并发数 = QPS * 平均响应时间(RT)
系统活跃度
- PV (Page View)
- UV (Unique Visitor)
- DAU (Daily Active User)
- MAU (monthly active users)
Content delivery network (CDN)
内容分发网络(CDN)是一个全球性的代理服务器分布式网络
A content delivery network (CDN) is a globally distributed network of proxy servers, serving content from locations closer to the user. Generally, static files such as HTML/CSS/JS, photos, and videos are served from CDN, although some CDNs such as Amazon's CloudFront support dynamic content. The site's DNS resolution will tell clients which server to contact.
Serving content from CDNs can significantly improve performance in two ways:
- Users receive content from data centers close to them
- Your servers do not have to serve requests that the CDN fulfills
Speed of Storage and Network
IOPS 每秒读写次数 | Latency | Throughput | Capacity | |
---|---|---|---|---|
Memory 内存 | 10M | 100ns | 10GB/s | 100GB |
Flash 闪存 | 100K | 10us | 1GB/s | 1TB |
Hard Drive 硬盘 | 100 | 10ms | 100MB/s | 1TB |
Rack | Data Center | Long distance | |
---|---|---|---|
P99 Latency | <1ms | 1ms | 100ms+ |
Bandwidth | 1GB/s | 100MB/s | 10MB/s- |