關(guān)注轉(zhuǎn)發(fā)，不間斷分享實戰(zhàn)內(nèi)容。
1. 為什么我們需要 URL 縮短？
短鏈接，通俗來說，就是將長的URL網(wǎng)址，通過程序計算等方式，轉(zhuǎn)換為簡短的網(wǎng)址字符串。
使用場景
微博和Twitter都有140字?jǐn)?shù)的限制，如果分享一個長網(wǎng)址，很容易就超出限制。
營銷短信，字?jǐn)?shù)的限制,當(dāng)字?jǐn)?shù)過長: 1.不美觀 2.超出字符額外收費。
生成二維碼的原始鏈接,當(dāng)原始鏈接過長時,生成的二維碼過于復(fù)雜,導(dǎo)致一些像素較低的手機無法掃描.
2. 設(shè)計目標(biāo)
功能要求：
非功能性要求：
擴展要求：
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)：注冊賬號的API開發(fā)者密鑰。除其他外，這將用于根據(jù)分配的配額限制用戶。
original_url（字符串）：要縮短的原始 URL。
custom_alias（字符串）：URL 的可選自定義鍵。
user_name（字符串）：在編碼中使用的可選用戶名。
expire_date (string): 縮短 URL 的可選過期日期。
返回：（字符串）
成功插入會返回縮短的 URL；否則，它會返回錯誤代碼。
deleteURL (api_dev_key, url_key)
其中“url_key”是一個字符串，表示要檢索的縮短的 URL；成功刪除會返回“已刪除 URL”。
如何發(fā)現(xiàn)和防止濫用？惡意用戶可以通過使用當(dāng)前設(shè)計中的所有 URL 密鑰使我們破產(chǎn)。為了防止濫用，我們可以通過他們的 api_dev_key 限制用戶。每個 api_dev_key 可以限制為每個時間段內(nèi)特定數(shù)量的 URL 創(chuàng)建和重定向（每個開發(fā)者密鑰可以設(shè)置為不同的持續(xù)時間）。
4. 數(shù)據(jù)庫設(shè)計
結(jié)合儲存數(shù)據(jù)設(shè)計：
數(shù)據(jù)庫架構(gòu)：
我們需要兩張表：一張用于存儲有關(guān) URL 映射的信息，另一張用于創(chuàng)建短鏈接的用戶數(shù)據(jù)。
應(yīng)該使用什么樣的數(shù)據(jù)庫？由于我們預(yù)計存儲數(shù)十億行，并且我們不需要使用對象之間的關(guān)系——NoSQL 選擇更容易擴展
5. 基本系統(tǒng)設(shè)計與算法
在第 1 節(jié)的示例中，縮短的 URL 是“https://tinyurl.com/vzet59pa”。這個 URL 的最后八個字符構(gòu)成了我們要生成的短鏈。討論以下兩種解決方案： 摘要算法、自增序列算法
方案一：摘要算法
這種算法,雖然會生成4個,但是仍然存在重復(fù)幾率
方案二：自增序列算法
設(shè)置 id 自增，一個 10進(jìn)制 id 對應(yīng)一個 62進(jìn)制的數(shù)值，1對1，也就不會出現(xiàn)重復(fù)的情況。這個利用的就是低進(jìn)制轉(zhuǎn)化為高進(jìn)制時，字符數(shù)會減少的特性。
兩種算法對比
第一種算法的好處就是簡單好理解，永不重復(fù)。但是短碼的長度不固定，隨著 id 變大從一位長度開始遞增。如果非要讓短碼長度固定也可以就是讓 id 從指定的數(shù)字開始遞增就可以了。百度短網(wǎng)址用的這種算法。
6. 數(shù)據(jù)分區(qū)和復(fù)制
為了擴展我們的數(shù)據(jù)庫，我們需要對其進(jìn)行分區(qū)，以便它可以存儲有關(guān)數(shù)十億個 URL 的信息。因此，我們需要開發(fā)一種分區(qū)方案，將我們的數(shù)據(jù)劃分并存儲到不同的數(shù)據(jù)庫服務(wù)器中。
一個基于范圍的分區(qū)：我們可以根據(jù)哈希鍵的第一個字母將 URL 存儲在單獨的分區(qū)中。因此，我們將所有以字母“A”（和“a”）開頭的 URL 哈希鍵保存在一個分區(qū)中，將那些以字母“B”開頭的 URL 哈希鍵保存在另一個分區(qū)中，依此類推。這種方法稱為基于范圍的分區(qū)。我們甚至可以將某些不太頻繁出現(xiàn)的字母組合到一個數(shù)據(jù)庫分區(qū)中。因此，我們應(yīng)該開發(fā)一種靜態(tài)分區(qū)方案，以始終以可預(yù)測的方式存儲/查找 URL。
這種方法的主要問題是它可能導(dǎo)致數(shù)據(jù)庫服務(wù)器不平衡。例如，我們決定將所有以字母“E”開頭的 URL 放入 DB 分區(qū)，但后來我們意識到我們有太多以字母“E”開頭的 URL。
另外基于散列的分區(qū)：在這個方案中，我們獲取我們正在存儲的對象的散列。然后我們根據(jù)哈希計算要使用的分區(qū)。在我們的例子中，我們可以使用“鍵”或短鏈接的哈希值來確定我們存儲數(shù)據(jù)對象的分區(qū)。
我們的散列函數(shù)會將 URL 隨機分布到不同的分區(qū)中（例如，我們的散列函數(shù)總是可以將任何“鍵”映射到 [1…256] 之間的數(shù)字）。這個數(shù)字將代表我們存儲對象的分區(qū)。
這種方法仍然會導(dǎo)致分區(qū)過載，這可以使用一致哈希解決。
7.緩存
可以緩存經(jīng)常訪問的 URL，結(jié)合緩存中間件例如 Memcached、redis，它可以存儲完整的 URL 及其各自的哈希值。因此，應(yīng)用服務(wù)器在訪問后端存儲之前，可以快速檢查緩存是否具有所需的 URL。
我們應(yīng)該有多少緩存內(nèi)存？我們可以從每天 20% 的流量開始，根據(jù)客戶的使用模式，我們可以調(diào)整我們需要多少緩存服務(wù)器。如上所述，我們需要 170GB 的內(nèi)存來緩存 20% 的日常流量。由于現(xiàn)代服務(wù)器可以擁有 256GB 內(nèi)存，我們可以輕松地將所有緩存放入一臺機器中?；蛘撸覀兛梢允褂脦讉€較小的服務(wù)器來存儲所有這些熱門 URL。
哪種緩存驅(qū)逐策略最適合我們的需求？當(dāng)緩存已滿，并且我們想用更新/更熱的 URL 替換鏈接時，我們將如何選擇？最近最少使用 (LRU) 可能是我們系統(tǒng)的合理策略。根據(jù)此政策，會首先丟棄最近最少使用的 URL，可以使用 Linked Hash Map 或類似的數(shù)據(jù)結(jié)構(gòu)來存儲我們的 URL 和哈希，這也將跟蹤最近訪問過的 URL。
如何更新每個緩存副本？每當(dāng)緩存未命中時，我們的服務(wù)器就會訪問后端數(shù)據(jù)庫。每當(dāng)發(fā)生這種情況時，我們都可以更新緩存并將新條目傳遞給所有緩存副本。每個副本都可以通過添加新條目來更新其緩存。如果副本已經(jīng)有該條目，它可以簡單地忽略它。
8.負(fù)載均衡器（LB）
我們可以在系統(tǒng)的三個地方添加負(fù)載均衡層：
9. 清除或數(shù)據(jù)庫清理
條目應(yīng)該永遠(yuǎn)存在，還是應(yīng)該被清除？如果達(dá)到用戶指定的過期時間，鏈接會發(fā)生什么？
如果我們選擇不斷搜索過期鏈接來刪除它們，這會給我們的數(shù)據(jù)庫帶來很大的壓力。相反，我們可以慢慢刪除過期鏈接并進(jìn)行惰性清理。我們的服務(wù)會確保只刪除過期的鏈接。
- 每當(dāng)用戶嘗試訪問過期鏈接時，我們都可以刪除該鏈接并向用戶返回錯誤。
- 可以定期運行單獨的清理服務(wù)，以從我們的存儲和緩存中刪除過期鏈接。該服務(wù)應(yīng)該非常輕量級，并且僅在預(yù)計用戶流量較低時才運行。
- 可以為每個鏈接設(shè)置一個默認(rèn)的過期時間（例如，兩年）。
- 刪除過期鏈接后，我們可以將密鑰放回密鑰數(shù)據(jù)庫中以供重復(fù)使用。
- 我們是否應(yīng)該刪除在一段時間內(nèi)（比如六個月）未訪問過的鏈接？這可能很棘手。由于存儲變得越來越便宜，我們可以決定永遠(yuǎn)保持鏈接。
10. 安全和權(quán)限
用戶能否創(chuàng)建私有 URL 或允許一組特定用戶訪問 URL？
可以將權(quán)限級別（公共/私有）與數(shù)據(jù)庫中的每個 URL 一起存儲，還可以創(chuàng)建一個單獨的表來存儲有權(quán)查看特定 URL 的 UserID。如果用戶沒有權(quán)限并嘗試訪問 URL，可以發(fā)回錯誤 (HTTP 401)。鑒于我們將數(shù)據(jù)存儲在像 Cassandra 這樣的 NoSQL 寬列數(shù)據(jù)庫中，表存儲權(quán)限的鍵將是“哈?！保ɑ?KGS 生成的“鍵”）。這些列將存儲那些有權(quán)查看 URL 的用戶的用戶 ID。
