高可用數(shù)據(jù)庫系統(tǒng)中的分布“一致性協(xié)議

儲(chǔ)佳佳,郭進(jìn)偉,劉柏fl,張晨東,錢衛(wèi)寧

(華東師范大學(xué)數(shù)據(jù)科學(xué)與工程研究院,上海200062)

高可用數(shù)據(jù)庫系統(tǒng)中的分布“一致性協(xié)議

儲(chǔ)佳佳,郭進(jìn)偉,劉柏fl,張晨東,錢衛(wèi)寧

(華東師范大學(xué)數(shù)據(jù)科學(xué)與工程研究院,上海200062)

可用性和一致性是分布式數(shù)據(jù)庫系統(tǒng)中的兩個(gè)重要特性和基礎(chǔ),需要借助分布式一致性協(xié)議來保證.保證一致性需要使用一致性協(xié)議為并發(fā)的事務(wù)更新操作確定一個(gè)全局的執(zhí)行順序,并協(xié)調(diào)局部狀態(tài)和全局狀態(tài)不斷地達(dá)到動(dòng)態(tài)一致.可用性的實(shí)現(xiàn),需要一致性協(xié)議協(xié)調(diào)多副本之間的一致來實(shí)現(xiàn)主備節(jié)點(diǎn)的無縫切換.可見,分布式一致性協(xié)議是高可用數(shù)據(jù)庫系統(tǒng)的實(shí)現(xiàn)基礎(chǔ).本文梳理、綜述了經(jīng)典的分布式一致性協(xié)議以及一致性協(xié)議在高可用數(shù)據(jù)庫系統(tǒng)中的主要應(yīng)用,并對(duì)分布式一致性協(xié)議的實(shí)現(xiàn)代價(jià)和局限性進(jìn)行了分析與評(píng)估.

高可用性;一致性;分布式一致性協(xié)議;分布式數(shù)據(jù)庫

0 引言

隨著數(shù)據(jù)規(guī)模的不斷擴(kuò)大,分布式數(shù)據(jù)庫系統(tǒng)得到了越來越廣泛的運(yùn)用.數(shù)據(jù)分片存儲(chǔ)、多副本冗余和多副本并發(fā)更新這些機(jī)制為分布式數(shù)據(jù)庫系統(tǒng)帶來了可擴(kuò)展、高并發(fā)等優(yōu)點(diǎn)的同時(shí),也引入了一致性、可用性的問題[1].

定義1實(shí)現(xiàn)分布式數(shù)據(jù)庫系統(tǒng)的動(dòng)態(tài)一致性,需要保證:

(1)狀態(tài)一致性,事務(wù)不能破壞數(shù)據(jù)庫的完整性、外鍵約束以及業(yè)務(wù)邏輯上的一致性.

(2)操作一致性,并發(fā)的事務(wù)在各個(gè)局部節(jié)點(diǎn)上串行化執(zhí)行順序和全局的串行化執(zhí)行順序是等價(jià)的.

(3)多副本一致性,主節(jié)點(diǎn)和冗余備份節(jié)點(diǎn)之間數(shù)據(jù)的更新序列是一致的.

分布式數(shù)據(jù)庫系統(tǒng)的一致性需要確保事務(wù)的串行化執(zhí)行順序、事務(wù)的最終狀態(tài)是全局一致的.保證了定義1中的狀態(tài)一致性、操作一致性、多副本一致性,就可以實(shí)現(xiàn)全局狀態(tài)和局部狀態(tài)不斷地從一個(gè)一致的狀態(tài)到達(dá)另一個(gè)一致狀態(tài),實(shí)現(xiàn)一種動(dòng)態(tài)的一致.可用性指數(shù)據(jù)庫系統(tǒng)能夠自動(dòng)容錯(cuò),持續(xù)地對(duì)外提供服務(wù).根據(jù)CAP理論[2],分布式環(huán)境下,可用性和一致性只能保證一點(diǎn).然而,一致性和可用性的權(quán)衡不必是一個(gè)達(dá)到極致,另一個(gè)完全不優(yōu)化(取值不必是0或1,可以是0%至100%).一致性可分為極致一致性、強(qiáng)一致性、最終一致性和弱一致性等多個(gè)級(jí)別,可用性可分為較高可用性、高可用性和弱可用性等.不同級(jí)別的可用性一致性組合可滿足不同的應(yīng)用需求.很多互聯(lián)網(wǎng)應(yīng)用對(duì)一致性要求不高,采取最終一致和較高可用的組合,這是一種一致性換可用性的做法.對(duì)一致性要求較高的關(guān)鍵應(yīng)用,比如銀行系統(tǒng)和金融證券業(yè),可以采取強(qiáng)一致性和高可用的組合,在保證多數(shù)派副本完全一致的前提下,將可用性盡可能地最大化[3].實(shí)現(xiàn)數(shù)據(jù)庫系統(tǒng)的強(qiáng)一致性,關(guān)鍵是選取合適的分布式一致性協(xié)議(distributed consensus protocol)來保證一致性.由于數(shù)據(jù)分布在多個(gè)節(jié)點(diǎn)和網(wǎng)絡(luò)的不確定性等因素,各個(gè)節(jié)點(diǎn)上的數(shù)據(jù)更新是相互隔離并且各自獨(dú)立進(jìn)行的.可能會(huì)出現(xiàn)的問題有:①各個(gè)節(jié)點(diǎn)上分布式事務(wù)的執(zhí)行狀態(tài)不同(對(duì)應(yīng)定義1中狀態(tài)一致性);②更新順序不同(對(duì)應(yīng)定義1中操作一致性);③主備副本數(shù)據(jù)不同步(對(duì)應(yīng)定義1中的多副本一致性)的問題,需要使用分布式一致性協(xié)議來協(xié)調(diào)分布式事務(wù)的提交、多節(jié)點(diǎn)并發(fā)更新和主備節(jié)點(diǎn)操作序列的同步,保證分布式數(shù)據(jù)庫系統(tǒng)的狀態(tài)一致性、操作一致性和多副本一致性.

