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

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

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

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

這個方案利用了數(shù)據(jù)庫的單點特性，其優(yōu)點為：
?無需寫額外代碼
?全局唯一
?絕對遞增
?遞增ID的步長確定

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

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

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

select max_id from T;

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

update T set max_id=200;

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

這個方案的優(yōu)點：
?數(shù)據(jù)庫只保存一條記錄
?性能極大增強

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

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

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

select max_id from T;
如上圖所示，兩個id-service在啟動的過程中，同時拿到了max-id為100。

兩個id-service同時對數(shù)據(jù)庫的max-id進(jìn)行寫回：

update T set max_id=200;

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

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

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

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

這樣，id-service2寫回時，就會失敗：

失敗后，id-service2要再次查詢max-id：

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

update t set max_id=300 where max_id=200;
寫回成功。

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

其不足為：
?由于有多個service，生成的ID 不是絕對遞增的，而是趨勢遞增的

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