Quorum (分布式系統)

  提示：此條目的主題不是法定人數。

Quorum 機制，是一種分布式系統中常用的，用來保證數據冗餘和最終一致性的投票算法，其主要數學思想來源於鴿巢原理。

基於Quorum投票的冗餘控制算法

在有冗餘數據的分布式存儲系統當中，冗餘數據對象會在不同的機器之間存放多份拷貝。但是同一時刻一個數據對象的多份拷貝只能用於讀或者用於寫。

該算法可以保證同一份數據對象的多份拷貝不會被超過兩個訪問對象讀寫。

算法來源於[Gifford, 1979][3]。 分布式系統中的每一份數據拷貝對象都被賦予一票。每一個讀操作獲得的票數必須大於最小讀票數（read quorum）（V_r），每個寫操作獲得的票數必須大於最小寫票數（write quorum）(V_w）才能讀或者寫。如果系統有V票（意味着一個數據對象有V份冗餘拷貝），那麼最小讀寫票數(quorum)應滿足如下限制：

1. V_r + V_w > V
2. V_w > V/2

第一條規則保證了一個數據不會被同時讀寫。當一個寫操作請求過來的時候，它必須要獲得V_w個冗餘拷貝的許可。而剩下的數量是V-V_w 不夠V_r，因此不能再有讀請求過來了。同理，當讀請求已經獲得了V_r個冗餘拷貝的許可時，寫請求就無法獲得許可了。

第二條規則保證了數據的串行化修改。一份數據的冗餘拷貝不可能同時被兩個寫請求修改。

算法的好處

在分布式系統中，冗餘數據是保證可靠性的手段，因此冗餘數據的一致性維護就非常重要。一般而言，一個寫操作必須要對所有的冗餘數據都更新完成了，才能稱為成功結束。比如一份數據在5台設備上有冗餘，因為不知道讀數據會落在哪一台設備上，那麼一次寫操作，必須5台設備都更新完成，寫操作才能返回。

對於寫操作比較頻繁的系統，這個操作的瓶頸非常大。Quorum算法可以讓寫操作只要寫完3台就返回。剩下的由系統內部緩慢同步完成。而讀操作，則需要也至少讀3台，才能保證至少可以讀到一個最新的數據。

Quorum的讀寫最小票數可以用來做為系統在讀、寫性能方面的一個可調節參數。寫票數V_w越大，則讀票數V_r越小，這時候系統讀的開銷就小。反之則寫的開銷就小。