分布式系統一緻性問題和一緻性算法

一緻性問題

一緻性算法是用來解決一緻性問題的,那麼什麼是一緻性問題呢? 在分布式系統中,一緻性問題(consensus problem)是指對于一組伺服器,給定一組操作,我們需要一個協定使得最後它們的結果達成一緻. 更詳細的解釋就是,當其中某個伺服器收到用戶端的一組指令時,它必須與其它伺服器交流以保證所有的伺服器都是以同樣的順序收到同樣的指令,這樣的話所有的伺服器會産生一緻的結果,看起來就像是一台機器一樣.

實際生産中一緻性算法需要具備以下屬性:

• safety:即不管怎樣都不會傳回錯誤的結果
• available:隻要大部分的機器正常,就仍然可以工作.比如五台機器的叢集允許最多兩台機器壞掉.
• 不依賴時間來確定一緻,即系統是異步的.
• 一般情況下,運作時間由大多數的機器決定,不會因為有少部分慢的機器而影響總體效率.

為什麼要解決一緻性問題?

我們可以說一個分布式系統可靠性達到99.99...%,但不能說它達到了100%, 為什麼? 就是因為一緻性問題是無法徹底解決的. 以下四個分布式系統中的問題都與一緻性問題有關:

1. reliable multicast 可靠多點傳播
2. membership protocal (failuer detector) 叢集中成員的管理
3. leader election 選舉算法

1. mutual exclution 互斥,例如資源的獨占和配置設定

分布式系統中的節點通信存在兩種模型：共享記憶體（Shared memory）和消息傳遞（Messages passing）。基于消息傳遞通信模型的分布式系統，不可避免地會發生以下錯誤：程序可能會慢、垮、重新開機，消息可能會延遲、丢失、重複（不考慮“Byzantinefailure”）。

一個典型的場景是：在一個分布式資料庫系統中，如果各節點的初始狀态一緻，每個節點都執行相同的操作序列，那麼它們最後能得到一個一緻的狀态。為保證每個節點執行相同的指令序列，需要在每一條指令上執行一個「一緻性算法」以保證每個節點看到的指令一緻。一個通用的一緻性算法可以應用在許多場景中，是分布式計算中的重要問題。從20世紀80年代起對于一緻性算法的研究就沒有停止過。

通俗地把一緻性的問題可分解為2個問題：

1、任何一次修改保證資料一緻性。

2、多次資料修改的一緻性。

在弱一緻性的算法，不要求每次修改的内容在修改後多副本的内容是一緻的，對問題1的解決比較寬松，更多解決問題2，該類算法追求每次修改的高度并發性，減少多副本之間修改的關聯性，以獲得更好的并發性能。例如最終一緻性，無所謂每次使用者修改後的多副本的一緻性及格過，隻要求在單調的時間方向上，資料最終保持一緻，如此獲得了修改極大的并發性能。

在強一緻性的算法中，強調單次修改後結果的一緻，需要保證了對問題1和問題2要求的實作，犧牲了并發性能。本文是讨論對解決問題1實作算法，這些算法往往在強一緻性要求的應用中使用。

解決問題1的方法，通常有兩階段送出算法、采用分布式鎖服務和采用樂觀鎖原理實作的同步方式,下面分别介紹這幾種算法的實作原理。

• 兩階段送出算法

在兩階段送出協定中，系統一般包含兩類機器（或節點）：一類為協調者（coordinator），通常一個系統中隻有一個；另一類為事務參與者（participants，cohorts或workers），一般包含多個，在資料存儲系統中可以了解為資料副本的個數。兩階段送出協定由兩個階段組成，在正常的執行下，這兩個階段的執行過程如下所述：

• 階段1：請求階段（commit-request phase，或稱表決階段，voting phase）。

         在請求階段，協調者将通知事務參與者準備送出或取消事務，然後進入表決過程。在表決過程中，參與者将告知協調者自己的決策：同意（事務參與者本地作業執行成功）或取消（本地作業執行故障）。

• 階段2：送出階段（commit phase）。

        在該階段，協調者将基于第一個階段的投票結果進行決策：送出或取消。當且僅當所有的參與者同意送出事務協調者才通知所有的參與者送出事務，否則協調者将通知所有的參與者取消事務。參與者在接收到協調者發來的消息後将執行響應的操作。

          舉個例子：A組織B、C和D三個人去爬長城：如果所有人都同意去爬長城，那麼活動将舉行；如果有一人不同意去爬長城，那麼活動将取消。用2PC算法解決該問題的過程如下：

