【轉】分布式全局唯一ID生成策略

為什么分布式系統(tǒng)需要用到ID生成系統(tǒng)

在復雜分布式系統(tǒng)中，往往需要對大量的數(shù)據(jù)和消息進行唯一標識。如在美團點評的金融、支付、餐飲、酒店、貓眼電影等產(chǎn)品的系統(tǒng)中，數(shù)據(jù)日漸增長，對數(shù)據(jù)庫的分庫分表后需要有一個唯一ID來標識一條數(shù)據(jù)或消息，數(shù)據(jù)庫的自增ID顯然不能滿足需求；特別一點的如訂單、騎手、優(yōu)惠券也都需要有唯一ID做標識。此時一個能夠生成全局唯一ID的系統(tǒng)是非常必要的。

概括下來，業(yè)務系統(tǒng)對ID號的要求有哪些呢？

ID生成系統(tǒng)的需求

1.全局唯一性：不能出現(xiàn)重復的ID，最基本的要求。
2.趨勢遞增：MySQL InnoDB引擎使用的是聚集索引，由于多數(shù)RDBMS使用B-tree的數(shù)據(jù)結構來存儲索引數(shù)據(jù)，在主鍵的選擇上面我們應盡量使用有序的主鍵保證寫入性能。
3.單調遞增：保證下一個ID一定大于上一個ID。
4.信息安全：如果ID是連續(xù)遞增的，惡意用戶就可以很容易的窺見訂單號的規(guī)則，從而猜出下一個訂單號，如果是競爭對手，就可以直接知道我們一天的訂單量。所以在某些場景下，需要ID無規(guī)則。

第3、4兩個需求是互斥的，無法同時滿足。

同時，在大型分布式網(wǎng)站架構中，除了需要滿足ID生成自身的需求外，還需要ID生成系統(tǒng)可用性極高。想象以下，如果ID生成系統(tǒng)癱瘓，那么整個業(yè)務無法進行下去，那將是一次災難。
因此，總結ID生成系統(tǒng)還需要滿足如下的需求：
1.高可用，可用性達到5個9或4個9。
2.高QPS，性能不能太差，否則容易造成線程堵塞。
3.平均延遲和TP999(保證99.9%的請求都能成功的最低延遲)延遲都要盡可能低。

ID生成系統(tǒng)的類型

UUID

UUID是指在一臺機器在同一時間中生成的數(shù)字在所有機器中都是唯一的。按照開放軟件基金會(OSF)制定的標準計算，用到了以太網(wǎng)卡地址、納秒級時間、芯片ID碼和許多可能的數(shù)字
UUID由以下幾部分的組合：
（1）當前日期和時間。
（2）時鐘序列。
（3）全局唯一的IEEE機器識別號，如果有網(wǎng)卡，從網(wǎng)卡MAC地址獲得，沒有網(wǎng)卡以其他方式獲得。
標準的UUID格式為：xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx (8-4-4-4-12)，以連字號分為五段形式的36個字符，示例：550e8400-e29b-41d4-a716-446655440000
Java標準類庫中已經(jīng)提供了UUID的API。

UUID.randomUUID()

優(yōu)點

  • 性能非常高：本地生成，沒有網(wǎng)絡消耗。

缺點

  • 不易存儲：UUID太長，16字節(jié)128位，通常以36長度的字符串表示，很多場景不適用。
  • 信息不安全：基于MAC地址生成UUID的算法可能會造成MAC地址泄露，這個漏洞曾被用于尋找梅麗莎病毒的制作者位置。
  • ID作為主鍵時在特定的環(huán)境會存在一些問題，比如做DB主鍵的場景下，UUID就非常不適用。

SnowFlake雪花算法

雪花ID生成的是一個64位的二進制正整數(shù)，然后轉換成10進制的數(shù)。64位二進制數(shù)由如下部分組成：

snowflake id生成規(guī)則
  • 1位標識符：始終是0，由于long基本類型在Java中是帶符號的，最高位是符號位，正數(shù)是0，負數(shù)是1，所以id一般是正數(shù)，最高位是0。
  • 41位時間戳：41位時間截不是存儲當前時間的時間截，而是存儲時間截的差值（當前時間截 - 開始時間截 )得到的值，這里的的開始時間截，一般是我們的id生成器開始使用的時間，由我們程序來指定的。
  • 10位機器標識碼：可以部署在1024個節(jié)點，如果機器分機房（IDC）部署，這10位可以由 5位機房ID + 5位機器ID 組成。
  • 12位序列：毫秒內的計數(shù)，12位的計數(shù)順序號支持每個節(jié)點每毫秒(同一機器，同一時間截)產(chǎn)生4096個ID序號

