CAP，ACID，我們能做什麼

05-21

CAP，ACID，我們能做什麼

來自專欄分散式系統思考和相關論文

本文從CAP理論和ACID性質為切入點，討論分散式（存儲）系統的設計。

分散式系統，尤其是分散式存儲系統，在進行設計考慮時，首先需要想到的就是CAP問題，即在C（Consistency）和A（Availability）之間如何進行取捨的問題。我在思考的過程中發現，儘管對於Consistency有著諸多分類，如Linearizability、Sequential Consistency、Causal Consistency，但是對於Availability卻沒有一個對應的分類。這有悖於對CAP理論的理解：我們降低了Consistency之後，能得到什麼程度的Availability？更進一步的，我們降低了Consistency後，是否真的能夠提高Availability？

知乎排版我無 f*ck 可說，連個表格都插不了我也是服氣了，請大家移步 CAP，ACID，我們能做什麼繼續觀看此文

CAP和ACID

我們之所以需要將一個單機系統擴展到分散式系統，主要原因有：

對性能的要求超過單機系統所能提供的極限
對Availability的要求超過單機系統所能提供的極限

對於前者，我們可以使用Shard的方式將負載分布到多個單機系統中。對於後者，我們在設計時必須考慮CAP理論的約束。

CAP

CAP理論的第一個較為正式的形式化表述和證明發表於論文[28]。CAP理論是針對於具有多個Replication的Single Data Object論述的，其模型類似於Distributed Shared Memory。其中P表示Network Partition Tolerance，由於目前一般的網路條件不能認為是可靠的，因此構建在這樣的網路上的系統必須認為Partition是可能發生的，進而在CAP理論中不能放棄P而選擇C和A，詳細的論述見[55]。CAP理論中的C指Linearizability Consistency，其具體含義見下文中的Linearizability一節，我們此時先認為其是一種非常強的一致性保證。CAP理論中的A指的是100%的Read & Write Availability，非形式化的理解，在任意時刻對任意節點發起的（讀或寫）請求，無需等待與系統中其他節點通信的結果，即可進行「正確」響應。

由於Partition不是經常發生[11]，在這樣的情況下，C和A是可以同時達到的。有趣的是，Google對於網路基礎設施的持續改善，使得在他們的網路環境中，由於網路通信導致的問題的概率比由於Bug導致的問題的概率還低，此時甚至可以認為網路是可靠的[17]。但是在Partition發生時，我們必須在Linearizability Consistency和100% Availability之間進行取捨。

這樣一來，就有一個關鍵的問題：如何判斷是否正在發生Network Partition？實踐中我們通常採用消息超時的機制進行判斷，即如果兩個節點之間的通信（即便經過一些重試）超時，則認為此時正在發生Network Partition。使用這種方法進行判斷，我們會發現Latency和Availability是一回事。Latency低的時候，節點之間可以正常通信，從而提供Linearizability Consistency。Latency高的時候，我們認為發生了Network Partition，或者等待Latency降低到足以在Threshold內進行通信（Network Partition解除），即放棄100% Availability但是保證Linearizability Consistency，或者放棄節點間進行通信直接進行響應，即放棄保證Linearizability Consistency但是提供100% Availability。目前越來越多的系統即使在P沒有發生時，也不提供Linearizability Consistency，其這樣做是為了提供更高的性能保證。也就是說，在P發生時，我們在C和A之間進行取捨；在P沒有發生時，我們在C和L（Latency）之間進行取捨。這樣，CAP理論被擴展為PACELC理論（If there is a Partition, how does the system trade off Availability and Consistency; Else, when the system is running normally in the absence of partitions, how does the system trade off Latency and Consistency?），見[1]。

進一步考慮，我們之所以需要在C和A之間進行取捨，或者是在C和L之間進行取捨，其根本原因在於節點之間需要進行同步通信才能夠保證C。極端情況下，我們可以使得整個系統無需進行同步通信，來達到極致的A和L。此時考慮一個寫請求，在寫入一個節點並收到成功確認後，如果該節點在和其他節點進行非同步通信之前就發生了永久性故障，則這一寫請求寫入的內容將永久性的丟失。這說明Consistency和Durability在某種程度上是類似的[43]。

