淺談短鏈的設計
大 廠 技 術 堅 持 周 更 精 選 好 文
背景
目前在很多場景下,都需要短鏈,尤其是涉及到一些 URL 下發的邏輯。之前做小馬 AI 課的業務時,銷售通過簡訊下發的連結就是一個短鏈。為什麼需要短鏈呢?考慮到一個 URL 上有 path、query 等引數,各種引數拼接在一起就成了一個長不拉幾的字串。
在很多社交平臺上,對於傳送的文字是有長度限制,過長的 URL 很容易被截斷,然後觸達就無效了。當用戶收到一個短鏈,心情可能更加愉悅:
![](http://mdimg.wxwenku.com/getimg/6b990ce30fa9193e296dd37902816f4bd7724f943d742fdfc27ac022d21544534d48edf6319a73e391cd31cb07608b30.jpg)
短鏈組成
知己知彼百戰百勝,先來看看一個短鏈有哪些資訊。
![](http://mdimg.wxwenku.com/getimg/6b990ce30fa9193e296dd37902816f4b591b12ec86537dc23da75428d4537db5702845a9027814b486ee819e24423536.jpg)
協議 + 域名 + 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。
![](http://mdimg.wxwenku.com/getimg/356ed03bdc643f9448b3f6485edc229b39d7d9d4f771e193b53a4d7d19ecfa1e594a912e2db91e6e302ec44a0c9c346d.jpg)
第一位佔用 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 生成器。http://github.com/baidu/uid-generator
-
Leaf
Leaf 是美團開源的分散式ID生成器,能保證全域性唯一,趨勢遞增,但需要依賴關係資料庫、Zookeeper等中介軟體。http://tech.meituan.com/2017/04/21/mt-leaf.html
進一步縮短
如果我們得到『1536389934』這個序號的話,看起來還是有點長,如果想進一步縮短,可以把十進位制數轉換成62進位制數。然後就得到一個比原序號更短的 ID 了。
![](http://mdimg.wxwenku.com/getimg/ccdf080c7af7e8a10e9b88444af98393e19ebf834a5b242e6b5fffdaeb3d933ac8fd2ccf12fb2ad4b6aea93fdb36c12b.jpg)
為什麼要用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
:heart: 謝謝支援
以上便是本次分享的全部內容,希望對你有所幫助^_^
喜歡的話別忘了 分享、點贊、收藏 三連哦~。
歡迎關注公眾號 ELab團隊 收貨大廠一手好文章~
我們來自位元組跳動,是旗下大力教育前端部門,負責位元組跳動教育全線產品前端開發工作。
我們圍繞產品品質提升、開發效率、創意與前沿技術等方向沉澱與傳播專業知識及案例,為業界貢獻經驗價值。包括但不限於效能監控、元件庫、多端技術、Serverless、視覺化搭建、音視訊、人工智慧、產品設計與營銷等內容。
歡迎感興趣的同學在評論區或使用內推碼內推到作者部門拍磚哦
位元組跳動校/社招投遞連結: http://job.toutia o.com/
內推碼: FD72CWA
- 使用 WebAssembly 打造定製 JS Runtime
- 前端也要懂演算法,不會演算法也能微調一個 NLP 預訓練模型
- 聯機遊戲原理入門即入土 -- 入門篇
- Plasmo Framework:次世代的瀏覽器外掛開發框架
- 深入理解 Mocha 測試框架:從零實現一個 Mocha
- Single Source of Truth:XCode SwiftUI 的介面編輯的設計理念
- 深入理解 D3.js 視覺化庫之力導向圖原理與實現
- 淺析神經網路 Neural Networks
- Cutter - Web視訊剪輯工具原理淺析
- 你可能需要一個四捨五入的工具函式
- 淺析eslint原理
- 最小編譯器the-super-tiny-compiler
- Git儲存原理及部分實現
- 淺談短鏈的設計
- Web元件構建庫-Lit
- 使用Svelte開發Chrome Extension
- Web3.0開發入門
- vscode外掛原理淺析與實戰
- 深入淺出 Web Audio API
- 探祕HTTPS