項目簡介：TinyURL是一項在線服務，允許用戶將長網址縮短為簡潔的短網址，以便于分享和使用。這種服務尤其適用于社交媒體和電子郵件，因為這些平臺對鏈接長度可能有限制。TinyURL的使用非常簡單，只需在它的網站上輸入長網址，然后系統會自動生成一個短網址供你使用和分享。

現在讓我們設計一個像TinyURL一樣的URL縮短服務。這個服務將提供短別名來重定向到長URL。

類似的產品有：bit.ly, ow.ly, short.io

系統難度級別：初級

1、為什么我們需要URL縮短？

URL縮短用于為長URL創建更短的別名。我們將這些縮短后的別名稱為“短鏈接”。當用戶點擊這些短鏈接時，他們會被重定向到原始URL。短鏈接在顯示、打印、發送信息或發推文時節省了大量空間。此外，用戶輸入錯誤的可能性也會隨著URL的縮短而減少。

例如，如果我們通過TinyURL縮短以下URL：

https://minorstone.com/archives/xi-tong-jia-gou-de-jing-sui-18-ge-bi-dong-de-she-ji-gai-nian-yi-lan

我們會得到：

http://tinyurl.mobi/JDZR

縮短后的URL幾乎只有實際URL的三分之一大小。

URL縮短用于優化設備間的鏈接，跟蹤單個鏈接以分析觀眾，測量廣告活動的效果，或者隱藏關聯的原始URL。

如果你之前沒有使用過tinyurl.com，請嘗試創建一個新的縮短URL，并花些時間了解他們服務提供的各種選項。這將對你理解這一章節有很大幫助。

2、系統的需求和目標

你應該在面試開始時就明確需求。務必提問，以找出面試官心中系統的準確范圍。

我們的URL縮短系統應滿足以下要求：

功能性需求：

1. 給定一個URL，我們的服務應生成一個更短且唯一的別名。這就是所謂的短鏈接。這個鏈接會足夠短，以便輕松復制并粘貼到應用程序中。
2. 當用戶訪問一個短鏈接時，我們的服務將它們重定向到原始鏈接。
3. 用戶可以自定義的短鏈接。
4. 鏈接將在默認的時間跨度后過期，用戶能夠指定過期時間。

非功能性需求：

1. 系統應高度可用。這是必需的，因為如果我們的服務宕機，所有的URL重定向會失敗
2. URL 重定向需要以最小的延遲實時發生
3. 縮短后的鏈接不可預測

擴展需求：

1. 分析功能；例如，重定向發生了多少次？
2. 其他服務也應通過REST API訪問我們的服務。

3、容量估計和約束

我們的系統將是讀取密集型的。與新的URL縮短相比，將會有大量的重定向請求。我們假設讀取和寫入的比例是100:1。

流量估計：假設我們每月將有5億次新的URL縮短，以100:1的讀/寫比率，我們可以預期在同一時期內有500億次重定向：

100?500M=>50B

我們系統的每秒查詢數（QPS）是多少？每秒新的URL縮短數量：

500million/(30days?24hours?3600seconds)= 200URLs/s

考慮到100:1的讀/寫比率，每秒的URL重定向數量將是：

100 * 200 URLs/s = 20K/s

存儲估計：我們假設存儲每個URL縮短請求（及關聯的縮短鏈接）5年。由于我們預計每月會有5億個新的URL，因此我們預計存儲的對象總數將是300億個：

500million?5years?12mnotallow=30billion

我們假設每個存儲的對象大約為500字節（這只是一個大致的估計——我們稍后會深入研究）。我們需要15TB的總存儲：

30billion?500bytes=15TB

帶寬估計：對于寫請求，由于我們預計每秒會有200個新的URL，我們的服務總入站數據將是每秒100KB：

200?500bytes=100KB/s

對于讀請求，由于我們預計每秒將有大約20K個URL重定向，我們的服務總出站數據將是每秒10MB：

20K?500bytes= 10MB/s

內存估計：如果我們想緩存一些經常訪問的熱門URL，我們需要多少內存來存儲它們？如果我們遵循80-20的規則，即20%的URL產生80%的流量，我們希望緩存這20%的熱門URL。

由于我們每秒有20K個請求，我們每天將獲得17億個請求：

20K?3600seconds?24hours= 1.7billion

為了緩存這20%的請求，我們需要170GB的內存。

0.2?1.7billion?500bytes= 170GB

這里需要注意的一點是，由于會有許多重復請求（相同的URL），我們實際的內存使用量將少于170GB。

高層次估計：假設每月有5億個新的URL，并且讀寫比率為100:1，以下是我們服務的高層次估計的概述：

