[[408786]]

本文轉(zhuǎn)載自微信公眾號「Java極客技術(shù)」，作者鴨血粉絲。轉(zhuǎn)載本文請聯(lián)系Java極客技術(shù)公眾號。

前言

首先說下我們?yōu)槭裁葱枰植际?ID，以及分布式 ID 是用來解決什么問題的。當(dāng)我們的項目還處于單體架構(gòu)的時候，我們使用數(shù)據(jù)庫的自增 ID 就可以解決很多數(shù)據(jù)標(biāo)識問題。但是隨著我們的業(yè)務(wù)發(fā)展我們的架構(gòu)就會逐漸演變成分布式架構(gòu)，那么這個時候再使用數(shù)據(jù)的自增 ID 就不行了，因為一個業(yè)務(wù)的數(shù)據(jù)可能會放在好幾個數(shù)據(jù)庫里面，此時我們就需要一個分布式 ID 用來標(biāo)識一條數(shù)據(jù)，因此我們需要一個分布式 ID 的生成服務(wù)。那么分布式 ID 的服務(wù)有什么要求和挑戰(zhàn)呢?

要求

全局唯一：既然是用來標(biāo)識數(shù)據(jù)唯一的，那么一個分布式 ID 肯定要是全局唯一的，在同一業(yè)務(wù)下的每個服務(wù)下面都是一致的，不會變的，這是一個基本的要求;

全局遞增：遞增這個也很好理解，我們要保證生成的 ID 是依次遞增的，因為很多時候 ID 是給人看的，如果說不具備遞增性，就缺乏了很多的可讀性;

信息安全：分布式 ID 的安全性也很重要，因為我們提到生成的 ID 是遞增的，這就有可能會給競爭對手知道我們的 ID 的生成頻率，這種在電商等場景會有很大的問題，但是這個往往跟全局遞增有點沖突;

高可用性：分布式 ID 的生成服務(wù)必須是高可用，畢竟一旦不能生成 ID，后續(xù)的所有服務(wù)都無法繼續(xù)使用;

常見的分布式 ID 實現(xiàn)

在當(dāng)下的互聯(lián)網(wǎng)當(dāng)中，根據(jù)業(yè)務(wù)場景以及需求的不同，對于分布式 ID 的實現(xiàn)有如下幾種實現(xiàn)方式：

1. UUID;
2. Redis;
3. 變形的數(shù)據(jù)庫自增 ID;
4. 推特雪花算法
5. 美團的 Leaf——雪花算法的變形;

UUID

寫 Java 的朋友對 UUID 肯定不陌生，7dbb9f04-d15e-4c88-b74b-72a35e0d7580 這是一個標(biāo)準(zhǔn)的 UUID，雖然都說 UUID 是全球唯一，具備我們前面提到的要求中的第一點，但是很顯然不具備全局遞增，這種分布式 ID 可讀性很差，如果說只是用來記錄日志或者不需要人去理解的場景是可以用，但是不適合我們這里說的業(yè)務(wù)數(shù)據(jù)的唯一標(biāo)識。而且這種無序的 UUID 如果作為主鍵會很嚴(yán)重影響性能。

Redis

Redis 有個 incr 的命令，這個命令是能保證原子遞增的，在某種程度上也是可以生成全局 ID，不過使用 Redis 有兩個問題：

1. 不美觀，雖然說我們需要的是一個全局 ID，但是 incr 命令是從 1 開始的整型，所以會導(dǎo)致全局 ID 的長度不一致，雖然說也可以用來標(biāo)識唯一業(yè)務(wù)數(shù)據(jù)，但是某些場景也缺少可讀性，因為不攜帶日期信息;
2. 依賴 Redis 的高可用，因為 Redis 是基于內(nèi)存的，為了保證 ID 的不丟失所以需要對 Redis 進(jìn)行持久化，但是關(guān)于 Redis 的兩種持久化的方式各有優(yōu)缺點，詳細(xì)的可以參考公眾號之前的文章 面試官：請說下 Redis 是如何保證在宕機后數(shù)據(jù)不丟失的;

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

前面我們提到單個數(shù)據(jù)庫在分布式環(huán)境下已經(jīng)沒辦法使用自增 ID 了，因為每個 MySQL 的實例自增 ID 都是從 1 開始，并且步長都按照 1依次遞增，這種情況下我們很容易想到是不是可以考慮給每個數(shù)據(jù)庫設(shè)置不同的步長。如果我們設(shè)置了不同的步長，這樣就可以保證每個數(shù)據(jù)庫實例都可以生成 ID，并且不會重復(fù)。雖然簡單的系統(tǒng)可以這樣用，但是也有幾個問題：

依賴數(shù)據(jù)庫 DB，在分布式環(huán)境下，如果過多的依賴數(shù)據(jù)庫是有風(fēng)險的，無法支持高并發(fā)的情況，特別是對于一些電商交易的場景，每秒幾十萬的 QPS，數(shù)據(jù)庫是扛不住的;

不同數(shù)據(jù)庫實例的數(shù)據(jù)不能直接關(guān)聯(lián)上，需要額外的存儲，才能把數(shù)據(jù)串起來，增加業(yè)務(wù)復(fù)雜度;

推特的雪花算法—— snowflake

snowflake 算法是推特開源的分布式 ID 生成算法，這個算法提供了一個標(biāo)準(zhǔn)的思路，很多公司都參考這個算法做了自己的實現(xiàn)，比較有名的是美團的 Leaf。這里我們就著重看下雪花算法是怎么實現(xiàn)的。

感興趣的可以去參考文章 https://tech.meituan.com/2017/04/21/mt-leaf.html 看下美團的 leaf 的實現(xiàn)原理。

