高併發短鏈系統設計

注：本文均爲韓宇的胡思亂寫，你隨便抄

博客

https://hanyu.cool

背景

什麼是短鏈

一個長的網址鏈接，轉換爲一個短的網址鏈接。
比如我發微博內容帶有 https://blog.hanyu.cool/about/ 鏈接時，鏈接會自動轉換成 https://t.cn/A6NlWmYi 這樣的短網址。

微博的短網址域名爲：t.cn，騰訊的短網址域名爲 url.cn，閱讀本文後，就可以自己實現一個高性能短鏈服務。

短鏈的作用

原理與實現

核心原理

實現過程

生成短鏈主要有兩種方式，哈希和 ID 生成器。

哈希

哈希算法

哈希算法可以將一個不管多長的字符串，轉化成一個長度固定的哈希值，所以可以利用哈希算法，來生成短網址。
常用的哈希算法如 MD5、SHA、MurMurHash、CRC32 等。
短鏈不需要考慮反向解密難度，只需要考慮計算速度快、衝突概率小即可。
目前應用比較廣泛非加密算法是 2008 年被髮明的 MurmurHash，據資料顯示，現在已經廣泛應用到 Redis、MemCache、Cassandra、HBase、Lucene 等軟件中，MurmurHash 算法具體實現可自行去了解，此處不展開（因爲我懂得不多）。
MurmurHash 計算可選長度 128 位、32 位等，位數多碰撞的概率就小，如果短鏈系統用的人不多，可以選擇 32 位，這樣生成的短鏈更短。
短鏈服務端接收到生成的請求後，可以把長鏈做 MurmurHash 計算，可以得到的一個哈希值，將哈希值與短鏈域名拼接，即可得到完整短鏈，如：   t.cn/111111111

進制轉換

如上所示，MurmurHash 計算後得到的結果並不算短，我們可以優化一下，常用的方式是將 10 進制轉換成 62 進制。
10 進制轉換 62 進制的邏輯就是，一直循環用 62 取餘然後倒序：

最終 t.cn/111111111 用 62 進製表示的短鏈就是 t.cn/7WD4h 。
假設生成 6 位字符的短鏈：
10 進制 最大隻能生成 10 ^ 6 - 1 = 999999 個
16 進制 最大隻能生成 16 ^ 6 - 1 = 16777215 個
62 進制 最大竟能生成 62 ^ 6 - 1 = 56800235583 個
A-Z a-z 0-9 剛好等於 62 位。

如果使用 128 進制，網址會更短，但之所以不使用 128 進制，是因爲可能會出現大量的不常用字符比如 #%& 等，不利於記憶和傳播。

哈希衝突

即使概率非常小，但哈希算法也可能會發生哈希衝突，也就是兩個不同的原始長網址哈希後得到了相同的短網址，短鏈服務將無法判斷當前的短網址對應的原始網址是哪個。

通常我們都會使用數據庫如配合緩存來存儲長短網址的映射關係，過程如下：

ID 生成器

除了通過哈希的方式，我們還可以通過各類 ID 生成器來進行短鏈生成。

ID 生成

包括但不限於：

例如通過數據庫自增 ID 拿到一個新的 ID，然後將 ID 進行 62 進制轉換，形成短鏈，將短鏈和原始網址映射關係存入庫中，當然，如果不怕暴露信息的情況下，ID 也可以不進行哈希。

二義性

使用 ID 生成器生成可能會存在二義性，也就是說一個原始長網址，經過兩次生成得到的短網址不一樣，解決思路如下:

高併發優化

爲了應對高併發的生成和訪問，我們需要對之前的短鏈系統做一定的優化。

數據庫索引

以生成的短鏈作爲數據庫唯一索引，這樣在生成短鏈後準備存入映射關係時，不必從數據庫先進行查找判重，而是直接進行數據庫的插入，如果捕獲了唯一索引異常，說明有衝突，再進行二次哈希即可。
這樣在生成短鏈時，減少了一次 SQL 查詢操作，同時也能利用到索引高效訪問。

布隆過濾器

布隆過濾器的原理是使用位圖和多次哈希計算判斷數據是否存在。不存儲數據本身，而是隻標識某數據的 “存在性”。

場景 1：對於之前我們使用哈希的方式進行短鏈生成，可以把已經生成的短網址，構建成布隆過濾器，長度是 10 億的布隆過濾器，也只需要 125MB 左右的內存空間。
有新的短鏈要生成的時候，我們使用該短鏈去布隆過濾器裏查找，如果不存在，那就一定不存在，我們直接將新生成的長短網址映射關係存儲即可。

