Quorum(NRW)演算法機制簡介

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

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

那麼有沒有一種方案能夠不需要更新完全部的資料，但又保證返回給使用者的是有效資料的解決方案呢？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 理論告訴我們沒有完美的方案。

在有冗餘資料的分散式儲存系統當中，冗餘資料物件會在不同的機器之間存放多份複製。但是同一時刻一個資料物件的多份複製只能用於讀或者用於寫。該演算法可以保證同一份資料物件的多份複製不會被超過兩個訪問物件讀寫。

分散式系統中的每一份資料複製物件都被賦予一票。每一個操作必須要獲得最小的讀票數（Vr）或者最小的寫票數(Vw）才能讀或者寫。如果一個系統有V票（意味著一個資料物件有V份冗餘複製），那麼這最小讀寫票必須滿足：

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

第二條規則保證了資料的序列化修改。一份資料的冗餘複製不可能同時被兩個寫請求修改。

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

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

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