針對Paxos算法的全局唯一自增ID的生成方法

黃振業(yè)

摘? 要：Paxos算法是被廣泛使用的分布式一致算法，為了保障Paxos算法的正確性和高性能，需要配合使用高性能、高可用、全局唯一自增序列號的生成系統(tǒng)。為此，該文提出了一種全局唯一自增ID的生成方法，該方法以物理機(jī)器時鐘頻率不會產(chǎn)生大波動的特性為前提，并在實現(xiàn)上采用多種高性能、高可用技術(shù)。最后構(gòu)建了測試環(huán)境，通過實驗證明了該方案在正常態(tài)和異常態(tài)時，都能正確產(chǎn)生全局唯一自增ID，同時整個系統(tǒng)也達(dá)到了預(yù)期的高性能要求。

關(guān)鍵詞：一致性? 唯一自增ID生成? 高性能? 高可用

中圖分類號：TP301? ? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識碼：A文章編號：1672-3791（2021）03（c）-0001-06

Generation Method of Global Unique Auto Increment ID Generation for Paxos Algorithm

HUANG Zhenye

（School of Information Technology， Zhejiang Financial College， Hangzhou， Zhejiang Province， 310018 China）

Abstract： Paxos is a protocol for solving consensus in a distribution system. Paxos can work in a network with fail-ures， and all processors in the network could be unreliable. While Paxos protocol has a precondition step： generat-ing the unique version numbers for Paxos protocol. This paper proposes a method to generate the unique version numbers for Paxos protocol. And this method should be high available and should have high performance. Aiming to this object， the method utilizes the stability of machine timestamp， and uses high available techniques on imple-mentation. Finally， a test environment is constructed. Experiments show that the method can generate the unique version numbers correctly in normal and abnormal conditions， and the whole system also achieves the expected high performance requirements.

Key Words： Consensus; Unique auto increment ID generation; High performance; High available

目前，有很多分布式一致性算法來解決分布式系統(tǒng)的一致性問題，而Paxos算法是其中重要的一種算法，它已經(jīng)被應(yīng)用到多種系統(tǒng)中[1]。Paxos算法又分為Basic Paxos算法和Multi-Paxos算法[2]。在這兩種算法之上又有一些改進(jìn)的算法[3-6]，但這些算法都需要有一個機(jī)制來生成全局唯一自增ID。如果不能保障生成全局唯一自增的ID，就不能保障Paxos算法的正確性。

該文提出了一種新的全局唯一自增ID的生成方法，同時會涉及工程上實現(xiàn)的細(xì)節(jié)。首先，簡單介紹Paxos算法，其中著重說明全局唯一自增ID的生成的必要性;其次，列舉其他一些常用的全局唯一自增的ID的生成方式以及它們的不足;最后，重點介紹新的全局唯一自增ID的生成方法及實驗結(jié)果。

1? Basic Paxos

Paxos算法分為Basic Paxos算法和Multi-Paxos算法，而全局唯一自增ID的生成方法對兩者并無區(qū)別，該文就以Basic Paxos算法作為例子來說明Paxos算法。

Paxos算法中的進(jìn)程有3種身份：proposer、acceptor、learner。Paxos算法又分為兩個階段：準(zhǔn)備階段與批準(zhǔn)階段[2，7]。

1.1 準(zhǔn)備階段

proposer選擇一個全局唯一遞增的ID，n作為本輪的版本號。群發(fā)版本號為n的prepare請求給一個acceptor的多數(shù)派，即超過半數(shù)的acceptor。

每個acceptor會存儲曾經(jīng)批準(zhǔn)過提案中最大版本號的提案，其中w+max_version，w為提案內(nèi)容，max_version為最大的提案版本，具體請參考批準(zhǔn)階段的詳細(xì)敘述。

每當(dāng)acceptor接收到一個版本號為n的prepare請求。當(dāng)n>max_version時，那么把最大版本號的提案返回給proposer，如果之前沒有批準(zhǔn)過任何提案，則返回“空”給proposer;當(dāng)n<=max_version時，那么proposer不對這個版本號為n的prepare請求做出響應(yīng)，并承諾今后不會批準(zhǔn)版本號小于n的任何提案，即版本號大于等于n的提案才會被批準(zhǔn)。

