2018年4月20日，蘋果宣布開源FoundationDB——一款支持多種數據模型、高性能、高可用、可擴展，且具備ACID事務的分布式KV NoSQL系統。FoundationDB已在蘋果公司內部的生產環境使用三年，主要用于iCloud上的云存儲服務。

蘋果于2015年收購開源的FoundationDB并將其閉源。此次再次開源，是因為蘋果預見到：FoundationDB有潛力成為下一代分布式數據庫系統的底層基礎設施。同時，也希望借助社區的力量，利用FoundationDB設計的分層機制，開發以其為底層核心且符合各種應用定制需求的存儲系統。這也間接使得蘋果的底層基礎設施更安全、更可靠，而最終實現公司和社區雙贏的結果。

拋開蘋果開源FoundationDB背后的商業利益不談，FoundationDB在技術上有兩點值得關注：

• NoSQL+ACID+SQL Layer=NewSQL

在獨立的KV存儲服務上實現事務ACID語義，再通過分層設計在應用層支持文檔、圖、SQL等多種數據模型。

• MVCC+OCC=SSI

基于多版本/樂觀并發控制技術實現可串行化的快照隔離級別。

一、NoSQL的沒落?

提起NoSQL，大家一定會想到Google的Bigtable(2008年)和Amazon的Dynamo(2007年)，前者出于互聯網企業數據量爆發的擴展性需求，實現了一個CP系統;而后者則出于商業用戶的寫高可用需求，實現了一個AP系統。

1、Bigtable & Dynamo

在CAP定理(2000年)的推波助瀾下，NoSQL運動發展的如火如荼(AP系統如Cassandra、Voldemort、Tokyo Cabinet、Riak，CP系統如HBase、Hypertable、MongoDB、Redis)，并總結出了自己的設計哲學：

• no SQL
• no ACID
• no schema
• high performance
• high scalability
• high availability
• low latency
• relaxed consistency

然而，隨著NoSQL系統在應用中的廣泛使用，系統設計中拋棄的技術債務成了應用開發人員的負擔，開發接口千奇百怪，數據不一致問題狀況百出，事務一致性無法保證，正如Eric Brewer所說：

The hidden cost of forfeiting consistency, which is the need to know the system's invariants. The subtle beauty of a consistent system is that the invariants tend to hold even when the designer does not know what they are.

尤其是在互聯網業內具備神級存在的Google公開的Spanner(2012)，成為壓垮NoSQL的最后一根稻草，又一次改變了分布式數據庫系統發展的方向。

2、Google從NoSQL轉向NewSQL的歷程

Google內部的存儲系統，在自身業務需求的推動下，經歷了幾代系統的演變，Bigtable、Percolator、Megastore、NoSQL Spanner、F1、SQL Spanner，本質上是一個NoSQL到NoSQL+APP ACID到NoSQL+ACID到NoSQL with ACID到NoSQL with ACID+SQL到SQL的過程。

Percolator(2010，NoSQL+APP ACID)

該系統實現為一個基于Bigtable的業務系統，用于搜索索引的構建，作者在論文中指出了Bigtable對應用需求的限制：

Distributed storage systems like Bigtable can scale to the size of our repository but don't provide tools to help programmers maintain data invariants in the face of concurrent updates.

同時也描述了支持事務語義的好處：

...make it more tractable for the user to reason about the state of the system and to avoid the introduction of errors into a long-lived repository.

Percolator通過2PL技術實現了多行ACID事務：

...stores its locks in special in-memory columns in the same Bigtable that stores data and reads or modifies the locks in a Bigtable row transaction when accessing data in that row...

Megastore(2011，NoSQL+ACID)

該系統用于內部交互式在線NoSQL系統，作者在論文中也指出了實現事務語義的好處：

Despite the operational advantages of eventually consistent systems,it is currently too difficult to give up the read-modify-write idiom in rapid application development.

Megastore通過OCC技術實現了單分區上的ACID事務，但論文中并沒有詳細描述實現細節。

Spanner(2012，NoSQL with ACID)

該系統是第一個不依賴Bigtable，從頭打造的分布式數據庫系統，作者在論文中也強調了支持事務語義的好處：

...it is better to have application programmers deal with performance problems due to overuse of transactions as bottlenecks arise, rather than always coding around the lack of transactions.

Spanner通過2PL技術實現了跨分區的多行ACID事務。

F1(2012，NoSQL with ACID + SQL)

