什么是短鏈系統(tǒng)？先讓我們來看一張耳熟能詳?shù)膱D片：

點(diǎn)擊短信里“藍(lán)色字體”，就能跳轉(zhuǎn)到一個(gè)網(wǎng)頁，其背后的秘密就是一套完整的短鏈系統(tǒng)，今天我們就來深入探討如何設(shè)計(jì)一套高性能短鏈服務(wù)！

上圖中那串藍(lán)色字符，有個(gè)專業(yè)的術(shù)語叫做“短鏈”，它可以是一個(gè)鏈接地址，也可以設(shè)計(jì)成二維碼。

一、為什么要用短鏈？

存在即合理，這里列舉 3個(gè)主要原因。

1.相對(duì)安全

短鏈不容易暴露訪問參數(shù)，生成方式可以完全迎合短信平臺(tái)的規(guī)則，能夠有效地規(guī)避關(guān)鍵詞、域名屏蔽等風(fēng)險(xiǎn)，而原始 URL地址，很可能因?yàn)榘厥庾址欢绦畔到y(tǒng)誤判，導(dǎo)致鏈接無法跳轉(zhuǎn)。

2.美觀

對(duì)于精簡(jiǎn)的文字，似乎更符合美學(xué)觀念，不太讓人產(chǎn)生反感。

3.平臺(tái)限制

短信發(fā)送平臺(tái)有字?jǐn)?shù)限制，在整條短信字?jǐn)?shù)不變的前提下，把鏈接縮短，其他部分的文字描述就能增加，這樣似乎更能達(dá)到該短信的實(shí)際目的（比如，營銷）。

二、短鏈的組成

如下圖，短鏈的組成通常包含兩個(gè)部分：域名 + 隨機(jī)碼

短鏈的域名最好和其他業(yè)務(wù)域名分開，而且要盡量簡(jiǎn)短，可以不具備業(yè)務(wù)含義（比如：xyz.com），因?yàn)槎替湸蟛糠质怯糜跔I銷，可能會(huì)被三方平臺(tái)屏蔽。

短鏈的隨機(jī)碼需要全局唯一，建議 10位以下。

三、短鏈跳轉(zhuǎn)的原理

首先，我們先看一個(gè)短鏈跳轉(zhuǎn)的簡(jiǎn)單例子，如下代碼，定義了一個(gè) 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); //真實(shí)的業(yè)務(wù)邏輯
    return new RedirectView(destUrl);
  }
}

接著，在瀏覽器訪問短鏈"http://127.0.0.1:8080/s2TYdWd" 后，請(qǐng)求會(huì)被重定向到 https://yuanjava.com ，下圖為瀏覽器控制臺(tái)信息：

從上圖，我們看到了 302狀態(tài)碼并且請(qǐng)求被 Location到另外一個(gè) URL，整個(gè)交互流程圖如下：

是不是有一種偷梁換柱的感覺？？？

最后，總結(jié)下短鏈跳轉(zhuǎn)的核心思想：

• 生成隨機(jī)碼，將隨機(jī)碼和目標(biāo) URL（長鏈）的映射關(guān)系存入數(shù)據(jù)庫；
• 用域名+隨機(jī)碼生成短鏈，并推送給目標(biāo)用戶；
• 當(dāng)用戶點(diǎn)擊短鏈后，請(qǐng)求會(huì)先到達(dá)短鏈系統(tǒng)，短鏈系統(tǒng)根據(jù)隨機(jī)碼查找出對(duì)應(yīng)的目標(biāo) URL，接著將請(qǐng)求 302重定向到目標(biāo) URL（長鏈）；

關(guān)于重定向有 301 和 302兩種，如何選擇？

• 302，代表臨時(shí)重定向：每次請(qǐng)求短鏈，請(qǐng)求都會(huì)先到達(dá)短鏈系統(tǒng)，然后重定向到目標(biāo) URL（長鏈），這樣，方便短鏈系統(tǒng)做一些統(tǒng)計(jì)點(diǎn)擊數(shù)等操作；通常采用 302
• 301，代表永久重定向：第一次請(qǐng)求拿到目標(biāo)長鏈接后，下次再次請(qǐng)求短鏈，請(qǐng)求不會(huì)到達(dá)短鏈系統(tǒng)，而是直接跳轉(zhuǎn)到瀏覽器緩存的目標(biāo) URL（長鏈），短鏈系統(tǒng)只能統(tǒng)計(jì)到第一次訪問的數(shù)據(jù)；一般不采用 301。

