一、Paxoskv的研發(fā)背景

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

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

2) primary上data操作和binlog操作的原子性,既和復(fù)制的進(jìn)度管理有關(guān),又和多副本系統(tǒng)中的一致性有關(guān)。比如在MySQL內(nèi)部,innodb和binlog之間采用內(nèi)部XA事務(wù)來解決這個問題,但在現(xiàn)有系統(tǒng)上如何解決好這個問題就比較有挑戰(zhàn)。

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

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

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

總之,相對于BIGO多元化的業(yè)務(wù)種類和快速增長的數(shù)據(jù)規(guī)模,現(xiàn)有存儲系統(tǒng)在數(shù)據(jù)一致性、系統(tǒng)可用性、性能和跨region部署能力等方面,已經(jīng)無法滿足BIGO內(nèi)部業(yè)務(wù)系統(tǒng)的訴求。具體而言,BIGO業(yè)務(wù)對存儲系統(tǒng)的核心訴求包含:

● 具備從線性一致性到最終一致性的多種一致性模型,不同業(yè)務(wù)場景可以根據(jù)自身的SLA,在RTO和RPO之間權(quán)衡;

● 具備多點(diǎn)寫入的能力,即宏觀上是一個multi-master的系統(tǒng),在容錯設(shè)計(jì)內(nèi)的節(jié)點(diǎn)故障,不對系統(tǒng)可用性產(chǎn)生影響;

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

● 具備友好的水平擴(kuò)展能力,可以快速地?cái)U(kuò)/縮容;在交付效率和資源利用方面更進(jìn)一步;

基于上面這些背景,我們開發(fā)了paxoskv。其設(shè)計(jì)目標(biāo)是:具備線性一致性/因果一致性/最終一致性可選的能力,具備多點(diǎn)寫入的能力,具備水平擴(kuò)展能力,讀寫性能和ssdb、pika相當(dāng)。

二、Paxoskv的技術(shù)實(shí)現(xiàn)

2.1 系統(tǒng)架構(gòu)

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

每一個replica server可以包含多個set的replica,同時對多個set進(jìn)行服務(wù)。一個replica server所服務(wù)的replica數(shù)量,可以隨著遷移、物理機(jī)器擴(kuò)容等因素而不時變化。整個集群的元數(shù)據(jù)存儲在etcd [16]中,smart client通過watch的方式及時感知整個集群拓?fù)淝闆r的變化。

2.2 設(shè)計(jì)選型

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

● 在復(fù)制模型方面,RW節(jié)點(diǎn)間paxoskv采用leaderless的multi-paxos架構(gòu),既允許多點(diǎn)寫入、又借助于multi-paxos來保證多個副本間狀態(tài)的一致性;

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

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

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

2.3 深度優(yōu)化

2.3.1 Leaderless

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

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

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

BIGO實(shí)際的業(yè)務(wù)場景中,同一個key從不同的client并發(fā)請求,且部分client和其對應(yīng)的paxoskv節(jié)點(diǎn)遭遇網(wǎng)絡(luò)分區(qū)(進(jìn)而認(rèn)為節(jié)點(diǎn)不可用,轉(zhuǎn)而切換到其它節(jié)點(diǎn)重試)發(fā)生的概率非常低。所以在向一個節(jié)點(diǎn)請求超時后,可以快速換節(jié)點(diǎn)發(fā)起重試請求,這樣系統(tǒng)的不可用時間窗口就大幅降低了。

2.3.2 Log is data

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

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

2.3.3 Fast accept

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

2.3.4 Fast chosen

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

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

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

2.3.5 WAL replication

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

在paxoskv的實(shí)現(xiàn)中,因?yàn)樽罱K存儲數(shù)據(jù)的引擎是Rocksdb [10],所以BIGO技術(shù)采用基于Rocksdb WAL log的復(fù)制。如下圖所示:

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

2.3.6 Linearizable quorum read

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

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

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

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

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

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

三、總結(jié)與展望

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

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

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

3.1 Access patterns/Load aware

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

3.2 Lightweight Multi-Key Transaction

paxoskv在BIGO內(nèi)部上線后,收到了很多反饋和需求,其中大部分是產(chǎn)品化能力加強(qiáng)的需求,其中技術(shù)側(cè)比較迫切的需求是實(shí)現(xiàn)多個key操作的原子性,比如在贈送相關(guān)的業(yè)務(wù)場景,實(shí)質(zhì)是一個A減B加的過程。paxoskv在下一個迭代中,將提供跨多個set的輕量級multi-key事務(wù)。

四、收獲與感謝

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

參考資料

[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技術(shù)自媒體)