4、API定義

一旦我們確定了需求，接下來需要定義系統API。需要明確說明系統的預期功能。

我們可以使用SOAP或REST API來公開我們服務的功能。創建和刪除URL的API定義可能如下：

createURL(api_dev_key, original_url, custom_alias=None, user_name=None, expire_date=None)

參數：

1. api_dev_key（字符串）：已注冊賬戶的API開發者密鑰。此密鑰將用于，包括但不限于，根據用戶分配的配額限制用戶。
2. original_url（字符串）：要縮短的原始URL。
3. custom_alias（字符串）：URL的可選自定義鍵。
4. user_name（字符串）：可選的用于編碼的用戶名。
5. expire_date（字符串）：縮短URL的可選過期日期。

返回：（字符串）

成功插入返回縮短后的URL；否則，返回一個錯誤碼。

deleteURL(api_dev_key, url_key)

其中url_key是表示要檢索的縮短URL的字符串；成功刪除后返回URL Removed。

如何檢測和防止濫用？惡意用戶可以通過消耗當前設計中的所有URL鍵會造成大量的冗余key。為了防止濫用，我們可以通過他們的api_dev_key限制用戶。每個api_dev_key可以限制在一定時間段內創建和重定向URL的數量（該時長可能會根據開發者密鑰設置為不同的時長）。

5、數據庫設計

在早期系統設計階段定義DB模式對理解數據在各個組件之間的流動非常有幫助，隨后會引導我們進行數據分區。

我們將存儲的數據具有以下特點：

1. 我們需要儲存上百億條記錄。
2. 我們存儲的每個對象都非常小（小于1K）。
3. 除了記錄哪個用戶創建了一個URL，記錄之間沒有關系。
4. 我們的服務主要是讀取操作。

數據庫架構：

我們需要兩個表：一個用于存儲URL映射信息，另一個用于存儲創建短鏈接的用戶的數據。

我們應該使用什么類型的數據庫？由于我們預計將存儲數十億行，而且我們不需要使用對象之間的關系—一個NoSQL存儲，如DynamoDB，Cassandra或Riak會是一個更好的選擇。一個NoSQL選擇也將更容易擴展。

6、基礎系統設計和算法

我們這里要解決的問題是如何為給定的URL生成一個短而唯一的鍵。

在第一部分的TinyURL示例中，縮短的URL是“http://tinyurl.mobi/JDZR”。這個URL的最后八個字符就是我們想要生成的短鍵。我們將在這里探討兩種解決方案：

A. 編碼實際的URL

我們可以計算給定URL的唯一哈希值（例如D5或**SHA256**等）。然后，哈希可以進行編碼以便顯示。這種編碼可以是Base36（[a-z ,0-9]）或Base62（[A-Z, a-z, 0-9]），如果我們添加 '+' 和 '/'，我們可以使用Base64編碼。一個合理的問題是，短鍵的長度應該是多少？6、8還是10個字符？

使用Base64編碼，長度為6個字符的鍵將產生646= 68764^6 = ~687646= 687億個可能的字符串。

使用Base64編碼，長度為8個字符的鍵將產生648= 28164^8 = ~281648= 281萬億個可能的字符串。

假設對于我們的系統來說，有687億個唯一字符串的六個字符鍵就足夠了。

如果我們使用MD5算法作為我們的哈希函數，它將產生一個128位的哈希值。經過Base64編碼后，我們會得到一個超過21個字符的字符串（因為每個Base64字符編碼了哈希值的6位）。現在我們每個短鍵只有6（或8）個字符的空間；那么我們怎么選擇我們的鍵呢？我們可以取前6（或8）個字符作為鍵。這可能會導致鍵重復；為了解決這個問題，我們可以從編碼字符串中選擇一些其他字符或交換一些字符。

我們的解決方案有哪些問題？我們的編碼方案有以下幾個問題：

1. 如果多個用戶輸入同一個URL，他們可能會得到相同的縮短URL，這是不可接受的。
2. 如果URL的部分是URL編碼的怎么辦？例如，https://minorstone.com/categories/design 和 https://minorstone.com/archives/xi-tong-jia-gou-de-jing-sui-18-ge-bi-dong-de-she-ji-gai-nian-yi-lan 除了URL編碼之外是相同的。

解決問題的方法：我們可以在每個輸入URL后附加一個遞增的序列號使其唯一，然后生成哈希。然而，我們不需要在數據庫中存儲這個序列號。這種方法可能的問題可能是一個不斷增加的序列號。它會溢出嗎？附加一個遞增的序列號也將影響服務的性能。