從一個更大的角度來看，在一個不可靠的分散式系統中，我們需要在Safety性質和Liveness性質之間進行取捨[29]。例如，Consistency是一種Safety性質，而Availability是一種Liveness性質。又例如，FLP問題[27]告訴我們在Consensus問題中如果有任意節點不可靠，則無法在保證Safety性質的同時保證Liveness性質。有關分散式系統中的Impossibility的重要問題有[15, 27, 28, 46]。

Paxos演算法可以容忍系統中少數集合中的節點失效，直覺上，我們認為Paxos演算法在系統級別提供高可用服務，同時提供了Linearizability Consistency。這似乎與CAP理論相違背。考慮CAP理論對於Availability的定義，要求對任意節點的請求都能立刻（read-time）得到回應。假設由於網路分區將系統分為了一個多數集和一個少數集，對於Paxos演算法，儘管多數集中的節點仍然可以正確且立即回復請求，但是少數集中的節點不能。CAP理論這樣定義有一定道理，因為在網路分區發生時，有可能客戶端並不能訪問多數集中的節點。

[37]提出了對CAP理論的一些批評和改進。考慮這樣一個事實，Availability是服務的一個觀測結果（Metric）而非系統的一個屬性，而Consistency和Partition是系統模型，這兩者並不能統一起來，CAP理論中對於Availability的定義是不嚴格的。Brewer在[16]中（非形式化的）提出，Availability和Consistency在CAP理論中並不是一個非0即1的離散變數，而是從0%至100%連續變化的變數。這與[28]中形式化描述CAP理論的工作是相違背的。這意味著我們有必要重新思考CAP理論的精確定義（形式化描述）。[37]中將CAP中的A定義為演算法對Latency的敏感程度，將C定義為演算法所使用的並發一致性模型，將P定義為Latency的突發增長。這樣一來，A不再是對服務的一個觀測結果，而是演算法的一個本質屬性；P的定義也能和A相結合。在這樣一種框架下，最終一致性模型也能很好的進行建模和推理，最終得出結論，最終一致性的Replica演算法在Partition永久性的發生時仍然能夠停機。這與我們的直覺，使用最終一致性協議可以提高Availability一致。文中還進一步總結了達成三種一致性模型所需時間的下界（不確定是否是下確界），假設消息傳播時間為 $d$ ，見下表：

Consistency Level | Write latency | Read latency

Linearizability | $mathcal{O}(d)$ | $mathcal{O}(d)$

Sequential Consistency | $mathcal{O}(d)$ | $mathcal{O}(1)$

Causal Consistency | $mathcal{O}(1)$ | $mathcal{O}(1)$

其中Sequential Consistency的讀寫延遲可以互換。

ACID

ACID性質指的是並行執行多個事務（Transaction）時需要保證的性質[33]：

Transaction Atomicity：組成事務的多個事件（Event）要麼都成功要麼都失敗（all-or-nothing）
Database Consistency：執行事務的前後，資料庫的狀態保持（應用程序層面）一致
Isolation：並發執行的事務之間不互相影響
Durability：已經提交的事務中的事件不會丟失

ACID中的Atomicity和Concurrent Programming領域中的Atomicity意義完全不同，為了區分這一點我將ACID中的A稱為Transaction Atomicity。同樣的，ACID中的Consistency和Concurrent Programming領域中的Consistency也完全不同，但是ACID中的Isolation和Concurrent Programming領域中的Consistency有一定相關性。這裡將ACID中的Consistency稱為Database Consistency是因為ACID中的A、I、D是更底層的性質，而C是上層應用的性質，具體見[38]中的第7章。

兩者區別

CAP理論更多的關注於分散式共享內存模型下對象的一致性問題和可用性問題，是傳統Concurrent Programming領域在不可靠系統下的問題。傳統Consistency的分類在[51]中有一個總結，其中比較常見的幾種一致性模型從弱到強如下：

Read-your-writes/Monotonic Reads/Monotonic Writes
PRAM（即FIFO，等於上面三者的和）
Causal（等於PRAM和Writes-follow-reads）
Sequential
Linearizability

ACID性質是資料庫系統中並發執行多個事務時的問題，是資料庫領域的傳統問題。ACID性質中的Isolation從弱到強有以下幾個常見級別[12]：

Read Uncommitted
Read Committed
Cursor Stability
Repeatable Read
Snapshot Isolation
Serializable

Linearizability和Serializability

Linearizability是Concurrent Programming中Consistency的最終目標，Serializability是資料庫事務中Isolation的最終目標，兩者均在分散式存儲系統中起到了重要的作用。