四、如何生成短鏈？

從短鏈組成章節(jié)可以總結(jié)出：短鏈=域名+隨機(jī)碼。因此，如何生成短鏈的問題轉(zhuǎn)換成了如何生成一個(gè)隨機(jī)碼，而且這個(gè)隨機(jī)碼需要全局唯一。

通常來說有 3種做法：

1.Base62

Base62 表示法是一種基數(shù)為62的數(shù)制系統(tǒng)，包含26個(gè)英文大寫字母（A-Z），26個(gè)英文小寫字母（a-z）和10個(gè)數(shù)字（0-9）。這樣，共有62個(gè)字符可以用來表示數(shù)值。如下代碼：

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();
  }
}

對(duì)于 Base62算法，如果是生成 6位隨機(jī)數(shù)有 62^6 - 1 = 56800235583, 568億多，如果是生成 7位隨機(jī)數(shù)有 62^7 - 1 = 3521614606208，合計(jì)3.5萬億多，足夠使用。

2.Hash算法

Hash算法算法是我們最容易想到的辦法，比如 MD5, SHA-1, SHA-256, MurmurHash, 但是這種算法生成的 Hash算法值還是比較長，常用的做法是把這個(gè) Hash算法值進(jìn)行 62/64進(jìn)行壓縮。

如下代碼，通過 Google的 MurmurHash算法把長鏈 Hash成一個(gè) 32位的 10進(jìn)制正數(shù)，然后再轉(zhuǎn)換成62進(jìn)制（壓縮），這樣就可以得到一個(gè) 6位隨機(jī)數(shù)，

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進(jìn)制數(shù)
        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進(jìn)制數(shù) 轉(zhuǎn)換成 62進(jìn)制
        String base62Hash = toBase62(hash);
        System.out.println("base62Hash:" + base62Hash);
    }
}

3.全局唯一 ID

比如，很多大中型公司都會(huì)有自己全局唯一 ID 的生成服務(wù)器，可以使用這些服務(wù)器生成的 ID來保證全局唯一，也可以使用雪花算法生成全局唯一的ID，再經(jīng)過 62/64進(jìn)制壓縮。

五、如何解決沖突

對(duì)于上述3種方法的前 2種：base62 或者 hash，因?yàn)槎际枪：瘮?shù)，所以，不可避免地會(huì)產(chǎn)生哈希沖突（盡管概率很低），該怎么解決呢？

要解決沖突，首先要檢測(cè)沖突，通常來說有 3種檢測(cè)方法。

1.利用數(shù)據(jù)庫鎖

如下，這里以 MySQL數(shù)據(jù)庫為例（也可以保存在 Redis中），表結(jié)構(gòu)如下：

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 '創(chuàng)建時(shí)間',
  PRIMARY KEY (`id`),
  UNIQUE INDEX 'short_url' ('short_url')
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

首先創(chuàng)建一張長鏈和短鏈的關(guān)系映射表，然后通過給 short_url字段添加唯一鎖，這樣，當(dāng)數(shù)據(jù)插入時(shí)，如果存在 Hash沖突（short_url值相等），數(shù)據(jù)庫就會(huì)拋錯(cuò)，插入失敗，因此，可以在業(yè)務(wù)代碼里捕獲對(duì)應(yīng)的錯(cuò)誤，這樣就能檢測(cè)出沖突。

也可以先用 short_url去查詢，如果能查到數(shù)據(jù)，說明 short_url存在 Hash沖突了。

對(duì)于這種通過查詢數(shù)據(jù)庫或者依賴于數(shù)據(jù)庫唯一鎖的機(jī)制，因?yàn)槎忌婕癉B操作，所以對(duì)數(shù)據(jù)庫是一個(gè)開銷，如果流量比較大的話，需要保證數(shù)據(jù)庫的性能。

2.布隆過濾器過濾器

