摩爾投票法和Quorum算法

1. 摩爾投票法

摩爾投票法也可以稱為多數(shù)投票法。

1.1 概述

摩爾投票法(Boyer–Moore majority vote algorithm)出自論文，算法解決的問題是如何在任意多的候選人（選票無序），選出獲得票數(shù)最多的那個(gè)。常見的算法是掃描一遍選票，對每個(gè)候選人進(jìn)行統(tǒng)計(jì)的選票進(jìn)行統(tǒng)計(jì)。當(dāng)候選人的數(shù)目固定時(shí)，這個(gè)常見算法的時(shí)間復(fù)雜度為：，當(dāng)候選人的數(shù)目不定時(shí)，統(tǒng)計(jì)選票可能會(huì)執(zhí)行較長時(shí)間，可能需運(yùn)行的時(shí)間。當(dāng)選票有序時(shí)，可以很容易編出的程序，首先找到中位數(shù)，然后檢查中位數(shù)的個(gè)數(shù)是否超過選票的一半。這篇論文針對無序且侯選人不定的情形，提出了摩爾投票算法。算法的比較次數(shù)最多是選票（記為n）的兩倍，可以在時(shí)間內(nèi)選出獲票最多的，空間開銷為。

1.2 算法

1.2.1 形象化描述

想象著這樣一個(gè)畫面：會(huì)議大廳站滿了投票代表，每個(gè)都有一個(gè)牌子上面寫著自己所選的候選人的名字。然后選舉意見不合的（所選的候選人不同）兩個(gè)人，會(huì)打一架，并且會(huì)同時(shí)擊倒對方。顯而易見，如果一個(gè)人擁有的選票比其它所有人加起來的選票還要多的話，這個(gè)候選人將會(huì)贏得這場“戰(zhàn)爭”，當(dāng)混亂結(jié)束，最后剩下的那個(gè)代表（可能會(huì)有多個(gè)）將會(huì)來自多數(shù)人所站的陣營。但是如果所有參加候選人的選票都不是大多數(shù)（選票都未超過一半），那么最后站在那的代表（一個(gè)人）并不能代表所有的選票的大多數(shù)。因此，當(dāng)某人站到最后時(shí)，需要統(tǒng)計(jì)他所選的候選人的選票是否超過一半（包括倒下的），來判斷選票結(jié)果是否有效。

1.2.2 算法步驟

算法分為兩個(gè)階段：pairing階段和counting階段。

1. pairing階段：兩個(gè)不同選票的人進(jìn)行對抗，并會(huì)同時(shí)擊倒對方，當(dāng)剩下的人都是同一陣營，相同選票時(shí)，結(jié)束。
2. counting階段：計(jì)數(shù)階段，對最后剩下的下進(jìn)行選票計(jì)算統(tǒng)計(jì)，判斷選票是否超過總票數(shù)的一半，選票是否有效。

• pairing階段的簡化

選票不同就要大干一架，太過粗魯，這里提供一種更加現(xiàn)代化的文明方式。
在場的有個(gè)叫onwaier的，他很聰明，他想到一個(gè)方法。他用他那犀利人目光掃一遍所有代表們的選票，在腦子記住兩件事，當(dāng)前的候選人的名字cand和他對應(yīng)的計(jì)數(shù)k（并不是他的選票數(shù)）。起始時(shí)，k的值為0，看每個(gè)人的選票時(shí)，先想想現(xiàn)在k是否為0，如果是0就將cand更新為他將看到的候選人的名字并且將k的值更新為1。觀察每個(gè)人選票的過程，如果這個(gè)人的選票與cand相同，則將k的值加1；否則，將k的值減1。最后的cand可能勝選，還需統(tǒng)計(jì)他的總選票數(shù)是否超過一半。

1.2.3 算法證明

證明：

假設(shè)共有n個(gè)代表（一人一票，選票總數(shù)為n）。當(dāng)onwaier看到第i個(gè)代表的選票時(shí)，前面他已經(jīng)看到的所有選票可以分為兩組，第一組是k個(gè)代表贊同cand；另一組是選票可以全部成對（選票不同）抵銷。當(dāng)處理完所有的選票時(shí)，如果存在大多數(shù)，則cand當(dāng)選。
假設(shè)存在一個(gè)x其不同于cand，但擁有的選票超過。但因?yàn)榈诙M的選票可以全部成對抵銷，所以x最多的選票數(shù)為，因此x必須要收到第一組的選票才能超過一半，但是第一組的選票都是cand的，出現(xiàn)矛盾，假設(shè)不成立。
所以，如果存在大多數(shù)，cand就是那個(gè)。

1.2.4 算法演示

來自網(wǎng)站

選票情況為：
A A A C C B B C C C B C C
結(jié)果應(yīng)該是C

• 算法執(zhí)行過程

1.2.5 算法代碼

• 偽代碼

  function find_majority(A[0..n-1]):
      candidate ← None
      count ← 0
  
      # 第一次遍歷：選出候選人
      for i from 0 to n-1:
          if count = 0:
              candidate ← A[i]
              count ← 1
          else if A[i] = candidate:
              count ← count + 1
          else:
              count ← count - 1
  
      # 候選人即為可能的多數(shù)元素
      # （可選：第二次遍歷校驗(yàn)出現(xiàn)次數(shù)是否 > n/2）
      return candidate
  