Linearizability

Linearizability是在具有多個副本的單個對象的情況下，對於並發操作的執行順序約束。也可以認為是在給定的並發操作歷史下，對於單個操作返回結果的約束。

Linearizability的原始論文為[35]，但是個人認為[45]的第16章更容易理解，此外[38]的第9章也給出了Linearizability的非形式化解釋。

Linearizability的形式化定義如下[35]：

A history H induces an irreflexive partial order H on operations:

$e_{0} <_{H}e_{1} ext{if} res(e_{0}) ext{precedes} inv(e_{1}) ext{in} H$

A history is linearizable if it can be extended (by appending zero or more response events) to some history such that:

H is equivalent to some legal sequential history
$<_{H} subseteq <_{S}$

直覺上理解，Linearizability執行的結果，等價於按照真實時間順序，依次（非並發的）執行這些事件（Event，在此理解為讀或寫操作）。

Serializability

Serializability是資料庫事務並發執行的約束。一個資料庫事務由涉及到多個對象（也可以只是一個對象）的多個操作（也可以只是一個）組成。Serializability要求這些事務執行的結果，等價於這些事務依次（非並發的）執行的結果。值得注意的是，Serializability並沒有對這些事務的執行順序做出約束。

Serializability的具體描述見[13]的第2章。

兩者區別

Linearizability主要應用於分散式共享內存模型下，對於單個對象的單個操作返回什麼樣的值合法做出限制。Linearizability是一種對Recency的限制，要求歷史上並行操作的執行順序必須反映他們的Real-Time順序。此處Real-Time指的並非實時系統領域的Real-Time，而是對應於全局時鐘而言的真實時間這一概念。

Serializability是資料庫事務並行執行時的Isolation要求，其約束了並行事務執行的結果等價於這些事務「一條接一條」的執行的結果，但是沒有限定這些並行事務的執行順序。資料庫事務通常涉及對多個對象的多個操作。

Serializability和Linearizability結合稱為Strict Serializability或One-copy Serializability。

對於兩者的比較也可以參考[39]。

我們能做什麼

理清了CAP理論和ACID，我們來考慮一下分散式系統設計中能做到什麼，以及如何進行取捨：

在滿足傳統資料庫的強一致性約束下，我們能做到多高的可用性，以及多低的延遲？
在滿足100% Read Write Availability的約束下，我們能做到多高的一致性？
在這兩者之間還存在什麼？

對於這些問題，我們總是從最簡單的模型入手，即多副本的Key-Value Store開始，然後再考慮如何加上分散式事務。當然對於一個分散式資料庫而言，我們至少還應該有Secondary Index，Data Constraint Check，等等功能，但是不在本文中進行進一步展開。

強一致性約束下的分散式系統

我們的目標是實現一個Linearizability Consistency的Key-Value Store，同時支持Serializability Isolation Level的分散式事務。

Linearizability Consistency的實現方法

我們的目標是實現一個Linearizability Consistency的Key-Value Store。由於Linearizability具有Local Property，我們可以將問題進一步簡化。首先我們考慮如何實現一個Atomic Read/Write Register。更具體的，應該是MRMW Atomic Register（Multi-Reader Multi-Writer Atomic Register）。

[38]的P333對於Replication方式是否能實現Linearizability有一個總結：

Single-leader replication (potentially linearizable)
Consensus algorithms (linearizable)
Multi-leader replication (not linearizable)
Leaderless replication (probably not linearizable)

[45]的第16章第4節對於如何實現Linearizability也有一個總結：

Atomicity Based on a Total Order Broadcast Abstraction
Atomicity of Read/Write Objects Based on Server Processes

Atomicity Based on a Server Process and Copy Invalidation
Atomicity Based on a Server Process and Copy Update

總的來說，分為這樣幾種思路：

Total Order Broadcast
Quorum read/write
Write-invalidate & Read-through
Write-through

Total Order Broadcast保證每個replication以相同的順序接收到全序排列的消息，顯然，這符合Linearizability Consistency的定義。使用Consensus演算法，例如Raft、ZAB等，相當於先在Leader節點上定序，然後再將消息和這一順序本身傳播給所有的replication，實際上等同於Total Order Broadcast。關於Total Order Broadcast的分類和實現方法見[23]。

