前言

據(jù)國家大氣研究中心的查爾斯·奈特稱朴肺，一般的雪花大約由10^19個水分子組成。在雪花形成過程中坚洽，會形成不同的結構分支戈稿，所以說大自然中不存在兩片完全一樣的雪花，每一片雪花都擁有自己漂亮獨特的形狀讶舰。雪花算法表示生成的id如雪花般獨一無二鞍盗。

snowflake是Twitter開源的分布式ID生成算法，結果是一個long型的ID跳昼。其核心思想是：使用41bit作為毫秒數(shù)般甲，10bit作為機器的ID（5個bit是數(shù)據(jù)中心，5個bit的機器ID）鹅颊，12bit作為毫秒內的流水號（意味著每個節(jié)點在每毫秒可以產(chǎn)生 4096 個 ID）敷存，最后還有一個符號位，永遠是0堪伍。

核心思想：分布式锚烦，唯一。

一帝雇、雪花算法的基本概念

雪花算法是一種全局ID生成算法涮俄，其核心思想是將64位的long型ID分為四個部分，分別為：時間戳尸闸、工作機器ID彻亲、數(shù)據(jù)中心ID和序列號。通過將數(shù)據(jù)映射到具有特定結構的分布式系統(tǒng)中吮廉，實現(xiàn)數(shù)據(jù)的存儲和查詢睹栖。該算法由一系列節(jié)點組成，每個節(jié)點負責存儲數(shù)據(jù)的一部分茧痕。這些節(jié)點通過哈希函數(shù)將數(shù)據(jù)映射到特定的位置野来，形成類似于雪花結構的分布式系統(tǒng)。通過這種方式踪旷，雪花算法能夠在分布式系統(tǒng)中保證ID的唯一性和有序性曼氛。

雪花算法具有以下優(yōu)點：

• 易于擴展：可以方便地添加或刪除節(jié)點豁辉，適應數(shù)據(jù)量的變化。
• 容錯性高：即使部分節(jié)點發(fā)生故障舀患，整個系統(tǒng)仍可正常運行徽级。
• 負載均衡：數(shù)據(jù)在節(jié)點間分布均勻，有效利用系統(tǒng)資源聊浅。
• 適用于各種數(shù)據(jù)訪問模式：支持隨機訪問和順序訪問等訪問模式餐抢。

二、雪花算法的原理

雪花算法是 64 位 的二進制低匙，一共包含了四部分：
1bit-符號位

• 1位標識：最高位是符號位旷痕，正數(shù)是0，負數(shù)是1顽冶。由于 id 一般是正數(shù)欺抗，所以第一位都是0。

41bit-時間戳

• 接下來41位存儲毫秒級時間戳强重，41位可以表示 2^41-1 毫秒绞呈。
• 轉化成年則是：(2^41-1)/(1000606024356)=69 年。這個時間戳大概可以使用 69年 不重復间景。

10bit-機器位

• 10位的數(shù)據(jù)機器位佃声，包括 5 位 datacenterId 和 5 位 workerId，最多可以部署 2^10=1024 臺機器倘要。
• 這里的 5 位可以表示的最大整數(shù)時 2^5-1=31圾亏，即可以用 0、1碗誉、2、3父晶、…31 這 32 個數(shù)字哮缺，來表示不同的 datacenterId 或 workerId

12bit-序列號

• 用來記錄同毫秒內產(chǎn)生的不同ID，12位的計數(shù)順序支持每個節(jié)點每毫秒（同一機器甲喝，同一時間戳）產(chǎn)生 4096 個ID序號尝苇。

三、源碼

import lombok.extern.slf4j.Slf4j;
import org.apache.commons.lang3.RandomUtils;
import org.apache.commons.lang3.StringUtils;
import org.apache.commons.lang3.SystemUtils;
 
