分布式系統(tǒng)中的讀寫模型
分布式系統(tǒng)是由多個(gè)節(jié)點(diǎn)（指代一臺(tái)服務(wù)器、存儲(chǔ)設(shè)備等）構(gòu)成，由于網(wǎng)絡(luò)異常、宕機(jī)等節(jié)點(diǎn)并不能保證正常工作，特別是在節(jié)點(diǎn)數(shù)量很大的時(shí)候，出現(xiàn)異常狀況的節(jié)點(diǎn)幾乎是肯定的。為了保證系統(tǒng)的正常運(yùn)行，能夠提供可靠的服務(wù)，分布式系統(tǒng)中對(duì)于數(shù)據(jù)的存儲(chǔ)采用多份數(shù)據(jù)副本（注：這里的副本并非只用來備份，它可參與提供系統(tǒng)服務(wù)）來保證可靠性，也就是其中一個(gè)節(jié)點(diǎn)上讀取數(shù)據(jù)失敗了那么可以轉(zhuǎn)向另外一個(gè)存有相同數(shù)據(jù)副本的節(jié)點(diǎn)讀取返回給用戶。這個(gè)過程對(duì)于用戶來說是透明的。那么隨之而來的就會(huì)帶來數(shù)據(jù)的副本數(shù)據(jù)的不一致性，例如：用戶提交一次修改后，那么原先保存的副本顯然就與當(dāng)前數(shù)據(jù)不一致了。
解決這個(gè)問題最簡(jiǎn)單的方法 Read Only Write All ，就是在用戶提交修改操作后，系統(tǒng)確保存儲(chǔ)的數(shù)據(jù)所有的副本全部完成更新后，再告訴用戶操作成功；而讀取數(shù)據(jù)的時(shí)候只需要查詢其中的一個(gè)副本數(shù)據(jù)返回給用戶就行了。 在很少對(duì)存儲(chǔ)的數(shù)據(jù)進(jìn)行修改的情形下（例如存檔歷史數(shù)據(jù)供以后分析），這種解決方案很好。如遇到經(jīng)常需要修改的情形，寫操作時(shí)延時(shí)現(xiàn)象就很明顯，加上并發(fā)或者連續(xù)的執(zhí)行的話效率就可想而知了。
實(shí)質(zhì)，這是由于 Write 和 Read 負(fù)載不均衡所致，Read 很輕松，Write 深表壓力！
解釋：
簡(jiǎn)單概括說來就是， Quorum 是一種集合 , l 中任意取集合S,R ，S,R 都存在交集。當(dāng)然，本文并不打算多講它的數(shù)學(xué)定義方面的理解，這里只是提供個(gè)信息，看不懂也沒事，聯(lián)系到前面的分布式讀寫模型就能很容易理解這個(gè)了。
回到文章的開頭，我們來看看是怎么運(yùn)用Quorum機(jī)制來解決讀寫模型中讀寫的負(fù)載均衡。其實(shí)，關(guān)鍵的是更新多少個(gè)數(shù)據(jù)副本后，使得讀取時(shí)總能讀到有效數(shù)據(jù)？
讀模型:
假設(shè)總共有 **N(副本個(gè)數(shù)) **個(gè)數(shù)據(jù)副本，其中 k 個(gè)已經(jīng)更新，N-k 個(gè)未更新的，那么我們?nèi)我庾x取 N-k+1(讀取副本的個(gè)數(shù))個(gè)數(shù)據(jù)的時(shí)候就必定至少有1個(gè)是屬于更新了的k個(gè)里面的，也就是 Quorum 的交集，我們只需比較 讀取的 N-k+1 中版本最高的那個(gè)數(shù)據(jù)返回給用戶就可以得到最新更新的數(shù)據(jù)了。
寫模型:
我也只需要完成k(寫更新副本的個(gè)數(shù)，大于N/2)個(gè)副本的更新后，就可以告訴用戶操作完成而不需要 Write All 了，當(dāng)然告訴完用戶完成操作后，系統(tǒng)內(nèi)部還是會(huì)慢慢的把剩余的副本更新，這對(duì)于用戶是透明的?？梢钥吹?，我們把 Write 身上的部分負(fù)載轉(zhuǎn)移到了Read上，Read讀取多個(gè)副本，使得Write不會(huì)過于勞累，不好的是弱化了分布式系統(tǒng)中的數(shù)據(jù)一致性。至于轉(zhuǎn)移多少負(fù)載比較合適，這個(gè)需要根據(jù)分布式系統(tǒng)的具體需求中對(duì)數(shù)據(jù)一致性的要求。不過，CAP 理論告訴我們沒有完美的方案。
基于Quorum投票的冗余控制算法
Quorom 機(jī)制，是一種分布式系統(tǒng)中常用的，用來保證數(shù)據(jù)冗余和最終一致性的投票算法，其主要數(shù)學(xué)思想來源于鴿巢原理。
在有冗余數(shù)據(jù)的分布式存儲(chǔ)系統(tǒng)當(dāng)中，冗余數(shù)據(jù)對(duì)象會(huì)在不同的機(jī)器之間存放多份拷貝。但是同一時(shí)刻一個(gè)數(shù)據(jù)對(duì)象的多份拷貝只能用于讀或者用于寫。
該算法可以保證同一份數(shù)據(jù)對(duì)象的多份拷貝不會(huì)被超過兩個(gè)訪問對(duì)象讀寫。
算法來源于[Gifford, 1979][3][1]。 分布式系統(tǒng)中的每一份數(shù)據(jù)拷貝對(duì)象都被賦予一票。每一個(gè)操作必須要獲得最小的讀票數(shù)（Vr）或者最小的寫票數(shù)(Vw）才能讀或者寫。如果一個(gè)系統(tǒng)有V票（意味著一個(gè)數(shù)據(jù)對(duì)象有V份冗余拷貝），那么這最小讀寫票必須滿足：
Vr + Vw > V
Vw > V/2
第一條規(guī)則保證了一個(gè)數(shù)據(jù)不會(huì)被同時(shí)讀寫。當(dāng)一個(gè)寫操作請(qǐng)求過來的時(shí)候，它必須要獲得Vw個(gè)冗余拷貝的許可。而剩下的數(shù)量是V-Vw 不夠Vr，因此不能再有讀請(qǐng)求過來了。同理，當(dāng)讀請(qǐng)求已經(jīng)獲得了Vr個(gè)冗余拷貝的許可時(shí)，寫請(qǐng)求就無法獲得許可了。
第二條規(guī)則保證了數(shù)據(jù)的串行化修改。一份數(shù)據(jù)的冗余拷貝不可能同時(shí)被兩個(gè)寫請(qǐng)求修改。
算法好處
在分布式系統(tǒng)中，冗余數(shù)據(jù)是保證可靠性的手段，因此冗余數(shù)據(jù)的一致性維護(hù)就非常重要。一般而言，一個(gè)寫操作必須要對(duì)所有的冗余數(shù)據(jù)都更新完成了，才能稱為成功結(jié)束。比如一份數(shù)據(jù)在5臺(tái)設(shè)備上有冗余，因?yàn)椴恢雷x數(shù)據(jù)會(huì)落在哪一臺(tái)設(shè)備上，那么一次寫操作，必須5臺(tái)設(shè)備都更新完成，寫操作才能返回。
對(duì)于寫操作比較頻繁的系統(tǒng)，這個(gè)操作的瓶頸非常大。Quorum算法可以讓寫操作只要寫完3臺(tái)就返回。剩下的由系統(tǒng)內(nèi)部緩慢同步完成。而讀操作，則需要也至少讀3臺(tái)，才能保證至少可以讀到一個(gè)最新的數(shù)據(jù)。
Quorum的讀寫最小票數(shù)可以用來做為系統(tǒng)在讀、寫性能方面的一個(gè)可調(diào)節(jié)參數(shù)。寫票數(shù)Vw越大，則讀票數(shù)Vr越小，這時(shí)候系統(tǒng)寫的開銷就大。反之則寫的開銷就小
該算法滿足CAP理論的 A（可用性）和P（容錯(cuò)性），不滿足 C（一致性）
NWR 策略讀寫模型的例子
假設(shè)兩個(gè)進(jìn)程同時(shí)來更新這份數(shù)據(jù)，進(jìn)程W1要把值改寫成C，進(jìn)程W2要把值改寫成B，那就有可能出現(xiàn)下圖的情形，兩個(gè)進(jìn)程各拿到一個(gè)副本改寫，都認(rèn)為自己的寫操作是成功的，結(jié)果卻留給系統(tǒng)三個(gè)不同的副本，這樣就出現(xiàn)數(shù)據(jù)副本不一致的問題。
所以公式W> N/2, 實(shí)際上變成了一個(gè)寫的鎖，意味著只有寫了過半數(shù)副本的才算寫成功，拿不到的就返回失敗，解決了競(jìng)爭(zhēng)的問題。如下圖，W1的會(huì)話成功，W2的會(huì)話就返回失敗。
W> N/2,同時(shí)意味著不需要把所有的副本都寫完，未完成的留給系統(tǒng)自己后臺(tái)慢慢同步，那這個(gè)時(shí)候問題就來了，一個(gè)新的會(huì)話過來讀數(shù)據(jù)的時(shí)候，分配到的副本有可能是沒來得及更新的。這時(shí)候R1讀回去的就是過時(shí)的數(shù)據(jù)B，而非最新的數(shù)據(jù)C
第2個(gè)公式變形下就是R> N-W,R=2就避免正好倒霉讀到?jīng)]更新的那一個(gè)。這樣讀回去C和B兩個(gè)數(shù)據(jù)，再比較后取最新的C。所以W+R> N 能夠保證每個(gè)讀的請(qǐng)求至少讀到一份最新的數(shù)據(jù)，
