XSQL發展

資料庫和作業系統是計算機基礎理論的核心產品，縱觀整個IT行業，無論是傳統的系統軟體還是通用的應用系統離不開這2款系統軟體。隨著業務系統的多樣性，OS和DB也在不斷的演進。對比OS， DB的演進更是處於百花齊放狀態，唯一目標就是在特定的場景中能更好的滿足業務的需求。

SQL

傳統的關係型資料庫有著悠久的歷史，從上世紀60年代開始就已經在航空領域發揮作用。因為事務性、強一致和通用的關係型數據模型接口，獲得了越來越多的應用，大有一統天下的氣勢。這期間，湧現出了一批佼佼者，其中有優秀的商業化資料庫如Oracle，DB2，SQL Server等，也有我們耳熟能詳的開源資料庫MySQL及PostgreSQL。這裡不嚴謹的將這類傳統資料庫統稱為SQL資料庫。

SQL to NoSQL

隨著網際網路應用的出現，在很多場景下業務並不需要傳統關係型資料庫提供的強一致性以及關係型數據模型。相反，由於快速膨脹和變化的業務場景，對可擴展性(Scalability)以及可靠性(Reliable)更加需要，而這個又正是傳統關係型資料庫的弱點。自然地，新的適合這種業務特點的資料庫NoSQL開始出現，其中最句代表性的是Amazon的Dynamo以及Google的BigTable，以及他們對應的開源版本像Cassandra以及HBase。

由於業務模型的千變萬化，以及拋棄了強一致和關係型，大大降低了技術難度，各種NoSQL版本像雨後春筍一樣湧現，基本成規模的網際網路公司都會有自己的NoSQL實現。主要可以從兩個維度來對各種NoSQL做區分：

1. 按元信息管理方式劃分：以Dynamo[1]為代表的對等節點的策略，由於沒有中心節點的束縛有更高的可用性。而採用有中心節點的策略的，以BigTable[2]為代表的的資料庫，則由於減少全網的信息交互而獲得更好的可擴展性。
2. 按數據模型劃分：針對不同業務模型出現的不同數據模型的資料庫，比較知名的有文檔型資料庫MongoDB，KV資料庫Redis、FoundationDB[3]和Pika等，列資料庫Cassandra、HBase，圖資料庫Neo4J。

NoSQL to New SQL

NoSQL也有很明顯的問題，由於缺乏強一致性及事務支持，很多業務場景被NoSQL拒之門外。同時，缺乏統一的高級數據模型、訪問接口，又讓業務代碼承擔了很多的負擔。圖靈獎得主Michael Stonebraker甚至專門發文聲討，」Why Enterprises Are ­Uninterested in NoSQL」 [3] 一文中，列出了NoSQL的三大罪狀：No ACID Equals No Interest， A Low-Level Query Language is Death，NoSQL Means No Standards。資料庫的歷史就這樣經歷了否定之否定，又螺旋上升的過程。

NoSQL 到 NewSQL的支持：數據分片

如何能在獲得SQL的強一致性、事務支持的同時，獲得NoSQL的可擴展性及可靠性。答案顯而易見，就是要在SQL的基礎上像NoSQL一樣做分片。通過分片將數據或計算打散到不同的節點，來擺脫單機硬體對容量和計算能力的限制，從而獲得更高的可用性、性能以及彈性：

我們將資料庫系統劃分為上下兩個部分，Part 1保持不動，將Part 2進行分片打散，由不同的節點負責，並在分片間通過副本方式保證高可用。同時，Part 2部分的功能由於被多個節點分擔，也可以獲得並行執行帶來的性能提升。

所以現在實現NewSQL的核心問題變成了：確定一條分割線將資料庫系統劃分為上下兩個部分，對Part 2做分片打散。而這條分割線的確定就成了主流NewSQL資料庫的不同方向，不同的選擇帶來的不同的ACID實現方式，以及遇到的問題也大不相同。下圖展示了更詳細的資料庫系統內部結構，以及主流的分界線選擇及工業實現代表：

為了方便說明，本文中根據這個分片分割線的位置，將不同的方案命名為：Partition All、Partition Engine、Partiton Storage 以及 Partition Disk。這裡先說結論：隨著分片層次的下降，可擴展性會降低，但易用性和生態兼容性會增大。下面就分別介紹每種選擇中需要解決的問題，優缺點，使用場景以及代表性工業實現的實現方式。

PARTITION ALL：分庫分表