1.2 批準(zhǔn)階段

proposer從acceptor的多數(shù)派獲得prepare請求的響應(yīng)，并從這些響應(yīng)中挑出版本號最大的提案內(nèi)容，假設(shè)該內(nèi)容為w。proposer群發(fā)一個批準(zhǔn)請求（版本號為n，內(nèi)容為w）給一個acceptor的多數(shù)派。如果proposer獲得的所有響應(yīng)都為空，那么群發(fā)的提案可以是任何內(nèi)容。

每個acceptor接收到一個批準(zhǔn)請求（版本號為n，內(nèi)容為w），如果它不違反之前的承諾，即n>=承諾過的最大版本號，那么該提案才會被批準(zhǔn)，并返回批準(zhǔn)響應(yīng)給proposer;否則，對這個批準(zhǔn)請求不做回應(yīng)。如果最后某個proposer沒有從一個acceptor的多數(shù)派獲得prepare的響應(yīng)，這個proposer需要重新生成一個全局唯一遞增的版本號，重新從準(zhǔn)備階段開始啟動算法。

Paxos算法本身的證明可以參閱參考文獻(xiàn)[7]。其中整個算法中的proposer每次必須生成一個全局唯一遞增的ID作為該輪算法的版本號。此版本號必須滿足兩個條件：全局唯一和自增。全局唯一就是兩個獨立的proposer不能生成相同的版本號，而自增則是每個proposer每次生成的版本號必須是遞增的。

2? 現(xiàn)有方案的缺陷

生成的全局的唯一自增ID要滿足以下幾點需求。

（1）保證生成的ID全局唯一，且每個進(jìn)程生成的ID自增。

（2）生成的ID最好不大于64位。

（3）生成ID的速度有要求。例如：在一個高吞吐量的場景中，需要每秒生成幾萬個ID。

（4）整個服務(wù)沒有單點。

如果沒有以上的幾點需求，那么可以有很多簡單的實現(xiàn)方案。

2.1 利用數(shù)據(jù)庫的自增ID方案

利用數(shù)據(jù)庫的自增ID的方法實現(xiàn)簡單，可以保證全局唯一，但是它依賴中間節(jié)點，而且每個節(jié)點都需要訪問一次數(shù)據(jù)庫才能得到ID值，這樣就出現(xiàn)了整個系統(tǒng)的單點問題。同時，由于數(shù)據(jù)庫本身的性能限制，也不能滿足高吞吐量的需求。

2.2 利用數(shù)據(jù)庫的其他變種方案

利用多個寫庫來解決單數(shù)據(jù)庫自增ID方案的單點問題：使用多個寫庫，每個寫庫的自增初始值不同，步長值不一樣。假設(shè)利用3個寫庫：A、B、C。其中A庫的ID序列為0、3、6、9，B庫為1、4、7、10，C庫為2、5、8，11。多寫庫的方案避免的單點問題，但性能還是會受到數(shù)據(jù)庫性能的限制，不滿足高性能需求。

另外，還有使用數(shù)據(jù)庫MyISAM+Replace Intro模式的方案。這個方案由Filcker提出，采用了MySQL自增ID的方法。數(shù)據(jù)庫中只存放單條記錄，每次利用replace into，然后通過select LAST_INSERT_ID獲取最后一個插入的ID值。該方案可以擴(kuò)展為多臺數(shù)據(jù)庫，也可以使用不同的初始值和步長值增加可用性，但是同樣不滿足高性能的要求。

2.3 利用中心服務(wù)器生成ID方案

利用一個中心服務(wù)器來統(tǒng)一生成unique ID，但是這種方案可能存在單點問題。例如：利用開源軟件Redis的原子操作方式來獲取遞增ID序列[8]。由于Redis具備高性能，該方案解決了數(shù)據(jù)庫方案性能受限的問題，但引入了Redis同樣增加了整個系統(tǒng)對Redis的強依賴，出現(xiàn)了單點問題，而且引入Redis后要保證Redis系統(tǒng)的高可用性與高可靠性，在工程上有很大的挑戰(zhàn)，實現(xiàn)難度較大。

