背景

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

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

　　任務(wù)

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

　　要發(fā)車了 :bus:

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

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

　　本文記錄了開發(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ā)布、傳播。

　　百度短網(wǎng)址 http://dwz.cn/

　　谷歌短網(wǎng)址服務(wù) https://goo.gl/ (需科學(xué)上網(wǎng))號(hào)稱是快的 :rocket:

　　原理解析

　　當(dāng)我們?cè)跒g覽器里輸入 http://t.cn/RlB2PdD 時(shí)

　　DNS首先解析獲得 http://t.cn 的 IP 地址

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

　　http://t.cn 服務(wù)器會(huì)通過(guò)短碼 RlB2PdD 獲取對(duì)應(yīng)的長(zhǎng) URL

　　請(qǐng)求通過(guò) HTTP 301 轉(zhuǎn)到對(duì)應(yīng)的長(zhǎng) URL https://m.helijia.com 。

　　這里有個(gè)小的知識(shí)點(diǎn)，為什么要用 301 跳轉(zhuǎn)而不是 302 吶?

　　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ì)有 62^6 ~= 568億種組合，基本上夠用了。

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

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

　　算法二

　　將長(zhǎng)網(wǎng)址 md5 生成 32 位簽名串,分為 4 段, 每段 8 個(gè)字節(jié)

　　對(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ì)比

　　先進(jìn)種算法的好處就是簡(jiǎn)單好理解，永不重復(fù)。但是短碼的長(zhǎng)度不固定，隨著 id 變大從一位長(zhǎng)度開始遞增。如果非要讓短碼長(zhǎng)度固定也可以就是讓 id 從指定的數(shù)字開始遞增就可以了。百度短網(wǎng)址用的這種算法。上文說(shuō)的開源短網(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: 開始

　　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: 查詢數(shù)據(jù)庫(kù)

　　是否存在對(duì)

　　應(yīng)的短碼

　　st->io1->cond1

　　cond1(no,bottom)->op2->op3->op4->op1->io2->e

　　cond1(yes)->op1->io2->e

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

　　st=>start: 開始

　　e=>end: 結(jié)束

　　io1=>inputoutput: 輸入網(wǎng)址

　　io2=>inputoutput: 返回短網(wǎng)址

　　io3=>inputoutput: 提示用戶

　　該短碼已存在

　　io4=>inputoutput: 提示用戶

　　不能輸入短鏈接

　　op1=>operation: 返回短碼

　　op2=>operation: 保存輸入的網(wǎng)址到數(shù)據(jù)庫(kù)

　　op3=>operation: 根據(jù)id計(jì)算對(duì)應(yīng)的短碼

　　op4=>operation: 查詢數(shù)據(jù)庫(kù)

　　獲得一條

　　自定義短碼的url

　　對(duì)應(yīng)的id記錄

　　op5=>operation: 更新短碼到數(shù)據(jù)庫(kù)

　　cond1=>condition: 查詢數(shù)據(jù)庫(kù)

　　是否存在該URL

　　cond2=>condition: 用戶選擇

　　自定義短碼

　　cond3=>condition: 生成的短碼

　　是否存在

　　cond4=>condition: 短碼是否存在

　　cond5=>condition: 短碼是否存在

　　cond6=>condition: 自定義的短碼

　　是否存在

　　cond7=>condition: 用戶輸入的是短鏈接

　　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)址還允許用戶自定義短碼，算法二 摘要算法，不和 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è)類型 type 字段，用來(lái)標(biāo)記短碼是用戶自定義生成的，還是系統(tǒng)自動(dòng)生成的。

　　如果有用戶自定義過(guò)短碼，把它的類型標(biāo)記自定義。每次根據(jù) id 計(jì)算短碼的時(shí)候，如果發(fā)現(xiàn)對(duì)應(yīng)的短碼被占用了，就從類型為自定義的記錄里選取一條記錄，用它的 id 去計(jì)算短碼。

　　這樣既可以區(qū)分哪些長(zhǎng)連接是用戶自己定義還是系統(tǒng)自動(dòng)生成的，還可以不浪費(fèi)被自定義短碼占用的 id

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

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

　　links 表

　　后期功能擴(kuò)展

　　統(tǒng)計(jì)：點(diǎn)擊量、訪問(wèn)的 ip 地域、用戶使用的設(shè)備

　　管理后臺(tái)：刪除、數(shù)據(jù)量

　　登錄：權(quán)限管理

　　設(shè)置密碼：輸入密碼才可以繼續(xù)訪問(wèn)