最直觀的想法，就是直接用多個DB實例共同服務，從而緩解單機資料庫的限制，這也是很多大公司內部在業務擴張期的第一選擇。這種方式相當於是在資料庫系統的最頂層就做了Partition，理想情況下，整個資料庫的各個模塊可以全部並發執行起來。

採用分庫分表的首要問題就是如何對數據進行分片，常見的就是在表或者庫的維度水平或垂直地進行分片。這裡分片的選擇是非常關鍵的，良好的，適應業務模式的分片可以讓多DB實例儘量的並發起來獲得最好的擴展性能。而不合適的分片則可能導致大量的跨節點訪問，導致負載不均衡，或引入訪問瓶頸。除分片策略之外，由於跨節點的訪問需要，會有一些通用的問題需要解決，比如如何在分片之間支持分布式事務，處理分布式Query拆分和結果合併，以及全局自增ID的生成等。而且，最重要的，所有這些新增的負擔全部要業務層來承擔，極大地增加了業務的成本。

因此，分庫分表的模式，在良好的業務側設計下可以獲得極佳的擴展性，取得高性能、大容量的資料庫服務。但業務耦合大，通用性差，需要用戶自己處理分片策略、分布式事務、分布式Query。這也是為什麼在各大公司內部都有成熟穩定的分庫分表的資料庫實現的情況下，這些實現卻很難對外通用的輸出。

PARTITION ENGINE: Spanner

我們將Part 1和Part2的分界線下移，到Server層之下，也就是只在引擎層做Partition。這種模式由於節點間相對獨立，也被稱作Share Nothing架構。相對於傳統分庫分表，Partition Engine的方式將之前複雜的分布式事務，分布式Query等處理放到了資料庫內部來處理。

本文就以分布式事務為例，來嘗試解釋這種分片層次所面對的問題和解決思路。要支持事務就需要解決事務的ACID問題。而ACID的問題在分布式的環境下又變得複雜很多：

A（Atomicity），在傳統資料庫系統中，通過REDO加UNDO的方式容易解決這個問題[4]，但當有多個不同的節點參與到同一個事務中的時候問題變的複雜起來，如何能把保證不同節點上的修改同時成功或同時回滾呢，這個問題有成熟的解決方案，就是2PC（Two-Phase Commit Protocol），引入Coordinator角色和prepare階段來在節點間協商。

D （Durability），單機資料庫中，我們通過REDO配合Buffer Pool的刷髒策略可以保證節點重啟後可以看到已經提交的事務[4]。而在分布式環境中通常會需要更高的可用性，節點宕機後馬上需要有新的節點頂上。這裡的解決方案也比較成熟，就是給分片提供多個副本（通常是3個），每個副本由不同的節點負責，並且採用一致性算法Multi-Paxos[6]或其變種來保證副本間的一致性。下圖是Spanner[5]的實現方式，每個spanserver節點負責不同partition的多個分片，每個partition的副本之間用Paxos來保證其一致性，而跨Partition的事務則用2PC來保證原子。

I（Isolation），「資料庫並發控控制」[7]一文中介紹過，是實現並發控制最直觀的做法是2PL（兩階段鎖），之後為了減少讀寫之間的加鎖衝突，大多數資料庫都採取了2PL + MVCC的實現方式，即通過維護多版本信息來讓寫請求和讀請求可以並發執行。

MVCC的實現中有十分依賴一個全局遞增的事務執行序列，用來判斷事務開始的先後，從而尋找正確的可讀歷史版本。而這個全局遞增的序列在分布式的資料庫中變得十分複雜，原因是機器間的時鐘存在誤差，並且這種誤差的範圍不確定。常見的做法是通過節點間的信息交互來確定跨節點的時間先後，如Lamport時鐘[8]。但更多的信息交互帶來了瓶頸，從而限制了集群的擴展規模以及跨地域的複製。Spanner[5]提出了一種新的思路，通過引入GPS和原子鐘的校準，在全球範圍內，將不同節點的時鐘誤差限制到一個確定的範圍內。這個確定的誤差範圍非常重要，因為他支持了一種可能：通過適度的等待保證事務的正確性。

具體的說，這裡Spanner需要保證External Consistency，即如果事務T2開始在T1 Commit之後， 那麼T2拿到的Commit Timestamp一定要大於T1的Timestamp。Spanner實現這個保證的做法，是讓事務等待其拿到的Commit Timestamp真正過去後才真正提交(Commit Wait)：