使用Quorum方式實現Linearizability，需要在每次Read/Write操作的之前都進行一次Repair，見[38]的P334，[20]的第4章，以及[4]。需要注意的是，只有Read/Write操作能夠以這種方式實現，Compare-And-Set之類的操作不能以這種形式實現，而必須使用分散式共識（Consensus）演算法，具體見[34]的Fig 1。

Read-through和Write-through的方式主要適用於Cache場景，在分散式存儲場景下使用這樣的方法有較大的丟失數據的風險。

達成Linearizability的代價為Client到Leader的延遲加上Leader到多數集中最慢的節點的延遲。

Serializability Isolation事務的實現方法

在已經有了分散式Key-Value Store的情況下，我們接下來的目標是實現一個Serializability Isolation Level的分散式事務。

在單機資料庫系統中實現Serializability Isolation Level事務的方法（按照Scalability從弱到強）主要有：

真實（單線程）Serialize執行
Strict 2 Phase Locking
Serializable Snapshot Isolation Algorithm

其中，Serialize execute和Strict 2PL（Strict 2 Phase Locking）屬於悲觀並發，SSI（Serializable Snapshot Isolation）屬於樂觀並發。SSI的原理大致是使用Snapshot Isolation但是在提交前檢查是否有已知的寫操作與當前事務的讀操作在Serializability語義下衝突，如果有的話就Abort，沒有的話就可以Commit並且保證Serializability了[21]。

實現分散式事務所需要解決的主要問題是Atomic Commitment，即多個節點all-or-nothing的決議commit或abort一個transaction的問題。Atomic Commitment分為Blocking和Non-blocking兩種。Blocking Atomic Commitment問題可以轉化為Consensus問題[31]。Blocking Atomic Commitment的一個典型的實現方法是2 Phase Commit，但是我覺得應該使用Paxos Commit Algorithm[31]。Non-blocking Atomic Commitment問題嚴格的比Consensus問題難[32]，一個典型的實現方法是3PC（3 Phase Commit），但是由於3PC不能在節點失效時保證正確性，所以幾乎沒有人在實際環境中使用3PC。

對於一個Linearizability Consistency的系統，我們無需關注每個Shard的多個副本（Replication）之間的一致性，因此對於沒有跨越Shard的事務的實現方法和單機資料庫事務的實現方法一致。對於跨越Shard的事務的實現方法，一個可行的方案是使用Paxos Commit Algorithm協調多個Shard，每個Shard使用Strict 2PL。除了需要額外的外部組件記錄整個系統中事務和鎖的關係以便進行死鎖檢測和處理，這個方案基本上和傳統資料庫的事務處理一致。SSI的實現需要解決一個重要問題，即如何跨越Shard生成一致的Snapshot。關於這方面我的經驗不多，希望能在以後閱讀了[26, 36, 48, 49, 53]後在補完這一部分內容（也有可能挖坑不埋）。

強一致性系統的問題

Linearizability Consistency雖然使得我們可以像是對待只有一份副本系統一樣使用這一系統，但是代價不僅是演算法的Network Latency Sensitive，還有Scalability下降。對於一個Linearizability Consistency的系統，不能夠通過增加副本來提高系統的性能。Linearizability Consistency代價非常高，即便是多核CPU也沒有使用Linearizability Consistency[47]。因此，我們應該只在必要的時候提供Linearizability Consistency，例如使用額外的系統（Zookeeper）。

Strict 2PL的並發度也比較低，帶來的問題是事務處理的性能低。SSI的並發度儘管比Strict 2PL要高，但是在高並發場景下Abort的概率也比較高。

高可用性約束下的分散式系統

從[3, 37]中總結的結論，若想實現一個100% Read & Write Available的系統（或者說，讀寫操作的時間複雜度不受節點間通信網路延遲的影響），最高只能支持Causal Consistency。特別的，考慮到Version Vector的大小，甚至可能不支持完全的Causal Consistency。另一方面，從[8]中的結論來看，對於分散式事務的支持最高也只能達到RC（Read Committed），MAV（Monotonic Atomic View）或P-CI（Predicate Cut Isolation）。

這裡故意避開了Eventual Consistency的概念，因為目前還沒有統一的對於Eventual Consistency的形式化的定義，分歧主要集中在How Eventual和What Consistency兩方面。[19, 51]中通過將Linearizability Consistency中的全序關係擴展到偏序關係，並且分解為Visible和Arbitration兩個維度，來統一的描述多種Consistency。特別的，只出現在Arbitration關係中，但是沒有出現在Visible關係中的事件相當於丟失了或被覆蓋了。

