如何設計一個短網(wǎng)址系統(tǒng)
網(wǎng)址短鏈接就是一些長鏈接的別名，比如 bit.ly, goo.gl, qlink.me，輸入這些鏈接會跳轉(zhuǎn)到對應的長鏈接。
1.為什么需要短鏈接
短鏈接主要用來為長鏈接生成更短的別名，用戶點擊短鏈接會重定向到原來的長鏈接，在顯示、打印、發(fā)送消息、發(fā)送推文等場景下，短鏈接節(jié)省了很大的顯示空間，更重要的是，用戶不太可能去拒絕輸入一個短鏈接。
舉個例子，為長鏈接 https://www.educative.io/collection/page/5668639101419520/5649050225344512/5668600 916475904/ 生成的短鏈接就是 http://tinyurl.com/jlg8zpc]，短鏈接的長度僅僅是原來的三分之一。
短鏈接主要用于優(yōu)化，可以跟蹤單個鏈接以進行分析受眾群體和廣告效果，并隱藏關聯(lián)的原始網(wǎng)址。如果你從未使用過 tinyurl.com，請在上面嘗試創(chuàng)建一個短網(wǎng)址，并了解一下他們的服務，這將有助于你理解需求。
2.系統(tǒng)的需求和目標
應在面試開始時就明確需求。面試時請務必提出問題，以找到所設計系統(tǒng)的確切范圍。我們的 URL 短鏈接系統(tǒng)應滿足以下需求：
功能需求：
1、 給定一個 URL，我們的服務應為其生成一個較短且唯一的別名，這也是最基本最核心的功能。
2、當用戶訪問短鏈接時，我們的服務應將其重定向到原始鏈接。
3、用戶應該可以選擇為其 URL 選擇自定義格式的短鏈接。
4、鏈接將在默認時間間隔后過期，用戶可以指定指定到期時間。
非功能需求：
1、該系統(tǒng)應具有很高的可用性。這是必需的，因為如果的服務中斷，則所有 URL 重定向?qū)⑹ ?/p>
2、URL 重定向應以最小的延遲實時進行。
3、生成的短鏈接是不可猜測的，也就是說長鏈接到短鏈接的轉(zhuǎn)換是無規(guī)律的。
擴展需求
1、數(shù)據(jù)分析需求：例如，重定向發(fā)生了多少次？
2、其他服務可以通過 REST API 訪問我們的服務。
3、短鏈接可以回收。
3.資源估算和約束
很明顯，我們的系統(tǒng)將是讀任務比寫任務繁重，也就是說重定向的請求次數(shù)要遠多于生成短網(wǎng)址的請求次數(shù)。假設讀寫之間的比例為 100：1，接下來進行一些估算：
流量估算
假設我們每月將有 500 M 新的 URL 生成，其中讀寫比為 100：1， 可以預測每月有 500 億次重定向：
100 * 500M => 50B
預測下系統(tǒng)每秒的請求次數(shù) QPS（Queries Per Second）：
500 million / (30 days * 24 hours * 3600 seconds) = ~200 URLs/s
也就是說每秒的寫請求次數(shù)是 200 次。考慮到讀寫比就 100:1，那么重定向的 QPS 是：
100 * 200 URLs/s = 20K/s
也就是每秒 2 萬次重定向請求。
存儲估算
假設我們存儲每個短鏈接的請求（以及相關的短 鏈接）為 5 年。由于我們預計每月會有 5 億個新 URL，因此對象總數(shù)我們預計將存儲 300 億：
500 million * 5 years * 12 months = 30 billion
假設每個存儲的對象大約為 500 個字節(jié)，當然，這僅是估算值，我們將需要 15 TB 的總存儲空間：
30 billion * 500 bytes = 15 TB
帶寬估計
對于寫請求，由于我們期望每秒總共 200 個新 URL，我們服務的傳入數(shù)據(jù)將為每秒 100 KB：
200 * 500字節(jié)= 100 KB / s
對于讀請求，由于我們期望每秒進行約 20 K 的 URL 重定向，因此我們的總傳出數(shù)據(jù)的服務將是每秒 10 MB：
20K * 500字節(jié)=?10 MB / s
內(nèi)存估算
如果要緩存一些經(jīng)常訪問的熱門網(wǎng)址，則需要多少多大的內(nèi)存來存儲它們呢？
如果我們遵循 80-20 規(guī)則，則意味著 20％ 的網(wǎng)址生成 80％ 的流量，我們想緩存這 20％ 的熱門 URL。
由于我們每秒有 2 萬個請求，因此我們每天將收到 17 億個請求：
20K * 3600秒* 24小時=約 17 億
要緩存這些請求的 20％，我們將需要 170 GB 的內(nèi)存。
0.2 * 17億* 500字節(jié)=?170GB
這里要注意的一件事是，由于會有很多重復的請求，即相同的 URL，因此，我們的實際內(nèi)存使用量將小于 170 GB。
估算匯總
假設每月有 5 億個新 URL，讀/寫比為 100：1，
新網(wǎng)址 200 / s/ URL 重定向 20 K / s 傳入數(shù)據(jù) 100 KB / s 傳出數(shù)據(jù) 10 MB / s 儲存 5 年 15 TB 緩存內(nèi)存 170 GB
4.系統(tǒng) API 設計
一旦確定了需求，最好的辦法就是定義系統(tǒng) API，這可以明確闡述系統(tǒng)的期望。我們可以使用 SOAP 或 REST API 來說明我們服務的功能。
以下可能是用于創(chuàng)建 URL 的 API 定義：
createURL(api_dev_key, original_url, custom_alias=None, user_name=None,
expire_date=None)
參數(shù)說明:
api_dev_key (字符串): 注冊帳戶的 API 開發(fā)人員密鑰。這可以根據(jù)分配的配額限制用戶。 original_url（字符串）：要縮短的原始 URL。 custom_alias（字符串）：URL 的可選自定義鍵。 user_name （字符串）：可選，用于編碼的用戶名 expire_date （字符串）：過期時間。
返回值：
如果成功則返回對應的短鏈接，否則返回錯誤代碼。
還需要一個過期后刪除短鏈接的 API，比如：
deleteURL(api_dev_key, url_key)
這里的 url_key 就是要刪除的短鏈接。如果刪除成功，則返回“url 已經(jīng)刪除”，必要時可以回收短鏈接資源。
如何檢測并防止惡意調(diào)用
惡意用戶可以通過消耗全部資源來使我們的服務不可用。當前設計中的 api_dev_key 就是為了防止濫用，可以通過其 api_dev_key 限制用戶。比如為每一個 api_dev_key 每一段時間限制為一定數(shù)量的 URL 創(chuàng)建和重定向。
5.數(shù)據(jù)庫設計
在面試的早期階段定義數(shù)據(jù)庫模式將有助于理解數(shù)據(jù)各個組件之間的交互，并指導數(shù)據(jù)分區(qū)。
我們要存儲的數(shù)據(jù)有以下特點：
我們需要存儲海量的數(shù)據(jù)，比如上億條記錄。 每一個對象都比較小，小于 1 K。 記錄與記錄之間沒有關系。 任務是讀繁重的。
數(shù)據(jù)庫模式
我們需要建兩個表，一個存儲 url 映射信息，一個存儲創(chuàng)建短鏈接的用戶數(shù)據(jù)。
url 表：
id original-url short-url creation-date expiration-date user-id
user 表：
user-id name email creation-date last-login
選用哪一種數(shù)據(jù)庫？
一方面要存儲大量的數(shù)據(jù)，另一方面，數(shù)據(jù)對象之間的關系非常簡單，使用非關系型數(shù)據(jù)庫是更好的選擇，比如 DynamoDB, Cassandra or Riak，而且選擇 NoSQL 更容易規(guī)模化。
6. 基本的系統(tǒng)設計和算法
我們這里要解決的問題是如何為給定的 URL 生成短而唯一的密鑰。
在第 1 節(jié)的 TinyURL 示例中，縮短的URL為 “ http://tinyurl.com/jlgzpc” 。最后六個 URL 的字符是我們要生成的短鍵。在此處探討兩種解決方案：
第一種：編碼實際的 URL
我們可以計算給定網(wǎng)址的唯一哈希（例如 MD5 或 SHA256 等）。哈希可以再被編碼用于顯示。此編碼可以是 base36（[a-z，0-9]）或 base62（[A-Z，a-z，0-9]），如果我們添加“-”和“.”，則可以使用 base64 編碼。一個合理的問題是，如何確定短鍵的長度，6、8 或 10 個字符？
使用 base64 編碼， 6 個字母長度可以生成 64 ^ 6 = 約 687 億個可能的字符串，8 個字母長度可以生成 64 ^ 8 =?281 萬億個可能的字符串。前面已經(jīng)估算過，5 年內(nèi)產(chǎn)生 300 億個新 URL，且短鏈接的保存期限也是 5 年，那么 687 億足夠滿足 5 年內(nèi)的使用，因此選擇 6 個字母長度即可。
如果我們將 MD5 算法用作哈希函數(shù)，它將產(chǎn)生 128 個二進制位。在 base64 之后編碼，我們將得到一個包含 21 個以上字符的字符串（因為每個 base64 字符代表 6 位 二進制位，128/6 = 21.3）。由于每個短鏈接只能容納 6 個字符，因此可以選取 21 個字符的前 6 個作為短鏈接的 key，不過這可能會導致密鑰重復，可以從編碼字符串中選擇其他一些字符或交換一些字符來降低重復的概率。
這樣的方案會產(chǎn)生什么問題：
1、如果多個用戶輸入相同的長鏈接，獲取的短鏈接也是相同的，這是不能接收的，即使相同的長鏈接，不同用戶生成的短鏈接也是不同的，只有這樣才可以跟蹤單個鏈接以進行分析受眾群體和廣告效果。
2、如果長鏈接被編碼了怎么辦，比如：“ http://www.educative.io/distributed.php? id=design” 和 “ http://www.educative.io/distributed.php%3Fid%3Ddesign” 是相同的鏈接，但后者進行了編碼，導致相同的 url 產(chǎn)生了不同的短鏈接。
如何解決呢？
針對第一個問題，我們可以為每一個 url 設置一個自增的序列號，確保每一個 url 的唯一性，然后 url 和序列號一起做哈希，數(shù)據(jù)庫中可以不保存這個序列號，即使如此也可能產(chǎn)生問題，比如說這個自增序列號會不會溢出，自增序列號是全局唯一的，使我們的服務要先獲取才能使用，一定程度上降低了并行度，降低了性能。
另一種方法是將 url 和 用戶的 api-dev-key 一起編碼，這種方式比前一種要好，但也不是沒有缺點，就是用戶必須注冊并獲取 api-dev-key 才能使用，我們的系統(tǒng)要能確保為用戶生成的 api-dev-key 都是唯一的。
第二個問題比較簡單，獲取到 url 后統(tǒng)一存放編碼后或編碼前的 url 即可。
第二種：離線生成短鏈接 key
我們可以有一個獨立的短鏈接 key 生成服務（KGS ：Key Generation Service），它可以生成隨機的六個字母字符串，事先將它們存儲在數(shù)據(jù)庫中（我們稱其為密鑰數(shù)據(jù)庫）。每當我們要縮短網(wǎng)址時，我們將只使用一個已經(jīng)生成好的字符串并使用它。這種方法會使事情變得相當簡單快捷。這樣就不需要對 URL 進行編碼，而且不必擔心重復或哈希碰撞。KGS 將確保插入到數(shù)據(jù)庫中的所有 key 都是唯一的。
這樣的話，并發(fā)度高會產(chǎn)生問題嗎？如果有多個服務器同時讀取 key，該如何解決？
使用 key 后，應立即對其進行標記，確保不再使用它。服務器可以使用 KGS 來讀取/標記數(shù)據(jù)庫中的 key。KGS 可以使用兩個表來存儲 key ：一個存儲尚未使用的 key，一個保存所有已使用的 key。一旦 KGS 將鑰匙交給其中一個服務器，它可以將它移動到已使用的 key 表中。KGS 始終可以在內(nèi)存中保留一些 key，以便服務器需要時更快的響應。
為簡單起見，一旦 KGS 將一些 key 加載到內(nèi)存中，它便可以將其移至已用的 key 表中。這樣可以確保每個服務器都獲得唯一的 key。如果在將所有已加載的 key 分配給某個服務器之前，KGS 服務宕機，我們將浪費那些已加載的 key，考慮到我們擁有的 key 數(shù)量巨大，這是可以接受的。
KGS 還必須確保不要將相同的 key 提供給多個服務器。為此，它必須同步（或鎖定）持有 key 的數(shù)據(jù)結構，然后再從中刪除，然后將其提供給服務器。
那么保存 key 的數(shù)據(jù)庫的大小是多少？使用 base64 編碼，我們可以生成 687 億個唯一的六個字母的 key。一個字節(jié)來可以存儲一個字符，則可以將所有這些鍵存儲，需要的數(shù)據(jù)庫大小為 412 GB：
6 (characters per key) * 68.7B (unique keys) = 412 GB.
KGS 存在單點故障嗎？是的。為了解決這個問題，我們可以有一個 KGS 的備機，只要主服務器死機，備用服務器就可以接管生成并提供 key。
每個應用服務器都可以從 key-DB 緩存一些 key 嗎？是的，這還可以加快速度。雖然 在這種情況下，如果應用服務器沒有使用完 key 之前就宕機，我們最終將失去這些密 key。這是可以接受的，因為我們有 687 億個唯一的六個字母 key。
如何執(zhí)行 key 的查找？我們可以在數(shù)據(jù)庫中根據(jù) key 獲取原始的 URL。如果存在，就向瀏覽器發(fā)出“ HTTP 302 重定向”狀態(tài)，并重定向到原始的 URL。如果該 key 不存在于系統(tǒng)中，請發(fā)出“未找到 HTTP 404”，將用戶重定向回首頁。
應該對自定義別名施加大小限制嗎？我們的服務支持自定義別名。用戶可以選擇 他們喜歡的任何“鍵”，但并非必須提供自定義別名。但是，這是合理的，而且通常 最好對自定義別名施加大小限制，以確保我們擁有一致的 URL 數(shù)據(jù)庫，比如用戶最多可指定 16 個字符，數(shù)據(jù)架構如下如所示：
7.數(shù)據(jù)分區(qū)
為了數(shù)據(jù)庫便于擴展，我們需要對其進行分區(qū)，以便它可以存儲數(shù)十億個 URL 的信息。所謂的分區(qū)就是將數(shù)據(jù)劃分并存儲到不同的數(shù)據(jù)庫服務器中。
一種方法是基于范圍的分區(qū)：我們可以根據(jù)網(wǎng)址的第一個字母或 url 的哈希值 將網(wǎng)址存儲在單獨的分區(qū)中，比如將所有以字母“ A”開頭的網(wǎng)址保存在一個分區(qū)中，字母“ B”開頭的保存在另一個分區(qū)中，依此類推。這種方法稱為基于范圍的分區(qū)。甚至可以將某些不經(jīng)常出現(xiàn)的字母組合，包含組合字母的 url 放到一個數(shù)據(jù)庫分區(qū)中。這也是一種靜態(tài)分區(qū)方案，提前規(guī)劃好方案，每一個 url 存儲到哪個分區(qū)都是可以預見的。
這種方法可能導致分區(qū)的不平衡。例如：將所有以字母 “E” 開頭的 URL 放入數(shù)據(jù)庫分區(qū) A，但后來我們意識到我們有太多以字母“ E”開頭的網(wǎng)址，于是分區(qū) A 存儲了過多的數(shù)據(jù)。
另一種方法就是基于散列的分區(qū)：在此方案中，我們對要存儲的對象進行散列。然后我們根據(jù)哈希計算要使用的分區(qū)。例如，我們的哈希函數(shù)總是可以將任何 url 映射到 1…256 之間的數(shù)字，該數(shù)字代表數(shù)據(jù)的分區(qū)我們，這種方法仍然會導致分區(qū)不平衡，不過這可以通過使用一致性哈希技術來解決。(什么是一致性哈希技術，我立刻搜了一下)
node_number = hash(key) % N
8.緩存
對于經(jīng)常訪問的 URL 可以緩存。我們可以使用一些現(xiàn)成的解決方案，例如 Memcache，可以存儲帶有各自哈希值的完整 URL。應用服務器問后端存儲之前，可以快速檢查緩存是否具有所需的URL。
緩存多大比較好？我們可以從每日流量的 20％ 開始，并根據(jù)客戶的使用情況調(diào)整所需的緩存服務器數(shù)量。前面內(nèi)存估算時，我們需要 170 GB 內(nèi)存來緩存每日流量的 20％。由于現(xiàn)代服務器可以擁有 256 GB 的內(nèi)存，因此我們可以輕松的將所有緩存放入一臺服務器。另外，我們可以使用幾個較小的服務器來存儲所有這些熱點網(wǎng)址。
哪種高速緩存淘汰算法最適合我們的需求？當緩存已滿時，我們想要用較新/較熱門的 URL 替換掉較舊/較冷門的鏈接，最近最少使用（LRU）就是最適合這個需求人根據(jù)此算法，我們將首先丟棄最近最少使用的 URL。我們可以使用 Java 的 Linked Hash Map 來實現(xiàn)，或者使用自定義的數(shù)據(jù)結構來實現(xiàn)。
為了進一步提高效率，我們可以復制緩存服務器，然后配置負載均衡。這樣會帶來一個問題：如何更新每個緩存副本？每當發(fā)生緩存未命中時，我們的服務器就會訪問后端數(shù)據(jù)庫，每當發(fā)生這種情況時，我們可以更新緩存并將新條目傳遞給 所有緩存副本。每個副本都可以通過添加新條目來更新其緩存。如果副本已經(jīng)存在 有該條目，它可以簡單地忽略它。
9.負載均衡器（LB）
我們可以在系統(tǒng)的三個位置添加一個負載平衡器（LB） ：
在客戶端和應用程序服務器之間 在應用程序服務器和數(shù)據(jù)庫服務器之間 在應用程序服務器和緩存服務器之間
最初，我們可以使用簡單的 Round Robin 方法，將傳入請求平均分配 在后端服務器之間，這樣易于實現(xiàn)，不會帶來任何開銷，如果某個服務器宕機，則負載平衡器會將其從循環(huán)中移出并停止向它發(fā)送任何流量。Round Robin LB 的問題是未考慮服務器負載。如果服務器是過載或速度較慢時，LB 不會停止向該服務器發(fā)送新請求。為了解決這個問題，可以放置智能 LB 解決方案，該解決方案定期向后端服務器查詢有關其負載和負載的信息，以此來調(diào)整流量。
10.清除或數(shù)據(jù)庫清理
url 記錄應該永久存儲還是應該物理刪除？如果用戶指定的到期時間為到達后，鏈接應該怎么處理？
如果我們選擇主動搜索過期鏈接以將其刪除，這將給數(shù)據(jù)庫服務器帶來很大壓力 。相反，我們可以慢慢刪除過期的鏈接并進行懶惰的清理。我們的服務會確保刪除過期的鏈接，盡管某些過期的鏈接可以生存更長的時間，但永遠不會返回給用戶。
每當用戶嘗試訪問過期的鏈接時，我們都可以刪除該鏈接并向該用戶返回錯誤提示。 可以定期運行單獨的清理服務，從數(shù)據(jù)庫和緩存進行清理，此服務應非常輕巧，并且可以安排在用戶流量很低的時間段執(zhí)行。 我們可以為每個鏈接設置默認的過期時間（例如，兩年）。 刪除過期的鏈接后，我們可以將短鏈接的 key 放回 key 數(shù)據(jù)庫中以重新使用。 我們是否應該刪除一段時間（例如六個月）未曾訪問過的鏈接？由于存儲設備價格便宜，我們可以永久保留鏈接。
11. 統(tǒng)計分析
短鏈接已使用了多少次，用戶位置是什么，訪問者所在的國家/地區(qū)，訪問日期和時間，點擊次數(shù)等等，我們將如何存儲這些統(tǒng)計數(shù)據(jù)？
12.安全性和權限
用戶可以創(chuàng)建私有 URL 還是允許特定的一組用戶訪問 URL？
我們可以使用數(shù)據(jù)庫中的每個 URL 存儲許可級別（公共/私有）。我們還可以創(chuàng)建一個單獨的表來存儲有權查看特定 URL 的 UserID。如果用戶沒有權限并嘗試訪問URL，我們可以將錯誤（HTTP 401）發(fā)送回去。
最后的話
系統(tǒng)設計設計軟件開放的方方面面，往往難以一次回答全面，但是無外乎以上幾個方面，按照梳理好的步驟去思考，展示自己的技術優(yōu)勢，面試就不會太差，本文內(nèi)容整理自《Grokking the System Design Interview》，如果想看英文原版可以關注本號后臺回復「系統(tǒng)設計」獲取。