新聞中心

這里有您想知道的互聯(lián)網營銷解決方案

云原生Etcd系列之Quorum和唱票那回事

云原生 Etcd 系列之quorum 和唱票那回事

作者：奇伢 2021-12-06 07:46:45
云計算
云原生唱票是在選舉流程中的一個步驟。還記得以前選班干部的時候，在黑板上寫“正”字，誰得票多誰就獲勝當選。

站在用戶的角度思考問題，與客戶深入溝通，找到思南網站設計與思南網站推廣的解決方案，憑借多年的經驗，讓設計與互聯(lián)網技術結合，創(chuàng)造個性化、用戶體驗好的作品，建站類型包括：網站制作、成都網站制作、企業(yè)官網、英文網站、手機端網站、網站推廣、國際域名空間、虛擬空間、企業(yè)郵箱。業(yè)務覆蓋思南地區(qū)。

本文轉載自微信公眾號「奇伢云存儲」，作者奇伢。轉載本文請聯(lián)系奇伢云存儲公眾號。

關于 Quorum 的兩個維度

前幾回說了那么多框架，設計思想的文章。今天分享一個很小的點，etcd 的 quorum 是怎么實現(xiàn)的?

Quorum 機制本質就是一個關于多數(shù)派的事情，這個多數(shù)派應用的有兩個方面：

選舉過程：獲得多數(shù)節(jié)點投票的節(jié)點才能獲勝，成為 Leader ;
運行過程：被多數(shù)節(jié)點 commit 的日志位置，這個才是被集群可靠記錄的位置。被集群 commit 的日志才能被應用 apply ;

那么這里有兩個小思考問題：

既然是選舉過程，那怎么選舉結果唱票的?

既然是運行過程，那集群的這些節(jié)點怎么確認集群的 commit 位置?

有選舉自然有唱票

唱票是在選舉流程中的一個步驟。還記得以前選班干部的時候，在黑板上寫“正”字，誰得票多誰就獲勝當選。

etcd 里面也有選舉，也就是 Leader 的選舉。Leader 獲勝的依據(jù)是的票滿足大多數(shù)，也就是滿足 quorum 機制。

今天我們就來看看 etcd 的唱票是怎么做的?

很簡單的思路，我們給每個參與選舉的朋友計數(shù)，得票超過半數(shù)的，那么就勝出。

比如說 A，B，C，D，E 五個人競選，那么得到 3 票的就可以勝出。

來看看 etcd 的唱票

選舉屬于 quorum 機制，代碼位于 etcd/raft/quorum/ 下。quorum 的核心實現(xiàn)在 MajorityConfig 的結構體，其實就是個 map 的封裝：

  
 
 
 
   
  
  
  type MajorityConfig map[uint64]struct{}

這個 map 的 key 是節(jié)點的 id，這里面包含了集群的節(jié)點，map 的 value 不重要，所用用的是 struct{} 類型。

思考個小問題：那既然 value 不 care ，那為什么不用 slice 結構?

其實就是為了查找的需求，map 的查找是常數(shù)級別，value 又用的 struct{} ，不占空間，一舉兩得。

  
 
 
 
   
  
  
  // etcd/raft/quorum/majority.go    
  
  
  func (c MajorityConfig) VoteResult(votes map[uint64]bool) VoteResult {    
  
  
      // 搞個長度為 2 的數(shù)組    
  
  
      ny := [2]int{}    
  
  
      // 遍歷集群節(jié)點    
  
  
      for id := range c {    
  
  
          v, ok := votes[id]    
  
  
          if !ok {    
  
  
              // 暫時沒投票的    
  
  
              missing++    
  
  
              continue    
  
  
          }    
  
  
          if v {    
  
  
              // 投票贊同的    
  
  
              ny[1]++    
  
  
          } else {    
  
  
              // 投票拒絕的    
  
  
              ny[0]++    
  
  
          }    
  
  
      }    
  
  
      q := len(c)/2 + 1    
  
  
      if ny[1] >= q {    
  
  
          // 選舉成功：得票數(shù)超過半數(shù)，，比如 votes => [yes, yes, yes]    
  
  
          return VoteWon    
  
  
      }    
  
  
      if ny[1]+missing >= q {    
  
  
          // 未知情況：不確定成功，也不確定失敗    
  
  
          return VotePending    
  
  
      }    
  
  
      // 選舉失敗    
  
  
      return VoteLost    
  
  
  }

唱票的實現(xiàn)很簡單，就如下幾個步驟：

遍歷集群節(jié)點;
統(tǒng)計誰贊同了、誰拒絕了、誰還沒投票;
唱票的結果有三種：成功，失敗，待定;
贊同投票的超過半數(shù)( len(c)/2+1 )，則勝利;

這實現(xiàn)可太簡單了，就是一個遍歷投票結果，寫“正”字，“正”字超過半數(shù)則勝出。

集群的節(jié)點怎么確認集群的 commit 位置?

集群內被多數(shù)節(jié)點 commit 的位置才是集群的 commit 點。也就是說這個也需要滿足 quorum 。這個就有意思了。

關鍵步驟：排序，然后取中間的位置。

取的這個中間的位置就是滿足 quorum 的 commit 。

  
 
 
 
   
  
  
  // etcd/raft/quorum/majority.go    
  
  
  func (c MajorityConfig) CommittedIndex(l AckedIndexer) Index {    
  
  
      // 遍歷集群節(jié)點：取出每個節(jié)點的 commit    
  
  
      for id := range c {    
  
  
          if idx, ok := l.AckedIndex(id); ok {    
  
  
              srt[i] = uint64(idx)    
  
  
              i--    
  
  
          }    
  
  
      }    
  
  
      // 排個序    
  
  
      insertionSort(srt)    
  
  
      
  
  
      // 取中間，這個位置就是大多數(shù) commit 的位置，屬集群共識    
  
  
      pos := n - (n/2 + 1)    
  
  
      return Index(srt[pos])    
  
  
  }

這個實現(xiàn)就很有意思了，撈出每個節(jié)點當前的 commit 位置，組成一個數(shù)組，然后給這個數(shù)組排個序，取中間的位置。這個位置就是集群的 commit 位置，也就是 apply 的位置。

先把集群每個節(jié)點的 commit 位置取出來，是這樣的：

后來排個序是這樣的，黑色的節(jié)點 commit 位置則是集群的 commit 位置：

總結

Quorum 機制是分布式系統(tǒng)中很重要的理論部分，這是一個關于多數(shù)派的機制。etcd 關于多數(shù)派有兩個方面：Leader 選舉和 raft 日志運行;

etcd 的唱票實現(xiàn)非常簡單，就是一個計數(shù)“正”字的實現(xiàn)，用一個 map 記錄集群的節(jié)點，投票計數(shù)超過多數(shù)則勝出;

etcd 確認集群 commit 位置則是先把每個節(jié)點的 commit 位置放在數(shù)組，然后排個序，然后取中間位置，這個位置就是集群的 commit 位置;

多數(shù)節(jié)點 commit 過的日志才是集群 commit 的位置，集群 commit 的日志才能 apply ，這個要記住嘍;

集群 commit 位置將由 Leader 通過心跳或者日志復制的消息告訴其他節(jié)點;

網站名稱：云原生Etcd系列之Quorum和唱票那回事
轉載來源：http://m.fisionsoft.com.cn/article/ccdcdde.html