Vesta多場景分布式發(fā)號(hào)器

Vesta 是一款通用的ID產(chǎn)生器，互聯(lián)網(wǎng)俗稱統(tǒng)一發(fā)號(hào)器，它具有全局唯一、粗略有序、可反解和可制造等特性，它支持三種發(fā)布模式：嵌入發(fā)布模式、中心服務(wù)器發(fā)布模式、REST發(fā)布模式，根據(jù)業(yè)務(wù)的性能需求，它可以產(chǎn)生最大峰值型和最小粒度型兩種類型的ID，它的實(shí)現(xiàn)架構(gòu)使其具有高性能，高可用和可伸縮等互聯(lián)網(wǎng)產(chǎn)品需要的質(zhì)量屬性，是一款通用的高性能的發(fā)號(hào)器產(chǎn)品。

主頁鏈接：http://vesta.cloudate.net/

當(dāng)前遇到的問題

當(dāng)前業(yè)務(wù)系統(tǒng)的ID使用數(shù)據(jù)庫的自增字段，自增字段完全依賴于數(shù)據(jù)庫，這在數(shù)據(jù)庫移植，擴(kuò)容，洗數(shù)據(jù)，分庫分表等操作時(shí)帶來了很多麻煩。

在數(shù)據(jù)庫分庫分表時(shí)，有一種辦法是通過調(diào)整自增字段或者數(shù)據(jù)庫sequence的步長來達(dá)到跨數(shù)據(jù)庫的ID的唯一性，但仍然是一種強(qiáng)依賴數(shù)據(jù)庫的解決方案，有諸多的限制，并且強(qiáng)依賴數(shù)據(jù)庫類型，我們并不推薦這種方法。

為什么不用UUID

UUID雖然能夠保證ID的唯一性，但是，它無法滿足業(yè)務(wù)系統(tǒng)需要的很多其他特性，例如：時(shí)間粗略有序性，可反解和可制造型。另外，UUID產(chǎn)生的時(shí)候使用完全的時(shí)間數(shù)據(jù)，性能比較差，并且UUID比較長，占用空間大，間接導(dǎo)致數(shù)據(jù)庫性能下降，更重要的是，UUID并不具有有序性，這導(dǎo)致B+樹索引在寫的時(shí)候會(huì)有過多的隨機(jī)寫操作（連續(xù)的ID會(huì)產(chǎn)生部分順序?qū)懀?，另外寫的時(shí)候由于不能產(chǎn)生順序的append操作，需要進(jìn)行insert操作，這會(huì)讀取整個(gè)B+樹節(jié)點(diǎn)到內(nèi)存，然后插入這條記錄后寫整個(gè)節(jié)點(diǎn)回磁盤，這種操作在記錄占用空間比較大的情況下，性能下降比較大，具體壓測報(bào)告請(qǐng)參考：Mysql性能壓測實(shí)踐報(bào)告

需求整理

既然數(shù)據(jù)庫自增ID和UUID有諸多的限制，我們需要整理一下發(fā)號(hào)器的需求。

1. 全局唯一

有些業(yè)務(wù)系統(tǒng)可以使用相對(duì)小范圍的唯一性，例如，如果用戶是唯一的，那么同一用戶的訂單采用自增序列在用戶范圍內(nèi)也是唯一的，但是如果這樣設(shè)計(jì)，訂單系統(tǒng)就會(huì)在邏輯上依賴用戶系統(tǒng)，因此，不如我們保證ID在系統(tǒng)范圍內(nèi)的全局唯一性更實(shí)用。

分布式系統(tǒng)保證全局唯一的一個(gè)悲觀策略是使用鎖或者分布式鎖，但是，只要使用了鎖，就會(huì)大大的降低性能。

因此，我們決定利用時(shí)間的有序性，并且在時(shí)間的某個(gè)單元下采用自增序列，達(dá)到全局的唯一性。

2. 粗略有序

上面討論了UUID的最大問題就是無序的，任何業(yè)務(wù)都希望生成的ID是有序的，但是，分布式系統(tǒng)中要做到完全有序，就涉及到數(shù)據(jù)的匯聚，當(dāng)然要用到鎖或者布式鎖，考慮到效率，只能采用折中的方案，粗略有序，到底有多粗略，目前有兩種主流的方案，一種是秒級(jí)有序，一種是毫秒級(jí)有序，這里又有一個(gè)權(quán)衡和取舍，我們決定支持兩種方式，通過配置來決定服務(wù)使用其中的一種方式。

3. 可反解

