一、Paxoskv的研發背景

在BIGO內部,存儲系統主要包含表格類存儲系統MyShard,分布式key/value類存儲系統ssdb [1]和pika [2],以及其它用于對象存儲的分布式系統。key/value的存儲內部大量采用ssdb和pika,雖然ssdb和pika都是很優秀的存儲系統,但在BIGO業務場景的具體實踐中,BIGO技術遭遇到了不少的問題和挑戰。例如,ssdb和pika都是采用基于binlog的primary/backup [3]復制模型,primary/backup模型很好地解決了讀擴展問題的同時,也帶來了如下圖所示的一些問題:

1) primary/backup之間的數據同步,不僅涉及到數據是否會丟失的問題,還涉及到整個存儲集群對外可以提供什么樣的一致性模型的問題。而單一的同步方式,無論是采用異步、半同步還是強同步的方式,都無法滿足不同業務差異化的需求。

2) primary上data操作和binlog操作的原子性,既和復制的進度管理有關,又和多副本系統中的一致性有關。比如在MySQL內部,innodb和binlog之間采用內部XA事務來解決這個問題,但在現有系統上如何解決好這個問題就比較有挑戰。

3) primary/backup模型,比較難處理多region寫入的問題。簡單的多點寫入不僅無法提供正確的一致性邊界,而且可能導致更新靜默丟失等問題,從而給故障定位和運維帶來較大的負擔。

4) primary/backup模型在多區部署的情況下,存在primary節點fanout放大、跨region流量冗余傳輸、backup節點資源利用受限等潛在問題。

5) pika也提供類似NRW [25]的復制模型,但即使采用R+W > N的quorum配置,如果不采用read repair等手段,也無法提供線性一致性,具體示例參考“2.3.6”章節。

總之,相對于BIGO多元化的業務種類和快速增長的數據規模,現有存儲系統在數據一致性、系統可用性、性能和跨region部署能力等方面,已經無法滿足BIGO內部業務系統的訴求。具體而言,BIGO業務對存儲系統的核心訴求包含:

● 具備從線性一致性到最終一致性的多種一致性模型,不同業務場景可以根據自身的SLA,在RTO和RPO之間權衡;

● 具備多點寫入的能力,即宏觀上是一個multi-master的系統,在容錯設計內的節點故障,不對系統可用性產生影響;

● 具備深度的掌控/定制能力,可以下沉部分高頻業務場景到存儲層;簡化開發的同時,有利于提升業務的核心競爭力;

● 具備友好的水平擴展能力,可以快速地擴/縮容;在交付效率和資源利用方面更進一步;

基于上面這些背景,我們開發了paxoskv。其設計目標是:具備線性一致性/因果一致性/最終一致性可選的能力,具備多點寫入的能力,具備水平擴展能力,讀寫性能和ssdb、pika相當。

二、Paxoskv的技術實現

2.1 系統架構

Paxoskv的系統架構示意如下,每一個set對應一個邏輯數據分區,每一個set在服務端有多個replica(圖中以3副本為例:replica1/replica2/replica3)。每一個set內的key,按照一致性hash劃分為多個key space,每一個key space對應到具體replica。這樣做的目的是為了讓每一個replica都具備處理請求的能力,與之對應的是raft [23]這類強leader協議,所有的寫請求必須路由到leader節點,由leader節點發起。這樣對follower節點的資源利用不是十分充分,一定程度上降低了整個集群的處理能力。

每一個replica server可以包含多個set的replica,同時對多個set進行服務。一個replica server所服務的replica數量,可以隨著遷移、物理機器擴容等因素而不時變化。整個集群的元數據存儲在etcd [16]中,smart client通過watch的方式及時感知整個集群拓撲情況的變化。

2.2 設計選型

在paxoskv的設計選型上,我們主要結合了“Paxoskv的研發背景”部分描述的現狀、BIGO內部業務的訴求、以及較為前沿的分布式存儲系統技術,來進行綜合的判斷和取舍。設計中,BIGO技術借鑒了WPaxos [24]中的很多想法,最終選擇paxoskv的理論支撐和工程實踐設計如下:

● 在復制模型方面,RW節點間paxoskv采用leaderless的multi-paxos架構,既允許多點寫入、又借助于multi-paxos來保證多個副本間狀態的一致性;

● 為避免data操作和binlog操作原子性的問題,RW到RO節點、RO節點到RO節點間paxoskv通過復制存儲引擎的WAL來回避這個問題,同時也帶來了成本和復制實時性方面的一些收益;

● 為應對多region部署的需求,和cloud spanner [5]類似,paxoskv內部節點分為RW(read-write)和RO(read-only)兩種角色,在region內部RW間采用multi-paxos做強同步復制,跨region通過RO做異步復制,多個region間采用chain-replication,避免產生冗余的跨region流量;

