關(guān)注轉(zhuǎn)發(fā)，不間斷分享實(shí)戰(zhàn)內(nèi)容。

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

短鏈接，通俗來說，就是將長(zhǎng)的URL網(wǎng)址，通過程序計(jì)算等方式，轉(zhuǎn)換為簡(jiǎn)短的網(wǎng)址字符串。

使用場(chǎng)景

微博和Twitter都有140字?jǐn)?shù)的限制，如果分享一個(gè)長(zhǎng)網(wǎng)址，很容易就超出限制。

營(yíng)銷短信，字?jǐn)?shù)的限制,當(dāng)字?jǐn)?shù)過長(zhǎng): 1.不美觀 2.超出字符額外收費(fèi)。

生成二維碼的原始鏈接,當(dāng)原始鏈接過長(zhǎng)時(shí),生成的二維碼過于復(fù)雜,導(dǎo)致一些像素較低的手機(jī)無法掃描.

2. 設(shè)計(jì)目標(biāo)

功能要求：

非功能性要求：

擴(kuò)展要求：

3.系統(tǒng)API

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

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

參數(shù)：

api_dev_key(string)：注冊(cè)賬號(hào)的API開發(fā)者密鑰。除其他外，這將用于根據(jù)分配的配額限制用戶。

original_url（字符串）：要縮短的原始 URL。

custom_alias（字符串）：URL 的可選自定義鍵。

user_name（字符串）：在編碼中使用的可選用戶名。

expire_date (string): 縮短 URL 的可選過期日期。

返回：（字符串）

成功插入會(huì)返回縮短的 URL；否則，它會(huì)返回錯(cuò)誤代碼。

deleteURL (api_dev_key, url_key)

其中“url_key”是一個(gè)字符串，表示要檢索的縮短的 URL；成功刪除會(huì)返回“已刪除 URL”。

如何發(fā)現(xiàn)和防止濫用？惡意用戶可以通過使用當(dāng)前設(shè)計(jì)中的所有 URL 密鑰使我們破產(chǎn)。為了防止濫用，我們可以通過他們的 api_dev_key 限制用戶。每個(gè) api_dev_key 可以限制為每個(gè)時(shí)間段內(nèi)特定數(shù)量的 URL 創(chuàng)建和重定向（每個(gè)開發(fā)者密鑰可以設(shè)置為不同的持續(xù)時(shí)間）。

4. 數(shù)據(jù)庫(kù)設(shè)計(jì)

結(jié)合儲(chǔ)存數(shù)據(jù)設(shè)計(jì)：

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

我們需要兩張表：一張用于存儲(chǔ)有關(guān) URL 映射的信息，另一張用于創(chuàng)建短鏈接的用戶數(shù)據(jù)。

應(yīng)該使用什么樣的數(shù)據(jù)庫(kù)？由于我們預(yù)計(jì)存儲(chǔ)數(shù)十億行，并且我們不需要使用對(duì)象之間的關(guān)系——NoSQL 選擇更容易擴(kuò)展

5. 基本系統(tǒng)設(shè)計(jì)與算法

在第 1 節(jié)的示例中，縮短的 URL 是“https://tinyurl.com/vzet59pa”。這個(gè) URL 的最后八個(gè)字符構(gòu)成了我們要生成的短鏈。討論以下兩種解決方案： 摘要算法、自增序列算法

方案一：摘要算法

這種算法,雖然會(huì)生成4個(gè),但是仍然存在重復(fù)幾率

方案二：自增序列算法

設(shè)置 id 自增，一個(gè) 10進(jìn)制 id 對(duì)應(yīng)一個(gè) 62進(jìn)制的數(shù)值，1對(duì)1，也就不會(huì)出現(xiàn)重復(fù)的情況。這個(gè)利用的就是低進(jìn)制轉(zhuǎn)化為高進(jìn)制時(shí)，字符數(shù)會(huì)減少的特性。

兩種算法對(duì)比

第一種算法的好處就是簡(jiǎn)單好理解，永不重復(fù)。但是短碼的長(zhǎng)度不固定，隨著 id 變大從一位長(zhǎng)度開始遞增。如果非要讓短碼長(zhǎng)度固定也可以就是讓 id 從指定的數(shù)字開始遞增就可以了。百度短網(wǎng)址用的這種算法。

6. 數(shù)據(jù)分區(qū)和復(fù)制

為了擴(kuò)展我們的數(shù)據(jù)庫(kù)，我們需要對(duì)其進(jìn)行分區(qū)，以便它可以存儲(chǔ)有關(guān)數(shù)十億個(gè) URL 的信息。因此，我們需要開發(fā)一種分區(qū)方案，將我們的數(shù)據(jù)劃分并存儲(chǔ)到不同的數(shù)據(jù)庫(kù)服務(wù)器中。

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

