現在的位置: 首頁 > 云計算 > 正文

如何實現一個短鏈接服務?怎么跳轉

2020年01月16日 云計算 ⁄ 共 3193字 ⁄ 字號 評論關閉

  短鏈接,通俗來說,就是將長的URL網址,通過程序計算等方式,轉換為簡短的網址字符串。

  大家經常會收到一些莫名的營銷短信,里面有一個非常短的鏈接讓你跳轉。新浪微博因為限制字數,所以也會經常見到這種看著不像網址的網址。短鏈的興起應該就是微博限制字數激起了大家的創造力。

  如果創建一個短鏈系統,我們應該做什么呢?

  將長鏈接變為短鏈;

  用戶訪問短鏈接,會跳轉到正確的長鏈接上去。

  查找到對應的長網址,并跳轉到對應的頁面。

  短鏈生成方法

  短碼一般是由 [a - z, A - Z, 0 - 9] 這62 個字母或數字組成,短碼的長度也可以自定義,但一般不超過8位。比較常用的都是6位,6位的短碼已經能有568億種的組合:(26+26+10)^6 = 56800235584,已滿足絕大多數的使用場景。

  目前比較流行的生成短碼方法有:自增id、摘要算法、普通隨機數。

  自增id

  該方法是一種無碰撞的方法,原理是,每新增一個短碼,就在上次添加的短碼id基礎上加1,然后將這個10進制的id值,轉化成一個62進制的字符串。

  一般利用數據表中的自增id來完成:每次先查詢數據表中的自增id最大值max,那么需要插入的長網址對應自增id值就是 max+1,將max+1轉成62進制即可得到短碼。

  但是短碼 id 是從一位長度開始遞增,短碼的長度不固定,不過可以用 id 從指定的數字開始遞增的方式來處理,確保所有的短碼長度都一致。同時,生成的短碼是有序的,可能會有安全的問題,可以將生成的短碼id,結合長網址等其他關鍵字,進行md5運算生成最后的短碼。

  摘要算法

  摘要算法又稱哈希算法,它表示輸入任意長度的數據,輸出固定長度的數據。相同的輸入數據始終得到相同的輸出,不同的輸入數據盡量得到不同的輸出。

  算法過程:

  將長網址md5生成32位簽名串,分為4段, 每段8個字節;

  對這四段循環處理, 取8個字節, 將他看成16進制串與0x3fffffff(30位1)與操作, 即超過30位的忽略處理;

  這30位分成6段, 每5位的數字作為字母表的索引取得特定字符, 依次進行獲得6位字符串;

  總的md5串可以獲得4個6位串;取里面的任意一個就可作為這個長url的短url地址;

  這種算法,雖然會生成4個,但是仍然存在重復幾率。

  雖然幾率很小,但是該方法依然存在碰撞的可能性,解決沖突會比較麻煩。不過該方法生成的短碼位數是固定的,也不存在連續生成的短碼有序的情況。

  普通隨機數

  該方法是從62個字符串中隨機取出一個6位短碼的組合,然后去數據庫中查詢該短碼是否已存在。如果已存在,就繼續循環該方法重新獲取短碼,否則就直接返回。

  該方法是最簡單的一種實現,不過由于Math.round()方法生成的隨機數屬于偽隨機數,碰撞的可能性也不小。在數據比較多的情況下,可能會循環很多次,才能生成一個不沖突的短碼。

  算法分析

  以上算法利弊我們一個一個來分析。

  如果使用自增id算法,會有一個問題就是不法分子是可以窮舉你的短鏈地址的。原理就是將10進制數字轉為62進制,那么別人也可以使用相同的方式遍歷你的短鏈獲取對應的原始鏈接。打個比方說:http://tinyurl.com/a3300和 http://bit.ly/a3300,這兩個短鏈網站,分別從a3300 - a3399,能夠試出來多次返回正確的url。所以這種方式生成的短鏈對于使用者來說其實是不安全的。

  摘要算法,其實就是hash算法吧,一說hash大家可能覺得很low,但是事實上hash可能是最優解。比如:http://www.sina.lt/ 和 http://mrw.so/ 連續生成的url發現并沒有規律,很有可能就是使用hash算法來實現。

  普通隨機數算法,這種算法生成的東西和摘要算法一樣,但是碰撞的概率會大一些。因為摘要算法畢竟是對url進行hash生成,隨機數算法就是簡單的隨機生成,數量一旦上來必然會導致重復。

  綜合以上,我選擇最low的算法:摘要算法。

  實現

  存儲方案

  數據庫存儲方案

  短網址基礎數據采用域名和后綴分開存儲的形式。另外域名需要區分 HTTP 和 HTTPS,hash方案針對整個鏈接進行hash而不是除了域名外的鏈接。域名單獨保存可以用于分析當前域名下鏈接的使用情況。

  增加當前鏈接有效期字段,一般有短鏈需求的可能是相關活動或者熱點事件,這種短鏈在一段時間內會很活躍,過了一定時間熱潮會持續衰退。所以沒有必要將這種鏈接永久保存增加每次查詢的負擔。

  對于過期數據的處理,可以在新增短鏈的時候判斷當前短鏈的失效日期,將每天到達失效日期的數據在HBase單獨建一張表,有新增的時候判斷失效日期放到對應的HBase表中即可,每天只用處理當天HBase表中的失效數據。

  緩存方案

  查詢需求

  個人認為對于幾百個G的數據量都放在緩存肯定是不合適的,所以有個折中的方案:將最近3個月內有查詢或者有新增的url放入緩存,使用LRU算法進行熱更新。這樣最近有使用的發概率會命中緩存,就不用走庫。查不到的時候再走庫更新緩存。

  新增需求

  對于新增的鏈接就先查緩存是否存在,緩存不存在再查庫,數據庫已經分表了,查詢的效率也不會很低。

  緩存的設計

  查詢的需求是用戶拿著短鏈查詢對應的真實地址,那么緩存的key只能是短鏈,可以使用 KV的形式存儲。

  番外

  其實也可以考慮別的存儲方案,比如HBase,HBase作為NOSQL數據庫,性能上僅次于redis但是存儲成本比redis低很多個數量級,存儲基于HDFS,寫數據的時候會先先寫入內存中,只有內存滿了會將數據刷入到HFile。讀數據也會快,原因是因為它使用了LSM樹型結構,而不是B或B+樹。HBase會將最近讀取的數據使用LRU算法放入緩存中,如果想增強讀能力,可以調大blockCache。

  其次,也可以使用ElasticSearch,合適的索引規則效果不輸緩存方案。

  是否有分庫分表的需要?

  對于單條數據10b以內,一億條數據總容量大約為 953G,單表肯定無法撐住這么大的量,所以有分表的需要,如果你對服務很有信心2年內能達到這個規模,那么你可以從一開始設計就考慮分表的方案。

  那么如何定義分表的規則呢?

  如果按照單表500萬條記錄來算,總計可以分為20張表,那么單表容量就是47G,還是挺大,所以考慮分表的 key 和單表容量,如果分為100張表那么單表容量就是10G,并且通過數字后綴路由到表中也比較容易。可以對short_code 做encoding編碼生成數字類型然后做路由。

  如何轉跳

  當我們在瀏覽器里輸入 http://bit.ly/a3300 時,DNS首先解析獲得 http://bit.ly的 IP 地址。當 DNS 獲得 IP 地址以后(比如:12.34.5.32),會向這個地址發送 HTTPGET 請求,查詢短碼 a3300

  [http://bit.ly 服務器會通過短碼 a3300 獲取對應的長 URL請求通過 HTTP301 轉到對應的長 URL http://www.theaustralian.news.com.au/story/0,25197,26089617-5013871,00.html。

  這里有個小的知識點,為什么要用 301 跳轉而不是 302 吶?

  知識點:為什么要使用302跳轉,而不是301跳轉呢?

  301是永久重定向,302是臨時重定向。短地址一經生成就不會變化,所以用301是符合http語義的。但是如果用了301, Google,百度等搜索引擎,搜索的時候會直接展示真實地址,那我們就無法統計到短地址被點擊的次數了,也無法收集用戶的Cookie, User Agent 等信息,這些信息可以用來做很多有意思的大數據分析,也是短網址服務商的主要盈利來源。

抱歉!評論已關閉.

奔驰宝马破解版下载 分分彩如何看走势图 价值投资股票 四川熊猫麻将下载官方下载 互联网平台靠什么赚 篮球技巧视频下载 大庆麻将有什么软件 澳洲幸运8计划 电玩城游戏大厅 微乐捉鸡麻将如何只赢不输 网上项目赚钱 股票投资平台 大嘴棋牌游戏大厅登陆 旺旺高手论坛51538 股票开户开户 快乐扑克官网 捕鱼游戏定制开发