另一種解決方案是在輸入URL后附加用戶id（userId是唯一的）。然而，如果用戶沒有登錄，我們將不得不要求用戶選擇一個唯一性鍵。

B. 離線生成鍵

我們可以設立一個獨立的鍵生成服務（KGS），預先生成隨機的六位字符串，并將其存儲在數據庫中（我們稱之為key-DB）。每當我們想要縮短一個URL，我們就會拿一個已經生成的鍵來使用。這種方式非常簡單和快速。我們不僅不需要編碼URL，而且不必擔心重復或沖突。KGS會確保插入key-DB的所有鍵都是唯一的。

**并發會引起問題嗎？**一旦一個鍵被使用，就應該在數據庫中標記，以確保它不再被使用。如果有多個服務器同時讀取鍵，我們可能會遇到兩個或更多的服務器試圖從數據庫中讀取同一個鍵的情況。我們如何解決這個并發問題？

服務器可以使用KGS在數據庫中讀取/標記鍵。KGS可以使用兩個表來存儲鍵：一個用于尚未使用的鍵，另一個用于所有已使用的鍵。一旦KGS將鍵提供給其中一個服務器，就可以將它們移動到已使用的鍵表中。KGS可以始終在內存中保留一些鍵，以便在服務器需要時快速提供。

為了簡單起見，一旦KGS在內存中加載了一些鍵，就可以將它們移動到已使用的鍵表中。這確保每個服務器得到的鍵都是唯一的。如果KGS在將所有加載的鍵分配給某個服務器之前死機，我們將會浪費這些鍵——鑒于我們擁有的鍵的數量龐大，這可能是可以接受的。

KGS還必須確保不給多個服務器相同的鍵。為此，它必須在從中移除鍵并將它們提供給服務器之前，對保存鍵的數據結構進行同步（或對其加鎖）。

key-DB的大小會是多少？使用base64編碼，我們可以生成687億個唯一的六位鍵。如果我們需要一個字節來存儲一個字母數字字符，我們可以將所有這些鍵存儲在：

6（每個鍵的字符數）* 68.7B（唯一鍵）= 412 GB

KGS會出現單點故障嗎？會的。為了解決這個問題，我們可以設置一個備用的KGS副本。當主服務器出現故障時，備用服務器可以接管，生成并提供鍵。

每個應用服務器可以從key-DB中緩存一些鍵嗎？是的，這肯定可以加快速度。然而，在這種情況下，如果應用服務器在消耗完所有鍵之前出現故障，我們將最終失去這些鍵。鑒于我們有687億個唯一的六位鍵，這是可以接受的。

我們如何執行鍵查找？我們可以在數據庫中查找鍵以獲取完整的URL。如果它存在于數據庫中，就向瀏覽器返回HTTP 302 Redirect狀態，并在請求的Location字段中傳遞存儲的URL。如果我們的系統中沒有該鍵，則返回HTTP 404 Not Found狀態或將用戶重定向回主頁。

我們應該對自定義別名設定大小限制嗎？我們的服務支持自定義別名。用戶可以自由選擇他們喜歡的key，但提供自定義別名并不是必須的。然而，為了確保我們有一個一致的URL數據庫，設定一個自定義別名的大小限制是合理的（甚至是用戶期望的）。我們假設用戶可以為每個自定義鍵指定最多16個字符（如上述數據庫模式所示）。

7、數據分區和復制

為了擴展我們的數據庫，我們需要對其進行分區，以便它能存儲數十億個URL的信息。因此，我們需要設計一個分區方案，將我們的數據劃分并存儲到不同的數據庫中。

A. 基于范圍的分區：我們可以根據哈希鍵的第一個字母在不同的分區中存儲URL。因此，我們將所有以字母“A”（和“a”）開頭的URL哈希鍵存儲在一個分區中，將以字母“B”開頭的URL存儲在另一個分區中，以此類推。這種方法被稱為基于范圍的分區。我們甚至可以將某些出現頻率較低的字母組合到一個數據庫分區中。因此，我們應開發一個靜態分區方案，始終以可預測的方式存儲/查找URL。

這種方法的主要問題是可能導致數據庫服務器不平衡。例如，我們決定將所有以字母“E”開頭的URL放入一個數據庫分區，但后來我們發現以字母“E”開頭的URL過多。

B. 基于哈希的分區：在這種方案中，我們對存儲的對象進行哈希。然后，我們根據哈希值計算使用哪個分區。在我們的情況下，我們可以獲取key或短鏈接的哈希值，以確定我們存儲數據對象的分區。

我們的哈希函數將隨機地將URL分配到不同的分區（例如，我們的哈希函數可以始終將任何key映射到[1...256]之間的一個數字）。這個數字將表示我們存儲對象的分區。

