短網址(short URL)系統的原理及其實現
背景
提供一個短址服務
你有沒有發現，我們的任務中出現長 URL 就會比較麻煩?如果有一個短址生成器就好了。雖然市面上有很多，但是我們可以重復發明一個輪子，利用這個機會嘗試一下簡單的 Web 全棧開發。
任務
做一個短鏈接生成器，可以將一個長鏈接縮短成一個短鏈接。
要發車了 :bus:
發車前，和大家說一下
如果不想重復的造輪子，想開箱即用，可以使用基于 PHP 的開源軟件 YOURLS 。 YOURLS 還可以和 WordPress 整合到一起，功能強大，可擴展性高。
本文記錄了開發短網址系統的整個過程，包括初期的算法調研、模塊設計、數據庫設計、功能擴展等。
什么是短鏈接 :link:
就是把普通網址，轉換成比較短的網址。比如： http://t.cn/RlB2PdD 這種，在微博這些限制字數的應用里。好處不言而喻。短、字符少、美觀、便于發布、傳播。
- 百度短網址 http://dwz.cn/
- 谷歌短網址服務 https://goo.gl/ (需科學上網)號稱是最快的 :rocket:
原理解析
- 當我們在瀏覽器里輸入 http://t.cn/RlB2PdD 時
- DNS首先解析獲得 http://t.cn 的 IP 地址
當 DNS 獲得 IP 地址以后(比如：74.125.225.72)，會向這個地址發送 HTTP GET 請求，查詢短碼 RlB2PdD
- http://t.cn 服務器會通過短碼 RlB2PdD 獲取對應的長 URL
- 請求通過 HTTP 301 轉到對應的長 URL https://m.helijia.com 。
- 這里有個小的知識點，為什么要用 301 跳轉而不是 302 吶?
- 301 是永久重定向，302 是臨時重定向。短地址一經生成就不會變化，所以用 301 是符合 http 語義的。同時對服務器壓力也會有一定減少。
但是如果使用了 301 ，我們就無法統計到短地址被點擊的次數了。而這個點擊次數是一個非常有意思的大數據分析數據源。能夠分析出的東西非常非常多。所以選擇302雖然會增加服務器壓力，但是我想是一個更好的選擇。
來自知乎 iammutex 的 答案
算法實現
網上比較流行的算法有兩種 自增序列算法、 摘要算法
算法一
自增序列算法也叫永不重復算法
設置 id 自增，一個 10進制 id 對應一個 62進制的數值，1對1，也就不會出現重復的情況。這個利用的就是低進制轉化為高進制時，字符數會減少的特性。
如下圖：十進制 10000，對應不同進制的字符表示。
短址的長度一般設為 6 位，而每一位是由 [a - z, A - Z, 0 - 9] 總共 62 個字母組成的，所以 6 位的話，總共會有 62^6 ~= 568億種組合，基本上夠用了。
哈哈，這里附上一個進制轉換工具 http://tool.lu/hexconvert/ 上圖的數據就是用這個工具生成的。
具體的算法實現，自行谷歌。
算法二
- 將長網址 md5 生成 32 位簽名串,分為 4 段, 每段 8 個字節
- 對這四段循環處理, 取 8 個字節, 將他看成 16 進制串與 0x3fffffff(30位1) 與操作, 即超過 30 位的忽略處理
這 30 位分成 6 段, 每 5 位的數字作為字母表的索引取得特定字符, 依次進行獲得 6 位字符串
總的 md5 串可以獲得 4 個 6 位串,取里面的任意一個就可作為這個長 url 的短 url 地址
這種算法,雖然會生成4個,但是仍然存在重復幾率
兩種算法對比
- 第一種算法的好處就是簡單好理解，永不重復。但是短碼的長度不固定，隨著 id 變大從一位長度開始遞增。如果非要讓短碼長度固定也可以就是讓 id 從指定的數字開始遞增就可以了。百度短網址用的這種算法。上文說的開源短網址項目 YOURLS 也是采用了這種算法。 源碼學習
- 第二種算法，存在碰撞(重復)的可能性，雖然幾率很小。短碼位數是比較固定的。不會從一位長度遞增到多位的。據說微博使用的這種算法。
我使用的算法一。有一個不太好的地方就是出現的短碼是有序的，可能會不安全。我的處理方式是構造 62進制的字母不要按順序排列。因為想實現自定義短碼的功能，我又對算法一進行了優化，下文會介紹。
流程圖
自增序列算法流程圖
- st=>start: 開始
- e=>end: 結束
- io1=>inputoutput: 輸入網址
- io2=>inputoutput: 返回短網址
- op1=>operation: 返回對應的短碼
- op2=>operation: 保存輸入的網址到數據庫
- op3=>operation: 根據id計算對應的短碼
- op4=>operation: 更新短碼到數據庫
- cond1=>condition: 查詢數據庫
- 是否存在對
- 應的短碼
- st->io1->cond1
- cond1(no,bottom)->op2->op3->op4->op1->io2->e
- cond1(yes)->op1->io2->e
自增序列算法 + 用戶自定義短碼 流程圖
- st=>start: 開始
- e=>end: 結束
- io1=>inputoutput: 輸入網址
- io2=>inputoutput: 返回短網址
- io3=>inputoutput: 提示用戶
- 該短碼已存在
- io4=>inputoutput: 提示用戶
- 不能輸入短鏈接
- op1=>operation: 返回短碼
- op2=>operation: 保存輸入的網址到數據庫
- op3=>operation: 根據id計算對應的短碼
- op4=>operation: 查詢數據庫
- 獲得一條
- 自定義短碼的url
- 對應的id記錄
- op5=>operation: 更新短碼到數據庫
- cond1=>condition: 查詢數據庫
- 是否存在該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
百度短網址還允許用戶自定義短碼，算法二 摘要算法，不和 id 綁定，好像挺好實現這個功能的。
但是自增序列算法是和 id 綁定的，如果允許自定義短碼就會占用之后的短碼，之后的 id 要生成短碼的時候就發現短碼已經被用了，那么 id 自增一對一不沖突的優勢就體現不出來了。
那么怎么實現自定義短碼吶?
我是這樣處理的：
- 數據庫增加一個類型 type 字段，用來標記短碼是用戶自定義生成的，還是系統自動生成的。
- 如果有用戶自定義過短碼，把它的類型標記自定義。每次根據 id 計算短碼的時候，如果發現對應的短碼被占用了，就從類型為自定義的記錄里選取一條記錄，用它的 id 去計算短碼。
- 這樣既可以區分哪些長連接是用戶自己定義還是系統自動生成的，還可以不浪費被自定義短碼占用的 id
我保留了 1 到 2 位的 短碼，從三位的短碼開始生成的。就像域名的保留域名一樣，好的要自己預留 :smirk:
數據表設計
links 表
后期功能擴展
- 統計：點擊量、訪問的 ip 地域、用戶使用的設備
- 管理后臺：刪除、數據量
- 登錄：權限管理
- 設置密碼：輸入密碼才可以繼續訪問