2.4 Twitter Snowflake方案

Twitter Snowflake方案是Twitter推出的一種算法[9]，其目的是為了滿足每秒能分配上萬個唯一ID的需求，滿足分布式環(huán)境的需求。其算法核心如下：Snowflake生成的unique ID，從高位到低位分別為：41位的時間戳、10位的節(jié)點ID和12位的序列號。為了避免保障機(jī)器號重復(fù)，每個進(jìn)程啟動時都需要從Zookeeper集群獲取機(jī)器號。Snowflake的優(yōu)點是算法簡單、性能高、保持自增。但是Snowflake的實現(xiàn)帶來了的風(fēng)險：依賴Zookeeper來解決單點問題。但Zookeeper工程上運維代價過高，面對高并發(fā)，Zookeeper的性能較差。一旦proposer所在機(jī)器時鐘故障，時鐘被回?fù)埽筒荒鼙Ｕ先治ㄒ磺疫f增。同樣由于機(jī)器時鐘可能存在的故障，有可能發(fā)生proposer宕機(jī)后恢復(fù)導(dǎo)致非遞增ID生成的極端情況。

以上列舉的幾種方案，都存在一定的局限或風(fēng)險，不能很好的滿足Paxos算法的需求。其中Snowflake是最接近高性能需求的方案，該文重點針對其進(jìn)行優(yōu)化，以達(dá)到高可用和高可靠的目標(biāo)。

3? 全局唯一自增ID生成

Snowflake的主要缺陷就是對本機(jī)時鐘有依賴，一旦本機(jī)時鐘故障導(dǎo)致時鐘回?fù)?，就不能正確的工作;同時由于對Zookeeper服務(wù)強依賴，整個系統(tǒng)較為復(fù)雜。該方案的重點就是在Snowflake的基礎(chǔ)上針對時鐘問題進(jìn)行改進(jìn)，其核心思想就是引入一個可靠的時鐘服務(wù)器，本機(jī)定時從外部時鐘服務(wù)器獲取到準(zhǔn)確的時間，而時鐘服務(wù)的工程實現(xiàn)比Zookeeper等開源系統(tǒng)簡單可靠，從而克服了其對外部一致性服務(wù)依賴的弊端以及機(jī)器時鐘回?fù)艿膯栴}，能很好地滿足Paxos算法的需求。同時，該方法只需要定時和時鐘服務(wù)器同步時間戳，確保系統(tǒng)具有高性能。

Snowflake生成的UniqueID的結(jié)構(gòu)是一個64位的int類型數(shù)據(jù)，具體情況見圖1。其中第一部分共1位，往往不使用;第二部分共41位，用來記錄時間戳，以毫秒來表示;第三部分共10位，用來記錄分布式節(jié)點ID，包括5位的datacenter ID和5位的worker ID，最大可部署1 024個節(jié)點;第四部分共12位，用來記錄不同ID同一毫秒時的序列號。

3.1 方案改進(jìn)

相對于Snowflake方案，該系統(tǒng)的關(guān)鍵改進(jìn)為引入一個節(jié)點ID分配服務(wù)（后續(xù)簡稱為IDCMaster），每個datacenter有一個IDCMaster，IDCMaster也同時作為時鐘服務(wù)器，向所有的節(jié)點提供時鐘同步服務(wù)。

用于組裝UniqueID的時間戳并不是proposer所在機(jī)器的時間戳，而是使用IDCMaster的時間戳來生成UniqueID。這樣所有的proposer全部以IDCMaster的時間為準(zhǔn)，不存在由于proposer本地時間戳不對而導(dǎo)致的各種不一致問題。同時，IDCMaster只是一個簡單的保證時間正確的服務(wù)，相比Zookeeper，實現(xiàn)和運維十分簡單，易于實現(xiàn)高性能、高可用。整個系統(tǒng)架構(gòu)見圖2。

3.2 計算方法

