背景

提供一個(gè)短址服務(wù)

你有沒(méi)有發(fā)現(xiàn)，我們的任務(wù)中出現(xiàn)長(zhǎng) URL 就會(huì)比較麻煩?如果有一個(gè)短址生成器就好了。雖然市面上有很多，但是我們可以重復(fù)發(fā)明一個(gè)輪子，利用這個(gè)機(jī)會(huì)嘗試一下簡(jiǎn)單的 Web 全棧開(kāi)發(fā)。

[[210840]]

任務(wù)

做一個(gè)短鏈接生成器，可以將一個(gè)長(zhǎng)鏈接縮短成一個(gè)短鏈接。

要發(fā)車(chē)了 :bus:

發(fā)車(chē)前，和大家說(shuō)一下

如果不想重復(fù)的造輪子，想開(kāi)箱即用，可以使用基于 PHP 的開(kāi)源軟件 YOURLS 。 YOURLS 還可以和 WordPress 整合到一起，功能強(qiáng)大，可擴(kuò)展性高。

本文記錄了開(kāi)發(fā)短網(wǎng)址系統(tǒng)的整個(gè)過(guò)程，包括初期的算法調(diào)研、模塊設(shè)計(jì)、數(shù)據(jù)庫(kù)設(shè)計(jì)、功能擴(kuò)展等。

什么是短鏈接 :link:

就是把普通網(wǎng)址，轉(zhuǎn)換成比較短的網(wǎng)址。比如： http://t.cn/RlB2PdD 這種，在微博這些限制字?jǐn)?shù)的應(yīng)用里。好處不言而喻。短、字符少、美觀、便于發(fā)布、傳播。

1. 百度短網(wǎng)址 http://dwz.cn/
2. 谷歌短網(wǎng)址服務(wù) https://goo.gl/ (需科學(xué)上網(wǎng))號(hào)稱(chēng)是最快的 :rocket:

原理解析

1. 當(dāng)我們?cè)跒g覽器里輸入 http://t.cn/RlB2PdD 時(shí)
2. DNS首先解析獲得 http://t.cn 的 IP 地址

當(dāng) DNS 獲得 IP 地址以后(比如：74.125.225.72)，會(huì)向這個(gè)地址發(fā)送 HTTP GET 請(qǐng)求，查詢(xún)短碼 RlB2PdD

1. http://t.cn 服務(wù)器會(huì)通過(guò)短碼 RlB2PdD 獲取對(duì)應(yīng)的長(zhǎng) URL
2. 請(qǐng)求通過(guò) HTTP 301 轉(zhuǎn)到對(duì)應(yīng)的長(zhǎng) URL https://m.helijia.com 。
3. 這里有個(gè)小的知識(shí)點(diǎn)，為什么要用 301 跳轉(zhuǎn)而不是 302 吶?
4. 301 是永久重定向，302 是臨時(shí)重定向。短地址一經(jīng)生成就不會(huì)變化，所以用 301 是符合 http 語(yǔ)義的。同時(shí)對(duì)服務(wù)器壓力也會(huì)有一定減少。

但是如果使用了 301 ，我們就無(wú)法統(tǒng)計(jì)到短地址被點(diǎn)擊的次數(shù)了。而這個(gè)點(diǎn)擊次數(shù)是一個(gè)非常有意思的大數(shù)據(jù)分析數(shù)據(jù)源。能夠分析出的東西非常非常多。所以選擇302雖然會(huì)增加服務(wù)器壓力，但是我想是一個(gè)更好的選擇。

來(lái)自知乎 iammutex 的 答案

算法實(shí)現(xiàn)

網(wǎng)上比較流行的算法有兩種 自增序列算法、 摘要算法

算法一

自增序列算法也叫永不重復(fù)算法

