雪花算法（snowflake）實作原理圖解

snowflake是twitter的分布式環境生成全局唯一id的解決方案

snowflake id組成分析

snowflake-64bit

分别有三部分（其中第一位保留位，暫時沒用）：

1. 第一部分：時間戳（毫秒級），這裡為41bit
2. 第二部分：工作機器id，一般為==5bit資料中心id（datacenterId）+5bit機器id（workerId）==組成，10位的長度最多支援部署1024個節點
3. 第三部分：在相同毫秒内，可以産生2^12 個id，12位的計數順序号支援每個節點每毫秒産生4096個ID序列

snowflake-32bit

大緻與64bit相同，唯一差別是時間戳部分這裡僅占用32bit，因為儲存的時間戳為：currStamp - START_STAMP，得出來的資料僅用10bit就可以儲存，位數越少，對磁盤、資料索引等資料提高越明顯

優點

1. 按照時間自增排序，在多個分布式系統内不會産生id碰撞（資料中心+機器id區分）
2. 高性能：理論上QPS約為409.6w/s（1000*2^12）
3. 不依賴于任何外部第三方系統
4. 靈活性高：可以根據自身業務情況調整配置設定bit位

缺點

1. 強依賴時鐘：生成都是以時間自增，如果時間回撥，可能導緻id重複

美團對此缺點做了一些改進，具體可以參考：Leaf——美團點評分布式ID生成系統

源碼解析

/**
 * twitter的snowflake算法 -- java實作
 *
 * @author beyond
 * @date 2016/11/26
 */
public class SnowFlake {

    /**
     * 起始的時間戳 2016-11-26 21:21:05
     */
    private final static long START_STAMP = 1480166465631L;

    /**
     * 每一部分占用的位數
     */
    private final static long SEQUENCE_BIT = 12; //序列号占用的位數
    private final static long MACHINE_BIT = 5;   //機器辨別占用的位數
    private final static long DATA_CENTER_BIT = 5;//資料中心占用的位數

    /**
     * 每一部分的最大值
     */
    private final static long MAX_DATA_CENTER_NUM = -1L ^ (-1L << DATA_CENTER_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 DATA_CENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
    private final static long TIMESTAMP_LEFT = DATA_CENTER_LEFT + DATA_CENTER_BIT;

    private long dataCenterId;  //資料中心
    private long machineId;     //機器辨別
    private long sequence = 0L; //序列号
    private long lastStamp = -1L;//上一次時間戳

    public SnowFlake(long dataCenterId, long machineId) {
        if (dataCenterId > MAX_DATA_CENTER_NUM || dataCenterId < 0) {
            throw new IllegalArgumentException("dataCenterId can't be greater than MAX_DATA_CENTER_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
     *
     * @return
     */
    public synchronized long nextId() {
        // 獲得目前時間的毫秒數
        long currStamp = getNewStamp();
        if (currStamp < lastStamp) {
            throw new RuntimeException("Clock moved backwards.  Refusing to generate id");
        }

        if (currStamp == lastStamp) {
            // 相同毫秒内，序列号自增
            sequence = (sequence + 1) & MAX_SEQUENCE; // 為了保證取值範圍最大為MAX_SEQUENCE
            // 同一毫秒的序列數已經達到最大
            if (sequence == 0L) { // 即：已經超出MAX_SEQUENCE 即：1000000000000
                currStamp = getNextMill();
            }
        } else {
            //不同毫秒内，序列号置為0
            sequence = 0L;
        }

        lastStamp = currStamp;

        return (currStamp - START_STAMP) << TIMESTAMP_LEFT // 時間戳部分
                | dataCenterId << DATA_CENTER_LEFT       // 資料中心部分
                | machineId << MACHINE_LEFT             // 機器辨別部分
                | sequence;                             // 序列号部分
    }

    /**
     * 獲得下一個毫秒數，比lastStamp大的下一個毫秒數
     *
     * @return
     */
    private long getNextMill() {
        long mill = getNewStamp();
        while (mill <= lastStamp) {
            mill = getNewStamp();
        }
        return mill;
    }

    /**
     * 獲得目前毫秒數
     *
     * @return
     */
    private long getNewStamp() {
        return System.currentTimeMillis();
    }


    public static void main(String[] args) {
        SnowFlake snowFlake = new SnowFlake(3L, 10L);
        System.out.println("snowFlake.nextId() = " + snowFlake.nextId());
    }
}
           

其中有對三個部分都限制了最大值（MAX_DATA_CENTER_NUM、MAX_MACHINE_NUM、MAX_SEQUENCE），我們通過圖解的方式來看下計算過程：

總結

其它還有利用資料庫來生成分布式全局唯一ID方案，不過性能與穩定性都不如snowflake，針對snowflake比較成熟的解決方案可以參考

Leaf——美團點評分布式ID生成系統，此方案綜合考慮到了高可用、容災、分布式下時鐘等問題。

參考

• https://blog.csdn.net/fly910905/article/details/82054196
• https://github.com/beyondfengyu/SnowFlake/blob/master/SnowFlake.java
• Leaf——美團點評分布式ID生成系統