proposer啟動時會先連接所在datacenter的IDCMaster，獲取當(dāng)前proposer唯一的workerID。IDCMaster保證分配出來的workerID在datacenter范圍內(nèi)唯一。proposer會定時從IDCMaster獲取到IDCMaster的時間戳并計算出proposer所在機(jī)器的時間戳相對IDCMaster的時間偏差并存放在本地，該時間偏差值設(shè)為diff_time。

當(dāng)提交prepare提案時，每個proposer不直接用本機(jī)的時間戳作為UniqueID的時間戳，而是用diff_time對本地時間戳作一個修正后來生成UniqueID。所以雖然本地時間戳可能不準(zhǔn)確，但可以通過diff_time來修正本地時間戳，保持每次生成ID時使用的本地時間戳和IDCMaster的時間戳一致。同時，由于本地時鐘頻率可由硬件保證，就算出現(xiàn)了時鐘故障導(dǎo)致機(jī)器時間被回?fù)?，只需定時和IDCMaster同步，獲取到diff_time就可以保證生成ID唯一遞增的正確性，并具有高性能。

3.3 注意事項

該方案盡管不同于物理機(jī)器的時間戳可能有偏差，但由于物理機(jī)器的時鐘頻率由硬件保證，極大情況下時鐘只會正向流逝。同時，即便是時間出現(xiàn)回?fù)?，也通過和IDCMasterde定時同步獲得正確的時間戳，快速恢復(fù)工作，并不會影響唯一自增ID的生成。這樣既保證了正確性，又保證了高性能。

proposer每次定時更新本機(jī)和IDCMaster的偏差 diff_time時，必須保證修正后的時間戳單調(diào)遞增。proposer只是定時訪問IDCMaster，所以IDCMaster的高可用方案比較容易實現(xiàn)。比如可以簡單地利用較成熟的IP地址漂移技術(shù)實現(xiàn)。利用IDCMaster Backup作為IDCMaster的備用機(jī)器，當(dāng)IDCMaster宕機(jī)時，IDCMaster對外的IP地址漂移到IDCMaster Backup。當(dāng)IDCMaster宕機(jī)恢復(fù)后，proposer會重連上IDCMaster，恢復(fù)更新本機(jī)和IDCMaster的時間戳的偏差即可。而且IDCMaster做的工作及其簡單，只是提供一個時間戳，性能極高。當(dāng)然也需要保障IDCMaster Backup的時間戳保證和IDCMaster的時間戳一致。

該方法最大的限制就是本機(jī)時鐘硬件故障。但只要時鐘流逝是正向的，不出現(xiàn)大幅時鐘回?fù)艿墓收系那闆r下，就不會破壞整個方案的正確性，即生成唯一自增ID。因此，只需要本機(jī)proposer在每次生成ID時確認(rèn)新生成的ID比上次生成的ID大。如果一旦檢測到新生成的ID較小的情況，就說明這次生成的ID不正確，直接拋棄掉，直到下次和IDCMaster同步后就又能生成正確的自增ID。

當(dāng)某個proposer下線后，再有一個新的proposer連上IDCMaster的場景，如果IDCMaster分配了原先的節(jié)點ID給新連上來的proposer，IDCMaster要保證同步給新proposer時間戳大于之前的下線的proposer的時間戳。

4? 實驗

為了驗證該方案的性能及唯一ID的產(chǎn)生，構(gòu)建了以下測試環(huán)境：10臺位于同一物理機(jī)房的物理機(jī)，其規(guī)格均為4核8G。實驗中逐步加大測試并發(fā)量，壓測每臺物理機(jī)，直到單機(jī)每秒吞吐量達(dá)到5萬以上，同時也會記錄下平均的延時和系統(tǒng)負(fù)載。測試過程中，會分別測試正常態(tài)下和異常態(tài)下系統(tǒng)的性能及產(chǎn)生ID的唯一性。

實驗進(jìn)程如下：初始狀態(tài)為1臺物理機(jī)連接上IDCMaster，并開始消耗唯一ID，然后每間隔1 min新增一臺物理機(jī)連接到IDCMaster;終態(tài)為10臺物理機(jī)同時連上IDCMaster進(jìn)行工作，然后逐步增大工作并發(fā)量直到單機(jī)每秒吞吐量達(dá)到5萬。

