如何設計一套高性能的短鏈系統？
什么是短鏈系統？先讓我們來看一張耳熟能詳的圖片：
點擊短信里“藍色字體”，就能跳轉到一個網頁，其背后的秘密就是一套完整的短鏈系統，今天我們就來深入探討如何設計一套高性能短鏈服務！
上圖中那串藍色字符，有個專業的術語叫做“短鏈”，它可以是一個鏈接地址，也可以設計成二維碼。
一、為什么要用短鏈？
存在即合理，這里列舉 3個主要原因。
1.相對安全
短鏈不容易暴露訪問參數，生成方式可以完全迎合短信平臺的規則，能夠有效地規避關鍵詞、域名屏蔽等風險，而原始 URL地址，很可能因為包含特殊字符被短信系統誤判，導致鏈接無法跳轉。
2.美觀
對于精簡的文字，似乎更符合美學觀念，不太讓人產生反感。
3.平臺限制
短信發送平臺有字數限制，在整條短信字數不變的前提下，把鏈接縮短，其他部分的文字描述就能增加，這樣似乎更能達到該短信的實際目的（比如，營銷）。
二、短鏈的組成
如下圖，短鏈的組成通常包含兩個部分：域名 + 隨機碼
短鏈的域名最好和其他業務域名分開，而且要盡量簡短，可以不具備業務含義（比如：xyz.com），因為短鏈大部分是用于營銷，可能會被三方平臺屏蔽。
短鏈的隨機碼需要全局唯一，建議 10位以下。
三、短鏈跳轉的原理
首先，我們先看一個短鏈跳轉的簡單例子，如下代碼，定義了一個 302重定向的代碼示例：
import org.springframework.stereotype.Controller;
import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.PathVariable;
import org.springframework.web.servlet.view.RedirectView;
@Controller
public class RedirectController {
@GetMapping("/{shortCode}")
public RedirectView redirect(@PathVariable String shortCode) {
String destUrl = "https://yuanjava.com";
// destUrl = getDestUrlByShortCode(shortCode); //真實的業務邏輯
return new RedirectView(destUrl);
}
}接著，在瀏覽器訪問短鏈"http://127.0.0.1:8080/s2TYdWd" 后，請求會被重定向到 https://yuanjava.com ，下圖為瀏覽器控制臺信息：
從上圖，我們看到了 302狀態碼并且請求被 Location到另外一個 URL，整個交互流程圖如下：
是不是有一種偷梁換柱的感覺？？？
最后，總結下短鏈跳轉的核心思想：
- 生成隨機碼，將隨機碼和目標 URL（長鏈）的映射關系存入數據庫；
- 用域名+隨機碼生成短鏈，并推送給目標用戶；
- 當用戶點擊短鏈后，請求會先到達短鏈系統，短鏈系統根據隨機碼查找出對應的目標 URL，接著將請求 302重定向到目標 URL（長鏈）；
關于重定向有 301 和 302兩種，如何選擇？
- 302，代表臨時重定向：每次請求短鏈，請求都會先到達短鏈系統，然后重定向到目標 URL（長鏈），這樣，方便短鏈系統做一些統計點擊數等操作；通常采用 302
- 301，代表永久重定向：第一次請求拿到目標長鏈接后，下次再次請求短鏈，請求不會到達短鏈系統，而是直接跳轉到瀏覽器緩存的目標 URL（長鏈），短鏈系統只能統計到第一次訪問的數據；一般不采用 301。
四、如何生成短鏈？
從短鏈組成章節可以總結出：短鏈=域名+隨機碼。因此，如何生成短鏈的問題轉換成了如何生成一個隨機碼，而且這個隨機碼需要全局唯一。
通常來說有 3種做法：
1.Base62
Base62 表示法是一種基數為62的數制系統，包含26個英文大寫字母（A-Z），26個英文小寫字母（a-z）和10個數字（0-9）。這樣，共有62個字符可以用來表示數值。如下代碼：
import java.security.SecureRandom;
public class RandomCodeGenerator {
private static final String CHAR_62 = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
private static final SecureRandom random = new SecureRandom();
public static String generateRandomCode(int length) {
StringBuilder sb = new StringBuilder(length);
for (int i = 0; i < length; i++) {
int rndCharAt = random.nextInt(CHAR_62.length());
char rndChar = CHAR_62.charAt(rndCharAt);
sb.append(rndChar);
}
return sb.toString();
}
}對于 Base62算法，如果是生成 6位隨機數有 62^6 - 1 = 56800235583, 568億多，如果是生成 7位隨機數有 62^7 - 1 = 3521614606208，合計3.5萬億多，足夠使用。
2.Hash算法
Hash算法算法是我們最容易想到的辦法，比如 MD5, SHA-1, SHA-256, MurmurHash, 但是這種算法生成的 Hash算法值還是比較長，常用的做法是把這個 Hash算法值進行 62/64進行壓縮。
如下代碼，通過 Google的 MurmurHash算法把長鏈 Hash成一個 32位的 10進制正數，然后再轉換成62進制（壓縮），這樣就可以得到一個 6位隨機數，
import com.google.common.hash.HashFunction;
import com.google.common.hash.Hashing;
import java.nio.charset.StandardCharsets;
public class MurmurHashToBase62 {
private static final String BASE62 = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
public static String toBase62(int value) {
StringBuilder sb = new StringBuilder();
while (value > 0) {
sb.insert(0, BASE62.charAt(value % 62));
value /= 62;
}
return sb.toString();
}
public static void main(String[] args) {
// 長鏈
String input = "https://yuanjava.cnposts/short-link-system/design?code=xsd&page=1";
// 長鏈利用 MurmurHash算法生成 32位 10進制數
HashFunction hashFunction = Hashing.murmur3_32();
int hash = hashFunction.hashString(input, StandardCharsets.UTF_8).asInt();
if (hash < 0) {
hash = hash & 0x7fffffff; // Convert to positive by dropping the sign bit
}
// 將 32位 10進制數 轉換成 62進制
String base62Hash = toBase62(hash);
System.out.println("base62Hash:" + base62Hash);
}
}3.全局唯一 ID
比如，很多大中型公司都會有自己全局唯一 ID 的生成服務器，可以使用這些服務器生成的 ID來保證全局唯一，也可以使用雪花算法生成全局唯一的ID，再經過 62/64進制壓縮。
五、如何解決沖突
對于上述3種方法的前 2種：base62 或者 hash，因為都是哈希函數，所以，不可避免地會產生哈希沖突（盡管概率很低），該怎么解決呢？
要解決沖突，首先要檢測沖突，通常來說有 3種檢測方法。
1.利用數據庫鎖
如下，這里以 MySQL數據庫為例（也可以保存在 Redis中），表結構如下：
CREATE TABLE `short_url_map` (
`id` int(11) unsigned NOT NULL AUTO_INCREMENT,
`long_url` varchar(160) DEFAULT NULL COMMENT '長鏈',
`short_url` varchar(10) DEFAULT NULL COMMENT '短鏈',
`gmt_create` int(11) DEFAULT NULL COMMENT '創建時間',
PRIMARY KEY (`id`),
UNIQUE INDEX 'short_url' ('short_url')
) ENGINE=InnoDB DEFAULT CHARSET=utf8;首先創建一張長鏈和短鏈的關系映射表，然后通過給 short_url字段添加唯一鎖，這樣，當數據插入時，如果存在 Hash沖突（short_url值相等），數據庫就會拋錯，插入失敗，因此，可以在業務代碼里捕獲對應的錯誤，這樣就能檢測出沖突。
也可以先用 short_url去查詢，如果能查到數據，說明 short_url存在 Hash沖突了。
對于這種通過查詢數據庫或者依賴于數據庫唯一鎖的機制，因為都涉及DB操作，所以對數據庫是一個開銷，如果流量比較大的話，需要保證數據庫的性能。
2.布隆過濾器過濾器
在 DB操作的上游增加一個布隆過濾器，在長鏈生成短鏈后， 先用短鏈在布隆過濾器中進行查找，如果存在就代表沖突了，如果不存在，說明 DB里不存在此短鏈，可以插入。對于布隆過濾器的選擇，單機可以采用 Google的布隆過濾器，分布式可以使用 RedisBloom。
整體流程可以抽象成下圖：
檢測出了沖突，需要如何解決沖突？
再 Hash，可以在長鏈后面拼接一個 UUID之類的隨機字符串，然后再次進行 Hash，用得出的新值再進行上述檢測，這樣 Hash沖突的概率又大大大的降低了。
六、表設計
在整個短鏈系統中，最核心的表就是 長鏈和短鏈的映射關系表，表設計如下：
CREATE TABLE `short_url_map` (
`id` int(11) unsigned NOT NULL AUTO_INCREMENT,
`long_url` varchar(160) DEFAULT NULL COMMENT '長鏈',
`short_url` varchar(10) DEFAULT NULL COMMENT '短鏈',
`gmt_create` int(11) DEFAULT NULL COMMENT '創建時間',
PRIMARY KEY (`id`),
UNIQUE INDEX 'short_url' ('short_url')
) ENGINE=InnoDB DEFAULT CHARSET=utf8;需要對短鏈字段short_url添加一個唯一索引，這樣的話，一方面可以保證 short_url全局唯一，一方面可以通過索引加快以下查詢語句的速度：
select * from short_url_map where short_url = ?七、高并發場景
在流量不大的情況，上述方法怎么折騰似乎都沒有問題，但是，為了架構的健壯性，很多時候需要考慮高并發，大流量的場景，因此架構需要支持水平擴展，比如：
- 采用微服務
- 功能模塊分離，比如，短鏈生成服務和長鏈查詢服務分離
- 功能模塊需要支持水平擴容，比如：短鏈生成服務和長鏈查詢服務能支持動態擴容
- 緩解數據庫壓力，比如，分區，分庫分表，主從，讀寫分離等機制
- 服務的限流，自保機制
- 完善的監控和預警機制
這里給出一套比較完整的設計思路圖：
八、分庫分表
關于短鏈和長鏈映射關系表的分庫分表是一個重點，這里需要詳細分析。
1.是否需要分庫分表
在做技術架構時，很忌諱過度設計，因此，對于高并發場景，是否需要分庫分表，分多少個庫，分多少個表，分庫分表鍵如何選擇等問題都應該根據具體業務數據量進行評估。
2.分庫分表鍵需要如何選擇
如果需要分庫分表，庫和表的 PartitionKey 該如何選擇？
方法一：短鏈碼進行 hash取模
如下算法，確認庫和表的路由規則：
庫ID = 短鏈的 hash值 % 庫數量
表ID = 短鏈的 hash值 / 庫數量 % 表數量該方法需要根據業務的數據量以及庫表設計需要支持幾年的數據總量來評估出庫的數量和表的數量，另外，因為短鏈數據絕大多數都是一次性的，所以可以對存量數據進行歸檔，這樣可以解決數據過多需要擴容的問題。
該方案的優缺點：
優點：
- 分庫分表方式清晰易懂
缺點：
- 擴容比較困難，擴容時需要遷移大量的數據；
- 最開始時就需要把庫和表全部創建好，對于前期數據量不多的時候，是一種浪費；
那么，有沒有一種好的方式，可以支持動態擴容而且盡量不牽涉到數據的遷移呢？這里我們就要看第二種方案。
方法二：支持動態擴容
通過方法一，我們可以知道，庫和表是動態計算出來的，能不能我們固定設置庫和表的標號呢？基于這個想法，我們設計了如下的方案，在隨機碼的前面增加一位代表庫的標號，在隨機碼的后面增加一位代表表的標號，如下圖：
這樣數據庫可以支持62個，每個庫的表可以支持62張表，按照每張表 2000萬條數據，支持的總數據 = 62 * 62 * 2000w = 768.8億，如果還不夠用的話，那可以在隨機碼的前后各增加兩位來表示庫和表，這樣就足夠了。
實現細節：
預先配置分庫分表中庫和表的標號，比如：庫標號 [0,1,2]，表標號 [0,1,2,3]，通過上面的方法獲取到一個隨機碼之后，然后從庫標號 [0,1,2]隨機獲取一個標號，拼接在隨機碼的前面作為庫標識，從表標號 [0,1,2,3]隨機獲取一個標號，拼接在隨機碼的后面作為表，然后在做分庫分表路由的時候，分別截取第一位和最后一位作為庫和表的路由編號。注意，這里是隨機獲取，也可以使用輪詢算法獲取庫標號和表標號。
擴容：
假如，需要對庫標號 [0,1,2]，表標號 [0,1,2,3]進行擴容，只需要將標號添加進去，比如：庫標號[0,1,2,3]，表標號 [0,1,2,3,4,5]，這樣原始的數據不需要進行遷移就完成了庫容操作。
該方案的優缺點：
優點：
- 支持動態擴容
- 動態擴容時不需要遷移數據
缺點
- 需要在隨機碼前后增加庫和表的標識，增加了短鏈的長度
- 庫標識和表標識添加的算法，直接影響數據的離散性
總結
本文從一條客服評價的短信開始，分析了短鏈的構成，短鏈跳轉的原理，同時也給出了業內的一些實現算法，以及一些架構上的建議。
對于業務體量小的公司，可以根據成本來搭建服務（單機或者少量服務器做負載），對于業務體量比較大的公司，更多需要考慮到高并發的場景，如何保證服務的穩定性，如何支持水平擴展，當服務出現問題時如何具備一套完善的監控和預警服務器。
其實，很多系統都是在一次又一次的業務流量挑戰下成長起來的，我們需要不斷打磨自己宏觀看架構，微觀看代碼的能力，這樣自己也就跟著業務，系統一起成長起來了。
