6種常見分布式唯一ID生成策略及它們的優(yōu)缺點(diǎn)對(duì)比

簡(jiǎn)單分析一下需求

所謂全局唯一的 id 其實(shí)往往對(duì)應(yīng)是生成唯一記錄標(biāo)識(shí)的業(yè)務(wù)需求。

這個(gè) id 常常是數(shù)據(jù)庫(kù)的主鍵，數(shù)據(jù)庫(kù)上會(huì)建立聚集索引（cluster index），即在物理存儲(chǔ)上以這個(gè)字段排序。這個(gè)記錄標(biāo)識(shí)上的查詢，往往又有分頁(yè)或者排序的業(yè)務(wù)需求。所以往往要有一個(gè)time字段，并且在time字段上建立普通索引（non-cluster index）。

普通索引存儲(chǔ)的是實(shí)際記錄的指針，其訪問(wèn)效率會(huì)比聚集索引慢，如果記錄標(biāo)識(shí)在生成時(shí)能夠基本按照時(shí)間有序，則可以省去這個(gè)time字段的索引查詢。

這就引出了記錄標(biāo)識(shí)生成的兩大核心需求：

• 全局唯一
• 趨勢(shì)有序

常見生成策略的優(yōu)缺點(diǎn)對(duì)比

方法一: 用數(shù)據(jù)庫(kù)的 auto_increment 來(lái)生成

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

• 此方法使用數(shù)據(jù)庫(kù)原有的功能，所以相對(duì)簡(jiǎn)單
• 能夠保證唯一性
• 能夠保證遞增性
• id 之間的步長(zhǎng)是固定且可自定義的

缺點(diǎn)：

• 可用性難以保證：數(shù)據(jù)庫(kù)常見架構(gòu)是 一主多從 + 讀寫分離，生成自增ID是寫請(qǐng)求 主庫(kù)掛了就玩不轉(zhuǎn)了
• 擴(kuò)展性差，性能有上限：因?yàn)閷懭胧菃吸c(diǎn)，數(shù)據(jù)庫(kù)主庫(kù)的寫性能決定ID的生成性能上限，并且 難以擴(kuò)展

改進(jìn)方案：

• 冗余主庫(kù)，避免寫入單點(diǎn)
• 數(shù)據(jù)水平切分，保證各主庫(kù)生成的ID不重復(fù)

如上圖所述，由1個(gè)寫庫(kù)變成3個(gè)寫庫(kù)，每個(gè)寫庫(kù)設(shè)置不同的 auto_increment 初始值，以及相同的增長(zhǎng)步長(zhǎng)，以保證每個(gè)數(shù)據(jù)庫(kù)生成的ID是不同的（上圖中DB 01生成0,3,6,9…，DB 02生成1,4,7,10，DB 03生成2,5,8,11…）

改進(jìn)后的架構(gòu)保證了可用性，但缺點(diǎn)是

• 喪失了ID生成的“絕對(duì)遞增性”：先訪問(wèn)DB 01生成0,3，再訪問(wèn)DB 02生成1，可能導(dǎo)致在非常短的時(shí)間內(nèi)，ID生成不是絕對(duì)遞增的（這個(gè)問(wèn)題不大，目標(biāo)是趨勢(shì)遞增，不是絕對(duì)遞增
• 數(shù)據(jù)庫(kù)的寫壓力依然很大，每次生成ID都要訪問(wèn)數(shù)據(jù)庫(kù)

為了解決這些問(wèn)題，引出了以下方法：

方法二：?jiǎn)吸c(diǎn)批量ID生成服務(wù)

分布式系統(tǒng)之所以難，很重要的原因之一是“沒有一個(gè)全局時(shí)鐘，難以保證絕對(duì)的時(shí)序”，要想保證絕對(duì)的時(shí)序，還是只能使用單點(diǎn)服務(wù)，用本地時(shí)鐘保證“絕對(duì)時(shí)序”。