設(shè)置 id 自增，一個(gè) 10進(jìn)制 id 對(duì)應(yīng)一個(gè) 62進(jìn)制的數(shù)值，1對(duì)1，也就不會(huì)出現(xiàn)重復(fù)的情況。這個(gè)利用的就是低進(jìn)制轉(zhuǎn)化為高進(jìn)制時(shí)，字符數(shù)會(huì)減少的特性。

如下圖：十進(jìn)制 10000，對(duì)應(yīng)不同進(jìn)制的字符表示。

短址的長(zhǎng)度一般設(shè)為 6 位，而每一位是由 [a - z, A - Z, 0 - 9] 總共 62 個(gè)字母組成的，所以 6 位的話(huà)，總共會(huì)有 62^6 ~= 568億種組合，基本上夠用了。

哈哈，這里附上一個(gè)進(jìn)制轉(zhuǎn)換工具 http://tool.lu/hexconvert/ 上圖的數(shù)據(jù)就是用這個(gè)工具生成的。

具體的算法實(shí)現(xiàn)，自行谷歌。

算法二

1. 將長(zhǎng)網(wǎng)址 md5 生成 32 位簽名串,分為 4 段, 每段 8 個(gè)字節(jié)
2. 對(duì)這四段循環(huán)處理, 取 8 個(gè)字節(jié), 將他看成 16 進(jìn)制串與 0x3fffffff(30位1) 與操作, 即超過(guò) 30 位的忽略處理

這 30 位分成 6 段, 每 5 位的數(shù)字作為字母表的索引取得特定字符, 依次進(jìn)行獲得 6 位字符串

總的 md5 串可以獲得 4 個(gè) 6 位串,取里面的任意一個(gè)就可作為這個(gè)長(zhǎng) url 的短 url 地址

這種算法,雖然會(huì)生成4個(gè),但是仍然存在重復(fù)幾率

兩種算法對(duì)比

• 第一種算法的好處就是簡(jiǎn)單好理解，永不重復(fù)。但是短碼的長(zhǎng)度不固定，隨著 id 變大從一位長(zhǎng)度開(kāi)始遞增。如果非要讓短碼長(zhǎng)度固定也可以就是讓 id 從指定的數(shù)字開(kāi)始遞增就可以了。百度短網(wǎng)址用的這種算法。上文說(shuō)的開(kāi)源短網(wǎng)址項(xiàng)目 YOURLS 也是采用了這種算法。 源碼學(xué)習(xí)
• 第二種算法，存在碰撞(重復(fù))的可能性，雖然幾率很小。短碼位數(shù)是比較固定的。不會(huì)從一位長(zhǎng)度遞增到多位的。據(jù)說(shuō)微博使用的這種算法。

我使用的算法一。有一個(gè)不太好的地方就是出現(xiàn)的短碼是有序的，可能會(huì)不安全。我的處理方式是構(gòu)造 62進(jìn)制的字母不要按順序排列。因?yàn)橄雽?shí)現(xiàn)自定義短碼的功能，我又對(duì)算法一進(jìn)行了優(yōu)化，下文會(huì)介紹。

流程圖

自增序列算法流程圖

st=>start: 開(kāi)始 
e=>end: 結(jié)束 
io1=>inputoutput: 輸入網(wǎng)址 
io2=>inputoutput: 返回短網(wǎng)址 
op1=>operation: 返回對(duì)應(yīng)的短碼 
op2=>operation: 保存輸入的網(wǎng)址到數(shù)據(jù)庫(kù) 
op3=>operation: 根據(jù)id計(jì)算對(duì)應(yīng)的短碼 
op4=>operation: 更新短碼到數(shù)據(jù)庫(kù) 
cond1=>condition: 查詢(xún)數(shù)據(jù)庫(kù) 
是否存在對(duì) 
應(yīng)的短碼 
 
st->io1->cond1 
cond1(no,bottom)->op2->op3->op4->op1->io2->e 
cond1(yes)->op1->io2->e 

