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

現(xiàn)在讓我們設(shè)計(jì)一個(gè)像TinyURL一樣的URL縮短服務(wù)。這個(gè)服務(wù)將提供短別名來重定向到長URL。

類似的產(chǎn)品有：bit.ly, ow.ly, short.io

系統(tǒng)難度級別：初級

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

URL縮短用于為長URL創(chuàng)建更短的別名。我們將這些縮短后的別名稱為“短鏈接”。當(dāng)用戶點(diǎn)擊這些短鏈接時(shí)，他們會被重定向到原始URL。短鏈接在顯示、打印、發(fā)送信息或發(fā)推文時(shí)節(jié)省了大量空間。此外，用戶輸入錯(cuò)誤的可能性也會隨著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幾乎只有實(shí)際URL的三分之一大小。

URL縮短用于優(yōu)化設(shè)備間的鏈接，跟蹤單個(gè)鏈接以分析觀眾，測量廣告活動(dòng)的效果，或者隱藏關(guān)聯(lián)的原始URL。

如果你之前沒有使用過tinyurl.com，請嘗試創(chuàng)建一個(gè)新的縮短URL，并花些時(shí)間了解他們服務(wù)提供的各種選項(xiàng)。這將對你理解這一章節(jié)有很大幫助。

2、系統(tǒng)的需求和目標(biāo)

你應(yīng)該在面試開始時(shí)就明確需求。務(wù)必提問，以找出面試官心中系統(tǒng)的準(zhǔn)確范圍。

我們的URL縮短系統(tǒng)應(yīng)滿足以下要求：

功能性需求：

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

非功能性需求：

1. 系統(tǒng)應(yīng)高度可用。這是必需的，因?yàn)槿绻覀兊姆?wù)宕機(jī)，所有的URL重定向會失敗
2. URL 重定向需要以最小的延遲實(shí)時(shí)發(fā)生
3. 縮短后的鏈接不可預(yù)測

擴(kuò)展需求：

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

3、容量估計(jì)和約束

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

流量估計(jì)：假設(shè)我們每月將有5億次新的URL縮短，以100:1的讀/寫比率，我們可以預(yù)期在同一時(shí)期內(nèi)有500億次重定向：

100?500M=>50B

我們系統(tǒng)的每秒查詢數(shù)（QPS）是多少？每秒新的URL縮短數(shù)量：

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

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

100 * 200 URLs/s = 20K/s

存儲估計(jì)：我們假設(shè)存儲每個(gè)URL縮短請求（及關(guān)聯(lián)的縮短鏈接）5年。由于我們預(yù)計(jì)每月會有5億個(gè)新的URL，因此我們預(yù)計(jì)存儲的對象總數(shù)將是300億個(gè)：

500million?5years?12mnotallow=30billion

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

30billion?500bytes=15TB

帶寬估計(jì)：對于寫請求，由于我們預(yù)計(jì)每秒會有200個(gè)新的URL，我們的服務(wù)總?cè)胝緮?shù)據(jù)將是每秒100KB：

200?500bytes=100KB/s

對于讀請求，由于我們預(yù)計(jì)每秒將有大約20K個(gè)URL重定向，我們的服務(wù)總出站數(shù)據(jù)將是每秒10MB：

20K?500bytes= 10MB/s

內(nèi)存估計(jì)：如果我們想緩存一些經(jīng)常訪問的熱門URL，我們需要多少內(nèi)存來存儲它們？如果我們遵循80-20的規(guī)則，即20%的URL產(chǎn)生80%的流量，我們希望緩存這20%的熱門URL。

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

20K?3600seconds?24hours= 1.7billion

為了緩存這20%的請求，我們需要170GB的內(nèi)存。

0.2?1.7billion?500bytes= 170GB

這里需要注意的一點(diǎn)是，由于會有許多重復(fù)請求（相同的URL），我們實(shí)際的內(nèi)存使用量將少于170GB。

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

4、API定義

一旦我們確定了需求，接下來需要定義系統(tǒng)API。需要明確說明系統(tǒng)的預(yù)期功能。

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

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