保證數(shù)據(jù)庫系統(tǒng)的高可用性,分布式一致性協(xié)議同樣至關(guān)重要,因?yàn)槎喔北疽恢滦允窍到y(tǒng)進(jìn)行主備切換的前提.高可用的數(shù)據(jù)庫系統(tǒng)通常采取“主備架構(gòu)”,其中主節(jié)點(diǎn)對(duì)外提供服務(wù),備節(jié)點(diǎn)作為主節(jié)點(diǎn)的冗余備份,存儲(chǔ)著和主節(jié)點(diǎn)相同的數(shù)據(jù).當(dāng)主節(jié)點(diǎn)出現(xiàn)故障宕機(jī)時(shí),期望是選取某個(gè)備節(jié)點(diǎn)成為新的主節(jié)點(diǎn).借助于分布式一致性協(xié)議,可以確保多副本一致性,使得主備節(jié)點(diǎn)的狀態(tài)數(shù)據(jù)始終是一致的.當(dāng)主節(jié)點(diǎn)發(fā)生故障時(shí),備節(jié)點(diǎn)就可以無縫切換為主節(jié)點(diǎn)來接管集群,使系統(tǒng)持續(xù)對(duì)外提供服務(wù).

綜上,分布式一致性協(xié)議是實(shí)現(xiàn)強(qiáng)一致性和高可用性的重要基礎(chǔ).本文梳理并總結(jié)了前人在設(shè)計(jì)一致性協(xié)議探索高可用數(shù)據(jù)庫系統(tǒng)方面進(jìn)行的研究工作,并給出了分析和評(píng)價(jià).第1節(jié)簡要介紹了經(jīng)典的一致性協(xié)議;第2節(jié)借助成熟的分布式數(shù)據(jù)庫系統(tǒng)來說明分布式一致性協(xié)議在高可用數(shù)據(jù)庫系統(tǒng)中都有哪些方面的應(yīng)用;第3節(jié)從消息交互次數(shù)和延遲兩個(gè)方面對(duì)分布式一致性協(xié)議進(jìn)行了代價(jià)評(píng)估,同時(shí)也對(duì)一致性協(xié)議運(yùn)用到實(shí)際系統(tǒng)中的局限性進(jìn)行了整理和分析;第4節(jié)對(duì)未來的研究工作進(jìn)行了展望.

1 分布式一致性協(xié)議概述

為了解決分布式環(huán)境下的一致性問題,前人探討并設(shè)計(jì)了很多策略,例如兩階段提交協(xié)議[4-6]、Paxos算法[7-9]等,這些策略很多已經(jīng)成為了工業(yè)標(biāo)準(zhǔn),在工程實(shí)踐中得到了越來越廣泛的運(yùn)用.圖1呈現(xiàn)了分布式一致性協(xié)議的發(fā)展簡史.

圖1 分布式一致性協(xié)議Fig.1A brief history of the distributed consensus protocols development

如圖1所示,兩階段提交協(xié)議通過預(yù)提交階段(投票階段)和正式提交階段的兩輪消息交互,使得協(xié)調(diào)者和參與者可以就某項(xiàng)決定達(dá)成一致,該協(xié)議的詳細(xì)步驟在相關(guān)論文中有具體的介紹.三階段提交協(xié)議[10]是兩階段提交協(xié)議的優(yōu)化,解決了兩階段提交協(xié)議的阻塞問題.Quorum[11]算法由Gifford于1979年提出,主要數(shù)學(xué)思想來源于鴿巢原理,通過限定讀寫操作最小參與的副本數(shù)目,實(shí)現(xiàn)讀寫操作的互斥來支持多副本的并發(fā)更新.Basic Paxos算法是Leslie Lamport于1998年提出的一種基于消息傳遞模型且具有高度容錯(cuò)特性的一致性算法.通過“提案階段(Prepare)”和“接受階段(Accept)”兩個(gè)階段使得提案者(proposer)和接受者(acceptor)就某項(xiàng)決議達(dá)成一致.除了Basic Paxos,Lamport還研究了多個(gè)變種算法,如Cheap Paxos[12]、Fast Paxos[13]和Vertical Paxos[14]等.Raft算法[15]是斯坦福大學(xué)的Diego Ongaro和John Ousterhout研究的一個(gè)管理日志復(fù)制的一致性算法.表1中呈現(xiàn)了上述一致性協(xié)議的特性.

