一、概述

1侥锦、SnowFlake算法生成id的結(jié)果是一個64bit大小的整數(shù)挽荠，它的結(jié)構(gòu)如下圖：

image.png

● 1位克胳，不用平绩。二進制中最高位為1的都是負數(shù)，但是我們生成的id一般都使用整數(shù)漠另，所以這個最高位固定是0

● 41位捏雌，用來記錄時間戳（毫秒）。
○ 41位可以表示個數(shù)字酗钞，
○ 如果只用來表示正整數(shù)（計算機中正數(shù)包含0）腹忽，可以表示的數(shù)值范圍是：0 至 ，減1是因為可表示的數(shù)值范圍是從0開始算的砚作，而不是1窘奏。
○ 也就是說41位可以表示個毫秒的值，轉(zhuǎn)化成單位年則是年

● 10位葫录，用來記錄工作機器id着裹。
○ 可以部署在個節(jié)點，包括 5位datacenterId 和 5位workerId
○ 5位（bit）可以表示的最大正整數(shù)是米同，即可以用0骇扇、1、2面粮、3少孝、....31這32個數(shù)字，來表示不同的datecenterId或workerId

● 12位熬苍，序列號稍走，用來記錄同毫秒內(nèi)產(chǎn)生的不同id。
○ 12位（bit）可以表示的最大正整數(shù)是柴底，即可以用0婿脸、1、2柄驻、3狐树、....4094這4095個數(shù)字，來表示同一機器同一時間截（毫秒)內(nèi)產(chǎn)生的4095個ID序號

由于在Java中64bit的整數(shù)是long類型鸿脓，所以在Java中SnowFlake算法生成的id就是long來存儲的抑钟。

SnowFlake可以保證：
● 所有生成的id按時間趨勢遞增
● 整個分布式系統(tǒng)內(nèi)不會產(chǎn)生重復(fù)id（因為有datacenterId和workerId來做區(qū)分）

二、使用

網(wǎng)上的教程一般存在兩個問題：
1. 機器ID（5位）和數(shù)據(jù)中心ID（5位）配置沒有解決野哭，分布式部署的時候會使用相同的配置味赃，任然有ID重復(fù)的風(fēng)險。
2. 使用的時候需要實例化對象虐拓，沒有形成開箱即用的工具類心俗。

本文針對上面兩個問題進行解決，筆者的解決方案是，workId使用服務(wù)器hostName生成城榛，dataCenterId使用IP生成揪利，這樣可以最大限度防止10位機器碼重復(fù)，但是由于兩個ID都不能超過32狠持，只能取余數(shù)疟位，還是難免產(chǎn)生重復(fù)，但是實際使用中喘垂，hostName和IP的配置一般連續(xù)或相近甜刻，只要不是剛好相隔32位，就不會有問題正勒，況且得院，hostName和IP同時相隔32的情況更加是幾乎不可能的事，平時做的分布式部署章贞，一般也不會超過10臺容器祥绞。

使用上面的方法可以零配置使用雪花算法，雪花算法10位機器碼的設(shè)定理論上可以有1024個節(jié)點鸭限，生產(chǎn)上使用docker配置一般是一次編譯蜕径，然后分布式部署到不同容器，不會有不同的配置败京，這里不知道其他公司是如何解決的兜喻，即使有方法使用一套配置，然后運行時根據(jù)不同容器讀取不同的配置赡麦，但是給每個容器編配ID朴皆，1024個（大部分情況下沒有這么多），似乎也不太可能隧甚，此問題留待日后解決后再行補充车荔。

具體生成 workId 和 dataCenterId 的方法如下：

    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);
        }
    }

使用上面的方法需要增加Apache Commons lang3 的依賴戚扳，這也是此方法的缺點，但是在實際使用的時候族吻，lang3這個類一般也是要引入的帽借，非常非常好用，提高效率的利器 (注意：這里的commons-lang3必須是 3.8版本或者更高版本超歌，否則低于這個版本會報沒有toCodePoints(CharSequence str) 和 getHostName() 方法)砍艾。

<dependency>
    <groupId>org.apache.commons</groupId>
    <artifactId>commons-lang3</artifactId>
    <version>3.8</version>
</dependency>

最終的完整代碼如下：

package cn.com.xxx.xxx.util;

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;
import java.util.Date;