記錄正常態(tài)的實驗過程中每次和IDCMaster同步的延時（系統(tǒng)設(shè)置為每分鐘和IDCMaster同步一次diff master），以及節(jié)點平均產(chǎn)生唯一ID的延時和最高延時，并記錄實驗產(chǎn)生的所有ID。正常態(tài)實驗結(jié)果見圖3。

實驗結(jié)果顯示，單個ID生成的耗時小于0.02 ms，生成1 000個ID的耗時在3 ms以內(nèi)。同時測試單機(jī)的平均吞吐量為5萬ID/s，并且在測試過程中，機(jī)器的負(fù)載很?。簡螜C(jī)CPU利用率小于10%，單機(jī)LOAD小于0.5。同時，驗證了所有升級的ID，滿足無重復(fù)遞增的要求。通過正常態(tài)測試，驗證了該方案能滿足分布式高吞吐量場景的正確性。

在正常態(tài)實驗的基礎(chǔ)上，進(jìn)行異常態(tài)測試。在實驗過程中，手工回?fù)軉闻_物理機(jī)的本機(jī)時間，關(guān)閉NTP服務(wù)，驗證服務(wù)器時鐘故障的場景下ID生成的正確性。異常態(tài)測試結(jié)果如圖4所示。

通過實驗驗證了該方法可以適應(yīng)時鐘回?fù)艿墓收?，不影響生成ID的自增屬性。當(dāng)時鐘回?fù)軙r，生成節(jié)點可檢測到時鐘問題，停止分配ID，避免了錯誤的ID生成，直到1 min后再次和IDCMaster同步時間戳后，能夠繼續(xù)分配正確的自增唯一ID。

5? 結(jié)語

該文介紹了一種可應(yīng)用在Paxos算法實現(xiàn)中的全局唯一自增ID生成方法。該方法基于Snowflake方案，但解決了Snowflake在物理機(jī)器時間戳不一致場景下不能保證生成的ID唯一自增的缺陷。該方案的核心思想是利用機(jī)器時鐘頻率變化不會過大的特性來實現(xiàn)分布式的自增ID的生成;同時也針對各種極限情況作了保障，使得即使發(fā)生特殊異常，也不會破壞整個Paxos算法的正確性。下一步工作是進(jìn)一步提升生成自增ID的TPS，并探索在云主機(jī)環(huán)境的適應(yīng)性，使該系統(tǒng)能適用于更大規(guī)模的場景。

參考文獻(xiàn)

[1] Chandra TD，Griesemer R，Redstone J.Paxos made live：an engineering perspective[C]//twenty-sixth acm symposium on principles of distributed computing.acm，2007：398-407.

[2] Saksham Chand，Yanhong A.Liu，Scott D.Stoller.Formal Ver-ification of Multi-Paxos for Distributed Consensus[C]//International Symposium on Formal Methods，2016：119-136.

[3] 胡創(chuàng)，馬文韜，王文杰，等.CC-Paxos：整合廣域存儲系統(tǒng)的一致性和可靠性[J].計算機(jī)工程與設(shè)計，2017，38（3）：626-632.

[4] 楊革，徐虹.Paxos算法的研究與改進(jìn)[J].科技創(chuàng)新與應(yīng)用，2017（7）：25-26.

[5] 趙守月，葛洪偉.MEPaxos：低延遲的共識算法[J].計算機(jī)科學(xué)與探索，2019，13（5）：866-874.

[6] 王江，章明星，武永衛(wèi)，等.類Paxos共識算法研究進(jìn)展[J].計算機(jī)研究與發(fā)展，2019，56（4）：692-707.

[7] Lamport L.Paxos made simple[J].ACM SIGACT News， 2001，32（4）：51-58.

[8] Yao Kan，Ni huxuan，wang yuan，et al.Low Cost and High Concurrency ID Mak-er in Distributed Environment[C]//ITM Web of Conferences，2017：03003.

[9] Jim Bumgardner.Tracking Twitter's Growth after Snow-flake[EB/OL].[2019-05-12].https：//www.jbum.com/papers/TrackingTwittersGrowthAfterSnowflake.pdf.