how to understand back-of-the-envelope estimation
how to calculate the storage and bandwidth? 一文搞懂系统面试中的性能估算
how much storage, machines, what scale is expected from the system?
1 B = 8 bits
1 KB = 1024 b
1 mB = 1024 KB
1 gB = 1024 mB
k * k = m
k * m = g
1 million / day = 12 / sec
1 million / day = 700 / min
1 million / day = 4200 / hour
1. twitter
- 3 billion monthly active users
- 50% of them would use twitter everyday
- everyone post 2 times per day
- 10% of the posts contains images or videos
- store data for five years
estimate
1.1 QPS(Query per second)
- DAU (daily active user) 300 million * 50% = 150 million
- Tweets QPS = 150 million * 2 tweets/ 24 hours/ 3600s = ~3500
- max QPS = QPS * 2 = ~7000
1.2 media starage estimate
- average post size: Id: 65 byte, post: 140 bytes, media: 1MB
- media size: 150 million * 2 * 10% = 30 TB/day
- 5 years storage: 30TB * 356 * 5 = ~55 PB
2. twitter
- 600 million users
- DAU: 200 million
- 25% post 2 times per day
- 200 * 25% * 2 = 100 million new tweets per day
- views per day: one user views 100 posts per day: 200 million * 100 = 20 B views per day
- 1 / 20 will have an image associated with it: 200 KB
- 1 / 100 will have a video associated with it: 2 MB
2.1 Storage Estimate
-
100 characters per tweet on the average
-
2 bytes per characters
- 200 bytes + 50 bytes(userId or the other data) = 250 bytes
- tweet text data = 100 million * 250 = 25000 million = 25 GB / day
- Image + Video = 100 million * 200 KB / 20 + 100 million * 2 * 1000 / 100 = 3 TB / day
- total final storage: 25 GB + 3 TB = ~ 3 TB
2.2 Bandwidth Estimate
-
Incoming to server = 3 TB ~= 23 MB / sec
-
outgoing text tweet data = 20 B * 250 bytess ~= 60 MB / sec
-
outgoing image data ~= 2.5 GB / sec
2. high level design
- draw
- components and connection
- jusity the idea
3. design core componets
4. scale the design,potential solutions and trade-offs
- identify and address bottlenecks
- load balancer
- horizontal scaling
- caching
- database sharding
5. scale
basic concept
延迟(Latency) : 通过管道需要花费的时间
带宽(Bandwidth) : 管道的宽度
吞吐(Throughput) : 每秒钟流过的水的数量就是吞吐
scalability
- Vertical scaling
MySQL
- Horizontal scaling Horizontal scaling (aka scaling out) refers to adding additional nodes or machines to your infrastructure to cope with new demands.
Cassandra, MongoDB
- Load balancing
- Database replication
- Database partitioning
- Clones
- Databases
- Caches
- Asynchronism
Performance vs scalability
Latency vs throughput
maximal throughput with acceptable latency
Availability vs consistency
CP - Consistency/Partition Tolerance
could result in a timeout error
等待分区节点的响应可能会导致延时错误。如果你的业务需求需要原子读写,CP 是一个不错的选择。
Choose Consistency over Availability when your business requirements dictate atomic reads and writes.
AP - Availability/Partition Tolerance
the system needs to continue to function in spite of external errors (shopping carts, etc.)
AP is a good choice if the business needs allow for eventual consistency or when the system needs to continue working despite external errors
如果业务需求允许最终一致性,或当有外部故障时要求系统继续运行,AP 是一个不错的选择
RPC VS REST
| 操作 | RPC | REST | | :—- | :—- |:—- | | 注册 | POST/signup | POST/persons | | 注销 | POST/resign {“personid”: “1234”} |DELETE/persons/1234 | | 读取用户信息 | GET/readPerson?personid=1234 |GET/persons/1234 | | 读取用户物品列表 | GET/readUsersItemsList?personid=1234 |GET/persons/1234/items | | 向用户物品列表添加一项 |Post/addItemToUserItemsList{“personid”: “1234”; “itemid”:“456”} |POST/persons/1234/items{“itemid”:“456”} | | 更新一个物品 | Post/modifyItem{“itemid”:“456”;“key”: “value” } |PUT/items/456{“key”: “value”} | |删除一个物品 | Post/removeItem{“itemid”:“456”} |DELETE/items/456|
该知道的时间数据
| power | Exact Value | Approx Value | Bytes | :—- | :—- |:—- |:—- | 7 | 128 | | | 8 | 256 | | | 10 | 1024 | 1 thousand | 1 kB | 16 | 65,536 | | 64 kB | 20 | 1,048,576 | 1 million | 1 MB | 30 | | 1 billion | 1 GB | 32 | | billion | 4 GB | 40 | | 1 trillion | 1 TB
延迟数字
2020 年数据
Latency Comparison Numbers
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 10,000 ns 10 us
Send 1 KB bytes over 1 Gbps network 10,000 ns 10 us
Read 4 KB 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
HDD seek 10,000,000 ns 10,000 us 10 ms 20x datacenter roundtrip
Read 1 MB sequentially from 1 Gbps 10,000,000 ns 10,000 us 10 ms 40x memory, 10X SSD
Read 1 MB sequentially from HDD 30,000,000 ns 30,000 us 30 ms 120x memory, 30X SSD
Send packet CA->Netherlands->CA 150,000,000 ns 150,000 us 150 ms
Notes
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
Read sequentially from HDD at 30 MB/s
Read sequentially from 1 Gbps Ethernet at 100 MB/s
Read sequentially from SSD at 1 GB/s
Read sequentially from main memory at 4 GB/s
6-7 world-wide round trips per second
2,000 round trips per second within a data center
以上是 2009 的数据,实际上内存、SSD 和机械硬盘顺序读取速度有了非常大的提升。
内存:100 秒
SSD:4.4 小时
同一数据中心往返:5.8 天
机械硬盘寻址:23.1 天
从远程服务器的内存中读数据要比直接从硬盘上读取要快的
对于读取 1MB 数据,内存、SSD 和磁盘基本差了一个数量级:
内存: 50 分钟
SSD: 13.6 小时
磁盘: 9.5 天
尤其在设计存储引擎时,很多开源软件(Kafka、Leveldb、Rocksdb)都充分利用了存储介质顺序读、写速度远远快过随机读、写的特性,只做追加写操作来达到最佳性能。