Causal Consistency對於很多場景都具有很高的價值。例如在社交網路中，A說自己的小孩走丟了（a1），A又發消息說小孩找到了（a2），B評論說太好了（b）。如果此時C只能看到消息a1和b，就會產生問題。從Causal Relation上看，a1->a2->b，一個Eventual Consistency的系統不提供Causal Relation的保證，但是Causal Consistency必須保證這一點。

儘管如此，目前主流的NoSQL只實現了Eventual Consistency[22]。這是因為實現一個通用的Causal Consistency的代價比較高，例如某個Client先讀取大量的數據然後進行了一次寫入，一個通用的系統不能知道這個寫入只是Causal依賴其中的哪些讀取操作，進而必須捕獲所有的讀取操作。即便是讓用戶顯式指定其寫操作依賴於哪些讀操作，還需要考慮Causal Relation的傳遞性（transitive），即讀操作又依賴於那些讀操作，等等。

Causal Consistency的實現方法

Single Object（或者說Per-Key）的Causal Consistency是容易實現的，使用MVCC等技術可以同時存儲對象的多個版本，在寫入時只需指定其依賴於哪一個版本，即可實現Single Object的Causal Consistency。需要注意的是，為了維持Session Level Guarantees，需要在Session維持期間只與同一個副本進行通信。個人認為，一般情況下，系統應該提供Single Object的Causal Consistency，這一負擔並不重。

可惜的是，不像Linearizability Consistency，Causal Consistency不具有Locality性質。即使實現了Single Object的Causal Consistency，也不能使得整個系統能夠滿足Causal Consistency。

目前，如何實現Causal Consistency是學術上的一個熱點[2, 6, 22, 24, 25, 40–42, 54]，一方面因為Causal Consistency是維持100% Availability情況下所能支持的最高的一致性級別，另一方面是因為Eventual Consistency提供的保證實在是太少了[10, 30]。

高可用分散式事務的實現方法

儘管[8]指出，在保證高可用的情況下，分散式事務最高能支持RC（Read Committed），MAV（Monotonic Atomic View）或P-CI（Predicate Cut Isolation），但是在其中並沒有指出可以使用什麼樣的演算法來做到這一點。特別的，[8]指出他們之所以寫這篇論文，就是因為儘管很多演算法實現了這些分散式事務，但是並沒有支持高可用，很多系統雖然宣稱自己是高可用的，但是用了這些不是高可用的演算法後，也就不是嚴格意義上的高可用系統。

[18]提出了一種無需Coordinator的分散式事務的實現方法，[7]對Coordination Avoidance進行了進一步的論述。Eiger系統分別提供了低延遲的只讀事務和只寫事務[41]，但是仍然需要進一步的仔細檢查，才能知道其是否是高可用的。Anna系統號稱實現了Read Committed級別的跨越Shard的分散式事務[54]，但是沒有披露更多的技術細節。其作者還發布過RAMP事務[9]，提供了低延遲的Read Atomic Isolation分散式事務。總的來說，高可用的分散式事務的實現還是一個開放問題。

其他

[7]對什麼樣的約束檢查需要進行Coordination進行了形式化的論述。總的來說，無需Coordination的約束檢查只能檢查具有Locality性質的約束，而不能檢查全局約束（例如非負計數器，自增主鍵等等）。

目前仍需探索的一個方向是如何在不同級別的Consistency和Isolation Level之間切換[50]。

Recommend Readings

在撰寫本文時，我閱讀了大量的相關資料，在此給出一個文獻的建議閱讀順序。

首先應該閱讀[38]中的第5章、第7章和第9章，這些章節分別介紹了Replication的方法，資料庫事務，Consistency和Consensus及它們之間的關係。這使得讀者對於CAP理論，資料庫事務，Concurrent Programming中的一致性模型，分散式系統的共識問題，有一個初步的理解。

然後建議閱讀[22]，對當前流行的NoSQL系統有一個初步的認識。

對於CAP理論相關的文獻，建議首先閱讀[28]，對於普遍認識中的CAP理論有非形式化和形式化的定義和證明。然後強烈建議閱讀[37]，其作者也是[38]的作者，在這篇論文中提出了對CAP理論現有工作的一些批評和改進，這些批評和改進非常具有啟發性和實用性。然後可以在以下列表中挑選感興趣的內容閱讀：

