1.背景
在我們的業(yè)務需求中通常有需要一些唯一的ID庶橱，來記錄我們某個數(shù)據(jù)的標識:
某個用戶的ID
某個訂單的單號
某個信息的ID
通常我們會調(diào)研各種各樣的生成策略，根據(jù)不同的業(yè)務贪惹，采取最合適的策略苏章，下面我會討論一下各種策略/算法，以及他們的一些優(yōu)劣點奏瞬。
2.UUID
UUID是通用唯一識別碼（Universally Unique Identifier)的縮寫枫绅，開放軟件基金會(OSF)規(guī)范定義了包括網(wǎng)卡MAC地址、時間戳硼端、名字空間（Namespace）并淋、隨機或偽隨機數(shù)、時序等元素珍昨。利用這些元素來生成UUID县耽。
UUID是由128位二進制組成句喷，一般轉換成十六進制，然后用String表示兔毙。在java中有個UUID類,在他的注釋中我們看見這里有4種不同的UUID的生成策略:
randomly: 基于隨機數(shù)生成UUID唾琼，由于Java中的隨機數(shù)是偽隨機數(shù)，其重復的概率是可以被計算出來的澎剥。這個一般我們用下面的代碼獲取基于隨機數(shù)的UUID:
time-based:基于時間的UUID,這個一般是通過當前時間锡溯，隨機數(shù)，和本地Mac地址來計算出來哑姚，自帶的JDK包并沒有這個算法的我們在一些UUIDUtil中祭饭，比如我們的log4j.core.util，會重新定義UUID的高位和低位蜻懦。
DCE security:DCE安全的UUID。
name-based：基于名字的UUID夕晓，通過計算名字和名字空間的MD5來計算UUID宛乃。
UUID的優(yōu)點:
通過本地生成，沒有經(jīng)過網(wǎng)絡I/O蒸辆，性能較快
無序征炼，無法預測他的生成順序。(當然這個也是他的缺點之一)
UUID的缺點:
128位二進制一般轉換成36位的16進制躬贡，太長了只能用String存儲谆奥，空間占用較多。
不能生成遞增有序的數(shù)字
適用場景:UUID的適用場景可以為不需要擔心過多的空間占用拂玻，以及不需要生成有遞增趨勢的數(shù)字酸些。在Log4j里面他在UuidPatternConverter中加入了UUID來標識每一條日志。
3.數(shù)據(jù)庫主鍵自增
大家對于唯一標識最容易想到的就是主鍵自增檐蚜，這個也是我們最常用的方法魄懂。例如我們有個訂單服務，那么把訂單id設置為主鍵自增即可闯第。
優(yōu)點:
簡單方便市栗，有序遞增，方便排序和分頁
缺點:
分庫分表會帶來問題咳短，需要進行改造填帽。
并發(fā)性能不高，受限于數(shù)據(jù)庫的性能咙好。
簡單遞增容易被其他人猜測利用篡腌，比如你有一個用戶服務用的遞增，那么其他人可以根據(jù)分析注冊的用戶ID來得到當天你的服務有多少人注冊勾效，從而就能猜測出你這個服務當前的一個大概狀況哀蘑。
數(shù)據(jù)庫宕機服務不可用诚卸。
適用場景: 根據(jù)上面可以總結出來，當數(shù)據(jù)量不多绘迁，并發(fā)性能不高的時候這個很適合合溺，比如一些to B的業(yè)務，商家注冊這些缀台，商家注冊和用戶注冊不是一個數(shù)量級的棠赛，所以可以數(shù)據(jù)庫主鍵遞增。如果對順序遞增強依賴膛腐，那么也可以使用數(shù)據(jù)庫主鍵自增睛约。
4.Redis
熟悉Redis的同學，應該知道在Redis中有兩個命令Incr哲身，IncrBy,因為Redis是單線程的所以能保證原子性辩涝。
優(yōu)點：
性能比數(shù)據(jù)庫好，能滿足有序遞增勘天。
缺點：
由于redis是內(nèi)存的KV數(shù)據(jù)庫怔揩，即使有AOF和RDB，但是依然會存在數(shù)據(jù)丟失脯丝，有可能會造成ID重復商膊。
依賴于redis，redis要是不穩(wěn)定宠进，會影響ID生成晕拆。
適用：由于其性能比數(shù)據(jù)庫好，但是有可能會出現(xiàn)ID重復和不穩(wěn)定材蹬，這一塊如果可以接受那么就可以使用实幕。也適用于到了某個時間，比如每天都刷新ID堤器，那么這個ID就需要重置茬缩，通過(Incr Today)，每天都會從0開始加吼旧。
5.Zookeeper
利用ZK的Znode數(shù)據(jù)版本如下面的代碼凰锡，每次都不獲取期望版本號也就是每次都會成功，那么每次都會返回最新的版本號:
Zookeeper這個方案用得較少圈暗，嚴重依賴Zookeeper集群掂为，并且性能不是很高，所以不予推薦员串。
6.數(shù)據(jù)庫分段+服務緩存ID
這個方法在美團的Leaf中有介紹勇哗，詳情可以參考美團技術團隊的發(fā)布的技術文章:Leaf——美團點評分布式ID生成系統(tǒng),這個方案是將數(shù)據(jù)庫主鍵自增進行優(yōu)化。
biz_tag代表每個不同的業(yè)務寸齐，max_id代表每個業(yè)務設置的大小欲诺，step代表每個proxyServer緩存的步長抄谐。 之前我們的每個服務都訪問的是數(shù)據(jù)庫，現(xiàn)在不需要扰法，每個服務直接和我們的ProxyServer做交互蛹含，減少了對數(shù)據(jù)庫的依賴。我們的每個ProxyServer回去數(shù)據(jù)庫中拿出步長的長度塞颁，比如server1拿到了1-1000,server2拿到來 1001-2000浦箱。如果用完會再次去數(shù)據(jù)庫中拿。
優(yōu)點:
比主鍵遞增性能高祠锣，能保證趨勢遞增酷窥。
如果DB宕機，proxServer由于有緩存依然可以堅持一段時間伴网。
缺點:
和主鍵遞增一樣蓬推，容易被人猜測。
DB宕機澡腾，雖然能支撐一段時間但是仍然會造成系統(tǒng)不可用沸伏。
適用場景:需要趨勢遞增，并且ID大小可控制的蛋铆，可以使用這套方案馋评。
當然這個方案也可以通過一些手段避免被人猜測放接，把ID變成是無序的刺啦，比如把我們生成的數(shù)據(jù)是一個遞增的long型，把這個Long分成幾個部分纠脾，比如可以分成幾組三位數(shù)玛瘸，幾組四位數(shù)，然后在建立一個映射表苟蹈，將我們的數(shù)據(jù)變成無序糊渊。
7.雪花算法-Snowflake
Snowflake是Twitter提出來的一個算法，其目的是生成一個64bit的整數(shù):
1bit:一般是符號位慧脱，不做處理
41bit:用來記錄時間戳渺绒，這里可以記錄69年，如果設置好起始時間比如今年是2018年菱鸥，那么可以用到2089年宗兼，到時候怎么辦？要是這個系統(tǒng)能用69年氮采，我相信這個系統(tǒng)早都重構了好多次了殷绍。
10bit:10bit用來記錄機器ID，總共可以記錄1024臺機器鹊漠，一般用前5位代表數(shù)據(jù)中心主到，后面5位是某個數(shù)據(jù)中心的機器ID
12bit:循環(huán)位茶行，用來對同一個毫秒之內(nèi)產(chǎn)生不同的ID，12位可以最多記錄4095個登钥，也就是在同一個機器同一毫秒最多記錄4095個畔师，多余的需要進行等待下毫秒。
上面只是一個將64bit劃分的標準怔鳖，當然也不一定這么做茉唉，可以根據(jù)不同業(yè)務的具體場景來劃分，比如下面給出一個業(yè)務場景：
服務目前QPS10萬结执，預計幾年之內(nèi)會發(fā)展到百萬度陆。
當前機器三地部署，上海献幔，北京懂傀，深圳都有。
當前機器10臺左右蜡感，預計未來會增加至百臺蹬蚁。
這個時候我們根據(jù)上面的場景可以再次合理的劃分62bit,QPS幾年之內(nèi)會發(fā)展到百萬，那么每毫秒就是千級的請求郑兴，目前10臺機器那么每臺機器承擔百級的請求犀斋，為了保證擴展，后面的循環(huán)位可以限制到1024情连，也就是2^10叽粹，那么循環(huán)位10位就足夠了。
機器三地部署我們可以用3bit總共8來表示機房位置却舀，當前的機器10臺虫几，為了保證擴展到百臺那么可以用7bit 128來表示，時間位依然是41bit,那么還剩下64-10-3-7-41-1 = 2bit,還剩下2bit可以用來進行擴展挽拔。
適用場景:當我們需要無序不能被猜測的ID辆脸，并且需要一定高性能，且需要long型螃诅，那么就可以使用我們雪花算法啡氢。比如常見的訂單ID，用雪花算法別人就無法猜測你每天的訂單量是多少术裸。
7.1一個簡單的Snowflake
public class IdWorker{
private long workerId;
private long datacenterId;
private long sequence = 0;
/**
* 2018/9/29日倘是，從此時開始計算，可以用到2089年
*/
private long twepoch = 1538211907857L;
private long workerIdBits = 5L;
private long datacenterIdBits = 5L;
private long sequenceBits = 12L;
private long workerIdShift = sequenceBits;
private long datacenterIdShift = sequenceBits + workerIdBits;
private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
// 得到0000000000000000000000000000000000000000000000000000111111111111
private long sequenceMask = -1L ^ (-1L << sequenceBits);
private long lastTimestamp = -1L;
public IdWorker(long workerId, long datacenterId){
this.workerId = workerId;
this.datacenterId = datacenterId;
}
public synchronized long nextId() {
long timestamp = timeGen();
//時間回撥穗椅，拋出異常
if (timestamp < lastTimestamp) {
System.err.printf("clock is moving backwards. Rejecting requests until %d.", lastTimestamp);
throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds",
lastTimestamp - timestamp));
}
if (lastTimestamp == timestamp) {
sequence = (sequence + 1) & sequenceMask;
if (sequence == 0) {
timestamp = tilNextMillis(lastTimestamp);
}
} else {
sequence = 0;
}
lastTimestamp = timestamp;
return ((timestamp - twepoch) << timestampLeftShift) |
(datacenterId << datacenterIdShift) |
(workerId << workerIdShift) |
sequence;
}
/**
* 當前ms已經(jīng)滿了
* @param lastTimestamp
* @return
*/
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 worker = new IdWorker(1,1);
for (int i = 0; i < 30; i++) {
System.out.println(worker.nextId());
}
}
}
復制代碼
上面定義了雪花算法的實現(xiàn)辨绊，在nextId中是我們生成雪花算法的關鍵。
7.2防止時鐘回撥
因為機器的原因會發(fā)生時間回撥匹表，我們的雪花算法是強依賴我們的時間的门坷，如果時間發(fā)生回撥宣鄙，有可能會生成重復的ID，在我們上面的nextId中我們用當前時間和上一次的時間進行判斷默蚌，如果當前時間小于上一次的時間那么肯定是發(fā)生了回撥冻晤，普通的算法會直接拋出異常,這里我們可以對其進行優(yōu)化,一般分為兩個情況:
如果時間回撥時間較短，比如配置5ms以內(nèi)绸吸，那么可以直接等待一定的時間鼻弧，讓機器的時間追上來。
如果時間的回撥時間較長锦茁，我們不能接受這么長的阻塞等待攘轩，那么又有兩個策略:
直接拒絕，拋出異常码俩，打日志度帮，通知RD時鐘回滾。
利用擴展位稿存，上面我們討論過不同業(yè)務場景位數(shù)可能用不到那么多笨篷，那么我們可以把擴展位數(shù)利用起來了，比如當這個時間回撥比較長的時候瓣履，我們可以不需要等待率翅，直接在擴展位加1。2位的擴展位允許我們有3次大的時鐘回撥袖迎，一般來說就夠了冕臭，如果其超過三次我們還是選擇拋出異常，打日志瓢棒。
通過上面的幾種策略可以比較的防護我們的時鐘回撥浴韭，防止出現(xiàn)回撥之后大量的異常出現(xiàn)丘喻。下面是修改之后的代碼脯宿，這里修改了時鐘回撥的邏輯:
最后
本文分析了各種生產(chǎn)分布式ID的算法的原理，以及他們的適用場景泉粉，相信你已經(jīng)能為自己的項目選擇好一個合適的分布式ID生成策略了连霉。沒有一個策略是完美的，只有適合自己的才是最好的嗡靡。
最后送波福利《搴常現(xiàn)在加群即可獲取Java工程化、高性能及分布式讨彼、高性能歉井、 高架構。性能調(diào)優(yōu)哈误、Spring哩至，MyBatis躏嚎，Netty源碼分析和大數(shù)據(jù)等多個知識 點高級進階干貨的直播免費學習權限及領取相關資料，群號：835638062 點 擊鏈接加入群聊【Java高級架構】：https://jq.qq.com/? _wv=1027&k=5S3kL3v