import java.net.Inet4Address;
import java.net.UnknownHostException;
@Slf4j
public class SnowflakeIdWorker {
    /**
     * 開始時間截 (2015-01-01)
     */
    private final long twepoch = 1489111610226L;
    /**
     * 機器id所占的位數(shù)
     */
    private final long workerIdBits = 5L;
    /**
     * 數(shù)據(jù)標識id所占的位數(shù)
     */
    private final long dataCenterIdBits = 5L;
    /**
     * 支持的最大機器id埠胖，結果是31 (這個移位算法可以很快的計算出幾位二進制數(shù)所能表示的最大十進制數(shù))
     */
    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
    /**
     * 支持的最大數(shù)據(jù)標識id糠溜，結果是31
     */
    private final long maxDataCenterId = -1L ^ (-1L << dataCenterIdBits);
    /**
     * 序列在id中占的位數(shù)
     */
    private final long sequenceBits = 12L;
    /**
     * 機器ID向左移12位
     */
    private final long workerIdShift = sequenceBits;
    /**
     * 數(shù)據(jù)標識id向左移17位(12+5)
     */
    private final long dataCenterIdShift = sequenceBits + workerIdBits;
    /**
     * 時間截向左移22位(5+5+12)
     */
    private final long timestampLeftShift = sequenceBits + workerIdBits + dataCenterIdBits;
    /**
     * 生成序列的掩碼，這里為4095 (0b111111111111=0xfff=4095)
     */
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);
    /**
     * 工作機器ID(0~31)
     */
    private long workerId;
    /**
     * 數(shù)據(jù)中心ID(0~31)
     */
    private long dataCenterId;
    /**
     * 毫秒內序列(0~4095)
     */
    private long sequence = 0L;
    /**
     * 上次生成ID的時間截
     */
    private long lastTimestamp = -1L;
 
    private static SnowflakeIdWorker idWorker;
 
    static {
        idWorker = new SnowflakeIdWorker(getWorkId(), getDataCenterId());
    }
 
    //==============================Constructors=====================================
 
    /**
     * 構造函數(shù)
     *
     * @param workerId     工作ID (0~31)
     * @param dataCenterId 數(shù)據(jù)中心ID (0~31)
     */
    public SnowflakeIdWorker(long workerId, long dataCenterId) {
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format("workerId can't be greater than %d or less than 0", maxWorkerId));
        }
        if (dataCenterId > maxDataCenterId || dataCenterId < 0) {
            throw new IllegalArgumentException(String.format("dataCenterId can't be greater than %d or less than 0", maxDataCenterId));
        }
        this.workerId = workerId;
        this.dataCenterId = dataCenterId;
    }
 
    // ==============================Methods==========================================
 
    /**
     * 獲得下一個ID (該方法是線程安全的)
     *
     * @return SnowflakeId
     */
    public synchronized long nextId() {
        long timestamp = timeGen();
        //如果當前時間小于上一次ID生成的時間戳直撤，說明系統(tǒng)時鐘回退過這個時候應當拋出異常
        if (timestamp < lastTimestamp) {
            throw new RuntimeException(
                    String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
        }
        //如果是同一時間生成的非竿，則進行毫秒內序列
        if (lastTimestamp == timestamp) {
            sequence = (sequence + 1) & sequenceMask;
            //毫秒內序列溢出
            if (sequence == 0) {
                //阻塞到下一個毫秒,獲得新的時間戳
                timestamp = tilNextMillis(lastTimestamp);
            }
        }
        //時間戳改變，毫秒內序列重置
        else {
            sequence = 0L;
        }
        //上次生成ID的時間截
        lastTimestamp = timestamp;
 
        //移位并通過或運算拼到一起組成64位的ID
        return ((timestamp - twepoch) << timestampLeftShift)
                | (dataCenterId << dataCenterIdShift)
                | (workerId << workerIdShift)
                | sequence;
    }
 
    /**
     * 阻塞到下一個毫秒谋竖，直到獲得新的時間戳
     *
     * @param lastTimestamp 上次生成ID的時間截
     * @return 當前時間戳
     */
    protected long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }
 
    /**
     * 返回以毫秒為單位的當前時間
     *
     * @return 當前時間(毫秒)
     */
    protected long timeGen() {
        return System.currentTimeMillis();
    }
 
    private static Long getWorkId() {
        try {
            String hostAddress = Inet4Address.getLocalHost().getHostAddress();
            int[] ints = StringUtils.toCodePoints(hostAddress);
            int sums = 0;
            for (int b : ints) {
                sums += b;
            }
            return (long) (sums % 32);
        } catch (UnknownHostException e) {
            // 如果獲取失敗红柱，則使用隨機數(shù)備用
            return RandomUtils.nextLong(0, 31);
        }
    }
 
    private static Long getDataCenterId() {
        int[] ints = StringUtils.toCodePoints(SystemUtils.getHostName());
        int sums = 0;
        for (int i : ints) {
            sums += i;
        }
        return (long) (sums % 32);
    }
 
    /**
     * 靜態(tài)工具類
     *
     * @return id
     */
    public static synchronized Long generateId() {
        return idWorker.nextId();
    }
 
}

3.1 注意事項

