??讀完這篇文章里你能收獲到
- 了解博主的短鏈生成的架構(gòu)設(shè)計思路
- 學(xué)習(xí)不同的短鏈技術(shù)方案選擇
- 學(xué)習(xí)基于混淆的自增短URL算法
- 了解博主造的輪子SuperShortLink短鏈開源項目
- 感謝點(diǎn)贊+收藏，避免下次找不到~
文章來源：http://www.zghlxwxcb.cn/news/detail-436684.html
一、需求分析
1. 短鏈生成及訪問需求
短 URL 生成器，也稱作短鏈接生成器，就是將一個比較長的 URL 生成一個比較短的URL，當(dāng)瀏覽器通過短 URL 生成器訪問這個短 URL 的時候，重定向訪問到原始的長 URL目標(biāo)服務(wù)器，訪問時序圖如下：
用戶訪問短URL時序描述：
- 由應(yīng)用調(diào)用短鏈服務(wù)生成短 URL，并將該短URL 展示給用戶
- 用戶在瀏覽器中點(diǎn)擊該短 URL 的時候，請求發(fā)送到短 URL 生成器
- 短URL 生成器返回 HTTP 重定向響應(yīng)，將用戶請求重定向到最初的原始長 URL
- 瀏覽器訪問長 URL 服務(wù)器，完成請求服務(wù)
2. 短鏈應(yīng)用授權(quán)管理需求
短鏈管理，短鏈系統(tǒng)管理員可以在管理后臺做以下操作：
- 查看已生成的短鏈列表以及短鏈的訪問次數(shù)統(tǒng)計
- 直接在線輸入長URL生成短URL
- 管理短鏈系統(tǒng)的授權(quán)秘鑰（只有已授權(quán)的應(yīng)用才可通過HTTP請求生成短鏈）
秘鑰使用時序圖如下：
秘鑰使用流程描述：
- 由管理員在管理后臺創(chuàng)建應(yīng)用秘鑰
- 將秘鑰配到應(yīng)用程序中
- 應(yīng)用程序攜帶秘鑰加密后的Token信息請求短鏈服務(wù)生成短URL
- 短鏈服務(wù)接收到請求時校驗Token是否合法，合法則返回相應(yīng)的短URL
3. 非功能性需求
- 系統(tǒng)需要保持高可用，不因單一服務(wù)器宕機(jī)而引起服務(wù)失效，即需保證服務(wù)是支持伸縮的
- 短 URL 應(yīng)該是不可猜測的，即不能猜測某個短 URL 是否存在，也不能猜測短 URL 可能對應(yīng)的長 URL 地址內(nèi)容
二、概要設(shè)計
概要設(shè)計階段主要關(guān)注短鏈服務(wù)的用例、部署模型、領(lǐng)域設(shè)計及短鏈生成方案的選擇
1. 短鏈服務(wù)用例圖
- 用戶可以訪問短URL，短鏈服務(wù)會將請求進(jìn)行重定向
- 應(yīng)用程序可以通過短鏈服務(wù)為長URL生成唯一的短URL
- 應(yīng)用程序可以存儲，統(tǒng)計分析短URL的相關(guān)數(shù)據(jù)，比如訪問次數(shù)
- 管理員可以在Web后臺檢索、查看短鏈的生成及使用情況
- 管理員可以在Web后臺管理授權(quán)訪問的應(yīng)用秘鑰
2. 整體部署模型
短鏈服務(wù)的業(yè)務(wù)邏輯比較簡單，相對比較有挑戰(zhàn)的就是高并發(fā)的短URL的訪問請求如何處理。高并發(fā)訪問主要通過負(fù)載均衡與緩存解決。具體的架構(gòu)圖如下：
3. 領(lǐng)域設(shè)計
領(lǐng)域設(shè)計這塊分為兩部分，一部分是短鏈生成記錄，另一部分是應(yīng)用授權(quán)
4. 短鏈生成技術(shù)方案選擇
短 URL 生成器的設(shè)計核心就是短 URL 的生成，即長 URL 通過某種函數(shù)，計算得到n個字符的短 URL。短 URL 有幾種不同的生成算法。由于Base64后面兩位的“+”和“/”在 URL 中會被編碼為“%2B”以及“%2F”，需要進(jìn)行再編碼，因此不考慮后兩位符號，下文皆以Base62編碼（[A-Z]，[a-z]，[0-9]）作為描述
4.1 單項散列函數(shù)生成短 URL
散列函數(shù)可以將任意長度的輸入（又叫做預(yù)映射， pre-image），通過執(zhí)行復(fù)雜的運(yùn)算，變成固定長度的輸出又叫散列值， hash value）。在短URL生成中，散列函數(shù)可用于將長URL映射到短URL，從而達(dá)到縮短URL的效果。
通常的設(shè)計方案：
- 將長URL作為散列函數(shù)的輸入
- 執(zhí)行散列函數(shù)（MD5 或者 SHA256），將長URL轉(zhuǎn)換為固定長度的哈希值
- 將哈希值進(jìn)行進(jìn)一步處理，進(jìn)行Base62編碼，防止沖突
- 將編碼后的字符串截取N個字符作為短URL
具體流程如圖：
- 優(yōu)點(diǎn)：生成速度快
- 缺點(diǎn)：存在哈希碰撞，相同的哈希值對應(yīng)不同的長URL，需要進(jìn)行特殊處理以避免這一問題。雖然哈希碰撞的概率極低，但是 Base62 編碼后再截斷的 N 個字符有可能會沖突的概率就很高了。所以在生成的時候，需要先校驗該短 URL 是否已經(jīng)映射為其他的長 URL，如果是，那么需要重新計算（換單向散列算法，或者換 Base62 編碼截斷位置）。重新計算得到的短 URL 依然可能沖突，需要再重新計算
這樣的沖突處理需要多次到存儲中查找 URL，無法保證短鏈服務(wù)的性能要求，不考慮該方案
4.2 預(yù)生成短 URL
預(yù)生成短URL是指提前生成一些短URL并保存到數(shù)據(jù)庫中，當(dāng)用戶需要縮短長URL時，直接從數(shù)據(jù)庫中獲取一個未被使用過的短URL，而不是現(xiàn)場生成新的短URL。
通常的設(shè)計方案：
- 采用隨機(jī)算法離線預(yù)生成一批短URL，為了避免短URL沖突，每次生成的時候都需要檢查該URL是否已存在
- 將預(yù)生成的短URL存到數(shù)據(jù)庫
- 從數(shù)據(jù)庫的短URL池中取一部分放到緩存中
- 當(dāng)用戶需要縮短一個長URL時，緩存中獲取一個短URL
- 當(dāng)緩存中的短URL快用完時，需從數(shù)據(jù)庫再加載一部分到緩存中
- 當(dāng)數(shù)據(jù)庫中的預(yù)生成短URL快用完時，需要生成更多的短URL并添加到數(shù)據(jù)庫中
具體流程如圖：
- 優(yōu)點(diǎn)：由于生成URL是離線計算，不會對服務(wù)器性能產(chǎn)生過大的負(fù)擔(dān)，使用的時候讀取短URL速度快
- 缺點(diǎn)：預(yù)生成短 URL 會生成大量未被使用的短URL，浪費(fèi)了存儲空間和資源。此外，如果預(yù)生成的短URL數(shù)量不足，用戶可能需要等待新的短URL被生成才能完成操作。越到后期隨機(jī)算法生成的URL產(chǎn)生沖突的概率會越大，導(dǎo)致需要對比的次數(shù)越多
由于需要提前占用大量的存儲空間，所以暫不考慮該方案
4.3 基于混淆的自增短 URL
自增短 URL 一種免沖突的算法是用自增長自然數(shù)來實現(xiàn)，即維持一個自增長的二進(jìn)制自然數(shù)，然后將該自然數(shù)進(jìn)行 Base62 編碼即可得到一系列的短 URL。這樣生成的的短 URL 必然唯一，通常采用自增序列號的方式進(jìn)行生成。原理是將每一個長鏈接映射到一個唯一的自增序列號，然后將自增序列號轉(zhuǎn)換為指定長度的短鏈接
比如：
- 自然數(shù) 1 的常規(guī)Base62 編碼是字符“B”
- 就可以用 http://1.cn/B 作為短 URL。
弊端：但是這種算法將導(dǎo)致短URL是可猜測的，只要知道了其中一個短 URL，就可以猜測下一個短 URL
為了解決上述問題，基于上面的方式在生成時加入隨機(jī)打亂編碼Base62等混淆方法，可以增加被預(yù)測的概率，增強(qiáng)短URL的安全性
通常的設(shè)計方案：
- 初始化一個計數(shù)器，用于記錄已經(jīng)生成的短URL數(shù)量
- 當(dāng)用戶輸入長URL時，將計數(shù)器自增1，并將自增后的值前面補(bǔ)0，比如自然數(shù)1變成0001
- 然后將該值倒轉(zhuǎn)，也就是0001變成1000
- 為了防止短URL被預(yù)測，對轉(zhuǎn)換后的Base62編碼進(jìn)行打亂或加密，以作混淆
- 將倒轉(zhuǎn)后的值轉(zhuǎn)換為混淆加密后的Base62編碼，得到短URL
具體流程如圖：
- 優(yōu)點(diǎn)：編碼保證絕對唯一，不會出現(xiàn)碰撞沖突，生成速度較快，不需要提前占用存儲空間
- 缺點(diǎn)：該方法需要維護(hù)一個計數(shù)器，如果生成短URL的并發(fā)量較大，性能瓶頸取決于計數(shù)器，計數(shù)器常見的方案：
- Redis原子自增
- 數(shù)據(jù)庫自增主鍵
我們就是采用了基于混淆的自增短URL，計數(shù)器避免引入過多的中間件，因此選擇了數(shù)據(jù)庫自增主鍵
三、詳細(xì)設(shè)計
在詳細(xì)設(shè)計階段，主要考慮重定向碼、高并發(fā)場景應(yīng)對方案、混淆加解密算法的解析及API授權(quán)校驗的流程
1. 混淆自增算法詳解
- 標(biāo)準(zhǔn)Base64編碼表如下：
其中“+”和“/”在 URL 中會被編碼為“%2B”以及“%2F”，需要進(jìn)行再編碼，因此直接使用標(biāo)準(zhǔn) Base64 編碼進(jìn)行短URL 編碼并不合適，所以，我們需要針對 URL 場景對 Base64 編碼進(jìn)行改造，Base64 編碼表中的 62，63 進(jìn)行編碼移除，更新為Base62編碼
1.1 混淆加密算法設(shè)計
- 將標(biāo)準(zhǔn)編碼隨機(jī)打亂 ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789
舉例：打亂成：s9LFkgy5RovixI1aOf8UhdY3r4DMplQZJXPqebE0WSjBn7wVzmN2Gc6THCAKhaut
- 6位長度標(biāo)準(zhǔn)編碼與打亂后編碼的對應(yīng)關(guān)系
| 計數(shù)器自增Id | 標(biāo)準(zhǔn)Base62編碼 | 標(biāo)準(zhǔn)Base62編碼（6位字符） | 打亂后Base62編碼 | 打亂Base62編碼（6位字符） |
|---|---|---|---|---|
| 6 | G | AAAAAG | y | sssssy |
| 66 | BE | AAAABE | 9k | ssss9k |
| 100 | Bm | AAAABm | 9E | ssss9E |
可以看出，雖然打亂了，但還順序性還是很明顯
- 將前面補(bǔ)0再倒轉(zhuǎn)，由于6位長度最大11位，為了避免倒轉(zhuǎn)后超過該數(shù)值，因此補(bǔ)到10位
| 計數(shù)器自增Id | 打亂后Base62編碼（6位字符） | 前面補(bǔ)0到10位 | 倒轉(zhuǎn)數(shù)字 | 倒轉(zhuǎn)后的打亂Base62編碼（6位字符） |
|---|---|---|---|---|
| 6 | sssssy | 0000000006 | 6000000000 | yPFrgP |
| 66 | ssss9k | 0000000066 | 6600000000 | 5xWCQH |
| 100 | ssss9E | 0000000100 | 10000000 | ssSKph |
1.2 恢復(fù)混淆解密算法設(shè)計
將請求收到的短鏈Key根據(jù)打亂后的Base62編碼轉(zhuǎn)成十進(jìn)制數(shù)，補(bǔ)0到10位，然后倒轉(zhuǎn)就得到原來的短鏈Id
| 短鏈Key | 解析后的十進(jìn)制數(shù) | 前面補(bǔ)0到10位 | 倒轉(zhuǎn)數(shù)字 |
|---|---|---|---|
| yPFrgP | 6000000000 | 6000000000 | 6 |
| 5xWCQH | 6600000000 | 6600000000 | 66 |
| ssSKph | 10000000 | 0010000000 | 100 |
1.3 算法量級支撐
| 短鏈長度 | 最大支持?jǐn)?shù) | 數(shù)據(jù)量級 |
|---|---|---|
| 5 | 99999999 | 億 |
| 6 | 9999999999 | 百億 |
| 7 | 999999999999 | 萬億 |
2. 重定向響應(yīng)碼
滿足短 URL 重定向要求的 HTTP 重定向響應(yīng)碼有 301 和 302 兩種
- 301 表示永久重定向，即瀏覽器一旦訪問過該短 URL，就將重定向的原始長 URL 緩存在本地，此后不再請求短 URL 生成器，直接根據(jù)緩存在瀏覽器（HTTP 客戶端）的長 URL 路徑進(jìn)行訪問
- 302 表示臨時重定向，每次訪問短 URL 都需要訪問短 URL 生成器
一般來說，使用 301 狀態(tài)碼可以降低短鏈服務(wù)器的負(fù)載壓力，但無法統(tǒng)計短 URL 的使用情況，而短鏈服務(wù)的架構(gòu)設(shè)計完全可以承受這些負(fù)載壓力，因此短鏈服務(wù)使用 302 狀態(tài)碼構(gòu)造重定向響應(yīng)
3. 高并發(fā)挑戰(zhàn)方案
系統(tǒng)調(diào)用可以分成兩種情況：
- 應(yīng)用請求生成短URL的過程
- 用戶訪問短URL，通過短鏈跳轉(zhuǎn)到長URL的過程
情況1：請求生成短URL不會太頻繁，因為是手動點(diǎn)擊生成的，因此第一點(diǎn)并發(fā)量會比較低，生成URL的性能瓶頸取決于計數(shù)器
情況2：由于是直接觸達(dá)客戶，一個短鏈可能被成千上萬的客戶訪問，上述部署模型中也提到，主要通過負(fù)載均衡與緩存解決，在此的緩存選擇了本地內(nèi)存緩存，減少與分布式緩存網(wǎng)絡(luò)請求的鏈路耗時，用戶訪問短鏈的泳道圖如下：
具體流程：
- 用戶點(diǎn)擊短URL，請求短鏈服務(wù)
- 短鏈服務(wù)解密短鏈Key生成短鏈的自增Id
- 通過自增Id到緩存中匹配是否有對應(yīng)的長URL
- 緩存匹配不到則根據(jù)主鍵Id查詢數(shù)據(jù)庫
- 數(shù)據(jù)庫中如果查不到長URL，則返回HTTP 404響應(yīng)
- 數(shù)據(jù)庫中如果查到長URL，則更新緩存，再更新數(shù)據(jù)庫的訪問次數(shù)，然后重定向到長URL
4. API授權(quán)校驗
授權(quán)校驗主要做了三重校驗：
- Body攜帶的時間戳timestamp必須在60秒內(nèi)
- Body攜帶的應(yīng)用Code（app_code）必須是數(shù)據(jù)庫中已存在的
- Headers攜帶的Token必須有效
Token的加密：由時間戳 + 應(yīng)用秘鑰 取大寫Md5，具體值為：
$"timestamp={timestampStr}&&app_secret={appSecretStr}".ToMd5().ToUpper()
具體的授權(quán)流程如下：
四、Web管理后臺
- 登錄頁
- 短鏈列表頁
- 在線生成頁
- 授權(quán)應(yīng)用頁
五、項目源碼
這是一個基于.NET開源的短鏈生成及監(jiān)控系統(tǒng)，它包含了在線生成短鏈、短鏈跳轉(zhuǎn)長鏈、支持短鏈訪問次數(shù)以及Web監(jiān)控頁面，可以幫助我們更容易地生成短鏈、監(jiān)控短鏈！
- https://github.com/Bryan-Cyf/SuperShortLink
- 歡迎大家提出PR，共同討論進(jìn)步
六、思考
- 用戶每次請求生成短 URL 的時候，短鏈服務(wù)都會返回一個新生成的短 URL，也就意味著，如果用戶重復(fù)提交同一個長 URL 請求生成短 URL，每次都會返回一個新的短 URL。你認(rèn)為這將導(dǎo)致什么問題？
- 用戶如果同時請求大量的無效短鏈過來，會遇到什么問題？
歡迎在評論區(qū)提出解決方法，沒有思路的可私聊或者看源碼
文章來源地址http://www.zghlxwxcb.cn/news/detail-436684.html
到了這里，關(guān)于『造輪子』億級短URL生成器的架構(gòu)設(shè)計及源碼分享的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![生成器設(shè)計模式（Builder Design Pattern）[論點(diǎn):概念、圖示、示例、框架中的應(yīng)用、場景]](https://imgs.yssmx.com/Uploads/2024/01/410797-1.png)