數(shù)據(jù)庫(kù)寫壓力大，是因?yàn)槊看紊蒊D都訪問(wèn)了數(shù)據(jù)庫(kù)，可以使用批量的方式降低數(shù)據(jù)庫(kù)寫壓力。

如上圖所述，數(shù)據(jù)庫(kù)使用雙master保證可用性，數(shù)據(jù)庫(kù)中只存儲(chǔ)當(dāng)前ID的最大值，例如4。

ID生成服務(wù)假設(shè)每次批量拉取5個(gè)ID，服務(wù)訪問(wèn)數(shù)據(jù)庫(kù)，將當(dāng)前ID的最大值修改為4，這樣應(yīng)用訪問(wèn)ID生成服務(wù)索要ID，ID生成服務(wù)不需要每次訪問(wèn)數(shù)據(jù)庫(kù)，就能依次派發(fā)0,1,2,3,4這些ID了。

當(dāng)ID發(fā)完后，再將ID的最大值修改為11，就能再次派發(fā)6,7,8,9,10,11這些ID了，于是數(shù)據(jù)庫(kù)的壓力就降低到原來(lái)的1/6。

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

• 保證了ID生成的絕對(duì)遞增有序
• 大大的降低了數(shù)據(jù)庫(kù)的壓力，ID生成可以做到每秒生成幾萬(wàn)幾十萬(wàn)個(gè)

缺點(diǎn)：

• 服務(wù)仍然是單點(diǎn)
• 如果服務(wù)掛了，服務(wù)重啟起來(lái)之后，繼續(xù)生成ID可能會(huì)不連續(xù)，中間出現(xiàn)空洞（服務(wù)內(nèi)存是保存著0,1,2,3,4，數(shù)據(jù)庫(kù)中max-id是4，分配到3時(shí)，服務(wù)重啟了，下次會(huì)從5開始分配，3和4就成了空洞，不過(guò)這個(gè)問(wèn)題也不大）
• 雖然每秒可以生成幾萬(wàn)幾十萬(wàn)個(gè)ID，但畢竟還是有性能上限，無(wú)法進(jìn)行水平擴(kuò)展

改進(jìn)方案

• 單點(diǎn)服務(wù)的常用高可用優(yōu)化方案是“備用服務(wù)”，也叫“影子服務(wù)”，所以我們能用以下方法優(yōu)化上述缺點(diǎn)：

如上圖，對(duì)外提供的服務(wù)是主服務(wù)，有一個(gè)影子服務(wù)時(shí)刻處于備用狀態(tài)，當(dāng)主服務(wù)掛了的時(shí)候影子服務(wù)頂上。這個(gè)切換的過(guò)程對(duì)調(diào)用方是透明的，可以自動(dòng)完成，常用的技術(shù)是 vip+keepalived。另外，id generate service 也可以進(jìn)行水平擴(kuò)展，以解決上述缺點(diǎn)，但會(huì)引發(fā)一致性問(wèn)題。

方法三：uuid / guid

不管是通過(guò)數(shù)據(jù)庫(kù)，還是通過(guò)服務(wù)來(lái)生成ID，業(yè)務(wù)方Application都需要進(jìn)行一次遠(yuǎn)程調(diào)用，比較耗時(shí)。uuid是一種常見的本地生成ID的方法。

UUID uuid = UUID.randomUUID();

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

• 本地生成ID，不需要進(jìn)行遠(yuǎn)程調(diào)用，時(shí)延低
• 擴(kuò)展性好，基本可以認(rèn)為沒有性能上限

缺點(diǎn)：

• 無(wú)法保證趨勢(shì)遞增
• uuid過(guò)長(zhǎng)，往往用字符串表示，作為主鍵建立索引查詢效率低，常見優(yōu)化方案為“轉(zhuǎn)化為兩個(gè)uint64整數(shù)存儲(chǔ)”或者“折半存儲(chǔ)”（折半后不能保證唯一性）

方法四：取當(dāng)前毫秒數(shù)