綜合考慮分布式一致性協(xié)議的發(fā)展歷程和特性,可以發(fā)現(xiàn)它們之間存在著微妙的繼承關(guān)系和相關(guān)性.比如Paxos算法融合了兩階段提交協(xié)議和Quorum算法的思想,通過Quorum算法W＞N/2(W為參與更新操作的最小副本數(shù);N為系統(tǒng)中的總副本數(shù))的“多數(shù)派”思想來實(shí)現(xiàn)更新操作的互斥性,使得只有一個(gè)決議值會(huì)被“多數(shù)派”節(jié)點(diǎn)認(rèn)可.兩個(gè)階段(提案階段和接受階段)的消息交互借鑒了兩階段提交的思路,保證多個(gè)節(jié)點(diǎn)之間更新操作的一致性.通過兩輪信息交互,多數(shù)派達(dá)成一致的決議值,其狀態(tài)一定是確定的(要么是已提交狀態(tài),要么是失敗狀態(tài)).引入“多數(shù)派”的思想,減小了系統(tǒng)阻塞問題的發(fā)生概率,不需要確保系統(tǒng)中所有節(jié)點(diǎn)通信狀況良好,只要保證至少存在多數(shù)派節(jié)點(diǎn)的通信狀況正常,系統(tǒng)就是可用的,“多數(shù)派”的策略一定程度上提高了系統(tǒng)的可用性.

相較于兩階段提交協(xié)議,Paxos增加了一種“學(xué)習(xí)者”角色,將“參與者”的功能一分為二,即“參與決策”交由“接受者”,“知曉決定”交由“學(xué)習(xí)者”.“接受者”和“學(xué)習(xí)者”的角色可以由同一節(jié)點(diǎn)來擔(dān)任(此時(shí)等同于兩階段提交協(xié)議中的“參與者”),也可以由不同節(jié)點(diǎn)來承擔(dān).這種更靈活和細(xì)化的角色分工,使得“參與決策”和“知曉決定”兩個(gè)功能彼此分開,從某種意義上減少了系統(tǒng)阻塞的發(fā)生概率.

Raft算法是Paxos算法的變種,使用更加嚴(yán)格的消息傳遞方式以及選舉規(guī)則,使得算法更加易于理解和工程實(shí)現(xiàn).Raft算法引入了選舉期(term)的概念,用于標(biāo)識(shí)從當(dāng)前輪次的選舉開始至下一輪選舉開始的這段時(shí)期.每個(gè)選舉期內(nèi),所有的伴隨者只能投票給一個(gè)候選者,這種“先到先得”的投票規(guī)則,相較于Paxos算法中的接受者可以多次投票、每次需要回復(fù)已接收到的最大決議值的做法,要更加清晰和簡單.

表1 分布“一致性協(xié)議的特性簡析Tab.1A brief analysis of the distributed consensus protocols

2 分布式一致性協(xié)議在高可用數(shù)據(jù)庫系統(tǒng)中的應(yīng)用

實(shí)現(xiàn)分布式數(shù)據(jù)庫的強(qiáng)一致性和高可用性,需要引入分布式一致性協(xié)議,來協(xié)調(diào)分布式事務(wù)的提交(狀態(tài)一致性)、多節(jié)點(diǎn)并發(fā)更新(操作一致性)和主備節(jié)點(diǎn)操作序列的同步(多副本一致性).這些落實(shí)到具體系統(tǒng)中,需要實(shí)現(xiàn)“分布式事務(wù)提交”、“主節(jié)點(diǎn)選舉”和“日志同步”三個(gè)模塊.本節(jié)首先簡要介紹了上述三個(gè)模塊的通用設(shè)計(jì)思路,并在2.2節(jié)中借助GoogleSpanner和OceanBase進(jìn)行了具體的探討.

2.1 應(yīng)用概述

分布式事務(wù)的一致性提交,保證了分布式事務(wù)的原子性.分布式事務(wù)的相關(guān)節(jié)點(diǎn)需要就事務(wù)的最終狀態(tài)(提交或失敗)達(dá)成一致,不能出現(xiàn)某些節(jié)點(diǎn)局部提交事務(wù)的情況.如果違背了事務(wù)的原子性,狀態(tài)一致性則無法保證.通用的分布式事務(wù)提交策略通過兩階段提交協(xié)議來實(shí)現(xiàn),經(jīng)過投票階段和提交階段的信息交互,使得協(xié)調(diào)者和參與者看到的事務(wù)最終狀態(tài)是一致的.

主節(jié)點(diǎn)的選舉,指的是從系統(tǒng)中的所有節(jié)點(diǎn)中選取領(lǐng)導(dǎo)者,如圖2所示.領(lǐng)導(dǎo)者可以是整個(gè)系統(tǒng)的管理者、主副本或是分布式事務(wù)的協(xié)調(diào)者.領(lǐng)導(dǎo)者往往是全局唯一的,并且能被所有節(jié)點(diǎn)感知到的節(jié)點(diǎn),選領(lǐng)導(dǎo)者的問題是分布式節(jié)點(diǎn)就“領(lǐng)導(dǎo)者信息”達(dá)成一致的問題.根據(jù)選舉規(guī)則的不同,選舉可分為“不基于節(jié)點(diǎn)狀態(tài)”和“基于節(jié)點(diǎn)狀態(tài)”的兩類.若領(lǐng)導(dǎo)者的選取,對(duì)節(jié)點(diǎn)的狀態(tài)和功能無特殊要求,可選取任意活躍的節(jié)點(diǎn)成為領(lǐng)導(dǎo)者,選舉則是“不基于節(jié)點(diǎn)狀態(tài)”的.“不基于節(jié)點(diǎn)狀態(tài)”的選舉,可以采取Raft中“先到先得”,或是欺負(fù)算法和環(huán)算法[16]中“進(jìn)程號(hào)最大優(yōu)先”的策略來制定選舉規(guī)則.若選舉需要考量節(jié)點(diǎn)的狀態(tài),即對(duì)節(jié)點(diǎn)的狀態(tài)、通信狀況和功能等有一定的要求時(shí),往往需要采取基于消息傳遞的一致性算法,比如Paxos算法,讓競(jìng)選者通過消息交互,針對(duì)某些屬性值進(jìn)行較量,來進(jìn)行選舉.

