天天看點
傳回

網頁短連結實作原理探究

事情是這樣的，今天一人問我一個問題，但是我懶得在說，就在網上找了一篇部落格通過QQ發送給他，但是在發送連結時我發現之前很長的連結變成了短連結，且這個短連結能夠正常通路之前的長連結，好奇之下就有了這篇文章．

什麼是短連結？

我的了解就是通過一定的算法和技術實作将原本很長的網址轉換為較短的網址，進而便于使用者記憶和在網際網路上的傳播．常用于有字數限制的微網誌，二維碼等場景．

現在很多公司都提供了短連結服務，比如百度，新浪微網誌等等，以供使用者***友善的生成短連結．

短連結的大緻整體流程

今天上午我找的原本連結是這個：

https://blog.wpjam.com/m/scripts-and-plugins-for-analyzing-website-traffic-stats/

生成的短連結(長期的話可能會無效)：

http://url.cn/5r8GoSZ

大緻流程是這樣的：我複制(輸入)了一個長連結，通過騰訊伺服器的轉化後得到一個以http://url.cn開頭的短連結，然後我可以将該網址在網際網路上進行分享和傳播，其他人在通路該短網址可以進入到之前原本長網址對應的頁面．

網頁短連結實作原理探究

是以要想将生成短連結，我們需要注意兩個問題：

  1. 如何将任意長的字元串轉化為較短長或者固定長的字元串．
  2.  如何将短連結還原成之前的長連結，使之能夠通路．

算法實作

Hash實作

通過一定方式将任意長的文本轉化為一個固定長的字元串，隻要目标文本長度适當，那麼我們對于不同的輸入通過哈希幾乎(注意是幾乎)不可能得到對應同一個字元串．通過對長連結進行Hash運算，将Hash值作為這個長連結的唯一标示．但是通過Hash實作可能會造成碰撞．不一樣的長網址縮短成了同一個短網址，那也就做不到複原了．

對于碰撞問題，有一種緩沖方法就是在呈現碰撞了以後後邊在增加随機字元，随機字元的增加能夠緩解碰撞的疑問，但是這終究是一種緩沖的辦法，沒有徹底解決碰撞． 

自增序列算法(永不重複算法)

我們可以設定一個自增id，對于每一個新的長連結給他一個不重複的id．

原理：當伺服器接收到一個網址時首先檢驗這個網址在伺服器中是否再存，如果不存在，存儲這個新網址并分發一個id，這個id設定成自增，保證了每一個存儲的網址的id都是唯一标示．比如上面的，當一個連結過來時，給這個連結發一個0，再有一個連結過來時，給後面這個連結一個1，以此類推．

資料實作：我們發現短連結後面的參數好像都是定長的，但是如果通過id進行時，參數不定長，且随着id的自增，可能會出現這種情況：url.cn/10000000．我們可以将十進制的id轉化為多進制，比如在以\'0-9a-z\'這36個字元表示的36進制中，一億可以被表示為1njchs，基本實作不重複夠用．如果資料量更大，我們可以采用62進制進行轉化：

網頁短連結實作原理探究

​

短址的長度一般設為 6 位，而每一位是由 

[a - z, A - Z, 0 - 9]

 總共 62 個字母組成的，是以 6 位的話，總共會有 62^6 ~= 568億種組合。

存儲實作：

對于小型系統，簡單的mysql系統的表自增索引即可實作(注意自增id資料類型，int隻能到65535)

大型系統可以搭建分布式key-value系統進行存儲．

我使用mysql簡單建了一張表，用于儲存長網址的資料，隻有兩個字段，一個是主鍵用于儲存id，一個url字段用于存放原始的長網址．在進行長網址轉換時，先檢查資料表中是否存在該長網址，如果存在直接擷取該記錄的id，否在建立一條新的記錄并傳回該記錄的id，對于這id進行進制轉化處理後拼接到準備好的域名後面得到一個對應的短網址傳回給使用者．

這裡我簡單模仿了一個轉換短連結的功能：

url.php：用于模拟資料庫存儲

<?php

return array(
    \'http://test1.com/12345vn6\',
    \'http://test2.com/1234gf56\',
    \'http://teat1.com/123ssgg456\',
    \'http://test1.com/1234svss56\',
    \'http://tefasfd1.com/123456\',
    \'http://tesddt1.com/12sss3456\',
    \'http://tehghdgst1.com/123dsaf456\',
    \'http://tedddst1.com/12SDsd3456\',
    \'http://testaa1bb.com/1234ccgfryh56\',
    \'http://testaa1dfd.com/1234ccgfryh56\',
    \'http://testaa1.com/1234ccgfryh56\',
    \'http://testaa1.cssom/1234ccgfryh56\',
    \'http://testaa1.com/1234ccgfryh56\',
    \'http://testraa1.com/1234ccgfryzh56\',
    \'http://teffstaa1.com/1234ccgfsryh56\',
    \'http://testaxxa1.com/1234ccgfrsryh56\',
    \'http://testaa1ll.com/1234ccgyrfryh56\',
    \'http://testaa1.com/1234ccgfryyh56\',
    \'http://tesbbtaa1.com/1ss234cjcgfryh56\',
)

?>

get.php：用于模拟生成短連結

