【轉載】ACID、Data Replication、CAP與BASE

【acid】

      在傳統資料庫系統中，事務具有 acid 4 個屬性（ jim gray 在《事務處理：概念與技術》中對事務進行了詳盡的讨論）。

原子性（atomicity）：事務是一個原子操作單元，其對資料的修改，要麼全都執行，要麼全都不執行。

一緻性（consistent）：在事務開始和完成時，資料都必須保持一緻狀态。這意味着所有相關的資料規則都必須應用于事務的修改，以保持資料的完整性；事務結束時，所有的内部資料結構（如b樹索引或雙向連結清單）也都必須是正确的。

隔離性（isolation）：資料庫系統提供一定的隔離機制，保證事務在不受外部并發操作影響的“獨立”環境執行。這意味着事務處理過程中的中間狀态對外部是不可見的，反之亦然。

持久性（durable）：事務完成之後，它對于資料的修改是永久性的，即使出現系統故障也能夠保持。

      對于單個節點的事務，資料庫都是通過并發控制（兩階段鎖 - two phase locking 或者多版本 - multiversioning）和恢複機制（日志技術）保證事務的 acid 特性。對于跨多個節點的分布式事務，通過兩階段送出協定（two phase commiting）來保證事務的 acid 。 

       可以說，資料庫系統是伴随着金融業的需求而快速發展起來。對于金融業，可用性和性能都不是最重要的，而一緻性是最重要的，使用者可以容忍系統故障而停止服務，但絕不能容忍帳戶上的錢無故減少(當然，無故增加是可以的)。而強一緻性的事務是這一切的根本保證。 

【data replication】 

       資料複制（data replication）屬于分布式計算的範疇，它并不僅僅局限于資料庫，但這裡主要是指分布式資料庫的複制。 

       在多副本構成的分布式資料庫系統中， 其事務特性與單個資料庫系統的差别主要表現在原子性和一緻性兩個方面。在原子性方面， 要求同一分布式事務的所有操作在所有相關副本上要麼送出， 要麼復原， 即除了保證原有的局部事務的原子性，還需要控制全局事務的原子性； 在一緻性方面，多副本之間需要保證單一副本一緻性。  

       針對分布式事務的原子性和一緻性這兩個複制協定中的核心問題，經過近20年的研究，人們提出了各種各樣的複制協定。這些協定在外在功能和内部實作兩方面都有較大的差别。據此，我們可以從這兩個大的方面進行分類說明。 

       從外在功能的角度看，依據文獻[1]，可以從事務執行的地點和時間兩個方面進行分類。從事務執行的地點，可以分為兩類：主從（priamry / copy）方式和更新所有（update-anywhere）方式。 

       前者的處理過程一般是系統中僅僅指定一個 primary 節點接受更新請求，在事務操作執行完畢後， 在事務送出前或後将操作廣播到其他 copy 節點。

       後者的處理過程稍微複雜，系統中的任何副本具有相同的地位，都可以接收 update 請求，在檢測事務沖突、 事務送出前或後将各個節點的 update 傳播到其他副本節點。 

       primary / copy 方式并發控制較為簡單， 由 primary 本地的事務控制即可實作， 事務的原子性的實作也較為簡單， 一般由 primary 節點作為協調節點來實作。但是其缺陷也顯而易見：僅僅單個節點提供 update 請求處理能力，對于 update 密集類型的應用， 如 oltp，容易形成單點性能瓶頸。update-anywhere 方式則與其相輔相成，可以通過多點提高事務吞吐率，但随之而來的是多個分布式事務之間複雜的并發控制和原子性問題。 

       從事務送出的時間點看， 可以分為積極（eager）和消極（lazy）兩類。其差別在于，前者是在事務送出前傳播更新，後者則是在送出之後才将事務操作傳播到其他副本。實際上，前者即通常所謂的同步複制（synchronous replication），後者即所謂的異步複制（asynchronous replication）。 

       異步複制的優點是可以提高響應速度，但犧牲了一緻性，一般實作該類協定的算法需要增加額外的補償機制。同步複制的優點是可以保證一緻性（一般通過兩階段送出協定），但是開銷較大，可用性不好（參見 cap 部分），帶來了更多的沖突和死鎖等問題。值得一提的是 lazy + primary/copy 的複制協定在實際生産環境中是非常實用的，mysql 的複制實際上就屬于這種。 

【cap】 

       在 2000 年的 podc（principles of distributed computing）會議上，brewer 提出了著名的 cap 理論。2002 年，seth gilbert 和 nancy lynch 證明了這一理論。cap 指的是：consistency、availability 和 partition tolerance 。   

consistency（一緻性）：一緻性是說資料的原子性，這種原子性在經典的資料庫中是通過事務來保證的，當事務完成時，無論其是成功還是復原，資料都會處于一緻的狀态。在分布式環境中，一緻性是說多個節點的資料是否一緻。

availability（可用性）：可用性是說服務能一直保證是可用的狀态，當使用者發出一個請求，服務能在有限時間内傳回結果。

partition tolerance（分區容錯性）：partition 是指網絡的分區。可以這樣了解，一般來說，關鍵的資料和服務都會位于不同的 idc 。

       cap 理論告訴我們，一個分布式系統不可能同時滿足一緻性，可用性和分區容錯性這三個需求，三個要素中最多隻能同時滿足兩點。三者不可兼顧，此所謂魚與熊掌不可兼得也！而對于分布式資料系統而言，分區容錯性是基本要求，否則就不稱其為分布式系統了。是以架構設計師不要把精力浪費在設計如何能同時滿足三者的完美分布式系統上，而是應該進行權衡取舍。這也意味着分布式系統的設計過程，也就是根據業務特點在c（一緻性）和a（可用性）之間尋求平衡的過程，要求架構師真正了解系統需求，把握業務特點。 

【base】 

        base 來自于網際網路的電子商務領域的實踐，它是基于 cap 理論逐漸演化而來，核心思想是即便不能達到強一緻性（strong consistency），但可以根據應用特點采用适當的方式來達到最終一緻性（eventual consistency）的效果。base 是 basically available、soft state、eventually consistent 三個詞組的簡寫，是對 cap 中 c & a 的延伸。base 的含義：   

basically available：基本可用；

soft-state：軟狀态/柔性事務，即狀态可以有一段時間的不同步；

eventual consistency：最終一緻性；

        base 是反 acid 的，它完全不同于 acid 模型，犧牲強一緻性，獲得基本可用性和柔性可靠性并要求達到最終一緻性。 

       cap、base 理論是目前在網際網路領域非常流行的 nosql 的理論基礎。 

主要參考 

[1]j.n.gray, p.helland,and a.d.s.p.o’neil. the dangers of replication and a solution. in proceedings of the 1996 acm sigmod international conference on management of data, pages 173–182,montreal, canada, june 1996.sigmod. 

[2]gilbert , s., lynch, n. 2002. brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services. acm sigact news 33(2). 

[3]http://www.allthingsdistributed.com/2008/12/eventually_consistent.html 

[4]http://queue.acm.org/detail.cfm?id=1394128 

[5]http://en.wikipedia.org/wiki/acid