● 另外,paxoskv是一個key一個獨立的multi-paxos log序列,不同的multi-paxos log之間完全隔離,比較好地可以讓大量的paxos實例并行運行,從而提升集群層面的并發響應能力;

2.3 深度優化

2.3.1 Leaderless

目前主流基于multi-paxos的多副本存儲系統中,都是采用set劃分的方式,一個set管理一個數據分片,一個set對應一個multi-paxos log。Paxoskv的實現中,為了滿足系統水平擴展性的需求,也是采用set化的思想,不過一個set中包含多個multi-paxos log。具體而言是每一個key都有自己獨立的multi-paxos log。在同一個set內,在smart client發起請求時,會根據一致性hash,將同一個set中的不同key均勻地分布到多個副本之間。所以paxoskv是具備多點寫入能力的leaderless架構,在微觀層面,對于同一個key,如果集群拓撲穩定,則走fast accept路徑,反之則走slow accept路徑,即原生的paxos算法兩階段流程。

Leaderless設計的一個好處是可以提供集群層面更好的可用性保證,在基于raft [23]或primary/backup [3]的設計中,通常采用租約的方式來保證系統中同一時刻只有一個Raft leader或primary節點,以避免在網絡分區等情況下產生“多主”問題。租約方式的不足是,租約期設置太小容易導致誤判,網絡抖動被認為是節點不可用;租約期設置太大,又會導致真正故障發生時,上一任租約過期到選出新租約持有節點的間隔較長,這個過度窗口期整個集群是不可用的,會影響系統的SLA。

如下圖所示(圖片來源[7]),Paxos算法天然具備leaderless屬性,無論是否有穩定的proposer leader節點存在,都可以保證算法的safety,最多犧牲一些liveness。工程實踐中,可以通過隨機避讓和重試等手段來提升paxos實例的liveness。這也是我們選擇paxos作為共識算法的原因之一:

BIGO實際的業務場景中,同一個key從不同的client并發請求,且部分client和其對應的paxoskv節點遭遇網絡分區(進而認為節點不可用,轉而切換到其它節點重試)發生的概率非常低。所以在向一個節點請求超時后,可以快速換節點發起重試請求,這樣系統的不可用時間窗口就大幅降低了。

2.3.2 Log is data

Log is data最早較為正式的起源是新國大2012年VLDB的論文《LogBase: A Scalable Log-structured Database System in the Cloud》[8],目前已經成為云原生數據庫架構的重要設計理念之一,主要是為了解決傳統WAL + data page數據庫架構中寫入IO容易成為瓶頸的不足。如下圖所示:

在paxoskv的實現中,value本身是paxos log的一部分,是比較合適采用log is data思想的場景。即BIGO技術把運行paxos達成共識的paxos log和最終對業務提供讀/寫的value融為一體,無需先寫paxos log,再replay paxos log到存儲引擎。但paxoskv目前的實現中,還是會帶來一定程度的讀/寫放大,尤其是value較大的場景體現較為明顯,采用多版本機制是更合理的方法,這是后續需要優化的方向之一。

2.3.3 Fast accept

如下圖所示(圖片來源[9]),原生的paxos算法分為兩個階段:第一階段包含phase-1a propose和phase-1b promise;第二階段包含phase-2a accept和phase-2b accepted;每一個階段消耗1個RTT。Paxoskv雖然采用leaderless的架構,但實現中借鑒了主流multi-paxos工程實現中具備stable leader的優化。對于同一個key,如果最新的chosen log其發起者正好是當前節點(Proposer ID會被記錄在paxos log的meta信息中),那么就不需要執行原生paxos算法的第一個階段(phase-1a propose/phase-1b promise),直接發起phase-2a accept請求,我們稱paxoskv中的這種流程為fast accept(在具體的工程實現中,為了保證協議的正確性,fast accept的提案會以1:Proposer ID作為提案編號發起,而非fast accept的提案會以2: Proposer ID作為提案編號發起)。因此,大多數集群拓撲穩定的情況下,paxoskv都可以走fast accept路徑。

2.3.4 Fast chosen

如下圖所示(圖片來源[9]),原生的paxos算法中,有Proposer/Acceptor/Learner三個角色,一個典型的paxos算法執行流程如下圖所示:

我們可以看到,即便是走fast accept的路徑,從發起accept請求到確定一個提案已經chosen,需要1.5個RTT(Proposer → Acceptor → Distinguished Proposer/Learner → Acceptor),在更新頻繁的場景,可以在下一個請求之上piggyback上一個提案的chosen通知。注意,如果每一個acceptor在accepted一個提案后,可以廣播給所有的Acceptor,以快速確定是否已經滿足多數派計數從而達成chosen狀態,但工程實現中一般不會這樣做,因為消息復雜度太高。

