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

1.背景

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

某個(gè)用戶的ID

某個(gè)訂單的單號(hào)

某個(gè)信息的ID

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

2.UUID

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

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

randomly: 基于隨機(jī)數(shù)生成UUID，由于Java中的隨機(jī)數(shù)是偽隨機(jī)數(shù)，其重復(fù)的概率是可以被計(jì)算出來(lái)的。這個(gè)一般我們用下面的代碼獲取基于隨機(jī)數(shù)的UUID:?

time-based:基于時(shí)間的UUID,這個(gè)一般是通過當(dāng)前時(shí)間，隨機(jī)數(shù)，和本地Mac地址來(lái)計(jì)算出來(lái)，自帶的JDK包并沒有這個(gè)算法的我們?cè)谝恍︰UIDUtil中，比如我們的log4j.core.util，會(huì)重新定義UUID的高位和低位。?

DCE security:DCE安全的UUID。

name-based：基于名字的UUID，通過計(jì)算名字和名字空間的MD5來(lái)計(jì)算UUID。

UUID的優(yōu)點(diǎn):

通過本地生成，沒有經(jīng)過網(wǎng)絡(luò)I/O，性能較快

無(wú)序，無(wú)法預(yù)測(cè)他的生成順序。(當(dāng)然這個(gè)也是他的缺點(diǎn)之一)

UUID的缺點(diǎn):

128位二進(jìn)制一般轉(zhuǎn)換成36位的16進(jìn)制，太長(zhǎng)了只能用String存儲(chǔ)，空間占用較多。

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

適用場(chǎng)景:UUID的適用場(chǎng)景可以為不需要擔(dān)心過多的空間占用，以及不需要生成有遞增趨勢(shì)的數(shù)字。在Log4j里面他在UuidPatternConverter中加入了UUID來(lái)標(biāo)識(shí)每一條日志。

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

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

優(yōu)點(diǎn):

簡(jiǎn)單方便，有序遞增，方便排序和分頁(yè)

缺點(diǎn):

分庫(kù)分表會(huì)帶來(lái)問題，需要進(jìn)行改造。

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

簡(jiǎn)單遞增容易被其他人猜測(cè)利用，比如你有一個(gè)用戶服務(wù)用的遞增，那么其他人可以根據(jù)分析注冊(cè)的用戶ID來(lái)得到當(dāng)天你的服務(wù)有多少人注冊(cè)，從而就能猜測(cè)出你這個(gè)服務(wù)當(dāng)前的一個(gè)大概狀況。

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

適用場(chǎng)景: 根據(jù)上面可以總結(jié)出來(lái)，當(dāng)數(shù)據(jù)量不多，并發(fā)性能不高的時(shí)候這個(gè)很適合，比如一些to B的業(yè)務(wù)，商家注冊(cè)這些，商家注冊(cè)和用戶注冊(cè)不是一個(gè)數(shù)量級(jí)的，所以可以數(shù)據(jù)庫(kù)主鍵遞增。如果對(duì)順序遞增強(qiáng)依賴，那么也可以使用數(shù)據(jù)庫(kù)主鍵自增。

4.Redis

熟悉Redis的同學(xué)，應(yīng)該知道在Redis中有兩個(gè)命令I(lǐng)ncr，IncrBy,因?yàn)镽edis是單線程的所以能保證原子性。

優(yōu)點(diǎn)：

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

缺點(diǎn)：

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

依賴于redis，redis要是不穩(wěn)定，會(huì)影響ID生成。

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

5.Zookeeper

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

Zookeeper這個(gè)方案用得較少，嚴(yán)重依賴Zookeeper集群，并且性能不是很高，所以不予推薦。

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

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

biz_tag代表每個(gè)不同的業(yè)務(wù)，max_id代表每個(gè)業(yè)務(wù)設(shè)置的大小，step代表每個(gè)proxyServer緩存的步長(zhǎng)。 之前我們的每個(gè)服務(wù)都訪問的是數(shù)據(jù)庫(kù)，現(xiàn)在不需要，每個(gè)服務(wù)直接和我們的ProxyServer做交互，減少了對(duì)數(shù)據(jù)庫(kù)的依賴。我們的每個(gè)ProxyServer回去數(shù)據(jù)庫(kù)中拿出步長(zhǎng)的長(zhǎng)度，比如server1拿到了1-1000,server2拿到來(lái) 1001-2000。如果用完會(huì)再次去數(shù)據(jù)庫(kù)中拿。

優(yōu)點(diǎn):

比主鍵遞增性能高，能保證趨勢(shì)遞增。

如果DB宕機(jī)，proxServer由于有緩存依然可以堅(jiān)持一段時(shí)間。

缺點(diǎn):

和主鍵遞增一樣，容易被人猜測(cè)。

DB宕機(jī)，雖然能支撐一段時(shí)間但是仍然會(huì)造成系統(tǒng)不可用。

適用場(chǎng)景:需要趨勢(shì)遞增，并且ID大小可控制的，可以使用這套方案。

當(dāng)然這個(gè)方案也可以通過一些手段避免被人猜測(cè)，把ID變成是無(wú)序的，比如把我們生成的數(shù)據(jù)是一個(gè)遞增的long型，把這個(gè)Long分成幾個(gè)部分，比如可以分成幾組三位數(shù)，幾組四位數(shù)，然后在建立一個(gè)映射表，將我們的數(shù)據(jù)變成無(wú)序。