uuid是一個(gè)本地算法，生成性能高，但無(wú)法保證趨勢(shì)遞增，且作為字符串ID檢索效率低，有沒有一種能保證遞增的本地算法呢？- 取當(dāng)前毫秒數(shù)是一種常見方案。（搜索公眾號(hào)Java知音，回復(fù)“2021”，送你一份Java面試題寶典）

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

• 本地生成ID，不需要進(jìn)行遠(yuǎn)程調(diào)用，時(shí)延低
• 生成的ID趨勢(shì)遞增
• 生成的ID是整數(shù)，建立索引后查詢效率高

缺點(diǎn)：

• 如果并發(fā)量超過(guò)1000，會(huì)生成重復(fù)的ID
• 這個(gè)缺點(diǎn)要了命了，不能保證ID的唯一性。當(dāng)然，使用微秒可以降低沖突概率，但每秒最多只能生成1000000個(gè)ID，再多的話就一定會(huì)沖突了，所以使用微秒并不從根本上解決問(wèn)題。

方法五：使用 Redis 來(lái)生成 id

當(dāng)使用數(shù)據(jù)庫(kù)來(lái)生成ID性能不夠要求的時(shí)候，我們可以嘗試使用Redis來(lái)生成ID。這主要依賴于Redis是單線程的，所以也可以用生成全局唯一的ID。可以用Redis的原子操作 INCR 和 INCRBY 來(lái)實(shí)現(xiàn)。

（搜索公眾號(hào)Java知音，回復(fù)“2021”，送你一份Java面試題寶典）

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

• 依賴于數(shù)據(jù)庫(kù)，靈活方便，且性能優(yōu)于數(shù)據(jù)庫(kù)。
• 數(shù)字ID天然排序，對(duì)分頁(yè)或者需要排序的結(jié)果很有幫助。

缺點(diǎn)：

• 如果系統(tǒng)中沒有Redis，還需要引入新的組件，增加系統(tǒng)復(fù)雜度。
• 需要編碼和配置的工作量比較大。

方法六：Twitter 開源的 Snowflake 算法

snowflake 是 twitter 開源的分布式ID生成算法，其核心思想為，一個(gè)long型的ID：

• 41 bit 作為毫秒數(shù) - 41位的長(zhǎng)度可以使用69年
• 10 bit 作為機(jī)器編號(hào) （5個(gè)bit是數(shù)據(jù)中心，5個(gè)bit的機(jī)器ID） - 10位的長(zhǎng)度最多支持部署1024個(gè)節(jié)點(diǎn)
• 12 bit 作為毫秒內(nèi)序列號(hào) - 12位的計(jì)數(shù)順序號(hào)支持每個(gè)節(jié)點(diǎn)每毫秒產(chǎn)生4096個(gè)ID序號(hào)

算法單機(jī)每秒內(nèi)理論上最多可以生成1000*(2^12)，也就是400W的ID，完全能滿足業(yè)務(wù)的需求。

該算法 java 版本的實(shí)現(xiàn)代碼如下：

package com;
 
