一、前言
在日趨復雜的分布式系統中，數據量越來越大，數據庫分庫分表是一貫的垂直水平做法，但是需要一個全局唯一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
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-11this.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 + 1if (timestamp == lastTimestamp) {sequence = (sequence + 1) & SEQUENCE_MASK;// Exceed the max sequence, we wait the next second to generate idif (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、時間戳自增徹底解決時鐘回撥問題
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自增到最大了，時間戳自增1startTimestamp += 1;}// 生成idreturn allocate(startTimestamp - twepoch);
}
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 + 1if (timestamp == lastTimestamp) {sequence = (sequence + 1) & SEQUENCE_MASK;// Exceed the max sequence, we wait the next second to generate idif (sequence == 0) {timestamp = tilNextMillis(lastTimestamp);index = (int)(timestamp % LENGTH);}} else {// 3、時間大于lastTimestamp沒有發生回撥， sequence 從0開始this.sequence = 0L;}// 緩存sequence + 更新lastTimestampsequenceCycle[index] = this.sequence;lastTimestamp = timestamp;// 生成idreturn allocate(timestamp - this.twepoch);
}
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 + 1if (timestamp == lastTimestamp) {sequence = (sequence + 1) & SEQUENCE_MASK;// Exceed the max sequence, we wait the next second to generate idif (sequence == 0) {timestamp = tilNextMillis(lastTimestamp);}} else {// 3、時間大于lastTimestamp沒有發生回撥， sequence 從0開始this.sequence = 0L;}lastTimestamp = timestamp;// 生成idreturn allocate(timestamp - this.twepoch);
}
![面試經典150題[001]：合并兩個有序數組（LeetCode 88）](http://pic.xiahunao.cn/面試經典150題[001]：合并兩個有序數組（LeetCode 88）)
—Dubbo Consumer接收服務調用響應)
知識補充——場景切換、退出游戲、鼠標隱藏鎖定、隨機數、委托)