• 首先A将成為該活動的協調者，B、C和D将成為該活動的參與者。
• 階段1：A發郵件給B、C和D，提出下周三去爬山，問是否同意。那麼此時A需要等待B、C和D的郵件。B、C和D分别檢視自己的日程安排表。B、C發現自己在當日沒有活動安排，則發郵件告訴A它們同意下周三去爬長城。由于某種原因，D白天沒有檢視郵件。那麼此時A、B和C均需要等待。到晚上的時候，D發現了A的郵件，然後檢視日程安排，發現周三當天已經有别的安排，那麼D回複A說活動取消吧。
• 階段2：此時A收到了所有活動參與者的郵件，并且A發現D下周三不能去爬山。那麼A将發郵件通知B、C和D，下周三爬長城活動取消。此時B、C回複A“太可惜了”，D回複A“不好意思”。至此該事務終止。

兩階段送出算法在分布式系統結合，可實作單使用者對檔案（對象）多個副本的修改，多副本資料的同步。其結合的原理如下：

          1、用戶端（協調者）向所有的資料副本的存儲主機（參與者）發送：修改具體的檔案名、偏移量、資料和長度資訊，請求修改資料，該消息是1階段的請求消息。

2、存儲主機接收到請求後，備份修改前的資料以備復原，修改檔案資料後，向用戶端回應修改成功的消息。 如果存儲主機由于某些原因（磁盤損壞、空間不足等）不能修改資料，回應修改失敗的消息。

3、用戶端接收發送出去的每一個消息回應，如果存儲主機全部回應都修改成功，向每存儲主機發送确認修改的送出消息；如果存在存儲主機回應修改失敗，或者逾時未回應，用戶端向所有存儲主機發送取消修改的送出消息。該消息是2階段的送出消息。

4、存儲主機接收到用戶端的送出消息，如果是确認修改，則直接回應該送出OK消息；如果是取消修改，則将修改資料還原為修改前，然後回應取消修改OK的消息。

5、 用戶端接收全部存儲主機的回應，整個操作成功。

      在該過程中可能存在通信失敗，例如網絡中斷、主機當機等諸多的原因，對于未在算法中定義的其它異常，都認為是送出失敗，都需要復原，這是該算法基于确定的通信回複實作的，在參與者的确定回複（無論是回複失敗還是回複成功）之上執行邏輯處理，符合确定性的條件當然能夠獲得确定性的結果哲學原理。

• 分布式鎖服務

 分布式鎖是對資料被外界修改持保守态度，在整個資料處理過程中将資料處于鎖定狀态，在使用者修改資料的同時，其它使用者不允許修改。

      采用分布式鎖服務實作資料一緻性，是在操作目标之前先擷取操作許可，然後再執行操作，如果其他使用者同時嘗試操作該目标将被阻止，直到前一個使用者釋放許可後，其他使用者才能夠操作目标。分析這個過程，如果隻有一個使用者操作目标，沒有多個使用者并發沖突，也申請了操作許可，造成了由于申請操作許可所帶來的資源使用消耗，浪費網絡通信和增加了延時。

      采用分布式鎖實作多副本内容修改的一緻性問題， 選擇控制内容顆粒度實作申請鎖服務。例如我們要保證一個檔案的多個副本修改一緻， 可以對整個檔案修改設定一把鎖，修改時申請鎖，修改這個檔案的多個副本，確定多個副本修改的一緻，修改完成後釋放鎖；也可以對檔案分段，或者是檔案中的單個位元組設定鎖， 實作更細顆粒度的鎖操作，減少沖突。

常用的鎖實作算法有Lamport bakery algorithm （俗稱面包店算法）， 還有Paxos算法。下面對其原理做簡單概述。

• Lamport面包店算法

是解決多個線程并發通路一個共享的單使用者資源的互斥問題的算法。 由Leslie Lamport（英語：Leslie Lamport）發明。    

    Lamport把這個并發控制算法可以非常直覺地類比為顧客去面包店采購。面包店隻能接待一位顧客的采購。已知有n位顧客要進入面包店采購，安排他們按照次序在前台登記一個簽到号碼。該簽到号碼逐次加1。根據簽到号碼的由小到大的順序依次入店購貨。完成購買的顧客在前台把其簽到号碼歸0. 如果完成購買的顧客要再次進店購買，就必須重新排隊。

     這個類比中的顧客就相當于線程，而入店購貨就是進入臨界區獨占通路該共享資源。由于計算機實作的特點，存在兩個線程獲得相同的簽到号碼的情況，這是因為兩個線程幾乎同時申請排隊的簽到号碼，讀取已經發出去的簽到号碼情況，這兩個線程讀到的資料是完全一樣的，然後各自在讀到的資料上找到最大值，再加1作為自己的排隊簽到号碼。為此，該算法規定如果兩個線程的排隊簽到号碼相等，則線程id号較小的具有優先權。