這種方法仍然可能導致分區負載過大，這可以通過使用'一致性哈希'來解決。

8、緩存

我們可以緩存頻繁訪問的URL。我們可以使用任何現成的解決方案，比如Memcached，它可以存儲完整的URL及其對應的哈希值。因此，應用服務器在訪問后端存儲之前，可以快速檢查緩存是否有所需的URL。

我們應該有多少緩存內存？我們可以從日流量的20%開始，根據客戶的使用模式，我們可以調整需要多少緩存服務器。如上所估計，我們需要170GB的內存來緩存日流量的20%。目前的一些服務器可以擁有256GB的內存，我們可以輕松將所有緩存放入一臺機器。或者，我們可以使用幾臺小一點的服務器來存儲所有這些熱門URL。

哪種緩存驅逐策略最適合我們的需求？當緩存滿了，我們想用一個新的/更熱門的URL替換一個鏈接，我們應該如何選擇？最近最少使用（LRU）可能是我們系統的一個合理策略。根據這個策略，我們首先丟棄最近最少使用的URL。我們可以使用Linked Hash Map或類似的數據結構來存儲我們的URL和哈希值，這也會記錄最近訪問過的URL。

為了進一步提高效率，我們可以復制我們的緩存服務器來分配它們之間的負載。

每個緩存副本如何更新？每當有一個緩存未命中，我們的服務器會訪問后端數據庫。當這種情況發生，我們可以更新緩存，并將新的條目傳遞給所有的緩存副本。每個副本都可以通過添加新的條目來更新其緩存。如果副本已經有了該條目，它可以簡單地忽略它。

9、負載均衡（LB）

我們可以在系統中的三個位置添加負載均衡層：

• 客戶端與應用服務器之間
• 應用服務器與數據庫服務器之間
• 應用服務器與緩存服務器之間

最初，我們可以使用一個簡單的輪詢方法，將進入的請求均等地分配到后端服務器。這種負載均衡方法簡單易行，不會引入任何額外的開銷。這種方法的另一個優點是，如果一個服務器死機，負載均衡器會將其從輪詢中移除，停止向其發送任何流量。

輪詢負載均衡的一個問題是，我們沒有考慮到服務器的負載。如果一個服務器過載或運行緩慢，負載均衡器不會停止向該服務器發送新的請求。為了處理這個問題，我們可以放置一個更優的負載均衡解決方案，它定期查詢后端服務器的負載，并根據負載情況調整流量。

10、清除或數據庫清理

key條目是否應永久存在，還是應該被清除？如果達到用戶設定的過期時間，鏈接應該怎么處理？

如果我們選擇持續尋找過期鏈接并將其刪除，這將對我們的數據庫產生很大壓力。相反，我們可以慢慢地刪除過期的鏈接，進行懶人清理。我們的服務將確保只刪除過期的鏈接，盡管有些過期鏈接可能會存在更長時間，但永遠不會被返回給用戶。

• 每當用戶試圖訪問一個已過期的鏈接，我們可以刪除該鏈接并向用戶返回錯誤。
• 我們可以設置一個單獨的清理服務，定期從我們的存儲和緩存中刪除過期的鏈接。這個服務需要非常輕量，只在預計用戶流量較低的時候運行。
• 我們可以為每個鏈接設定一個默認的過期時間（例如兩年）。
• 刪除過期鏈接后，我們可以將該key重新放回Key-DB，以供重復使用。
• 我們是否應刪除一段時間（比如說六個月）內沒有被訪問過的鏈接？這可能有點不合適。由于存儲成本越來越低，我們可以決定永久保存鏈接。

11、數據跟蹤

我們如何統計短鏈接被使用的次數、用戶的位置等信息？我們如何儲存這些統計信息？如果它是數據庫中的一部分，每次查看都需要更新，那么當一個流行的短鏈接被大量并發請求瞬間涌入時，會發生什么？

一些值得追蹤的統計數據：訪客的國家、訪問的日期和時間、引導點擊的網頁、訪問頁面的瀏覽器或平臺。

12、安全和權限

用戶能否創建私有URL或者允許特定的用戶組訪問某個URL？

我們可以在數據庫中每個URL的條目里存儲訪問權限級別（公開/私有）。我們也可以創建一個單獨的表來存儲有權訪問特定URL的用戶的UserID。如果一個用戶沒有權限但試圖訪問一個URL，我們可以返回一個錯誤（HTTP 401）。考慮到我們的數據儲存在一個類似Cassandra的NoSQL寬列數據庫中，儲存權限的表的key將是‘哈希值’（或KGS生成的key）。列將儲存有權查看URL的用戶的UserID。