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

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

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

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

關(guān)于 Quorum 的兩個維度

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

Quorum 機(jī)制本質(zhì)就是一個關(guān)于多數(shù)派的事情，這個多數(shù)派應(yīng)用的有兩個方面：

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

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

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

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

有選舉自然有唱票

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

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

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

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

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

來看看 etcd 的唱票

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

  
 
 
 

   
  
  
  
type MajorityConfig map[uint64]struct{} 
  
 
 
 

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

思考個小問題：那既然 value 不 care ，那為什么不用 slice 結(jié)構(gòu)?

其實就是為了查找的需求，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)計誰贊同了、誰拒絕了、誰還沒投票;
• 唱票的結(jié)果有三種：成功，失敗，待定;
• 贊同投票的超過半數(shù)( len(c)/2+1 )，則勝利;

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

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

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

關(guān)鍵步驟：排序，然后取中間的位置。

取的這個中間的位置就是滿足 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é)點當(dāng)前的 commit 位置，組成一個數(shù)組，然后給這個數(shù)組排個序，取中間的位置。這個位置就是集群的 commit 位置，也就是 apply 的位置。

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

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

總結(jié)

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

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

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

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

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

網(wǎng)站題目：云原生Etcd系列之Quorum和唱票那回事
標(biāo)題網(wǎng)址：http://m.5511xx.com/article/ccdcdde.html