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

public class IdWorker{

private long workerId;

private long datacenterId;

private long sequence = 0;

/**

* 2018/9/29日，從此時(shí)開始計(jì)算，可以用到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();

//時(shí)間回?fù)埽瑨伋霎惓?/p>

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;

}

/**

* 當(dāng)前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());

}

}

}

復(fù)制代碼

上面定義了雪花算法的實(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è)策略是完美的，只有適合自己的才是最好的。

最后送波福利?，F(xiàn)在加群即可獲取Java工程化、高性能及分布式、高性能、 高架構(gòu)。性能調(diào)優(yōu)、Spring，MyBatis，Netty源碼分析和大數(shù)據(jù)等多個(gè)知識(shí) 點(diǎn)高級(jí)進(jìn)階干貨的直播免費(fèi)學(xué)習(xí)權(quán)限及領(lǐng)取相關(guān)資料，群號(hào)：835638062 點(diǎn) 擊鏈接加入群聊【Java高級(jí)架構(gòu)】：https://jq.qq.com/? _wv=1027&k=5S3kL3v