[[408786]]

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

前言

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

要求

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

全局遞增：遞增這個(gè)也很好理解，我們要保證生成的 ID 是依次遞增的，因?yàn)楹芏鄷r(shí)候 ID 是給人看的，如果說不具備遞增性，就缺乏了很多的可讀性;

信息安全：分布式 ID 的安全性也很重要，因?yàn)槲覀兲岬缴傻?ID 是遞增的，這就有可能會(huì)給競爭對(duì)手知道我們的 ID 的生成頻率，這種在電商等場(chǎng)景會(huì)有很大的問題，但是這個(gè)往往跟全局遞增有點(diǎn)沖突;

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

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

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

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

UUID

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

Redis

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

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

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

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

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

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

推特的雪花算法—— snowflake

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

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

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

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

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

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

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

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

public class SnowFlakeUtil { 
 
    //初始時(shí)間戳 
    private final static long START_TIMESTAMP = 1624796691000L; 
    //數(shù)據(jù)中心占用的位數(shù) 
    private final static long DATA_CENTER_BIT = 5; 
    //機(jī)器標(biāo)識(shí)占用的位數(shù) 
    private final static long MACHINE_BIT = 5; 
    //序列號(hào)占用的位數(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和機(jī)器標(biāo)志ID生成指定的序列號(hào) 
     * 
     * @param idc      數(shù)據(jù)中心ID 
     * @param serverId 機(jī)器標(biāo)志ID 
     */ 
    public SnowFlakeUtil(long idc, long serverId) { 
        if (idc > MAX_DATA_CENTER_NUM || idc < 0) { 
            throw new IllegalArgumentException("IDC 數(shù)據(jù)中心編號(hào)非法！"); 
        } 
        if (serverId > MAX_MACHINE_NUM || serverId < 0) { 
            throw new IllegalArgumentException("serverId 機(jī)器編號(hào)非法！"); 
        } 
        this.idc = idc; 
        this.serverId = serverId; 
    } 
 
    /** 
     * 生成下一個(gè) 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)，序列號(hào)自增 
            sequence = (sequence + 1) & MAX_SEQUENCE; 
            //同一毫秒的序列數(shù)已經(jīng)達(dá)到最大 
            if (sequence == 0L) { 
                currTimeStamp = getNextMill(); 
            } 
        } else { 
            //不同毫秒內(nèi)，序列號(hào)置為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生成方式，面試官有點(diǎn)懵了 

Leaf——美團(tuán)點(diǎn)評(píng)分布式ID生成系統(tǒng)