[[438630]]

本文轉(zhuǎn)載自微信公眾號(hào)「奇伢云存儲(chǔ)」，作者奇伢。轉(zhuǎn)載本文請(qǐng)聯(lián)系奇伢云存儲(chǔ)公眾號(hào)。

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

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

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

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

那么這里有兩個(gè)小思考問(wèn)題：

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

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

有選舉自然有唱票

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

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

今天我們就來(lái)看看 etcd 的唱票是怎么做的?

很簡(jiǎn)單的思路，我們給每個(gè)參與選舉的朋友計(jì)數(shù)，得票超過(guò)半數(shù)的，那么就勝出。

比如說(shuō) A，B，C，D，E 五個(gè)人競(jìng)選，那么得到 3 票的就可以勝出。

來(lái)看看 etcd 的唱票

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

type MajorityConfig map[uint64]struct{} 

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

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

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

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

唱票的實(shí)現(xiàn)很簡(jiǎn)單，就如下幾個(gè)步驟：

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

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

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

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

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

取的這個(gè)中間的位置就是滿足 quorum 的 commit 。

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

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

先把集群每個(gè)節(jié)點(diǎn)的 commit 位置取出來(lái)，是這樣的：

后來(lái)排個(gè)序是這樣的，黑色的節(jié)點(diǎn) commit 位置則是集群的 commit 位置：

總結(jié)

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

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

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

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

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