淺談CAS在分布式ID生成方案上的應(yīng)用

近幾篇文章聊CAS被罵得較多，今天還是聊CAS，談?wù)凜AS在一種“分布式ID生成方案”上的應(yīng)用。 

所謂“分布式ID生成方案”，是指在分布式環(huán)境下，生成全局唯一ID的方法。

可以利用DB自增鍵(auto inc id)來(lái)生成全局唯一ID，插入一條記錄，生成一個(gè)ID：

這個(gè)方案利用了數(shù)據(jù)庫(kù)的單點(diǎn)特性，其優(yōu)點(diǎn)為：
?無(wú)需寫(xiě)額外代碼
?全局唯一
?絕對(duì)遞增
?遞增ID的步長(zhǎng)確定

其不足為：
?需要做數(shù)據(jù)庫(kù)HA，保證生成ID的高可用
?數(shù)據(jù)庫(kù)中記錄數(shù)較多
?生成ID的性能，取決于數(shù)據(jù)庫(kù)插入性能

優(yōu)化方案為：
?利用雙主保證高可用
?定期刪除數(shù)據(jù)
?增加一層服務(wù)，采用批量生成的方式降低數(shù)據(jù)庫(kù)的寫(xiě)壓力，提升整體性能

增加服務(wù)后，DB中只需保存當(dāng)前最大的ID即可，在服務(wù)啟動(dòng)初始化的過(guò)程中，首先拉取當(dāng)前的max-id：

select max_id from T;

然后批量獲取一批ID，放到id-servcie內(nèi)存里，并將max-id寫(xiě)回?cái)?shù)據(jù)庫(kù)：

update T set max_id=200;

這樣，id-service就拿到了[100, 200]這一批ID，上游在獲取ID時(shí)，不用每次都插入數(shù)據(jù)庫(kù)，而是分配完100個(gè)ID后，再修改max-id的值，這樣分配ID的整體性能就增加了100倍。

這個(gè)方案的優(yōu)點(diǎn)：
?數(shù)據(jù)庫(kù)只保存一條記錄
?性能極大增強(qiáng)

其不足為：
?如果id-service重啟，可能內(nèi)存會(huì)有一段已經(jīng)申請(qǐng)的ID沒(méi)有分配出去，導(dǎo)致ID空洞，當(dāng)然，這不是一個(gè)嚴(yán)重的問(wèn)題
?服務(wù)沒(méi)有做HA，無(wú)法保證高可用

優(yōu)化方案為：
?冗余服務(wù)，做集群保證高可用

冗余了服務(wù)后，多個(gè)服務(wù)在啟動(dòng)過(guò)程中，進(jìn)行ID批量申請(qǐng)時(shí)，可能由于并發(fā)導(dǎo)致數(shù)據(jù)不一致：

select max_id from T;
如上圖所示，兩個(gè)id-service在啟動(dòng)的過(guò)程中，同時(shí)拿到了max-id為100。

兩個(gè)id-service同時(shí)對(duì)數(shù)據(jù)庫(kù)的max-id進(jìn)行寫(xiě)回：

update T set max_id=200;

寫(xiě)回max-id成功后，這兩個(gè)id-service都以為自己拿到了[100,200]這一批ID，導(dǎo)致集群會(huì)生成重復(fù)的ID。

問(wèn)題發(fā)生的原因，是并發(fā)寫(xiě)回時(shí)，沒(méi)有對(duì)max-id的初始值進(jìn)行比對(duì)：
id-service1寫(xiě)回max-id=200成功的條件是，max-id必須等于100
id-service2寫(xiě)回max-id=200成功的條件是，max-id也必須等于100

id-service1寫(xiě)回時(shí)，max-id是100，理應(yīng)寫(xiě)回成功
id-service2寫(xiě)回時(shí)，max-id已經(jīng)被改成了200，不應(yīng)該寫(xiě)回成功

只要實(shí)施CAS樂(lè)觀鎖，在寫(xiě)回時(shí)對(duì)max-id的初始條件進(jìn)行比對(duì)，就能避免數(shù)據(jù)的不一致，寫(xiě)回SQL由：
update T set max_id=200;
升級(jí)為：
update T set max_id=200 where max_id=100;

這樣，id-service2寫(xiě)回時(shí)，就會(huì)失?。?br />
失敗后，id-service2要再次查詢max-id：

此時(shí)max-id已經(jīng)變?yōu)?00，于是id-service2獲取到了[200, 300]這一批ID，并將max-id=300寫(xiě)回：

update t set max_id=300 where max_id=200;
寫(xiě)回成功。

這種方案的好處是：
?能夠通過(guò)水平擴(kuò)展的方式，達(dá)到分布式ID生成服務(wù)的無(wú)限性能
?使用CAS簡(jiǎn)潔的保證不會(huì)生成重復(fù)的ID

其不足為：
?由于有多個(gè)service，生成的ID 不是絕對(duì)遞增的，而是趨勢(shì)遞增的

本文介紹了CAS在分布式ID生成方案上的一種應(yīng)用，更多的分布式ID生成方案，請(qǐng)參考《細(xì)聊分布式ID生成器架構(gòu)》。