在系統設計面試中，有時你會被要求使用「粗略估算（back-of-the-envelope estimation）」來評估系統的容量或效能需求。根據 Google 資深院士 Jeff Dean 的說法：「粗略估算是透過思想實驗與常見效能數據的組合所建立的估計，用來對哪些設計能滿足需求獲得良好的直覺」[1]。
要能有效地進行粗略估算，你必須對擴展性（scalability）的基礎有良好的掌握。以下概念應該要熟悉：
- 2 的次方（power of two）[2]
- 每個程式設計師都應該知道的延遲數字（latency numbers）
- 可用性數字（availability numbers）
Power of two#
處理分散式系統時，資料量可能變得非常龐大，但計算最終都回歸到基本。要得到正確的計算結果，關鍵在於熟悉以 2 的次方為單位的資料量。
一個 byte 是 8 個 bit 的序列。一個 ASCII 字元佔用 1 byte 的記憶體（8 bits）。下表說明各級資料量單位（表 1）。
| Power | Approximate value | Full name | Short name |
|---|---|---|---|
| 10 | 1 Thousand | 1 Kilobyte | 1 KB |
| 20 | 1 Million | 1 Megabyte | 1 MB |
| 30 | 1 Billion | 1 Gigabyte | 1 GB |
| 40 | 1 Trillion | 1 Terabyte | 1 TB |
| 50 | 1 Quadrillion | 1 Petabyte | 1 PB |
表 1
Latency numbers every programmer should know#
Google 的 Dean 博士在 2010 年揭露了典型電腦操作的耗時 [1]。隨著電腦變得更快更強，有些數字已經過時。不過這些數字仍能讓我們對不同電腦操作的快慢有個概念。
| Operation name | Time |
|---|---|
| L1 cache reference | 0.5 ns |
| Branch mispredict | 5 ns |
| L2 cache reference | 7 ns |
| Mutex lock/unlock | 100 ns |
| Main memory reference | 100 ns |
| Compress 1K bytes with Zippy | 10,000 ns = 10 µs |
| Send 2K bytes over 1 Gbps network | 20,000 ns = 20 µs |
| Read 1 MB sequentially from memory | 250,000 ns = 250 µs |
| Round trip within the same datacenter | 500,000 ns = 500 µs |
| Disk seek | 10,000,000 ns = 10 ms |
| Read 1 MB sequentially from the network | 10,000,000 ns = 10 ms |
| Read 1 MB sequentially from disk | 30,000,000 ns = 30 ms |
| Send packet CA (California) ->Netherlands->CA | 150,000,000 ns = 150 ms |
表 2
單位換算說明：
- ns = nanosecond，µs = microsecond，ms = millisecond
- 1 ns = 10^-9 秒
- 1 µs = 10^-6 秒 = 1,000 ns
- 1 ms = 10^-3 秒 = 1,000 µs = 1,000,000 ns
一位 Google 軟體工程師建立了一個工具將 Dean 博士的數字視覺化。這個工具也考慮了時間因素。圖 1 顯示截至 2020 年的延遲數字視覺化結果（圖片來源：參考資料 [3]）。
分析圖 1 中的數字，我們可以得到以下結論：
- 記憶體（memory）很快，但磁碟（disk）很慢。
- 盡可能避免 disk seek。
- 簡單的壓縮演算法速度很快。
- 在透過網路傳送資料之前，盡可能先壓縮。
- 資料中心通常位於不同區域，資料在彼此之間傳輸需要時間。
Availability numbers#
高可用性（high availability）是指系統能夠在令人期望的長時間內持續運作的能力。高可用性以百分比來衡量，100% 代表完全沒有停機時間（downtime）。大多數服務介於 99% 到 100% 之間。
服務等級協議（Service Level Agreement, SLA） 是服務供應商常用的術語。它是你（服務供應商）與客戶之間的協議，正式定義你的服務將提供的可用運行時間等級。Amazon [4]、Google [5] 與 Microsoft [6] 等雲端供應商將他們的 SLA 設在 99.9% 或更高。
Uptime 傳統上以「幾個 9」來衡量，9 越多越好。如表 3 所示，9 的個數對應到預期的系統停機時間。
| Availability % | Downtime per day | Downtime per week | Downtime per month | Downtime per year |
|---|---|---|---|---|
| 99% | 14.40 minutes | 1.68 hours | 7.31 hours | 3.65 days |
| 99.99% | 8.64 seconds | 1.01 minutes | 4.38 minutes | 52.60 minutes |
| 99.999% | 864.00 milliseconds | 6.05 seconds | 26.30 seconds | 5.26 minutes |
| 99.9999% | 86.40 milliseconds | 604.80 | 2.63 seconds | 31.56 seconds |
表 3
Example: Estimate Twitter QPS and storage requirements#
請注意以下數字僅用於本練習，並非 Twitter 的真實數字。
假設：
- 每月 3 億活躍使用者。
- 50% 的使用者每天使用 Twitter。
- 使用者平均每天發 2 則推文。
- 10% 的推文包含媒體（media）。
- 資料保留 5 年。
估算：
每秒查詢數（Query per second, QPS）估算：
- 每日活躍使用者（Daily active users, DAU）= 3 億 * 50% = 1.5 億
- Tweets QPS = 1.5 億 * 2 tweets / 24 小時 / 3600 秒 = ~3500
- 尖峰 QPS = 2 * QPS = ~7000
這裡我們只估算媒體儲存：
- 平均推文大小：
- tweet_id 64 bytes
- text 140 bytes
- media 1 MB
- 媒體儲存：1.5 億 _ 2 _ 10% * 1 MB = 每天 30 TB
- 5 年媒體儲存：30 TB _ 365 _ 5 = ~55 PB
Tips#
粗略估算的重點在於過程。解決問題比得到結果更重要。面試官可能是在測試你的解題能力。
以下是一些可以遵循的訣竅：
- 四捨五入與近似（Rounding and Approximation）：面試時很難進行複雜的數學運算，例如「99987 / 9.1」的結果是多少？沒有必要花寶貴的時間解複雜的數學題。精度並非重點。善用整數與近似值。上面的除法可以簡化為「100,000 / 10」。
- 寫下你的假設：把假設寫下來是個好習慣，方便之後參照。
- 標註你的單位：當你寫下「5」時，它代表 5 KB 還是 5 MB？你可能會把自己搞糊塗。寫下單位，因為「5 MB」能避免歧義。
- 常見的粗略估算題目：QPS、尖峰 QPS、儲存量、快取、伺服器數量等等。準備面試時可以多練習這些計算。熟能生巧。
恭喜你讀到這裡！給自己拍拍肩，做得很好！