6 種常見分佈式唯一 ID 生成策略及它們的優缺點對比

作者_：長河_

blog.csdn.net/u010398771/article/details/79765836

全局唯一的 ID 幾乎是所有系統都會遇到的剛需。這個 id 在搜索, 存儲數據, 加快檢索速度等等很多方面都有着重要的意義。有多種策略來獲取這個全局唯一的 id，針對常見的幾種場景，我在這裏進行簡單的總結和對比。

簡單分析一下需求

所謂全局唯一的 id 其實往往對應是生成唯一記錄標識的業務需求。

這個 id 常常是數據庫的主鍵，數據庫上會建立聚集索引（cluster index），即在物理存儲上以這個字段排序。這個記錄標識上的查詢，往往又有分頁或者排序的業務需求。所以往往要有一個 time 字段，並且在 time 字段上建立普通索引（non-cluster index）。

普通索引存儲的是實際記錄的指針，其訪問效率會比聚集索引慢，如果記錄標識在生成時能夠基本按照時間有序，則可以省去這個 time 字段的索引查詢。

這就引出了記錄標識生成的兩大核心需求：

全局唯一
趨勢有序

常見生成策略的優缺點對比

方法一: 用數據庫的 auto_increment 來生成

優點：

此方法使用數據庫原有的功能，所以相對簡單
能夠保證唯一性
能夠保證遞增性
id 之間的步長是固定且可自定義的

缺點：

可用性難以保證：數據庫常見架構是一主多從 + 讀寫分離，生成自增 ID 是寫請求主庫掛了就玩不轉了
擴展性差，性能有上限：因爲寫入是單點，數據庫主庫的寫性能決定 ID 的生成性能上限，並且難以擴展

改進方案：

冗餘主庫，避免寫入單點
數據水平切分，保證各主庫生成的 ID 不重複

方法一改進方案的結構圖

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

改進後的架構保證了可用性，但缺點是

喪失了 ID 生成的 “絕對遞增性”：先訪問 DB 01 生成 0,3，再訪問 DB 02 生成 1，可能導致在非常短的時間內，ID 生成不是絕對遞增的（這個問題不大，目標是趨勢遞增，不是絕對遞增
數據庫的寫壓力依然很大，每次生成 ID 都要訪問數據庫

爲了解決這些問題，引出了以下方法：

方法二：單點批量 ID 生成服務

分佈式系統之所以難，很重要的原因之一是 “沒有一個全局時鐘，難以保證絕對的時序”，要想保證絕對的時序，還是隻能使用單點服務，用本地時鐘保證 “絕對時序”。

數據庫寫壓力大，是因爲每次生成 ID 都訪問了數據庫，可以使用批量的方式降低數據庫寫壓力。

方法二的結構圖

如上圖所述，數據庫使用雙 master 保證可用性，數據庫中只存儲當前 ID 的最大值，例如 4。

ID 生成服務假設每次批量拉取 5 個 ID，服務訪問數據庫，將當前 ID 的最大值修改爲 4，這樣應用訪問 ID 生成服務索要 ID，ID 生成服務不需要每次訪問數據庫，就能依次派發 0,1,2,3,4 這些 ID 了。

當 ID 發完後，再將 ID 的最大值修改爲 11，就能再次派發 6,7,8,9,10,11 這些 ID 了，於是數據庫的壓力就降低到原來的 1/6。

優點：

保證了 ID 生成的絕對遞增有序
大大的降低了數據庫的壓力，ID 生成可以做到每秒生成幾萬幾十萬個

缺點：

服務仍然是單點
如果服務掛了，服務重啓起來之後，繼續生成 ID 可能會不連續，中間出現空洞（服務內存是保存着 0,1,2,3,4，數據庫中 max-id 是 4，分配到 3 時，服務重啓了，下次會從 5 開始分配，3 和 4 就成了空洞，不過這個問題也不大）
雖然每秒可以生成幾萬幾十萬個 ID，但畢竟還是有性能上限，無法進行水平擴展

改進方案

單點服務的常用高可用優化方案是 “備用服務”，也叫 “影子服務”，所以我們能用以下方法優化上述缺點：

方法二改進方案的結構圖

如上圖，對外提供的服務是主服務，有一個影子服務時刻處於備用狀態，當主服務掛了的時候影子服務頂上。這個切換的過程對調用方是透明的，可以自動完成，常用的技術是 vip+keepalived。另外，id generate service 也可以進行水平擴展，以解決上述缺點，但會引發一致性問題。

方法三：uuid / guid

不管是通過數據庫，還是通過服務來生成 ID，業務方 Application 都需要進行一次遠程調用，比較耗時。uuid 是一種常見的本地生成 ID 的方法。

UUID uuid = UUID.randomUUID();

優點：

本地生成 ID，不需要進行遠程調用，時延低
擴展性好，基本可以認爲沒有性能上限

缺點：

無法保證趨勢遞增
uuid 過長，往往用字符串表示，作爲主鍵建立索引查詢效率低，常見優化方案爲 “轉化爲兩個 uint64 整數存儲” 或者“折半存儲”（折半後不能保證唯一性）

方法四：取當前毫秒數

uuid 是一個本地算法，生成性能高，但無法保證趨勢遞增，且作爲字符串 ID 檢索效率低，有沒有一種能保證遞增的本地算法呢？- 取當前毫秒數是一種常見方案。（搜索公衆號 Java 知音，回覆 “2021”，送你一份 Java 面試題寶典）

優點：

本地生成 ID，不需要進行遠程調用，時延低
生成的 ID 趨勢遞增
生成的 ID 是整數，建立索引後查詢效率高

