淺談短鏈的設計
背景
目前在很多場景下,都需要短鏈,尤其是涉及到一些 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 等自增的序號,然後把長鏈和序號的映射保存在數據庫裏面,然後得到如 https://fake.short/1、https://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 生成器:
- UidGenerator
由百度開源的分佈式 UID 生成器。https://github.com/baidu/uid-generator
- Leaf
Leaf 是美團開源的分佈式 ID 生成器,能保證全局唯一,趨勢遞增,但需要依賴關係數據庫、Zookeeper 等中間件。https://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 的壓力。(沒有什麼是不能通過加機器解決的
參考資料
https://juejin.cn/post/6990275533057556494
https://tech.meituan.com/2017/04/21/mt-leaf.html
https://zhuanlan.zhihu.com/p/85837641
https://www.zhihu.com/question/29270034
https://www.zhihu.com/question/20103344
本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源:https://mp.weixin.qq.com/s/KtLbCClA_k54Ew08bp0jSg