【原創】這可能是東半球最接地氣的短鏈接系統設計
- 2019 年 11 月 10 日
- 筆記
引言
今天下午，煙哥和同事在廁所里排隊等坑的時候(人多坑少)。想像一下一個場景，我正在一邊排隊，一邊拿着手機撩妹。前面一個同事，拿着手機短訊轉過頭來和我聊天。
於是，我們就開始討論下面這種短鏈接的實現原理(沒錯，上廁所也不忘學習！)。
點擊其中短鏈接後，我們會跳到如下地址
http://h5.dangdang.com/mix_20191015_or4x
本文，我們來討論一下其實現原理！
正文
需求緣起
這裡說一下，為什麼需要短鏈接？這個簡單，比如大家發微博的時候
如果URL地址過長，顯然可以寫的關鍵字就越少!
再比如發短訊如果短訊內容過長，那麼一條短訊就要拆成兩條發，浪費錢!
因此採用短鏈接，不僅節約資源，還十分美觀!
請求流程
首先，我們先看看噹噹的短鏈接http://dwz.win/nXR
它是由兩個部分組成
http://dwz.win:短鏈接系統的域名地址
nXR:請求參數
請求http://dwz.win/nXR地址後，返回狀態如下所示
於是，我們可以推斷出，敲下http://dwz.win/nXR地址後，發生了什麼呢？
這裡渣渣煙就要多嘴一句了。上圖所示短鏈接系統，返回的狀態可以為301或者302，只是噹噹網用的是301。
這裡我要說一下，大家應該明白30X狀態，在HTTP協議中，代表的是重定向的狀態。
301代表什麼？
301代表的是永久重定向。什麼意思呢?
對於GET請求, 301跳轉會默認被瀏覽器cache。也就是說，用戶第一次訪問某個短鏈接後，如果服務器返回301狀態碼，則這個用戶在後續多次訪問同一短鏈接地址，瀏覽器會直接請求跳轉地址，而不會再去短鏈接系統上取！
這麼做優點很明顯，降低了服務器壓力，但是無法統計到短鏈接地址的點擊次數。
302代表什麼？
302代表的是臨時定向。什麼意思呢?
對於GET請求, 302跳轉默認不會被瀏覽器緩存，除非在HTTP響應中通過 Cache-Control 或 Expires 暗示瀏覽器緩存。因此，用戶每次訪問同一短鏈接地址，瀏覽器都會去短鏈接系統上取。
這麼做的優點是，能夠統計到短地址被點擊的次數了。但是服務器的壓力變大了。
下面說最關鍵的一段，怎麼將http://h5.dangdang.com/mix_20191015_or4x壓縮為nXR字符
算法原理
首先呢，我們需要一張表來存儲，長短鏈接間的映射關係。表結構如下
| 列名 | 說明 |
|---|---|
| id | BIGINT,自增主鍵 |
| url | 長地址，也就是需要跳轉的原地址 |
好的，假設我們此時表裡的數據如下
| id | url |
|---|---|
| 1 | http://h5.dangdang.com/mix_20191015_or4x |
| 2 | http://h5.dangdang.com/mix_20191102_ad3x |
我們此時拿自增id作為短鏈接的key。假設域名http://dwz.win是短鏈接系統，也就是說請求:
(1)http://dwz.win/1會跳轉http://h5.dangdang.com/mix_20191015_or4x;
(2)http://dwz.win/2會跳轉http://h5.dangdang.com/mix_20191102_ad3x;
這麼做，也不是不行，有兩個缺點你要評估能不能接受！
- (1)如果數據比較大，比如幾百億，你的url地址依然過長
- (2)你的數據具有規律性，別人用一個簡單的腳本就可以遍歷出你的跳轉地址！
為了解決上面的兩個缺點，我們增加一個列，用來存儲key值。此時表結構如下
| 列名 | 說明 |
|---|---|
| id | BIGINT,自增主鍵 |
| key | 短串，需要加唯一索引 |
| url | 長地址，也就是需要跳轉的原地址 |
我們為了縮短id的長度呢，一般可以這麼做。由於我們的短鏈接是由 a-z、A-Z 和 0-9 共 62 個字符可以選擇。因此，我們可以講十進制的數字id，轉換為一個62進制的數，例如201314就可以轉換為Qn0。
算法如下
private static final String BASE = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"; public static String toBase62(long num) { StringBuilder sb = new StringBuilder(); do { int i = (int) (num % 62); sb.append(BASE.charAt(i)); num /= 62; } while (num > 0); return sb.reverse().toString(); }另外，我們需要引入一個全局發號器，一直返回全局自增的ID。相當於，我們的短鏈接系統先去請求這個全局自增ID，然後將全局自增ID轉換為62進制的數，作為key。
接下來，解決第二個問題！數據具有規律性的問題。畢竟你轉換為62進制後，只是解決了數據過長的問題，數據規律性問題還是沒解決。
因此，我們需要引入一個隨機算法。那麼此時，你的考慮點在於，你是否要根據key值，反推出全局id值！來抉擇不同的隨機算法！
(1)不希望反推出全局ID
OK，那就用一個洗牌算法，打亂算出的值。比如十進制的201314就可以轉換為Qn0。然後再使用洗牌算法，可以返回n0Q、Q0n….其中之一。但是會有一定幾率衝突，多洗幾次就行。
(2)希望反推出全局ID
OK，那就在得到Qn0這個數字後，將其轉換為二進制數。然後在固定位，第五位，第十位…(等等)插入一個隨機值即可。
至於如何反推也很簡單，你拿到短鏈接key後，將固定位的數字去除，再轉換為十進制即可。
講到這裡，就基本將key如何生成的邏輯講清楚了。那麼用戶在點擊短鏈接的時候，例如地址http://dwz.win/nXR，短鏈接系統解析出key為nXR，根據唯一索引去表中將nXR對應的url返回即可。
細節優化
(1)分庫分表
如果這個系統是放在公網，給大家使用的。建議上來就分庫分表，數據量過1000萬是很容易的。這裡涉及到一個問題，拿全局發號器給的自增id做分片健，還是拿轉換後的key做分片鍵。
顯然，用轉換後的key做分片鍵會更容易一些。如果用ID做為分片鍵，存在兩個問題！
(1)用戶請求的key，需要做一個逆運算推算回ID，然後根據ID，再去對應表裡去找，增加響應時間。
(2)根據選擇的隨機算法不同，key不一定能夠推算回ID值。這種情況下，只能每張表去查，更慢。
所以用key做分片鍵，再適合不過了。拿到用戶請求的KEY後，直接定位到對應的表裡將url取出即可。
(2)讀寫分離
這種系統顯然，讀遠大於寫。建議可以考慮做讀寫分離。
(3)引入緩存
假設，我們在一個時間。給手機推送短訊鏈接的短訊後。顯然，後面的一段時間內，對該短鏈接的請求量會大大提升。沒有必要每次都去數據庫查詢，因此可以引入redis緩存。
(4)全局發號器用其他算法行不行
可以。這裡只是要一個全局唯一ID而已。自己要估算好，使用其他算法所帶來的性能影響。以及採用其他算法，會不會造成生成的生成的ID過於規律。
(5)防攻擊
做好被惡意攻擊的準備，防止自增ID的值，被全部耗光。
總結
好久沒寫這種設計型的文章了。畢竟是我和同事在廁所蹲坑排隊之餘，在那閑聊出來的。最後，由於煙哥過於專註和同事聊技術，導致後來我回復那個妹紙的時候已經沒有了下文，注孤生！
希望大家有所收穫！