優(yōu)點

  • 簡單高效，生成速度快。
  • 時間戳在高位，自增序列在低位，整個ID是趨勢遞增的，按照時間有序遞增。
  • 靈活度高，可以根據(jù)業(yè)務需求，調整bit位的劃分，滿足不同的需求。

缺點

  • 依賴機器的時鐘，如果服務器時鐘回撥，會導致重復ID生成。
  • 在分布式環(huán)境上，每個服務器的時鐘不可能完全同步，有時會出現(xiàn)不是全局遞增的情況。

snowflake Java實現(xiàn)

/**
 * Twitter_Snowflake<br>
 * SnowFlake的結構如下(每部分用-分開):<br>
 * 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 <br>
 * 1位標識，由于long基本類型在Java中是帶符號的，最高位是符號位，正數(shù)是0，負數(shù)是1，所以id一般是正數(shù)，最高位是0<br>
 * 41位時間截(毫秒級)，注意，41位時間截不是存儲當前時間的時間截，而是存儲時間截的差值（當前時間截 - 開始時間截)
 * 得到的值），這里的的開始時間截，一般是我們的id生成器開始使用的時間，由我們程序來指定的（如下下面程序IdWorker類的startTime屬性）。
 * 41位的時間截，可以使用69年，年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69<br>
 * 10位的數(shù)據(jù)機器位，可以部署在1024個節(jié)點，包括5位datacenterId和5位workerId<br>
 * 12位序列，毫秒內的計數(shù)，12位的計數(shù)順序號支持每個節(jié)點每毫秒(同一機器，同一時間截)產(chǎn)生4096個ID序號<br>
 * 加起來剛好64位，為一個Long型。<br>
 * SnowFlake的優(yōu)點是，整體上按照時間自增排序，并且整個分布式系統(tǒng)內不會產(chǎn)生ID碰撞(由數(shù)據(jù)中心ID和機器ID作區(qū)分)，并且效率較高，
 * 經(jīng)測試，SnowFlake每秒能夠產(chǎn)生26萬ID左右。
 */
public class SnowflakeIdWorker {

    // ==============================Fields===========================================
    /** 開始時間截 (2015-01-01) */
    private final long twepoch = 1420041600000L;

    /** 機器id所占的位數(shù) */
    private final long workerIdBits = 5L;

    /** 數(shù)據(jù)標識id所占的位數(shù) */
    private final long datacenterIdBits = 5L;

    /** 支持的最大機器id，結果是31 (這個移位算法可以很快的計算出幾位二進制數(shù)所能表示的最大十進制數(shù)) */
    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向左移12位 */
    private final long workerIdShift = sequenceBits;

    /** 數(shù)據(jù)標識id向左移17位(12+5) */
    private final long datacenterIdShift = sequenceBits + workerIdBits;

    /** 時間截向左移22位(5+5+12) */
    private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;

    /** 生成序列的掩碼，這里為4095 (0b111111111111=0xfff=4095) */
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);

    /** 工作機器ID(0~31) */
    private long workerId;

    /** 數(shù)據(jù)中心ID(0~31) */
    private long datacenterId;

    /** 毫秒內序列(0~4095) */
    private long sequence = 0L;

    /** 上次生成ID的時間截 */
    private long lastTimestamp = -1L;

    //==============================Constructors=====================================
    /**
     * 構造函數(shù)
     * @param workerId 工作ID (0~31)
     * @param datacenterId 數(shù)據(jù)中心ID (0~31)
     */
    public SnowflakeIdWorker(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 (該方法是線程安全的)
     * @return SnowflakeId
     */
    public synchronized long nextId() {
        long timestamp = timeGen();

        //如果當前時間小于上一次ID生成的時間戳，說明系統(tǒng)時鐘回退過這個時候應當拋出異常
        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;
            //毫秒內序列溢出
            if (sequence == 0) {
                //阻塞到下一個毫秒,獲得新的時間戳
                timestamp = tilNextMillis(lastTimestamp);
            }
        }
        //時間戳改變，毫秒內序列重置
        else {
            sequence = 0L;
        }

        //上次生成ID的時間截
        lastTimestamp = timestamp;

        //移位并通過或運算拼到一起組成64位的ID
        return ((timestamp - twepoch) << timestampLeftShift) //
                | (datacenterId << datacenterIdShift) //
                | (workerId << workerIdShift) //
                | sequence;
    }

    /**
     * 阻塞到下一個毫秒，直到獲得新的時間戳
     * @param lastTimestamp 上次生成ID的時間截
     * @return 當前時間戳
     */
    protected long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

    /**
     * 返回以毫秒為單位的當前時間
     * @return 當前時間(毫秒)
     */
    protected long timeGen() {
        return System.currentTimeMillis();
    }

    //==============================Test=============================================
    /** 測試 */
    public static void main(String[] args) {
        SnowflakeIdWorker idWorker = new SnowflakeIdWorker(0, 0);
        for (int i = 0; i < 1000; i++) {
            long id = idWorker.nextId();
            System.out.println(Long.toBinaryString(id));
            System.out.println(id);
        }
    }
}