雪花算法的思想是化整為零，將分布式 ID 的生成分散到每個機房和機器上，采用一個 64 位 long 類型的的結(jié)構(gòu)來表示一個 ID，64 的結(jié)構(gòu)如下所示，第一位符號位 0，然后是 41 位的時間戳，接下來的 10 位是機房加機器，最后的 12 位是序列號。

上面這個結(jié)構(gòu)是雪花算法的基本結(jié)構(gòu)，不同公司根據(jù)自身的業(yè)務(wù)會進(jìn)行相應(yīng)的調(diào)整，有的可以采用 32 位或者其他位數(shù)，而且時間戳的位數(shù)也可以根據(jù)實際情況進(jìn)行調(diào)整，10 位的 workerID 有機房的公司可以用機房加機器組成，沒有機房的公司可以直接用機器來組成，序列位也可以根據(jù)情況適當(dāng)調(diào)整。

我們可以簡單算一下，41 位的時間位是2 ^ 41 / (365 * 24 * 3600 * 1000) = 69 年，每個機器每毫秒可以生成 2 ^ 12 = 4096 個 ID。

那是不是說我們這個代碼只能運行 69 年呢?其實不是的，這里服務(wù)在啟動的時候會設(shè)置一個初始值，這里的時間戳是用機器的時間減去初始值的差值。那 SnowFlake 算法有什么優(yōu)缺點呢?

1. 因為有時間戳，所以滿足自增的要求，同時也具備一定的可讀性;
2. 化整為零每個服務(wù)在各自的機器上可以直接生成唯一 ID，只需要配置好機房和機器編號即可;
3. 長度可以根據(jù)業(yè)務(wù)自行調(diào)整;
4. 缺點是依賴機器的時鐘，如果說機器的時鐘有問題，會導(dǎo)致生成的 ID 可能會重復(fù)，這個需要控制;

結(jié)合上面的原理，我們可以通過 Java 代碼來具體實現(xiàn)，代碼如下：

public class SnowFlakeUtil { 
 
    //初始時間戳 
    private final static long START_TIMESTAMP = 1624796691000L; 
    //數(shù)據(jù)中心占用的位數(shù) 
    private final static long DATA_CENTER_BIT = 5; 
    //機器標(biāo)識占用的位數(shù) 
    private final static long MACHINE_BIT = 5; 
    //序列號占用的位數(shù) 
    private final static long SEQUENCE_BIT = 12; 
 
 
    /** 
     * 每一部分的最大值 
     */ 
    private final static long MAX_SEQUENCE = ~(-1L << SEQUENCE_BIT); 
    private final static long MAX_MACHINE_NUM = ~(-1L << MACHINE_BIT); 
    private final static long MAX_DATA_CENTER_NUM = ~(-1L << DATA_CENTER_BIT); 
 
    /** 
     * 每一部分向左的位移 
     */ 
    private final static long MACHINE_LEFT = SEQUENCE_BIT; 
    private final static long DATA_CENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT; 
    private final static long TIMESTAMP_LEFT = DATA_CENTER_LEFT + DATA_CENTER_BIT; 
 
    private final long idc; 
    private final long serverId; 
    private long sequence = 0L; 
    private long lastTimeStamp = -1L; 
 
    private long getNextMill() { 
        long mill = System.currentTimeMillis(); 
        while (mill <= lastTimeStamp) { 
            mill = System.currentTimeMillis(); 
        } 
        return mill; 
    } 
 
    /** 
     * 根據(jù)指定的數(shù)據(jù)中心ID和機器標(biāo)志ID生成指定的序列號 
     * 
     * @param idc      數(shù)據(jù)中心ID 
     * @param serverId 機器標(biāo)志ID 
     */ 
    public SnowFlakeUtil(long idc, long serverId) { 
        if (idc > MAX_DATA_CENTER_NUM || idc < 0) { 
            throw new IllegalArgumentException("IDC 數(shù)據(jù)中心編號非法！"); 
        } 
        if (serverId > MAX_MACHINE_NUM || serverId < 0) { 
            throw new IllegalArgumentException("serverId 機器編號非法！"); 
        } 
        this.idc = idc; 
        this.serverId = serverId; 
    } 
 
    /** 
     * 生成下一個 ID 
     * 
     * @return 
     */ 
    public synchronized long genNextId() { 
        long currTimeStamp = System.currentTimeMillis(); 
        if (currTimeStamp < lastTimeStamp) { 
            throw new RuntimeException("Clock moved backwards.  Refusing to generate id"); 
        } 
        if (currTimeStamp == lastTimeStamp) { 
            //相同毫秒內(nèi)，序列號自增 
            sequence = (sequence + 1) & MAX_SEQUENCE; 
            //同一毫秒的序列數(shù)已經(jīng)達(dá)到最大 
            if (sequence == 0L) { 
                currTimeStamp = getNextMill(); 
            } 
        } else { 
            //不同毫秒內(nèi)，序列號置為0 
            sequence = 0L; 
        } 
        lastTimeStamp = currTimeStamp; 
        return (currTimeStamp - START_TIMESTAMP) << TIMESTAMP_LEFT | idc << DATA_CENTER_LEFT | serverId << MACHINE_LEFT | sequence; 
    } 
 
    public static void main(String[] args) { 
        SnowFlakeUtil snowFlake = new SnowFlakeUtil(4, 3); 
        for (int i = 0; i < 100; i++) { 
            System.out.println(snowFlake.genNextId()); 
        } 
    } 
} 

參考

知乎·一口氣說出9種分布式ID生成方式，面試官有點懵了 

Leaf——美團點評分布式ID生成系統(tǒng)