一個(gè) ID 生成之后，ID本身帶有很多信息量，線上排查的時(shí)候，我們通常首先看到的是ID，如果根據(jù)ID就能知道什么時(shí)候產(chǎn)生的，從哪里來的，這樣一個(gè)可反解的 ID 可以幫上很多忙。

如果ID 里有了時(shí)間而且能反解，在存儲(chǔ)層面就會(huì)省下很多傳統(tǒng)的timestamp 一類的字段所占用的空間了，這也是一舉兩得的設(shè)計(jì)。

4. 可制造

一個(gè)系統(tǒng)即使再高可用也不會(huì)保證永遠(yuǎn)不出問題，出了問題怎么辦，手工處理，數(shù)據(jù)被污染怎么辦，洗數(shù)據(jù)，可是手工處理或者洗數(shù)據(jù)的時(shí)候，假如使用數(shù)據(jù)庫自增字段，ID已經(jīng)被后來的業(yè)務(wù)覆蓋了，怎么恢復(fù)到系統(tǒng)出問題的時(shí)間窗口呢？

所以，我們使用的發(fā)號(hào)器一定要可復(fù)制，可恢復(fù) ，可制造。

5. 高性能

不管哪個(gè)業(yè)務(wù)，訂單也好，商品也好，如果有新記錄插入，那一定是業(yè)務(wù)的核心功能，對(duì)性能的要求非常高，ID生成取決于網(wǎng)絡(luò)IO和CPU的性能，CPU一般不是瓶頸，根據(jù)經(jīng)驗(yàn)，單臺(tái)機(jī)器TPS應(yīng)該達(dá)到10000/s。

6. 高可用

首先，發(fā)號(hào)器必須是一個(gè)對(duì)等的集群，一臺(tái)機(jī)器掛掉，請(qǐng)求必須能夠轉(zhuǎn)發(fā)到其他機(jī)器，另外，重試機(jī)制也是必不可少的。最后，如果遠(yuǎn)程服務(wù)宕機(jī)，我們需要有本地的容錯(cuò)方案，本地庫的依賴方式可以作為高可用的最后一道屏障。

7. 可伸縮

作為一個(gè)分布式系統(tǒng)，永遠(yuǎn)都不能忽略的就是業(yè)務(wù)在不斷地增長，業(yè)務(wù)的絕對(duì)容量不是衡量一個(gè)系統(tǒng)的唯一標(biāo)準(zhǔn)，要知道業(yè)務(wù)是永遠(yuǎn)增長的，所以，系統(tǒng)設(shè)計(jì)不但要考慮能承受的絕對(duì)容量，還必須考慮業(yè)務(wù)增長的速度，系統(tǒng)的水平伸縮是否能滿足業(yè)務(wù)的增長速度是衡量一個(gè)系統(tǒng)的另一個(gè)重要標(biāo)準(zhǔn)。 

設(shè)計(jì)與實(shí)現(xiàn)

發(fā)布模式

根據(jù)最終的客戶使用方式，可分為嵌入發(fā)布模式，中心服務(wù)器發(fā)布模式和REST發(fā)布模式。

1. 嵌入發(fā)布模式：只適用于Java客戶端，提供一個(gè)本地的Jar包，Jar包是嵌入式的原生服務(wù)，需要提前配置本地機(jī)器ID（或者服務(wù)啟動(dòng)時(shí)候Zookeeper動(dòng)態(tài)分配唯一的ID,在第二版中實(shí)現(xiàn))，但是不依賴于中心服務(wù)器。

2. 中心服務(wù)器發(fā)布模式：只適用于Java客戶端，提供一個(gè)服務(wù)的客戶端Jar包，Java程序像調(diào)用本地API一樣來調(diào)用，但是依賴于中心的ID產(chǎn)生服務(wù)器。

3. REST發(fā)布模式：中心服務(wù)器通過Restful API導(dǎo)出服務(wù)，供非Java語言客戶端使用。

發(fā)布模式最后會(huì)記錄在生成的ID中。也參考下面數(shù)據(jù)結(jié)構(gòu)段的發(fā)布模式相關(guān)細(xì)節(jié)。

ID類型

根據(jù)時(shí)間的位數(shù)和序列號(hào)的位數(shù)，可分為最大峰值型和最小粒度型。

1. 最大峰值型：采用秒級(jí)有序，秒級(jí)時(shí)間占用30位，序列號(hào)占用20位

2. 最小粒度型：采用毫秒級(jí)有序，毫秒級(jí)時(shí)間占用40位，序列號(hào)占用10位

最大峰值型能夠承受更大的峰值壓力，但是粗略有序的粒度有點(diǎn)大，最小粒度型有較細(xì)致的粒度，但是每個(gè)毫秒能承受的理論峰值有限，為1k，同一個(gè)毫秒如果有更多的請(qǐng)求產(chǎn)生，必須等到下一個(gè)毫秒再響應(yīng)。

