項目簡介：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縮短系統應滿足以下要求：
功能性需求：
- 給定一個URL，我們的服務應生成一個更短且唯一的别名。這就是所謂的短連結。這個連結會足夠短，以便輕松複制并粘貼到應用程式中。
- 當使用者通路一個短連結時，我們的服務将它們重定向到原始連結。
- 使用者可以自定義的短連結。
- 連結将在預設的時間跨度後過期，使用者能夠指定過期時間。
非功能性需求：
- 系統應高度可用。這是必需的，因為如果我們的服務當機，所有的URL重定向會失敗
- URL 重定向需要以最小的延遲實時發生
- 縮短後的連結不可預測
擴充需求：
- 分析功能；例如，重定向發生了多少次？
- 其他服務也應通過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∗12months=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，以下是我們服務的高層次估計的概述：
| 新網址 | 200/秒 |
| URL 重定向 | 20K/秒 |
| 傳入資料 | 100KB/秒 |
| 傳出資料 | 10MB/秒 |
| 儲存5年 | 15TB |
| 緩存記憶體 | 170GB |
4、API定義
一旦我們确定了需求，接下來需要定義系統API。需要明确說明系統的預期功能。
我們可以使用SOAP或REST API來公開我們服務的功能。建立和删除URL的API定義可能如下：
createURL(api_dev_key, original_url, custom_alias=None, user_name=None, expire_date=None)
參數：
- api_dev_key（字元串）：已注冊賬戶的API開發者密鑰。此密鑰将用于，包括但不限于，根據使用者配置設定的配額限制使用者。
- original_url（字元串）：要縮短的原始URL。
- custom_alias（字元串）：URL的可選自定義鍵。
- user_name（字元串）：可選的用于編碼的使用者名。
- 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模式對了解資料在各個元件之間的流動非常有幫助，随後會引導我們進行資料分區。
我們将存儲的資料具有以下特點：
- 我們需要儲存上百億條記錄。
- 我們存儲的每個對象都非常小（小于1K）。
- 除了記錄哪個使用者建立了一個URL，記錄之間沒有關系。
- 我們的服務主要是讀取操作。
資料庫架構：
我們需要兩個表：一個用于存儲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）個字元作為鍵。這可能會導緻鍵重複；為了解決這個問題，我們可以從編碼字元串中選擇一些其他字元或交換一些字元。
我們的解決方案有哪些問題？我們的編碼方案有以下幾個問題：
- 如果多個使用者輸入同一個URL，他們可能會得到相同的縮短URL，這是不可接受的。
- 如果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。