背景

目前在很多場(chǎng)景下，都需要短鏈，尤其是涉及到一些 URL 下發(fā)的邏輯。為什么需要短鏈呢？考慮到一個(gè) URL 上有 path、query 等參數(shù)，各種參數(shù)拼接在一起就成了一個(gè)長(zhǎng)不拉幾的字符串。

在很多社交平臺(tái)上，對(duì)于發(fā)送的文本是有長(zhǎng)度限制，過(guò)長(zhǎng)的 URL 很容易被截?cái)?，然后觸達(dá)就無(wú)效了。當(dāng)用戶收到一個(gè)短鏈，心情可能更加愉悅：

短鏈組成

知己知彼百戰(zhàn)百勝，先來(lái)看看一個(gè)短鏈有哪些信息。

協(xié)議 + 域名 + path，協(xié)議可以直接忽略。域名是必須的（廢話），并且足夠短，否則的話就變成了長(zhǎng)的短鏈（挺傻的）。最后 path 的部分才是關(guān)鍵，看起來(lái)是一個(gè)由 6 個(gè)字符組成的字符串，并且字符的范圍是大小寫字母+數(shù)字。

足夠短的域名需要什么條件？大概率錢夠就行。涉及到錢的部分，這里就不深入探究了。所以來(lái)研究一下這個(gè) path 的生成。

Path 的生成

獲取一個(gè)序號(hào)

哈希算法

Path 的其中一種方式就是通過(guò)哈希算法計(jì)算得到。常見的哈希函數(shù)有 MD5、SHA1 等大家常見的加密型哈希算法，也有 HighwayHash、MurmurHash 等非加密型哈希函數(shù)。以 MurmurHash 為例，目前已經(jīng)迭代到 MurmurHash 3，能夠產(chǎn)生 32bit 和 128 bit 的哈希值，并且對(duì)于規(guī)律性較強(qiáng)的 key，隨機(jī)分布的特征表現(xiàn)的很不錯(cuò)。

不過(guò)哈希沖突是不可控的，我們雖然有 N 種解決哈希沖突的方式，但是會(huì)增加整個(gè)系統(tǒng)的整體復(fù)雜度。

自增 ID

也可以維護(hù)一個(gè) ID 自增生成器，對(duì)于每一個(gè)長(zhǎng)鏈生成1、2、3等自增的序號(hào)，然后把長(zhǎng)鏈和序號(hào)的映射保存在數(shù)據(jù)庫(kù)里面，然后得到如 https://fake.short/1、https://fake.short/2 等短鏈?？紤]到單機(jī)容易造成單點(diǎn)故障，所以一般都是分布式的 ID 生成器。

Mysql 自增

假設(shè)有 10 臺(tái) Mysql 服務(wù)器，每一臺(tái)初始值分別為 0……9，然后每生成一個(gè)需要就遞增 10，這樣確保這 10 臺(tái) Mysql 服務(wù)器產(chǎn)生的 ID 不重復(fù)。但這個(gè)方案缺點(diǎn)比較明顯，就是 ID 是有跡可循的，爬蟲的可以順著順序依次請(qǐng)求得到；水平擴(kuò)展不容易，如之前約定 10 臺(tái)機(jī)器，每臺(tái)機(jī)器生產(chǎn)的步長(zhǎng)是 10，如果需要增加一臺(tái)機(jī)器，比較困難；數(shù)據(jù)庫(kù)壓力還是很大，每次獲取ID都得讀寫一次數(shù)據(jù)庫(kù)，只能靠堆機(jī)器來(lái)提高性能。

基于雪花算法

SnowFlake 是 Twitter 公司采用的一種算法，目的是在分布式系統(tǒng)中產(chǎn)生全局唯一且趨勢(shì)遞增的ID。

第一位占用 1bit，其值始終是0，沒(méi)有實(shí)際作用。2.時(shí)間戳 占用 41bit，精確到毫秒，總共可以容納約 69 年的時(shí)間。3.工作機(jī)器id 占用10bit，其中高位 5bit 是數(shù)據(jù)中心ID，低位 5bit 是工作節(jié)點(diǎn)ID，最多可以容納 1024 個(gè)節(jié)點(diǎn)。4.序列號(hào) 占用12bit，每個(gè)節(jié)點(diǎn)每毫秒0開始不斷累加，最多可以累加到4095，一共可以產(chǎn)生 4096 個(gè)ID。

SnowFlake算法在同一毫秒內(nèi)最多可以生成 1024 X 4096 = 4194304 個(gè)全局唯一ID。

國(guó)內(nèi)也有不少基于（類）雪花算法的開源分布式唯一ID生成器：

1. UidGenerator

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

2. Leaf

Leaf 是美團(tuán)開源的分布式ID生成器，能保證全局唯一，趨勢(shì)遞增，但需要依賴關(guān)系數(shù)據(jù)庫(kù)、Zookeeper等中間件。https://tech.meituan.com/2017/04/21/mt-leaf.html

進(jìn)一步縮短

如果我們得到『1536389934』這個(gè)序號(hào)的話，看起來(lái)還是有點(diǎn)長(zhǎng)，如果想進(jìn)一步縮短，可以把十進(jìn)制數(shù)轉(zhuǎn)換成62進(jìn)制數(shù)。然后就得到一個(gè)比原序號(hào)更短的 ID 了。

為什么要用62進(jìn)制轉(zhuǎn)換？

• 62進(jìn)制轉(zhuǎn)換是因?yàn)?2進(jìn)制轉(zhuǎn)換后只含數(shù)字+小寫+大寫字母。而64進(jìn)制轉(zhuǎn)換會(huì)含有/,+這樣的符號(hào)（不符合正常URL的字符）encodeURIComponent('+') => %xx
• 10進(jìn)制轉(zhuǎn)62進(jìn)制可以縮短字符，如果我們要6位字符的話，已經(jīng)有560億個(gè)組合了。

重定向是 301 還是 302

眾所周知，301 是永久重定向，瀏覽器會(huì)把重定向后的地址緩存下來(lái)，下次訪問(wèn)的時(shí)候，就不會(huì)向原地址發(fā)起請(qǐng)求；按理來(lái)說(shuō)通過(guò) 301 的重定向性能會(huì)更好，對(duì)服務(wù)的壓力也更小。

但是，正因?yàn)?301 會(huì)在瀏覽器中有緩存，所以服務(wù)端就沒(méi)辦法知道有多少用戶是通過(guò)這個(gè)短鏈訪問(wèn)的，在現(xiàn)如今什么數(shù)據(jù)都可以分析一波的時(shí)代，這些數(shù)據(jù)的缺失，就失去了分析活動(dòng)的能力。所以一般都通過(guò) 302 進(jìn)行重定向，便于記錄使用的數(shù)據(jù)，稍微增加點(diǎn) Server 的壓力。（沒(méi)有什么是不能通過(guò)加機(jī)器解決的