數(shù)據(jù)一致性理論

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

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

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

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

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

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

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

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

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

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

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