7.雪花算法-Snowflake

Snowflake是Twitter提出來(lái)的一個(gè)算法，其目的是生成一個(gè)64bit的整數(shù):

1bit:一般是符號(hào)位，不做處理

41bit:用來(lái)記錄時(shí)間戳，這里可以記錄69年，如果設(shè)置好起始時(shí)間比如今年是2018年，那么可以用到2089年，到時(shí)候怎么辦？要是這個(gè)系統(tǒng)能用69年，我相信這個(gè)系統(tǒng)早都重構(gòu)了好多次了。

10bit:10bit用來(lái)記錄機(jī)器ID，總共可以記錄1024臺(tái)機(jī)器，一般用前5位代表數(shù)據(jù)中心，后面5位是某個(gè)數(shù)據(jù)中心的機(jī)器ID

12bit:循環(huán)位，用來(lái)對(duì)同一個(gè)毫秒之內(nèi)產(chǎn)生不同的ID，12位可以最多記錄4095個(gè)，也就是在同一個(gè)機(jī)器同一毫秒最多記錄4095個(gè)，多余的需要進(jìn)行等待下毫秒。

上面只是一個(gè)將64bit劃分的標(biāo)準(zhǔn)，當(dāng)然也不一定這么做，可以根據(jù)不同業(yè)務(wù)的具體場(chǎng)景來(lái)劃分，比如下面給出一個(gè)業(yè)務(wù)場(chǎng)景：

服務(wù)目前QPS10萬(wàn)，預(yù)計(jì)幾年之內(nèi)會(huì)發(fā)展到百萬(wàn)。

當(dāng)前機(jī)器三地部署，上海，北京，深圳都有。

當(dāng)前機(jī)器10臺(tái)左右，預(yù)計(jì)未來(lái)會(huì)增加至百臺(tái)。

這個(gè)時(shí)候我們根據(jù)上面的場(chǎng)景可以再次合理的劃分62bit,QPS幾年之內(nèi)會(huì)發(fā)展到百萬(wàn)，那么每毫秒就是千級(jí)的請(qǐng)求，目前10臺(tái)機(jī)器那么每臺(tái)機(jī)器承擔(dān)百級(jí)的請(qǐng)求，為了保證擴(kuò)展，后面的循環(huán)位可以限制到1024，也就是2^10，那么循環(huán)位10位就足夠了。

機(jī)器三地部署我們可以用3bit總共8來(lái)表示機(jī)房位置，當(dāng)前的機(jī)器10臺(tái)，為了保證擴(kuò)展到百臺(tái)那么可以用7bit 128來(lái)表示，時(shí)間位依然是41bit,那么還剩下64-10-3-7-41-1 = 2bit,還剩下2bit可以用來(lái)進(jìn)行擴(kuò)展。

適用場(chǎng)景:當(dāng)我們需要無(wú)序不能被猜測(cè)的ID，并且需要一定高性能，且需要long型，那么就可以使用我們雪花算法。比如常見的訂單ID，用雪花算法別人就無(wú)法猜測(cè)你每天的訂單量是多少。

7.1一個(gè)簡(jiǎn)單的Snowflake

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

? ? * 2018/9/29日，從此時(shí)開始計(jì)算，可以用到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();//時(shí)間回?fù)?，拋出異常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;? ? }/**? ? * 當(dāng)前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());? ? ? ? }? ? }}

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

7.2防止時(shí)鐘回?fù)?/p>

因?yàn)闄C(jī)器的原因會(huì)發(fā)生時(shí)間回?fù)?，我們的雪花算法是?qiáng)依賴我們的時(shí)間的，如果時(shí)間發(fā)生回?fù)?，有可能?huì)生成重復(fù)的ID，在我們上面的nextId中我們用當(dāng)前時(shí)間和上一次的時(shí)間進(jìn)行判斷，如果當(dāng)前時(shí)間小于上一次的時(shí)間那么肯定是發(fā)生了回?fù)?，普通的算法?huì)直接拋出異常,這里我們可以對(duì)其進(jìn)行優(yōu)化,一般分為兩個(gè)情況:

如果時(shí)間回?fù)軙r(shí)間較短，比如配置5ms以內(nèi)，那么可以直接等待一定的時(shí)間，讓機(jī)器的時(shí)間追上來(lái)。

如果時(shí)間的回?fù)軙r(shí)間較長(zhǎng)，我們不能接受這么長(zhǎng)的阻塞等待，那么又有兩個(gè)策略:

直接拒絕，拋出異常，打日志，通知RD時(shí)鐘回滾。

利用擴(kuò)展位，上面我們討論過不同業(yè)務(wù)場(chǎng)景位數(shù)可能用不到那么多，那么我們可以把擴(kuò)展位數(shù)利用起來(lái)了，比如當(dāng)這個(gè)時(shí)間回?fù)鼙容^長(zhǎng)的時(shí)候，我們可以不需要等待，直接在擴(kuò)展位加1。2位的擴(kuò)展位允許我們有3次大的時(shí)鐘回?fù)?，一般?lái)說(shuō)就夠了，如果其超過三次我們還是選擇拋出異常，打日志。

通過上面的幾種策略可以比較的防護(hù)我們的時(shí)鐘回?fù)?，防止出現(xiàn)回?fù)苤蟠罅康漠惓３霈F(xiàn)。下面是修改之后的代碼，這里修改了時(shí)鐘回?fù)艿倪壿?

最后

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

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

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