1. 背景
分布式系統(tǒng)或者微服務(wù)架構(gòu)基本都采用了分庫分表的設(shè)計(jì)，全局唯一id生成的需求變得很迫切。
傳統(tǒng)的單體應(yīng)用，使用單庫，數(shù)據(jù)庫中自增id可以很方便實(shí)現(xiàn)。分庫之后，首先需要分庫鍵，分庫鍵必然不能重復(fù)，所以傳統(tǒng)的做法并不能滿足需求。概括下來，那業(yè)務(wù)系統(tǒng)對ID號的要求有哪些呢？
1.全局唯一性：不能出現(xiàn)重復(fù)的ID號，既然是唯一標(biāo)識，這是最基本的要求。
2.趨勢遞增：在MySQL InnoDB引擎中使用的是聚集索引，由于多數(shù)RDBMS使用B-tree的數(shù)據(jù)結(jié)構(gòu)來存儲索引數(shù)據(jù)，在主鍵的選擇上面我們應(yīng)該盡量使用有序的主鍵保證寫入性能。
3.單調(diào)遞增：保證下一個(gè)ID一定大于上一個(gè)ID，例如事務(wù)版本號、IM增量消息、排序等特殊需求。
4.信息安全：如果ID是連續(xù)的，惡意用戶的扒取工作就非常容易做了，直接按照順序下載指定URL即可；如果是訂單號就更危險(xiǎn)了，競對可以直接知道我們一天的單量。所以在一些應(yīng)用場景下，會需要ID無規(guī)則、不規(guī)則。
其中第3和第4點(diǎn)是互斥的。除了功能性需求，還有性能和可靠性的需求：
- 平均延遲和TP999延遲都要盡可能低；
- 可用性5個(gè)9；
- 高QPS。
2. 進(jìn)階歷程
自從項(xiàng)目從單體應(yīng)用拆分成微服務(wù)架構(gòu)后，對全局id部分做了些摸索。
2.1 uuid
剛開始拆分業(yè)務(wù)，id主鍵都是使用uuid字符串。
UUID(Universally Unique Identifier)的標(biāo)準(zhǔn)型式包含32個(gè)16進(jìn)制數(shù)字，以連字號分為五段，形式為8-4-4-4-12的36個(gè)字符。類似這樣的字符串：dc5adf0a-d531-11e5-95aa-3c15c2d22392。128位，根本不用擔(dān)心不夠用。生成的方法也很簡單：
UUID userId = UUID.randomUUID();
uuid全球唯一，本地生成，沒有網(wǎng)絡(luò)消耗，產(chǎn)生的性能絕對可以滿足。
其缺點(diǎn)也是顯而易見的，比較占地方，和INT類型相比，存儲一個(gè)UUID要花費(fèi)更多的空間。
使用UUID后，URL顯得冗長，不夠友好。ID作為主鍵時(shí)在特定的環(huán)境會存在一些問題，比如做DB主鍵的場景下，UUID就非常不適用：
- MySQL官方有明確的建議主鍵要盡量越短越好，36個(gè)字符長度的UUID不符合要求。
- 對MySQL索引不利：如果作為數(shù)據(jù)庫主鍵，在InnoDB引擎下，UUID的無序性可能會引起數(shù)據(jù)位置頻繁變動(dòng)，嚴(yán)重影響性能。
2.2 數(shù)據(jù)庫生成
以MySQL舉例，利用給字段設(shè)置auto_increment_increment和auto_increment_offset來保證ID自增，每次業(yè)務(wù)使用下列SQL讀寫MySQL得到ID號。
參考了Leaf的實(shí)現(xiàn)思想:
- id server每次批量從數(shù)據(jù)庫取號段，本地緩存這個(gè)號段，并且設(shè)置閾值，當(dāng)達(dá)到0.8（已用與號段容量的比值），自動(dòng)去獲取一個(gè)新的號段，更新本地緩存的號段。
- id client，即具體的調(diào)用服務(wù)實(shí)例，在本地也做一個(gè)緩存，實(shí)現(xiàn)和id server的緩存差不多，這樣做的目的是為了減輕id服務(wù)端的壓力，同時(shí)減少了rpc調(diào)用的網(wǎng)絡(luò)消耗。
以上方案，其缺點(diǎn)是：
- 號段存在浪費(fèi)，無論哪個(gè)客戶端還是服務(wù)端重啟都會浪費(fèi)號段。
- 號段是直接自增，不夠隨機(jī)，對外暴露信息過多。
- DB宕機(jī)會造成整個(gè)系統(tǒng)不可用。雖然在DB宕機(jī)之后，利用緩存還能進(jìn)行短暫供號，但是數(shù)據(jù)庫的依賴還是很重。Leaf采用的一般做法是高可用容災(zāi):
采用一主兩從的方式，同時(shí)分機(jī)房部署，Master和Slave之間采用半同步方式同步數(shù)據(jù)。同時(shí)使用DBProxy做主從切換。當(dāng)然這種方案在一些情況會退化成異步模式，甚至在非常極端情況下仍然會造成數(shù)據(jù)不一致的情況，但是出現(xiàn)的概率非常小。
3. snowflake方案
3.1 介紹
考慮到上述方案的缺陷，筆者調(diào)查了其他的生成方案，snowflake就是其中一種方案。
趨勢遞增和不夠隨機(jī)的問題，在snowflake完全可以解決，Snowflake ID有64bits長，由以下三部分組成：
第一位為0，不用。
timestamp—41bits,精確到ms，那就意味著其可以表示長達(dá)(2^41-1)/(1000360024*365)=139.5年，另外使用者可以自己定義一個(gè)開始紀(jì)元（epoch)，然后用(當(dāng)前時(shí)間-開始紀(jì)元）算出time，這表示在time這個(gè)部分在140年的時(shí)間里是不會重復(fù)的，官方文檔在這里寫成了41bits，應(yīng)該是寫錯(cuò)了。另外，這里用time還有一個(gè)很重要的原因，就是可以直接更具time進(jìn)行排序，對于twitter這種更新頻繁的應(yīng)用，時(shí)間排序就顯得尤為重要了。
-
machine id—10bits,該部分其實(shí)由datacenterId和workerId兩部分組成，這兩部分是在配置文件中指明的。
- datacenterId，方便搭建多個(gè)生成uid的service，并保證uid不重復(fù)，比如在datacenter0將機(jī)器0，1，2組成了一個(gè)生成uid的service，而datacenter1此時(shí)也需要一個(gè)生成uid的service，從本中心獲取uid顯然是最快最方便的，那么它可以在自己中心搭建，只要保證datacenterId唯一。如果沒有datacenterId，即用10bits，那么在搭建一個(gè)新的service前必須知道目前已經(jīng)在用的id，否則不能保證生成的id唯一，比如搭建的兩個(gè)uid service中都有machine id為100的機(jī)器，如果其server時(shí)間相同，那么產(chǎn)生相同id的情況不可避免。
- workerId是實(shí)際server機(jī)器的代號，最大到32，同一個(gè)datacenter下的workerId是不能重復(fù)的。它會被注冊到consul上，確保workerId未被其他機(jī)器占用，并將host:port值存入，注冊成功后就可以對外提供服務(wù)了。
sequence id —12bits,該id可以表示4096個(gè)數(shù)字，它是在time相同的情況下，遞增該值直到為0，即一個(gè)循環(huán)結(jié)束，此時(shí)便只能等到下一個(gè)ms到來，一般情況下4096/ms的請求是不太可能出現(xiàn)的，所以足夠使用了。
3.2 實(shí)現(xiàn)思路
snowflake方案，id服務(wù)端生成，不依賴DB，既能保證性能，且生成的id足夠隨機(jī)。每一毫秒，一臺worker可以生成4096個(gè)id，如果超過，會阻塞到下一毫秒生成。
對于那些并發(fā)量很大的系統(tǒng)來說,顯然是不夠的, 那么這個(gè)時(shí)候就是通過datacenterId和workerId來做區(qū)分,這兩個(gè)ID,分別是5bit,共10bit,最大值是1024(0-1023)個(gè), 在這種情況下,snowflake一毫秒理論上最大能夠生成的ID數(shù)量是約42W個(gè),這是一個(gè)非常大的基數(shù)了,理論上能夠滿足絕大多數(shù)系統(tǒng)的并發(fā)量。
該方案依賴于系統(tǒng)時(shí)鐘，需要考慮時(shí)鐘回?fù)艿膯栴}。本地緩存上一次請求的lastTimestamp，一個(gè)線程過來獲取id時(shí)，首先校驗(yàn)當(dāng)前時(shí)間是否小于上一次ID生成的時(shí)間戳。如果小于說明系統(tǒng)時(shí)鐘被修改過，回退在上一次ID生成時(shí)間之前應(yīng)當(dāng)拋出異常！如此可以解決運(yùn)行中，系統(tǒng)時(shí)鐘被修改的問題。
另一種情況是，server服務(wù)啟動(dòng)時(shí)，系統(tǒng)的時(shí)間被回?fù)埽m然比較極端，還是列在考慮中），這樣有可能與之前生成的id沖突，全局不唯一。這邊解決方法是利用項(xiàng)目的服務(wù)發(fā)現(xiàn)與注冊組件consul，在consul集群存儲最新的lastTimestamp，key為對應(yīng)的machine-id。consul的一致性基于raft算法，并利用Gossip協(xié)議：
Consul uses a gossip protocol to manage membership and broadcast messages to the cluster. All of this is provided through the use of the Serf library.
具體的協(xié)議算法，可以參考Gossip。
每次server實(shí)例啟動(dòng)時(shí)，實(shí)例化id生成bean的時(shí)候，會首先校驗(yàn)當(dāng)前時(shí)間與consul集群中該worker對應(yīng)的lastTimestamp大小，如果當(dāng)前時(shí)間偏小，則拋出異常，服務(wù)啟動(dòng)失敗并報(bào)警。
筆者項(xiàng)目暫時(shí)未分data center，所以machine-id部分都是以服務(wù)實(shí)例的workid代替。workid可以從配置中心獲取，也可以本地配置。請求id生成流程圖如下：
服務(wù)實(shí)例啟動(dòng)的流程圖見上文，此處不畫出了。這邊需要強(qiáng)調(diào)的是，服務(wù)注冊與發(fā)現(xiàn)組件consul。部署時(shí)每個(gè)服務(wù)實(shí)例都會注冊到一個(gè)consul agent（一般是本機(jī)），consul agent連接到consul集群，通過gossip協(xié)議進(jìn)行廣播信息，所以如果連接的consul agent進(jìn)程不幸掛掉（大多為系統(tǒng)宕機(jī)），在進(jìn)程重啟后，還是能迅速獲取到集群中存儲的該workid的lastTimestamp，針對該workid，如果系統(tǒng)時(shí)間回?fù)苄∮趌astTimestamp，Generator啟動(dòng)時(shí)會報(bào)警。而對于大于lastTimestamp的情況，可能系統(tǒng)時(shí)鐘還是相對回?fù)?，我們姑且可以認(rèn)為對全局id沒有影響。
實(shí)例化時(shí)，進(jìn)行校驗(yàn)：
public IdServiceImpl(long workerId, ConsulClient consulClient) {
if (workerId > idMeta.MAX_ID || workerId < 0) {
throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", idMeta.MAX_ID));
}
this.workerId = workerId;
this.consulClient = consulClient;
validateStoredTimestamp();
log.info("worker starting. timestamp left shift {}, worker id bits {}, sequence bits {}, workerid {}", idMeta.TIMESTAMP_LEFT_SHIFT_BITS, idMeta.ID_BITS, idMeta.SEQUENCE_BITS, workerId);
}
校驗(yàn)函數(shù)：
/**
* checks for timestamp by workerId when server starts.
* if server starts for the first time, just let it go and log warns.
* if current timestamp is smaller than the value stored in consul server, throw exception.
*/
private void validateStoredTimestamp() {
long current = timeGen();
Response<GetValue> keyValueResponse = consulClient.getKVValue(String.valueOf(workerId));
if (keyValueResponse.getValue() != null) {
lastTimestamp = Long.parseLong(keyValueResponse.getValue().getDecodedValue());
validateTimestamp(current, lastTimestamp, Periods.START);
} else {
log.warn(String.format("clock in consul is null. Generator works as for the 1st time."));
}
}
validateTimestamp:
/**
* 如果當(dāng)前時(shí)間戳小于上一次ID生成的時(shí)間戳，說明系統(tǒng)時(shí)鐘被修改過，回退在上一次ID生成時(shí)間之前應(yīng)當(dāng)拋出異常！??！
*
* @param lastTimestamp 上一次ID生成的時(shí)間戳
* @param timestamp 當(dāng)前時(shí)間戳
*/
private void validateTimestamp(long timestamp, long lastTimestamp, Periods period) {
if (timestamp < lastTimestamp) {
log.error(String.format("clock is moving backwards. Rejecting requests until %d.", lastTimestamp));
throw new IllegalStateException(String.format("Clock moved backwards in %s. Refusing to generate id for %d milliseconds", period, lastTimestamp - timestamp));
}
}
獲取id方法：
/**
* 生成ID（線程安全）
*
* @return id
*/
public synchronized long genId() {
long timestamp = timeGen();
//如果當(dāng)前時(shí)間小于上一次ID生成的時(shí)間戳，說明系統(tǒng)時(shí)鐘被修改過，回退在上一次ID生成時(shí)間之前應(yīng)當(dāng)拋出異常?。?！
validateTimestamp(timestamp, lastTimestamp, Periods.RUNNING);
//如果是同一時(shí)間生成的，則進(jìn)行毫秒內(nèi)sequence生成
if (lastTimestamp == timestamp) {
sequence = (sequence + 1) & IdMeta.SEQUENCE_MASK;
//溢出處理
if (sequence == 0) {//阻塞到下一毫秒,獲得新時(shí)間戳
timestamp = tilNextMillis(lastTimestamp);
}
} else {//時(shí)間戳改變，毫秒內(nèi)sequence重置
sequence = 0L;
}
//上次生成ID時(shí)間截
lastTimestamp = timestamp;
consulClient.setKVValue(String.valueOf(workerId), String.valueOf(lastTimestamp));
//移位并通過或運(yùn)算組成64位ID
return ((timestamp - idMeta.START_TIME) << idMeta.TIMESTAMP_LEFT_SHIFT_BITS) | (workerId << idMeta.ID_SHIFT_BITS) | sequence;
}
4. 總結(jié)
這篇文章和大家分享了筆者項(xiàng)目中全局id生成服務(wù)的演進(jìn)過程。當(dāng)前的方案可以滿足筆者當(dāng)前項(xiàng)目的需求，至于分data-center（同一個(gè)機(jī)房優(yōu)先調(diào)用），需要結(jié)合rpc調(diào)用進(jìn)一步做處理，所以這塊后續(xù)可以繼續(xù)完善。歡迎大家提出建議。
參考：