該系統基于NoSQL Spanner實現為AdWords的存儲系統，作者在論文中(同上)從業務視角直接陳述了事務和SQL的缺失對業務開發造成的影響：

...the complexity of dealing with a non-ACID data store in every part of our business logic would be too great, and there was simply no way our business could function without SQL queries.

F1借助Spanner基于樂觀鎖實現了樂觀事務，并詳盡描述了優缺點(無法避免幻讀)，這個和數據庫層面基于OCC技術實現的事務有本質的區別.

Spanner(2017，SQL)

該系統是一個全功能的SQL系統，作者在論文中再次強調了支持事務和SQL的重要性：

...developers of many OLTP applications found it difficult to build these applications without a strong schema system, cross-row transactions, consistent replication and a powerful query language.

如果沒有強表達能力的查詢語言：

...developers had to write complex code to process and aggregate the data in their applications.

與此同時，作者對NoSQL with ACID + SQL的技術架構也寄予了高度的肯定：

A scalable, manageable, transactional key-value store is perhaps the lowest common denominator for building enterprise-strength global storage systems. It has been demonstrated by our colleagues from the F1 team that a transactional NoSQL core can be used to build a scalable SQL DBMS.

并且，在存儲系統中松耦合還是緊耦合實現SQL還是一個需要認真討論的問題：

both the loosely coupled (in case of F1) and tightly coupled SQL designs can be deployed successfully, and even simultaneously, on a transactional NoSQL core. A detailed exploration of the pros and cons of these designs is still outstanding. But it is perhaps fair to say that from the perspective of many engineers working on the Google infrastructure, the SQL vs NoSQL dichotomy may no longer be relevant.

二、NewSQL的繁榮?

根據論文中的定義，NewSQL的核心特性如下：

• 支持SQL接口。
• 支持ACID事務語義。
• 在OLTP場景下具備NoSQL的高性能、高可用、高擴展性。

Spanner和F1論文發表至今，催生了一些優秀的NewSQL開源項目：

• 2015年6月4日，前Google員工創辦CockroachDB;2015年融資600萬美元;2016年融資2000萬美元;2017年融資2700萬美元。
• 2015年中，前豌豆莢員工發布TiDB;2017年融資1500萬美元。
• 2015年5月24日，HP開源Trafodion，一款基于HBase，支持ACID事務、SI隔離級別的SQL數據庫;2018年1月10日，Apache宣布Trafodion成為頂級項目。
• 2017年11月2日，前Facebook員工創辦YugaByte DB;2017年融資800萬美元;2018年融資1600萬美元。

從這些項目的實現架構來看，主要分為兩種：

• 原生實現：如CockroachDB、YugaByteDB
• NoSQL+ACID+SQL：如TiDB、Trafodion

VoltDB在評價FoundationDB的博文中對NoSQL+ACID+SQL架構下SQL實現的性能表示了質疑，這種架構的主要技術缺陷是計算無法下沉到存儲節點會導致大量的網絡傳輸開銷。

然而，2017年Google的Spanner論文中已經將類似這種架構的F1與SQL Spanner相提并論，兩種架構的優劣性仍然有待觀察和研究，但它們的共同點是都依賴于一個支持事務的NoSQL基礎系統。從這個視角來看，以下這些支持事務的NoSQL系統也具備演變成NewSQL的可能性：

• 2009年，FoundationDB開源，基于MVCC NoSQL，支持SSI隔離級別;2015年閉源;2018年4月開源。
• 2016年3月28日，Yahoo開源Omid，基于HBase，支持SI隔離級別;后續閉源，商業化為LeanXscale，同時支持SQL。
• 2016年3月7日，Tephra開源，基于HBase，支持SI隔離級別;由Cask公司商業化運作。
• 2018年2月15日，MongoDB宣布將在今年夏季發布的4.0版本中支持多文檔ACID事務，基于WiredTiger存儲引擎改造。

三、事務的心臟——并發控制

從上述章節NewSQL的發展趨勢來看，ACID事務的回歸是必然的，而且在分布式場景下，均致力于實現可擴展、高性能的串行化隔離級別，這在傳統數據庫的實現中是難以達到的。事務管理的核心技術是并發控制，原子性、一致性、隔離性都與它相關，本章簡單科普一下事務并發控制技術。

事務的并發控制是為了實現事務的調度。

一個正確、高效的事務調度應滿足如下屬性：

