在本章中，我們將處理一個有趣且經典的系統設計面試題：設計一個類似 tinyurl 的 URL 縮短服務。
Step 1 - 理解問題並確立設計範圍#
系統設計面試題目刻意保持開放式。為了設計出精良的系統，提出釐清性的問題至關重要。
應徵者：可以舉個例子說明 URL 縮短器如何運作嗎？
面試官：假設原始 URL 是 https://www.systeminterview.com/q=chatsystem&c=loggedin&v=v3&l=long。你的服務會建立一個較短的別名：https://tinyurl.com/y7keocwj。當你點擊該別名時，會被重新導向到原始 URL。
應徵者：流量規模是多少？
面試官：每天會產生 1 億個 URL。
應徵者：縮短後的 URL 有多長？
面試官：越短越好。
應徵者：縮短後的 URL 允許哪些字元？
面試官：縮短後的 URL 可以是數字（0-9）和字元（a-z、A-Z）的組合。
應徵者：縮短後的 URL 可以被刪除或更新嗎？
面試官：為了簡化問題，我們假設縮短的 URL 不能被刪除或更新。
以下是基本的使用案例：
- URL 縮短：給定一個長 URL => 回傳一個更短的 URL
- URL 重新導向：給定一個短 URL => 重新導向到原始 URL
- 高可用性、可擴展性與容錯考量
粗略估算（Back of the envelope estimation）#
- 寫入操作：每天產生 1 億個 URL
- 每秒寫入操作：1 億 / 24 / 3600 = 1160
- 讀取操作：假設讀寫比為 10:1，每秒讀取操作為 1160 * 10 = 11,600
- 總紀錄數：假設 URL 縮短服務會運行 10 年，這表示我們必須支援 1 億 * 365 * 10 = 3650 億筆紀錄
- 平均 URL 長度：假設為 100
- 10 年儲存需求：3650 億 * 100 bytes = 36.5 TB
務必與面試官一同走過這些假設與計算，讓雙方對齊認知。
Step 2 - 提出高階設計並取得認可#
在本節中，我們討論 API 端點、URL 重新導向以及 URL 縮短的流程。
API 端點#
API 端點促進客戶端與伺服器之間的通訊。我們會以 REST 風格設計 API。如果你不熟悉 RESTful API，可以參考外部資料，例如參考資料 [1]。URL 縮短器主要需要兩個 API 端點。
URL 縮短。要建立新的短 URL，客戶端會發送一個 POST 請求，其中包含一個參數：原始長 URL。API 如下：
POST api/v1/data/shorten - request parameter: {longUrl: longURLString} - return: shortURLURL 重新導向。要將短 URL 重新導向到對應的長 URL，客戶端會發送一個 GET 請求。API 如下：
GET api/v1/shortUrl - return: longURL for HTTP redirection
URL 重新導向#
圖 1 顯示當你在瀏覽器輸入 tinyurl 時所發生的事。當伺服器收到 tinyurl 請求後，它會以 301 redirect 將短 URL 轉換為長 URL。
客戶端與伺服器之間詳細的通訊如圖 2 所示。
這裡值得討論的一件事是 301 redirect 與 302 redirect 的差異。
- 301 redirect：表示請求的 URL 已「永久」移到長 URL。由於是永久重新導向，瀏覽器會快取該回應，後續對相同 URL 的請求將不會送到 URL 縮短服務，而是直接導向長 URL 伺服器。
- 302 redirect：表示 URL 是「暫時」移到長 URL，意思是後續對相同 URL 的請求會先送到 URL 縮短服務，然後再被導向長 URL 伺服器。
每種重新導向方式都有其優缺點：
- 如果優先目標是降低伺服器負載，使用 301 redirect 是合理的，因為相同 URL 只有第一次請求會送到 URL 縮短伺服器。
- 然而，若**分析（analytics）**很重要，302 redirect 是更好的選擇，因為它能更容易追蹤點擊率與點擊來源。
實作 URL 重新導向最直觀的方式是使用 hash table。假設 hash table 儲存 <shortURL, longURL> 對，URL 重新導向可以實作如下：
- 取得 longURL：
longURL = hashTable.get(shortURL) - 取得 longURL 後執行 URL 重新導向
URL 縮短#
讓我們假設短 URL 看起來像這樣：www.tinyurl.com/{hashValue}。為了支援 URL 縮短的使用案例，我們必須找到一個 hash function fx，將長 URL 對應到 hashValue，如圖 3 所示。
該 hash function 必須滿足以下需求：
- 每個 longURL 必須被 hash 為一個 hashValue
- 每個 hashValue 必須能對應回 longURL
hash function 的詳細設計會在深入探討中討論。
Step 3 - 設計深入探討#
到目前為止，我們已經討論了 URL 縮短與 URL 重新導向的高階設計。在本節中，我們會深入以下內容：資料模型、hash function、URL 縮短與 URL 重新導向。
資料模型#
在高階設計中，所有東西都儲存在 hash table 裡。這是個好的起點；然而，這種方式對真實世界系統並不可行，因為記憶體資源有限且昂貴。
較好的做法是將 <shortURL, longURL> 對應儲存在關聯式資料庫中。圖 4 顯示一個簡單的資料表設計。簡化版本的資料表包含 3 個欄位：id、shortURL、longURL。
Hash function#
hash function 用來把長 URL 雜湊為短 URL，也稱為 hashValue。
Hash 值長度#
hashValue 由 [0-9, a-z, A-Z] 中的字元組成，共有 10 + 26 + 26 = 62 個可能字元。要決定 hashValue 的長度，我們找出最小的 n 使得 62^n ≥ 3650 億。根據粗略估算，系統必須支援多達 3650 億個 URL。表 1 顯示 hashValue 的長度與其能支援的最大 URL 數量。
| n | 最大 URL 數量 |
|---|---|
| 1 | 62^1 = 62 |
| 2 | 62^2 = 3,844 |
| 3 | 62^3 = 238,328 |
| 4 | 62^ 4 = 14,776,336 |
| 5 | 62^5 = 916,132,832 |
| 6 | 62^6 = 56,800,235,584 |
| 7 | 62^7 = 3,521,614,606,208 = 約 3.5 兆 |
| 8 | 62^8 = 218,340,105,584,896 |
表 1
當 n = 7 時，62 ^ n = 約 3.5 兆，3.5 兆遠超過 3650 億個 URL 的需求，因此 hashValue 的長度是 7。
我們會探討兩種 URL 縮短器的 hash function：
- Hash + 碰撞解析（collision resolution）
- 62 進位轉換（base 62 conversion）
我們逐一說明。
Hash + 碰撞解析#
要縮短長 URL，我們應該實作一個 hash function 將長 URL 雜湊為一個 7 字元字串。一個直接的做法是使用知名的 hash function，例如 CRC32、MD5 或 SHA-1。下表比較這幾個 hash function 套用在以下這個 URL 上的結果：
https://en.wikipedia.org/wiki/Systems_design
| Hash function | Hash 值（十六進位） |
|---|---|
| CRC32 | 5cb54054 |
| MD5 | 5a62509a84df9ee03fe1230b9df8b84e |
| SHA-1 | 0eeae7916c06853901d9ccbefbfcaf4de57ed85b |
表 2
如表 2 所示，即使是最短的 hash 值（CRC32）仍然太長（超過 7 字元）。我們如何讓它更短？
第一種方法是取 hash 值的前 7 個字元；然而這種做法可能造成 hash 碰撞。為了解決 hash 碰撞，我們可以遞迴地附加一個預先定義的字串，直到不再發生碰撞為止。此流程於圖 5 解釋。
這個方法可以消除碰撞；然而，每個請求都要查詢資料庫檢查 shortURL 是否存在的成本太高。
一種叫做 bloom filter [2] 的技術可以改善效能。Bloom filter 是一種空間效率高的機率性技術，用來測試元素是否屬於某個集合。詳情請參閱參考資料 [2]。
62 進位轉換#
進位轉換是另一種常用於 URL 縮短器的方法。進位轉換可以將同一個數字在不同進位的表示法之間互相轉換。會使用 62 進位轉換是因為 hashValue 有 62 個可能的字元。讓我們用一個例子來說明轉換如何運作：把 1115710 轉換成 62 進位表示（1115710 在 10 進位中代表 11157）。
- 顧名思義，62 進位是使用 62 個字元編碼的方式。對應關係為：0-0、…、9-9、10-a、11-b、…、35-z、36-A、…、61-Z，其中 ‘a’ 代表 10，‘Z’ 代表 61，依此類推。
- 1115710 = 2 x 622 + 55 x 621 + 59 x 620 = [2, 55, 59] -> 在 62 進位表示中為 [2, T, X]。圖 6 顯示轉換過程。
- 因此，短 URL 為
https://tinyurl.com/2TX
兩種方法的比較#
表 3 顯示兩種方法的差異。
| Hash + 碰撞解析 | 62 進位轉換 |
|---|---|
| 短 URL 長度固定。 | 短 URL 長度不固定，會隨 ID 增加。 |
| 不需要唯一 ID 產生器。 | 此選項依賴唯一 ID 產生器。 |
| 可能發生碰撞且需要被解決。 | 不會發生碰撞，因為 ID 是唯一的。 |
| 因為不依賴 ID，無法推算下一個可用的短 URL。 | 若 ID 對每個新項目以 1 遞增，很容易推算下一個可用的短 URL。這可能是安全疑慮。 |
表 3
使用 62 進位轉換時，若 ID 以 1 遞增，攻擊者可輕易推算下一個可用的短 URL，這可能造成安全疑慮。
URL 縮短深入探討#
作為系統的核心之一，我們希望 URL 縮短流程在邏輯上保持簡單且功能完備。我們的設計採用 62 進位轉換。我們建立以下圖示（圖 7）來示範該流程。
longURL是輸入。- 系統檢查
longURL是否已在資料庫中。 - 如果是，表示該
longURL之前已被轉換為shortURL。在此情況下，從資料庫取出shortURL並回傳給客戶端。 - 如果否，表示此
longURL是新的。一個新的唯一 ID（主鍵）由唯一 ID 產生器產生。 - 用 62 進位轉換把 ID 轉換為
shortURL。 - 在資料庫中建立一筆新的紀錄，包含 ID、
shortURL與longURL。
為了讓流程更容易理解，讓我們看一個具體例子。
- 假設輸入的 longURL 為：
https://en.wikipedia.org/wiki/Systems_design - 唯一 ID 產生器回傳 ID：2009215674938
- 用 62 進位轉換把 ID 轉換為 shortURL。ID（2009215674938）會被轉換為 “zn9edcu”
- 將 ID、shortURL 與 longURL 儲存到資料庫，如表 4 所示
| id | shortURL | longURL |
|---|---|---|
| 2009215674938 | zn9edcu | https://en.wikipedia.org/wiki/Systems_design |
表 4
分散式唯一 ID 產生器值得一提。其主要功能是產生全域唯一的 ID，用於建立 shortURL。在高度分散的環境中，實作唯一 ID 產生器具有挑戰性。幸運的是，我們已經在「Design A Unique ID Generator in Distributed Systems」章節中討論過幾種解決方案。你可以回頭參考以複習記憶。
URL 重新導向深入探討#
圖 8 顯示 URL 重新導向的詳細設計。由於讀取多於寫入，<shortURL, longURL> 對應會儲存在快取中以提升效能。
URL 重新導向流程總結如下：
- 使用者點擊一個短 URL 連結：
https://tinyurl.com/zn9edcu - 負載平衡器將請求轉發給網頁伺服器。
- 如果 shortURL 已經在快取中，直接回傳 longURL。
- 如果 shortURL 不在快取中，從資料庫取出 longURL。如果資料庫中也沒有，使用者可能輸入了無效的 shortURL。
- longURL 被回傳給使用者。
Step 4 - 總結#
在本章中，我們討論了 API 設計、資料模型、hash function、URL 縮短與 URL 重新導向。
如果面試結束時還有時間，這裡是一些可以繼續討論的點。
- 速率限制器（Rate limiter）：我們可能面臨的潛在安全問題是惡意使用者發送大量的 URL 縮短請求。速率限制器可幫助根據 IP 位址或其他過濾規則篩除請求。如果你想複習速率限制，請參考「Design a rate limiter」章節。
- 網頁伺服器擴展：由於 web tier 是無狀態的，可以透過增減網頁伺服器來輕易擴展。
- 資料庫擴展：資料庫複寫（replication）與分片（sharding）是常見的技術。
- 分析（Analytics）：資料對企業成功越來越重要。將分析方案整合進 URL 縮短器有助於回答重要問題，例如有多少人點擊連結？他們何時點擊？等等。
- 可用性、一致性與可靠性：這些概念是任何大型系統成功的核心。我們在「Scale From Zero To Millions Of Users」章節中詳細討論過，請複習這些主題。
恭喜你看到這裡！現在給自己一個鼓勵。做得好！