• 1承匣、雪花算法（SnowflakeAlgorithm）在系統(tǒng)運行時只需要調用一次，然后通過SnowflakeIdInit.snowflakeId.nextId()自增來生成唯一的ID锤悄。
• 2韧骗、雪花算法是一種分布式唯一ID生成器，它基于Twitter的雪花算法（SnowflakeAlgorithm）實現(xiàn)零聚。該算法通過生成一個64位的ID來確保在分 布式系統(tǒng)中生成唯一的ID袍暴。
• 3、在雪花算法中隶症，ID被劃分為多個部分政模，包括時間戳、機器標識和序列號等沿腰。首次調用時览徒，會根據(jù)當前時間戳、機器標識和序列號生成一個唯一的ID颂龙。之后习蓬，每次調用nextId()方法時，會根據(jù)上次生成的ID計算出下一個ID措嵌。
• 4躲叼、具體來說，SnowflakeIdInit.snowflakeId.nextId()方法會根據(jù)上次生成的ID企巢，增加一定的值（通常是1）枫慷，然后生成一個新的ID。這個新的ID會比上次生成的ID更大浪规，因為時間戳部分會隨著時間的推移而增加或听。
• 5、雪花算法生成的ID是單調遞增的笋婿，并且具有較好的分布性和擴展性誉裆。但是，由于機器標識和序列號的長度有限缸濒，所以在某些情況下可能會出現(xiàn)ID沖突的情況足丢。為了解決這個問題，可以引入沖突檢測機制或者使用其他更高級的分布式唯一ID生成器庇配。

3.2 遇到的問題：數(shù)據(jù)傾斜

使用的過程中斩跌，我發(fā)現(xiàn)產(chǎn)生的分布式id始終是偶數(shù)，這樣會產(chǎn)生嚴重的數(shù)據(jù)傾斜捞慌。

分布式的組成是時間戳+機器id+序列號耀鸦，跟蹤源碼發(fā)現(xiàn)如果時間戳不一樣，每次序列號都是0啸澡，所以64位二進制最后12位一直都是000000000000揭糕，而決定奇偶的關鍵在于最后一個0萝快。為0就是偶數(shù)，為1就是奇數(shù)著角。

3.2.1 數(shù)據(jù)傾斜問題解決

• 方案一揪漩、不是同一毫秒，取一個0或者1的隨機數(shù)
  

  image.png

• 方案二吏口、不同毫秒內自增
  

四奄容、防止時鐘回撥

因為機器的原因會發(fā)生時間回撥，我們的雪花算法是強依賴我們的時間的产徊，如果時間發(fā)生回撥昂勒，有可能會生成重復的ID，在我們上面的nextId中我們用當前時間和上一次的時間進行判斷舟铜，如果當前時間小于上一次的時間那么肯定是發(fā)生了回撥戈盈，普通的算法會直接拋出異常,這里我們可以對其進行優(yōu)化,一般分為兩個情況：

• 如果時間回撥時間較短，比如配置5ms以內谆刨，那么可以直接等待一定的時間塘娶，讓機器的時間追上來。
• 如果時間的回撥時間較長痊夭，我們不能接受這么長的阻塞等待刁岸，那么又有兩個策略:
  • 1、直接拒絕她我，拋出異常虹曙，打日志，通知RD時鐘回滾番舆。
  • 2酝碳、利用擴展位，上面我們討論過不同業(yè)務場景位數(shù)可能用不到那么多恨狈，那么我們可以把擴展位數(shù)利用起來了疏哗，比如當這個時間回撥比較長的時候，我們可以不需要等待拴事，直接在擴展位加1沃斤。2位的擴展位允許我們有3次大的時鐘回撥圣蝎，一般來說就夠了刃宵，如果其超過三次我們還是選擇拋出異常，打日志徘公。

通過上面的幾種策略可以比較的防護我們的時鐘回撥牲证，防止出現(xiàn)回撥之后大量的異常出現(xiàn)。下面是修改之后的代碼关面，這里修改了時鐘回撥的邏輯：

import org.apache.commons.lang3.RandomUtils;
import org.apache.commons.lang3.StringUtils;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
 