ID類型在配置時(shí)指定，需要重啟服務(wù)才能互相切換。

數(shù)據(jù)結(jié)構(gòu)

1. 序列號(hào)

最大峰值型

20位，理論上每秒內(nèi)平均可產(chǎn)生2^20= 1048576個(gè)ID，百萬級(jí)別，如果系統(tǒng)的網(wǎng)絡(luò)IO和CPU足夠強(qiáng)大，可承受的峰值達(dá)到每毫秒百萬級(jí)別。

最小粒度型

10位，每毫秒內(nèi)序列號(hào)總計(jì)2^10=1024個(gè), 也就是每個(gè)毫秒最多產(chǎn)生1000+個(gè)ID，理論上承受的峰值完全不如我們最大峰值方案。

2. 秒級(jí)時(shí)間/毫秒級(jí)時(shí)間

最大峰值型

30位，表示秒級(jí)時(shí)間，2^30/60/60/24/365=34，也就是可使用30+年。

最小粒度型

40位，表示毫秒級(jí)時(shí)間，2^40/1000/60/60/24/365=34，同樣可以使用30+年。

3. 機(jī)器ID

10位， 2^10=1024, 也就是最多支持1000+個(gè)服務(wù)器。中心發(fā)布模式和REST發(fā)布模式一般不會(huì)有太多數(shù)量的機(jī)器，按照設(shè)計(jì)每臺(tái)機(jī)器TPS 1萬/s，10臺(tái)服務(wù)器就可以有10萬/s的TPS，基本可以滿足大部分的業(yè)務(wù)需求。

但是考慮到我們?cè)跇I(yè)務(wù)服務(wù)可以使用內(nèi)嵌發(fā)布方式，對(duì)機(jī)器ID的需求量變得更大，這里最多支持1024個(gè)服務(wù)器。

4. 生成方式

2位，用來區(qū)分三種發(fā)布模式：嵌入發(fā)布模式，中心服務(wù)器發(fā)布模式，REST發(fā)布模式。

00：嵌入發(fā)布模式 01：中心服務(wù)器發(fā)布模式 02：REST發(fā)布模式 03：保留未用

5. ID類型

1位，用來區(qū)分兩種ID類型：最大峰值型和最小粒度型。

0：最大峰值型 1：最小粒度型

6. 版本

1位，用來做擴(kuò)展位或者擴(kuò)容時(shí)候的臨時(shí)方案。

0：默認(rèn)值，以免轉(zhuǎn)化為整型再轉(zhuǎn)化回字符串被截?cái)?nbsp;1：表示擴(kuò)展或者擴(kuò)容中 

作為30年后擴(kuò)展使用，或者在30年后ID將近用光之時(shí)，擴(kuò)展為秒級(jí)時(shí)間或者毫秒級(jí)時(shí)間來掙得系統(tǒng)的移植時(shí)間窗口，其實(shí)只要擴(kuò)展一位，完全可以再使用30年。

并發(fā)

對(duì)于中心服務(wù)器和REST發(fā)布方式，ID生成的過程涉及到網(wǎng)絡(luò)IO和CPU操作，ID的生成基本都是內(nèi)存到高速緩存的操作，沒有IO操作，網(wǎng)絡(luò)IO是系統(tǒng)的瓶頸。

相對(duì)于CPU計(jì)算速度來說網(wǎng)絡(luò)IO是瓶頸，因此，ID產(chǎn)生的服務(wù)使用多線程的方式，對(duì)于ID生成過程中的競爭點(diǎn)time和sequence，我們使用concurrent包的ReentrantLock進(jìn)行互斥。

機(jī)器ID的分配

我們將機(jī)器ID分為兩個(gè)區(qū)段，一個(gè)區(qū)段服務(wù)于中心服務(wù)器發(fā)布模式和REST發(fā)布模式，另外一個(gè)區(qū)段服務(wù)于嵌入發(fā)布模式。

0-923：嵌入發(fā)布模式，預(yù)先配置，（或者由Zookeeper產(chǎn)生，第二版中實(shí)現(xiàn)），最多支持924臺(tái)內(nèi)嵌服務(wù)器 924 – 1023：中心服務(wù)器發(fā)布模式和REST發(fā)布模式，最多支持300臺(tái)，最大支持300*1萬=300萬/s的TPS

如果嵌入式發(fā)布模式和中心服務(wù)器發(fā)布模式以及REST發(fā)布模式的使用量不符合這個(gè)比例，我們可以動(dòng)態(tài)調(diào)整兩個(gè)區(qū)間的值來適應(yīng)。

