知識星球本文主要基於真實踩坑經歷展開
-
1. 異常概述
-
2. 原因分析
-
2.1 Snowflake工作原理
-
2.2 問題定位
-
2.3 排除時鐘回撥
-
2.4 研究workerid
-
2.5 疑點
-
3. 解決方案
-
3.1 HostNameKeyGenerator
-
3.2 IPSectionKeyGenerator
-
3.3 使用我們團隊自研的全域性唯一ID服務
-
3.4 其他思路
-
4. 感謝
-
666. 彩蛋
友情提示：歡迎關註公眾號【芋道原始碼】。?關註後，拉你進【原始碼圈】微信群和【芋艿】搞基嗨皮。
友情提示：歡迎關註公眾號【芋道原始碼】。?關註後，拉你進【原始碼圈】微信群和【芋艿】】搞基嗨皮。
友情提示：歡迎關註公眾號【芋道原始碼】。?關註後，拉你進【原始碼圈】微信群和【芋艿】】搞基嗨皮。
1. 異常概述
2018年1月26日下午，業務方信貸小組的同學反饋服務執行資料庫插入操作出現異常，異常資訊顯示資料庫主鍵出現重覆：
在仔細分析了使用者的重覆主鍵ID、機器串列、雪花演演算法之後，下掉55這臺機器，至此，異常得以解除。
本次異常看似平常，然而仔細分析起來可能造成的後果比較嚴重。
（1）波及面廣、影響時間長。目前大量業務都採用了雪花演演算法的主鍵生成策略，如果業務、運維同學不瞭解雪花演演算法，會造成大量的時間分析排查此問題，造成一定的業務損失。
（2）存在潛在的隱患。雪花演演算法除了會產生此類Workid問題，也強依賴機器時鐘，如果機器上時鐘回撥，會導致發號重覆或者服務會處於不可用狀態。
2. 原因分析
為什麼會造成資料庫主鍵重覆呢？
要回答這個問題要先介紹一下作為主鍵生成策略主要演演算法之一的雪花演演算法的工作原理。
2.1 Snowflake工作原理
對於分散式的ID生成，以Twitter Snowflake為代表的， Flake 系列演演算法，屬於劃分名稱空間並行生成的一種演演算法，生成的資料為64bit的long型資料，在資料庫中應該用大於等於64bit的數字型別的欄位來儲存該值，比如在MySQL中應該使用BIGINT。
Twitter在2010年6月1日（在Flickr那篇文章釋出不到4個月之後），Ryan King 在Twitter的Blog 撰文 寫道：
-
Ticket Servers方案缺乏順序的保證
-
考慮過採用UUID，不過128-bit太長了
-
E也考慮過採用ZooKeeper所提供的 Unique Naming Seuence Nodes 所提供的 Unique Naming 特性，但是效能不能滿足。(Sequence Nodes的設計標的是解決分散式鎖的問題，但不解決效能要求極高的ID生成問題，直接應用是一種Hack行為)
在這種情況下，Twitter給出了 64-bit 長的 Snowflake ，它的結構是：
-
E1-bit reserved
-
E41-bit timestamp
-
E10-bit machine id
-
E12-bit sequence
在過了不到4年，2014年的5月31日，Twitter 更新了 Snowflake 的 README，其中陳述了兩個容易被忽視的事實:
“We have retired the initial release of Snowflake …”
“… heavily relies on existing infrastructure at Twitter to run. “
可以看出，這個方案所支援的最小劃分粒度是「毫秒 * 執行緒」，單執行緒（Snowflake 裡對應的概念是 Worker）的每秒容量是12-bit，也就是接近4096。
Snowflake的意義，不僅僅在於提供瞭解決方式，更多的是一種基於Long長度實現具有時間相關性的id自增序列。因此，很多公司基於它進行二次改造適應自己的場景。Snowflake家族的演演算法還有Instagram SnowFlake、Simpleflake、Boundary flake等等。
目前業界使用噹噹亮哥的sharding-jdbc，一般都會採取其內建的Snowflake演演算法，關於二次改造我這裡列舉一個58沈劍在《架構師之路》系列中提出的例子。
2.2 問題定位
收到業務方反饋以後，條件反射得第一時間連問了業務方同學三個問題：
-
你們的服務有沒有什麼特殊型的地方？
-
是重啟的時候發生的麼？
-
你能不能查一下對應重覆的記錄所在的機器，重覆是不是隻發生在這個ip段？
業務方也是第一時間給了反饋
-
就是普通的微服務，普通的機器
-
不是重啟時發生的
-
果然就是兩臺機器上出現了問題！
好了，那我就定位到了是workid出現了問題，馬上建議業務方下掉其中一臺。為什麼是workid,而不是時鐘回撥等其他原因，且聽我慢慢道來。
2.3 排除時鐘回撥
大家應該都知道雪花演演算法存在的缺點是：
-
依賴機器時鐘，如果機器時鐘回撥，會導致重覆ID生成
-
在單機上是遞增的，但是由於設計到分散式環境，每臺機器上的時鐘不可能完全同步，有時候會出現不是全域性遞增的情況（此缺點可以認為無所謂，一般分散式ID只要求趨勢遞增，並不會嚴格要求遞增～90%的需求都只要求趨勢遞增）
我們採用的是噹噹的sharding-jdbc 1.4.2這個版本（1.5之前的sj並不成熟，強烈推薦使用2.x），可以說直接使用了其com.dangdang.ddframe.rdb.sharding.id.generator.self.IPIdGenerator進行主鍵生成，其序列號生成採用的是com.dangdang.ddframe.rdb.sharding.id.generator.self.CommonSelfIdGenerator，這裡特別推薦讀者讀一下這兩個類前面的註釋，寫得非常清楚。
/**
* 根據機器IP獲取工作行程Id,如果線上機器的IP二進製表示的最後10位不重覆,建議使用此種方式
* ,列如機器的IP為192.168.1.108,二進製表示:11000000 10101000 00000001 01101100
* ,擷取最後10位 01 01101100,轉為十進位制364,設定workerId為364.
*
* @author DonneyYoung
*/
public class IPIdGenerator implements IdGenerator {
上面這段註釋非常有用，先貼在這裡，後面會詳細談到。
序列號生成採用的IPIdGenerator，噹噹的實現演演算法如下所示：
/**
* 自生成Id生成器.
*
*
* 長度為64bit,從高位到低位依次為
*
*
*
* 1bit 符號位
* 41bits 時間偏移量從2016年11月1日零點到現在的毫秒數
* 10bits 工作行程Id
* 12bits 同一個毫秒內的自增量
*
*
*
* 工作行程Id獲取優先順序: 系統變數{@code sjdbc.self.id.generator.worker.id} 大於 環境變數{@code SJDBC_SELF_ID_GENERATOR_WORKER_ID}
* ,另外可以呼叫@{@code CommonSelfIdGenerator.setWorkerId}進行設定
*
*
* @author gaohongtao
*/
@Getter
@Slf4j
public class CommonSelfIdGenerator implements IdGenerator {
public static final long SJDBC_EPOCH;//時間偏移量，從2016年11月1日零點開始
private static final long SEQUENCE_BITS = 12L;//自增量佔用位元
private static final long WORKER_ID_BITS = 10L;//工作行程ID位元
private static final long SEQUENCE_MASK = (1 << SEQUENCE_BITS) - 1;//自增量掩碼（最大值）
private static final long WORKER_ID_LEFT_SHIFT_BITS = SEQUENCE_BITS;//工作行程ID左移位元數（位數）
private static final long TIMESTAMP_LEFT_SHIFT_BITS = WORKER_ID_LEFT_SHIFT_BITS + WORKER_ID_BITS;//時間戳左移位元數（位數）
private static final long WORKER_ID_MAX_VALUE = 1L << WORKER_ID_BITS;//工作行程ID最大值
@Setter
private static AbstractClock clock = AbstractClock.systemClock();
@Getter
private static long workerId;//工作行程ID
static {
Calendar calendar = Calendar.getInstance();
calendar.set(2016, 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);
SJDBC_EPOCH = calendar.getTimeInMillis();
initWorkerId();
}
private long sequence;//最後自增量
private long lastTime;//最後生成編號時間戳，單位：毫秒
static void initWorkerId() {
String workerId = System.getProperty("sjdbc.self.id.generator.worker.id");
if (!Strings.isNullOrEmpty(workerId)) {
setWorkerId(Long.valueOf(workerId));
return;
}
workerId = System.getenv("SJDBC_SELF_ID_GENERATOR_WORKER_ID");
if (Strings.isNullOrEmpty(workerId)) {
return;
}
setWorkerId(Long.valueOf(workerId));
}
/**
* 設定工作行程Id.
*
* @param workerId 工作行程Id
*/
public static void setWorkerId(final Long workerId) {
Preconditions.checkArgument(workerId >= 0L && workerId < WORKER_ID_MAX_VALUE);
CommonSelfIdGenerator.workerId = workerId;
}
/**
* 生成Id.
*
* @return 傳回@{@link Long}型別的Id
*/
@Override
public synchronized Number generateId() {
//保證當前時間大於最後時間。時間回退會導致產生重覆id
long time = clock.millis();
Preconditions.checkState(lastTime <= time, "Clock is moving backwards, last time is %d milliseconds, current time is %d milliseconds", lastTime, time);
// 獲取序列號
if (lastTime == time) {
if (0L == (sequence = ++sequence & SEQUENCE_MASK)) {
time = waitUntilNextTime(time);
}
} else {
sequence = 0;
}
// 設定最後時間戳
lastTime = time;
if (log.isDebugEnabled()) {
log.debug("{}-{}-{}", new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS").format(new Date(lastTime)), workerId, sequence);
}
// 生成編號
return ((time - SJDBC_EPOCH) << TIMESTAMP_LEFT_SHIFT_BITS) | (workerId << WORKER_ID_LEFT_SHIFT_BITS) | sequence;
}
//不停獲得時間，直到大於最後時間
private long waitUntilNextTime(final long lastTime) {
long time = clock.millis();
while (time <= lastTime) {
time = clock.millis();
}
return time;
}
}透過這段程式碼可以看到噹噹的時鐘回撥在單機上是做了處理的了，不但會丟擲Clock is moving backwards balabalabala的IllegalStateException，而且也做了waitUntilNextTime一直等待的處理。如果單機是時鐘回撥，除非應用重啟或者回撥了時間，然而，線上伺服器執行得好好的，根本沒人動過，所以就不是單機時鐘回撥的問題。
再考慮是否是叢集回撥的情況，同樣，如果workerid不同出現重覆主鍵的機率基本不可能，並且我也仔細比對了出問題兩臺機器的時間基本保持一致，所以雖然我們公司的機器是漸進式時間管理（據說有些公司運維直接做了一個同步指令碼，如果時鐘不是指令碼同步，而是漸進同步的就可能會產生重覆ID），也不應該是大量出現此類問題的原因（使用者反饋給了我幾十個重覆主鍵ID）。
當然，這段程式碼還能收穫的一個資訊就是，debug樣式你可以看到你的workerId、sequence等等資訊，可是，線上執行，哪個系統會一一給你把主鍵ID打出來呢？線上雞肋，雞肋雞肋，食之無味，棄之有味。至於怎麼拿workId，請看下節。2.4 研究WorkId
如下圖所示，這就是我們全篇討論的雪花演演算法：
-
第一位元保留
-
時間戳，41位元，從2016年11月1日零點到現在的毫秒數,可以用到2156年，100多年後才會用完
-
機器id，10位元，這個機器id每個業務要唯一，機器id獲取的策略後面會詳述
-
序列號，12位元，每臺機器每毫秒最多產生4096個id，超過這個數的話會等到下一毫秒
我們細化2.3節中雪花演演算法的實現：
public synchronized Number generateId() {
long time = clock.millis();
Preconditions.checkState(lastTime <= time, "Clock is moving backwards, last time is %d milliseconds, current time is %d milliseconds", lastTime, time);
if (lastTime == time) {
if (0L == (sequence = ++sequence & SEQUENCE_MASK)) {
time = waitUntilNextTime(time);
}
} else {
sequence = 0;
}
lastTime = time;
if (log.isDebugEnabled()) {
log.debug("{}-{}-{}", new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS").format(new Date(lastTime)), workerId, sequence);
}
return ((time - SJDBC_EPOCH) << TIMESTAMP_LEFT_SHIFT_BITS) | (workerId << WORKER_ID_LEFT_SHIFT_BITS) | sequence;
}
-
TIMESTAMP_LEFT_SHIFT_BITS時間戳左移22位
-
WORKER_ID_LEFT_SHIFT_BITS工作機器ID左移動12位
-
最後12位序列號
進一步研究一下workid基於IPIdGenerator的實現
CommonSelfIdGenerator.setWorkerId((long) (((ipAddressByteArray[ipAddressByteArray.length - 2] & 0B11) << Byte.SIZE) + (ipAddressByteArray[ipAddressByteArray.length - 1] & 0xFF)));
可以很清楚得看到，這就是取ip的最後兩個段，一共取10bit，和我之前強調的註釋說得一模一樣
根據機器IP獲取工作行程Id,如果線上機器的IP二進製表示的最後10位不重覆,建議使用此種方式,列如機器的IP為192.168.1.108,二進製表示:11000000 10101000 00000001 01101100,擷取最後10位 01 01101100,轉為十進位制364,設定workerId為364.
然後把我們出問題的機器XXX.XXX.209.55，XXX.XXX.161.55(出於安全資料脫敏)轉化為workid，發現都是一樣的。
當然，你也可以使用下麵程式碼自己跑出workid。
@Test
public void generateId3() throws UnknownHostException, NoSuchFieldException, IllegalAccessException {
String ipv4s =
// "XXX.XXX.161.55\n"
"XXX.XXX.209.55\n"
// "XXX.XXX.209.126 \n" +
// "XXX.XXX.209.127\t\n" +
// "XXX.XXX.208.227 \n" +
// "XXX.XXX.148.134 \n" +
// "XXX.XXX.148.135\t\n" +
// "XXX.XXX.148.132\t\n" +
// "XXX.XXX.148.133";
;
for (String ipv4 : ipv4s.split("\n")) {
ipv4 = ipv4.replaceAll("\t", "").trim();
byte[] ipv4Byte = new byte[4];
String[] ipv4StingArray = ipv4.split("\\.");
for (int i = 0; i < 4; i++) {
ipv4Byte[i] = (byte) Integer.valueOf(ipv4StingArray[i]).intValue();
}
address = InetAddress.getByAddress("dangdang-db-sharding-dev-233", ipv4Byte);
PowerMockito.mockStatic(InetAddress.class);
PowerMockito.when(InetAddress.getLocalHost()).thenReturn(address);
IPKeyGenerator.initWorkerId();
// IPSectionKeyGenerator.initWorkerId();
Field workerIdField = DefaultKeyGenerator.class.getDeclaredField("workerId");
workerIdField.setAccessible(true);
System.out.println(ipv4 + "\t" + workerIdField.getLong(DefaultKeyGenerator.class));
}
}
另外我們也可以根據使用者提供的所有重覆的ID反解workerid
psvm+sout+(ID/4096%1024)
/4096的意思是整除2的12次方，變相干掉12bit序列號，%1024的意思是取2的十次方的餘數，拿到工作機器id
居然所有使用者的重覆ID反解出來的workerid都是一樣的。至此，我們可以得到結論，workerid重覆導致了線上主鍵重覆
2.5 疑點
但是上面的推測還有一個謎團沒有解開，就是隻有Workerid相同，41bit的時間戳和12bit的序列號怎麼可能碰撞那麼嚴重，兩天內出現了近百次衝突？如果說這個碰撞和hashmap的碰撞一樣，那麼也一定是高併發低機率的，為什麼會這麼頻繁？
所以，我又追問了業務方一個問題：
-
你們的併發度如何？
業務方給我的反饋是“併發量不大”。
我頓時明白了，翻了一下上面序列號生成的程式碼實現，該序列是用來在同一個毫秒內生成不同的Id，該Id順序遞增，如果在這個毫秒內生成的數量超過4096(2的12次方)，那麼生成器會等待到下個毫秒繼續生成。從Id的組成部分看，不同行程的Id肯定是不同的，同一個行程首先是透過時間位保證不重覆，如果時間相同則是透過序列位保證。 同時由於時間位是單調遞增的，且各個伺服器如果大體做了時間同步，那麼生成的Id在分散式環境可以認為是總體有序的。
透過
psvm+sout+(ID%4096)
驗證得知，所有重覆主鍵ID的序列號都是0，完全印證了我的猜想。
所以，因為序列號是從0開始遞增的，結論就是只要workerid相同，同時在這兩臺機器上出現請求，就會產生重覆，或者說只要線上IP末尾相同，就有可能會產生重覆！！！
3. 解決方案
運維下線了重覆的55一臺舊機器解決了此問題。瞭解到以前公司的機器IP都是連號的沒有出現這種並行的形式，這次是新老機器並存導致的。當然還有別的解決方案。
3.1 HostNameKeyGenerator
根據機器名最後的數字編號獲取工作行程編號。如果線上機器命名有統一規範,建議使用此種方式。例如，機器的 HostName 為: dangdang-db-sharding-dev-01(公司名-部門名-服務名-環境名-編號)，會擷取 HostName 最後的編號 01 作為工作行程編號( workId )。
3.2 IPSectionKeyGenerator
改進版本的IP生成策略。
瀏覽 IPKeyGenerator 工作行程編號生成的規則後，感覺對伺服器IP後10位（特別是IPV6）數值比較約束。
有以下最佳化思路：
因為工作行程編號最大限制是 2^10，我們生成的工程行程編號只要滿足小於 1024 即可。
1.針對IPV4:
….IP最大 255.255.255.255。而（255+255+255+255) < 1024。
….因此採用IP段數值相加即可生成唯一的workerId，不受IP位限制。
針對IPV6:
….IP最大 ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff
….為了保證相加生成出的工程行程編號 < 1024,思路是將每個 Bit 位的後6位相加。這樣在一定程度上也可以滿足workerId不重覆的問題。
使用這種 IP 生成工作行程編號的方法,必須保證IP段相加不能重覆
對於 IPV6 ：2^ 6 = 64。64 * 8 = 512 < 1024。
// IPSectionKeyGenerator.java
static void initWorkerId() {
InetAddress address;
try {
address = InetAddress.getLocalHost();
} catch (final UnknownHostException e) {
throw new IllegalStateException("Cannot get LocalHost InetAddress, please check your network!");
}
byte[] ipAddressByteArray = address.getAddress();
long workerId = 0L;
// IPV4
if (ipAddressByteArray.length == 4) {
for (byte byteNum : ipAddressByteArray) {
workerId += byteNum & 0xFF;
}
// IPV6
} else if (ipAddressByteArray.length == 16) {
for (byte byteNum : ipAddressByteArray) {
workerId += byteNum & 0B111111;
}
} else {
throw new IllegalStateException("Bad LocalHost InetAddress, please check your network!");
}
DefaultKeyGenerator.setWorkerId(workerId);
}
PS：此人的思路雖然巧妙，也不能絕對OK，例如，254.255和255.254會重覆，172.16.x.x，即使這個段，也是2的16次方，不過也能湊活得用，還是基於etcd或者zk發號靠譜。
或者只要公司機器編號準確，HostNameKeyGenerator也是非常靠譜的。
3.3 使用我們團隊自研的全域性唯一ID服務
做到的地方
-
高可用，短ID服務允許部署多套完全獨立的環境，每個環境產生的ID都不一樣，client可以failover到任何環境
-
高效能，每秒鐘可以獲取百萬級的ID，並且不會出現阻塞
-
基於時間的大致有序，基本上獲取到的ID會越來越大，無法保證嚴格有序，比如一小時前獲取的ID應該會比一小時後的小
-
一致性，絕對保證不會獲取到重覆的ID（服務端保證）
做不到的地方
-
無法保證嚴格全域性有序
-
無法保證按照時間有序
-
無法保證每個ID都不浪費
3.4 其他思路
-
美團開源的leaf在zookeeper協調雪花演演算法時鐘回撥，一直刷等回撥導致重覆的時候過去，其實在2017年閏秒的時候就出現過這個情況，leaf還是成功避免了。
-
還有一種避免回撥的方式是用1～2臺關閉NTP時鐘的機器做backup
-
百度的snakeflow是使用了預先分配id的方式來避免這種情況，雖然不能完全避免，其實預先分配是比較合理的方式
-
還有別的解決方案，重覆的時間後面可以增加版本號，做專門的校時伺服器，因為叢集獲取機器時間就會有時間視窗問題，造成生成的Id編號重覆
-
最好的方案還是老老實實使用資料庫生成的那種（資料庫號段生成的分散式ID），對業務影響不大就用snakeflow。因為InnoDB表的資料寫入順序能和B+樹索引的葉子節點順序一致的話，這時候存取效率是最高的，所以考慮主鍵的時候，一般需要自增、或者趨勢自增。
-
上文提到的基於host，其實也是一種不錯的解決方案
4. 感謝
這是公眾號「工匠小豬豬的技術世界」的第一篇文章，感謝「芋道原始碼」芋艿在技術、排版等方面給予的大力指導！
666. 彩蛋
第一篇 公眾號 的文章，如果有地方寫的不正確，還望指出，謝謝。
更多 分散式ID 內容，推薦閱讀如下文章：
-
美團 —— 《Leaf——美團點評分散式ID生成系統》
-
58 —— 《細聊分散式ID生成方法》
-
芋道原始碼 —— 《談談 ID》
-
王延炯博士 —— 《生成全域性唯一ID的3個思路，來自一個資深架構師的總結》