缺點：

如果併發量超過 1000，會生成重複的 ID
這個缺點要了命了，不能保證 ID 的唯一性。當然，使用微秒可以降低衝突概率，但每秒最多隻能生成 1000000 個 ID，再多的話就一定會衝突了，所以使用微秒並不從根本上解決問題。

方法五：使用 Redis 來生成 id

當使用數據庫來生成 ID 性能不夠要求的時候，我們可以嘗試使用 Redis 來生成 ID。這主要依賴於 Redis 是單線程的，所以也可以用生成全局唯一的 ID。可以用 Redis 的原子操作 INCR 和 INCRBY 來實現。

（搜索公衆號 Java 知音，回覆 “2021”，送你一份 Java 面試題寶典）

優點：

依賴於數據庫，靈活方便，且性能優於數據庫。
數字 ID 天然排序，對分頁或者需要排序的結果很有幫助。

缺點：

如果系統中沒有 Redis，還需要引入新的組件，增加系統複雜度。
需要編碼和配置的工作量比較大。

方法六：Twitter 開源的 Snowflake 算法

snowflake 是 twitter 開源的分佈式 ID 生成算法，其核心思想爲，一個 long 型的 ID：

41 bit 作爲毫秒數 - 41 位的長度可以使用 69 年
10 bit 作爲機器編號（5 個 bit 是數據中心，5 個 bit 的機器 ID） - 10 位的長度最多支持部署 1024 個節點
12 bit 作爲毫秒內序列號 - 12 位的計數順序號支持每個節點每毫秒產生 4096 個 ID 序號

Snowflake 圖示

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

該算法 java 版本的實現代碼如下：

package com;

 public class SnowflakeIdGenerator {
    //================================================Algorithm's Parameter=============================================
    // 系統開始時間截 (UTC 2017-06-28 00:00:00)
    private final long startTime = 1498608000000L;
    // 機器id所佔的位數
    private final long workerIdBits = 5L;
    // 數據標識id所佔的位數
    private final long dataCenterIdBits = 5L;
    // 支持的最大機器id(十進制)，結果是31 (這個移位算法可以很快的計算出幾位二進制數所能表示的最大十進制數)
    // -1L 左移 5位 (worker id 所佔位數) 即 5位二進制所能獲得的最大十進制數 - 31
    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
    // 支持的最大數據標識id - 31
    private final long maxDataCenterId = -1L ^ (-1L << dataCenterIdBits);
    // 序列在id中佔的位數
    private final long sequenceBits = 12L;
    // 機器ID 左移位數 - 12 (即末 sequence 所佔用的位數)
    private final long workerIdMoveBits = sequenceBits;
    // 數據標識id 左移位數 - 17(12+5)
    private final long dataCenterIdMoveBits = sequenceBits + workerIdBits;
    // 時間截向 左移位數 - 22(5+5+12)
    private final long timestampMoveBits = sequenceBits + workerIdBits + dataCenterIdBits;
    // 生成序列的掩碼(12位所對應的最大整數值)，這裏爲4095 (0b111111111111=0xfff=4095)
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);
    //=================================================Works's Parameter================================================
    /**
     * 工作機器ID(0~31)
     */
    private long workerId;
    /**
     * 數據中心ID(0~31)
     */
    private long dataCenterId;
    /**
     * 毫秒內序列(0~4095)
     */
    private long sequence = 0L;
    /**
     * 上次生成ID的時間截
     */
    private long lastTimestamp = -1L;
    //===============================================Constructors=======================================================
    /**
     * 構造函數
     *
     * @param workerId     工作ID (0~31)
     * @param dataCenterId 數據中心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========================================================
    // 線程安全的獲得下一個 ID 的方法
    public synchronized long nextId() {
        long timestamp = currentTime();
        //如果當前時間小於上一次ID生成的時間戳: 說明系統時鐘回退過 - 這個時候應當拋出異常
        if (timestamp < lastTimestamp) {
            throw new RuntimeException(
                    String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
        }
        //如果是同一時間生成的，則進行毫秒內序列
        if (lastTimestamp == timestamp) {
            sequence = (sequence + 1) & sequenceMask;
            //毫秒內序列溢出 即 序列 > 4095
            if (sequence == 0) {
                //阻塞到下一個毫秒,獲得新的時間戳
                timestamp = blockTillNextMillis(lastTimestamp);
            }
        }
        //時間戳改變，毫秒內序列重置
        else {
            sequence = 0L;
        }
        //上次生成ID的時間截
        lastTimestamp = timestamp;
        //移位並通過或運算拼到一起組成64位的ID
        return ((timestamp - startTime) << timestampMoveBits) //
                | (dataCenterId << dataCenterIdMoveBits) //
                | (workerId << workerIdMoveBits) //
                | sequence;
    }
    // 阻塞到下一個毫秒 即 直到獲得新的時間戳
    protected long blockTillNextMillis(long lastTimestamp) {
        long timestamp = currentTime();
        while (timestamp <= lastTimestamp) {
            timestamp = currentTime();
        }
        return timestamp;
    }
    // 獲得以毫秒爲單位的當前時間
    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);
        }
    }
}

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/wUlBXHFbJ3_2EavTvd0tyA

簡單分析一下需求

常見生成策略的優缺點對比

方法一: 用數據庫的 auto_increment 來生成

方法二：單點批量 ID 生成服務

方法三：uuid / guid

方法四：取當前毫秒數

方法五：使用 Redis 來生成 id

方法六：Twitter 開源的 Snowflake 算法

猜你喜歡