場景 2：對於使用 ID 生成器的二義性問題，我們也可以通過布隆過濾器解決。
我們將接之前都已經存儲好的長鏈構建成布隆過濾器，後續接收到生成短鏈的請求時，先拿原始網址去布隆過濾器裏查找

多級緩存

我們可以將長短網址的映射關係存入本地緩存如 Guava 作爲一級緩存，同時存入 Redis 作爲二級緩存。
同時還可以採用 LRU 緩存過期淘汰，減少無畏的內存消耗。
無論是生成時還是訪問時，都可以先從一二級緩存中進行查找，大大提高效率。

並且，Guava 和 Redis 都有布隆過濾器的接口實現，如果使用布隆過濾器，沒有特殊必要的話不必自己造輪子。

前置發號器

我們可以採用類似大禹治水的分治、分流思想。

將 ID 生成器服務上層放置多個發號器（服務 + 隊列），生成器在啓動時，批量預生成一批短鏈給各個發號器，比如給每個發號器預生成 3000 個短鏈，當發號器內數量少於 200 時，主動向生成器取一批號。
這樣就提高了發號的併發能力，同時生成器也的大量計算操作也不受高併發請求線程的影響。

好啦，今天就到這裏，如有錯誤或有問題請去博客找我吧~

注：布隆過濾器
布隆過濾器是一種概率型數據結構，它的特點是高效的插入和查詢，能確定某個字符串一定存在或者可能存在。布隆過濾器不存儲具體數據，所以佔用空間小，查詢結果存在誤差，但誤差可控，同時不支持刪除操作。布隆過濾器爲了節約內存，是使用的位圖。
（1）一個巨大的數據文件，需要知道是否存在某個 key，如果把整個文件讀取進行查找，這個效率就比較低。那麼可以添加一個布隆過濾器，插入數據時對 key 做標識，查詢 key 是否存在時直接查詢布隆過濾器。
（2）一個數據庫查詢，想要查詢數據庫中是否存在 key，可以添加一個布隆過濾器，查詢 key 時直接查詢布隆過濾器，不需要 IO 操作，大大提升查詢效率。

一個元素加入位圖時，通過 k 個 hash 函數將元素映射到位圖的 k 個點，並把它們置 1；當檢索時，再通過 k 個 hash 函數運算檢查位圖的 k 個點是否都爲 1；如果有不爲 1 的點，那麼認爲該 key 不存在；如果全部爲 1，則可能存在。
只要有一個槽位爲 0，則 key 一定不存在；如果 key 映射的所有槽位都爲 1，不能說明一定存在，只能說明可能存在。
常見使用場景： 爬蟲去重、解決緩存穿透、反垃圾郵件等。

注：snowflake
Twitter 開源的分佈式 ID 生成算法，保證大規模生成唯一的 ID 號。
優點是：高性能，低延遲；獨立的應用；按時間有序。
缺點是：需要獨立的開發和部署。要求機器時鐘同步（到秒級即可），需要解決時鐘回撥問題，如果某臺機器的系統時鐘回撥，有可能造成 ID 衝突，或 ID 亂序。
41 位的時間序列（精確到毫秒，41 位的長度可以使用 69 年）；
10 位的機器標識（10 位的長度最多支持部署 1024 個節點）；
12 位的計數順序號（12 位的計數順序號支持每個節點每毫秒產生 4096 個 ID 序號）最高位是符號位，始終爲 0。

注：301 和 302 狀態碼
301 重定向（301 Move Permanently），指頁面永久性轉移，表示爲資源或頁面永久性地轉移到了另一個位置。301 是 HTTP 協議中的一種狀態碼，當用戶或搜索引擎向服務器發出瀏覽請求時，服務器返回的 HTTP 數據流中頭信息（header）中包含狀態碼 301 ，表示該資源已經永久改變了位置。
301 重定向是一種非常重要的 " 自動轉向 “技術，網址重定向最爲可行的一種方法。
301 重定向是頁面永久性轉移，搜索引擎在抓取新內容的同時也將舊的網址替換成重定向之後的網址；
302 重定向是頁面暫時性轉移，搜索引擎會抓取新的內容而保存舊的網址並認爲新的網址只是暫時的。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/5H8SSBkxngSzkN2Hin8njQ

猜你喜歡