如上圖[9]所示，事務Commit時，首先通過TrueTime API獲取一個當前時間now，這個時間是一個範圍now = [t - ε， t + ε]，那麼這個t - ε就是作為這個事務的Commit Timestamp，之後要一直等待到TrueTime API返回的當前時間now.earliest > s時，才可以安全地開始做真正的comimt，這也就保證，這個事務commit以後，其他事務再也不會拿到更小的Timestamp。

總結下， 採用Partition Engine策略的NewSQL，向用戶屏蔽了分布式事務等細節，提供統一的資料庫服務，簡化了用戶使用。Spanner，CockroachDB，Oceanbase，TIDB都屬於這種類型。這裡有個值得探討的問題：由於大多數分庫分表的實現也會通過中間件的引入來屏蔽分布式事務等實現細節，同樣採用類Multi Paxos這樣的一致性協議來保證副本一致，同樣對用戶提供統一的資料庫訪問，那麼相較而言，Partition Engine的策略優勢又有多大呢？在大企業，銀行等場景下， 這兩種方案或許正在正面競爭，我們拭目以待[11]。

PARTITION STORAGE: AURORA、POLARDB

繼續將分片的分界線下移，到事務及索引系統的下層。這個時候由於Part 1部分保留了完整的事務系統，已經不是無狀態的，通常會保留單獨的節點來處理服務。這樣Part 1主要保留了計算相關邏輯，而Part 2負責了存儲相關的像REDO，刷髒以及故障恢復。因此這種結構也就是我們常說的計算存儲分離架構，也被稱為Share Storage架構。

這種策略由於關鍵的事務系統並沒有做分片處理，也避免了分布式事務的需要。而更多的精力放在了存儲層的數據交互及高效的實現。這個方向最早的工業實現是Amazon的Aurora[12]。Aurora的計算節點層保留了鎖，事務管理，死鎖檢測等影響請求能否執行成功的模塊，對存儲節點來說只需要執行持久化操作而不需要Vote。另外，計算節點還維護了全局遞增的日誌序列號LSN，通過跟存儲節點的交互可以知道當前日誌在所有分片上完成持久化的LSN位置，來進行實物提交或緩存淘汰的決策。因此，Aurora可以避免Partition Engine架構中面臨的分布式事務的問題[18]。

Auraro認為計算節點與存儲節點之間，存儲節點的分片副本之間的網絡交互會成為整個系統的瓶頸。而這些數據交互中的大量Page信息本身是可以通過REDO信息構建的，也就是說有大量的網絡交互是冗餘的，因此Aurora提出了「Log is Database」，也就是所有的節點間網絡交互全部只傳輸REDO，每個節點本地自己在通過REDO的重放來構建需要的Page信息。

從上圖可以看出，計算節點和存儲節點之間傳輸的只有REDO，也就是是說，傳統資料庫中存儲相關的部分從計算節點移到了存儲節點中，這些功能包括：

• REDO日誌的持久化
• 髒頁的生成與持久化
• Recovery過程的REDO重放
• 快照及備份

這些功能對資料庫整體的性能有非常大的影響：首先，根據ARIES[17]安全性要求，只有當REDO落盤後事務才能提交，這使得REDO的寫速度很容易成為性能瓶頸；其次，當Buffer Pool接近滿時，如果不能及時對Page做刷髒，後續的請求就會由於獲取不到內存而變慢；最後，節點發生故障重啟時，在完成REDO重放之前是無法對外提供服務的，因此這個時間會直接影響資料庫的可用性。而在Aurora中，由於存儲節點中對數據頁做了分片打散，這些功能可以由不同的節點負責，得以並發執行，充分利用多節點的資源獲得更大的容量，更好的性能。

PolarDB

2017年，由於RDMA的出現及普及，大大加快了網絡間的網絡傳輸速率，PolarDB[15]認為未來網絡的速度會接近總線速度，也就是瓶頸不再是網絡，而是軟體棧。因此PolarDB採用新硬體結合Bypass Kernel的方式來實現高效的共享盤實現，進而支撐高效的資料庫服務。由於PolarDB的分片層次更低，也就能做到更好的生態兼容，也就是為什麼PolarDB能夠很快的做到社區版本的全覆蓋。副本間PoalrDB採用了ParalleRaft來允許一定範圍內的亂序確認，亂序Commit以及亂序Apply。