[16]為CAP理論的提出者Brewer在12年後對CAP理論的回顧和補充
[1]這篇論文將CAP理論擴展為PACELC理論，將Latency納入對Availability的解釋中
[29]這篇論文將CAP理論擴展為Safety性質和Liveness性質的Impossibility問題
[55]解釋了在CAP理論中P是不可捨棄的（應該作為演算法設計模型的一部分），這一問題在[37]中也略有涉及
[51]對於Consistency進行了非常詳盡的形式化的總結，但是強烈建議先看完[19]再看這個，因為其描述方法是沿用[19]中的方式，否則容易看不懂
[52]對Eventual Consistency有一個簡略的介紹和總結
[30]對於Eventual Consistency的Eventual有一個略微深入的展開
[19]是一個對Eventual Consistency非常詳盡和形式化的總結

關於Linearizability Consistency，建議閱讀[45]的第16章，其原始論文為[35]，關於其性能的一些討論可以在[5]中找到。關於Eventual Consistency，建議閱讀[10, 14, 52]，關於其一些形式化的描述，建議閱讀[19, 51]。

關於Serializability建議閱讀[13]的第2章。

關於Concurrent Programming中的Consistency，建議閱讀

對於（單機）資料庫事務，建議閱讀[38]的第7章。關於Serializable Snapshot Isolation，見[21, 44]。關於實現單機資料庫事務的新方法，見[53]。

分散式事務的一致性和分散式共識問題有很強的相關性，建議閱讀[38]中的第9章，以及Lamport寫的[31]。關於Non-blocking Atomic Commitment，建議閱讀[32]。

References

[1] Abadi, D. 2012. Consistency Tradeoffs in Modern Distributed Database System Design: CAP is Only Part of the Story. Computer. 45, 2 (2012), 37–42. DOI:https://doi.org/10.1109/MC.2012.33.

[2] Akkoorath, D.D. et al. 2016. Cure: Strong Semantics Meets High Availability and Low Latency. 2016 IEEE 36th International Conference on Distributed Computing Systems (ICDCS) (Jun. 2016), 405–414.

[3] Attiya, H. et al. 2017. Limitations of Highly-Available Eventually-Consistent Data Stores. IEEE Transactions on Parallel and Distributed Systems. 28, 1 (2017), 141–155. DOI:https://doi.org/10.1109/TPDS.2016.2556669.

[4] Attiya, H. et al. 1995. Sharing memory robustly in message-passing systems. Journal of the ACM. 42, 1 (1995), 124–142. DOI:https://doi.org/10.1145/200836.200869.

[5] Attiya, H. and Welch, J.L. 1994. Sequential consistency versus linearizability. ACM Transactions on Computer Systems. 12, 2 (1994), 91–122. DOI:https://doi.org/10.1145/176575.176576.

[6] Bailis, P. et al. 2013. Bolt-on causal consistency. Proceedings of the 2013 international conference on Management of data - SIGMOD 』13. (2013), 761. DOI:https://doi.org/10.1145/2463676.2465279.

[7] Bailis, P. et al. 2015. Coordination Avoidance in Database Systems. Pvldb. 8, 4 (2015), 185–196. DOI:https://doi.org/1402.2237v2.

[8] Bailis, P. et al. 2013. Highly Available Transactions: Virtues and Limitations. Proceedings of the VLDB Endowment. 7, 3 (2013), 181–192. DOI:https://doi.org/10.14778/2732232.2732237.

[9] Bailis, P. et al. 2014. Scalable atomic visibility with RAMP transactions. Proceedings of the 2014 ACM SIGMOD international conference on Management of data - SIGMOD 』14. (2014), 27–38. DOI:https://doi.org/10.1145/2588555.2588562.

[10] Bailis, P. and Ghodsi, A. 2013. Eventual consistency today. Communications of the ACM. 56, 5 (2013), 55. DOI:https://doi.org/10.1145/2447976.2447992.

[11] Bailis, P. and Kingsbury, K. 2014. The Network is Reliable. Queue. 12, 7 (2014), 20:20-20:32. DOI:https://doi.org/10.1145/2639988.2639988.