參數(shù)：

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

返回：（字符串）

成功插入返回縮短后的URL；否則，返回一個(gè)錯(cuò)誤碼。

deleteURL(api_dev_key, url_key)

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

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

5、數(shù)據(jù)庫設(shè)計(jì)

在早期系統(tǒng)設(shè)計(jì)階段定義DB模式對理解數(shù)據(jù)在各個(gè)組件之間的流動(dòng)非常有幫助，隨后會引導(dǎo)我們進(jìn)行數(shù)據(jù)分區(qū)。

我們將存儲的數(shù)據(jù)具有以下特點(diǎn)：

1. 我們需要儲存上百億條記錄。
2. 我們存儲的每個(gè)對象都非常?。ㄐ∮?K）。
3. 除了記錄哪個(gè)用戶創(chuàng)建了一個(gè)URL，記錄之間沒有關(guān)系。
4. 我們的服務(wù)主要是讀取操作。

數(shù)據(jù)庫架構(gòu)：

我們需要兩個(gè)表：一個(gè)用于存儲URL映射信息，另一個(gè)用于存儲創(chuàng)建短鏈接的用戶的數(shù)據(jù)。

我們應(yīng)該使用什么類型的數(shù)據(jù)庫？由于我們預(yù)計(jì)將存儲數(shù)十億行，而且我們不需要使用對象之間的關(guān)系—一個(gè)NoSQL存儲，如DynamoDB，Cassandra或Riak會是一個(gè)更好的選擇。一個(gè)NoSQL選擇也將更容易擴(kuò)展。

6、基礎(chǔ)系統(tǒng)設(shè)計(jì)和算法

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

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

A. 編碼實(shí)際的URL

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

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

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

假設(shè)對于我們的系統(tǒng)來說，有687億個(gè)唯一字符串的六個(gè)字符鍵就足夠了。

如果我們使用MD5算法作為我們的哈希函數(shù)，它將產(chǎn)生一個(gè)128位的哈希值。經(jīng)過Base64編碼后，我們會得到一個(gè)超過21個(gè)字符的字符串（因?yàn)槊總€(gè)Base64字符編碼了哈希值的6位）?，F(xiàn)在我們每個(gè)短鍵只有6（或8）個(gè)字符的空間；那么我們怎么選擇我們的鍵呢？我們可以取前6（或8）個(gè)字符作為鍵。這可能會導(dǎo)致鍵重復(fù)；為了解決這個(gè)問題，我們可以從編碼字符串中選擇一些其他字符或交換一些字符。

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

1. 如果多個(gè)用戶輸入同一個(gè)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編碼之外是相同的。

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

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

B. 離線生成鍵

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

**并發(fā)會引起問題嗎？**一旦一個(gè)鍵被使用，就應(yīng)該在數(shù)據(jù)庫中標(biāo)記，以確保它不再被使用。如果有多個(gè)服務(wù)器同時(shí)讀取鍵，我們可能會遇到兩個(gè)或更多的服務(wù)器試圖從數(shù)據(jù)庫中讀取同一個(gè)鍵的情況。我們?nèi)绾谓鉀Q這個(gè)并發(fā)問題？

服務(wù)器可以使用KGS在數(shù)據(jù)庫中讀取/標(biāo)記鍵。KGS可以使用兩個(gè)表來存儲鍵：一個(gè)用于尚未使用的鍵，另一個(gè)用于所有已使用的鍵。一旦KGS將鍵提供給其中一個(gè)服務(wù)器，就可以將它們移動(dòng)到已使用的鍵表中。KGS可以始終在內(nèi)存中保留一些鍵，以便在服務(wù)器需要時(shí)快速提供。

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

KGS還必須確保不給多個(gè)服務(wù)器相同的鍵。為此，它必須在從中移除鍵并將它們提供給服務(wù)器之前，對保存鍵的數(shù)據(jù)結(jié)構(gòu)進(jìn)行同步（或?qū)ζ浼渔i）。

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

