開發(fā)四年只會寫業(yè)務(wù)代碼襟铭，分布式高并發(fā)都不會還想去BAT？>>>?

1.背景

在我們的業(yè)務(wù)需求中通常有需要一些唯一的ID，來記錄我們某個數(shù)據(jù)的標識:

某個用戶的ID

某個訂單的單號

某個信息的ID

通常我們會調(diào)研各種各樣的生成策略寒砖，根據(jù)不同的業(yè)務(wù)赐劣，采取最合適的策略，下面我會討論一下各種策略/算法哩都，以及他們的一些優(yōu)劣點魁兼。

2.UUID

UUID是通用唯一識別碼（Universally Unique Identifier)的縮寫，開放軟件基金會(OSF)規(guī)范定義了包括網(wǎng)卡MAC地址漠嵌、時間戳咐汞、名字空間（Namespace）、隨機或偽隨機數(shù)献雅、時序等元素碉考。利用這些元素來生成UUID。

UUID是由128位二進制組成挺身，一般轉(zhuǎn)換成十六進制侯谁，然后用String表示。在java中有個UUID類,在他的注釋中我們看見這里有4種不同的UUID的生成策略:

randomly: 基于隨機數(shù)生成UUID章钾，由于Java中的隨機數(shù)是偽隨機數(shù)墙贱，其重復(fù)的概率是可以被計算出來的。這個一般我們用下面的代碼獲取基于隨機數(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)絡(luò)I/O纵隔，性能較快

無序，無法預(yù)測他的生成順序炮姨。(當然這個也是他的缺點之一)

UUID的缺點:

128位二進制一般轉(zhuǎn)換成36位的16進制捌刮，太長了只能用String存儲，空間占用較多舒岸。

不能生成遞增有序的數(shù)字

適用場景:UUID的適用場景可以為不需要擔心過多的空間占用绅作，以及不需要生成有遞增趨勢的數(shù)字。在Log4j里面他在UuidPatternConverter中加入了UUID來標識每一條日志蛾派。

3.數(shù)據(jù)庫主鍵自增

大家對于唯一標識最容易想到的就是主鍵自增棚蓄，這個也是我們最常用的方法堕扶。例如我們有個訂單服務(wù)，那么把訂單id設(shè)置為主鍵自增即可梭依。

優(yōu)點:

簡單方便稍算，有序遞增，方便排序和分頁

缺點:

分庫分表會帶來問題役拴，需要進行改造糊探。

并發(fā)性能不高，受限于數(shù)據(jù)庫的性能河闰。

簡單遞增容易被其他人猜測利用科平，比如你有一個用戶服務(wù)用的遞增，那么其他人可以根據(jù)分析注冊的用戶ID來得到當天你的服務(wù)有多少人注冊姜性，從而就能猜測出你這個服務(wù)當前的一個大概狀況瞪慧。

數(shù)據(jù)庫宕機服務(wù)不可用。

適用場景: 根據(jù)上面可以總結(jié)出來部念，當數(shù)據(jù)量不多弃酌，并發(fā)性能不高的時候這個很適合，比如一些to B的業(yè)務(wù)儡炼，商家注冊這些妓湘，商家注冊和用戶注冊不是一個數(shù)量級的，所以可以數(shù)據(jù)庫主鍵遞增乌询。如果對順序遞增強依賴榜贴，那么也可以使用數(shù)據(jù)庫主鍵自增。

4.Redis

熟悉Redis的同學(xué)妹田，應(yīng)該知道在Redis中有兩個命令I(lǐng)ncr唬党，IncrBy,因為Redis是單線程的所以能保證原子性。

優(yōu)點：

性能比數(shù)據(jù)庫好鬼佣，能滿足有序遞增驶拱。

缺點：

由于redis是內(nèi)存的KV數(shù)據(jù)庫，即使有AOF和RDB沮趣，但是依然會存在數(shù)據(jù)丟失屯烦，有可能會造成ID重復(fù)坷随。

依賴于redis房铭，redis要是不穩(wěn)定，會影響ID生成温眉。

適用：由于其性能比數(shù)據(jù)庫好缸匪，但是有可能會出現(xiàn)ID重復(fù)和不穩(wěn)定，這一塊如果可以接受那么就可以使用类溢。也適用于到了某個時間凌蔬，比如每天都刷新ID露懒，那么這個ID就需要重置，通過(Incr Today)砂心，每天都會從0開始加懈词。

5.Zookeeper

利用ZK的Znode數(shù)據(jù)版本如下面的代碼，每次都不獲取期望版本號也就是每次都會成功辩诞，那么每次都會返回最新的版本號:

Zookeeper這個方案用得較少坎弯，嚴重依賴Zookeeper集群，并且性能不是很高译暂，所以不予推薦抠忘。

6.數(shù)據(jù)庫分段+服務(wù)緩存ID

這個方法在美團的Leaf中有介紹，詳情可以參考美團技術(shù)團隊的發(fā)布的技術(shù)文章:Leaf——美團點評分布式ID生成系統(tǒng),這個方案是將數(shù)據(jù)庫主鍵自增進行優(yōu)化外永。

