分布式ID方案SnowFlake雪花算法分析

image

1、算法

SnowFlake算法生成的數(shù)據(jù)組成結(jié)構(gòu)如下：

snowflake.png

在java中用long類型標(biāo)識，共64位（每部分用-分開）：
0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 0000000000 00

  • 1位標(biāo)識，0表示正數(shù)。
  • 41位時間戳，當(dāng)前時間的毫秒減去開始時間的毫秒數(shù)?？捎?(1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69年。
  • 5位數(shù)據(jù)中心標(biāo)識，可支持(1L << 5) = 32個數(shù)據(jù)中心。
  • 5位機器標(biāo)識，每個數(shù)據(jù)中心可支持(1L << 5) = 32個機器標(biāo)識。
  • 12位序列號，每個節(jié)點每一毫秒支持(1L << 12) = 4096個序列號。

2、Java版本實現(xiàn)


/**
 * 雪花算法<br>
 * 在java中用long類型標(biāo)識，共64位（每部分用-分開）：<br>
 * 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 0000000000 00<br>
 * 1位標(biāo)識，0表示正數(shù)。<br>
 * 41位時間戳，當(dāng)前時間的毫秒減去開始時間的毫秒數(shù)?？捎?(1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69年。<br>
 * 5位數(shù)據(jù)中心標(biāo)識，可支持(1L << 5) = 32個數(shù)據(jù)中心。<br>
 * 5位機器標(biāo)識，每個數(shù)據(jù)中心可支持(1L << 5) = 32個機器標(biāo)識。<br>
 * 12位序列號，每個節(jié)點每一毫秒支持(1L << 12) = 4096個序列號。<br>
 */
public class SnowflakeIdWorker {
    /**
     * 機器標(biāo)識
     */
    private long workerId;
    /**
     * 數(shù)據(jù)中心標(biāo)識
     */
    private long dataCenterId;
    /**
     * 序列號
     */
    private long sequence;
    /**
     * 機器標(biāo)識占用5位
     */
    private long workerIdBits = 5L;
    /**
     * 數(shù)據(jù)中心標(biāo)識占用5位
     */
    private long dataCenterIdBits = 5L;
    /**
     * 12位序列號
     */
    private long sequenceBits = 12L;

    /**
     * 12位序列號支持的最大正整數(shù)
     * ....... 00001111 11111111
     * 2^12-1 = 4095
     */
    private long sequenceMask = ~(-1L << sequenceBits);

    /**
     * The Worker id shift.
     * 12位
     */
    private long workerIdShift = sequenceBits;
    /**
     * The Data center id shift.
     * 12 + 5 = 17位
     */
    private long dataCenterIdShift = sequenceBits + workerIdBits;
    /**
     * The Timestamp shift.
     * 12 + 5 + 5 = 22位
     */
    private long timestampShift = sequenceBits + workerIdBits + dataCenterIdBits;
    /**
     * 開始時間戳毫秒
     */
    private long startEpoch = 29055616000L;
    /**
     * The Last timestamp.
     */
    private long lastTimestamp = -1L;

    public SnowflakeIdWorker(long workerId, long dataCenterId, long sequence) {
        // 檢查workerId是否正常
        /*
          機器標(biāo)識最多支持的最大正整數(shù)
          -1的補碼：
          11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111
          -1 左移 5 位，高位溢出，低位補0：
          11111111 11111111 11111111 11111111 11111111 11111111 11111111 11100000
          取反：
          00000000 00000000 00000000 00000000 00000000 00000000 00000000 00011111
          轉(zhuǎn)10進制：
          16 + 8 + 4 + 2 + 1 = 31
         */
        long maxWorkerId = ~(-1L << workerIdBits);
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format("工作Id不能大于%d或小于0", maxWorkerId));
        }

        /*
          數(shù)據(jù)中心最多支持的最大正整數(shù)31
         */
        long maxDataCenterId = ~(-1L << dataCenterIdBits);
        if (dataCenterId > maxDataCenterId || dataCenterId < 0) {
            throw new IllegalArgumentException(String.format("數(shù)據(jù)中心Id不能大于%d或小于0", maxDataCenterId));
        }

        this.workerId = workerId;
        this.dataCenterId = dataCenterId;
        this.sequence = sequence;
    }

    private synchronized long nextId() {
        //獲取當(dāng)前時間毫秒數(shù)
        long timestamp = timeGen();

        //如果當(dāng)前時間毫秒數(shù)小于上一次的時間戳
        if (timestamp < lastTimestamp) {
            System.err.printf("時鐘發(fā)生回調(diào)，拒絕生成ID,直到： %d.", lastTimestamp);
            throw new RuntimeException(String.format("時鐘發(fā)生回調(diào)，  拒絕為 %d 毫秒生成ID。",
                    lastTimestamp - timestamp));
        }

        //當(dāng)前時間毫秒數(shù)與上次時間戳相同，增加序列號
        if (lastTimestamp == timestamp) {
            //假設(shè)sequence=4095
            //(4095 + 1) & 4095
            //4096:  ....... 00010000 00000000
            //4095:  ....... 00001111 11111111
            //       ....... 00000000 00000000
            //最終sequence為0，即sequence發(fā)生溢出。
            sequence = (sequence + 1) & sequenceMask;
            //如果發(fā)生序列號為0，即當(dāng)前毫秒數(shù)的序列號已經(jīng)溢出，則借用下一毫秒的時間戳
            if (sequence == 0) {
                timestamp = tilNextMillis(lastTimestamp);
            }
        } else {
            //當(dāng)前毫秒數(shù)大于上次的時間戳，序列號為0
            sequence = 0;
        }

        //更新
        lastTimestamp = timestamp;

        //生成ID算法，左移幾位，則后面加幾個0。
        //1、當(dāng)前時間的毫秒數(shù)-開始時間的毫秒數(shù)，結(jié)果左移22位
        // 假設(shè)：timestamp - startEpoch = 1
        // 二進制:
        // 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001
        // 左移22位:
        // 00000000 00000000 00000000 00000000 00000000 01000000 00000000 00000000
        //2、dataCenterId左移17位
        // 假設(shè)：dataCenterId = 1
        // 二進制:
        // 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001
        // 左移17位:
        // 00000000 00000000 00000000 00000000 00000000 00000010 00000000 00000000

        //3、workerId左移12位
        // 假設(shè)：workerId = 1
        // 二進制:
        // 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001
        // 左移12位:
        // 00000000 00000000 00000000 00000000 00000000 00000000 00010000 00000000
        //4、最后的所有結(jié)果按位`或`
        //假設(shè)：sequence = 1
        //00000000 00000000 00000000 00000000 00000000 01000000 00000000 00000000
        //00000000 00000000 00000000 00000000 00000000 00000010 00000000 00000000
        //00000000 00000000 00000000 00000000 00000000 00000000 00010000 00000000
        //00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001
        //00000000 00000000 00000000 00000000 00000000 01000010 00010000 00000001
        //結(jié)果： 0 - 0000000 00000000 00000000 00000000 00000000 01 - 00001 - 00001 - 0000 00000001

        return ((timestamp - startEpoch) << timestampShift) |
                (dataCenterId << dataCenterIdShift) |
                (workerId << workerIdShift) |
                sequence;
    }

    /**
     * 獲取下一秒
     *
     * @param lastTimestamp the last timestamp
     * @return the long
     */
    private long tilNextMillis(long lastTimestamp) {
        //獲取當(dāng)前毫秒數(shù)
        long timestamp = timeGen();
        //只要當(dāng)前的毫秒數(shù)小于上次的時間戳，就一直循環(huán)，大于上次時間戳
        while (timestamp <= lastTimestamp) {
            //獲取當(dāng)前毫秒數(shù)
            timestamp = timeGen();
        }
        return timestamp;
    }

    /**
     * 獲取當(dāng)前毫秒數(shù)
     *
     * @return the long
     */
    private long timeGen() {
        return System.currentTimeMillis();
    }


    public static void main(String[] args) {
        SnowflakeIdWorker worker = new SnowflakeIdWorker(1, 1, 1);
        for (int i = 0; i < 10000; i++) {
            long id = worker.nextId();
            System.out.println(id);
            System.out.println(Long.toString(id).length());
            System.out.println(Long.toBinaryString(id));
            System.out.println(Long.toBinaryString(id).length());
        }
    }

}