在 DB操作的上游增加一個(gè)布隆過濾器，在長鏈生成短鏈后， 先用短鏈在布隆過濾器中進(jìn)行查找，如果存在就代表沖突了，如果不存在，說明 DB里不存在此短鏈，可以插入。對(duì)于布隆過濾器的選擇，單機(jī)可以采用 Google的布隆過濾器，分布式可以使用 RedisBloom。

整體流程可以抽象成下圖：

檢測(cè)出了沖突，需要如何解決沖突？

再 Hash，可以在長鏈后面拼接一個(gè) UUID之類的隨機(jī)字符串，然后再次進(jìn)行 Hash，用得出的新值再進(jìn)行上述檢測(cè)，這樣 Hash沖突的概率又大大大的降低了。

六、表設(shè)計(jì)

在整個(gè)短鏈系統(tǒng)中，最核心的表就是 長鏈和短鏈的映射關(guān)系表，表設(shè)計(jì)如下：

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 '創(chuàng)建時(shí)間',
  PRIMARY KEY (`id`),
  UNIQUE INDEX 'short_url' ('short_url')
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

需要對(duì)短鏈字段short_url添加一個(gè)唯一索引，這樣的話，一方面可以保證 short_url全局唯一，一方面可以通過索引加快以下查詢語句的速度：

select * from short_url_map  where short_url = ?

七、高并發(fā)場(chǎng)景

在流量不大的情況，上述方法怎么折騰似乎都沒有問題，但是，為了架構(gòu)的健壯性，很多時(shí)候需要考慮高并發(fā)，大流量的場(chǎng)景，因此架構(gòu)需要支持水平擴(kuò)展，比如：

• 采用微服務(wù)
• 功能模塊分離，比如，短鏈生成服務(wù)和長鏈查詢服務(wù)分離
• 功能模塊需要支持水平擴(kuò)容，比如：短鏈生成服務(wù)和長鏈查詢服務(wù)能支持動(dòng)態(tài)擴(kuò)容
• 緩解數(shù)據(jù)庫壓力，比如，分區(qū)，分庫分表，主從，讀寫分離等機(jī)制
• 服務(wù)的限流，自保機(jī)制
• 完善的監(jiān)控和預(yù)警機(jī)制

這里給出一套比較完整的設(shè)計(jì)思路圖：

八、分庫分表

關(guān)于短鏈和長鏈映射關(guān)系表的分庫分表是一個(gè)重點(diǎn)，這里需要詳細(xì)分析。

1.是否需要分庫分表

在做技術(shù)架構(gòu)時(shí)，很忌諱過度設(shè)計(jì)，因此，對(duì)于高并發(fā)場(chǎng)景，是否需要分庫分表，分多少個(gè)庫，分多少個(gè)表，分庫分表鍵如何選擇等問題都應(yīng)該根據(jù)具體業(yè)務(wù)數(shù)據(jù)量進(jìn)行評(píng)估。

2.分庫分表鍵需要如何選擇

如果需要分庫分表，庫和表的 PartitionKey 該如何選擇？

方法一：短鏈碼進(jìn)行 hash取模

如下算法，確認(rèn)庫和表的路由規(guī)則：

庫ID = 短鏈的 hash值 % 庫數(shù)量
表ID = 短鏈的 hash值 / 庫數(shù)量  % 表數(shù)量

該方法需要根據(jù)業(yè)務(wù)的數(shù)據(jù)量以及庫表設(shè)計(jì)需要支持幾年的數(shù)據(jù)總量來評(píng)估出庫的數(shù)量和表的數(shù)量，另外，因?yàn)槎替湐?shù)據(jù)絕大多數(shù)都是一次性的，所以可以對(duì)存量數(shù)據(jù)進(jìn)行歸檔，這樣可以解決數(shù)據(jù)過多需要擴(kuò)容的問題。

該方案的優(yōu)缺點(diǎn)：

優(yōu)點(diǎn)：

• 分庫分表方式清晰易懂

缺點(diǎn)：

• 擴(kuò)容比較困難，擴(kuò)容時(shí)需要遷移大量的數(shù)據(jù)；
• 最開始時(shí)就需要把庫和表全部創(chuàng)建好，對(duì)于前期數(shù)據(jù)量不多的時(shí)候，是一種浪費(fèi)；

