一、簡介

有這么一種說法，自然界中并不存在兩片完全一樣的雪花的。每一片雪花都擁有自己漂亮獨特的形狀、獨一無二。雪花算法也表示生成的ID如雪花般獨一無二。

雪花算法 （SnowFlake ）算法，是 Twitter 開源的分布式 id 生成算法。

其核心思想是：使用一個 64 bit 的 long 型的數字作為全局唯一 id。在分布式系統中的應用十分廣泛，且ID 引入了時間戳，基本上保持自增的。

這 64 個 bit 中，其中 1 個 bit 是不用的（我們生成的 id 都是正數，所以第一個 bit 統一都是 0），然后用其中的 41 bit 作為毫秒數，用 10 bit 作為工作機器 id，12 bit 作為序列號。

第一個部分，是 1 個 bit：0，這個是無意義的。

第二個部分是 41 個 bit：表示的是時間戳。

第三個部分是 5 個 bit：表示的是機房 id，10001。

第四個部分是 5 個 bit：表示的是機器 id，1 1001。

第五個部分是 12 個 bit：表示的序號，就是某個機房某臺機器上這一毫秒內同時生成的 id 的序號，0000 00000000。

①1 bit：是不用的，為啥呢？

因為二進制里第一個 bit 為如果是 1，那么都是負數，但是我們生成的 id 都是正數，所以第一個 bit 統一都是 0。

②41 bit：表示的是時間戳，單位是毫秒。

41 bit 可以表示的數字多達 2^41 - 1，也就是可以標識 2 ^ 41 - 1 個毫秒值，換算成年就是表示 69 年的時間。

③10 bit：記錄工作機器 id，代表的是這個服務最多可以部署在 2^10 臺機器上，也就是 1024 臺機器。

但是 10 bit 里 5 個 bit 代表機房 id，5 個 bit 代表機器 id。意思就是最多代表 2 ^ 5 個機房（32 個機房），每個機房里可以代表 2 ^ 5 個機器（32 臺機器），也可以根據自己公司的實際情況確定。

④12 bit：這個是用來記錄同一個毫秒內產生的不同 id。

12 bit 可以代表的最大正整數是 2 ^ 12 - 1 = 4096，也就是說可以用這個 12 bit 代表的數字來區分同一個毫秒內的 4096 個不同的 id。

二、算法優缺點

雪花算法的優點：

（1）無依賴：不依賴第三方庫或者中間件，完全在內存中生成，可用性強。

（2）高性能：每秒中能生成數百萬的自增ID。

（3）ID自增：基于時間戳，以及同一時間戳下序列號自增，基本保證 id 有序遞增。

雪花算法的缺點：

依賴與系統時間的一致性，如果系統時間被回調，或者改變，可能會造成id沖突或者重復。算法中可通過記錄最后一個生成 id 時的時間戳來解決，每次生成 id 之前比較當前服務器時鐘是否被回撥，避免生成重復 id。

三、算法實現

