短連結,通俗來說,就是将長的 URL 網址,通過程式計算等方式,轉換為簡短的網址字元串。
大家經常會收到一些莫名的營銷短信,裡面有一個非常短的連結讓你跳轉。新浪微網誌因為限制字數,是以也會經常見到這種看着不像網址的網址。短鍊的興起應該就是微網誌限制字數激起了大家的創造力。
如果建立一個短鍊系統,我們應該做什麼呢?
将長連結變為短鍊;
使用者通路短連結,會跳轉到正确的長連結上去。
查找到對應的長網址,并跳轉到對應的頁面。
短鍊生成方法
短碼一般是由[a - z, A - Z, 0 - 9]這 62 個字母或數字組成,短碼的長度也可以自定義,但一般不超過 8 位。比較常用的都是 6 位,6 位的短碼已經能有 568 億種的組合:(26+26+10)^6 = 56800235584,已滿足絕大多數的使用場景。
目前比較流行的生成短碼方法有:自增id、摘要算法、普通随機數。分布式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 表中的失效資料。
資料庫基礎表如下:
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLicmbw5SOiFWY3QWMiN2M3gzMwYmYmRWO0gjZkhjYzMmYhJWYk9CX5d2bs92Yl1iclB3bsVmdlR2LcNWaw9CXt92Yu4GZjlGbh5yYjV3Lc9CX6MHc0RHaiojIsJye.png)
字段釋義:
base_url:域名
suffix_url:連結除了域名外的字尾
full_url:完整連結
shot_code:目前 suffix_url 連結的短碼
expiration_date:失效日期
total_click_count:目前連結總點選次數
expiration_date:目前連結失效時間
緩存方案
查詢需求
個人認為對于幾百個 G 的資料量都放在緩存肯定是不合适的,是以有個折中的方案:将最近 3 個月内有查詢或者有新增的 url 放入緩存,使用 LRU 算法進行熱更新。這樣最近有使用的發機率會命中緩存,就不用走庫。查不到的時候再走庫更新緩存。
新增需求
對于新增的連結就先查緩存是否存在,緩存不存在再查庫,資料庫已經分表了,查詢的效率也不會很低。
緩存的設計
查詢的需求是使用者拿着短鍊查詢對應的真實位址,那麼緩存的 key 隻能是短鍊,可以使用 KV 的形式存儲。
番外
其實也可以考慮别的存儲方案,比如 HBase,HBase 作為 NOSQL 資料庫,性能上僅次于 redis 但是存儲成本比 redis 低很多個數量級,存儲基于 HDFS,寫資料的時候會先先寫入記憶體中,隻有記憶體滿了會将資料刷入到 HFile。
關注微信公衆号:Java技術棧,在背景回複:redis,可以擷取我整理的 N 篇最新Redis教程,都是幹貨。
讀資料也會快,原因是因為它使用了 LSM 樹型結構,而不是 B 或 B+樹。HBase 會将最近讀取的資料使用 LRU 算法放入緩存中,如果想增強讀能力,可以調大 blockCache。
其次,也可以使用 ElasticSearch,合适的索引規則效果不輸緩存方案。
是否有分庫分表的需要?
對于單條資料 10b 以内,一億條資料總容量大約為 953G,單表肯定無法撐住這麼大的量,是以有分表的需要,如果你對服務很有信心 2 年内能達到這個規模,那麼你可以從一開始設計就考慮分表的方案。推薦:大廠在用的分庫分表方案,看這篇就夠了。
那麼如何定義分表的規則呢?
如果按照單表 500 萬條記錄來算,總計可以分為 20 張表,那麼單表容量就是 47G,還是挺大,是以考慮分表的 key 和單表容量,如果分為 100 張表那麼單表容量就是 10G,并且通過數字字尾路由到表中也比較容易。可以對 short_code 做 encoding 編碼生成數字類型然後做路由。
如何轉跳
當我們在浏覽器裡輸入
時
DNS 首先解析獲得
http://bit.ly的`IP`位址
當DNS獲得IP位址以後(比如:12.34.5.32),會向這個位址發送HTTP``GET請求,查詢短碼a3300
[http://bit.ly 伺服器會通過短碼a3300擷取對應的長 URL
請求通過HTTP 301轉到對應的長 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 等資訊,這些資訊可以用來做很多有意思的大資料分析,也是短網址服務商的主要盈利來源。
引自:
https://www.zhihu.com/question/20103344/answer/573638467附上兩個算法:
摘要算法:
import org.apache.commons.lang3.StringUtils;
import javax.xml.bind.DatatypeConverter;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.concurrent.atomic.AtomicLong;
import static com.alibaba.fastjson.util.IOUtils.DIGITS;
/**
* @author rickiyang
* @date 2020-01-07
* @Desc TODO
*/
public class ShortUrlGenerator {
public static void main(String[] args) {
String sLongUrl = "http://www.baidu.com/121244/ddd";
for (String shortUrl : shortUrl(sLongUrl)) {
System.out.println(shortUrl);
}
}
public static String[] shortUrl(String url) {
// 可以自定義生成 MD5 加密字元傳前的混合 KEY
String key = "dwz";
// 要使用生成 URL 的字元
String[] chars = new String[]{"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", "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"
};
// 對傳入網址進行 MD5 加密
String sMD5EncryptResult = "";
try {
MessageDigest md = MessageDigest.getInstance("MD5");
md.update((key + url).getBytes());
byte[] digest = md.digest();
sMD5EncryptResult = DatatypeConverter.printHexBinary(digest).toUpperCase();
} catch (NoSuchAlgorithmException e) {
e.printStackTrace();
}
String[] resUrl = new String[4];
//得到 4組短連結字元串
for (int i = 0; i < 4; i++) {
// 把加密字元按照 8 位一組 16 進制與 0x3FFFFFFF 進行位與運算
String sTempSubString = sMD5EncryptResult.substring(i * 8, i * 8 \+ 8);
// 這裡需要使用 long 型來轉換,因為 Inteper .parseInt() 隻能處理 31 位 , 首位為符号位 , 如果不用 long ,則會越界
long lHexLong = 0x3FFFFFFF & Long.parseLong(sTempSubString, 16);
String outChars = "";
//循環獲得每組6位的字元串
for (int j = 0; j < 6; j++) {
// 把得到的值與 0x0000003D 進行位與運算,取得字元數組 chars 索引(具體需要看chars數組的長度 以防下标溢出,注意起點為0)
long index = 0x0000003D & lHexLong;
// 把取得的字元相加
outChars += chars[(int) index];
// 每次循環按位右移 5 位
lHexLong = lHexLong >> 5;
}
// 把字元串存入對應索引的輸出數組
resUrl[i] = outChars;
}
return resUrl;
}
}
數字轉為 base62 算法:
/**
* @author rickiyang
* @date 2020-01-07
* @Desc TODO
* <p>
* 進制轉換工具,最大支援十進制和62進制的轉換
* 1、将十進制的數字轉換為指定進制的字元串;
* 2、将其它進制的數字(字元串形式)轉換為十進制的數字
*/
public class NumericConvertUtils {
public static void main(String[] args) {
String str = toOtherNumberSystem(22, 62);
System.out.println(str);
}
/**
* 在進制表示中的字元集合,0-Z分别用于表示最大為62進制的符号表示
*/
private static final char[] digits = {'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',
'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'};
/**
* 将十進制的數字轉換為指定進制的字元串
*
* @param number 十進制的數字
* @param seed 指定的進制
* @return 指定進制的字元串
*/
public static String toOtherNumberSystem(long number, int seed) {
if (number < 0) {
number = ((long) 2 \* 0x7fffffff) \+ number + 2;
}
char[] buf = new char[32];
int charPos = 32;
while ((number / seed) > 0) {
buf[--charPos] = digits[(int) (number % seed)];
number /= seed;
}
buf[--charPos] = digits[(int) (number % seed)];
return new String(buf, charPos, (32 \- charPos));
}
/**
* 将其它進制的數字(字元串形式)轉換為十進制的數字
*
* @param number 其它進制的數字(字元串形式)
* @param seed 指定的進制,也就是參數str的原始進制
* @return 十進制的數字
*/
public static long toDecimalNumber(String number, int seed) {
char[] charBuf = number.toCharArray();
if (seed == 10) {
return Long.parseLong(number);
}
long result = 0, base = 1;
for (int i = charBuf.length - 1; i >= 0; i--) {
int index = 0;
for (int j = 0, length = digits.length; j < length; j++) {
//找到對應字元的下标,對應的下标才是具體的數值
if (digits[j] == charBuf[i]) {
index = j;
}
}
result += index * base;
base *= seed;
}
return result;
}
}