圖2 主節(jié)點(diǎn)選舉Fig.2Election of the master-node

日志同步,或稱為日志數(shù)據(jù)的復(fù)制,用于主備節(jié)點(diǎn)之間同步更新操作的序列,如圖3所示.主節(jié)點(diǎn)將更新操作以日志記錄的方式發(fā)送給備份節(jié)點(diǎn),備節(jié)點(diǎn)通過執(zhí)行這些日志記錄中的更新操作,達(dá)到和主節(jié)點(diǎn)一致的狀態(tài).主備節(jié)點(diǎn)的日志記錄必須是相同和確定的,日志同步問題即是分布式節(jié)點(diǎn)就“每個(gè)日志號(hào)對(duì)應(yīng)的日志內(nèi)容”達(dá)成一致的問題.主備節(jié)點(diǎn)的日志同步,主要包括兩種策略,立即復(fù)制(Eager replication)和延遲復(fù)制(Lazy replication)[17].立即復(fù)制將同步到備機(jī)的操作并入事務(wù)的更新操作中,在立即復(fù)制模式下,主節(jié)點(diǎn)需要收到備份節(jié)點(diǎn)關(guān)于日志同步操作的回復(fù)之后,才能提交事務(wù)并答復(fù)客戶端,確保已提交的事務(wù)在備節(jié)點(diǎn)中一定有相應(yīng)的日志記錄,實(shí)現(xiàn)主備節(jié)點(diǎn)之間的強(qiáng)一致性.在延遲復(fù)制的模式下,主節(jié)點(diǎn)執(zhí)行更新操作,同時(shí)異步地向所有備機(jī)發(fā)送日志,主節(jié)點(diǎn)不用等到備機(jī)回復(fù)即可提交事務(wù).

圖3 日志同步Fig.3Log synchronization

2.2 新型DBMS中分布式一致性的實(shí)現(xiàn)

為了實(shí)現(xiàn)系統(tǒng)的高可用性,分布式一致性協(xié)議已經(jīng)被廣泛地應(yīng)用到很多成熟的數(shù)據(jù)庫產(chǎn)品中,本節(jié)通過介紹Google Spanner和OceanBase系統(tǒng)中處理分布式事務(wù)、主節(jié)點(diǎn)選舉和日志同步的設(shè)計(jì)思路,來分析新型分布式數(shù)據(jù)庫系統(tǒng)的高可用策略,并在表2中呈現(xiàn)結(jié)論.

表2 主流數(shù)據(jù)庫系統(tǒng)的高可用策略Tab.2High availability strategies for popular database systems

Spanner[18]是由Google公司研發(fā)的一個(gè)全球分布式的、多版本、支持同步復(fù)制的可擴(kuò)展數(shù)據(jù)庫.采用兩階段提交協(xié)議來協(xié)調(diào)分布式事務(wù)的提交,主節(jié)點(diǎn)選舉和日志同步都是基于Paxos算法的.Spanner以基于時(shí)間戳的方式實(shí)現(xiàn)了數(shù)據(jù)讀寫的全局一致性,在TrueTime API提供的精確時(shí)間戳的基礎(chǔ)上,通過Paxos選舉產(chǎn)生領(lǐng)導(dǎo)者來協(xié)調(diào)、管理事務(wù)提交的絕對(duì)時(shí)間和提交次序,進(jìn)而保證數(shù)據(jù)的讀寫一致性.關(guān)于日志同步,主節(jié)點(diǎn)向多個(gè)備份節(jié)點(diǎn)同步redo日志,同步流程和Paxos的兩個(gè)階段類似,通過Paxos協(xié)議保證主備節(jié)點(diǎn)之間日志序列的確定性和一致性,從而保證數(shù)據(jù)在多個(gè)副本上是一致的.

OceanBase[19-21]是由阿里集團(tuán)研發(fā)的支持海量數(shù)據(jù)、可擴(kuò)展的高性能分布式數(shù)據(jù)庫.開源版本OceanBase 0.4.2中,借助第三方軟件Linux HA來進(jìn)行主備切換,Linux HA通過心跳監(jiān)控集群管理節(jié)點(diǎn)(集群管理節(jié)點(diǎn)是整個(gè)集群的管理者和協(xié)調(diào)者,管理系統(tǒng)中的所有節(jié)點(diǎn),并維護(hù)元數(shù)據(jù)表的信息),一旦檢測(cè)到主集群管理節(jié)點(diǎn)故障Linux HA會(huì)將Vip漂移到備份的集群管理節(jié)點(diǎn),來實(shí)現(xiàn)主備節(jié)點(diǎn)的切換.OceanBase 0.4.2的日志同步使用的是主備復(fù)制的模型,日志同步發(fā)生在主備事務(wù)管理節(jié)點(diǎn)之間.OceanBase系統(tǒng)執(zhí)行更新操作時(shí),主事務(wù)管理節(jié)點(diǎn)需要將操作日志發(fā)送到備機(jī),備份事務(wù)管理節(jié)點(diǎn)通過回放操作日志達(dá)到和主事務(wù)管理節(jié)點(diǎn)一致的數(shù)據(jù)庫狀態(tài). OceanBase 0.4.2同樣是通過兩階段提交協(xié)議來協(xié)調(diào)分布式事務(wù)的提交.