[12] Berenson, H. et al. 1995. A critique of ANSI SQL isolation levels. ACM SIGMOD Record. 24, 2 (1995), 1–10. DOI:https://doi.org/10.1145/568271.223785.

[13] Bernstein, P.A. et al. 1987. Concurrency Control and Recovery in Database Systems. Addison-Wesley Pub. Co.

[14] Bernstein, P.A. and Das, S. 2013. Rethinking eventual consistency. Proceedings of the 2013 international conference on Management of data - SIGMOD 』13. (2013), 923. DOI:https://doi.org/10.1145/2463676.2465339.

[15] Borowsky, E. and Gafni, E. 1993. Generalized FLP impossibility result for t -resilient asynchronous computations. Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC 』93. 5, (1993), 91–100. DOI:https://doi.org/10.1145/167088.167119.

[16] Brewer, E. 2012. CAP twelve years later: How the 「rules」 have changed. Computer. 45, 2 (2012), 23–29. DOI:https://doi.org/10.1109/MC.2012.37.

[17] Brewer, E. 2017. Spanner, TrueTime & The CAP Theorem. White Papers. 2015, 4/4/2015 (2017), 1–7.

[18] Burckhardt, S. et al. 2012. Eventually Consistent Transactions. Proceedings of the 22n European Symposium on Programming (ESOP). Springer. 67–86.

[19] Burckhardt, S. 2014. Principles of Eventual Consistency. Foundations and Trends? in Programming Languages. 1, 1–2 (2014), 1–150. DOI:https://doi.org/10.1561/2500000011.

[20] Cachin, C. et al. 2011. Introduction to reliable and secure distributed programming. Springer.

[21] Cahill, M.J. et al. 2009. Serializable isolation for snapshot databases. ACM Transactions on Database Systems. 34, 4 (Dec. 2009), 1–42. DOI:https://doi.org/10.1145/1620585.1620587.

[22] Davoudian, A. et al. 2018. A Survey on NoSQL Stores. ACM Computing Surveys. 51, 2 (Apr. 2018), 1–43. DOI:https://doi.org/10.1145/3158661.

[23] Défago, X. et al. 2004. Total order broadcast and multicast algorithms: Taxonomy and Survey. ACM Computing Surveys. 36, 4 (Dec. 2004), 372–421. DOI:https://doi.org/10.1145/1041680.1041682.

[24] Didona, D. et al. 2017. Okapi: Causally Consistent Geo-Replication Made Faster, Cheaper and More Available. (Feb. 2017).

[25] Du, J. et al. 2014. GentleRain?: Cheap and Scalable Causal Consistency with Physical Clocks. SOCC 』14 Proceedings of the ACM Symposium on Cloud Computing. (2014), 1–13. DOI:https://doi.org/10.1145/2670979.2670983.

[26] Dutta, P. et al. 2005. How fast can eventual synchrony lead to consensus? Proceedings of the International Conference on Dependable Systems and Networks. March (2005), 22–27. DOI:https://doi.org/10.1109/DSN.2005.54.

[27] Fischer, M.J. et al. 1983. Impossibility of distributed consensus with one faulty process. Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems - PODS 』83 (New York, New York, USA, Apr. 1983), 1–7.

[28] Gilbert, S. and Lynch, N. 2002. Brewer』s conjecture and the feasibility of consistent, available, partition-tolerant web services. ACM SIGACT News. 33, 2 (2002), 51. DOI:https://doi.org/10.1145/564585.564601.

[29] Gilbert, S. and Lynch, N. 2012. Perspectives on the CAP Theorem. Computer. 45, 2 (2012), 30–36. DOI:https://doi.org/10.1109/MC.2011.389.

[30] Golab, W. et al. 2014. Eventually consistent: not what you were expecting? Communications of the ACM. 57, 3 (2014), 38–44. DOI:https://doi.org/10.1145/ 2576794.

[31] Gray, J. and Lamport, L. 2004. Consensus on Transaction Commit. 1, April 2004 (2004). DOI:https://doi.org/10.1145/1132863.1132867.

[32] Guerraoui, R. 1995. Revisiting the relationship between non-blocking atomic commitment and consensus. Distributed Algorithms (1995), 87–100.

[33] Haerder, T. and Reuter, A. 1983. Principles of transaction-oriented database recovery. ACM Computing Surveys. 15, 4 (1983), 287–317. DOI:https://doi.org/10.1145/289.291.

