Quorum

目錄(?)[+]

1. 分布式系統中的讀寫模型
2. 從國小的抽屜原理說起
3. Quorum機制

轉載自http://blog.csdn.net/turkeyzhou/article/details/9307551

和http://blog.csdn.net/zxk364961978/article/details/51865640的結合

分布式系統的設計中會涉及到許多的協定、機制用來解決可靠性問題、資料一緻性問題等，Quorum 機制就是其中的一種。我們通過分布式系統中的讀寫模型來簡單介紹它。

分布式系統中的讀寫模型

　　分布式系統是由多個節點（指代一台伺服器、儲存設備等）構成，由于網絡異常、當機等節點并不能保證正常工作，特别是在節點數量很大的時候，出現異常狀況的節點幾乎是肯定的。為了保證系統的正常運作，能夠提供可靠的服務，分布式系統中對于資料的存儲采用多份資料副本（注：這裡的副本并非隻用來備份，它可參與提供系統服務）來保證可靠性，也就是其中一個節點上讀取資料失敗了那麼可以轉向另外一個存有相同資料副本的節點讀取傳回給使用者。這個過程對于使用者來說是透明的。那麼随之而來的就會帶來資料的副本資料的不一緻性，例如：使用者送出一次修改後，那麼原先儲存的副本顯然就與目前資料不一緻了。解決這個問題最簡單的方法 Read Only Write All ，就是在使用者送出修改操作後，系統确儲存儲的資料所有的副本全部完成更新後，再告訴使用者操作成功；而讀取資料的時候隻需要查詢其中的一個副本資料傳回給使用者就行了。 在很少對存儲的資料進行修改的情形下（例如存檔曆史資料供以後分析），這種解決方案很好。如遇到經常需要修改的情形，寫操作時延時現象就很明顯，加上并發或者連續的執行的話效率就可想而知了。實質，這是由于 Write 和 Read 負載不均衡所緻，Read 很輕松，Write 深表壓力！

　　那麼有沒有一種方案能夠不需要更新完全部的資料，但又保證傳回給使用者的是有效資料的解決方案呢？Quorum機制便是一種選擇。

從國小的抽屜原理說起

      為什麼從抽屜原理說起？一來大家對這個比較熟悉，二來它與Quorum機制有異曲同工的地方。回顧抽屜原理，2個抽屜每個抽屜最多容納2個蘋果，現在有3個蘋果無論怎麼放，其中的一個抽屜裡面會有2個蘋果。那麼我們把抽屜原理變變型，2個抽屜一個放了2個紅蘋果，另一個放了2個青蘋果，我們取出3個蘋果，無論怎麼取至少有1個是紅蘋果，這個了解起來也很簡單。我們把紅蘋果看成更新了的有效資料，青蘋果看成未更新的無效資料。便可以看出來，不需要更新全部資料（并非全部是紅蘋果）我們就可以得到有效資料，當然我們需要讀取多個副本完成（取出多個蘋果）。這就是Quorum機制的原型，其實質是将Write All 的負載均衡到 Read Only 上。

Quorum機制

         蘋果抽屜理論隻是對它的了解，引用參考文獻中對Quorum的定義：

      簡單概括說來就是， Quorum 是一種集合 , l 中任意取集合S,R ，S,R 都存在交集。當然，本文并不打算多講它的數學定義方面的了解，這裡隻是提供個資訊，看不懂也沒事聯系到前面的分布式讀寫模型就能很容易了解這個了。

      回到文章的開頭，我們來看看是怎麼運用Quorum機制來解決讀寫模型中讀寫的負載均衡。其實，關鍵的是更新多少個資料副本後，使得讀取時總能讀到有效資料？回想我們的的紅蘋果，假設總共有 N 個資料副本，其中 k 個已經更新，N-k 個未更新的，那麼我們任意讀取 N-k+1 個資料的時候就必定至少有1個是屬于更新了的k個裡面的，也就是 Quorum 的交集，我們隻需比較 讀取的 N-k+1 中版本最高的那個資料傳回給使用者就可以得到最新更新的資料了。

      那麼對于寫模型呢？我也隻需要完成 k個副本的更新後，就可以告訴使用者操作完成而不需要 Write All 了，當然告訴完使用者完成操作後，系統内部還是會慢慢的把剩餘的副本更新，這對于使用者是透明的。可以看到，我們把 Write 身上的部分負載轉移到了Read上，Read讀取多個副本，使得Write不會過于勞累，不好的是弱化了分布式系統中的資料一緻性。至于轉移多少負載比較合适，這個需要根據分布式系統的具體需求中對資料一緻性的要求。不過，CAP 理論告訴我們沒有完美的方案。

  提高到數學公式：

N表示資料所具有的副本數。

R表示完成讀操作所需要讀取的最小副本數，即一次讀操作所需參與的最小節點數目。

W表示完成寫操作所需要寫入的最小副本數，即一次寫操作所需要參與的最小節點數目。

由Quorum的理論可知，W和R是關聯的，W值決定R值，要擷取最新資料，R > N - W。

假設N=5， 如果R=1， 那麼W必須是5. 是以就是寫入所有的節點是全部節點，那麼讀取任何一個節點就可以最新的資料。 有點就是像讀寫鎖了。

如果R=5， 那麼W隻要是1就可以了。 那麼寫的效率就非常高。 讀取的效率比較低。 

如果R=N/2+1， W=N/2， 讀寫之間為達到某個平衡。 是不錯的政策。兼顧了性能和可用性，Dynamo系統的預設設定就是這種。

由此可得，隻需要保證R + W>N，就可以保證強一緻性。

=====================================================================

基于Quorum投票的備援控制算法

在有備援資料的分布式存儲系統當中，備援資料對象會在不同的機器之間存放多份拷貝。但是同一時刻一個資料對象的多份拷貝隻能用于讀或者用于寫。

該算法可以保證同一份資料對象的多份拷貝不會被超過兩個通路對象讀寫。

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

1. Vr + Vw > V
2. Vw > V/2

第一條規則保證了一個資料不會被同時讀寫。當一個寫操作請求過來的時候，它必須要獲得Vw個備援拷貝的許可。而剩下的數量是V-Vw 不夠Vr，是以不能再有讀請求過來了。同理，當讀請求已經獲得了Vr個備援拷貝的許可時，寫請求就無法獲得許可了。

第二條規則保證了資料的串行化修改。一份資料的備援拷貝不可能同時被兩個寫請求修改。

算法的好處

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

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

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