分布式系統唯一id方案-SnowFlake

摘要：

SnowFlake算法生成的ID大緻上是按照時間遞增的，用在分布式系統中時，需要注意資料中心辨別和機器辨別必須唯一，這樣就能保證每個節點生成的ID都是唯一的。它可以滿足Twitter每秒上萬條消息ID配置設定的請求，這些消息ID是唯一的且有大緻的遞增順序，且是一個64位整形，即8位元組，可以展示為一個Long類型的整數。結構如下（每一部分用“-”符号分隔）：

0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000

64位整型：符号 + 時間戳 + 資料中心辨別 + 機器辨別 + 序列号

符号：1位 預設為0

時間戳：41位，不會存儲目前的時間戳，而是時間戳的內插補點（目前時間-固定的開始時間），這樣可以使産生的ID從更小值開始；41位的時間戳可以使用69年，(1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69年；

資料中心辨別：5位，用于不同的資料中心

機器辨別：5位， 機器号保證分布式系統

序列号:12位，機關毫秒内可生成的序列号數目的理論極限。

public class SnowFlake {
    // 起始的時間戳
    private final static long START_STMP = 1480166465631L;
    // 每一部分占用的位數，就三個
    private final static long SEQUENCE_BIT = 12;// 序列号占用的位數
    private final static long MACHINE_BIT = 5; // 機器辨別占用的位數
    private final static long DATACENTER_BIT = 5;// 資料中心占用的位數
    // 每一部分最大值
    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; // 資料中心
    private long machineId; // 機器辨別
    private long sequence = 0L; // 序列号
    private long lastStmp = -1L;// 上一次時間戳

    public SnowFlake(long datacenterId, long machineId) {
        if (datacenterId > MAX_DATACENTER_NUM || datacenterId < 0) {
            throw new IllegalArgumentException("datacenterId can't be greater than MAX_DATACENTER_NUM or less than 0");
        }
        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;
    }
    //産生下一個ID
    public synchronized long nextId() {
        long currStmp = getNewstmp();
        if (currStmp < lastStmp) {
            throw new RuntimeException("Clock moved backwards.  Refusing to generate id");
        }

        if (currStmp == lastStmp) {
            //if條件裡表示目前調用和上一次調用落在了相同毫秒内，隻能通過第三部分，序列号自增來判斷為唯一，是以+1.
            sequence = (sequence + 1) & MAX_SEQUENCE;
            //同一毫秒的序列數已經達到最大，隻能等待下一個毫秒
            if (sequence == 0L) {
                currStmp = getNextMill();
            }
        } else {
            //不同毫秒内，序列号置為0
            //執行到這個分支的前提是currTimestamp > lastTimestamp，說明本次調用跟上次調用對比，已經不再同一個毫秒内了，這個時候序号可以重新回置0了。
            sequence = 0L;
        }

        lastStmp = currStmp;
         //就是用相對毫秒數、機器ID和自增序号拼接
        return (currStmp - START_STMP) << TIMESTMP_LEFT //時間戳部分
                | datacenterId << DATACENTER_LEFT      //資料中心部分
                | machineId << MACHINE_LEFT            //機器辨別部分
                | sequence;                            //序列号部分
    }

    private long getNextMill() {
        long mill = getNewstmp();
        while (mill <= lastStmp) {
            mill = getNewstmp();
        }
        return mill;
    }

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


}
           

測試類：

public class Test {

    public static void main(String[] args) {
        // 構造方法設定機器碼：第9個機房的第20台機器
        SnowFlake  snowFlake = new SnowFlake(9, 20);
        for(int i =0; i <(1<< 12); i++){
            System.out.println(snowFlake.nextId());
        }
    }

}
           

nextId的synchronized方法+遞增的序列号：保證單機器内線程安全.

69年的問題怎麼解決？

timestamp減個常量就可以了，對于已生成的曆史id，可以導表刷id，當然，這裡涉及到個資料庫設計原則，系統之間傳遞資料不應使用實體主鍵，這樣刷id 就容易了。

資料中心辨別和機器辨別怎麼擷取？

可以存到庫裡 如mac位址 + ipv4位址 确定唯一機器，插入資料庫，機器号通過庫的自增主鍵自增産生

是以啟動的時候直接查詢，如果有了直接擷取到機器id

否則插入後擷取