[34] Herlihy, M. 1991. Wait-free synchronization. ACM Transactions on Programming Languages and Systems. 13, 1 (1991), 124–149. DOI:https://doi.org/10.1145/114005.102808.

[35] Herlihy, M.P. and Wing, J.M. 1990. Linearizability: a correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems. 12, 3 (Jul. 1990), 463–492. DOI:https://doi.org/10.1145/78969.78972.

[36] Jung, H. et al. 2011. Serializable Snapshot Isolation for Replicated Databases in High-Update Scenarios. PVLDB. 4, 11 (2011), 783–794.

[37] Kleppmann, M. 2015. A Critique of the CAP Theorem. (2015).

[38] Kleppmann, M. 2017. Designing data-intensive applications. O』Reilly Media, Inc.

[39] Linearizability versus Serializability: 2014. http://www.bailis.org/blog/linearizability-versus-serializability/. Accessed: 2018-05-08.

[40] Lloyd, W. et al. 2011. Don』t Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS. Proceedings of the Symposium on Operating Systems Principles. (2011), 1–16. DOI:https://doi.org/10.1145/2043556.2043593.

[41] Lloyd, W. et al. 2013. Stronger Semantics for Low-Latency Geo-Replicated Storage. Proceedings of the Symposium on Networked Systems Design and Implementation. April (2013), 313–328. DOI:https://doi.org/10.1145/2602649.2610533.

[42] Mehdi, S.A. et al. 2017. I Can』t Believe It』s Not Causal! Scalable Causal Consistency with No Slowdown Cascades. 14th {USENIX} Symposium on Networked Systems Design and Implementation, {NSDI} 2017, Boston, MA, USA, March 27-29, 2017. (2017), 453–468.

[43] On Consistency and Durability: http://www.bailis.org/blog/on-consistency-and-durability/. Accessed: 2018-05-08.

[44] Ports, D.R.K. and Grittner, K. 2012. Serializable snapshot isolation in PostgreSQL. Proceedings of the VLDB Endowment. 5, 12 (Aug. 2012), 1850–1861. DOI:https://doi.org/10.14778/2367502.2367523.

[45] Raynal, M. 2013. Distributed Algorithms for Message-Passing Systems. Springer, Berlin, Heidelberg.

[46] Saks, M. and Zaharoglou, F. 1993. Wait-free k-set agreement is impossible. Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC 』93. (1993), 101–110. DOI:https://doi.org/10.1145/167088.167122.

[47] Sewell, P. et al. 2010. X86-TSO: A Rigorous and Usable Programmer』s Model for x86 Multiprocessors. Communications of the ACM. 53, 7 (Jul. 2010), 89. DOI:https://doi.org/10.1145/1785414.1785443.

[48] Shao, J. et al. 2016. Read Consistency in Distributed Database Based on DMVCC. 2016 IEEE 23rd International Conference on High Performance Computing (HiPC). (Dec. 2016), 142–151. DOI:https://doi.org/10.1109/HiPC.2016.11.

[49] Sovran, Y. et al. 2011. Transactional storage for geo-replicated systems. Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles - SOSP 』11. (2011), 385. DOI:https://doi.org/10.1145/2043556.2043592.

[50] Tripathi, A. and Thirunavukarasu, B.D. 2015. A transaction model for management of replicated data with multiple consistency levels. 2015 IEEE International Conference on Big Data (Big Data) (Oct. 2015), 470–477.

[51] Viotti, P. and Vukoli?, M. 2016. Consistency in Non-Transactional Distributed Storage Systems. ACM Computing Surveys. 49, 1 (Jun. 2016), 1–34. DOI:https://doi.org/10.1145/2926965.

[52] Vogels, W. 2008. Eventually Consistent. Queue. 6, 6 (2008), 14. DOI:https://doi.org/10.1145/1466443.1466448.

[53] Wang, T. et al. 2016. Efficiently making (almost) any concurrency control mechanism serializable. The VLDB Journal. 26, 4 (May 2016), 537–562. DOI:https://doi.org/10.1007/s00778-017-0463-8.

[54] Wu, C. et al. 2018. Anna?: A KVS For Any Scale. 34th IEEE International Conference on Data Engineering. (2018).

[55] You Can』t Sacrifice Partition Tolerance: 2010. https://codahale.com/you-cant-sacrifice-partition-tolerance/. Accessed: 2018-04-17.