那么，有沒有一種好的方式，可以支持動(dòng)態(tài)擴(kuò)容而且盡量不牽涉到數(shù)據(jù)的遷移呢？這里我們就要看第二種方案。

方法二：支持動(dòng)態(tài)擴(kuò)容

通過方法一，我們可以知道，庫和表是動(dòng)態(tài)計(jì)算出來的，能不能我們固定設(shè)置庫和表的標(biāo)號(hào)呢？基于這個(gè)想法，我們?cè)O(shè)計(jì)了如下的方案，在隨機(jī)碼的前面增加一位代表庫的標(biāo)號(hào)，在隨機(jī)碼的后面增加一位代表表的標(biāo)號(hào)，如下圖：

這樣數(shù)據(jù)庫可以支持62個(gè)，每個(gè)庫的表可以支持62張表，按照每張表 2000萬條數(shù)據(jù)，支持的總數(shù)據(jù) = 62 * 62 * 2000w = 768.8億，如果還不夠用的話，那可以在隨機(jī)碼的前后各增加兩位來表示庫和表，這樣就足夠了。

實(shí)現(xiàn)細(xì)節(jié)：

預(yù)先配置分庫分表中庫和表的標(biāo)號(hào)，比如：庫標(biāo)號(hào) [0,1,2]，表標(biāo)號(hào) [0,1,2,3]，通過上面的方法獲取到一個(gè)隨機(jī)碼之后，然后從庫標(biāo)號(hào) [0,1,2]隨機(jī)獲取一個(gè)標(biāo)號(hào)，拼接在隨機(jī)碼的前面作為庫標(biāo)識(shí)，從表標(biāo)號(hào) [0,1,2,3]隨機(jī)獲取一個(gè)標(biāo)號(hào)，拼接在隨機(jī)碼的后面作為表，然后在做分庫分表路由的時(shí)候，分別截取第一位和最后一位作為庫和表的路由編號(hào)。注意，這里是隨機(jī)獲取，也可以使用輪詢算法獲取庫標(biāo)號(hào)和表標(biāo)號(hào)。

擴(kuò)容：

假如，需要對(duì)庫標(biāo)號(hào) [0,1,2]，表標(biāo)號(hào) [0,1,2,3]進(jìn)行擴(kuò)容，只需要將標(biāo)號(hào)添加進(jìn)去，比如：庫標(biāo)號(hào)[0,1,2,3]，表標(biāo)號(hào) [0,1,2,3,4,5]，這樣原始的數(shù)據(jù)不需要進(jìn)行遷移就完成了庫容操作。

該方案的優(yōu)缺點(diǎn)：

優(yōu)點(diǎn)：

• 支持動(dòng)態(tài)擴(kuò)容
• 動(dòng)態(tài)擴(kuò)容時(shí)不需要遷移數(shù)據(jù)

缺點(diǎn)

• 需要在隨機(jī)碼前后增加庫和表的標(biāo)識(shí)，增加了短鏈的長度
• 庫標(biāo)識(shí)和表標(biāo)識(shí)添加的算法，直接影響數(shù)據(jù)的離散性

總結(jié)

本文從一條客服評(píng)價(jià)的短信開始，分析了短鏈的構(gòu)成，短鏈跳轉(zhuǎn)的原理，同時(shí)也給出了業(yè)內(nèi)的一些實(shí)現(xiàn)算法，以及一些架構(gòu)上的建議。

對(duì)于業(yè)務(wù)體量小的公司，可以根據(jù)成本來搭建服務(wù)（單機(jī)或者少量服務(wù)器做負(fù)載），對(duì)于業(yè)務(wù)體量比較大的公司，更多需要考慮到高并發(fā)的場(chǎng)景，如何保證服務(wù)的穩(wěn)定性，如何支持水平擴(kuò)展，當(dāng)服務(wù)出現(xiàn)問題時(shí)如何具備一套完善的監(jiān)控和預(yù)警服務(wù)器。

其實(shí)，很多系統(tǒng)都是在一次又一次的業(yè)務(wù)流量挑戰(zhàn)下成長起來的，我們需要不斷打磨自己宏觀看架構(gòu)，微觀看代碼的能力，這樣自己也就跟著業(yè)務(wù)，系統(tǒng)一起成長起來了。