原生實現(xiàn)
本文承接sharding-jdbc源碼之分布式ID苇倡，在這篇文章中詳細介紹了sharding-jdbc的分布式ID是如何實現(xiàn)的；很遺憾的是sharding-jdbc只是基于snowflake算法實現(xiàn)了如何生成分布式ID囤踩，并沒有解決snowflake算法的缺點：
- 時鐘回撥問題旨椒；
- 趨勢遞增，而不是絕對遞增堵漱；
- 不能在一臺服務器上部署多個分布式ID服務综慎；
第2點算不上缺點，畢竟如果絕對遞增的話怔锌，需要犧牲不少的性能寥粹；第3點也算不上缺點变过，即使一臺足夠大內(nèi)存的服務器，在部署一個分布式ID服務后涝涤，還有很多可用的內(nèi)存媚狰，可以用來部署其他的服務，不一定非得在一臺服務器上部署一個服務的多個實例阔拳；可以參考elasticsearch的主分片和副本的劃分規(guī)則：某個主分片的副本是不允許和主分片在同一臺節(jié)點上--因為這樣意思不大崭孤，如果這個分片只擁有一個副本，且這個節(jié)點宕機后糊肠，服務狀態(tài)就是"RED"辨宠；
所以這篇文章的主要目的是解決第1個缺點：時鐘回撥問題；先來看一下sharding-jdbc的DefaultKeyGenerator.java中generateKey()方法的源碼：
@Override
public synchronized Number generateKey() {
long currentMillis = timeService.getCurrentMillis();
Preconditions.checkState(lastTime <= currentMillis, "Clock is moving backwards, last time is %d milliseconds, current time is %d milliseconds", lastTime, currentMillis);
if (lastTime == currentMillis) {
if (0L == (sequence = ++sequence & SEQUENCE_MASK)) {
currentMillis = waitUntilNextTime(currentMillis);
}
} else {
sequence = 0;
}
lastTime = currentMillis;
if (log.isDebugEnabled()) {
log.debug("{}-{}-{}", new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS").format(new Date(lastTime)), workerId, sequence);
}
return ((currentMillis - EPOCH) << TIMESTAMP_LEFT_SHIFT_BITS) | (workerId << WORKER_ID_LEFT_SHIFT_BITS) | sequence;
}
說明：從這段代碼可知货裹，sharding-jdbc并沒有嘗試去解決snowflake算法時鐘回撥的問題嗤形，只是簡單判斷如果
lastTime <= currentMillis不滿足就拋出異常：Preconditions.checkState(lastTime <= currentMillis, "Clock is moving backwards, last time is %d milliseconds, current time is %d milliseconds", lastTime, currentMillis);
改進思路
snowflake算法一個很大的優(yōu)點就是不需要依賴任何第三方組件，筆者想繼續(xù)保留這個優(yōu)點：畢竟多一個依賴的組件弧圆，多一個風險赋兵，并增加了系統(tǒng)的復雜性。
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船庇，以此類推……
說明：如果你的業(yè)務真的需要512個以上分布式ID服務才能滿足需求吭产，那么不需要繼續(xù)往下看了，這個方案不適合你^^溢十；
改進實現(xiàn)
對generateKey()方法的改進如下：
// 修改處: workerId原則上上限為1024, 但是為了每臺sequence服務預留一個workerId, 所以實際上workerId上限為512
private static final long WORKER_ID_MAX_VALUE = 1L << WORKER_ID_BITS >> 1;
/**
* 保留workerId和lastTime, 以及備用workerId和其對應的lastTime
*/
private static Map<Long, Long> workerIdLastTimeMap = new ConcurrentHashMap<>();
/**
* Generate key. 考慮時鐘回撥, 與sharding-jdbc源碼的區(qū)別就在這里</br>
* 缺陷: 如果連續(xù)兩次時鐘回撥, 可能還是會有問題, 但是這種概率極低極低
* @return key type is @{@link Long}.
* @Author 阿飛
*/
@Override
public synchronized Number generateKey() {
long currentMillis = System.currentTimeMillis();
// 當發(fā)生時鐘回撥時
if (lastTime > currentMillis){
// 如果時鐘回撥在可接受范圍內(nèi), 等待即可
if (lastTime - currentMillis < MAX_BACKWARD_MS){
try {
Thread.sleep(lastTime - currentMillis);
} catch (InterruptedException e) {
e.printStackTrace();
}
}else {
// 如果時鐘回撥太多, 那么換備用workerId嘗試
// 當前workerId和備用workerId的值的差值為512
long interval = 512L;
// 發(fā)生時鐘回撥時, 計算備用workerId[如果當前workerId小于512,
// 那么備用workerId=workerId+512; 否則備用workerId=workerId-512, 兩個workerId輪換用]
if (MyKeyGenerator.workerId >= interval) {
MyKeyGenerator.workerId = MyKeyGenerator.workerId - interval;
} else {
MyKeyGenerator.workerId = MyKeyGenerator.workerId + interval;
}
// 取得備用workerId的lastTime
Long tempTime = workerIdLastTimeMap.get(MyKeyGenerator.workerId);
lastTime = tempTime==null?0L:tempTime;
// 如果在備用workerId也處于過去的時鐘, 那么拋出異常
// [這里也可以增加時鐘回撥是否超過MAX_BACKWARD_MS的判斷]
Preconditions.checkState(lastTime <= currentMillis, "Clock is moving backwards, last time is %d milliseconds, current time is %d milliseconds", lastTime, currentMillis);
// 備用workerId上也處于時鐘回撥范圍內(nèi)的邏輯還可以優(yōu)化: 比如摘掉當前節(jié)點. 運維通過監(jiān)控發(fā)現(xiàn)問題并修復時鐘回撥
}
}
// 如果和最后一次請求處于同一毫秒, 那么sequence+1
if (lastTime == currentMillis) {
if (0L == (sequence = ++sequence & SEQUENCE_MASK)) {
currentMillis = waitUntilNextTime(currentMillis);
}
} else {
// 如果是一個更近的時間戳, 那么sequence歸零
sequence = 0;
}
lastTime = currentMillis;
// 更新map中保存的workerId對應的lastTime
workerIdLastTimeMap.put(MyKeyGenerator.workerId, lastTime);
if (log.isDebugEnabled()) {
log.debug("{}-{}-{}", new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS").format(new Date(lastTime)), workerId, sequence);
}
System.out.println(new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS").format(new Date(lastTime))
+" -- "+workerId+" -- "+sequence+" -- "+workerIdLastTimeMap);
return ((currentMillis - EPOCH) << TIMESTAMP_LEFT_SHIFT_BITS) | (workerId << WORKER_ID_LEFT_SHIFT_BITS) | sequence;
}
改進驗證
Powered By 阿飛Javaer.png
第一個紅色箭頭的地方通過修改本地時間垮刹，通過啟動了備用workerId從而避免了時鐘回撥60s（window系統(tǒng)直接修改系統(tǒng)時間模擬）引起的問題；第二個紅色箭頭在60s內(nèi)再次模擬時鐘回撥张弛，就會有問題荒典，因為無論是workerId還是備用workerId都會有沖突；如果第二紅色箭頭是60s后模擬時鐘回撥吞鸭，依然可以避免問題寺董，原因嘛，你懂得刻剥；
再次優(yōu)化
每個workerId可以配置任意個備用workerId遮咖，由使用者去平衡sequence服務的性能及高可用，終極版代碼如下：
public final class MyKeyGenerator implements KeyGenerator {
private static final long EPOCH;
private static final long SEQUENCE_BITS = 12L;
private static final long WORKER_ID_BITS = 10L;
private static final long SEQUENCE_MASK = (1 << SEQUENCE_BITS) - 1;
private static final long WORKER_ID_LEFT_SHIFT_BITS = SEQUENCE_BITS;
private static final long TIMESTAMP_LEFT_SHIFT_BITS = WORKER_ID_LEFT_SHIFT_BITS + WORKER_ID_BITS;
/**
* 每臺workerId服務器有3個備份workerId, 備份workerId數(shù)量越多, 可靠性越高, 但是可部署的sequence ID服務越少
*/
private static final long BACKUP_COUNT = 3;
/**
* 實際的最大workerId的值<br/>
* workerId原則上上限為1024, 但是需要為每臺sequence服務預留BACKUP_AMOUNT個workerId,
*/
private static final long WORKER_ID_MAX_VALUE = (1L << WORKER_ID_BITS) / (BACKUP_COUNT + 1);
/**
* 目前用戶生成ID的workerId
*/
private static long workerId;
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是服務器第一次上線時間點, 設(shè)置后不允許修改
EPOCH = calendar.getTimeInMillis();
}
private long sequence;
private long lastTime;
/**
* 保留workerId和lastTime, 以及備用workerId和其對應的lastTime
*/
private static Map<Long, Long> workerIdLastTimeMap = new ConcurrentHashMap<>();
static {
// 初始化workerId和其所有備份workerId與lastTime
// 假設(shè)workerId為0且BACKUP_AMOUNT為4, 那么map的值為: {0:0L, 256:0L, 512:0L, 768:0L}
// 假設(shè)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 * WORKER_ID_MAX_VALUE), 0L);
}
System.out.println("workerIdLastTimeMap:" + workerIdLastTimeMap);
}
/**
* 最大容忍時間, 單位毫秒, 即如果時鐘只是回撥了該變量指定的時間, 那么等待相應的時間即可;
* 考慮到sequence服務的高性能, 這個值不易過大
*/
private static final long MAX_BACKWARD_MS = 3;
/**
* Set work process id.
* @param workerId work process id
*/
public static void setWorkerId(final long workerId) {
Preconditions.checkArgument(workerId >= 0L && workerId < WORKER_ID_MAX_VALUE);
MyKeyGenerator.workerId = workerId;
}
/**
* Generate key. 考慮時鐘回撥, 與sharding-jdbc源碼的區(qū)別就在這里</br>
* 缺陷: 如果連續(xù)兩次時鐘回撥, 可能還是會有問題, 但是這種概率極低極低
* @return key type is @{@link Long}.
* @Author 阿飛
*/
@Override
public synchronized Number generateKey() {
long currentMillis = System.currentTimeMillis();
// 當發(fā)生時鐘回撥時
if (lastTime > currentMillis){
// 如果時鐘回撥在可接受范圍內(nèi), 等待即可
if (lastTime - currentMillis < MAX_BACKWARD_MS){
try {
Thread.sleep(lastTime - currentMillis);
} catch (InterruptedException e) {
e.printStackTrace();
}
}else {
tryGenerateKeyOnBackup(currentMillis);
}
}
// 如果和最后一次請求處于同一毫秒, 那么sequence+1
if (lastTime == currentMillis) {
if (0L == (sequence = ++sequence & SEQUENCE_MASK)) {
currentMillis = waitUntilNextTime(currentMillis);
}
} else {
// 如果是一個更近的時間戳, 那么sequence歸零
sequence = 0;
}
lastTime = currentMillis;
// 更新map中保存的workerId對應的lastTime
workerIdLastTimeMap.put(MyKeyGenerator.workerId, lastTime);
if (log.isDebugEnabled()) {
log.debug("{}-{}-{}", new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS").format(new Date(lastTime)), workerId, sequence);
}
System.out.println(new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS").format(new Date(lastTime))
+" -- "+workerId+" -- "+sequence+" -- "+workerIdLastTimeMap);
return ((currentMillis - EPOCH) << TIMESTAMP_LEFT_SHIFT_BITS) | (workerId << WORKER_ID_LEFT_SHIFT_BITS) | sequence;
}
/**
* 嘗試在workerId的備份workerId上生成
* @param currentMillis 當前時間
*/
private long tryGenerateKeyOnBackup(long currentMillis){
System.out.println("try GenerateKey OnBackup, map:" + workerIdLastTimeMap);
// 遍歷所有workerId(包括備用workerId, 查看哪些workerId可用)
for (Map.Entry<Long, Long> entry:workerIdLastTimeMap.entrySet()){
MyKeyGenerator.workerId = entry.getKey();
// 取得備用workerId的lastTime
Long tempLastTime = entry.getValue();
lastTime = tempLastTime==null?0L:tempLastTime;
// 如果找到了合適的workerId
if (lastTime<=currentMillis){
return lastTime;
}
}
// 如果所有workerId以及備用workerId都處于時鐘回撥, 那么拋出異常
throw new IllegalStateException("Clock is moving backwards, current time is "
+currentMillis+" milliseconds, workerId map = " + workerIdLastTimeMap);
}
private long waitUntilNextTime(final long lastTime) {
long time = System.currentTimeMillis();
while (time <= lastTime) {
time = System.currentTimeMillis();
}
return time;
}
}
核心優(yōu)化代碼在方法
tryGenerateKeyOnBackup()中造虏，BACKUP_COUNT即備份workerId數(shù)越多御吞，sequence服務避免時鐘回撥影響的能力越強麦箍，但是可部署的sequence服務越少，設(shè)置BACKUP_COUNT為3陶珠，最多可以部署1024/(3+1)即256個sequence服務挟裂，完全夠用，抗時鐘回撥影響的能力也得到非常大的保障揍诽。
改進總結(jié)
這種改進方案最大優(yōu)點就是沒有引入任何第三方中間件（例如redis诀蓉，zookeeper等），但是避免時鐘回撥能力得到極大的提高暑脆，而且時鐘回撥本來就是極小概率渠啤。阿飛Javaer認為這種方案能夠達到絕大部分sequence服務的需求了；