6（每個(gè)鍵的字符數(shù)）* 68.7B（唯一鍵）= 412 GB

KGS會出現(xiàn)單點(diǎn)故障嗎？會的。為了解決這個(gè)問題，我們可以設(shè)置一個(gè)備用的KGS副本。當(dāng)主服務(wù)器出現(xiàn)故障時(shí)，備用服務(wù)器可以接管，生成并提供鍵。

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

我們?nèi)绾螆?zhí)行鍵查找？我們可以在數(shù)據(jù)庫中查找鍵以獲取完整的URL。如果它存在于數(shù)據(jù)庫中，就向?yàn)g覽器返回HTTP 302 Redirect狀態(tài)，并在請求的Location字段中傳遞存儲的URL。如果我們的系統(tǒng)中沒有該鍵，則返回HTTP 404 Not Found狀態(tài)或?qū)⒂脩糁囟ㄏ蚧刂黜摗?/p>

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

7、數(shù)據(jù)分區(qū)和復(fù)制

為了擴(kuò)展我們的數(shù)據(jù)庫，我們需要對其進(jìn)行分區(qū)，以便它能存儲數(shù)十億個(gè)URL的信息。因此，我們需要設(shè)計(jì)一個(gè)分區(qū)方案，將我們的數(shù)據(jù)劃分并存儲到不同的數(shù)據(jù)庫中。

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

這種方法的主要問題是可能導(dǎo)致數(shù)據(jù)庫服務(wù)器不平衡。例如，我們決定將所有以字母“E”開頭的URL放入一個(gè)數(shù)據(jù)庫分區(qū)，但后來我們發(fā)現(xiàn)以字母“E”開頭的URL過多。

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

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

這種方法仍然可能導(dǎo)致分區(qū)負(fù)載過大，這可以通過使用'一致性哈希'來解決。

8、緩存

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

我們應(yīng)該有多少緩存內(nèi)存？我們可以從日流量的20%開始，根據(jù)客戶的使用模式，我們可以調(diào)整需要多少緩存服務(wù)器。如上所估計(jì)，我們需要170GB的內(nèi)存來緩存日流量的20%。目前的一些服務(wù)器可以擁有256GB的內(nèi)存，我們可以輕松將所有緩存放入一臺機(jī)器?；蛘?，我們可以使用幾臺小一點(diǎn)的服務(wù)器來存儲所有這些熱門URL。

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

為了進(jìn)一步提高效率，我們可以復(fù)制我們的緩存服務(wù)器來分配它們之間的負(fù)載。

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

9、負(fù)載均衡（LB）

我們可以在系統(tǒng)中的三個(gè)位置添加負(fù)載均衡層：

• 客戶端與應(yīng)用服務(wù)器之間
• 應(yīng)用服務(wù)器與數(shù)據(jù)庫服務(wù)器之間
• 應(yīng)用服務(wù)器與緩存服務(wù)器之間

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

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

10、清除或數(shù)據(jù)庫清理

key條目是否應(yīng)永久存在，還是應(yīng)該被清除？如果達(dá)到用戶設(shè)定的過期時(shí)間，鏈接應(yīng)該怎么處理？

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

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

11、數(shù)據(jù)跟蹤

我們?nèi)绾谓y(tǒng)計(jì)短鏈接被使用的次數(shù)、用戶的位置等信息？我們?nèi)绾蝺Υ孢@些統(tǒng)計(jì)信息？如果它是數(shù)據(jù)庫中的一部分，每次查看都需要更新，那么當(dāng)一個(gè)流行的短鏈接被大量并發(fā)請求瞬間涌入時(shí)，會發(fā)生什么？

一些值得追蹤的統(tǒng)計(jì)數(shù)據(jù)：訪客的國家、訪問的日期和時(shí)間、引導(dǎo)點(diǎn)擊的網(wǎng)頁、訪問頁面的瀏覽器或平臺。

12、安全和權(quán)限

用戶能否創(chuàng)建私有URL或者允許特定的用戶組訪問某個(gè)URL？

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