3、難點

Tips: 左移幾位，則后面加幾個0。

3.1、計算機器標(biāo)識最多支持的最大正整數(shù)

private long workerIdBits = 5L;
long maxWorkerId = ~(-1L << workerIdBits);

計算過程：

  • -1的補碼：

    11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111
  • -1 左移 5 位，高位溢出，低位補0：

    11111111 11111111 11111111 11111111 11111111 11111111 11111111 11100000
  • 取反：

    00000000 00000000 00000000 00000000 00000000 00000000 00000000 00011111
  • 轉(zhuǎn)10進制：

    16 + 8 + 4 + 2 + 1 = 31

3.2、sequence溢出處理

sequence = (sequence + 1) & sequenceMask;

計算過程:

假設(shè)sequence=4095：

  • (4095 + 1) & 4095
  • 4096: ....... 00010000 00000000
  • 4095: ....... 00001111 11111111
  • 按位與 ....... 00000000 00000000
  • 最終sequence為0，即sequence發(fā)生溢出。

3.3、ID計算

((timestamp - startEpoch) << timestampShift) |
(dataCenterId << dataCenterIdShift) |
(workerId << workerIdShift) |
sequence

計算過程：

  • 當(dāng)前時間的毫秒數(shù)-開始時間的毫秒數(shù)，結(jié)果左移22位

假設(shè)：timestamp - startEpoch = 1

二進制: 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001

左移22位: 00000000 00000000 00000000 00000000 00000000 01000000 00000000 00000000

  • dataCenterId左移17位

假設(shè)：dataCenterId = 1

二進制: 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001

左移17位: 00000000 00000000 00000000 00000000 00000000 00000010 00000000 00000000

  • workerId左移12位

假設(shè)：workerId = 1

二進制: 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001

左移12位: 00000000 00000000 00000000 00000000 00000000 00000000 00010000 00000000

  • 最后的所有結(jié)果按位或

假設(shè)：sequence = 1

00000000 00000000 00000000 00000000 00000000 01000000 00000000 00000000

00000000 00000000 00000000 00000000 00000000 00000010 00000000 00000000

00000000 00000000 00000000 00000000 00000000 00000000 00010000 00000000

00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001

00000000 00000000 00000000 00000000 00000000 01000010 00010000 00000001

  • 結(jié)果：

0 - 0000000 00000000 00000000 00000000 00000000 01 - 00001 - 00001 - 0000 00000001

符合SnowFlake算法數(shù)據(jù)組成結(jié)構(gòu)。

參考

理解分布式id生成算法SnowFlake
Twitter雪花算法SnowFlake算法的java實現(xiàn)

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

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容