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

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