• 簡單分析一下需求
• 常見生成策略的優(yōu)缺點對比
• 方法一: 用數(shù)據(jù)庫的 auto_increment 來生成
• 方法二：單點批量ID生成服務
• 方法三：uuid / guid
• 方法四：取當前毫秒數(shù)
• 方法五：使用 Redis 來生成 id
• 方法六：Twitter 開源的 Snowflake 算法

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

簡單分析一下需求

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

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

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

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

• 全局唯一
• 趨勢有序

常見生成策略的優(yōu)缺點對比

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

優(yōu)點：

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

缺點：

• 可用性難以保證：數(shù)據(jù)庫常見架構(gòu)是 一主多從 + 讀寫分離，生成自增ID是寫請求 主庫掛了就玩不轉(zhuǎn)了
• 擴展性差，性能有上限：因為寫入是單點，數(shù)據(jù)庫主庫的寫性能決定ID的生成性能上限，并且 難以擴展

改進方案：

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

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

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

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

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

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

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

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

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

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

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

優(yōu)點：

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

缺點：

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

改進方案

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

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

方法三：uuid / guid

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

UUID uuid = UUID.randomUUID();

優(yōu)點：

• 本地生成ID，不需要進行遠程調(diào)用，時延低
• 擴展性好，基本可以認為沒有性能上限

缺點：

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

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

uuid是一個本地算法，生成性能高，但無法保證趨勢遞增，且作為字符串ID檢索效率低，有沒有一種能保證遞增的本地算法呢？- 取當前毫秒數(shù)是一種常見方案。

優(yōu)點：

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

缺點：

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

方法五：使用 Redis 來生成 id

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

優(yōu)點：

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

缺點：

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

方法六：Twitter 開源的 Snowflake 算法

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

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

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

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

package com;

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