paxoskv的實現中,在3副本的情況下,Proposer會先本地accepted,然后再發送accept請求給acceptors,這樣一來,任何一個acceptor只要本地判斷滿足accepted的條件,加上Proposer的一個accepted計數,就可以確定滿足majority accepted的條件,從而快速進入chosen狀態。和前面提到的下一個請求之上piggyback上一個提案的chosen通知方式相比,寫入的延時沒有明顯的改善,但這里可以和log is data的思想結合,對于acceptor來說,確定chosen后一次磁盤寫入就完成了本次paxos的流程,節省了一次寫Rocksdb [10]的IO操作。當然,fast chosen只有在3副本的配置下才能生效(BIGO的實際部署中,目前都是3副本的配置)。

2.3.5 WAL replication

在采用binlog進行復制的系統中,在產生binlog的節點上要面臨更新data和binlog原子性的問題。binlog通常又分為基于statement和基于ROW的兩種格式,涉及到的問題包含如何保證在其它副本上replay binlog后產生相同的數據頁、同時還要考慮同步的binlog的大小、binlog是否可以被并行replay等問題。

在paxoskv的實現中,因為最終存儲數據的引擎是Rocksdb [10],所以BIGO技術采用基于Rocksdb WAL log的復制。如下圖所示:

paxoskv WAL replication的實現主要依賴Rocksdb [10]的GetLatestSequenceNumber()和GetUpdatesSince()這兩個API。在初始化或者復制中斷恢復時,采用pull/push結合的模式來對齊同步位點,具體的實現和MySQL 5.7基于GTID的binlog復制比較類似[11]。

2.3.6 Linearizable quorum read

在強一致的存儲系統中,實現線性一致性讀寫,一般是通過在paxos proposer leader上實現master lease來完成,亦或者從集群中實施多數派讀來實現。上述主流實現方式中,leader節點容易成為集群的瓶頸,follower節點的資源則比較難以充分利用。paxoskv針對這個問題,借鑒《Linearizable Quorum Reads in Paxos》[12]中的算法,優化了paxoskv的線性一致性讀的流程,實際驗證表明性能有80+%以上的提升。

簡單的quorum讀并不能保證線性一致性,例如傳統的NRW模型,即便在選擇R + W > N的strict quorum配置下,也會破壞線性一致性。如下圖所示,Reader A先發起讀請求,返回了新版本的值x=1;此后某個時間點Reader B后發起讀請求,卻返回了舊版本的值x=0,破壞了線性一致性的約束。圖片來源于《Designing Data-Intensive Applications》:

具體的實現算法為Paxos Quorum Reads(簡稱為PQR),圖片來源于《Linearizable Quorum Reads in Paxos》[12]論文:

算法分為quorum-read和rinse兩個階段。quorum-read階段,smart client從除leader之外的多數派中讀取最新被accepted的slot。每一個replica不管accepted slot是否存在gap,直接返回自己所見的最大accepted slot,例如某一個replica本地accepted的slot是[1,4]和6,那么返回6給smart client。smart client收集所有回復中最大的accepted slot,作為發起rinse階段的accepted slot,這個slot的value會作為最終返回給調用的value;但這個accepted的slot可能還沒有完成commit,所以smart client必須等待以確保這個slot已經完成持久化的commit,通過這種方式來完成client視角的強一致性。

在rinse階段中,smart client向quorum-read階段的replica集合中任意一個replica發送請求,檢查對應的accepted slot是否已經被commit。如果被選中的replica回復已經commit,smart client以這個commit的value返回給調用者。

這種方式還是需要2個RTT才能完成強一致性的讀,paxoskv在實現的時候,在quorum-read階段,返回最新的accepted slot和最新的committed slot。如果多數派的replica返回了相同的accepted slot和committed slot,實際上這就是集群中最新的數據;換句話說,保證了線性一致性的約束。因此,paxoskv中大多數場景下,線性一致性都只需要一個RTT就可以完成。

三、總結與展望

自從Paxos算法1989年[9]問世以后,工業界很多重量級產品都基于Paxos算法或其變種來構建高可用能力和提升數據的一致性,例如大家熟悉的Google Chubby [14]、Apache Zookeeper [15],以及比較新的etcd [16]和consul [17]等。但這些實現都強依賴一個中心化的leader節點,所以這類系統基本都只能部署在IDC內,或者同城的IDC之間,我們稱這類協議為leader-based的協議。

Paxos [9]算法也一直是學術界的熱點,比較新的研究成果包含Mencius [18]協議和EPaxos [19]協議,這兩者都屬于Leaderless的協議,Mencius [18]協議通過對paxos實例進行靜態的預分配,雖然達到了多點寫入的目的,但其提交的延時還是依賴于集群中最慢的節點。而EPaxos協議應用于實際工程中,主要的缺陷是通常需要3/4(大于常規的多數派 [n/2]+f)的節點通訊正常,其次是協議工程化復雜度較高。所以雖然Mencius [18]和EPaxos [19]比較好的解決了多點寫入的問題,但是由于上述限制,還是無法部署于副本之間延時比較高的場景,比如異地多IDC之間。