Cedar[22]和CBase都是在OceanBase 0.4.2基礎(chǔ)上研發(fā)的分布式數(shù)據(jù)庫系統(tǒng).考慮到Ocean-Base 0.4.2中的主備集群管理節(jié)點(diǎn)的切換機(jī)制不夠靈活(需借助第三方工具LinuxHA),并且主備事務(wù)管理節(jié)點(diǎn)之間日志不是強(qiáng)同步的,Cedar設(shè)計(jì)并實(shí)現(xiàn)了支持三集群架構(gòu)、基于Paxos的主節(jié)點(diǎn)選舉和日志強(qiáng)同步.CBase中的主節(jié)點(diǎn)選舉采取的是LEBR算法,日志同步采取的是MTS算法,LEBR和MTS算法[23]與Raft算法中的領(lǐng)導(dǎo)者選舉、日志同步相類似,是Raft算法在工程實(shí)踐中的一種優(yōu)化.Cedar采取三集群的架構(gòu),即一個(gè)主集群,兩個(gè)備集群,當(dāng)主集群故障時(shí),會(huì)觸發(fā)選舉,其中一個(gè)備集群可自動(dòng)地切換為主集群,實(shí)現(xiàn)自動(dòng)容錯(cuò),并繼續(xù)對(duì)外提供服務(wù). CBase采取“一個(gè)邏輯大集群、多個(gè)物理小集群”的部署架構(gòu),系統(tǒng)中有一個(gè)主集群管理節(jié)點(diǎn),多個(gè)備用管理節(jié)點(diǎn),當(dāng)主管理節(jié)點(diǎn)故障時(shí),主節(jié)點(diǎn)選舉會(huì)被觸發(fā),系統(tǒng)會(huì)自動(dòng)地從多個(gè)備用管理節(jié)點(diǎn)中選舉出新的主管理節(jié)點(diǎn),來接管集群.Cedar和CBase的日志同步都是強(qiáng)同步、強(qiáng)一致的,主事務(wù)管理節(jié)點(diǎn)需要將日志同步到多數(shù)派備用事務(wù)管理節(jié)點(diǎn),并接收到多數(shù)派的回復(fù)后才可以提交事務(wù).

3 高可用系統(tǒng)中一致性協(xié)議的應(yīng)用分析

不同的分布式一致性協(xié)議在具體應(yīng)用過程中,會(huì)有不同的代價(jià)開銷.本節(jié)將從消息數(shù)目和延遲兩個(gè)方面對(duì)一致性協(xié)議進(jìn)行代價(jià)分析,并結(jié)合生產(chǎn)環(huán)境中存在的異常干擾因素,分析一致性協(xié)議的局限性.

3.1 一致性協(xié)議的代價(jià)分析

設(shè)定系統(tǒng)中有N個(gè)節(jié)點(diǎn),其中1個(gè)為主節(jié)點(diǎn),其他N-1個(gè)節(jié)點(diǎn)為主節(jié)點(diǎn)的備份節(jié)點(diǎn),各個(gè)節(jié)點(diǎn)之間通信狀況良好并且不存在拜占庭故障[24].本節(jié)的后續(xù)分析都基于上述設(shè)定,并通過表3簡要呈現(xiàn)了本節(jié)探究工作的結(jié)論.

表3 分布“一致性算法的代價(jià)估計(jì)Tab.3Cost estimation of the distributed consensus algorithms

結(jié)論1運(yùn)用兩階段提交協(xié)議,使得各個(gè)節(jié)點(diǎn)就某個(gè)決議達(dá)成一致,需要的消息數(shù)目為3N-3,消息延遲為3次.

預(yù)提交階段,協(xié)調(diào)者向系統(tǒng)中所有參與者發(fā)送預(yù)提交請(qǐng)求,消息數(shù)目為N-1.當(dāng)參與者接收到協(xié)調(diào)者發(fā)來的預(yù)提交請(qǐng)求后,會(huì)向協(xié)調(diào)者進(jìn)行回復(fù),消息數(shù)目為N-1.如果協(xié)調(diào)者收集到所有參與者針對(duì)預(yù)提交請(qǐng)求的回復(fù),可向系統(tǒng)中所有參與者發(fā)送提交請(qǐng)求,消息數(shù)目為N-1.至此,協(xié)調(diào)者已做出提交決定,并且已經(jīng)和參與者達(dá)成一致.綜上,協(xié)調(diào)者和參與者達(dá)成一致需要的消息數(shù)目為3N-3,消息延遲為3次[25].

結(jié)論2運(yùn)用Quorum策略,使得各個(gè)節(jié)點(diǎn)就某個(gè)決議達(dá)成一致,需要的消息數(shù)目為2R(NWR機(jī)制中參數(shù)R的取值)或2W(NWR機(jī)制中參數(shù)W的取值),消息延遲為2次.

Quorum策略的NWR機(jī)制在第一章中已經(jīng)具體介紹過,基于Quorum策略,執(zhí)行讀操作時(shí),需要至少讀取R個(gè)副本,執(zhí)行寫操作需要至少在W個(gè)副本上更新成功.分析可知,進(jìn)行讀操作,客戶端需要詢問R個(gè)副本,R個(gè)副本接收到客戶端的讀操作請(qǐng)求時(shí)會(huì)對(duì)客戶端進(jìn)行回復(fù),需要的總的消息數(shù)目為2R,消息延遲為兩次;進(jìn)行寫操作時(shí),客戶端將寫操作的請(qǐng)求發(fā)送到W個(gè)副本,W個(gè)副本執(zhí)行該寫請(qǐng)求并對(duì)客戶端進(jìn)行應(yīng)答,需要的消息數(shù)目為2W,消息延遲為兩次.