import java.lang.management.ManagementFactory;
import java.net.InetAddress;
import java.net.NetworkInterface;
import java.net.UnknownHostException;
import java.text.SimpleDateFormat;
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.LockSupport;
 
 
/**
 * 分布式全局ID雪花算法解決方案
 *
 * 防止時鐘回撥
 * 因為機器的原因會發(fā)生時間回撥坦袍，我們的雪花算法是強依賴我們的時間的十厢，如果時間發(fā)生回撥，
 * 有可能會生成重復的ID捂齐，在我們上面的nextId中我們用當前時間和上一次的時間進行判斷蛮放，
 * 如果當前時間小于上一次的時間那么肯定是發(fā)生了回撥，
 * 普通的算法會直接拋出異常,這里我們可以對其進行優(yōu)化,一般分為兩個情況:
 * 如果時間回撥時間較短奠宜，比如配置5ms以內包颁，那么可以直接等待一定的時間，讓機器的時間追上來压真。
 * 如果時間的回撥時間較長娩嚼，我們不能接受這么長的阻塞等待，那么又有兩個策略:
 * 直接拒絕滴肿，拋出異常岳悟，打日志，通知RD時鐘回滾泼差。
 * 利用擴展位贵少，上面我們討論過不同業(yè)務場景位數(shù)可能用不到那么多，那么我們可以把擴展位數(shù)利用起來了拴驮，
 * 比如當這個時間回撥比較長的時候春瞬，我們可以不需要等待，直接在擴展位加1套啤。
 * 2位的擴展位允許我們有3次大的時鐘回撥宽气，一般來說就夠了，如果其超過三次我們還是選擇拋出異常潜沦，打日志萄涯。
 * 通過上面的幾種策略可以比較的防護我們的時鐘回撥，防止出現(xiàn)回撥之后大量的異常出現(xiàn)唆鸡。下面是修改之后的代碼涝影，這里修改了時鐘回撥的邏輯:
 */
public class SnowflakeIdFactory {
 
    private static final Logger log = LoggerFactory.getLogger(SnowflakeIdFactory.class);
 
    /**
     * EPOCH是服務器第一次上線時間點, 設置后不允許修改
     * 2018/9/29日，從此時開始計算争占，可以用到2089年
     */
    private static long EPOCH = 1538211907857L;
 
    /**
     * 每臺workerId服務器有3個備份workerId, 備份workerId數(shù)量越多, 可靠性越高, 但是可部署的sequence ID服務越少
     */
    private static final long BACKUP_COUNT = 3;
 
    /**
     * worker id 的bit數(shù)燃逻，最多支持8192個節(jié)點
     */
    private static final long workerIdBits = 5L;
    /**
     * 數(shù)據(jù)中心標識位數(shù)
     */
    private static final long dataCenterIdBits = 5L;
    /**
     * 序列號哥童，支持單節(jié)點最高每毫秒的最大ID數(shù)4096
     * 毫秒內自增位
     */
    private static final long sequenceBits = 12L;
 
    /**
     * 機器ID偏左移12位
     */
    private static final long workerIdShift = sequenceBits;
 
    /**
     * 數(shù)據(jù)中心ID左移17位(12+5)
     */
    private static final long dataCenterIdShift = sequenceBits + workerIdBits;
 
    /**
     * 時間毫秒左移22位(5+5+12)
     */
    private static final long timestampLeftShift = sequenceBits + workerIdBits + dataCenterIdBits;
    /**
     * sequence掩碼薪前，確保sequnce不會超出上限
     * 最大的序列號，4096
     * -1 的補碼（二進制全1）右移12位, 然后取反
     * 生成序列的掩碼晃择，這里為4095 (0b111111111111=0xfff=4095)
     */
    private static final long sequenceMask = -1L ^ (-1L << sequenceBits);
 
    //private final static long sequenceMask = ~(-1L << sequenceBits);
    /**
     * 實際的最大workerId的值 結果是31握童，8091
     * workerId原則上上限為1024, 但是需要為每臺sequence服務預留BACKUP_AMOUNT個workerId,
     * (這個移位算法可以很快的計算出幾位二進制數(shù)所能表示的最大十進制數(shù))
     */
    //private static final long maxWorkerId = (1L << workerIdBits) / (BACKUP_COUNT + 1);
 
    //原來代碼 -1 的補碼（二進制全1）右移13位, 然后取反
    private static final long maxWorkerId = -1L ^ (-1L << workerIdBits);
    //private final static long maxWorkerId = ~(-1L << workerIdBits);
 
    /**
     * 支持的最大數(shù)據(jù)標識id姆怪，結果是31
     */
    private static final long maxDataCenterId = -1L ^ (-1L << dataCenterIdBits);
    /**
     * long workerIdBits = 5L;
     * -1L 的二進制: 1111111111111111111111111111111111111111111111111111111111111111
     * -1L<<workerIdBits = -32 ,二進制: 1111111111111111111111111111111111111111111111111111111111100000
     *  workerMask= -1L ^ -32 = 31, 二進制: 11111
     */
    private static long workerMask= -1L ^ (-1L << workerIdBits);
    //進程編碼
    private long processId = 1L;
    private static long processMask=-1L ^ (-1L << dataCenterIdBits);
 
 
    /**
     * 工作機器ID(0~31)
     * snowflake算法給workerId預留了10位，即workId的取值范圍為[0, 1023]稽揭，
     * 事實上實際生產(chǎn)環(huán)境不大可能需要部署1024個分布式ID服務溪掀，
     * 所以：將workerId取值范圍縮小為[0, 511]事镣，[512, 1023]
     * 這個范圍的workerId當做備用workerId。workId為0的備用workerId是512蛮浑，
     * workId為1的備用workerId是513只嚣，以此類推
     */
    private static long workerId;
 