public class SnowflakeIdGenerator {
    //================================================Algorithm's Parameter=============================================
    // 系統(tǒng)開始時(shí)間截 (UTC 2017-06-28 00:00:00)
    private final long startTime = 1498608000000L;
    // 機(jī)器id所占的位數(shù)
    private final long workerIdBits = 5L;
    // 數(shù)據(jù)標(biāo)識(shí)id所占的位數(shù)
    private final long dataCenterIdBits = 5L;
    // 支持的最大機(jī)器id(十進(jìn)制)，結(jié)果是31 (這個(gè)移位算法可以很快的計(jì)算出幾位二進(jìn)制數(shù)所能表示的最大十進(jìn)制數(shù))
    // -1L 左移 5位 (worker id 所占位數(shù)) 即 5位二進(jìn)制所能獲得的最大十進(jìn)制數(shù) - 31
    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
    // 支持的最大數(shù)據(jù)標(biāo)識(shí)id - 31
    private final long maxDataCenterId = -1L ^ (-1L << dataCenterIdBits);
    // 序列在id中占的位數(shù)
    private final long sequenceBits = 12L;
    // 機(jī)器ID 左移位數(shù) - 12 (即末 sequence 所占用的位數(shù))
    private final long workerIdMoveBits = sequenceBits;
    // 數(shù)據(jù)標(biāo)識(shí)id 左移位數(shù) - 17(12+5)
    private final long dataCenterIdMoveBits = sequenceBits + workerIdBits;
    // 時(shí)間截向 左移位數(shù) - 22(5+5+12)
    private final long timestampMoveBits = sequenceBits + workerIdBits + dataCenterIdBits;
    // 生成序列的掩碼(12位所對(duì)應(yīng)的最大整數(shù)值)，這里為4095 (0b111111111111=0xfff=4095)
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);
    //=================================================Works's Parameter================================================
    /**
     * 工作機(jī)器ID(0~31)
     */
    private long workerId;
    /**
     * 數(shù)據(jù)中心ID(0~31)
     */
    private long dataCenterId;
    /**
     * 毫秒內(nèi)序列(0~4095)
     */
    private long sequence = 0L;
    /**
     * 上次生成ID的時(shí)間截
     */
    private long lastTimestamp = -1L;
    //===============================================Constructors=======================================================
    /**
     * 構(gòu)造函數(shù)
     *
     * @param workerId     工作ID (0~31)
     * @param dataCenterId 數(shù)據(jù)中心ID (0~31)
     */
    public SnowflakeIdGenerator(long workerId, long dataCenterId) {
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format("Worker Id can't be greater than %d or less than 0", maxWorkerId));
        }
        if (dataCenterId > maxDataCenterId || dataCenterId < 0) {
            throw new IllegalArgumentException(String.format("DataCenter Id can't be greater than %d or less than 0", maxDataCenterId));
        }
        this.workerId = workerId;
        this.dataCenterId = dataCenterId;
    }
    // ==================================================Methods========================================================
    // 線程安全的獲得下一個(gè) ID 的方法
    public synchronized long nextId() {
        long timestamp = currentTime();
        //如果當(dāng)前時(shí)間小于上一次ID生成的時(shí)間戳: 說(shuō)明系統(tǒng)時(shí)鐘回退過(guò) - 這個(gè)時(shí)候應(yīng)當(dāng)拋出異常
        if (timestamp < lastTimestamp) {
            throw new RuntimeException(
                    String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
        }
        //如果是同一時(shí)間生成的，則進(jìn)行毫秒內(nèi)序列
        if (lastTimestamp == timestamp) {
            sequence = (sequence + 1) & sequenceMask;
            //毫秒內(nèi)序列溢出 即 序列 > 4095
            if (sequence == 0) {
                //阻塞到下一個(gè)毫秒,獲得新的時(shí)間戳
                timestamp = blockTillNextMillis(lastTimestamp);
            }
        }
        //時(shí)間戳改變，毫秒內(nèi)序列重置
        else {
            sequence = 0L;
        }
        //上次生成ID的時(shí)間截
        lastTimestamp = timestamp;
        //移位并通過(guò)或運(yùn)算拼到一起組成64位的ID
        return ((timestamp - startTime) << timestampMoveBits) //
                | (dataCenterId << dataCenterIdMoveBits) //
                | (workerId << workerIdMoveBits) //
                | sequence;
    }
    // 阻塞到下一個(gè)毫秒 即 直到獲得新的時(shí)間戳
    protected long blockTillNextMillis(long lastTimestamp) {
        long timestamp = currentTime();
        while (timestamp <= lastTimestamp) {
            timestamp = currentTime();
        }
        return timestamp;
    }
    // 獲得以毫秒為單位的當(dāng)前時(shí)間
    protected long currentTime() {
        return System.currentTimeMillis();
    }
    //====================================================Test Case=====================================================
    public static void main(String[] args) {
        SnowflakeIdGenerator idWorker = new SnowflakeIdGenerator(0, 0);
        for (int i = 0; i < 100; i++) {
            long id = idWorker.nextId();
            //System.out.println(Long.toBinaryString(id));
            System.out.println(id);
        }
    }
}

END