結(jié)論3運(yùn)用Paxos算法,使得各個(gè)節(jié)點(diǎn)就某個(gè)決議達(dá)成一致,需要的消息數(shù)目為2k×N,消息延遲為4次.

假設(shè)系統(tǒng)中有k個(gè)提案者,提案階段,提案者(proposer)向系統(tǒng)中多數(shù)派節(jié)點(diǎn)發(fā)送提案請(qǐng)求,消息數(shù)目為,當(dāng)接受者(acceptor)接收到提案請(qǐng)求時(shí),會(huì)向提案者進(jìn)行承諾(具體可參考第一章Paxos算法的介紹),消息數(shù)目為.在接受階段,提案者向多數(shù)派節(jié)點(diǎn)發(fā)送決議,消息數(shù)目為,接受者接收到?jīng)Q議值時(shí),會(huì)對(duì)提案者進(jìn)行回復(fù),消息數(shù)目為.可知,總共需要的消息數(shù)目為2k×N,消息延遲為4次.

結(jié)論4運(yùn)用Raft算法,使得各個(gè)節(jié)點(diǎn)就某項(xiàng)決議達(dá)成一致,選舉leader需要的消息數(shù)目為(k+1)×N一2k,消息延遲為2次,日志同步需要的消息數(shù)目為3N一3,消息延遲為3次.

Raft算法將節(jié)點(diǎn)之間達(dá)成一致的問題分為了領(lǐng)導(dǎo)者選舉和日志同步兩個(gè)獨(dú)立的子問題.領(lǐng)導(dǎo)者選舉過程中,假設(shè)有k個(gè)候選者(candidate),候選者向系統(tǒng)中所有的參與者(follower)發(fā)送投票請(qǐng)求,消息數(shù)目為k×(N一1).參與者接收到候選者的投票請(qǐng)求后,會(huì)向候選者進(jìn)行投票回復(fù),消息數(shù)目為N一k.可知,總共需要的消息數(shù)目為(k+1)×N一2k,消息延遲為2次.

對(duì)于領(lǐng)導(dǎo)者和參與者之間的日志同步,領(lǐng)導(dǎo)者需要將日志發(fā)送給系統(tǒng)中所有參與者,消息數(shù)目為N一1.參與者接收到日志信息后,向Leader進(jìn)行回復(fù),消息數(shù)目為N一1.當(dāng)領(lǐng)導(dǎo)者接收到多數(shù)派參與者關(guān)于某條日志的應(yīng)答消息后,會(huì)提交該日志,將提交日志號(hào)寫入下一批日志記錄中,發(fā)送給參與者,消息數(shù)目為N一1.可知,總共需要的消息數(shù)目為3N一3,消息延遲為3次.

結(jié)論5運(yùn)用LEBR算法,選舉Leader需要的消息數(shù)目為(k+3)×N一2k一2,消息延遲為4次.

LEBR算法將主節(jié)點(diǎn)的選舉分為了投票和廣播兩個(gè)階段,假設(shè)共有k個(gè)備選者(Candidate).投票階段,備選者會(huì)向所有追隨者(Follower)發(fā)送投票請(qǐng)求,消息數(shù)目為k×(N一1).參與者接收到備選者的投票請(qǐng)求后,會(huì)向候選者進(jìn)行投票回復(fù),消息數(shù)目為N一k.在廣播階段,獲得多數(shù)派支持票的備選者可以向所有的追隨者發(fā)送廣播請(qǐng)求,消息數(shù)目為N一1,追隨者接收到備選者的當(dāng)選廣播請(qǐng)求時(shí),會(huì)更新領(lǐng)導(dǎo)者的信息,并對(duì)備選者進(jìn)行回復(fù),消息數(shù)目為N一1,接收到多數(shù)派追隨者對(duì)于當(dāng)選廣播的回復(fù)后,備選者才會(huì)進(jìn)行身份切換,成為領(lǐng)導(dǎo)者,至此,選舉結(jié)束.可知,總共需要的消息數(shù)目為(k+3)×N一2k一2,消息延遲為4次.

結(jié)論6運(yùn)用MTS算法,使得主備事務(wù)節(jié)點(diǎn)就某條日志信息達(dá)成一致,需要的消息數(shù)目為3N-3,消息延遲為3次.

MTS算法中,進(jìn)行一次日志同步,主TNode首先需要將日志發(fā)送給系統(tǒng)中所有備TNode,消息數(shù)目為N一1.備TNode接收到日志信息后,向主TNode進(jìn)行響應(yīng),消息數(shù)目為N一1.當(dāng)主TNode接收到多數(shù)派備TNode關(guān)于某條日志的應(yīng)答消息后,會(huì)提交該日志,將提交日志號(hào)寫入下一批日志記錄中,發(fā)送給參與者,消息數(shù)目為N一1.可知,總共需要的消息數(shù)目為3N一3,消息延遲為3次.

3.2 分布式一致性協(xié)議的應(yīng)用局限性分析

分布式一致性協(xié)議都不可避免得具有一定的局限性.實(shí)際的系統(tǒng)需要從工程角度,針對(duì)不同的應(yīng)用場(chǎng)景,對(duì)協(xié)議進(jìn)行一些調(diào)整和優(yōu)化.