    /**
     * 數(shù)據(jù)中心ID(0~31)
     */
    private long dataCenterId;
 
    /**
     * 當前毫秒生成的序列
     */
    private long sequence = 0L;
 
    /**
     * 上次生成ID的時間戳
     */
    private long lastTimestamp = -1L;
 
    private long extension = 0L;
    private long maxExtension =  0L;
 
    /**
     * 保留workerId和lastTimestamp, 以及備用workerId和其對應的lastTimestamp
     */
    private static Map<Long, Long> workerIdLastTimeMap = new ConcurrentHashMap<>();
 
    /**
     * 最大容忍時間, 單位毫秒, 即如果時鐘只是回撥了該變量指定的時間, 那么等待相應的時間即可;
     * 考慮到sequence服務的高性能, 這個值不易過大
     */
    private static final long MAX_BACKWARD_MS = 3;
    private static SnowflakeIdFactory idWorker;
 
    static {
        idWorker = new SnowflakeIdFactory();
    }
 
 
 
    static {
        Calendar calendar = Calendar.getInstance();
        calendar.set(2018, Calendar.NOVEMBER, 1);
        calendar.set(Calendar.HOUR_OF_DAY, 0);
        calendar.set(Calendar.MINUTE, 0);
        calendar.set(Calendar.SECOND, 0);
        calendar.set(Calendar.MILLISECOND, 0);
        // EPOCH是服務器第一次上線時間點, 設置后不允許修改
        EPOCH = calendar.getTimeInMillis();
 
        // 初始化workerId和其所有備份workerId與lastTimestamp
        // 假設workerId為0且BACKUP_AMOUNT為4, 那么map的值為: {0:0L, 256:0L, 512:0L, 768:0L}
        // 假設workerId為2且BACKUP_AMOUNT為4, 那么map的值為: {2:0L, 258:0L, 514:0L, 770:0L}
       /* for (int i = 0; i<= BACKUP_COUNT; i++){
            workerIdLastTimeMap.put(workerId + (i * maxWorkerId), 0L);
        }*/
    }
 
    //成員類沮稚，IdGenUtils的實例對象的保存域
    private static class SnowflakeIdGenHolder {
        private static final SnowflakeIdFactory instance = new SnowflakeIdFactory();
    }
    //外部調用獲取IdGenUtils的實例對象，確保不可變
    public static SnowflakeIdFactory getInstance(){
        return SnowflakeIdGenHolder.instance;
    }
 
    /**
     * 靜態(tài)工具類
     *
     * @return
     */
    public static Long generateId(){
        long id = idWorker.nextId();
        return id;
    }
 
    //初始化構造蕴掏，無參構造有參函數(shù)调鲸，默認節(jié)點都是0
    public SnowflakeIdFactory(){
        //this(0L, 0L);
        this.dataCenterId = getDataCenterId(maxDataCenterId);
        //獲取機器編碼
        this.workerId = getWorkerId(dataCenterId, maxWorkerId);
    }
 
