淺談短鏈的設計

背景

目前在很多場景下，都需要短鏈，尤其是涉及到一些 URL 下發的邏輯。之前做小馬 AI 課的業務時，銷售通過簡訊下發的連結就是一個短鏈。為什麼需要短鏈呢？考慮到一個 URL 上有 path、query 等引數，各種引數拼接在一起就成了一個長不拉幾的字串。

在很多社交平臺上，對於傳送的文字是有長度限制，過長的 URL 很容易被截斷，然後觸達就無效了。當用戶收到一個短鏈，心情可能更加愉悅：

短鏈組成

知己知彼百戰百勝，先來看看一個短鏈有哪些資訊。

協議 + 域名 + path，協議可以直接忽略。域名是必須的（廢話），並且足夠短，否則的話就變成了長的短鏈（挺傻的）。最後 path 的部分才是關鍵，看起來是一個由 6 個字元組成的字串，並且字元的範圍是大小寫字母+數字。

足夠短的域名需要什麼條件？大概率錢夠就行。涉及到錢的部分，這裡就不深入探究了。所以來研究一下這個 path 的生成。

Path 的生成

獲取一個序號

雜湊演算法

Path 的其中一種方式就是通過雜湊演算法計算得到。常見的雜湊函式有 MD5、SHA1 等大家常見的加密型雜湊演算法，也有 HighwayHash、MurmurHash 等非加密型雜湊函式。以 MurmurHash 為例，目前已經迭代到 MurmurHash 3，能夠產生 32bit 和 128 bit 的雜湊值，並且對於規律性較強的 key，隨機分佈的特徵表現的很不錯。

不過雜湊衝突是不可控的，我們雖然有 N 種解決雜湊衝突的方式，但是會增加整個系統的整體複雜度。

自增 ID

也可以維護一個 ID 自增生成器，對於每一個長鏈生成1、2、3等自增的序號，然後把長鏈和序號的對映儲存在資料庫裡面，然後得到如 http://fake.short/1、http://fake.short/2 等短鏈。考慮到單機容易造成單點故障，所以一般都是分散式的 ID 生成器。

Mysql 自增

假設有 10 臺 Mysql 伺服器，每一臺初始值分別為 0……9，然後每生成一個需要就遞增 10，這樣確保這 10 臺 Mysql 伺服器產生的 ID 不重複。但這個方案缺點比較明顯，就是 ID 是有跡可循的，爬蟲的可以順著順序依次請求得到；水平擴充套件不容易，如之前約定 10 臺機器，每臺機器生產的步長是 10，如果需要增加一臺機器，比較困難；資料庫壓力還是很大，每次獲取ID都得讀寫一次資料庫，只能靠堆機器來提高效能。

基於雪花演算法

SnowFlake 是 Twitter 公司採用的一種演算法，目的是在分散式系統中產生全域性唯一且趨勢遞增的ID。

第一位佔用 1bit，其值始終是0，沒有實際作用。2.時間戳 佔用 41bit，精確到毫秒，總共可以容納約 69 年的時間。3.工作機器id 佔用10bit，其中高位 5bit 是資料中心ID，低位 5bit 是工作節點ID，做多可以容納 1024 個節點。4.序列號 佔用12bit，每個節點每毫秒0開始不斷累加，最多可以累加到4095，一共可以產生 4096 個ID。

SnowFlake演算法在同一毫秒內最多可以生成 1024 X 4096 = 4194304 個全域性唯一ID。

國內也有不少基於（類）雪花演算法的開源分散式唯一ID生成器：

1. UidGenerator

由百度開源的分散式 UID 生成器。http://github.com/baidu/uid-generator

2. Leaf

Leaf 是美團開源的分散式ID生成器，能保證全域性唯一，趨勢遞增，但需要依賴關係資料庫、Zookeeper等中介軟體。http://tech.meituan.com/2017/04/21/mt-leaf.html

進一步縮短

如果我們得到『1536389934』這個序號的話，看起來還是有點長，如果想進一步縮短，可以把十進位制數轉換成62進位制數。然後就得到一個比原序號更短的 ID 了。

為什麼要用62進位制轉換？

• 62進位制轉換是因為62進位制轉換後只含數字+小寫+大寫字母。而64進位制轉換會含有 / , + 這樣的符號（不符合正常URL的字元）encodeURIComponent('+') => %xx

• 10進位制轉62進位制可以縮短字元，如果我們要6位字元的話，已經有560億個組合了。

重定向是 301 還是 302

眾所周知，301 是永久重定向，瀏覽器會把重定向後的地址快取下來，下次訪問的時候，就不會向原地址發起請求；按理來說通過 301 的重定向效能會更好，對服務的壓力也更小。

但是，正因為 301 會在瀏覽器中有快取，所以服務端就沒辦法知道有多少使用者是通過這個短鏈訪問的，在現如今什麼資料都可以分析一波的時代，這些資料的缺失，就失去了分析活動的能力。所以一般都通過 302 進行重定向，便於記錄使用的資料，稍微增加點 Server 的壓力。（沒有什麼是不能通過加機器解決的

參考資料

http://juejin.cn/post/6990275533057556494

http://tech.meituan.com/2017/04/21/mt-leaf.html

http://zhuanlan.zhihu.com/p/85837641

http://www.zhihu.com/question/29270034

http://www.zhihu.com/question/20103344