• python代碼

  def boyer_moore_majority(nums):
      candidate = None
      count = 0
  
      # 第一次遍歷：尋找候選元素
      for num in nums:
          if count == 0:
              candidate = num
              count = 1
          elif num == candidate:
              count += 1
          else:
              count -= 1
  
      # （可選）第二次遍歷：驗(yàn)證候選是否為多數(shù)
      if nums.count(candidate) > len(nums) // 2:
          return candidate
      else:
          return None  # 不存在多數(shù)元素
  

2. Quorum算法

2.1 概述

分布式系統(tǒng)中的每一份數(shù)據(jù)拷貝對象都被賦予一票。每一個(gè)讀操作獲得的票數(shù)必須大于最小讀票數(shù)（read quorum）（Vr），每個(gè)寫操作獲得的票數(shù)必須大于最小寫票數(shù)（write quorum）(Vw）才能讀或者寫。如果系統(tǒng)有V票（意味著一個(gè)數(shù)據(jù)對象有V份冗余拷貝），那么最小讀寫票數(shù)(quorum)應(yīng)滿足如下限制：

1. Vr + Vw > V（總票數(shù)）
2. Vw > V/2（保證寫多數(shù)）

第一條規(guī)則保證了一個(gè)數(shù)據(jù)不會(huì)被同時(shí)讀寫。當(dāng)一個(gè)寫操作請求過來的時(shí)候，它必須要獲得Vw個(gè)冗余拷貝的許可。而剩下的數(shù)量是V-Vw 不夠Vr，因此不能再有讀請求過來了。同理，當(dāng)讀請求已經(jīng)獲得了Vr個(gè)冗余拷貝的許可時(shí)，寫請求就無法獲得許可了。

第二條規(guī)則保證了數(shù)據(jù)的串行化修改。一份數(shù)據(jù)的冗余拷貝不可能同時(shí)被兩個(gè)寫請求修改。

簡單說，假設(shè)有N個(gè)副本。當(dāng)更新操作w在超過Vw個(gè)副本上成功之后，才認(rèn)為此次更新操作成功；而對于讀操作而言，至少需要讀到Vr個(gè)副本才能讀到此次更新的數(shù)據(jù)。其中Vw+Vr>N，即Vw和Vr有重疊，一般Vr + Vw = N + 1。

舉個(gè)栗子，假設(shè)系統(tǒng)有5個(gè)副本，Vw=3，Vr=3。初始時(shí)數(shù)據(jù)為（V1, V1, V1, V1, V1）——【成功提交的版本號(hào)為1】。

在某次更新操作在3個(gè)副本上成功之后，就認(rèn)為此次更新操作成功。數(shù)據(jù)變成：（V2, V2, V2, V1, V1）——【成功提交的版本號(hào)為2】

因此，最多只需要讀3個(gè)副本，一定就可以讀到V2（此次更新成功的數(shù)據(jù)）。而后臺(tái)可以對剩余的V1同步成V2，且不需要讓Client知道

2.2 架構(gòu)圖

假設(shè)quorum值 = （系統(tǒng)節(jié)點(diǎn)數(shù)/2）+1，B系統(tǒng)必須部署奇數(shù)臺(tái)節(jié)點(diǎn)，A系統(tǒng)每次向B系統(tǒng)發(fā)送數(shù)據(jù)，都必須給B系統(tǒng)中的每個(gè)節(jié)點(diǎn)發(fā)送一次。A系統(tǒng)判斷本次數(shù)據(jù)發(fā)送成功與否的依據(jù)是，在指定時(shí)間內(nèi)，B系統(tǒng)中至少有quorum臺(tái)節(jié)點(diǎn)回復(fù)了ACK，即B系統(tǒng)中超過半數(shù)的節(jié)點(diǎn)接收成功。

2.3 優(yōu)勢

• 提升可用性：寫操作無需等待所有副本響應(yīng)，只需部分副本成功即可。

• 保證一致性：寫和讀操作之間票數(shù)重疊，避免“讀到舊數(shù)據(jù)”或“寫沖突”。

• 容錯(cuò)能力強(qiáng)：集群中即使有若干節(jié)點(diǎn)故障，只要剩余節(jié)點(diǎn)滿足 Quorum，就能繼續(xù)服務(wù)。

Quorum 機(jī)制也廣泛用于分布式共識(shí)算法（如 Paxos、Raft、Zab）的多數(shù)投票流程中，確保決策在至少多數(shù)副本確認(rèn)后才生效，從而避免腦裂和不一致。

2.4 算法實(shí)現(xiàn)

• 偽代碼

procedure majorityVote(A[0..n?1]):
    candidate ← null
    count ← 0

    for i from 0 to n?1 do
        if count == 0 then
            candidate ← A[i]
            count ← 1
        else if A[i] == candidate then
            count ← count + 1
        else
            count ← count ? 1
    return candidate

• python實(shí)現(xiàn)

  def majority_vote(nums):
      # 第一階段：尋找候選人
      candidate = None
      count = 0
      for num in nums:
          if count == 0:
              candidate = num
              count = 1
          elif num == candidate:
              count += 1
          else:
              count -= 1
  
      # 第二階段：驗(yàn)證候選人是否真的是多數(shù)
      if candidate is not None and nums.count(candidate) > len(nums) // 2:
          return candidate
      return None