數(shù)據(jù)庫自增ID機制

主要思路是采用數(shù)據(jù)庫自增ID + replace_into實現(xiàn)唯一ID的獲取。

create table t_global_id(
    id bigint(20) unsigned not null auto_increment,
    stub char(1) not null default '',
    primary key (id),
    unique key stub (stub)
) engine=MyISAM;


# 每次業(yè)務可以使用以下SQL讀寫MySQL得到ID號
replace into t_golbal_id(stub) values('a');
select last_insert_id();

replace into跟insert功能類似，不同點在于：replace into首先嘗試插入數(shù)據(jù)列表中，如果發(fā)現(xiàn)表中已經(jīng)有此行數(shù)據(jù)（根據(jù)主鍵或唯一索引判斷）則先刪除，再插入。否則直接插入新數(shù)據(jù)。
當然為了避免數(shù)據(jù)庫的單點故障，最少需要兩個數(shù)據(jù)庫實例，通過區(qū)分auto_increment的起始值和步長來生成奇偶數(shù)的ID。如下：

Server1：
auto-increment-increment = 2
auto-increment-offset = 1

Server2：
auto-increment-increment = 2
auto-increment-offset = 2

優(yōu)點

  • 簡單。充分借助數(shù)據(jù)庫的自增ID機制，可靠性高，生成有序的ID。

缺點

  • ID生成依賴數(shù)據(jù)庫單機的讀寫性能。
  • 依賴數(shù)據(jù)庫，當數(shù)據(jù)庫異常時整個系統(tǒng)不可用。

對于MySQL的性能問題，可以用如下方案解決
在分布式環(huán)境中，我們可以部署N臺數(shù)據(jù)庫實例，每臺設置成不同的初始值，自增步長為機器的臺數(shù)。每臺的初始值分別為1,2,3...N，步長為N。

MySQL數(shù)據(jù)庫自增ID多機圖

以上方案雖然解決了性能問題，但是也存在很大的局限性：

  • 系統(tǒng)水平擴容困難：系統(tǒng)定義好步長之后，增加機器之后調整步長困難。如果要添加機器怎么辦？假設現(xiàn)在只有一臺機器發(fā)號是1,2,3,4,5（步長是1），這個時候需要擴容機器一臺。可以這樣做：把第二臺機器的初始值設置得比第一臺超過很多，比如14（假設在擴容時間之內第一臺不可能發(fā)到14），同時設置步長為2，那么這臺機器下發(fā)的號碼都是14以后的偶數(shù)。然后摘掉第一臺，把ID值保留為奇數(shù)，比如7，然后修改第一臺的步長為2。讓它符合我們定義的號段標準，對于這個例子來說就是讓第一臺以后只能產(chǎn)生奇數(shù)。擴容方案看起來復雜嗎？貌似還好，現(xiàn)在想象一下如果我們線上有100臺機器，這個時候要擴容該怎么做？簡直是噩夢。
  • 數(shù)據(jù)庫壓力大：每次獲取一個ID都必須讀寫一次數(shù)據(jù)庫。當然對于這種問題，也有相應的解決方案，就是每次獲取ID時都批量獲取一個區(qū)間的號段到內存中，用完之后再來獲取。數(shù)據(jù)庫的性能提高了幾個量級。

第三方軟件生成（Redis）

Redis實現(xiàn)了一個原子操作INCR和INCRBY實現(xiàn)遞增的操作。當使用數(shù)據(jù)庫性能不夠時，可以采用Redis來代替，同時使用Redis集群來提高吞吐量?？梢猿跏蓟颗_Redis的初始值為1,2,3,4,5，然后步長為5。各個Redis生成的ID為：

A：1，6，11，16，21
B：2，7，12，17，22
C：3，8，13，18，23
D：4，9，14，19，24
E：5，10，15，20，25

優(yōu)點

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

缺點：

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

關于分布式全局唯一ID的生成，各個互聯(lián)網(wǎng)公司有很多實現(xiàn)方案，比如美團點評的Leaf-snowflake，用zookeeper解決了各個服務器時鐘回撥的問題，弱依賴zookeeper。以及Leaf-segment類似上面數(shù)據(jù)庫批量ID獲取的方案。

最后編輯于 ：
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
【社區(qū)內容提示】社區(qū)部分內容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內容（如有圖片或視頻亦包括在內）由作者上傳并發(fā)布，文章內容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內容

友情鏈接更多精彩內容