<?php

    require \'./jinzhi.php\';
    $arr = include(\'./url.php\');

    $host = \'http://url.cn/\';

    $url = $_SERVER[\'HTTP_HOST\'] . $_SERVER[\'SCRIPT_NAME\'];

    $keyId = in_array($url, $arr) ? array_search($url, $arr) : (array_push($arr, $url) - 1);

    $toKey = get_char($keyId);

    echo $host . $toKey;

?>

jinzhi.php：模拟進制轉化

<?php

/**
 * @desc  im:十進制數轉換成三十六機制數
 * @param (int)$num 十進制數
 * return 傳回：三十六進制數
*/
function get_char($num) {
    $num = intval($num);
    if ($num <= 0)
        return false;
    $charArr = array("0","1","2","3","4","5","6","7","8","9",\'A\', \'B\', \'C\', \'D\', \'E\', \'F\', \'G\', \'H\', \'I\', \'J\', \'K\', \'L\', \'M\', \'N\', \'O\', \'P\', \'Q\', \'R\', \'S\', \'T\', \'U\', \'V\', \'W\', \'X\', \'Y\', \'Z\');
    $char = \'\';
    do {
        $key = ($num - 1) % 36;
        $char= $charArr[$key] . $char;
        $num = floor(($num - $key) / 36);
    } while ($num > 0);
    return $char;
}

/**
 * @desc  im:三十六進制數轉換成十機制數
 * @param (string)$char 三十六進制數
 * return 傳回：十進制數
 */
function get_num($char){
    $array=array("0","1","2","3","4","5","6","7","8","9","A", "B", "C", "D","E", "F", "G", "H", "I", "J", "K", "L","M", "N", "O","P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y","Z");
    $len=strlen($char);
    for($i=0;$i<$len;$i++){
        $index=array_search($char[$i],$array);
        $sum+=($index+1)*pow(36,$len-$i-1);
    }
    return $sum;
}

?>

進行路由請求：http://localhost:4000/get.php/10000000

輸出：http://url.cn/J

至于解析短連結跳轉至原有連結，隻是對上面思路進行取反．

摘要算法

實作思路：

  1. 将長網址 

    md5

      生成 32 位簽名串,分為 4 段, 每段 8 個位元組
  2. 對這四段循環處理, 取 8 個位元組, 将他看成 16 進制串與 0x3fffffff(30位1) 與操作, 即超過 30 位的忽略處理
  3. 這 30 位分成 6 段, 每 5 位的數字作為字母表的索引取得特定字元, 依次進行獲得 6 位字元串
  4. 總的 

    md5

      串可以獲得 4 個 6 位串,取裡面的任意一個就可作為這個長 url 的短 url 位址

這種算法雖然會生成四個短連結，但是存在重複幾率．

算法對比

采用自增序列的好處就是簡單好了解易操作．但是由于id随着增大長度不固定，但是這個問題可以通過讓id從指定的數字開始遞增即可以解決．還有一個問題就是我們使用的短碼是有序的，可能會存在安全方面的問題．當然相關的防護手法也有很多，比如簽名驗證之類的安全政策；我們也可以自己實作安全手法，比如從一個随機中心值進行開端計數，然後選用一些校檢位算法計算出固定位的校檢碼，将其連接配接起來，得到固定長不遞增的短碼．

第二種算法存在碰撞的問題，雖然産生重複(碰撞)的幾率很小．但是也采用這種算法也有一個好處就是短碼的位數是固定的，不會從一位到多位．

是以這兩種算法各有千秋，如果事務所需要的短連結有效期較短，那麼通過批處理定期清洗，那麼用摘要算法也不錯．而自增算法能夠確定任何懇求量都不會呈現沖突也不失一種非常好的解決算法．

重定向的問題(301還是302)

短連結重定向的執行過程：

  1. 使用者通路短連結：https://dwz.cn/9WnR9Qcx
  2. 短連結伺服器dwz.cn收到請求，根據URL路徑9WnR9Qcx擷取到原始的長連結：http://www.lishanlei.cn/
  3. 伺服器傳回狀态碼，将響應頭中的Location設定為：http://www.lishanlei.cn/
  4. 浏覽器重新向http://www.lishanlei.cn/發送請求
  5. 傳回響應 
Request URL: https://dwz.cn/9WnR9Qcx
Request Method: GET
Status Code: 302 Found
Remote Address: 220.181.164.108:443
Referrer Policy: no-referrer-when-downgrade

Access-Control-Allow-Credentials: true
Access-Control-Allow-Headers: Origin,Accept,Content-Type,X-Requested-With
Access-Control-Allow-Methods: POST,GET,PUT,PATCH,DELETE,HEAD
Access-Control-Allow-Origin: 
Content-Length: 47
Content-Type: text/html; charset=utf-8
Date: Wed, 03 Oct 2018 05:42:18 GMT
Location: http://www.lishanlei.cn/

那麼伺服器在傳回狀态碼時應該選取301還是302呢？

301是永久重定向，而302是臨時重定向．

如果選取301，短連結生成以後就不會變化，是以用301符合http語義，這樣對伺服器的壓力會有所減少．但是這樣一來，我們就無法統計短位址被點選的次數了．

而選擇302會增加伺服器的壓力，但是我們可以統計短連結被點選的次數，這些資料可能對于公司的發展規劃非常重要．

綜上所述，我認為更好的應該選擇302

End

上一篇: java切割字元串并保留分隔符_java – 如何拆分一個字元串,但也保留分隔符？
下一篇: P2936 [USACO09JAN]全流Total Flow