Egalitarian Paxos

epaxos的目标

• 1）優化在wide-area環境下，當有節點failover出現，仍然能保證低commit延遲；
• 2）把叢集的load分散到各個node上，以此提高整體叢集的吞吐；

• 3）epaxos保證：在common case下，choose一個value隻需要一次roundtrip（fast path）；在有沖突的case下，最多需要2次roundtrip（slow path

  基于leader的paxos變種協定

multi-paxos優缺點

• 優點：選出一個node當leader，原本兩階段的prepare和accept隻需要accept階段就能choose出一個value。
• 缺點：

1. 1. 當leader當機，叢集在選出leader之前，不可服務；
   2. leader幹了所有的活，和其他節點不對等，也就是說leaser節點是叢集的瓶頸所在；
   3. 在geo-replication環境下，client必須要proposal發送到leader上，多了一跳；
   4. 當出現某個節點慢或者crash，叢集的抖動比較大；

epaxos的特點

1. 沒有leader，這樣，所有節點都是對等的（也就是論文的标題），沒有瓶頸節點，叢集的load分散到各個節點上；
2. client可以把proposal就近發送到某個節點上;
3. 容錯性更高，不會出現因為慢節點而影響叢集的服務品質，降低長尾的latency

epaxos算法的創新

1. 分布式算法執行的過程就是對cmd進行排序的過程：multi-paxox, g-paxos完全由leader配置設定順序；mencius是按照規則預先建立起來的槽位；
2. Epaxos的順序是動态決定的，給每個cmd添加排序的限制（依賴關系），每個節點通過依賴關系最終保證commit的順序是一樣的
3. fast-path：左圖C1和C2更新obj_A和obj_B，沒有沖突，一個roundtrip達成commitslow 2）slow-path：右圖C3和C2都更新obj_A有沖突，C4的update請求在R3上先發生；C3的update請求在R3上後發生，R3拒絕C3的update，同時傳回C3->C4的依賴關系，R1隻需要再進行一次accept階段就可以達成commit）

   

RSM中Cmd順序問題

• cmd之間沒有依賴關系：就沒有必要保證一緻性的順序
• cmd之間有依賴關系：後發生的cmd需要擷取dependencies，每個cmd在發送前攜帶它所看到的dependencies。
• 通過解析dependencies關系，來确定execute順序（epaxos隻保證dependencies是一緻的）

和其他paxos變種協定比較

• mencius paxox：

1. 1. mencius通過預先配置設定instance槽位實作了多寫（mysql的group replication）
   2. 運作速度取決于最慢的一個；
   3. avalibilty比multipaxos還差，一旦任意一個replica出現failure，其他replica都要等待，直到逾時後發起一個noops；

• fast paxos：

1. 1. client發送cmd到所有的replica，減少一跳消息；
   2. 需要一個replica來充當coordinator和learner，當acceptors收到的cmd的順序不一緻時，必須有穩定的leader來仲裁；

• Generalized-Paxos:

1. 1. 當cmd沒有依賴關系，允許亂序commit
   2. 同樣需要leader來給有依賴關系的cmd排序

• 注意：epaxos的fast path需要3個消息，Generalized-Paxos和fast-paxos都需要2個消息（client直接廣播給所有的replica），但是epxos的client是發給本地的replica(co-locate)，在同一個datacenter中，相比wide-area這個延遲可以忽略。這樣的好處是：epaxos可以有一個小的fast-path quorum（沒必要廣播給所有的replica）

epaxos協定的設計

• Preliminaries ：

1. 1. Instance的順序不是事先配置設定的（比如paxos中在issue一個proposal時就要決定出一個instanceID），而是随着cmd被commit時決定出來的；
   2. commit和execute順序沒有必然聯系，是不同的操作（raft的commit順序和execute是一樣的，g-paxos是不一樣的），兩者沒有必要保持一緻；
   3. replica告知client一個cmd被commit了，client并不能知曉這個cmd是否被execute了，隻能通過發起一次read操作，replica會保證先execute；

• 定義command interfere：如果執行[a, b]的順序和執行[b, a]産生的結果不一樣，就說a,b 之間是有依賴關

算法流程

前面提到過，choose和execute的過程是分開了，是以算法分兩個子協定commit protocol和execute protocol。

• Commit protocol分成2個階段

• • 第一階段：fast path

• • • Replica L收到了client發過來的cmd a，開始a的choose過程;
    • L在自己的instance sub-space裡找到下一個instance槽位;
    • L計算自己看到的cmd a的依賴關系deps（也就是在cmd a之前，還有哪些cmd也更新同一個值），依賴關系的計算方法：周遊其他replica 的conficts 的沖突，找到相同key對應的instance（這個instance沒有必要是commit的）；
    • L計算cmd的seq：用來打破循環依賴，周遊所有replica上seq最大值加1；
    • 廣播PreAccept消息(PreAccept=<cmd a, deps, seq>)到fast path；
    • 其他replica收到PreAccept消息後更新内容的conflict map，并且持久化PreAccept（deps,seq也要持久化)；
    • Replica L開始接收RepAccept的Reply消息：