這種方法的主要問題是它可能導(dǎo)致數(shù)據(jù)庫(kù)服務(wù)器不平衡。例如，我們決定將所有以字母“E”開頭的 URL 放入 DB 分區(qū)，但后來我們意識(shí)到我們有太多以字母“E”開頭的 URL。

另外基于散列的分區(qū)：在這個(gè)方案中，我們獲取我們正在存儲(chǔ)的對(duì)象的散列。然后我們根據(jù)哈希計(jì)算要使用的分區(qū)。在我們的例子中，我們可以使用“鍵”或短鏈接的哈希值來確定我們存儲(chǔ)數(shù)據(jù)對(duì)象的分區(qū)。

我們的散列函數(shù)會(huì)將 URL 隨機(jī)分布到不同的分區(qū)中（例如，我們的散列函數(shù)總是可以將任何“鍵”映射到 [1…256] 之間的數(shù)字）。這個(gè)數(shù)字將代表我們存儲(chǔ)對(duì)象的分區(qū)。

這種方法仍然會(huì)導(dǎo)致分區(qū)過載，這可以使用一致哈希解決。

7.緩存

可以緩存經(jīng)常訪問的 URL，結(jié)合緩存中間件例如 Memcached、redis，它可以存儲(chǔ)完整的 URL 及其各自的哈希值。因此，應(yīng)用服務(wù)器在訪問后端存儲(chǔ)之前，可以快速檢查緩存是否具有所需的 URL。

我們應(yīng)該有多少緩存內(nèi)存？我們可以從每天 20% 的流量開始，根據(jù)客戶的使用模式，我們可以調(diào)整我們需要多少緩存服務(wù)器。如上所述，我們需要 170GB 的內(nèi)存來緩存 20% 的日常流量。由于現(xiàn)代服務(wù)器可以擁有 256GB 內(nèi)存，我們可以輕松地將所有緩存放入一臺(tái)機(jī)器中。或者，我們可以使用幾個(gè)較小的服務(wù)器來存儲(chǔ)所有這些熱門 URL。

哪種緩存驅(qū)逐策略最適合我們的需求？當(dāng)緩存已滿，并且我們想用更新/更熱的 URL 替換鏈接時(shí)，我們將如何選擇？最近最少使用 (LRU) 可能是我們系統(tǒng)的合理策略。根據(jù)此政策，會(huì)首先丟棄最近最少使用的 URL，可以使用 Linked Hash Map 或類似的數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)我們的 URL 和哈希，這也將跟蹤最近訪問過的 URL。

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

8.負(fù)載均衡器（LB）

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

9. 清除或數(shù)據(jù)庫(kù)清理

條目應(yīng)該永遠(yuǎn)存在，還是應(yīng)該被清除？如果達(dá)到用戶指定的過期時(shí)間，鏈接會(huì)發(fā)生什么？

如果我們選擇不斷搜索過期鏈接來刪除它們，這會(huì)給我們的數(shù)據(jù)庫(kù)帶來很大的壓力。相反，我們可以慢慢刪除過期鏈接并進(jìn)行惰性清理。我們的服務(wù)會(huì)確保只刪除過期的鏈接。

• 每當(dāng)用戶嘗試訪問過期鏈接時(shí)，我們都可以刪除該鏈接并向用戶返回錯(cuò)誤。
• 可以定期運(yùn)行單獨(dú)的清理服務(wù)，以從我們的存儲(chǔ)和緩存中刪除過期鏈接。該服務(wù)應(yīng)該非常輕量級(jí)，并且僅在預(yù)計(jì)用戶流量較低時(shí)才運(yùn)行。
• 可以為每個(gè)鏈接設(shè)置一個(gè)默認(rèn)的過期時(shí)間（例如，兩年）。
• 刪除過期鏈接后，我們可以將密鑰放回密鑰數(shù)據(jù)庫(kù)中以供重復(fù)使用。
• 我們是否應(yīng)該刪除在一段時(shí)間內(nèi)（比如六個(gè)月）未訪問過的鏈接？這可能很棘手。由于存儲(chǔ)變得越來越便宜，我們可以決定永遠(yuǎn)保持鏈接。

10. 安全和權(quán)限

用戶能否創(chuàng)建私有 URL 或允許一組特定用戶訪問 URL？

可以將權(quán)限級(jí)別（公共/私有）與數(shù)據(jù)庫(kù)中的每個(gè) URL 一起存儲(chǔ)，還可以創(chuàng)建一個(gè)單獨(dú)的表來存儲(chǔ)有權(quán)查看特定 URL 的 UserID。如果用戶沒有權(quán)限并嘗試訪問 URL，可以發(fā)回錯(cuò)誤 (HTTP 401)。鑒于我們將數(shù)據(jù)存儲(chǔ)在像 Cassandra 這樣的 NoSQL 寬列數(shù)據(jù)庫(kù)中，表存儲(chǔ)權(quán)限的鍵將是“哈?！保ɑ?KGS 生成的“鍵”）。這些列將存儲(chǔ)那些有權(quán)查看 URL 的用戶的用戶 ID。