背景

在復(fù)雜分布式系統(tǒng)中，往往需要對(duì)大量的數(shù)據(jù)和消息進(jìn)行唯一標(biāo)識(shí)。如在支付流水號(hào)、訂單號(hào)等，隨者業(yè)務(wù)數(shù)據(jù)日漸增長(zhǎng)，對(duì)數(shù)據(jù)分庫分表后需要有一個(gè)唯一ID來標(biāo)識(shí)一條數(shù)據(jù)或消息，數(shù)據(jù)庫的自增ID顯然不能滿足需求，此時(shí)一個(gè)能夠生成全局唯一ID的系統(tǒng)是非常必要的。

生成的唯一id需要具備哪些條件

1. 全局唯一性：不能出現(xiàn)重復(fù)的ID號(hào)，既然是唯一標(biāo)識(shí)，這是最基本的要求。
2. 趨勢(shì)遞增：在MySQL InnoDB引擎中使用的是聚集索引，由于多數(shù)RDBMS使用B-tree的數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)索引數(shù)據(jù)，在主鍵的選擇上面我們應(yīng)該盡量使用有序的主鍵保證寫入性能。
3. 單調(diào)遞增：保證下一個(gè)ID一定大于上一個(gè)ID，例如事務(wù)版本號(hào)、IM增量消息、排序等特殊需求。
4. 信息安全：如果ID是連續(xù)的，惡意用戶的扒取工作就非常容易做了，直接按照順序下載指定URL即可；如果是訂單號(hào)就更危險(xiǎn)了，競(jìng)對(duì)可以直接知道我們一天的單量。所以在一些應(yīng)用場(chǎng)景下，會(huì)需要ID無規(guī)則、不規(guī)則。

UUID

關(guān)于分布式id,很多人會(huì)想到使用UUID，UUID在唯一性上確實(shí)可以達(dá)到這個(gè)目的，但它也存在很大的缺陷

優(yōu)點(diǎn)：

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

缺點(diǎn)：

• 不易于存儲(chǔ)：UUID太長(zhǎng)，16字節(jié)128位，通常以36長(zhǎng)度的字符串表示，很多場(chǎng)景不適用。
• 信息不安全：基于MAC地址生成UUID的算法可能會(huì)造成MAC地址泄露，這個(gè)漏洞曾被用于尋找梅麗莎病毒的制作者位置。
• ID作為主鍵時(shí)在特定的環(huán)境會(huì)存在一些問題，比如做DB主鍵的場(chǎng)景下，UUID就非常不適用。（MySQL官方有明確的建議主鍵要盡量越短越好，36個(gè)字符長(zhǎng)度的UUID不符合要求。對(duì)MySQL索引不利：如果作為數(shù)據(jù)庫主鍵，在InnoDB引擎下，UUID的無序性可能會(huì)引起數(shù)據(jù)位置頻繁變動(dòng)，嚴(yán)重影響性能。）

snowflake

"世界上沒有一片雪花是相同的"，這大概是snowflake名字的由來吧。

SnowFlake算法是Twitter設(shè)計(jì)的一個(gè)可以在分布式系統(tǒng)中生成唯一的ID的算法，它可以滿足Twitter每秒上萬條消息ID分配的請(qǐng)求，這些消息ID是唯一的且有大致的遞增順序。

snowflake算法的原理

SnowFlake算法產(chǎn)生的ID是一個(gè)64位的整型，結(jié)構(gòu)如下（每一部分用“-”符號(hào)分隔）：

snowflake.png

需要注意的是64位是二進(jìn)制，2的64次方 = 18446744073709551616，這就是能表示的id的范圍，范圍可以通過擴(kuò)展序列號(hào)或則工作機(jī)器id來增加id的上限。

1位標(biāo)識(shí)部分

在java中由于long的最高位是符號(hào)位，正數(shù)是0，負(fù)數(shù)是1，一般生成的ID為正數(shù)，所以為0；

41位時(shí)間戳部分

