分布式系統(tǒng)原理介紹

分布式系統(tǒng)原理介紹前言 11概念 21.1模型 21.1.1節(jié)點(diǎn) 21.1.2通信 21.1.3存儲(chǔ) 21.1.4異常 31.2副本 81.2.1副本的概念 81.2.2副本一致性 81.3衡量分布式系統(tǒng)的指標(biāo) 91.3.1性能 91.3.2可用性 91.3.3可擴(kuò)展性 91.3.4一致性 102分布式系統(tǒng)原理 112.1數(shù)據(jù)分布方式 112.1.1哈希方式 112.1.2按數(shù)據(jù)范圍分布 132.1.3按數(shù)據(jù)量分布 142.1.4一致性哈希 142.1.5副本與數(shù)據(jù)分布 162.1.6本地化計(jì)算 182.1.7數(shù)據(jù)分布方式的選擇 182.1.8工程投影 182.2基本副本協(xié)議 202.2.1中心化副本控制協(xié)議 202.2.2primary-secondary協(xié)議 20 2.2.4工程投影 242.3Lease機(jī)制 26 2.3.2lease機(jī)制的分析 28 2.3.5工程投影 302.4Quorum機(jī)制 332.4.1約定 332.4.2Write-all-read-one 332.4.3Quorum定義 34 2.4.6工程投影 372.5日志技術(shù) 41 2.5.3NoUndo/NoRedolog 432.5.4工程投影 442.6兩階段提交協(xié)議 452.6.1問(wèn)題背景 452.6.2流程描述 452.6.3異常處理 472.6.4協(xié)議分析 49 C 2.7.3工程投影 52 2.8.1簡(jiǎn)介 532.8.2協(xié)議描述 532.8.3實(shí)例 552.8.4競(jìng)爭(zhēng)及活鎖 582.8.5協(xié)議推導(dǎo) 592.8.6工程投影 61 2.9.1定義 66P 2.9.3協(xié)議分析 663參考資料 691前言著重分析第二部分中的理論是如何被綜合運(yùn)用在這些真實(shí)的分布式系統(tǒng)中的。在具體寫作時(shí)，筆者度橫向分析這些系統(tǒng)的特點(diǎn)。在分布式層面的協(xié)議和算法設(shè)計(jì)，開(kāi)發(fā)分布式系統(tǒng)所需要的其他方面的知識(shí)與技術(shù)則不在本文的討意見(jiàn)和建議。21.1模型系統(tǒng)的全貌做了比較詳細(xì)的介紹[1][2]。為了控制規(guī)模，討論。本文盡量精簡(jiǎn)分布式系統(tǒng)模型是為了控制問(wèn)題的規(guī)模。限圖1-1本文的分布式系統(tǒng)模型點(diǎn)是指一個(gè)可以獨(dú)立按照分布式協(xié)議完成一組邏輯的程序個(gè)體。在具體的工程項(xiàng)目中，一個(gè)點(diǎn)與節(jié)點(diǎn)之間是完全獨(dú)立、相互隔離的，節(jié)點(diǎn)之間傳遞信息的唯一方式是通過(guò)不可靠的網(wǎng)絡(luò)進(jìn)行通信。即一個(gè)節(jié)點(diǎn)可以向其他節(jié)點(diǎn)通過(guò)網(wǎng)絡(luò)發(fā)送消息，但發(fā)送消息的節(jié)點(diǎn)無(wú)法確認(rèn)消息是否被節(jié)點(diǎn)可以通過(guò)將數(shù)據(jù)寫入與節(jié)點(diǎn)在同一臺(tái)機(jī)器的本地存儲(chǔ)設(shè)備保存數(shù)據(jù)。通常的存儲(chǔ)設(shè)備有磁3有狀態(tài)節(jié)點(diǎn)。上節(jié)點(diǎn)不能正常工作。假設(shè)節(jié)點(diǎn)的工作流程是三個(gè)獨(dú)立原子的步驟，宕機(jī)造成的后果是節(jié)在任何時(shí)刻都可能發(fā)生宕機(jī)，從而造成某些協(xié)議流程無(wú)法完成。后，機(jī)器上的節(jié)點(diǎn)可以重新啟動(dòng)，但節(jié)點(diǎn)將失去所有的內(nèi)存信息。在某些分布式系統(tǒng)中，節(jié)點(diǎn)可以通過(guò)讀取本地存儲(chǔ)設(shè)備中的信息或通過(guò)讀取其他節(jié)點(diǎn)數(shù)據(jù)的方式恢復(fù)內(nèi)存信息，從而恢復(fù)到某一宕able為宕機(jī)恢復(fù)。圖1-1中虛線節(jié)點(diǎn)表示宕機(jī)的節(jié)點(diǎn)。不可靠的網(wǎng)絡(luò)進(jìn)行通信。、設(shè)備異常等情況時(shí)，都可能發(fā)生發(fā)送的數(shù)據(jù)丟失。由于數(shù)據(jù)丟失的情況。絡(luò)質(zhì)量的不同，網(wǎng)絡(luò)消息丟失的概率也不同，甚至可能出現(xiàn)在一段時(shí)間內(nèi)某些節(jié)點(diǎn)之間4節(jié)點(diǎn)之間始終無(wú)法正常通信，則稱這種特殊的網(wǎng)絡(luò)異常為“網(wǎng)絡(luò)分化”(networkpartition)。網(wǎng)絡(luò)分化是一類常見(jiàn)的網(wǎng)絡(luò)異常，尤其當(dāng)分布式系統(tǒng)部署在多個(gè)機(jī)房之間時(shí)。圖1-1中，用虛線分割了兩特網(wǎng)用戶都可以正常訪問(wèn)兩個(gè)機(jī)房?jī)?nèi)對(duì)外服務(wù)節(jié)點(diǎn)。本文后續(xù)將討論出現(xiàn)這種嚴(yán)重的網(wǎng)絡(luò)分化時(shí)，式系統(tǒng)的設(shè)計(jì)帶來(lái)的巨大挑戰(zhàn)。節(jié)點(diǎn)發(fā)送的網(wǎng)絡(luò)消息有一定的概率不是按照發(fā)送時(shí)的順序依次到達(dá)目的節(jié)點(diǎn)。通設(shè)計(jì)分布式協(xié)議時(shí)，考慮使用序列號(hào)等機(jī)制處理網(wǎng)絡(luò)消息的亂序問(wèn)題，使得無(wú)效的、過(guò)期的。以立可靠的傳輸服務(wù)。TCP協(xié)議通過(guò)為傳輸?shù)拿恳粋€(gè)字節(jié)設(shè)置TCPTCP的校驗(yàn)和從而檢查數(shù)據(jù)錯(cuò)TCP制極大的提高了傳輸性能，解決了網(wǎng)絡(luò)傳輸?shù)臅r(shí)延P態(tài)感知底層鏈路的帶寬加以合理使用并與其他TCP鏈接分享帶寬(TCPfriendly)。CPCP5TCP能被丟失從而無(wú)法被目標(biāo)節(jié)點(diǎn)正確處理。更有甚者，在PPTCPTCP發(fā)送的消息就一定處理。P概念。在單機(jī)系統(tǒng)中，我們調(diào)用。RPC(Remoteprocedurecall)調(diào)用，即某個(gè)節(jié)6成功處理請(qǐng)求成功處理請(qǐng)求RPC請(qǐng)求成功處理請(qǐng)求成功處理請(qǐng)求RPC請(qǐng)求RPCRPC請(qǐng)求ver圖1-2RPC執(zhí)行成功但超時(shí)的例子C后續(xù)本文中，如果說(shuō)明“不成功”即指“失敗”或“超時(shí)”兩種狀態(tài)之一。如果說(shuō)明“失敗”失指節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)不可被讀取或讀取出的數(shù)據(jù)錯(cuò)誤。數(shù)據(jù)丟失是另一類常見(jiàn)的異常。O，幾十秒恢復(fù)了，如此交替。又例如網(wǎng)絡(luò)不穩(wěn)定時(shí)也會(huì)引起“半死不活”異常，例如網(wǎng)絡(luò)發(fā)生嚴(yán)重7驟時(shí)一旦發(fā)生各種異常的情況下系統(tǒng)的處理方式及造成的影響。單的流程可能遇到各種異常且不能正確處理：第一、當(dāng)前需要發(fā)送的整數(shù)沒(méi)有持久化，為了說(shuō)明異常分析的基本方法。，在系統(tǒng)設(shè)計(jì)時(shí)不能放過(guò)任何異常情況。常容易出問(wèn)題的一種思路是認(rèn)為某種異常出現(xiàn)的概率非常小以至于可以忽略不計(jì)。這次，每次請(qǐng)求都要執(zhí)行有異常風(fēng)險(xiǎn)的流程，那么系統(tǒng)每天發(fā)生這種異常的概率就為1?(1?81.2副本副本(replica/copy)指在分布式系統(tǒng)中為數(shù)據(jù)或服務(wù)提供的冗余。對(duì)于數(shù)據(jù)副本指在不同的節(jié)分布式系統(tǒng)解決數(shù)據(jù)丟失異常的唯一手段。另一類副本是服務(wù)副本，指數(shù)個(gè)節(jié)點(diǎn)提供某種相同服務(wù)，這種服務(wù)一般并不依賴于節(jié)點(diǎn)的本地存儲(chǔ)，其所需數(shù)據(jù)一般來(lái)自其他節(jié)點(diǎn)。致性的強(qiáng)弱即約束條件的不同苛刻程度，副本一致性分為若干變種或者級(jí)別，本文挑選strongconsistency一次成功更新的副本數(shù)個(gè)用戶在這次會(huì)話過(guò)程中不會(huì)再讀到比這個(gè)值更舊的值。會(huì)話一致性通過(guò)引入會(huì)話的概念，在單同用戶間的一致性和同一用戶不同會(huì)話間的一致性沒(méi)有保障。實(shí)踐中有許多機(jī)制正好對(duì)應(yīng)會(huì)話的n9最終一致性(eventualconsistency)：最終一致性要求一旦更新成功，各個(gè)副本上的數(shù)據(jù)最終將達(dá)弱一致性(weekconsistency)：一旦某個(gè)更新成功，用戶無(wú)法在一個(gè)確定時(shí)間內(nèi)讀到這次更新的1.3衡量分布式系統(tǒng)的指標(biāo)價(jià)分布式系統(tǒng)有一些常用的指標(biāo)。依據(jù)設(shè)計(jì)需求的不同，分布式系統(tǒng)對(duì)于這些指標(biāo)也有不同無(wú)論是分布式系統(tǒng)還是單機(jī)系統(tǒng)，都會(huì)對(duì)性能(performance)有所要求。對(duì)于不同的系統(tǒng)，不同ailability的系統(tǒng)的可擴(kuò)展性(scalability)指分布式系統(tǒng)通過(guò)擴(kuò)展集群機(jī)器規(guī)模提高系統(tǒng)性能(吞吐、延遲、群規(guī)模取決于系統(tǒng)的性能和任務(wù)的要求。當(dāng)任務(wù)的需求隨著具體業(yè)務(wù)不斷提高時(shí)，除了升級(jí)系統(tǒng)性能，另一個(gè)做法就是通過(guò)增加機(jī)器的方式擴(kuò)展系統(tǒng)的規(guī)模。好的分布式系統(tǒng)總在追求“線性擴(kuò)系統(tǒng)為了提高可用性，總是不可避免的使用副本的機(jī)制，從而引發(fā)副本一致性的問(wèn)題。8127318127312.1數(shù)據(jù)分布方式謂分布式系統(tǒng)顧名思義就是利用多臺(tái)計(jì)算機(jī)協(xié)同解決單臺(tái)計(jì)算機(jī)所不能解決的計(jì)算、存儲(chǔ)等單機(jī)問(wèn)題使用分布式解決，首先要解決的就是如何將問(wèn)題拆解為可以使用多機(jī)分布式解決，使得布式系統(tǒng)中的每臺(tái)機(jī)器負(fù)責(zé)原問(wèn)題的一個(gè)子集。由于無(wú)論是計(jì)算還是存儲(chǔ)，其問(wèn)題輸入對(duì)象都是哈希方式機(jī)器中的機(jī)器建立映射關(guān)系，從而將不同哈希值的數(shù)據(jù)分布到不同的機(jī)器上。所謂數(shù)據(jù)特征可以是keyvaluekey的值。例如，一種常見(jiàn)的哈希方式是按如3)服務(wù)器組成一組，用哈希值除以總的組數(shù)，其余數(shù)為服務(wù)器組的編號(hào)。圖2-1給出了哈希方811273圖2-1哈希方式分?jǐn)?shù)據(jù)哈希方式想象為一個(gè)大的哈希表，每臺(tái)(組)機(jī)器就是一個(gè)哈希表中的桶，數(shù)據(jù)根據(jù)哈到各個(gè)桶上面。式需1117114數(shù)據(jù)需要被遷移并重新分布。工程中，擴(kuò)展哈希分布數(shù)據(jù)的系統(tǒng)時(shí)，往往使得集群規(guī)模成倍擴(kuò)按照數(shù)據(jù)重新計(jì)算哈希，這樣原本一臺(tái)機(jī)器上的數(shù)據(jù)只需遷移一半到另一臺(tái)對(duì)應(yīng)的機(jī)器上即可新機(jī)器上，從而使得擴(kuò)容不再依賴于機(jī)器數(shù)量的成本增長(zhǎng)。這種做法和2.1.2中按數(shù)據(jù)范圍分布數(shù)、2.1.3按數(shù)據(jù)量分布數(shù)據(jù)的有一個(gè)共同點(diǎn)，都需要以較復(fù)雜的機(jī)制維護(hù)大量的元數(shù)據(jù)。skewid戶id的數(shù)據(jù)量異常龐大時(shí)，該用411117圖2-2哈希方式的數(shù)據(jù)傾斜思路是，使用數(shù)據(jù)的全部而不是某些維度的特征計(jì)算哈希，這樣數(shù)據(jù)將被完全打散在集群中。實(shí)踐中有時(shí)并不這樣做，這是因?yàn)檫@樣做使得每個(gè)數(shù)據(jù)之間的關(guān)聯(lián)性完全消失，例如上述例子d2按數(shù)據(jù)范圍分布使得集群中每臺(tái)(組)服務(wù)器處理不同區(qū)間的數(shù)據(jù)。負(fù)責(zé)處理。圖2-3給出這個(gè)例子的示意圖。圖2-3按數(shù)據(jù)范圍分布d固定的閾值之下。與哈希分布數(shù)據(jù)的方式只需要記錄哈希函數(shù)及分桶個(gè)數(shù)(機(jī)器數(shù))不同，按數(shù)據(jù)范圍分布數(shù)據(jù)稱這種數(shù)據(jù)的分布信息為一種元信息。甚至對(duì)于大規(guī)模的集群，由于元信息的規(guī)模非常龐大，單臺(tái)機(jī)器作為元信息服務(wù)器。分區(qū)需要1KB的元信息記錄數(shù)據(jù)分區(qū)情況及副本所在的服務(wù)器。1000臺(tái)服務(wù)器的總存儲(chǔ)量為MMB統(tǒng)中的數(shù)據(jù)類似一個(gè)哈希表。按范圍分?jǐn)?shù)據(jù)的方式則使得從全局看群擴(kuò)容。責(zé)的多元數(shù)據(jù)服務(wù)器機(jī)制解決這個(gè)問(wèn)題。3按數(shù)據(jù)量分布據(jù)量分布數(shù)據(jù)與具體的數(shù)據(jù)特征無(wú)關(guān)，而是將數(shù)據(jù)視為一個(gè)順序增長(zhǎng)的文件，并將這個(gè)文件按照某一較為固定的大小劃分為若干數(shù)據(jù)塊(chunk)，不同的數(shù)據(jù)塊分布到不同的服務(wù)器上。與按數(shù)據(jù)范圍分布數(shù)據(jù)的方式類似的是，按數(shù)據(jù)量分布數(shù)據(jù)也需要記錄數(shù)據(jù)塊的具體分布情況，并將該分布信元數(shù)據(jù)使用元數(shù)據(jù)服務(wù)器管理。題。1.4一致性哈希一致性哈希(consistenthashing)是另一個(gè)種在工程中使用較為廣泛的數(shù)據(jù)分布方式。一致性哈希最初在P2P網(wǎng)絡(luò)中作為分布式哈希表(DHT)的常用數(shù)據(jù)分布算法。一致性哈希的基本方式是使CBCB子的示意圖。9876A22345圖2-4一致性哈希優(yōu)點(diǎn)在于可以任意動(dòng)態(tài)添加、刪除節(jié)點(diǎn)，每次添加、刪除一個(gè)節(jié)點(diǎn)僅影響一致性哈希環(huán)上相鄰的常比按數(shù)據(jù)范圍分布數(shù)據(jù)和按數(shù)據(jù)量分布數(shù)據(jù)的元信息量要小很多。基本的一致性哈希算法有很明顯的缺點(diǎn)，隨機(jī)分布節(jié)點(diǎn)的方式使得很難均勻的分布哈希一個(gè)相鄰節(jié)點(diǎn)分?jǐn)倝毫Αode法中的節(jié)點(diǎn)相同。為每個(gè)節(jié)點(diǎn)分配若干虛節(jié)點(diǎn)。操作數(shù)據(jù)時(shí)，首先通過(guò)數(shù)據(jù).5副本與數(shù)據(jù)分布節(jié)討論了幾種常見(jiàn)的數(shù)據(jù)分布方式，這些討論中沒(méi)有考慮數(shù)據(jù)副本的問(wèn)題。分布式系統(tǒng)可用性的基本手段就是使用副本。對(duì)于數(shù)據(jù)副本的分布方式主要影響系統(tǒng)的可擴(kuò)展性。。圖2-5以機(jī)器為單位的副本的新機(jī)器也可以提供服務(wù)，需要從正常的兩臺(tái)機(jī)器上拷貝數(shù)據(jù)。此種全盤拷貝數(shù)據(jù)一般都較為消T限速較小(例如10MB/s)，往往需要數(shù)天才能夠完成恢復(fù)。種方式不利于系統(tǒng)容錯(cuò)。當(dāng)出現(xiàn)一臺(tái)機(jī)器宕機(jī)時(shí)，該機(jī)器上的原有壓力只能被剩下的副本。實(shí)踐中，常常使得每個(gè)數(shù)據(jù)段的大小盡量相等且控制在一定的大小以內(nèi)。數(shù)據(jù)段有很多不n哈希分?jǐn)?shù)據(jù)的方式，每個(gè)哈希分桶后的余數(shù)可以作為一個(gè)數(shù)據(jù)段，為了控制數(shù)據(jù)段的大小，常常據(jù)量分?jǐn)?shù)據(jù)的方式，可以自然的按照每個(gè)數(shù)據(jù)塊作為數(shù)據(jù)段。對(duì)于一致性哈希分布數(shù)據(jù)的方式，每個(gè)分區(qū)中的數(shù)據(jù)可以作為一個(gè)數(shù)據(jù)段。opqoppqqo圖2-6以數(shù)據(jù)段為單位的副本布與機(jī)器無(wú)關(guān)，數(shù)據(jù)丟失后的恢復(fù)效率將非常高。這是因?yàn)椋坏┠撑_(tái)機(jī)器的數(shù)據(jù)，群中各機(jī)器遷移數(shù)據(jù)，與數(shù)據(jù)恢復(fù)同理，效率也較高。，完全按照數(shù)據(jù)段建立副本會(huì)引起需要管理的元數(shù)據(jù)的開(kāi)銷增大，副本維護(hù)的難度也相適的范圍內(nèi)。.6本地化計(jì)算到此為止都是討論的數(shù)據(jù)分布的方式，容易被理解為僅僅是對(duì)數(shù)據(jù)存儲(chǔ)分布方式的討論。對(duì)于分布式系統(tǒng)而言，除了解決大規(guī)模存儲(chǔ)問(wèn)題更需要解決大規(guī)模的計(jì)算問(wèn)題。然而計(jì)算離不開(kāi)數(shù)據(jù)，計(jì)算的規(guī)模往往與輸入的數(shù)據(jù)量或者計(jì)算產(chǎn)生的中間結(jié)果的數(shù)據(jù)量正相關(guān)。在分布式系統(tǒng)中，的分布方式也深深影響著計(jì)算的分布方式。分布式系統(tǒng)中計(jì)算節(jié)點(diǎn)和保存計(jì)算數(shù)據(jù)的存儲(chǔ)節(jié)點(diǎn)可以在同一臺(tái)物理機(jī)器上，也可以位于不儲(chǔ)節(jié)點(diǎn)在同一臺(tái)物理機(jī)器上的計(jì)算節(jié)點(diǎn)上進(jìn)行，這稱之為本地化計(jì)算。本地化計(jì)算是計(jì)算調(diào)度的一7數(shù)據(jù)分布方式的選擇分析了各種常見(jiàn)的數(shù)據(jù)分布方式及這些方式的優(yōu)缺點(diǎn)。在實(shí)際工程實(shí)踐中，可以根據(jù)需求2.1.6：繼續(xù)討論2.1.1中提到的數(shù)據(jù)傾斜問(wèn)題，在按哈希分?jǐn)?shù)據(jù)的基礎(chǔ)上引入按數(shù)據(jù)量分布某一閾值將用戶的數(shù)據(jù)切為多個(gè)均勻的數(shù)據(jù)段，將這些數(shù)據(jù)段分布到集群中去。由于大部分用數(shù)據(jù)的規(guī)模。這種哈希分布數(shù)據(jù)方式與按數(shù)據(jù)量分布數(shù)據(jù)方式組合使用的方案，在某真實(shí)系統(tǒng)1.8工程投影。GFS[9]&HDFSMapreduce[10]BigTable[11]&HBasePNUTS[14]Dynamo[16]&Cassandra[17]morBigPipe[18]Doris]2.2。致性要求的分布式協(xié)議。副本控制協(xié)議要具有一定的對(duì)抗異常狀態(tài)的容錯(cuò)能力，從而使得系統(tǒng)具有一定的可用性，同時(shí)副本控制協(xié)議要能提供一定一致性級(jí)別。由CAP原理(在2.9節(jié)詳細(xì)分析)可、一致性與性能等各要素之間按照具體需求折中。2.1中心化副本控制協(xié)議節(jié)點(diǎn)協(xié)調(diào)副本數(shù)據(jù)的更新、維護(hù)副本之間的一致化副本協(xié)議的通用架構(gòu)。中心化副本控制協(xié)議的優(yōu)點(diǎn)是協(xié)議相對(duì)較為簡(jiǎn)單，有的副本相關(guān)的控制交由中心節(jié)點(diǎn)完成。并發(fā)控制將由中心節(jié)點(diǎn)完成，從而使得一個(gè)分布式并發(fā)點(diǎn)異常或與中心節(jié)點(diǎn)通信中斷時(shí)，系統(tǒng)將失去某些服務(wù)(通常至少失去更新服務(wù))，所以中心本控制協(xié)議的缺點(diǎn)正是存在一定的停服務(wù)時(shí)間。圖2-7中心化副本控制2.2.2primary-secondary協(xié)議護(hù)數(shù)據(jù)的更新、并發(fā)控制、協(xié)調(diào)副本的一致性。副本的確定和切換、數(shù)據(jù)同步(reconcile2.1數(shù)據(jù)更新基本流程3.primary節(jié)點(diǎn)進(jìn)行并發(fā)控制即確定并發(fā)更新操作的先后順序4.primary節(jié)點(diǎn)將更新操作發(fā)送給secondary節(jié)點(diǎn)primary根據(jù)secondary節(jié)點(diǎn)的完成情況決定更新是否成功并將結(jié)果返回外部節(jié)點(diǎn)imaryimary圖2-8primary-secondary基本更新流程primarysecondary出了這個(gè)更新的數(shù)據(jù)。在工程實(shí)踐中，如果由primary直接同時(shí)發(fā)送給其他N個(gè)副本發(fā)送數(shù)據(jù)，則每個(gè)rimary于第4步的具體處理，本節(jié)先不展開(kāi)討論，在2.4中介紹一種基于Quorum的副本控制機(jī)制。第52.2數(shù)據(jù)讀取方式也與一致性高度相關(guān)。如果只需要最終一致性，則讀取任何副本都可以滿足需求。如果需要會(huì)保證用戶讀到的數(shù)據(jù)在會(huì)話范圍內(nèi)單調(diào)遞增。使用primary-secondary比較困難的是實(shí)現(xiàn)強(qiáng)一致性。副本提供讀服務(wù)在很多場(chǎng)景下并不會(huì)造出機(jī)器資源浪費(fèi)。回憶2.1.5節(jié)，將數(shù)據(jù)分為數(shù)據(jù)段，以數(shù)y時(shí)，primary將該secondary副本標(biāo)記為不可用，從而用戶不再讀取該不可用的副本。不可用的mary從而符合較高的一致性要求。這種方式依賴于一個(gè)中心元數(shù)據(jù)管理系統(tǒng)，用于記錄哪些副本可用，第三、基于Quorum機(jī)制，本文在2.4節(jié)中詳細(xì)分析Quorum機(jī)制。這里不展開(kāi)討論。2.2.2.3primary副本的確定與切換息，由專門的元數(shù)據(jù)服務(wù)器維護(hù)。執(zhí)行更新操作時(shí)，首先查詢?cè)獢?shù)據(jù)服務(wù)器獲取副本的primary信aryryy然而在原primary已經(jīng)發(fā)送宕機(jī)等異常時(shí)，如何確定一個(gè)secondary副本使得該副本上的數(shù)據(jù)與原primarysecondary價(jià)問(wèn)題。上節(jié)中本文在2.4.5介紹一種基于Quorum機(jī)制確定新primary的方法。這樣的探測(cè)時(shí)間通常是10秒級(jí)別(見(jiàn)2.3.3使用lease確定節(jié)點(diǎn)狀態(tài))，這也意味著一旦primary異常，最多需要10秒級(jí)別的新服務(wù)，如果系統(tǒng)只能讀primary副本，則這段時(shí)間內(nèi)甚至不能提供讀服務(wù)。從這里可以看到，rimary.2.2.4數(shù)據(jù)同步econcileyimary好的做法是設(shè)計(jì)的分布式協(xié)議不產(chǎn)生臟數(shù)據(jù)。如果協(xié)議一定有產(chǎn)生臟數(shù)據(jù)的可能，則也應(yīng)該使得生臟數(shù)據(jù)的概率降到非常低得情況，從而一旦發(fā)生臟數(shù)據(jù)的情況可以簡(jiǎn)單的直接丟棄有臟數(shù)據(jù)的aryprimarysnapshot副本數(shù)據(jù)形成快照，然后拷貝快照，拷貝的更新操作。去中心化副本控制協(xié)議心化節(jié)點(diǎn)異常而帶來(lái)的停服務(wù)等問(wèn)題。圖2-9給出了去中圖2-9去中心化副本控制協(xié)議本控制協(xié)議具有某些共性不同，各類去中心化副本控制協(xié)議則各有各的巧妙。本節(jié)不再就去中心化副本控制協(xié)議做進(jìn)一步詳細(xì)分析。Paxos是唯一在工程中得到應(yīng)用的強(qiáng)一致性去中心化副本控制協(xié)議。本文在2.8節(jié)詳細(xì)分析paxos協(xié)議。2.4工程投影然簡(jiǎn)單，但使用卻極其廣泛。向下更新另一個(gè)副本，但是數(shù)據(jù)的更新過(guò)程完全是由primary控制的，所以也可以認(rèn)為數(shù)據(jù)是由ry副本進(jìn)行控制的。2.2.4.3Niobe中的Primary-Secondary協(xié)議.4Dynamo/Cassandra的去中心化副本控制協(xié)議缺乏較好的一致性，應(yīng)用在編程時(shí)的難度被大大增加了。本文在2.4.6中較為詳細(xì)的分析了Dynamo。.4.5Chubby/Zookeeper的副本控制協(xié)議marysecondary節(jié)點(diǎn)。本文在2.8.6中進(jìn)一步分析這三個(gè)系統(tǒng)的工作原理。.6Megastore的副本控制協(xié)議primary-secondary方式[12]。另一方面，Megastore又結(jié)合了Primary-secondary本文在2.8.6中進(jìn)一epaxos7其他系統(tǒng)的副本控制協(xié)議2.3Lease機(jī)制Lease機(jī)制是最重要的分布式協(xié)議，廣泛應(yīng)用于各種實(shí)際的分布式系統(tǒng)中。即使在某些系統(tǒng)中重要的應(yīng)用：判定節(jié)點(diǎn)狀態(tài)。]。著一些數(shù)據(jù)，這些數(shù)據(jù)是系統(tǒng)的元數(shù)據(jù)。系統(tǒng)中其他的節(jié)點(diǎn)通過(guò)訪問(wèn)中心服務(wù)器節(jié)點(diǎn)讀取、修改其上的元數(shù)據(jù)。由于系統(tǒng)中各種操作都依賴于元數(shù)據(jù)，如果每次讀取元數(shù)據(jù)的操作都訪問(wèn)中心服務(wù)器節(jié)點(diǎn)，那么中心服務(wù)器節(jié)點(diǎn)的性能成為系統(tǒng)的瓶頸。為此，設(shè)計(jì)一種元數(shù)據(jù)cache，在各個(gè)節(jié)點(diǎn)上cache元數(shù)據(jù)信息，從而減少對(duì)中心服務(wù)器節(jié)點(diǎn)的訪問(wèn)，提高性能。另一方面，系統(tǒng)的正確運(yùn)行嚴(yán)e戶端節(jié)點(diǎn)一個(gè)基本流程如下：ee節(jié)點(diǎn)請(qǐng)求讀取元數(shù)據(jù)信息1.2.2客戶端是否成功收到服務(wù)器返回的數(shù)據(jù)據(jù)并向客戶端節(jié)點(diǎn)返回修改成功。各個(gè)節(jié)點(diǎn)上的cache與中心服務(wù)器上的中心始終一致。這是因?yàn)橹行姆?wù)器的在lease有效期內(nèi)cache數(shù)據(jù)。上述lease機(jī)制可以容錯(cuò)的關(guān)鍵是：服務(wù)器一旦lease機(jī)制的分析用頒發(fā)者的承諾。ryeLease機(jī)制依賴于有效期，這就要求頒發(fā)者和接收者的時(shí)鐘是同步的。一方面，如果頒發(fā)者的頒發(fā)給其他節(jié)點(diǎn)，造成承諾失效，影響系統(tǒng)的正確性。對(duì)于這種時(shí)鐘不同步，實(shí)踐中的通常做法是分布式系統(tǒng)中確定一個(gè)節(jié)點(diǎn)是否處于正常工作狀態(tài)是一個(gè)困難的問(wèn)題。由于可能存在網(wǎng)絡(luò)分，節(jié)點(diǎn)的狀態(tài)是無(wú)法通過(guò)網(wǎng)絡(luò)通信來(lái)確定的。下面舉一個(gè)較為具體的例子來(lái)討論這個(gè)問(wèn)題。ryAACy解決這種問(wèn)題有兩種思路，第一、設(shè)計(jì)的分布式協(xié)議可以容忍“雙主”錯(cuò)誤，即不依賴于對(duì)節(jié)點(diǎn)狀lease定節(jié)點(diǎn)狀態(tài)。primary主”問(wèn)題。的設(shè)計(jì)。lease的有效期時(shí)間選擇證的經(jīng)驗(yàn)值，實(shí)踐中可以作為參考并綜合選擇合適的時(shí)長(zhǎng)。3.5工程投影sechuck上的執(zhí)行順序。GFS中的Lease信息由Master在響應(yīng)各個(gè)節(jié)點(diǎn)的HeartBeat時(shí)附帶傳遞 ert5.2Niobe中的LeaseeaseobeSMprimarysecondary與數(shù)據(jù)后才能發(fā)起新的更新元數(shù)據(jù)的操作，而如果被對(duì)方kill，那么重新讀取元數(shù)據(jù)時(shí)會(huì)發(fā)現(xiàn)自己已e我們知道chubby通過(guò)paxos協(xié)議實(shí)現(xiàn)去中心化的選擇primary節(jié)點(diǎn)(見(jiàn)2.8.6)。一旦某個(gè)節(jié)點(diǎn)似。seeleasese節(jié)點(diǎn)則發(fā)起新的paxos選舉，只要primary與secondary工作正常，新發(fā)起的選舉由于缺乏多數(shù)工程中完全可以間接使用Lease。借助zookeeper，我們可以簡(jiǎn)單的實(shí)現(xiàn)高效的、無(wú)單點(diǎn)選主、狀態(tài)實(shí)際上，這些功能的實(shí)現(xiàn)都是依賴于背后zookeeper2.4Quorum機(jī)制Quorum機(jī)制是一種簡(jiǎn)單有效的副本管理機(jī)制。本節(jié)首先討論一種最簡(jiǎn)單的副本控制規(guī)則2.4.1約定2.4.2Write-all-read-oneWrite-all-read-one(簡(jiǎn)稱WARO)是一種最簡(jiǎn)單的副本控制規(guī)則，顧名思義即在更新時(shí)寫所有讀任一副本上的數(shù)據(jù)。agici頸。O4.3Quorum定義umWWR圖2-10Quorum機(jī)制v2。N交的數(shù)據(jù)。定最新已成功提交的版本號(hào)，除非將最新已提交的版本號(hào)作為元數(shù)據(jù)由特定的元數(shù)據(jù)服務(wù)器或元數(shù)讀取最新成功提交的數(shù)據(jù)v哪一個(gè)。v2v2v2v1v1v2v1v1v1v1(a)(b)圖2-11僅讀R個(gè)副本無(wú)法判斷最新已成功提交的數(shù)據(jù)m取條件做進(jìn)一步加強(qiáng)。號(hào)必須是連續(xù)增加的。為(v2v2)則v2是最新的已提交的副本；若讀到剩余的兩個(gè)副本為(v2v1)或(v1v1)則v1是最新交的版本；若讀取后續(xù)兩個(gè)副本有任一超時(shí)或失敗，則無(wú)法判斷哪個(gè)版本是最新的成功提交 通過(guò)Quorum機(jī)制讀取最新的成功提交的版本。例數(shù)據(jù)。quorumprimary.2.2節(jié)，基本primary-secondary協(xié)以有不同的做法：如果需要強(qiáng)一致性的立刻讀取到最新的成功提交的數(shù)據(jù)，則可以簡(jiǎn)單的只讀yW系統(tǒng)的最新的成功提交的數(shù)據(jù)，v2是一個(gè)處于中間狀態(tài)的未成功提交的數(shù)據(jù)。假設(shè)此刻原primaryprimary。下面v2v2v1v2v2v1v1v1v1vvvvvv1v1v1圖2-12基于quorum選擇primary情況1vv1v1)，則任yvvv2v1v1v1222v2v22224.6工程投影GFS使用WARO機(jī)制讀寫副本，即如果更新所有副本成功則認(rèn)為更新成功，一旦更新成功，，是一種非常值得借鑒的設(shè)計(jì)思路。Dynamoprimary中心控制，每次更新操作都可能由1，即(1，1，1)。上的數(shù)據(jù)分別為(2，1，2)。CMVCC式幫助用戶解決數(shù)據(jù)沖突。所謂clockvectorlockvectorB。C此時(shí)數(shù)據(jù)為(5,3,5)，此時(shí)三個(gè)副本的clockvector為([(2,A),(1,A)],[(1,B)],[(2,A),(1,A)])。設(shè)用戶判斷出，其實(shí)這些加法操作可以合并，那么最終的數(shù)據(jù)應(yīng)該是7，又例如用戶可以選擇保選擇合并這些多版本數(shù)據(jù)。Dynamo建議可以簡(jiǎn)單的按照數(shù)據(jù)更新的時(shí)間戳進(jìn)行合并，即用數(shù)據(jù)時(shí)是有效且正確的。然而類似上例中這類并發(fā)的加法操作(例如“向購(gòu)物車中增加商品”)，簡(jiǎn)單的用yprimary節(jié)點(diǎn)只需更新超過(guò)半數(shù)(含自身)的節(jié)點(diǎn)后就返回用戶成功。每次更新操作都會(huì)遞增各個(gè)節(jié)副本。這個(gè)原則與2.4.5中描述的完全一致。值得一提的是，在2.4.5中分析到，新primary的版本0ary大于新primary的版本號(hào)的數(shù)據(jù)(中間態(tài)版本)，和2.4.5分析的一樣，此時(shí)這樣的中間態(tài)版本數(shù)據(jù)MolaArmorQuorum據(jù)在多數(shù)副本上更新成功則認(rèn)Mola不關(guān)注強(qiáng)一致性，而提供最終一致性。對(duì)于Armor*，可以通過(guò)讀取副本版本號(hào)的方式，按Quorum規(guī)則判斷最新已提交的版本(參考2.4.4)。由于每次讀數(shù)據(jù)都需要讀取版本號(hào)，降低了系統(tǒng)系統(tǒng)性能，Doris*系統(tǒng)在讀取Armor*數(shù)據(jù)時(shí)采用了一種優(yōu)化思路：由于BigPipe*中的副本管理也是采用了WARO機(jī)制。值得一提的是，BigPipe利用了zookeeper的息后會(huì)將最后一個(gè)更新操作作為“臟數(shù)據(jù)”并回退掉最后一個(gè)更新操作，新切換的副本組也從這里不難看出，當(dāng)出現(xiàn)更新失敗時(shí)，最后一條更新操作成為類似2.4.5中的中間態(tài)數(shù)據(jù)。與12.5日志技術(shù)志技o(jì)g數(shù)據(jù)庫(kù)系統(tǒng)日志技術(shù)簡(jiǎn)述在數(shù)據(jù)庫(kù)系統(tǒng)中實(shí)現(xiàn)宕機(jī)恢復(fù)，其難點(diǎn)在于數(shù)據(jù)庫(kù)操作需要滿足ACID，尤其在支持事務(wù) 目標(biāo)就是數(shù)據(jù)庫(kù)系統(tǒng)恢復(fù)到一個(gè)穩(wěn)定可靠狀態(tài)，消除未完成的事務(wù)對(duì)數(shù)據(jù)庫(kù)狀態(tài)的影響。2.5.2.1問(wèn)題模型統(tǒng)，將數(shù)據(jù)全部存放在內(nèi)存中以實(shí)現(xiàn)高速的數(shù)據(jù)查詢，每次更新操作更新一小部分?jǐn)?shù)據(jù)(例如有一個(gè)更新操作，且每次更新操作都可以也必須立即提交(Autocommit)。2RedoLog1.將更新操作的結(jié)果(例如SetK1=1，則記錄K1=1)以追加寫(append)的方式寫入磁盤的按更新操作修改內(nèi)存中的數(shù)據(jù)更新成功2儲(chǔ)設(shè)備上效率較高。數(shù)據(jù)。3Checkpoint減少宕機(jī)恢復(fù)時(shí)需要回放的日志數(shù)據(jù)。1.向日志文件中記錄“BeginCheckPoint”3.向日志文件中記錄“EndCheckPoint”.從后向前掃描日志文件，尋找最后一個(gè)“EndCheckPoint”日志。3123452terrdtory3.從最后一個(gè)“EndCheckPoint”日志向前找到最近的一個(gè)“123452terrdtoryredodump程中，有些時(shí)候Redo日志無(wú)法具有冪等性，nt2.5.3NoUndo/NoRedologdologry，Directory0ABCABC圖2-130/1目錄示例4C0/1目錄將批量事務(wù)操作的原子性通過(guò)目錄手段歸結(jié)到主記錄的原子切換。由于多條記錄的原子修改一般較難實(shí)現(xiàn)而單條記錄的原子修改往往可以實(shí)現(xiàn)，從而降低了問(wèn)題實(shí)現(xiàn)的難度。在工程中0/1目錄的思想運(yùn)用非常廣泛，其形式也不局限在上述流程中，可以是內(nèi)存中的兩個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)回5.4工程投影rMySQL的主從庫(kù)設(shè)計(jì)也是基于日志。從庫(kù)只需通過(guò)回放主庫(kù)的日志，就可以實(shí)現(xiàn)與主庫(kù)的同rmor以立刻讀取到成功更新的數(shù)據(jù)。52.6兩階段提交協(xié)議2.6.1問(wèn)題背景兩階段提交(twophasecommit)協(xié)議是一種歷史悠久的分布式控制協(xié)議。最早用于在分布式數(shù)數(shù)據(jù)庫(kù)中的操作都是事務(wù)(transaction)，一個(gè)事務(wù)是一系列讀、寫操作，事務(wù)滿足ACID。每個(gè)事務(wù)的最終狀態(tài)要么是提交(commit)，要么是失敗(abort)。一旦一個(gè)事務(wù)成功提交，那與本事務(wù)有沖突(例如死鎖)，從而造成在有些副本上事務(wù)可以提交，而有些副本上事務(wù)無(wú)法提交。庫(kù)系統(tǒng)相關(guān)資料了解。流程描述節(jié)點(diǎn)分為兩類：一個(gè)中心化協(xié)調(diào)者節(jié)點(diǎn)(coordinator)和N個(gè)參與者節(jié)點(diǎn)(participant)。每個(gè)參與即上文背景介紹中的管理數(shù)據(jù)庫(kù)副本的節(jié)點(diǎn)。段提交的思路比較簡(jiǎn)單，在第一階段，協(xié)調(diào)者詢問(wèn)所有的參與者是否可以提交事務(wù)(請(qǐng)參6.向所有參與者發(fā)送“prepare消息”；收參與者發(fā)送的對(duì)“prepare消息”的響應(yīng)；收到任何一個(gè)參與者發(fā)送的“vote-abort消息”；向所有的參與者發(fā)送“global-abort消息”；若收到所有參與者發(fā)送的“vote-commit”消息；向所有的參與者發(fā)送“global-commit消息”；endtransaction日志流程結(jié)束。2.1若參與者可以提交本次事務(wù)向協(xié)調(diào)者發(fā)送“vote-commit”消息1.4等待協(xié)調(diào)者的消息.4.1若收到協(xié)調(diào)者的“global-abort”消息2.1.4.1.2向協(xié)調(diào)者發(fā)送對(duì)“global-abort”的確認(rèn)消息4.2若收到協(xié)調(diào)者的“global-commit”消息2.1.4.1.2向協(xié)調(diào)者發(fā)送對(duì)“global-commit”的確認(rèn)消息2.2若參與者無(wú)法提交本次事務(wù)7.2.2向協(xié)調(diào)者發(fā)送“vote-abort”消息2.3流程對(duì)該參與者結(jié)束.2.4若后續(xù)收到協(xié)調(diào)者的“global-abort”消息可以響應(yīng)it應(yīng)的確認(rèn)消息。.6.3異常處理.6.3.1宕機(jī)恢復(fù)3.1.1協(xié)調(diào)者宕機(jī)恢復(fù)發(fā)送過(guò)“prepare消息”也可能還沒(méi)發(fā)送，但協(xié)調(diào)者一定還沒(méi)有發(fā)送過(guò)“global-commit消息”或“global-abort消息”，即事務(wù)的全局狀態(tài)還沒(méi)有確定。此時(shí)，協(xié)調(diào)者可以重新發(fā)送“prepare消息”prepare的議的一致性。balcommitglobalabort1.2參與者宕機(jī)恢復(fù)續(xù)流程等待協(xié)調(diào)者發(fā)送的“prepare消息”。送“vote-commit”消息并不可知。所以8送過(guò)對(duì)“global-commit”或“global-abort”的確認(rèn)消息則未知。但即使沒(méi)有發(fā)送過(guò)確認(rèn)消息，由于協(xié)議的全局一致性。2.6.3.2響應(yīng)超時(shí)一分析這些超時(shí)的原因和對(duì)協(xié)議的影響。響應(yīng)消息。協(xié)調(diào)者此時(shí)放棄事務(wù)不影響協(xié)議的一致性。1.協(xié)調(diào)者與某個(gè)參與者網(wǎng)絡(luò)中斷，協(xié)調(diào)者的“global-commit”或“global-abort”消息無(wú)法發(fā)協(xié)調(diào)者。t。rt9協(xié)調(diào)者的“prepare”消息時(shí)超時(shí)，此種異常的原因可能是協(xié)調(diào)者宕機(jī)或者協(xié)調(diào)者與ABORT使后續(xù)收到了“prepare”棄。網(wǎng)絡(luò)中斷。協(xié)議分析下幾點(diǎn)：法執(zhí)行下去的情況，且也無(wú)法判斷流程狀態(tài)。在工程中好的分布式協(xié)議往往總是可以在即使發(fā)生異常的情況下也能執(zhí)行下去。例如，回憶Lease機(jī)制(2.3)，一旦lease發(fā)出，無(wú)論出Lease交的協(xié)議顯得較為復(fù)雜且容錯(cuò)能力差。段提交協(xié)議可以提高容錯(cuò)能力和性能，然而這類協(xié)議依舊是在工程中意義。XX實(shí)現(xiàn)分布式事務(wù)除了使用類似“兩階段提交”協(xié)議等方式外，另一種簡(jiǎn)單高效的方式就是使用ultiversionCocurrentControlMVCC2.7.1MVCC簡(jiǎn)介Version1圖2-14MVCC示例各自對(duì)數(shù)據(jù)進(jìn)行了一些本地修改(這些修改只有事務(wù)自己可見(jiàn)，不影響真正的數(shù)據(jù))，之后事務(wù)A礎(chǔ)數(shù)據(jù)版本中的數(shù)據(jù)完全拷貝出來(lái)再修改，SVN即使用了這種方法，SVNcheckout即是拷貝的過(guò)N所有更新操作要么同時(shí)在各個(gè)節(jié)點(diǎn)生效，要么都不生效。假設(shè)不存在并發(fā)的事務(wù)，即上一個(gè)事務(wù)個(gè)典型的事務(wù)可能是{(site_A,var1,add,10),(site_B,var2,sub,1),(site_A,var3,set,2)}，這個(gè)事務(wù)在節(jié)點(diǎn)都完成后，在全局元信息中記錄本次事務(wù)的編號(hào)。在讀取數(shù)據(jù)時(shí)，先讀取元信息中已成功的的操作，并將這些操作應(yīng)用到基礎(chǔ)數(shù)據(jù)形成讀取結(jié)果。Asetvar1=11Asetvar1Asetvarvar1+22Bsetvar1Bsetvar4=12然實(shí)現(xiàn)對(duì)歷史版本數(shù)據(jù)的讀取。下表：Asetvar1=32Asetvar2Bsetvar22Bsetvar4=12不參與合并。7.3工程投影CegastoreBigTable紹完全一致，不再贅述。的版本號(hào)與數(shù)據(jù)上的導(dǎo)入版本號(hào)做過(guò)濾，從而不讀取正在更新的尚未生效的數(shù)據(jù)，實(shí)現(xiàn)了分布式2.8Paxos協(xié)議2.8.1簡(jiǎn)介Paxos協(xié)議是少數(shù)在工程實(shí)踐中證實(shí)的強(qiáng)一致性、高可用的去中心化分布式協(xié)議[6][7]。決議獲得了超過(guò)半數(shù)節(jié)點(diǎn)的同意則生效。Paxos協(xié)議中只要有超過(guò)一半的節(jié)點(diǎn)正常，就可以工作，些復(fù)雜的例子演示協(xié)議的過(guò)程。最后，本文再介紹協(xié)議是如何推導(dǎo)設(shè)計(jì)出來(lái)的。.2協(xié)議描述.8.2.1節(jié)點(diǎn)角色Acceptorlue類角色只是邏輯上的劃分，實(shí)踐中一個(gè)節(jié)點(diǎn)可以同時(shí)充當(dāng)這三類角色。.8.2.2流程描述(準(zhǔn)備階段)(批準(zhǔn)階段，根據(jù)收到的Acceptor的消息作出不同選擇)tor(準(zhǔn)備階段)(批準(zhǔn)階段)2.8.3實(shí)例Paxos典型的場(chǎng)景下協(xié).8.3.1基本例子Acceptor1Acceptor2Acceptor3Acceptor4Acceptor5B00000VNULLNULLNULLNULLNULLProposer1b1Acceptor1Acceptor2Acceptor3Acceptor4Acceptor5B11111VNULLNULLNULLNULLNULLProposer1b1Acceptor1Acceptor2Acceptor3Acceptor4Acceptor5B11111Vv1vv1vv1vv1vv1v協(xié)議也無(wú)法改變value。Acceptor1Acceptor2Acceptor3Acceptor4Acceptor5B33322Vv1vv1vv1vNULLNULLAcceptor1Acceptor2Acceptor3Acceptor4Acceptor5B44444Vv1vv1vv1vNULLNULLeeptvtvAcceptor1Acceptor2Acceptor3Acceptor4Acceptor5B44444Vv1vv1vv1vv1vNULL可以看到一旦一個(gè)value被批準(zhǔn)，此后永遠(yuǎn)只能批準(zhǔn)這個(gè)value。3一種不可能出現(xiàn)的狀態(tài)os協(xié)議時(shí)的一種錯(cuò)誤狀態(tài)。Acceptor1Acceptor2Acceptor3Acceptor4Acceptor5B11122Vv1vv1vv1vv2vv2v批準(zhǔn)的value是v1。torL3.4節(jié)點(diǎn)異常Acceptor1Acceptor2Acceptor3Acceptor4Acceptor5B11000VNULLNULLNULLNULLNULLsLAcceptor1Acceptor2Acceptor3Acceptor4Acceptor5B21220VNULLNULLNULLNULLNULLAcceptor1Acceptor2Acceptor3Acceptor4Acceptor5B21220VNULLNULLv1vv1vNULLAcceptor1Acceptor2Acceptor3Acceptor4Acceptor5B33323VNULLNULLv1vv1vNULLULLAcceptor1Acceptor2Acceptor3Acceptor4Acceptor5B33323Vv2vv2vv1vv1vNULLAcceptor1Acceptor2Acceptor3Acceptor4Acceptor5B44444Vv2vv2vv1vv1vNULLAcceptor1Acceptor2Acceptor3Acceptor4Acceptor5B44444Vv2vv1vv1vv1vNULL競(jìng)爭(zhēng)及活鎖從前面的例子不難看出，Paxos協(xié)議的過(guò)程類似于“占坑”，哪個(gè)value把超過(guò)半數(shù)的“坑”自己占用的鎖，從而造成系統(tǒng)死鎖。NULL)Acceptor1Acceptor2Acceptor3Acceptor4Acceptor5B11111VNULLNULLNULLNULLNULLNULL)Acceptor1Acceptor2Acceptor3Acceptor4Acceptor5B22222VNULLNULLNULLNULLNULLNULL)Acceptor1Acceptor2Acceptor3Acceptor4Acceptor5B33333VNULLNULLNULLNULLNULL.5協(xié)議推導(dǎo)tor提議搶占低輪次的提議來(lái)避免死鎖。xosValue過(guò)程就是不斷推導(dǎo)出“約束條件1”的必要不充分條件，直到某個(gè)必要不充分條件在工程上易于實(shí)“約束條件2”eve之前Paxos協(xié)議批準(zhǔn)的也只能是v2。8.6工程投影儲(chǔ)、分布式鎖等服務(wù)，從而間接的提供了Paxos功能。saryy的高可用(幾乎不會(huì)停服務(wù))的中心節(jié)點(diǎn)，其他分布式系統(tǒng)可以基于這個(gè)大中心節(jié)點(diǎn)可以實(shí)現(xiàn)中心鏈接關(guān)閉后，這個(gè)鏈接上不再有數(shù)據(jù)傳遞。由于TCP協(xié)議為傳輸?shù)拿恳粋€(gè)字節(jié)設(shè)置了序列號(hào)這個(gè)場(chǎng)景里，Leader接收客戶端發(fā)送的更新操作，以一種類似兩階段提交的過(guò)程在各個(gè)follower hcountcountzxid新操作的全局序號(hào)(版本號(hào))。xiderpaxos過(guò)程中以b=(zxid,nodeid)發(fā)起提議，從而當(dāng)zxid相同時(shí)會(huì)優(yōu)先選擇節(jié)點(diǎn)編號(hào)較大的節(jié)點(diǎn)成為稱為NEW_LEADER消息，是為了在各個(gè)節(jié)點(diǎn)上更新leader信息，當(dāng)收到超過(guò)半數(shù)的follower對(duì)rrZookeeper通過(guò)zxid將兩個(gè)場(chǎng)景階段較好的結(jié)合起來(lái)，且能保證全局的強(qiáng)一致性。由于同一時(shí)seperos使得Megastore具有一個(gè)去中心化的副本控制機(jī)制。另一方面，為了獲得較大的數(shù)據(jù)更新性能，能。為此，Megastore使用了一些方式對(duì)Paxos訪問(wèn)特點(diǎn)機(jī)房中的副本。為此，Megastore在每個(gè)機(jī)房為每個(gè)副本部署一個(gè)特殊的稱為協(xié)調(diào)器 coordinatorCoordinator對(duì)Megastore的底層Bigtable系統(tǒng)而言顯得非常簡(jiǎn)單，Megastoreclient訪問(wèn)Coordinator本一致，即當(dāng)前副本是否具有最新的已提交的數(shù)據(jù)。利超過(guò)半數(shù)的節(jié)點(diǎn)就可以讀取到最新的數(shù)據(jù)。e重要功能：1.嘗試更新本地副本的coordinator。2.解決中間態(tài)數(shù)據(jù)問(wèn)題。這里需要說(shuō)明的是，e。個(gè)副本，雖然已經(jīng)滿足Quorum，但在這兩個(gè)副本中選擇版本號(hào)最大的一個(gè)副本，卻不能知道該