自增序列算法 + 用戶(hù)自定義短碼 流程圖

st=>start: 開(kāi)始 
e=>end: 結(jié)束 
io1=>inputoutput: 輸入網(wǎng)址 
io2=>inputoutput: 返回短網(wǎng)址 
io3=>inputoutput: 提示用戶(hù) 
該短碼已存在 
io4=>inputoutput: 提示用戶(hù) 
不能輸入短鏈接 
op1=>operation: 返回短碼 
op2=>operation: 保存輸入的網(wǎng)址到數(shù)據(jù)庫(kù) 
op3=>operation: 根據(jù)id計(jì)算對(duì)應(yīng)的短碼 
op4=>operation: 查詢(xún)數(shù)據(jù)庫(kù) 
獲得一條 
自定義短碼的url 
對(duì)應(yīng)的id記錄 
op5=>operation: 更新短碼到數(shù)據(jù)庫(kù) 
cond1=>condition: 查詢(xún)數(shù)據(jù)庫(kù) 
是否存在該URL 
cond2=>condition: 用戶(hù)選擇 
自定義短碼 
cond3=>condition: 生成的短碼 
是否存在 
cond4=>condition: 短碼是否存在 
cond5=>condition: 短碼是否存在 
cond6=>condition: 自定義的短碼 
是否存在 
cond7=>condition: 用戶(hù)輸入的是短鏈接 
 
st->io1->cond7 
cond7(no,bottom)->cond1 
cond7(yes)->io4->e 
cond1(no,bottom)->cond2 
cond1(yes)->op1->io2->e 
cond2(no,bottom)->op3->cond4 
cond2(yes)->cond5 
cond4(no, bottom)->op5->op1->io2->e 
cond4(yes)->op4->op3->cond4 
cond5(no,bottom)->op5 
cond5(yes)->io3->e 

百度短網(wǎng)址還允許用戶(hù)自定義短碼，算法二 摘要算法，不和 id 綁定，好像挺好實(shí)現(xiàn)這個(gè)功能的。

但是自增序列算法是和 id 綁定的，如果允許自定義短碼就會(huì)占用之后的短碼，之后的 id 要生成短碼的時(shí)候就發(fā)現(xiàn)短碼已經(jīng)被用了，那么 id 自增一對(duì)一不沖突的優(yōu)勢(shì)就體現(xiàn)不出來(lái)了。

那么怎么實(shí)現(xiàn)自定義短碼吶?

我是這樣處理的：

• 數(shù)據(jù)庫(kù)增加一個(gè)類(lèi)型 type 字段，用來(lái)標(biāo)記短碼是用戶(hù)自定義生成的，還是系統(tǒng)自動(dòng)生成的。
• 如果有用戶(hù)自定義過(guò)短碼，把它的類(lèi)型標(biāo)記自定義。每次根據(jù) id 計(jì)算短碼的時(shí)候，如果發(fā)現(xiàn)對(duì)應(yīng)的短碼被占用了，就從類(lèi)型為自定義的記錄里選取一條記錄，用它的 id 去計(jì)算短碼。
• 這樣既可以區(qū)分哪些長(zhǎng)連接是用戶(hù)自己定義還是系統(tǒng)自動(dòng)生成的，還可以不浪費(fèi)被自定義短碼占用的 id

我保留了 1 到 2 位的 短碼，從三位的短碼開(kāi)始生成的。就像域名的保留域名一樣，好的要自己預(yù)留 :smirk:

數(shù)據(jù)表設(shè)計(jì)

links 表

后期功能擴(kuò)展

• 統(tǒng)計(jì)：點(diǎn)擊量、訪問(wèn)的 ip 地域、用戶(hù)使用的設(shè)備
• 管理后臺(tái)：刪除、數(shù)據(jù)量
• 登錄：權(quán)限管理
• 設(shè)置密碼：輸入密碼才可以繼續(xù)訪問(wèn)