biz_tag代表每個不同的業(yè)務(wù)播掷，max_id代表每個業(yè)務(wù)設(shè)置的大小州既，step代表每個proxyServer緩存的步長。 之前我們的每個服務(wù)都訪問的是數(shù)據(jù)庫，現(xiàn)在不需要口糕，每個服務(wù)直接和我們的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年孵运，如果設(shè)置好起始時間比如今年是2018年，那么可以用到2089年蔓彩，到時候怎么辦掐松？要是這個系統(tǒng)能用69年，我相信這個系統(tǒng)早都重構(gòu)了好多次了粪小。

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è)務(wù)的具體場景來劃分，比如下面給出一個業(yè)務(wù)場景：

服務(wù)目前QPS10萬姿骏，預(yù)計幾年之內(nèi)會發(fā)展到百萬糖声。

當前機器三地部署，上海分瘦，北京蘸泻，深圳都有。

當前機器10臺左右嘲玫，預(yù)計未來會增加至百臺悦施。

這個時候我們根據(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

publicclassIdWorker{privatelongworkerId;privatelongdatacenterId;privatelongsequence =0;/**

? ? * 2018/9/29日漆魔，從此時開始計算，可以用到2089年

? ? */privatelongtwepoch =1538211907857L;privatelongworkerIdBits =5L;privatelongdatacenterIdBits =5L;privatelongsequenceBits =12L;privatelongworkerIdShift = sequenceBits;privatelongdatacenterIdShift = sequenceBits + workerIdBits;privatelongtimestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;// 得到0000000000000000000000000000000000000000000000000000111111111111privatelongsequenceMask = -1L^ (-1L<< sequenceBits);privatelonglastTimestamp = -1L;publicIdWorker(longworkerId,longdatacenterId){this.workerId = workerId;this.datacenterId = datacenterId;? ? }publicsynchronizedlongnextId(){longtimestamp = timeGen();//時間回撥却音，拋出異常if(timestamp < lastTimestamp) {? ? ? ? ? ? System.err.printf("clock is moving backwards.? Rejecting requests until %d.", lastTimestamp);thrownewRuntimeException(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)滿了? ? *@paramlastTimestamp? ? *@return*/privatelongtilNextMillis(longlastTimestamp){longtimestamp = timeGen();while(timestamp <= lastTimestamp) {? ? ? ? ? ? timestamp = timeGen();? ? ? ? }returntimestamp;? ? }privatelongtimeGen(){returnSystem.currentTimeMillis();? ? }publicstaticvoidmain(String[] args){? ? ? ? IdWorker worker =newIdWorker(1,1);for(inti =0; i <30; i++) {? ? ? ? ? ? System.out.println(worker.nextId());? ? ? ? }? ? }}

上面定義了雪花算法的實現(xiàn)改抡，在nextId中是我們生成雪花算法的關(guān)鍵。

7.2防止時鐘回撥

因為機器的原因會發(fā)生時間回撥系瓢，我們的雪花算法是強依賴我們的時間的阿纤，如果時間發(fā)生回撥，有可能會生成重復(fù)的ID夷陋，在我們上面的nextId中我們用當前時間和上一次的時間進行判斷欠拾，如果當前時間小于上一次的時間那么肯定是發(fā)生了回撥，普通的算法會直接拋出異常,這里我們可以對其進行優(yōu)化,一般分為兩個情況:

如果時間回撥時間較短骗绕，比如配置5ms以內(nèi)藐窄，那么可以直接等待一定的時間，讓機器的時間追上來酬土。

如果時間的回撥時間較長荆忍，我們不能接受這么長的阻塞等待，那么又有兩個策略:

直接拒絕撤缴，拋出異常东揣，打日志，通知RD時鐘回滾腹泌。

利用擴展位嘶卧，上面我們討論過不同業(yè)務(wù)場景位數(shù)可能用不到那么多，那么我們可以把擴展位數(shù)利用起來了凉袱，比如當這個時間回撥比較長的時候芥吟，我們可以不需要等待，直接在擴展位加1专甩。2位的擴展位允許我們有3次大的時鐘回撥钟鸵，一般來說就夠了，如果其超過三次我們還是選擇拋出異常涤躲，打日志棺耍。

通過上面的幾種策略可以比較的防護我們的時鐘回撥，防止出現(xiàn)回撥之后大量的異常出現(xiàn)种樱。下面是修改之后的代碼蒙袍，這里修改了時鐘回撥的邏輯:

最后

本文分析了各種生產(chǎn)分布式ID的算法的原理俊卤，以及他們的適用場景，相信你已經(jīng)能為自己的項目選擇好一個合適的分布式ID生成策略了害幅。沒有一個策略是完美的消恍，只有適合自己的才是最好的。

這篇文章被我收錄于JGrowing以现，一個全面狠怨，優(yōu)秀，由社區(qū)一起共建的Java學(xué)習(xí)路線邑遏，如果您想?yún)⑴c開源項目的維護佣赖，可以一起共建，github地址為:https://github.com/javagrowing/JGrowing?麻煩給個小星星喲记盒。

最后打個廣告茵汰，如果你覺得這篇文章對你有文章，可以關(guān)注我的技術(shù)公眾號孽鸡，也可以加入我的技術(shù)交流群進行更多的技術(shù)交流蹂午。最近作者收集了很多最新的學(xué)習(xí)資料視頻以及面試資料，關(guān)注之后即可領(lǐng)取彬碱，你的關(guān)注和轉(zhuǎn)發(fā)是對我最大的支持豆胸，O(∩_∩)O。