兩階段提交協(xié)議在運(yùn)用到實(shí)際系統(tǒng)中時(shí),若出現(xiàn)了協(xié)調(diào)者宕機(jī)或是協(xié)調(diào)者和參與者網(wǎng)絡(luò)通信故障,系統(tǒng)會(huì)進(jìn)入阻塞狀態(tài).阻塞問題已經(jīng)在表1中詳細(xì)介紹,此處不再贅述.在系統(tǒng)實(shí)現(xiàn)過程中,往往通過引入“超時(shí)機(jī)制”和“多副本機(jī)制”解決阻塞問題,超時(shí)機(jī)制保證節(jié)點(diǎn)不會(huì)永久等待,多副本機(jī)制消除了單節(jié)點(diǎn)故障導(dǎo)致的系統(tǒng)阻塞.

基于Quorum算法的NWR機(jī)制,由于支持多副本并發(fā)更新,會(huì)出現(xiàn)多副本之間日志順序不一致的問題.以至于執(zhí)行讀操作時(shí),從R個(gè)副本中讀取數(shù)據(jù)會(huì)出現(xiàn)沖突.所以將Quorum算法運(yùn)用到實(shí)際系統(tǒng)中時(shí),需要在上層增加一些應(yīng)用來協(xié)調(diào)多副本寫入順序不同的沖突.

Paxos算法支持多個(gè)Proposer交替發(fā)起提案,可能會(huì)出現(xiàn)長期無法就某個(gè)提案達(dá)成一致的情形(論文中提到的局限性).所以在系統(tǒng)實(shí)現(xiàn)過程中,往往會(huì)先選出一個(gè)主副本,每次僅由主副本發(fā)起提案請(qǐng)求,避免交替提案的情況發(fā)生.

Raft算法中的領(lǐng)導(dǎo)者選舉策略在實(shí)際運(yùn)用過程中,可能會(huì)出現(xiàn)“雙領(lǐng)導(dǎo)者”和“頻繁選主”的問題.“雙領(lǐng)導(dǎo)者”指系統(tǒng)中出現(xiàn)了兩個(gè)領(lǐng)導(dǎo)者,而“頻繁選主”指的是領(lǐng)導(dǎo)者不合理得頻繁發(fā)生變化.引發(fā)上述兩個(gè)問題的原因是分布式環(huán)境中的網(wǎng)絡(luò)通信故障.當(dāng)選定的領(lǐng)導(dǎo)者和其他伴隨者處于兩個(gè)不同的網(wǎng)絡(luò)分區(qū)中,相互之間無法通信時(shí),其他的伴隨者可能會(huì)因?yàn)槌瑫r(shí)從而選出新的領(lǐng)導(dǎo)者,舊領(lǐng)導(dǎo)者感知不到這一切的發(fā)生,依然嘗試著給所有伴隨者發(fā)送心跳信息,此時(shí)B出現(xiàn)了“雙領(lǐng)導(dǎo)者”.若某個(gè)伴隨者和領(lǐng)導(dǎo)者通信不上,由于接收不到領(lǐng)導(dǎo)者的心跳,該伴隨者會(huì)認(rèn)為系統(tǒng)中沒有領(lǐng)導(dǎo)者存在,從而增大選舉期(Term)的值發(fā)起選舉操作.一旦該伴隨者得到多數(shù)派節(jié)點(diǎn)的支持,它將成為領(lǐng)導(dǎo)者.而舊領(lǐng)導(dǎo)者接收到其他參與者的反饋的選舉期信息,發(fā)現(xiàn)自己選舉期的值較小,將切換身份變?yōu)樽冯S者,切換為追隨者的舊領(lǐng)導(dǎo)者由于接收不到新領(lǐng)導(dǎo)者的心跳(通信故障依然存在),很可能再次發(fā)起選舉并贏得選舉,系統(tǒng)就進(jìn)入了“頻繁換主”的不穩(wěn)定狀態(tài).“雙領(lǐng)導(dǎo)者”和“頻繁選主”在實(shí)際生產(chǎn)環(huán)境中是很容易發(fā)生的兩個(gè)不合理狀態(tài),所以,真正將Raft運(yùn)用到實(shí)際系統(tǒng)中時(shí),需要額外增加一些策略,例如CBase中就通過增加“租約機(jī)制”和“廣播階段”等策略來規(guī)避”頻繁選主“和”雙領(lǐng)導(dǎo)者“兩個(gè)異常狀況.

4 總結(jié)與展望

分布式一致性協(xié)議是實(shí)現(xiàn)數(shù)據(jù)庫系統(tǒng)高可用性的基礎(chǔ).本文梳理和分析了流行的分布式一致性協(xié)議的特點(diǎn)、代價(jià)開銷以及應(yīng)用局限性,并借助一些成熟的數(shù)據(jù)庫系統(tǒng)來介紹生產(chǎn)實(shí)踐中如何通過分布式一致性協(xié)議來實(shí)現(xiàn)分布式事務(wù)提交、主節(jié)點(diǎn)選舉和日志同步.隨著數(shù)據(jù)規(guī)模的不斷擴(kuò)大,使用分布式數(shù)據(jù)庫系統(tǒng)是必然的發(fā)展趨勢(shì).未來的研究工作,將基于學(xué)界和工業(yè)界已有的分布式一致性理論和成熟的數(shù)據(jù)庫產(chǎn)品,探究并設(shè)計(jì)普適和完整的高可用方案來解決分布式數(shù)據(jù)庫系統(tǒng)中的一致性和可用性問題.

［1］LAMPSON B W.How to build a highly available system using consensus[C]//International Workshop on Distributed Algorithms.Springer-Verlag,1996:1-17.

［2］GILBERT S,LYNCH N.Brewer’s conjecture and the feasibility of consistent,available,partition-tolerant web services[J].Acm Sigact News,2002,33(2):51-59.

［3］BREWER E A.Towards robust distributed systems(abstract)[C]//Nineteenth ACM Symposium on Principles of Distributed Computing.ACM,2007:7.