1. 1. 1. 1. 如果cmdleader 收到足夠多的reply，并且這些reply的attribute都是一緻的，意味着多數派看到的attribute是consistent，L就認為可以commit了；
         2. 如果收到attr不同的reply，則更新自己attr：取所有deps的并集，并更新seq為最大值，并且進入第二階段

• • 第二階段：slow path

• • • 這一階段對應basic paxos的accept階段，發送上一階段merge之後的<cmd a, deps, seq>。也就是：Replica L發現了新的依賴關系，要其他的Replica也接受這個依賴關系；
    • Accept消息成功的廣播之後，達成了commit了，發送commit；

      

• execute protocol

• • 每個Replica周遊自己的所有的instance space；
  • 如果instance沒有依賴其他的instance，直接execute；
  • 如果instance有依賴關系，則進行Tarjan算法，尋找以這個點根的最大聯通分量，并把這個聯通分量按照seq排序，依次execute；
  • 如果instance一定的逾時時間之内沒有達到commit，則主動發送prepare，觸發prepare階段；

Epaxos算法的正确性

• 定理1：consistency 和 stability：Replica R上在Q.i commit了cmd a，那麼在其他任意Replica上，它的Q.i在相同instance上commit的cmd也是a

1. 1. basic paxos的限制：v被commit了，更高ballot的v被commit，則兩個v相等
   2. cmd a在Q.i上被commit了，當且僅當Q發起過Phase1，一個instance上Q不能發起多個cmd（原因同multi-paxos）
   3. 如果Q當機，其他Replica通過Prepare消息運作basic paxos過程，以此來保證1中的特性（考慮Q issue了一個cmd失敗了，又issue了另一個cmd）

• 定理2：<cmd a, Deps-a, Seq-a>滿足一緻性
• 定理3：execute consistency：如果兩個有依賴關系的cmd a和cmd b被commit了，那麼a，b的execute順序在所有的replica上是一緻的

1. 1. cmd達成commit時，cmd之間的依賴關系至少在半數以上存在，當commit之後的proposal被issue出去後，會對attr做union操作，也就是說：一旦達成commit，依賴關系就會在後續的cmd被承認
   2. 進行recovery的時候也是成立的

• 定理4：cmd1在cmd2之前被commit，保證cmd1在cmd2之前被execute

recovery協定

• 當一個replica依賴某個instancde時，需要learn，如果learn不到，發送Explicit Prepare：

1. 1. 如果其他replica上有這個instance，則學到後進行comit；
   2. 如果其他replica都沒有，則commit一個noop，讓它不阻塞後面instance的commit
   3. 如果允許client重試，那麼replica在進行cmd1的複制過程時，client認為逾時，又發送給replica一次這個cmd，導緻重複，解決：

1. 1. 1. 唯一的ID；
      2. 幂等性

read leases

• Paxos協定族的讀操作需要像寫一下發起協定流程，否則可能會讀取到老的資料
• 通過限制在一個leases内某個key隻在某個replica上被送出，這個leases對這個key的讀操作也發到這個replica上

和其他協定的資料對比

• 延遲對比

• • 環境：5副本，在每個副本同一個機房部署10個client，異步的發射請求，一共50個client
  • 結論：

1. 1. 1. epaxos具有最好的中位數commit letency
      2. multi-paxos的leader在CA，是以CA的client延時比VA和EU都低
      3. mencius-balance：各個階段壓力均衡的情況下，表現很好，僅次于epaxos（各個replica均攤了load）
      4. mencius-imbalance：各個階段壓力不均衡的情況下，抖動很大（需要主動發起prepare）
      5. epaxs-2%測試集：即使有2%的沖突幾乎不影響延時
      6. epaxos-100%測試集：即使100%的沖突，延遲也優于multi-paxos

         

• 吞吐對比

• • 節點異常測試

• • • 在某個node上執行for循環，搶占cpu，模拟cpu慢：

• • • • epaxos：基本不受影響，其他節點是對等的，可以對等承受壓力
      • mencius：降為50%，原因是，mencius要求是連續的，apply時需要等待慢節點
      • multi：lader是瓶頸節點，一點慢了，就直接影響總體的吞吐

• • • epaxos通過ping探測時延，動态的屏蔽掉慢節點

• • • • mencius：理論性能取決于最慢的一個，因為instances是預配置設定的，必須等待前面的被learn到了，才能進行commit