文章目錄
-
- 一、前言
- 二、雪花算法snowflake
-
- 1、基本定義
- 2、snowflake的優缺點
- 三、Java代碼實作snowflake
-
- 1、組裝生成id
- 2、計算最大值的幾種方式
- 3、反解析ID
- 4、ID生成器使用方式
- 四、時鐘回撥問題和解決方案讨論
-
- 1、時間戳自增徹底解決時鐘回撥問題
- 2、緩存曆史序列号緩解時鐘回撥問題
- 3、等待時鐘校正
- 五、要點總結
一、前言
在日趨複雜的分布式系統中，資料量越來越大，資料庫分庫分表是一貫的垂直水準做法，但是需要一個全局唯一ID辨別一條資料或者MQ消息，資料庫id自增就顯然不能滿足要求了。因為場景不同，分布式ID需要滿足以下幾個條件：
- 全局唯一性，不能出現重複的ID。
- 趨勢遞增，在
MySQL InnoDB
RDBMS
B-tree
- 單調遞增，保證下一個ID一定大于上一個ID。例如分布式事務版本号、IM增量消息、排序等特殊需求。
- 資訊安全，對于特殊業務，如訂單等，分布式ID生成應該是無規則的，不能從ID上反解析出流量等敏感資訊。
市面上對分布式ID生成大緻有幾種算法（一些開源項目都是圍着這幾種算法進行實作和優化）：
- UUID：因為是本地生成，性能極高，但是生成的ID太長，16位元組128位，通常需要字元串類型存儲，且無序，是以很多場景不适用，也不适用于作為MySQL資料庫的主鍵和索引（MySql官方建議，主鍵越短越好；對于
InnoDB
- 資料庫自增ID：每次擷取ID都需要DB的IO操作，DB壓力大，性能低。資料庫當機對外依賴服務就是毀滅性打擊，不過可以部署資料庫叢集保證高可用。
- 資料庫号段算法：對資料庫自增ID的優化，每次擷取一個号段的值。用完之後再去資料庫擷取新的号段，可以大大減輕資料庫的壓力。号段越長，性能越高，同時如果資料庫當機，号段沒有用完，短時間還可以對外提供服務。（美團的Leaf、滴滴的TinyId）
- 雪花算法：Twitter開源的snowflake，以時間戳+機器+遞增序列組成，基本趨勢遞增，且性能很高，因為強依賴機器時鐘，是以需要考慮時鐘回撥問題，即機器上的時間可能因為校正出現倒退，導緻生成的ID重複。（百度的uid-generator、美團的Leaf）
雪花算法和資料庫号段算法用的最多，本篇主要對雪花算法原理剖析和解決時鐘回撥問題讨論。
二、雪花算法snowflake
1、基本定義
snowflake原理其實很簡單，生成一個
64bit（long）
的全局唯一ID，标準元素以1bit無用符号位+41bit時間戳+10bit機器ID+12bit序列化組成，其中除1bit符号位不可調整外，其他三個辨別的bit都可以根據實際情況調整：
- 41bit-時間可以表示（1L<<41）/(1000L360024*365)=69年的時間。
- 10bit-機器可以表示1024台機器。如果對IDC劃分有需求，還可以将10-bit分5-bit給IDC，分5-bit給工作機器。這樣就可以表示32個IDC，每個IDC下可以有32台機器。
- 12個自增序列号可以表示2^12個ID，理論上snowflake方案的QPS約為409.6w/s。
注：都是從0開始計數。
2、snowflake的優缺點
優點：
- 毫秒數在高位，自增序列在低位，整個ID都是趨勢遞增的。
- 可以不依賴資料庫等第三方系統，以服務的方式部署，穩定性更高，生成ID的性能也非常高。
- 可以根據自身業務特性配置設定bit位，非常靈活。
缺點：
- 強依賴機器時鐘，如果機器上時鐘回撥，會導緻發号重複或者服務處于不可用狀态。
三、Java代碼實作snowflake
如下示例，41bit給時間戳，5bit給IDC，5bit給工作機器，12bit給序列号，代碼中是寫死的，如果某些bit需要動态調整，可在成員屬性定義。計算過程需要一些位運算基礎。
public class SnowflakeIdGenerator {
public static final int TOTAL_BITS = 1 << 6;
private static final long SIGN_BITS = 1;
private static final long TIME_STAMP_BITS = 41L;
private static final long DATA_CENTER_ID_BITS = 5L;
private static final long WORKER_ID_BITS = 5L;
private static final long SEQUENCE_BITS = 12L;
/**
* 時間向左位移位數 22位
*/
private static final long TIMESTAMP_LEFT_SHIFT = WORKER_ID_BITS + DATA_CENTER_ID_BITS + SEQUENCE_BITS;
/**
* IDC向左位移位數 17位
*/
private static final long DATA_CENTER_ID_SHIFT = WORKER_ID_BITS + SEQUENCE_BITS;
/**
* 機器ID 向左位移位數 12位
*/
private static final long WORKER_ID_SHIFT = SEQUENCE_BITS;
/**
* 序列掩碼，用于限定序列最大值為4095
*/
private static final long SEQUENCE_MASK = -1L ^ (-1L << SEQUENCE_BITS);
/**
* 最大支援機器節點數0~31，一共32個
*/
private static final long MAX_WORKER_ID = -1L ^ (-1L << WORKER_ID_BITS);
/**
* 最大支援資料中心節點數0~31，一共32個
*/
private static final long MAX_DATA_CENTER_ID = -1L ^ (-1L << DATA_CENTER_ID_BITS);
/**
* 最大時間戳 2199023255551
*/
private static final long MAX_DELTA_TIMESTAMP = -1L ^ (-1L << TIME_STAMP_BITS);
/**
* Customer epoch
*/
private final long twepoch;
private final long workerId;
private final long dataCenterId;
private long sequence = 0L;
private long lastTimestamp = -1L;
/**
*
* @param workerId 機器ID
* @param dataCenterId IDC ID
*/
public SnowflakeIdGenerator(long workerId, long dataCenterId) {
this(workerId, dataCenterId, null);
}
/**
*
* @param workerId 機器ID
* @param dataCenterId IDC ID
* @param epochDate 初始化時間起點
*/
public SnowflakeIdGenerator(long workerId, long dataCenterId, Date epochDate) {
if (workerId > MAX_WORKER_ID || workerId < 0) {
throw new IllegalArgumentException("worker Id can't be greater than "+ MAX_WORKER_ID + " or less than 0");
}
if (dataCenterId > MAX_DATA_CENTER_ID || dataCenterId < 0) {
throw new IllegalArgumentException("datacenter Id can't be greater than {" + MAX_DATA_CENTER_ID + "} or less than 0");
}
this.workerId = workerId;
this.dataCenterId = dataCenterId;
if (epochDate != null) {
this.twepoch = epochDate.getTime();
} else {
//2010-10-11
this.twepoch = 1286726400000L;
}
}
public long genID() throws Exception {
try {
return nextId();
} catch (Exception e) {
throw e;
}
}
public long getLastTimestamp() {
return lastTimestamp;
}
/**
* 通過移位解析出sequence，sequence有效位為[0,12]
* 是以先向左移64-12，然後再像右移64-12，通過兩次移位就可以把無效位移除了
* @param id
* @return
*/
public long getSequence2(long id) {
return (id << (TOTAL_BITS - SEQUENCE_BITS)) >>> (TOTAL_BITS - SEQUENCE_BITS);
}
/**
* 通過移位解析出workerId，workerId有效位為[13,17], 左右兩邊都有無效位
* 先向左移 41+5+1，移除掉41bit-時間，5bit-IDC、1bit-sign，
* 然後右移回去41+5+1+12，進而移除掉12bit-序列号
* @param id
* @return
*/
public long getWorkerId2(long id) {
return (id << (TIME_STAMP_BITS + DATA_CENTER_ID_BITS + SIGN_BITS)) >>> (TIME_STAMP_BITS + DATA_CENTER_ID_BITS + SEQUENCE_BITS + SIGN_BITS);
}
/**
* 通過移位解析出IDC_ID，dataCenterId有效位為[18,23]，左邊兩邊都有無效位
* 先左移41+1，移除掉41bit-時間和1bit-sign
* 然後右移回去41+1+5+12，移除掉右邊的5bit-workerId和12bit-序列号
* @param id
* @return
*/
public long getDataCenterId2(long id) {
return (id << (TIME_STAMP_BITS + SIGN_BITS)) >>> (TIME_STAMP_BITS + WORKER_ID_BITS + SEQUENCE_BITS + SIGN_BITS);
}
/**
* 41bit-時間，左邊1bit-sign為0，可以忽略，不用左移，是以隻需要右移，并加上起始時間twepoch即可。
* @param id
* @return
*/
public long getGenerateDateTime2(long id) {
return (id >>> (DATA_CENTER_ID_BITS + WORKER_ID_BITS + SEQUENCE_BITS)) + twepoch;
}
public long getSequence(long id) {
return id & ~(-1L << SEQUENCE_BITS);
}
public long getWorkerId(long id) {
return id >> WORKER_ID_SHIFT & ~(-1L << WORKER_ID_BITS);
}
public long getDataCenterId(long id) {
return id >> DATA_CENTER_ID_SHIFT & ~(-1L << DATA_CENTER_ID_BITS);
}
public long getGenerateDateTime(long id) {
return (id >> TIMESTAMP_LEFT_SHIFT & ~(-1L << 41L)) + twepoch;
}
private synchronized long nextId() throws Exception {
long timestamp = timeGen();
// 1、出現時鐘回撥問題，直接抛異常
if (timestamp < lastTimestamp) {
long refusedTimes = lastTimestamp - timestamp;
// 可自定義異常類
throw new UnsupportedOperationException(String.format("Clock moved backwards. Refusing for %d seconds", refusedTimes));
}
// 2、時間等于lastTimestamp，取目前的sequence + 1
if (timestamp == lastTimestamp) {
sequence = (sequence + 1) & SEQUENCE_MASK;
// Exceed the max sequence, we wait the next second to generate id
if (sequence == 0) {
timestamp = tilNextMillis(lastTimestamp);
}
} else {
// 3、時間大于lastTimestamp沒有發生回撥， sequence 從0開始
this.sequence = 0L;
}
lastTimestamp = timestamp;
return allocate(timestamp - this.twepoch);
}
private long allocate(long deltaSeconds) {
return (deltaSeconds << TIMESTAMP_LEFT_SHIFT) | (this.dataCenterId << DATA_CENTER_ID_SHIFT) | (this.workerId << WORKER_ID_SHIFT) | this.sequence;
}
private long timeGen() {
long currentTimestamp = System.currentTimeMillis();
// 時間戳超出最大值
if (currentTimestamp - twepoch > MAX_DELTA_TIMESTAMP) {
throw new UnsupportedOperationException("Timestamp bits is exhausted. Refusing ID generate. Now: " + currentTimestamp);
}
return currentTimestamp;
}
private long tilNextMillis(long lastTimestamp) {
long timestamp = timeGen();
while (timestamp <= lastTimestamp) {
timestamp = timeGen();
}
return timestamp;
}
/**
* 測試
* @param args
*/
public static void main(String[] args) throws Exception {
SnowflakeIdGenerator snowflakeIdGenerator = new SnowflakeIdGenerator(1,2);
long id = snowflakeIdGenerator.genID();
System.out.println("ID=" + id + ", lastTimestamp=" + snowflakeIdGenerator.getLastTimestamp());
System.out.println("ID二進制：" + Long.toBinaryString(id));
System.out.println("解析ID:");
System.out.println("Sequence=" + snowflakeIdGenerator.getSequence(id));
System.out.println("WorkerId=" + snowflakeIdGenerator.getWorkerId(id));
System.out.println("DataCenterId=" + snowflakeIdGenerator.getDataCenterId(id));
System.out.println("GenerateDateTime=" + snowflakeIdGenerator.getGenerateDateTime(id));
System.out.println("Sequence2=" + snowflakeIdGenerator.getSequence2(id));
System.out.println("WorkerId2=" + snowflakeIdGenerator.getWorkerId2(id));
System.out.println("DataCenterId2=" + snowflakeIdGenerator.getDataCenterId2(id));
System.out.println("GenerateDateTime2=" + snowflakeIdGenerator.getGenerateDateTime2(id));
}
}
1、組裝生成id
生成id的過程，就是把每一種辨別（時間、機器、序列号）移到對應位置，然後相加。
long id = (deltaTime << TIMESTAMP_LEFT_SHIFT) | (this.dataCenterId << DATA_CENTER_ID_SHIFT) | (this.workerId << WORKER_ID_SHIFT) | this.sequence;
-
deltaTime
-
dataCenterId
-
workerId
-
sequence
- 中間的
|
+
2、計算最大值的幾種方式
（1）注意到代碼中分别對每個辨別的最大值做了計算：
//序列掩碼，用于限定序列最大值為4095 ((2^12)-1) ，從0開始算就有4096個序列
private static final long SEQUENCE_MASK = -1L ^ (-1L << SEQUENCE_BITS);
//最大支援機器節點數0~31，一共32個 (2^5)-1
private static final long MAX_WORKER_ID = -1L ^ (-1L << WORKER_ID_BITS);
//最大支援資料中心節點數0~31，一共32個 (2^5)-1
private static final long MAX_DATA_CENTER_ID = -1L ^ (-1L << DATA_CENTER_ID_BITS);
//最大時間戳 2199023255551 (2^41)-1
private static final long MAX_DELTA_TIMESTAMP = -1L ^ (-1L << TIME_STAMP_BITS);
如上方式計算最大值并不好了解，就是利用二進制的運算邏輯，如果不了解根本看不懂。拿
-1L ^ (-1L << SEQUENCE_BITS)
舉例：
先看看從哪個方向開始計算：
-1L ^ (-1L << 12)
，
-1L
和
(-1L <<12)
做
^
按位異或運算（
1 ^ 1 = 0，1 ^ 0 = 1，0 ^ 1 = 1，0 ^ 0 = 0
）。
-
-1L
1111111111111111111111111111111111111111111111111111111111111111
-
-1L
1111111111111111111111111111111111111111111111111111 000000 000000
- 最後
1111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111 000000 000000
^
0000000000000000000000000000000000000000000000000000 111111 111111
（2）其實有一種更容易了解的計算最大值的方式，比如計算12bit-序列号的最大值，那就是
(2^12 -1)
呀，但是位運算性能更高，用位運算的方式就是
((1 << 12) -1)
。1左移12位得到
1 0000 0000 0000
，減1也是可以得到
1111 1111 1111
，即4095。
（3）還看到一種計算最大值的方式，繼續拿12bit-序列号舉例，
~(-1L << 12)
，
~
不知道怎麼計算那就傻了：
-1L先向左移12位得到
1111111111111111111111111111111111111111111111111111 000000 000000
，然後進行
~
按位非運算（
~ 1 = -2，~ 0 = -1 ，~n = - ( n+1 )
），也可以了解為反轉，1轉為0,0轉為1，然後也可以得到
0000000000000000000000000000000000000000000000000000 111111 111111
。
3、反解析ID
（1）通過已經生成的ID解析出時間、機器和序列号：
public long getSequence(long id) {
return id & ~(-1L << SEQUENCE_BITS);
}
public long getWorkerId(long id) {
return id >> WORKER_ID_SHIFT & ~(-1L << WORKER_ID_BITS);
}
public long getDataCenterId(long id) {
return id >> DATA_CENTER_ID_SHIFT & ~(-1L << DATA_CENTER_ID_BITS);
}
public long getGenerateDateTime(long id) {
return (id >> TIMESTAMP_LEFT_SHIFT & ~(-1L << 41L)) + twepoch;
}
因為
sequence
本身就在低位，是以不需要移動，其他機器和時間都是需要将id向右移動，使得自己的有效位置在低位，至于和自己的最大值做
&
運算，是為了讓不屬于自己bit的位置無效，即都轉為0。
例如：生成的id為1414362783486840832，轉為二進制
1001110100000110100110111010100111101010001000001000000000000
，想解析出
workerId
，
workerId
有效位為[13, 17]，那就将id向右移12位，移到低位得到
0000000000001001110100000110100110111010100111101010001000001
，
workerId
有5-bit，那麼除了低位5-bit，其他位置都是無效bit，轉為0。
0000000000001001110100000110100110111010100111101010001000001
和
11111
做
&
運算得到1（左邊都是0可以省掉）。
（2）不過還有一種解析的思路更易于了解，就是運用兩次移位運算，把無效位置移除：
1bit-sign + 41bit-time + 5bit-IDC + 5bit-workerId + 12bit-sequence
/**
* 通過移位解析出sequence，sequence有效位為[0,12]
* 是以先向左移64-12，然後再像右移64-12，通過兩次移位就可以把無效位移除了
* @param id
* @return
*/
public long getSequence2(long id) {
return (id << (TOTAL_BITS - SEQUENCE_BITS)) >>> (TOTAL_BITS - SEQUENCE_BITS);
}
/**
* 通過移位解析出workerId，workerId有效位為[13,17], 左右兩邊都有無效位
* 先向左移 41+5+1，移除掉41bit-時間，5bit-IDC、1bit-sign，
* 然後右移回去41+5+1+12，進而移除掉12bit-序列号
* @param id
* @return
*/
public long getWorkerId2(long id) {
return (id << (TIME_STAMP_BITS + DATA_CENTER_ID_BITS + SIGN_BITS)) >>> (TIME_STAMP_BITS + DATA_CENTER_ID_BITS + SEQUENCE_BITS + SIGN_BITS);
}
/**
* 通過移位解析出IDC_ID，dataCenterId有效位為[18,23]，左邊兩邊都有無效位
* 先左移41+1，移除掉41bit-時間和1bit-sign
* 然後右移回去41+1+5+12，移除掉右邊的5bit-workerId和12bit-序列号
* @param id
* @return
*/
public long getDataCenterId2(long id) {
return (id << (TIME_STAMP_BITS + SIGN_BITS)) >>> (TIME_STAMP_BITS + WORKER_ID_BITS + SEQUENCE_BITS + SIGN_BITS);
}
/**
* 41bit-時間，左邊1bit-sign為0，可以忽略，不用左移，是以隻需要右移，并加上起始時間twepoch即可。
* @param id
* @return
*/
public long getGenerateDateTime2(long id) {
return (id >>> (DATA_CENTER_ID_BITS + WORKER_ID_BITS + SEQUENCE_BITS)) + twepoch;
}
4、ID生成器使用方式
主要有兩種方式，一種是發号器，一種是本地生成：
- 發号器，就是把雪花算法ID生成封裝成一個服務，部署在多台機器上，由外界請求發号器服務擷取ID。這樣做的好處，是機器不需要那麼多，1024台完全足夠了，相對ID的時間戳和序列号的bit就可以調大一些。但是因為需要遠端請求擷取ID，是以會受到網絡波動的影響，性能上肯定是沒有直接從本地生成擷取高的，同時發号器一旦挂了，很多服務就不能對外提供服務了，是以發号器服務需要高可用，多執行個體，異地部署和容災，發号器在發号的時候，也可以釋出一段時間的ID，服務本地緩存起來，這樣不僅提高性能，不需要每次都去請求發号器，也在一定程度上緩解了發号器故障帶來的影響。
- 本地生成ID，沒有網絡延遲，性能極高。隻能通過機器id來保證生成的ID唯一性，是以需要提供足夠多的機器id，每台機器可能部署多個服務，每個服務可能部署在多台機器，都需要配置設定不同的機器id，并且服務重新開機了也需要重新配置設定機器id。這樣機器id就有了用後即毀的特點。需要足夠多的機器id，就必須縮減時間bit和序列号bit。
可以利用
MySql
或者
zk
進行機器id的配置設定和管理。
四、時鐘回撥問題和解決方案讨論
首先看看時鐘為什麼會發生回撥？機器本地時鐘可能會因為各種原因發生不準的情況，網絡中提供了NTP服務來做時間校準，做校準的時候就會發生時鐘的跳躍或者回撥的問題。
因為雪花算法強依賴機器時鐘，是以難以避免受到時鐘回撥的影響，有可能産生ID重複。原标準實作代碼中是直接抛異常，短暫停止對外服務，這樣在實際生産中是無法忍受的。是以要盡量避免時鐘回撥帶來的影響，解決思路有兩個：
- 不依賴機器時鐘驅動，就沒時鐘回撥的事兒了。即定義一個初始時間戳，在初始時間戳上自增，不跟随機器時鐘增加。時間戳何時自增？當序列号增加到最大時，此時時間戳+1，這樣完全不會浪費序列号，适合流量較大的場景，如果流量較小，可能出現時間斷層滞後。
- 依然依賴機器時鐘，如果時鐘回撥範圍較小，如幾十毫秒，可以等到時間回到正常；如果流量不大，前幾百毫秒或者幾秒的序列号肯定有剩餘，可以将前幾百毫秒或者幾秒的序列号緩存起來，如果發生時鐘回撥，就從緩存中擷取序列号自增。
（時鐘回撥問題，可通過手動調整電腦上的時鐘進行模拟測試。）
1、時間戳自增徹底解決時鐘回撥問題
private long sequence = -1L;
private long startTimestamp = 1623947387000L;
private synchronized long nextId2() {
long sequenceTmp = sequence;
sequence = (sequence + 1) & SEQUENCE_MASK;
// sequence =0 有可能是初始+1=0，也可能是超過了最大值等于0
// 是以把 初始+1=0排除掉
if (sequence == 0 && sequenceTmp >= 0) {
// sequence自增到最大了，時間戳自增1
startTimestamp += 1;
}
// 生成id
return allocate(startTimestamp - twepoch);
}
起始時間可以構造器裡指定，也可以用預設的，而
sequence
初始為-1，是為了不想浪費
sequence+1=0
這一序列号。
sequence = 0
排除掉初始
sequence=-1 +1 = 0
的情況就是
sequence
超過最大值了，此時時間戳
startTimestamp
自增。
代碼和思路都很簡單，就是完全脫離機器時鐘，徹底解決了時鐘回撥問題。顯而易見的優點，每一毫秒4096個序列号（
[0,4095]
）沒有浪費，同時因為時間自增由程式自己掌控，是以可以利用未來時間，預先生成一些ID放在緩存裡，外界從緩存中直接擷取ID，快消費完了再生産，這樣就形成了永動的生産-消費者模式，擷取ID省去了生成的過程，性能也會大大提升。
但是時間戳完全自控，也有很明顯的缺點，ID生成的時間，并不是真實的時間，如果流量較小，時間可能會滞後很多。如果對從ID解析出來的時間戳沒有什麼利用意義，這個缺點也不需要關心。
2、緩存曆史序列号緩解時鐘回撥問題
// 記錄近2S的毫秒數的sequence的緩存
private int LENGTH = 2000;
// sequence緩存
private long[] sequenceCycle = new long[LENGTH];
private synchronized long nextId() throws Exception {
long timestamp = timeGen();
int index = (int)(timestamp % LENGTH);
// 1、出現時鐘回撥問題，擷取曆史序列号自增
if (timestamp < lastTimestamp) {
long sequence = 0;
do {
if ((lastTimestamp - timestamp) > LENGTH) {
// 可自定義異常、告警等，短暫不能對外提供，故障轉移，将請求轉發到正常機器。
throw new UnsupportedOperationException("The timeback range is too large and exceeds 2000ms caches");
}
long preSequence = sequenceCycle[index];
sequence = (preSequence + 1) & SEQUENCE_MASK;
if (sequence == 0) {
// 如果取出的曆史序列号+1後已經達到超過最大值，
// 則重新擷取timestamp,重新拿其他位置的緩存
timestamp = tilNextMillis(lastTimestamp);
index = (int)(timestamp % LENGTH);
} else {
// 更新緩存
sequenceCycle[index] = this.sequence;
return allocate((timestamp - this.twepoch), sequence);
}
} while (timestamp < lastTimestamp);
// 如果在擷取緩存的過程中timestamp恢複正常了，就走正常流程
}
// 2、時間等于lastTimestamp，取目前的sequence + 1
if (timestamp == lastTimestamp) {
sequence = (sequence + 1) & SEQUENCE_MASK;
// Exceed the max sequence, we wait the next second to generate id
if (sequence == 0) {
timestamp = tilNextMillis(lastTimestamp);
index = (int)(timestamp % LENGTH);
}
} else {
// 3、時間大于lastTimestamp沒有發生回撥， sequence 從0開始
this.sequence = 0L;
}
// 緩存sequence + 更新lastTimestamp
sequenceCycle[index] = this.sequence;
lastTimestamp = timestamp;
// 生成id
return allocate(timestamp - this.twepoch);
}
這裡緩存了2000ms的序列号，如果發生時鐘回撥，且回撥範圍在2000ms内，就從緩存中取序列号自增，超過2000ms回撥，就抛異常，故障轉移，将請求配置設定到正常機器。
- 若擷取的曆史
sequence+1
sequence
- 極端情況下，擷取很多次緩存
sequence+1
- 在這個重新擷取的過程中，時鐘可能恢複正常了，則此時也要退出循環，走正常流程。
3、等待時鐘校正
private synchronized long nextId3() {
long timestamp = timeGen();
// 1、出現時鐘回撥問題，如果回撥幅度不大，等待時鐘自己校正
if (timestamp < lastTimestamp) {
int sleepCntMax = 2;
int sleepCnt = 0;
do {
long sleepTime = lastTimestamp - timestamp;
if (sleepCnt > sleepCntMax) {
// 可自定義異常類
throw new UnsupportedOperationException(String.format("Clock moved backwards. Refusing for %d seconds", sleepTime));
}
if (sleepTime <= 500) {
try {
Thread.sleep(sleepTime);
} catch (InterruptedException e) {
e.printStackTrace();
} finally {
sleepCnt++;
timestamp = tilNextMillis(lastTimestamp);
}
} else {
// 可自定義異常類
throw new UnsupportedOperationException(String.format("Clock moved backwards. Refusing for %d seconds", sleepTime));
}
} while (timestamp < lastTimestamp);
}
// 2、時間等于lastTimestamp，取目前的sequence + 1
if (timestamp == lastTimestamp) {
sequence = (sequence + 1) & SEQUENCE_MASK;
// Exceed the max sequence, we wait the next second to generate id
if (sequence == 0) {
timestamp = tilNextMillis(lastTimestamp);
}
} else {
// 3、時間大于lastTimestamp沒有發生回撥， sequence 從0開始
this.sequence = 0L;
}
lastTimestamp = timestamp;
// 生成id
return allocate(timestamp - this.twepoch);
}
等待時鐘自己校正來解決時鐘回撥問題，适用于回撥幅度小的場景。比如回撥時長小于500ms，那就睡眠500ms，等時間恢複到正常，如果這個過程中又發生了時鐘回撥，不可能一直等它校正，實際生産中可限定校正的次數，超過最大校正次數，那就抛異常吧，這屬于極端情況。
解決時鐘回撥問題的方法還有很多，無非就是避免和緩解。每種方式有各自的特點和适用場景，可以兩兩結合使用，比如時鐘回撥幅度小，就休眠校正，回撥幅度大或者出現多次回撥，也不抛異常，擷取緩存
sequence
對外提供服務。也可以當發生時鐘回撥時，用備用機器id生成ID等。
五、要點總結
- 生成全局唯一的分布式ID的方式有很多，常用的有資料庫号段算法和雪花算法，這兩個算法的實踐，大廠也有開源的項目，如百度的uid-generator、美團的Leaf、滴滴的TinyId等。
- 雪花算法的原理很簡單，主要由時間戳+機器id+序列号生成64bit的ID，整體趨勢遞增，且全局唯一，性能也不錯。每種組成辨別的bit都可以自定義，靈活性很高，如果需要更高的QPS，可以相對的把序列号bit調大一些。
- 因為雪花算法強依賴機器時鐘，就難以避免時鐘回撥問題，解決的方式很多，無非從避免和緩解兩個角度出發，常用的方式有，時間戳自增脫離機器時鐘依賴，利用緩存序列号，或者等待時鐘校正等，各有各的特點，正确利用其優點，才能最大提高性能。
- 雪花算法ID生成器的使用方式有兩種，一種是遠端發号器，需要做到高可用。另一種就是直接本地生成ID，省去了遠端請求過程，性能自然也是比遠端發号器高的，但是機器id用後即毀，需要配置設定足夠多的機器id。機器id的管理和配置設定可以利用
MySql
ZK
參考：
- Leaf——美團點評分布式ID生成系統
- http://www.cnblogs.com/relucent/p/4955340.html
- https://segmentfault.com/a/1190000011282426
- https://www.yuque.com/simonalong/butterfly/tul824
如若文章有錯誤了解，歡迎批評指正，同時非常期待你的評論、點贊和收藏。