［4］GRAY J N.Notes on data base operating systems[C]//Advanced Course:Operating Systems.Springer-Verlag, 1978:393-481.

［5］MOHAN C,LINDSAY B,OBERMARCK R.Transaction management in the R*distributed database management system[J].ACM Transactions on Database Systems,1986,11(4):378-396.

［6］LAMPSONBW,LOMETDB.ANewPresumedCommitOptimizationforTwoPhaseCommit[C]//International Conference on Very Large Data Bases.Morgan Kaufmann Publishers Inc,1993:630-640.

［7］LAMPORT L.Paxos made simple[J].AcmSigact News,2001,32(4):1-11.

［8］CHANDRA T D,GRIESEMER R,REDSTONE J.Paxos made live:An engineering perspective[C]//Twenty-Sixth ACM Symposium on Principles of Distributed Computing.ACM,2007:398-407.

［9］LAMPORT L.The part-time parliament[J].Acm Transactions on Computer Systems,1998,16(2):133-169.

［10］SKEEN D.Nonblocking commit protocols[C]//ACM SIGMOD International Conference on Management of Data, Ann Arbor,Michigan,April 29-May.1981:133-142.

［11］GIFFORD D K.Weighted voting for replicated data[C]//ACM Symposium on Operating Systems Principles. ACM,1979:150-162.

［12］LAMPORT L B,MASSA M T.Cheap paxos:IEEE,US 7249280 B2[P].2007.

［13］LAMPORT L.Fast Paxos[J].Distributed Computing,2005,19(2):79-103.

［14］LAMPORT L,MALKHI D,ZHOU L,et al.Vertical paxos and primary-backup replication[C]//Principles of Distributed Computing,2009:312-313.

［15］ONGARO D,OUSTERHOUT J.In search of an understandable consensus algorithm[R/OL].[2016-07-07]. https://ramcloud.atlassian.net/wiki/download/attachments/6586375/raft.pdf

［16］COULOURIS G,DOLLIMORE J,KINDBERG Tet al.Distrinbuted Systems Concepts and Design[M].5版.北京:機(jī)械工業(yè)出版社,2015:378-380.

［17］GRAY J.The dangers of replication and a solution[J].AcmSigmod Record,1996,25(2):173-182.［18］CORBETT J C,DEAN J,EPSTEIN M P,et al.Spanner:Google’s globally-distributed database[C].Operating Systems Design and Implementation,2012:251-264.

［19］陽振坤.OceanBase關(guān)系數(shù)據(jù)庫架構(gòu)[J].華東師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2014(5):141-148.

［20］李凱,韓富最.OceanBase內(nèi)存事務(wù)引擎[J].華東師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2014(5):149-163.

［21］楊傳輝.OceanBase高可用方案[J].華東師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2014(5):173-179.

［22］張晨東,郭進(jìn)偉,劉柏眾,等.基于Raft一致性協(xié)議的高可用性實(shí)現(xiàn)[J].華東師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2015(5):172-184.

［23］龐天澤.可擴(kuò)展數(shù)據(jù)管理系統(tǒng)中的高可用性實(shí)現(xiàn)[D].上海:華東師范大學(xué)計(jì)算機(jī)科學(xué)與軟件工程學(xué)院.2016.

［24］LAMPORT L,SHOSTAK R,PEASE M.The byzantine generals problem[J].Acm Transactions on Programming Languages&Systems,1995,4(3):382-401.

［25］GRAY J,LAMPORT L.Consensus on transaction commit[J].Acm Transactions on Database Systems,2010, 31(1):133-160.

(責(zé)任編輯:李萬會(huì))

On the distributed consensus protocol in high-availability database systems

CHU Jia-jia,GUO Jin-wei,LIU Bo-zhong,ZHANG Chen-dong,QIAN Wei-ning
(Institute for Data Science and Engineering,East China Normal University, Shanghai200062,China)

Availability and consistency are the two important characteristics of the distributed database systems,which need to be guaranteed by the distributed consensus protocol.Ensuring consistency requires a consensus protocol to determine a global execution sequence for concurrent transaction updates,and to coordinate the consistency between local states and the global state continuously.For the implementation of the availability,we need to coordinate the consistency between the multiple backups to achieve the seamless switch between the main and backup nodes.Visible,distributed consistency protocol is the basis for the realization of high availability database system.Distributed consensus protocol is the base of high availability database systems.This paper summarizes the classical consistency protocols and the main applications in high-availability systems of the distributed consistency protocols.Meanwhile,the implementation costs and limitations of the consistency protocols are analyzed and evaluated.

high availability;consistency;distributed consensus protocol;distributed database

TP392

A

10.3969/j.issn.1000-5641.2016.05.001

1000-5641(2016)05-0001-09

2016-05

國家自然科學(xué)基金重點(diǎn)項(xiàng)目(61332006);國家863計(jì)劃項(xiàng)目(2015AA015307)

儲(chǔ)佳佳,女,博士研究生,研究方向?yàn)閿?shù)據(jù)庫系統(tǒng).E-mail:cjj25233@163.com.

錢衛(wèi)寧,男,教授,博士生導(dǎo)師,研究方向?yàn)樯缃幻襟w數(shù)據(jù)管理與分析、互聯(lián)網(wǎng)環(huán)境的數(shù)據(jù)管理與基準(zhǔn)評(píng)測(cè)、基于開放信息的知識(shí)圖譜構(gòu)建與利用等. E-mail:wnqian@sei.ecnu.edu.cn.