數(shù)據(jù)一致性理論第一頁，共十四頁，編輯于2023年，星期三2.1CAP理論CAP理論由EricBrewer在ACMPODC會(huì)議上的主題報(bào)告中提出，這個(gè)理論是NoSQL數(shù)據(jù)庫管理系統(tǒng)構(gòu)建的基礎(chǔ)，如下圖所示：第二頁，共十四頁，編輯于2023年，星期三其中字母“C”,”A”,”P”分別代表以下三個(gè)特征：強(qiáng)一致性（Consistency）。系統(tǒng)在執(zhí)行過某項(xiàng)操作后仍然處于一致的狀態(tài)。在分布式系統(tǒng)中，更新操作執(zhí)行成功后所有的用戶都應(yīng)該讀取到最新值。可用性（Availability）。每一個(gè)操作總是能夠在一定時(shí)間內(nèi)返回結(jié)果。需要注意“一定時(shí)間”和“返回結(jié)果”?！耙欢〞r(shí)間”是指，系統(tǒng)結(jié)果必須在給定時(shí)間內(nèi)返回?！胺祷亟Y(jié)果”是指系統(tǒng)返回操作成功或失敗的結(jié)果。分區(qū)容錯(cuò)性（PartitionTolerance）。分區(qū)容錯(cuò)性可以理解為系統(tǒng)在存在網(wǎng)絡(luò)分區(qū)的情況下仍然可以接受請(qǐng)求（滿足一致性和可用性）。第三頁，共十四頁，編輯于2023年，星期三CAP是在分布式環(huán)境中設(shè)計(jì)和部署系統(tǒng)時(shí)所要考慮的三個(gè)重要的系統(tǒng)需求。根據(jù)CAP理論，數(shù)據(jù)共享系統(tǒng)只能滿足這三個(gè)特性中兩個(gè)，而不能同時(shí)滿足三個(gè)條件。因此系統(tǒng)設(shè)計(jì)者必須在這三個(gè)特征之間做出權(quán)衡。根據(jù)CAP理論，系統(tǒng)滿足三個(gè)條件中不同的兩個(gè)條件會(huì)具有不同的特點(diǎn)。如下表所示：序號(hào)選擇特點(diǎn)例子1C、A兩階段提交、緩存驗(yàn)證協(xié)議傳統(tǒng)數(shù)據(jù)庫、集群數(shù)據(jù)庫2C、P悲觀加鎖分布式數(shù)據(jù)庫、分布式加鎖3A、P沖突處理、樂觀DNS、Coda第四頁，共十四頁，編輯于2023年，星期三2.1數(shù)據(jù)一致性模型

一些分布式系統(tǒng)通過復(fù)制數(shù)據(jù)來提高系統(tǒng)的可靠性和容錯(cuò)性，并且將數(shù)據(jù)的不同的副本存放在不同的機(jī)器，由于維護(hù)數(shù)據(jù)副本的一致性代價(jià)高，因此許多系統(tǒng)采用若一致性來提高性能，一些不同的一致性模型也相繼被提出。

強(qiáng)一致性：要求無論更新操作是在哪一個(gè)副本執(zhí)行，之后所有的讀操作都要能獲得最新的數(shù)據(jù)。

弱一致性：用戶讀到某一操作對(duì)系統(tǒng)特定數(shù)據(jù)的更新需要一段時(shí)間，我們稱這段時(shí)間為“不一致性窗口”。

最終一致性：是弱一致性的一種特例，保證用戶最終能夠讀取到某操作對(duì)系統(tǒng)特定數(shù)據(jù)的更新。第五頁，共十四頁，編輯于2023年，星期三2.3ACID與BASEBASE方法通過犧牲一致性和孤立性來提高可用性和系統(tǒng)性能，其中BASE分別代表：基本可用（BasicallyAvailable)：系統(tǒng)能夠基本運(yùn)行、一直提供服務(wù)。軟狀態(tài)（Soft-state)：系統(tǒng)不要求一直保持強(qiáng)一致狀態(tài)。最終一致性（Eventualconsistency）：系統(tǒng)需要在某一時(shí)刻后達(dá)到一致性要求。第六頁，共十四頁，編輯于2023年，星期三事務(wù)是用戶定義的一個(gè)數(shù)據(jù)庫操作序列，要么全不做，要么全做，是一個(gè)不可分割的工作單位，ACID是事務(wù)所具有的特性。

原子性（Atomicity）：事務(wù)中的操作要么全做，要么不做。一致性（Consistency)：系統(tǒng)必須始終處在強(qiáng)一致狀態(tài)下。

隔離性（Isolation）：一個(gè)事務(wù)的執(zhí)行不能被其他事務(wù)所干擾。

持續(xù)性（Durability）：一個(gè)已提交的事務(wù)對(duì)數(shù)據(jù)庫中數(shù)據(jù)的改變是永久性的。保證ACID特性是傳統(tǒng)關(guān)系型數(shù)據(jù)庫中事務(wù)管理的重要任務(wù)，也是恢復(fù)和并發(fā)控制的基本單位。第七頁，共十四頁，編輯于2023年，星期三