/**
 * Twitter_Snowflake<br>
 * SnowFlake的結(jié)構(gòu)如下(每部分用-分開):<br>
 * 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 <br>
 * 1位標識，由于long基本類型在Java中是帶符號的巍举，最高位是符號位脆荷，正數(shù)是0，負數(shù)是1，所以id一般是正數(shù)蜓谋，最高位是0<br>
 * 41位時間截(毫秒級)梦皮，注意，41位時間截不是存儲當前時間的時間戳桃焕，而是存儲時間戳的差值（當前時間戳 - 開始時間戳)
 * 得到的值）剑肯，這里的的開始時間戳，一般是我們的id生成器開始使用的時間观堂，由我們程序來指定的（如下下面程序IdWorker類的startTime屬性）让网。41位的時間戳，可以使用69年师痕，年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69<br>
 * 10位的數(shù)據(jù)機器位溃睹，可以部署在1024個節(jié)點，包括5位datacenterId和5位workerId<br>
 * 12位序列七兜，毫秒內(nèi)的計數(shù)丸凭，12位的計數(shù)順序號支持每個節(jié)點每毫秒(同一機器，同一時間截)產(chǎn)生4096個ID序號<br>
 * 加起來剛好64位腕铸，為一個Long型惜犀。<br>
 * SnowFlake的優(yōu)點是，整體上按照時間自增排序狠裹，并且整個分布式系統(tǒng)內(nèi)不會產(chǎn)生ID碰撞(由數(shù)據(jù)中心ID和機器ID作區(qū)分)虽界，并且效率較高，經(jīng)測試涛菠，SnowFlake每秒能夠產(chǎn)生26萬ID左右莉御。
 */
public class SnowflakeIdUtils {

    /** 開始時間截 (2021-01-01) */
    private final long twepoch = 1609430400000L;

    /** 機器id所占的位數(shù) */
    private final long workerIdBits = 5L;

    /** 數(shù)據(jù)標識id所占的位數(shù) */
    private final long dataCenterIdBits = 5L;

    /** 支持的最大機器id，結(jié)果是31 (這個移位算法可以很快的計算出幾位二進制數(shù)所能表示的最大十進制數(shù)) */
    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);

    /** 支持的最大數(shù)據(jù)標識id俗冻，結(jié)果是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;

    /** 毫秒內(nèi)序列(0~4095) */
    private long sequence = 0L;

    /** 上次生成ID的時間截 */
    private long lastTimestamp = -1L;

    private static SnowflakeIdUtils idWorker;

    static {
        idWorker = new SnowflakeIdUtils(getWorkId(), getDataCenterId());
    }

    /**
     * 構(gòu)造函數(shù)
     * @param workerId 工作ID (0~31)
     * @param dataCenterId 數(shù)據(jù)中心ID (0~31)
     */
    public SnowflakeIdUtils(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;
    }

    /**
     * 獲得下一個ID (該方法是線程安全的)
     * @return SnowflakeId
     */
    public synchronized long nextId() {
        long timestamp = timeGen();

        //如果當前時間小于上一次ID生成的時間戳，說明系統(tǒng)時鐘回退過這個時候應(yīng)當拋出異常
        if (timestamp < lastTimestamp) {
            throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
        }

        //如果是同一時間生成的迄薄，則進行毫秒內(nèi)序列
        if (lastTimestamp == timestamp) {
            sequence = (sequence + 1) & sequenceMask;
            //毫秒內(nèi)序列溢出
            if (sequence == 0) {
                //阻塞到下一個毫秒,獲得新的時間戳
                timestamp = tilNextMillis(lastTimestamp);
            }
        }
        //時間戳改變琅关，毫秒內(nèi)序列重置
        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
     */
    public static synchronized Long generateId(){
        long id = idWorker.nextId();
        return id;
    }

    /** 測試 */
    public static void main(String[] args) {
        System.out.println(System.currentTimeMillis());
        long startTime = System.nanoTime();
        for (int i = 0; i < 5; i++) {
            long id = SnowflakeIdUtils.generateId();
            System.out.println(id);
        }
        System.out.println((System.nanoTime()-startTime)/1000000+"ms");

        Date date = DateUtils.stringToDate("2021-01-01 00:00:00");
        System.out.println(date.getTime());
    }

}