把該算法原理與分布式系統相結合，即可實作分步鎖。

• Paxos算法

 該算法比較熱門，參見WIKI，http://zh.wikipedia.org/wiki/Paxos%E7%AE%97%E6%B3%95

Paxos算法解決的問題是一個分布式系統如何就某個值(決議)達成一緻。一個典型的場景是，在一個分布式資料庫系統中，如果各節點的初始狀态一緻，每個節點都執行相同的操作序列，那麼他們最後能得到一個一緻的狀态。為保證每個節點執行相同的指令序列，需要在每一條指令上執行一個“一緻性算法”以保證每個節點看到的指令一緻。一個通用的一緻性算法可以應用在許多場景中，是分布式計算中的重要問題。節點通信存在兩種模型：共享記憶體(Shared memory)和消息傳遞(Messages passing)。Paxos算法就是一種基于消息傳遞模型的一緻性算法。BigTable使用一個分布式資料鎖服務Chubby，而Chubby使用Paxos算法來保證備份的一緻性。

• 采用樂觀鎖原理實作的同步

      我們舉個例子說明該算法的實作原理。如一個金融系統，當某個操作員讀取使用者的資料，并在讀出的使用者資料的基礎上進行修改時（如更改使用者帳戶餘額），如果采用前面的分布式鎖服務機制，也就意味着整個操作過程中（從操作員讀出資料、開始修改直至送出修改結果的全過程，甚至還包括操作員中途去煮咖啡的時間），資料庫記錄始終處于加鎖狀态，可以想見，如果面對幾百上千個并發，這樣的情況将導緻怎樣的後果。

      樂觀鎖機制在一定程度上解決了這個問題。樂觀鎖，大多是基于資料版本（ Version）記錄機制實作。何謂資料版本？即為資料增加一個版本辨別，在基于資料庫表的版本解決方案中，一般是通過為資料庫表增加一個 “version” 字段來實作。讀取出資料時，将此版本号一同讀出，之後更新時，對此版本号加一。此時，将送出資料的版本資料與資料庫表對應記錄的目前版本資訊進行比對，如果送出的資料版本号大于資料庫表目前版本号，則予以更新，否則認為是過期資料。

       對于上面修改使用者帳戶資訊的例子而言，假設資料庫中帳戶資訊表中有一個 version 字段，目前值為 1 ；而目前帳戶餘額字段（ balance ）為 $100 。

1. 操作員 A 此時将其讀出（version=1 ），并從其帳戶餘額中扣除 $50（$100-$50 ）。
2. 在操作員 A 操作的過程中，操作員B也讀入此使用者資訊（ version=1 ），并從其帳戶餘額中扣除 $20 （ $100-$20 ）。
3. 操作員 A 完成了修改工作，将資料版本号加一（ version=2 ），連同帳戶扣除後餘額（ balance=$50 ），送出至資料庫更新，此時由于送出資料版本大于資料庫記錄目前版本，資料被更新，資料庫記錄 version 更新為 2 。
4. 操作員 B 完成了操作，也将版本号加一（ version=2 ）試圖向資料庫送出資料（ balance=$80 ），但此時比對資料庫記錄版本時發現，操作員 B 送出的資料版本号為 2 ，資料庫記錄目前版本也為 2 ，不滿足 “ 送出版本必須大于記錄目前版本才能執行更新 “ 的樂觀鎖政策，是以，操作員 B 的送出被駁回。這樣，就避免了操作員 B 用基于 version=1 的舊資料修改的結果覆寫操作員A 的操作結果的可能。

樂觀鎖機制與分布式系統相結合上， 我整理了僞代碼如下：

obj  操作的目标      

vlaue 修改的值      

atom_update_ver 每個目标上的版本，每次修改該值遞增      

set( obj, value)      

{      

     //從每個節點上取出修改前的對象版本      

    get original_ver = obj.atom_update_ver from each node;      

     //将值賦到每個節點的obj目标      

    set obj = value from each node;      

     //條件修改每個節點的obj版本，目标版本加一      

     //比較和修改操作是原子操作      

    result = (set obj.atom_update_ver = original_ver + 1      

                  where  original_ver + 1 >  obj.atom_update_ver      

                   for each node);      

    if(result == ok)      

        return set_ok;      

    else      

        return set(obj, value);//不成功遞歸修改      

該算法未考慮節點下線、失效等問題，在後續我将分析采用樂觀鎖原理實作一緻性算法，解決問題2、節點失效、通信失敗等問題。

Raft一緻性算法

參見 Raft 為什麼是更易了解的分布式一緻性算法