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:
image.png -
time-based:基于時(shí)間的UUID,這個(gè)一般是通過(guò)當(dāng)前時(shí)間砌创，隨機(jī)數(shù)虏缸，和本地Mac地址來(lái)計(jì)算出來(lái)鲫懒，自帶的JDK包并沒有這個(gè)算法的我們?cè)谝恍︰UIDUtil中，比如我們的log4j.core.util刽辙，會(huì)重新定義UUID的高位和低位窥岩。
image.png DCE security:DCE安全的UUID。
name-based：基于名字的UUID宰缤，通過(guò)計(jì)算名字和名字空間的MD5來(lái)計(jì)算UUID颂翼。
UUID的優(yōu)點(diǎn):
通過(guò)本地生成，沒有經(jīng)過(guò)網(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)心過(guò)多的空間占用语淘，以及不需要生成有遞增趨勢(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)問(wèn)題，需要進(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就需要重置蜈首，通過(guò)(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ù)都訪問(wèn)的是數(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è)方案也可以通過(guò)一些手段避免被人猜測(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，用雪花算法別人就發(fā)猜測(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ù)苤ǜВ瑨伋霎惓? 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());
}
}
}
上面定義了雪花算法的實(shí)現(xiàn)涌攻，在nextId中是我們生成雪花算法的關(guān)鍵。
7.2防止時(shí)鐘回?fù)?/h5>
因?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ò)展位盹廷，上面我們討論過(guò)不同業(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ō)就夠了渤弛，如果其超過(guò)三次我們還是選擇拋出異常，打日志甚带。
通過(guò)上面的幾種策略可以比較的防護(hù)我們的時(shí)鐘回?fù)苣喊牛乐钩霈F(xiàn)回?fù)苤蟠罅康漠惓３霈F(xiàn)。下面是修改之后的代碼欲低，這里修改了時(shí)鐘回?fù)艿倪壿?
最后
本文分析了各種生產(chǎn)分布式ID的算法的原理，以及他們的適用場(chǎng)景畜晰，相信你已經(jīng)能為自己的項(xiàng)目選擇好一個(gè)合適的分布式ID生成策略了砾莱。沒有一個(gè)策略是完美的，只有適合自己的才是最好的凄鼻。