這個(gè)是毫秒級(jí)的時(shí)間，一般實(shí)現(xiàn)上不會(huì)存儲(chǔ)當(dāng)前的時(shí)間戳，而是時(shí)間戳的差值（當(dāng)前時(shí)間-固定的開始時(shí)間），這樣可以使產(chǎn)生的ID從更小值開始；41位的時(shí)間戳可以使用69年，(1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69年；

10位節(jié)點(diǎn)部分

Twitter實(shí)現(xiàn)中使用前5位作為數(shù)據(jù)中心標(biāo)識(shí)，后5位作為機(jī)器標(biāo)識(shí)，可以部署1024個(gè)節(jié)點(diǎn)，在Spring Cloud中可以為每一個(gè)實(shí)例生成唯一的機(jī)器識(shí)別碼，這樣就能保證每個(gè)實(shí)例中生成的id都不一樣。

12位序列號(hào)部分

支持同一毫秒內(nèi)同一個(gè)節(jié)點(diǎn)可以生成4096（2的12次方）個(gè)ID，這個(gè)同樣可以擴(kuò)展，但其實(shí)每毫秒生成4096個(gè)id已經(jīng)能滿足大部分場(chǎng)景了。

算法的java代碼

/**
 * twitter的snowflake算法 -- java實(shí)現(xiàn)
 * 
 * @author beyond
 * @date 2016/11/26
 */
public class SnowFlake {

    /**
     * 起始的時(shí)間戳（最后的時(shí)間 = 當(dāng)前時(shí)間戳 - 起始的時(shí)間戳)
     */
    private final static long START_STMP = 1480166465631L;

    /**
     * 每一部分占用的位數(shù)
     */
    private final static long SEQUENCE_BIT = 12; //序列號(hào)占用的位數(shù)
    private final static long MACHINE_BIT = 5;   //機(jī)器標(biāo)識(shí)占用的位數(shù)
    private final static long DATACENTER_BIT = 5;//數(shù)據(jù)中心占用的位數(shù)

    /**
     * 每一部分的最大值
     */
    private final static long MAX_DATACENTER_NUM = -1L ^ (-1L << DATACENTER_BIT);
    private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);
    private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT);

    /**
     * 每一部分向左的位移
     */
    private final static long MACHINE_LEFT = SEQUENCE_BIT;
    private final static long DATACENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
    private final static long TIMESTMP_LEFT = DATACENTER_LEFT + DATACENTER_BIT;

    private long datacenterId;  //數(shù)據(jù)中心
    private long machineId;     //機(jī)器標(biāo)識(shí)
    private long sequence = 0L; //序列號(hào)
    private long lastStmp = -1L;//上一次時(shí)間戳

    public SnowFlake(long datacenterId, long machineId) {
        // 校驗(yàn)datacenterId長(zhǎng)度超過范圍就拋異常
        if (datacenterId > MAX_DATACENTER_NUM || datacenterId < 0) {
            throw new IllegalArgumentException("datacenterId can't be greater than MAX_DATACENTER_NUM or less than 0");
        }
       // 校驗(yàn)machineId長(zhǎng)度超過范圍就拋異常
        if (machineId > MAX_MACHINE_NUM || machineId < 0) {
            throw new IllegalArgumentException("machineId can't be greater than MAX_MACHINE_NUM or less than 0");
        }
        this.datacenterId = datacenterId;
        this.machineId = machineId;
    }

    /**
     * 產(chǎn)生下一個(gè)ID
     *
     * @return
     */
    public synchronized long nextId() {
        long currStmp = getNewstmp();
        if (currStmp < lastStmp) {
            throw new RuntimeException("Clock moved backwards.  Refusing to generate id");
        }

        if (currStmp == lastStmp) {
            //相同毫秒內(nèi)，序列號(hào)自增
            sequence = (sequence + 1) & MAX_SEQUENCE;
            //同一毫秒的序列數(shù)已經(jīng)達(dá)到最大
            if (sequence == 0L) {
                currStmp = getNextMill();
            }
        } else {
            //不同毫秒內(nèi)，序列號(hào)置為0
            sequence = 0L;
        }

        lastStmp = currStmp;
        //使用二進(jìn)制的"|"運(yùn)算符將4部分的值整合成我們需要的id
        return (currStmp - START_STMP) << TIMESTMP_LEFT //時(shí)間戳部分
                | datacenterId << DATACENTER_LEFT       //數(shù)據(jù)中心部分
                | machineId << MACHINE_LEFT             //機(jī)器標(biāo)識(shí)部分
                | sequence;                             //序列號(hào)部分
    }
    
    //如果當(dāng)前毫秒值下的序列號(hào)用完，就循環(huán)獲取下個(gè)毫秒值，如果沒有獲取到下個(gè)毫秒值就
    //一直循環(huán)下去
    private long getNextMill() {
        long mill = getNewstmp();
        while (mill <= lastStmp) {
            mill = getNewstmp();
        }
        return mill;
    }

    private long getNewstmp() {
        return System.currentTimeMillis();
    }

    public static void main(String[] args) {
        SnowFlake snowFlake = new SnowFlake(2, 3);

        for (int i = 0; i < (1 << 12); i++) {
            System.out.println(snowFlake.nextId());
        }

    }
}

總結(jié)

10位節(jié)點(diǎn)部分在代碼中分成了兩個(gè)5位節(jié)點(diǎn)，看具體需求，也可以用一個(gè)10位節(jié)點(diǎn)代替。snowflake更多的是提供一種算法思想，具體的id生成邏輯可以在此基礎(chǔ)上進(jìn)一步的優(yōu)化。