應對leader-based協議只能單點寫入的另外一個途徑是sharding,比如Google Spanner [20]、ZooNet [21]和Bizur [22]等,但這些解決方案美中不足是對數據進行了靜態分區,而且以分區為粒度生成multi-paxos log一定程度上降低了并發能力。實際的業務負載中,通常數據的局部性會不時動態變化,因此比較理想的情況是存儲系統具備根據業務access patterns和服務器的負載等維度,應用相關的策略來動態調整數據對象的讀/寫訪問接入點。在下一階段的迭代中,paxoskv將重點打造下面兩個主要功能:

3.1 Access patterns/Load aware

前面提到,在同一個set內paxoskv采用一致性hash來將不同的key打散到不同的節點上,但如果業務的key分布相對穩定,即某一部分key都穩定在一個固定的IDC內進行讀寫,那么一個比較自然的調整就是將這部分key的讀寫請求發往離client最近的節點,這樣達到比較優化的端到端延時。和work stealing [13]設計類似,更通用的抽象是根據不同的access patterns,以不同的key分布策略來動態調整每一個key的就近接入點。與此類似,我們也可以根據節點間的負載,來動態遷移一部分key的接入點,來達到整個集群層面資源利用更合理的效果。

3.2 Lightweight Multi-Key Transaction

paxoskv在BIGO內部上線后,收到了很多反饋和需求,其中大部分是產品化能力加強的需求,其中技術側比較迫切的需求是實現多個key操作的原子性,比如在贈送相關的業務場景,實質是一個A減B加的過程。paxoskv在下一個迭代中,將提供跨多個set的輕量級multi-key事務。

四、收獲與感謝

從paxoskv設計研發到上線落地的過程中,BIGO技術深刻地體會到開發一個健壯的分布式存儲系統所面臨的挑戰和取舍。比如如何測試并驗證系統的正確性,如何驗證系統在遭遇異常后的自愈能力。再比如我們選擇了key粒度的multi-paxos log,雖然帶來了多點寫入和并發能力提升方面的收益,但是也給集群的成員變更、全局快照備份等方面帶來了很大的復雜度。這些問題我們將在后續的介紹中陸續展開,也借這個機會感謝所有給我們提出寶貴建議和反饋的同學們!

參考資料

[1]:http://ssdb.io/zh_cn/

[2]:https://github.com/pika/pika

[3]:https://en.wikipedia.org/wiki/Replication_(computing)#Primary-backup_and_multi-primary_replication

[4]:https://www.cs.cornell.edu/courses/cs6410/2017fa/slides/22-p2p-storage.pdf

[5]:https://cloud.google.com/spanner/docs/replication

[6]:http://muratbuffalo.blogspot.com/2018/11/sdpaxos-building-efficient-semi.html

[7]:https://www.slideshare.net/InfoQ/consensus-why-cant-we-all-just-agree

[8]:http://vldb.org/pvldb/vol5/p1004_hoangtamvo_vldb2012.pdf

[9]:https://en.wikipedia.org/wiki/Paxos_(computer_science)

[10]:https://github.com/facebook/rocksdb

[11]:https://dev.mysql.com/doc/refman/5.7/en/replication-gtids-howto.html

[12]:https://www.usenix.org/system/files/hotstorage19-paper-charapko.pdf

[13]:https://en.wikipedia.org/wiki/Work_stealing

[14]:Chubby,https://static.googleusercontent.com/media/research.google.com/zh-CN//archive/chubby-osdi06.pdf

[15]:Zookeeper,https://github.com/apache/zookeeper

[16]:etcd,https://github.com/etcd-io/etcd

[17]:consul,https://github.com/hashicorp/consul

[18]:Mencius,https://www.usenix.org/legacy/events/osdi08/tech/full_papers/mao/mao.pdf

[19]:EPaxos,https://www.cs.cmu.edu/～dga/papers/epaxos-sosp2013.pdf

[20]:Spanner,https://www.usenix.org/system/files/conference/osdi12/osdi12-final-16.pdf

[21]:Zoonet,https://www.usenix.org/system/files/conference/atc16/atc16_paper-lev-ari.pdf

[22]:Bizur,https://arxiv.org/abs/1702.04242

[23]:Raft,https://www.usenix.org/conference/atc14/technical-sessions/presentation/ongaro

[24]:WPaxos,https://cse.buffalo.edu/tech-reports/2017-01.pdf

[25]:http://courses.cse.tamu.edu/caverlee/csce438/readings/dynamo-paper.pdf

(稿件來源BIGO技術自媒體)