採用Partition Storage的策略的NewSQL，由於保持了完整的計算層，所以相對於傳統資料庫需要用戶感知的變化非常少，能過做到更大程度的生態兼容。同時也因為只有存儲層做了分片和打散，可擴展性不如上面提到的兩種方案。在計算存儲分離的基礎上，Microsoft的Socrates[13]提出了進一步將Log模塊拆分，實現Durability和Available的分離；Oracal的Cache Fusion[14]通過增加計算節點間共享的Memory來獲得多點寫及快速Recovery，總體來講他們都屬於Partition Storage這個範疇。

對比

可以看出，如果我們以可擴展性為橫坐標，易用及兼容生態作為縱坐標，可以得到如上圖所示的坐標軸，越往右上角當然約理想，但現實是二者很難兼得，需要作出一定的取捨。

首先來看傳統的單節資料庫其實就是不易擴展的極端，同時由於他自己就是生態所以兼容生態方面滿分。另一個極端就是傳統的分庫分表實現，良好的分片設計下這種策略能一定程度下獲得接近線性的擴展性。但需要做業務改造，並且需要外部處理分布式事務，分布式Query這種棘手的問題。之後以Spanner為代表的的Partition Engine類型的NewSQL由於較高的分片層次，可以獲得接近傳統分庫分表的擴展性，因此容易在TPCC這樣的場景下取得好成績，但其需要做業務改造也是一個大的限制。以Aurora及PolarDB為代表的的Partition Storage的NewSQL則更傾向於良好的生態兼容，幾乎為零的業務改造，來交換了一定程度的可擴展性。

使用場景上來看，大企業，銀行等對用戶對擴展性要求較高，可以接受業務改造的情況下，類Spanner的NewSQL及傳統分庫分表的實現正在正面競爭。而Aurora和PolarDB則在雲資料庫的場景下一統江湖。

參考

• [1] DeCandia, Giuseppe, et al. 「Dynamo: amazon’s highly available key-value store.」 ACM SIGOPS operating systems review 41.6 (2007): 205-220.
• [2] Chang, Fay, et al. 「Bigtable: A distributed storage system for structured data.」 ACM transactions on Computer Systems (TOCS) 26.2 (2008): 1-26.
• [3] Jingyu Zhou, Alex Miller, et al. 「FoundationDB: A Distributed Unbundled Transactional KeyValue Store.」 ACM ISBN 978-1-4503-8343-1/21/06
• [4] 資料庫故障恢復機制的前世今生：https://zhuanlan.zhihu.com/p/20868175
• [5] James C. Corbett, et al. 「Spanner: Google’s Globally-Distributed Database.」 Published in the Proceedings of OSDI 2012
• [6] Chandra, Tushar D., Robert Griesemer, and Joshua Redstone. 「Paxos made live: an engineering perspective.」 Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing. 2007.
• [7] 淺析資料庫並發控制。https://zhuanlan.zhihu.com/p/45339550
• [8] Lamport, Leslie. 「Time, clocks, and the ordering of events in a distributed system.」 Concurrency: the Works of Leslie Lamport. 2019. 179-196.
• [9] Spanner的分布式事務實現。https://zhuanlan.zhihu.com/p/20868175
• [10] Pavlo, Andrew, and Matthew Aslett. 「What’s really new with NewSQL?.」 ACM Sigmod Record 45.2 (2016): 45-55.
• [11] 分庫分表 or NewSQL資料庫? https://dbaplus.cn/news-159-2690-1.html
• [12] Verbitski, Alexandre, et al. 「Amazon aurora: Design considerations for high throughput cloud-native relational databases.」 Proceedings of the 2017 ACM International Conference on Management of Data. 2017.
• [13] Antonopoulos, Panagiotis, et al. 「Socrates: the new SQL server in the cloud.」 Proceedings of the 2019 International Conference on Management of Data. 2019.
• [14] Lahiri, Tirthankar, et al. 「Cache fusion: Extending shared-disk clusters with shared caches.」 VLDB. Vol. 1. 2001.
• [15] Cao, Wei, et al. 「PolarFS: an ultra-low latency and failure resilient distributed file system for shared storage cloud database.」 Proceedings of the VLDB Endowment 11.12 (2018): 1849-1862.
• [16] Depoutovitch, Alex, et al. 「Taurus Database: How to be Fast, Available, and Frugal in the Cloud.」 Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. 2020.
• [17] Mohan, Chandrasekaran, et al. 「ARIES: a transaction recovery method supporting fine-granularity locking and partial rollbacks using write-ahead logging.」 ACM Transactions on Database Systems (TODS) 17.1 (1992): 94-162.
• [18] Amazon Aurora: On Avoiding Distributed Consensus for I/Os, Commits, and Membership Changes