    /**
     * 構造函數(shù)
     * @param workerId 工作ID (0~31)
     * @param dataCenterId 數(shù)據(jù)中心ID (0~31)
     */
    public SnowflakeIdFactory(long workerId, long dataCenterId) {
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
        }
        if (dataCenterId > maxDataCenterId || dataCenterId < 0) {
            throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDataCenterId));
        }
        this.workerId = workerId;
        this.dataCenterId = dataCenterId;
    }
 
   /**
     * 獲取帶自定義前綴的全局唯一編碼
     */
    public String getStrCodingByPrefix(String prefix){
        Long ele = this.nextId();
        return prefix + ele.toString();
    }
 
    /**
     * 獲得下一個ID (該方法是線程安全的)
     * 在單節(jié)點上獲得下一個ID藐石，使用Synchronized控制并發(fā)，而非CAS的方式于微，
     * 是因為CAS不適合并發(fā)量非常高的場景。
     *
     * 考慮時鐘回撥
     * 缺陷: 如果連續(xù)兩次時鐘回撥, 可能還是會有問題, 但是這種概率極低極低
     * @return
     */
    public synchronized long nextId() {
        long currentTimestamp = timeGen();
        // 當發(fā)生時鐘回撥時
        if (currentTimestamp < lastTimestamp){
            // 如果時鐘回撥在可接受范圍內, 等待即可
            long offset = lastTimestamp - currentTimestamp;
            if ( offset <= MAX_BACKWARD_MS){
                try {
                    //睡（lastTimestamp - currentTimestamp）ms讓其追上
                    LockSupport.parkNanos(TimeUnit.MILLISECONDS.toNanos(offset));
                    //時間偏差大小小于5ms驱证，則等待兩倍時間
                    //wait(offset << 1);
                    //Thread.sleep(waitTimestamp);
 
                    currentTimestamp = timeGen();
                    //如果時間還小于當前時間恋腕，那么利用擴展字段加1
                    //或者是采用拋異常并上報
                    if (currentTimestamp < lastTimestamp) {
                        //擴展字段
                        //extension += 1;
                        //if (extension > maxExtension) {
                            //服務器時鐘被調整了,ID生成器停止服務.
                            throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - currentTimestamp));
                        //}
                    }
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }else {
                //擴展字段
                /*extension += 1;
                if (extension > maxExtension) {
                    //服務器時鐘被調整了,ID生成器停止服務.
                    throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - currentTimestamp));
                }*/
                tryGenerateKeyOnBackup(currentTimestamp);
            }
        }
        //對時鐘回撥簡單處理
       /* if (currentTimestamp < lastTimestamp) {
            //服務器時鐘被調整了,ID生成器停止服務.
            throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - currentTimestamp));
        }*/
 
        // 如果和最后一次請求處于同一毫秒, 那么sequence+1
        if (lastTimestamp == currentTimestamp) {
            // 如果當前生成id的時間還是上次的時間荠藤，那么對sequence序列號進行+1
            sequence = (sequence + 1) & sequenceMask;
            if (sequence == 0) {
                //自旋等待到下一毫秒
                currentTimestamp = waitUntilNextTime(lastTimestamp);
            }
            //判斷是否溢出,也就是每毫秒內超過4095哈肖，當為4096時，與sequenceMask相與牡彻，sequence就等于0
            /*if (sequence == sequenceMask) {
 
                // 當前毫秒生成的序列數(shù)已經(jīng)大于最大值庄吼，那么阻塞到下一個毫秒再獲取新的時間戳
                currentTimestamp = this.waitUntilNextTime(lastTimestamp);
            }*/
 
        } else {
            // 如果是一個更近的時間戳, 那么sequence歸零
            sequence = 0L;
        }
        // 更新上次生成id的時間戳
        lastTimestamp = currentTimestamp;
 
        // 更新map中保存的workerId對應的lastTimestamp
        //workerIdLastTimeMap.put(this.workerId, lastTimestamp);
 
        if (log.isDebugEnabled()) {
            log.debug("{}-{}-{}", new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS").format(new Date(lastTimestamp)), workerId, sequence);
        }
 
        // 進行移位操作生成int64的唯一ID
        //時間戳右移動23位
        long timestamp = (currentTimestamp - EPOCH) << timestampLeftShift;
 
        //workerId 右移動10位
        long workerId = this.workerId << workerIdShift;
 
        //dataCenterId 右移動(sequenceBits + workerIdBits = 17位)
        long dataCenterId = this.dataCenterId << dataCenterIdShift;
        return timestamp | dataCenterId | workerId | sequence;
    }
 
    /**
     * 嘗試在workerId的備份workerId上生成
     * 核心優(yōu)化代碼在方法tryGenerateKeyOnBackup()中，BACKUP_COUNT即備份workerId數(shù)越多器罐，
     * sequence服務避免時鐘回撥影響的能力越強渐行，但是可部署的sequence服務越少，
     * 設置BACKUP_COUNT為3肴沫，最多可以部署1024/(3+1)即256個sequence服務蕴忆，完全夠用，
     * 抗時鐘回撥影響的能力也得到非常大的保障套鹅。
     * @param currentMillis 當前時間
     */
    private long tryGenerateKeyOnBackup(long currentMillis){
        // 遍歷所有workerId(包括備用workerId, 查看哪些workerId可用)
        for (Map.Entry<Long, Long> entry:workerIdLastTimeMap.entrySet()){
            this.workerId = entry.getKey();
            // 取得備用workerId的lastTime
            Long tempLastTime = entry.getValue();
            lastTimestamp = tempLastTime==null?0L:tempLastTime;
 
            // 如果找到了合適的workerId
            if (lastTimestamp<=currentMillis){
                return lastTimestamp;
            }
        }
 
        // 如果所有workerId以及備用workerId都處于時鐘回撥, 那么拋出異常
        throw new IllegalStateException("Clock is moving backwards, current time is "
                +currentMillis+" milliseconds, workerId map = " + workerIdLastTimeMap);
    }
 
    /**
     * 阻塞到下一個毫秒卓鹿，直到獲得新的時間戳
     * @param lastTimestamp 上次生成ID的時間截
     * @return 當前時間戳
     */
    protected long waitUntilNextTime(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }
 
    protected long timeGen() {
        return System.currentTimeMillis();
    }
 
    /**
     *  獲取WorkerId
     * @param dataCenterId
     * @param maxWorkerId
     * @return
     */
    protected static long getWorkerId(long dataCenterId, long maxWorkerId) {
        StringBuffer mpid = new StringBuffer();
        mpid.append(dataCenterId);
        String name = ManagementFactory.getRuntimeMXBean().getName();
        if (!name.isEmpty()) {
           // GET jvmPid
           mpid.append(name.split("@")[0]);
        }
       // MAC + PID 的 hashcode 獲取16個低位
        return (mpid.toString().hashCode() & 0xffff) % (maxWorkerId + 1);
    }
 
    /**
     * 獲取機器編碼 用來做數(shù)據(jù)ID
     * 數(shù)據(jù)標識id部分 通常不建議采用下面的MAC地址方式吟孙，
     * 因為用戶通過破解很容易拿到MAC進行破壞
     */
    protected static long getDataCenterId(long tempMaxDataCenterId) {
        if (tempMaxDataCenterId < 0L  || tempMaxDataCenterId > maxDataCenterId) {
            tempMaxDataCenterId = maxDataCenterId;
        }
        long id = 0L;
        try {
            InetAddress ip = InetAddress.getLocalHost();
            NetworkInterface network = NetworkInterface.getByInetAddress(ip);
            if (network == null) {
                id = 1L;
            } else {
                byte[] mac = network.getHardwareAddress();
                id = ((0x000000FF & (long) mac[mac.length - 1])
                        | (0x0000FF00 & (((long) mac[mac.length - 2]) << 8))) >> 6;
                id = id % (tempMaxDataCenterId + 1);
            }
        } catch (Exception e) {
            System.out.println(" getDatacenterId: " + e.getMessage());
        }
        return id;
    }
 
 
    public static void testProductIdByMoreThread(int dataCenterId, int workerId, int n) throws InterruptedException {
        List<Thread> tlist = new ArrayList<>();
        Set<Long> setAll = new HashSet<>();
        CountDownLatch cdLatch = new CountDownLatch(10);
        long start = System.currentTimeMillis();
        int threadNo = dataCenterId;
        Map<String,SnowflakeIdFactory> idFactories = new HashMap<>();
        for(int i=0;i<10;i++){
            //用線程名稱做map key.
            idFactories.put("snowflake"+i,new SnowflakeIdFactory(workerId, threadNo++));
        }
        for(int i=0;i<10;i++){
            Thread temp =new Thread(new Runnable() {
                @Override
                public void run() {
                    Set<Long> setId = new HashSet<>();
                    SnowflakeIdFactory idWorker = idFactories.get(Thread.currentThread().getName());
                    for(int j=0;j<n;j++){
                        setId.add(idWorker.nextId());
                    }
                    synchronized (setAll){
                        setAll.addAll(setId);
                        log.info("{}生產(chǎn)了{}個id,并成功加入到setAll中.",Thread.currentThread().getName(),n);
                    }
                    cdLatch.countDown();
                }
            },"snowflake"+i);
            tlist.add(temp);
        }
        for(int j=0;j<10;j++){
            tlist.get(j).start();
        }
        cdLatch.await();
 
        long end1 = System.currentTimeMillis() - start;
 
        log.info("共耗時:{}毫秒,預期應該生產(chǎn){}個id, 實際合并總計生成ID個數(shù):{}",end1,10*n,setAll.size());
 
    }
 
    public static void testProductId(int dataCenterId, int workerId, int n){
        SnowflakeIdFactory idWorker = new SnowflakeIdFactory(workerId, dataCenterId);
        SnowflakeIdFactory idWorker2 = new SnowflakeIdFactory(workerId+1, dataCenterId);
        Set<Long> setOne = new HashSet<>();
        Set<Long> setTow = new HashSet<>();
        long start = System.currentTimeMillis();
        for (int i = 0; i < n; i++) {
            setOne.add(idWorker.nextId());//加入set
        }
        long end1 = System.currentTimeMillis() - start;
        log.info("第一批ID預計生成{}個,實際生成{}個<<<<*>>>>共耗時:{}",n,setOne.size(),end1);
 
        for (int i = 0; i < n; i++) {
            setTow.add(idWorker2.nextId());//加入set
        }
        long end2 = System.currentTimeMillis() - start;
        log.info("第二批ID預計生成{}個,實際生成{}個<<<<*>>>>共耗時:{}",n,setTow.size(),end2);
 
        setOne.addAll(setTow);
        log.info("合并總計生成ID個數(shù):{}",setOne.size());
 
    }
 
    public static void testPerSecondProductIdNums(){
        SnowflakeIdFactory idWorker = new SnowflakeIdFactory(1, 2);
        long start = System.currentTimeMillis();
        int count = 0;
        for (int i = 0; System.currentTimeMillis()-start<1000; i++,count=i) {
            /**  測試方法一: 此用法純粹的生產(chǎn)ID,每秒生產(chǎn)ID個數(shù)為300w+ */
            idWorker.nextId();
            /**  測試方法二: 在log中打印,同時獲取ID,此用法生產(chǎn)ID的能力受限于log.error()的吞吐能力.
             * 每秒徘徊在10萬左右. */
            //log.error("{}",idWorker.nextId());
        }
        long end = System.currentTimeMillis()-start;
        System.out.println(end);
        System.out.println(count);
    }
 
    public static void main(String[] args) {
        /** case1: 測試每秒生產(chǎn)id個數(shù)?
         *   結論: 每秒生產(chǎn)id個數(shù)300w+ */
        testPerSecondProductIdNums();
 
        /** case2: 單線程-測試多個生產(chǎn)者同時生產(chǎn)N個id,驗證id是否有重復?
         *   結論: 驗證通過,沒有重復. */
        //testProductId(1,2,10000);//驗證通過!
        //testProductId(1,2,20000);//驗證通過!
 
        /** case3: 多線程-測試多個生產(chǎn)者同時生產(chǎn)N個id, 全部id在全局范圍內是否會重復?
         *   結論: 驗證通過,沒有重復. */
       /* try {
            testProductIdByMoreThread(1,2,100000);//單機測試此場景,性能損失至少折半!
        } catch (InterruptedException e) {
            e.printStackTrace();
        }*/
 
    }
}