另外，各個(gè)垂直業(yè)務(wù)之間具有天生的隔離性，每個(gè)業(yè)務(wù)都可以使用最多1024臺(tái)服務(wù)器。

與Zookeeper集成

對(duì)于嵌入發(fā)布模式，服務(wù)啟動(dòng)需要連接Zookeeper集群，Zookeeper分配一個(gè)0-923區(qū)間的一個(gè)ID，如果0-923區(qū)間的ID被用光，Zookeeper會(huì)分配一個(gè)大于923的ID，這種情況，拒絕啟動(dòng)服務(wù)。

如果不想使用Zookeeper產(chǎn)生的唯一的機(jī)器ID，我們提供缺省的預(yù)配的機(jī)器ID解決方案，每個(gè)使用統(tǒng)一發(fā)號(hào)器的服務(wù)需要預(yù)先配置一個(gè)默認(rèn)的機(jī)器ID。

注：此功能在第二版中實(shí)現(xiàn)。

時(shí)間同步

使用Linux的定時(shí)任務(wù)crontab，定時(shí)通過授時(shí)服務(wù)器虛擬集群（全球有3000多臺(tái)服務(wù)器）來核準(zhǔn)服務(wù)器的時(shí)間。

ntpdate -u pool.ntp.orgpool.ntp.org

設(shè)計(jì)驗(yàn)證

1. 我們根據(jù)不同的信息分段構(gòu)建一個(gè)ID，使ID具有全局唯一，可反解和可制造。

2. 我們使用秒級(jí)別時(shí)間或者毫秒級(jí)別時(shí)間以及時(shí)間單元內(nèi)部序列遞增的方法保證ID粗略有序。

3. 對(duì)于中心服務(wù)器發(fā)布模式和REST發(fā)布模式，我們使用多線程處理，為了減少多線程間競爭，我們對(duì)競爭點(diǎn)time和sequence使用ReentrantLock來進(jìn)行互斥，由于ReentrantLock內(nèi)部使用CAS，這比JVM的Synchronized關(guān)鍵字性能更好，在千兆網(wǎng)卡的前提下，至少可達(dá)到1萬/s以上的TPS。

4. 由于我們支持中心服務(wù)器發(fā)布模式，嵌入式發(fā)布模式和REST發(fā)布模式，如果某種模式不可用，可以回退到其他發(fā)布模式，如果Zookeeper不可用，可以會(huì)退到使用本地預(yù)配的機(jī)器ID。從而達(dá)到服務(wù)的最大可用。

5. 由于ID的設(shè)計(jì)，我們最大支持1024臺(tái)服務(wù)器，我們將服務(wù)器機(jī)器號(hào)分為兩個(gè)區(qū)段，一個(gè)從0開始向上，一個(gè)從128開始向下，并且能夠動(dòng)態(tài)調(diào)整分界線，滿足了可伸縮性。

性能需求

最終的性能驗(yàn)證要保證每臺(tái)服務(wù)器的TPS達(dá)到1萬/s以上。

FAQ

1. 調(diào)整時(shí)間是否會(huì)影響ID產(chǎn)生功能？

1. 未重啟機(jī)器調(diào)慢時(shí)間，Vesta拋出異常，拒絕產(chǎn)生ID。重啟機(jī)器調(diào)快時(shí)間，調(diào)整后正常產(chǎn)生ID，調(diào)整時(shí)段內(nèi)沒有ID產(chǎn)生。
2. 重啟機(jī)器調(diào)慢時(shí)間，Vesta將可能產(chǎn)生重復(fù)的時(shí)間，系統(tǒng)管理員需要保證不會(huì)發(fā)生這種情況。重啟機(jī)器調(diào)快時(shí)間，調(diào)整后正常產(chǎn)生ID，調(diào)整時(shí)段內(nèi)沒有ID產(chǎn)生。

1. 每4年一次同步潤秒會(huì)不會(huì)影響ID產(chǎn)生功能？

1. 原子時(shí)鐘和電子時(shí)鐘每四年誤差為1秒，也就是說電子時(shí)鐘每4年會(huì)比原子時(shí)鐘慢1秒，所以，每隔四年，網(wǎng)絡(luò)時(shí)鐘都會(huì)同步一次時(shí)間，但是本地機(jī)器Windows,Linux等不會(huì)自動(dòng)同步時(shí)間，需要手工同步，或者使用ntpupdate向網(wǎng)絡(luò)時(shí)鐘同步。
2. 由于時(shí)鐘是調(diào)快1秒，調(diào)整后不影響ID產(chǎn)生，調(diào)整的1s內(nèi)沒有ID產(chǎn)生。