• 可串行化：多個并發事務的調度S與一個串行化的調度產生相同的結果，則稱這個調度S是可串行化的;在數據庫實現中，一般使用沖突可串行化技術。
• 可恢復性：已經提交的事務沒有讀過被終止的事務寫過的數據，防止臟讀異常。
• 避免級聯終止：避免由于事務T1的終止而導致事務T2的終止。
• 嚴格性：先發生寫操作的事務的提交或終止應先于其它沖突事務的提交或終止。

并發控制從實現思路維度可以分為如下三類：

• 樂觀：重在事后檢測，在事務提交時檢查是否滿足隔離級別。滿足，則提交;否則回滾并自動重新執行。
• 悲觀：重在事前預防，在事務執行時檢查是否滿足隔離級別。滿足，則繼續執行;否則等待或回滾。
• 半樂觀：混合使用樂觀和悲觀技術實現事務并發控制。

并發控制從實現方式維度可以分為如下幾種：

• 基于鎖的并發控制

2PL(two-phase locking)：事務在執行期間被明確的劃分為growing和shrinking階段，growing階段只能持有鎖不能釋放鎖;shrinking階段只能釋放鎖不能持有鎖，僅滿足可恢復性;

S2PL(strict two-phase locking)：在滿足2PL的前提下，要求持有的排它鎖必須在事務提交后才釋放，避免了級聯回滾;

SS2PL(strong strict two-phase locking)：在滿足2PL的前提下，要求事務提交之前不得釋放任何鎖，保證了嚴格性。

• 基于時間戳的并發控制

在事務開始時生成一個單調遞增的時間戳，數據項上維護最近讀時間戳和最近寫時間戳。每次讀寫操作，系統都會將事務時間戳與數據項上的時間戳進行檢查，對于任意讀寫操作，如果事務時間戳小于數據項的最近寫時間戳，則將事務回滾;對于寫操作，如果事務時間戳小于數據項的最近讀時間戳，則將事務回滾;如果都滿足，則繼續訪問下一個數據項。

• 基于OCC的并發控制

事務的生命周期被劃分為三個階段，將串行化檢測推遲到提交階段：

讀階段：事務寫操作僅是對事務私有空間中數據的更新，并不對數據庫中的數據項進行真實的更新，保證讀階段沒有任何事務沖突及鎖開銷;

驗證階段：檢測事務是否滿足串行化隔離級別;

寫階段：將事務私有空間中的更新數據寫入數據庫。

• 基于多版本的并發控制

每一次寫操作會生成一個新的數據項版本，數據項的版本號可以使用事務的時間戳或事務號;系統維護多個數據版本，讀操作根據所在事務的時間戳或事務號能夠讀到指定的版本，做到讀-寫或寫-讀操作不阻塞，寫-寫操作的沖突依賴2PL實現。

上述只是傳統數據庫時代總結的并發控制技術，在分布式場景下一般會采用MVCC與其它并發控制技術的組合，目的是提高并發度，減小同步開銷。

四、悲觀還是樂觀

在了解了數據庫的基本并發控制技術后，本章針對現今感興趣的生產級NewSQL分布式數據庫使用的并發控制技術進行了簡單的總結：

由上表可以看出，FoundationDB是第一個使用OCC技術實現ACID事務的生產級數據庫系統(嚴格地說，Google的MegaStore也使用了OCC并用于Google APP Engine等業務，但它的ACID事務實現僅作用于單個分區)。

當然，FoundationDB的OCC實現也有一些限制，比如官方文檔對KV和事務的大小及時長做出了如下限制：

• key不超過10K;value不超過100K;事務不超過10M(包括所有讀、寫涉及的KV);
• 僅支持運行時間不超過5s的讀寫事務。

這些限制在OLTP場景下是完全可以接受的，若要在其Layer機制上實現OLAP場景，需要做適配性改造。

不管怎樣，FoundationDB通過OCC技術實現了NoSQL+ACID，并經過了蘋果企業級生產環境的檢驗，NewSQL的設計者到底是該使用悲觀還是樂觀并發控制技術，現在看來是一個需要認真考慮的問題了。

以上就是對當前NewSQL的發展趨勢及使用到的相關并發控制技術的一些思考。

參考

1、An Evaluation of Distributed Concurrency Control

2、Concurrency Control in Distributed Database Systems

3、What’s Really New with NewSQL?

4、CAP Twelve Years Later： How the 'Rules' Have Change

5、foundationdbs-lesson-fast-key-value-store-not-enough