由于時間回撥導致的生產(chǎn)重復的ID的問題肥隆，其實百度和美團都有自己的解決方案了稚失，有興趣可以去看看栋艳，下面不是它們官網(wǎng)文檔的信息：

• 百度UIDGenerator：https://github.com/baidu/uid-...

  • UidGenerator是Java實現(xiàn)的, 基于Snowflake算法的唯一ID生成器。UidGenerator以組件形式工作在應用項目中, 支持自定義workerId位數(shù)和初始化策略, 從而適用于docker等虛擬化環(huán)境下實例自動重啟句各、漂移等場景凿宾。 在實現(xiàn)上, UidGenerator通過借用未來時間來解決sequence天然存在的并發(fā)限制; 采用RingBuffer來緩存已生成的UID, 并行化UID的生產(chǎn)和消費, 同時對CacheLine補齊，避免了由RingBuffer帶來的硬件級「偽共享」問題. 最終單機QPS可達600萬初厚。

• 美團Leaf:https://tech.meituan.com/2019...

  • leaf-segment 方案

    • 優(yōu)化：雙buffer + 預分配
    • 容災：Mysql DB 一主兩從，異地機房排作，半同步方式
    • 缺點：如果用segment號段式方案：id是遞增妄痪，可計算的，不適用于訂單ID生成場景裳瘪，比如競對在兩天中午12點分別下單罪针，通過訂單id號相減就能大致計算出公司一天的訂單量，這個是不能忍受的皆怕。

  • leaf-snowflake方案

    • 使用Zookeeper持久順序節(jié)點的特性自動對snowflake節(jié)點配置workerID

      • 1.啟動Leaf-snowflake服務西篓，連接Zookeeper，在leaf_forever父節(jié)點下檢查自己是否已經(jīng)注冊過（是否有該順序子節(jié)點）虱黄。
      • 2.如果有注冊過直接取回自己的workerID（zk順序節(jié)點生成的int類型ID號）吮成，啟動服務粱甫。
      • 3.如果沒有注冊過，就在該父節(jié)點下面創(chuàng)建一個持久順序節(jié)點茶宵，創(chuàng)建成功后取回順序號當做自己的workerID號乌庶，啟動服務。

    • 緩存workerID螃征，減少第三方組件的依賴

    • 由于強依賴時鐘透敌，對時間的要求比較敏感踢械，在機器工作時NTP同步也會造成秒級別的回退内列，建議可以直接關閉NTP同步泼疑。要么在時鐘回撥的時候直接不提供服務直接返回ERROR_CODE荷荤，等時鐘追上即可。或者做一層重試会油，然后上報報警系統(tǒng)古毛，更或者是發(fā)現(xiàn)有時鐘回撥之后自動摘除本身節(jié)點并報警

參考：
https://segmentfault.com/a/1190000040964518

https://blog.csdn.net/bangyanya/article/details/134182630

https://blog.csdn.net/weixin_39075154/article/details/137965936

https://blog.csdn.net/ycb1689/article/details/89331634