ACID和BASE的比較ACIDBASE強(qiáng)一致性若一致性隔離性可用性優(yōu)先采用悲觀、保守方法采用樂觀方法難以改變適應(yīng)變化、更簡(jiǎn)單、更快第八頁，共十四頁，編輯于2023年，星期三2.4數(shù)據(jù)一致性實(shí)現(xiàn)技術(shù)2.4.1Quorum系統(tǒng)NRW策略這個(gè)協(xié)議有三個(gè)關(guān)鍵值N、R、W。N表示數(shù)據(jù)所具有的副本數(shù)。R表示完成讀操作所需要讀取的最小副本數(shù)，即一次讀操作所需參與的最小節(jié)點(diǎn)數(shù)目。W表示完成寫操作所需要寫入的最小副本數(shù)，即一次寫操作所需要參與的最小節(jié)點(diǎn)數(shù)目。該策略中，只需要保證R+W>N，就可以保證強(qiáng)一致性。R和W的設(shè)置直接影響系統(tǒng)的性能、擴(kuò)展性與一致性。第九頁，共十四頁，編輯于2023年，星期三下面為不同設(shè)置的幾種特殊情況。1.當(dāng)W=1,R=N時(shí)，系統(tǒng)對(duì)寫操作有較高的要求，但讀操作會(huì)比較慢，若N個(gè)節(jié)點(diǎn)中有節(jié)點(diǎn)發(fā)生故障，那么讀操作將不能完成。2.當(dāng)R=1，W=N時(shí)，系統(tǒng)對(duì)讀操作有較高性能、高可用，但寫操作性能較低，用于需要大量讀操作的系統(tǒng)，若N個(gè)節(jié)點(diǎn)中有節(jié)點(diǎn)發(fā)生故障，那么寫操作將不能完成。3.當(dāng)R=Q,W=Q(Q=N/2+1)時(shí)，系統(tǒng)在讀寫性能之間取得平衡，兼顧了性能和可用性。第十頁，共十四頁，編輯于2023年，星期三2.4.2兩階段提交協(xié)議在兩階段提交協(xié)議中，系統(tǒng)包含兩類機(jī)器（或節(jié)點(diǎn)）：一類為協(xié)調(diào)者，通常一個(gè)系統(tǒng)中只有一個(gè)；另一類為事務(wù)參與者，一般包含多個(gè)，在數(shù)據(jù)存儲(chǔ)系統(tǒng)中可以理解為數(shù)據(jù)副本的個(gè)數(shù)。階段1：請(qǐng)求階段在請(qǐng)求階段，協(xié)調(diào)者將通知事務(wù)參與者準(zhǔn)備提交或取消事務(wù)，然后進(jìn)入表決過程。在表決過程中，參與者將告知協(xié)調(diào)者自己的決策：同意或取消。階段2：提交階段協(xié)調(diào)者將第一階段投票結(jié)果進(jìn)行表決，當(dāng)且僅當(dāng)所有的參與者同意提交，事務(wù)協(xié)調(diào)者才通知所有的參與者提交事務(wù)。參與者在接收到協(xié)調(diào)者發(fā)來的消息后將執(zhí)行相應(yīng)操作。第十一頁，共十四頁，編輯于2023年，星期三2.4.3時(shí)間戳策略時(shí)間戳策略在關(guān)系數(shù)據(jù)庫中有廣泛應(yīng)用，該策略主要用于關(guān)系數(shù)據(jù)庫日志系統(tǒng)中記錄事務(wù)操作，以及數(shù)據(jù)恢復(fù)時(shí)的Undo/Redo等操作。在并行系統(tǒng)中，時(shí)間戳策略有更加廣泛的應(yīng)用。我們用分布式系統(tǒng)中事件的先后關(guān)系，用“->”符號(hào)來表示，例如：若事件a發(fā)生在事件b之前，那么a->b。該關(guān)系需要滿足下列三個(gè)條件：如果a和b是同一進(jìn)程中的事件，a在b之前發(fā)生，則a->b。

如果事件a是消息發(fā)送方，b是接受方，則a->b。

對(duì)于事件a、b、c，如果有a->b，b->c，則有a->c。第十二頁，共十四頁，編輯于2023年，星期三邏輯時(shí)鐘這里為每一進(jìn)程Pi定義一個(gè)時(shí)鐘Ci,該時(shí)鐘能夠?yàn)槿我庖粋€(gè)事件a分配一個(gè)時(shí)鐘：Ci(a)。在全局上，同樣存在一個(gè)時(shí)鐘C，對(duì)于事件b，該時(shí)鐘能夠分配一個(gè)時(shí)鐘值C（b）,并且如果事件b發(fā)生在進(jìn)程Pi上，那么C（b)=Ci(b)。時(shí)鐘條件：如果對(duì)于事件a和事件b,a->b,那么C(a)<C(b)。以下兩個(gè)限制條件滿足實(shí)際情況。C1：如果事件a和事件b是同一個(gè)進(jìn)程Pi中的事件，并且a在b之前發(fā)生，那么：Ci(a)<Ci(b)C2:如果a為進(jìn)程Pi上某消息發(fā)送事件，b為進(jìn)程Pj上消息接收事件，那么：Ci(a)<Ci(b)第十三頁，共十四頁，編輯于2023年，星期三下面我們來說明該系統(tǒng)是如何滿足C1和C2條件的。對(duì)于C1條件來說，系統(tǒng)需要滿足下面的實(shí)現(xiàn)規(guī)則。IR1：對(duì)于同一節(jié)點(diǎn)上任意的連續(xù)事件來說，該節(jié)點(diǎn)上的時(shí)鐘只需要保證較晚發(fā)生事件的時(shí)鐘值大于較早發(fā)生事件的時(shí)鐘值即可。對(duì)于C2條件來