代碼實現：

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import java.lang.management.ManagementFactory;
import java.net.InetAddress;
import java.net.NetworkInterface;public class IdWorker {private static final Logger LOGGER = LoggerFactory.getLogger(IdWorker .class);private final static String ERROR_CLOCK_BACK = "時間回撥，拒絕為超出%d毫秒生成ID";private final static String ERROR_ATTR_LIMIT = "%s屬性的范圍為0-%d";/*** 用于用當前時間戳減去這個時間戳，算出偏移量*/protected static final long TWEPOCH = 1538211907857L;/*** 機器id所占的位數(表示只允許workId的范圍為：0-1023)*/protected static final long WORKER_ID_BITS = 5L;/*** 數據標識id所占的位數*/protected static final long DATACENTER_ID_BITS = 5L;/*** 支持的最大機器id，結果是31 (這個移位算法可以很快的計算出幾位二進制數所能表示的最大十進制數)*/private static final long MAX_WORKER_ID = ~(-1L << WORKER_ID_BITS);/*** 支持的最大數據標識id，結果是31*/private static final long MAX_DATACENTER_ID = ~(-1L << DATACENTER_ID_BITS);/*** 序列在id中占的位數 (表示只允許sequenceId的范圍為：0-4095)*/protected static final long SEQUENCE_BITS = 12L;/*** 機器ID向左移12位*/private static final long WORKER_ID_SHIFT = SEQUENCE_BITS;/*** 數據標識id向左移17位(12+5)*/private static final long DATACENTER_ID_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS;/*** 時間截向左移22位(5+5+12)*/private static final long TIMESTAMP_LEFT_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS + DATACENTER_ID_BITS;/*** 生成序列的掩碼，(防止溢出:位與運算保證計算的結果范圍始終是 0-4095，0b111111111111=0xfff=4095)*/private static final long SEQUENCE_MASK = -1L ^ (-1L << SEQUENCE_BITS);/*** 工作機器ID(0~31)*/private long workerId;/*** 數據中心ID(0~31)*/private long datacenterId;/*** 毫秒內序列(0~4095)*/private long sequence = 0L;/*** 上次生成ID的時間截*/private long lastTimestamp = -1L;public IdWorker () {this.datacenterId = getDataCenterId(MAX_DATACENTER_ID);this.workerId = getWorkerId(datacenterId, MAX_WORKER_ID);}public IdWorker (long workerId, long dataCenterId) {if (workerId > MAX_WORKER_ID || workerId < 0) {throw new IllegalArgumentException(String.format(ERROR_ATTR_LIMIT, "workerId", MAX_WORKER_ID));}this.workerId = workerId;this.datacenterId = dataCenterId;}private static long getWorkerId (long dataCenterId, long maxWorkerId) {StringBuffer mpid = new StringBuffer();mpid.append(dataCenterId);String name = ManagementFactory.getRuntimeMXBean().getName();if (!name.isEmpty()) {// GET jvmPidmpid.append(name.split("@")[0]);}// MAC + PID 的 hashcode 獲取16個低位return (mpid.toString().hashCode() & 0xffff) % (maxWorkerId + 1);}private static long getDataCenterId(long tempMaxDataCenterId) {if (tempMaxDataCenterId < 0L || tempMaxDataCenterId > MAX_DATACENTER_ID) {tempMaxDataCenterId = MAX_DATACENTER_ID;}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) {LOGGER.warn("Get Data Center Id error, e:{}", e);}return id;}public synchronized long nextId() {long timestamp = timeGen();// 閏秒：如果當前時間小于上一次ID生成的時間戳，說明系統時鐘回退過這個時候應當拋出異常if (timestamp < lastTimestamp) {long offset = lastTimestamp - timestamp;if (offset <= 5) {try {// 時間偏差大小小于5ms，則等待兩倍時間wait(offset << 1);timestamp = timeGen();if (timestamp < lastTimestamp) {// 還是小于，拋異常并上報throw new RuntimeException(String.format(ERROR_CLOCK_BACK, lastTimestamp - timestamp));}} catch (InterruptedException e) {throw new RuntimeException(e);}} else {throw new RuntimeException(String.format(ERROR_CLOCK_BACK, lastTimestamp - timestamp));}}// 解決跨毫秒生成ID序列號始終為偶數的缺陷:如果是同一時間生成的，則進行毫秒內序列if (lastTimestamp == timestamp) {// 通過位與運算保證計算的結果范圍始終是 0-4095sequence = (sequence + 1) & SEQUENCE_MASK;// 毫秒內序列溢出if (sequence == 0) {// 阻塞到下一個毫秒,獲得新的時間戳timestamp = tilNextMillis(lastTimestamp);}} else {// 時間戳改變，毫秒內序列重置sequence = 0L;}// 上次生成ID的時間截lastTimestamp = timestamp;return ((timestamp - TWEPOCH) << TIMESTAMP_LEFT_SHIFT)| (datacenterId << DATACENTER_ID_SHIFT)| (workerId << WORKER_ID_SHIFT)| sequence;}private long tilNextMillis(long lastTimestamp) {long timestamp = timeGen();while (timestamp <= lastTimestamp) {timestamp = timeGen();}return timestamp;}private long timeGen() {return System.currentTimeMillis();}
}

測試代碼：

public static void main(String[] args) {IdWorker idWorker = new IdWorker();for (int i = 0; i < 10; i++){System.out.println(idWorker.nextId());}}

輸出結果：

761722546083581952
761722546083581953
761722546083581954
761722546087776256
761722546087776257
761722546087776258
761722546087776259
761722546087776260
761722546087776261
761722546087776262