Prepare System Design
- 詢問需求和規格 - 先確定這個系統需要提供哪些功能。
- 了解限制條件 - 問問面試官系統需要處理多少流量(traffic)、多少數據，延遲(latency)重要與否，優先選擇可用性還是一致性(CAP), AC選一個)。
- 計算所需資源 - 確定需要多少機器和儲存空間。
- 抽象設計 - 首先畫出系統的整體架構圖，確保每個組件都被包含在內，再根據面試官的需求深入討論某個具體的組件。
- 擴展性(Scale)設計 - 確保你的系統具有容錯能力(fault tolerance)，能夠擴展到大型公司的系統架構。
CAP 可用性、一致性、分區容錯性, 詳細可看 http://ksat.me/a-plain-english-introduction-to-cap-theorem
Design Cache
soucre from 系統設計 - Design cache
Step 1, 2: 問requirement
- 多少資料需要進cache? 30TB
- expected QPS? 10M
- eviction strategy? LRU
- Access pattern? Write back(有空的話Write through, write around, write back都要知道什麼意思 利弊)
- Latency重要嗎? cache的用途就是降低latency
- C or A: A
Step 3:算一下你需要多大的machine多少台
Latency Numbers Every Programmer Should Know 這裡面的數字要有點sense
Latency Comparison Numbers (~2012)
----------------------------------
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 10 ms 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
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
Credit
------
By Jeff Dean: http://research.google.com/people/jeff/
Originally by Peter Norvig: http://norvig.com/21-days.html#answers
Contributions
-------------
'Humanized' comparison: https://gist.github.com/hellerbarde/2843375
Visual comparison chart: http://i.imgur.com/k0t1e.png
假設我們現在要用 72GB RAM 4 core的 machine.
那總共以儲存data來說需要 30TB/72GB = 420台
這樣的話每台的QPS = 10M/420 = 23000, 即使所有core都用了,
每個core要處理6000QPS (23000/4=5750), 代表說 1/6000 = 167 us . 167 us per queries
搭配上面那個比較可知道即使是ram sequentially read 1MB要250 us 所以我們如果用這個size的machine 會無法負荷
Read 1 MB sequentially from memory 250,000 ns 250 us
改變主意 假設現在用16GB RAM 4core的machine 30TB/16GB = 1875台, QPS per CPU = 10M/1875/4 = 1400QPS = 700us per queries. 這個數字負擔小多了
先用data constrain算出要幾台機器, 再用traffic constrain算看看這樣的配置合不合理, 這樣做完你就知道你的system是需要猛的機器少台一點還是差一點的機器多台一點
Step4: 畫出大架構
這時候就必須推薦CS75 (Summer 2012) Lecture 9 Scalability Harvard Web Development David Malan , 後面架構圖的部份一定要看, 這個影片很長, 但是很值得看, 有很多很實用的東西
別人整理好的影片中點 : https://ninefu.github.io/blog/Harvard_CS75_Notes/
Step5: 喇賽時間
這時候system畫完了, 如果要scale的話需要什麼東西
- load balance
- DB就是可能要master-slave或是multi-master這種東西
至於怎麼fault tolerance呢
- 常見的處理就是replication, 就是一樣的資料存很多地方
- 假設有P個 replication 因為每次寫和讀都寫進/讀出這P個地方非常花時間, 那該怎麼辦呢? 假設寫的時候, 只要有W個replication confirm update我就return to user
- 假設讀的時候, 只要有R個replication給我一個一樣的value, 我就return這個value給user depends on design的use case(這就是為什麼use case很重要)
- 你要看read跟write哪一個operation可以承受高一些的latency
- 如果要求read很快 write可以慢一點沒關係, 那就可以設R = 1, W = P, 反之可以設R = P, W = 1 總之 只要R+W > N 那這database就是
strong consistent!
如果真的要求高速度的話就必須犧牲consistent, 那 R+W 就會 <P (weak consistent)
R = 1, W = P 和 R = P, W = 1 是在談論分佈式系統中的一致性模型， R 表示讀取操作 W 表示寫入操作 P 表示副本數量
在第一種模型中，即 R = 1, W = P，它假設讀取操作的一致性要求不高，可以從任意一個副本中讀取最新的資料。因此，只需要讀取一個副本，但寫入操作需要寫入所有的副本，以確保資料的一致性。
在第二種模型中，即 R = P, W = 1，則假設寫入操作的一致性要求不高，只需要將資料寫入任意一個副本。而讀取操作需要從所有副本中讀取資料，以確保讀取到最新的資料。
無論是哪種模型，只要讀取操作和寫入操作的總數量（R+W）超過副本的數量（N），這個分佈式系統就可以實現強一致性。換句話說，只要系統確保了所有的讀取和寫入都能夠經過足夠數量的副本，就可以保證強一致性。這些模型的選擇取決於對於讀取和寫入操作一致性要求的不同，以及系統的性能和成本考慮。
下禮拜要面system design的話
InterviewBit這是個非常好的互動式網站 他是一步一步漸進式的問你每個你在面試中該問的問題,帶你走過一遍system design interview的process 非常建議這裡面的八題都要寫過
Scalable Web Architecture and Distributed Systems
下個月要面的話
把checkcheckzz/system-design-interview#intro和checkcheckzz/system-design-interview#blog的文章都K過你就比大多數candidate強很多了
總結
其實有工作經驗的都知道 你很常需要去design一個新的project 而釐清use case這些事情是基本 連use case都沒問那面試官根本不會覺得你是個好的工程師 主要考察的是communication and problem solving, 給你一個開放性問題 你怎麼分析step by step, 你如何跟別人討論你的idea, 如何optimize你的system 往這個方向想就覺得其實system design其實沒想像中的難