王磊（Ivan），現任光大銀行科技部數據領域架構師，曾任職於IBM全球諮詢服務部從事技術諮詢工作，具有十餘年數據領域研發及諮詢經驗。目前負責全行數據領域系統的日常架構設計、評審及內部研發等工作，對分佈式數據庫、Hadoop等基礎架構研究有濃厚興趣。個人公眾號：金融數士。
在上一篇文章《從架構特點到功能缺陷，重新認識分析型分佈式數據庫》中，我們完成了對不同“分佈式數據庫”的橫向分析，本文我將講述拆解的第二部分，會結合NoSQL與NewSQL的差異，從縱向來談談OLTP場景“分佈式數據庫”實現方案的關鍵技術要點。這樣的思考是前文的延伸，也是分佈式數據庫專題文章的一個總綱，其中的要點我之後也會單獨撰文闡述。
一、NewSQL & NoSQL
NewSQL是本專題關注的重點，也是前文中特指的“分佈式數據庫”，其適用於OLTP場景，具有高併發低延遲的特點，特性接近Oracle/DB2等傳統數據庫，依賴通用X86服務器實現性能上的水平拓展，能夠扛住海量交易的性能壓力。
目前具有較高知名度的NewSQL有Google的Spanner / F1、阿里的OceanBase、CockroachDB、TiDB。其中後兩者是正在成長中的開源項目，2018年相繼發佈了2.0版本。
NewSQL與NoSQL有很深的淵源，所以下文在對NewSQL的介紹中會穿插一些NoSQL對應的實現技術方式。
1 存儲引擎
B+ Tree
B+樹是關係型數據庫常用的索引存儲模型，能夠支持高效的範圍掃描，葉節點相關鏈接並且按主鍵有序，掃描時避免了耗時的遍歷樹操作。B+樹的侷限在於不適合大量隨機寫場景，會出現“寫放大”和“存儲碎片”。
以下借用姜承堯老師書中的例子[1]來說明B+樹的操作過程↓
存在高度為2的B+樹，存儲在5個頁表中，每頁可存放4條記錄，扇出為5。下圖展示了該B+ Tree的構造，其中略去了葉子節點指向數據的指針以及葉子節點之間的順序指針：
B+樹由內節點（InterNode）和葉節點（LeafNode）兩類節點構成，後者攜帶指向數據的指針，而前者僅包含索引信息。
當插入一個索引值為70的記錄，由於對應頁表的記錄已滿，需要對B+樹重新排列，變更其父節點所在頁表的記錄，並調整相鄰頁表的記錄。完成重新分佈後的效果如下：
變更過程中存在兩個問題：
寫放大
本例中，邏輯上僅需要一條寫入記錄（黃色標註），實際變動了3個頁表中的7條索引記錄，額外的6條記錄（綠色標註）是為了維護B+樹結構產生的寫放大。
注：寫放大（Write Amplification）：Write amplification is the amount of data written to storage compared to the amount of data that the application wrote，也就是說實際寫入磁盤的數據大小和應用程序要求寫入數據大小之比
存儲不連續
新增葉節點會加入到原有葉節點構成的有序鏈表中，整體在邏輯上是連續的；但磁盤存儲上，新增頁表申請的存儲空間與原有頁表很可能是不相鄰的。這樣，在後續包含新增葉節點的查詢中，將會出現多段連續讀取，磁盤尋址的時間將會增加。進一步來說，在B+Tree上進行大量隨機寫會造成存儲的碎片化。
在實際應用B+Tree的數據庫產品（如MySQL）中，通常提供了填充因子（Factor Fill）進行針對性的優化。填充因子設置過小會造成頁表數量膨脹，增大對磁盤的掃描範圍，降低查詢性能；設置過大則會在數據插入時出現寫擴大，產生大量的分頁，降低插入性能，同時由於數據存儲不連續，也降低了查詢性能。
LSM-Tree
LSM-Tree（Log Structured-Merge Tree）由Patrick O'Neil首先提出，其在論文[2]中系統闡述了與B+樹的差異。而後Google在Bigtable中引入了該模型，如下圖所示：
LSM-Tree的主要思想是藉助內存將隨機寫轉換為順序寫，提升了寫入性能；同時由於大幅度降低了寫操作對磁盤的佔用，使讀操作獲得更多的磁盤控制權，讀操作性能也並未受到過多的影響。
寫操作簡化過程如下：
當寫入請求到達時，首先寫入內存中Memtable，處理增量數據變化，同時記錄WAL預寫日誌；
內存增量數據達到一定閾值後，當前Memtable會被凍結，並創建一個新的Memtable，已凍結的Memtable中的數據會被順序寫入磁盤，形成有序文件SSTable（Sorted String Table），這個操作被稱為Minor Compaction（在HBase中該操作稱為Flush操作，而Minor Compaction有其他含義）；
這些SSTable滿足一定的規則後進行合併，即Major Compaction。每個Column Family下的所有SSTable被合併為一個大的SSTable。
該模型規避了隨機寫的IO效率問題，有效緩解了B樹索引的寫放大問題，極大的提升了寫入效率。
NoSQL廣泛使用了LSM-Tree模型，包括HBase、Cassandra、LevelDB、RocksDB等K/V存儲。
當然LSM-Tree也存在自身的缺陷：
首先，其Major Compaction的操作非常重影響聯機讀寫，同時也會產生寫放大。因為這個原因，HBase的使用中通常會禁止系統自動執行Major Compaction。
註釋：
Major Compaction操作的意義是降低讀操作的時間複雜度。設系統包含多個SSTable文件，共有N數據，SSTable平均包含m數據。
執行讀操作時，對單一SSTable文件採用折半查找方法的時間複雜度為O(log2m)，則整體時間複雜度為O(N/m* log2m)；合併為一個SSTable後，時間複雜度可降低到O(log2N)
-
其次是對讀效率的影響，因為SSTable文件均處於同一層次，根據批量寫的執行時序形成若干文件，所以不同文件中的Key（記錄主鍵）會出現交叉重疊，這樣在執行讀操作時每個文件都要查找，產生非必要的I/O開銷。
最後是空間上的放大（Space Amplification），最壞情況下LSM Tree需要與數據大小等同的自由空間以完成Compact動作，即空間放大了100%，而B+樹的空間放大約為1/3。
Leveled LSM Tree
Leveled LSM Tree 的變化在於將SSTable做了進一步的分層，降低寫放大的情況，縮小了讀取的文件範圍，在LevelDB 中率先使用，隨後Cassandra 1.0也引入了該策略[3]。
SSTable的層次化設計策略是：
單個SSTable文件大小是固定的，在Cassandra中默認設置為5M；
層級從Level 0開始遞增，存儲數據量隨著層級的提升而增長，層級之間有一致的增長係數（Growth Factor）。Cassandra中Growth Factor設置為10，Level 1文件為1-10M則Level 2 文件為10-100M，這樣10TB數據量會達到Level 7；
Level 0的SSTable比較特殊，固定為4個文件，且文件之間存在Key交叉重疊的情況，從Level 1開始，SSTable不再出現Key交叉情況；
Level 0層的SSTable超過容量大小時，向Level 1 Compaction，因為存在Key交叉，所以要讀取Level 0的所有SSTable；當Level 1 的文件大小超過閾值時，將創建Level 2的SSTable並刪除掉Level 1原有的SSTable；當Level 1的Key範圍對應Level 2的多個SSTable時，要重寫多個SSTable，但由於SSTable的大小固定，所以通常只會涉及少數的SSTable。
Level間Compact操作
多個有序的SSTable，避免了Major Compaction這樣的重量級文件重寫，每次僅更新部分內容，降低了寫放大率。
對於讀取元數據來鎖定相關的SSTable，效率顯然超過了對所有SSTable的折半查找和Bloom Filter。因此，讀取效率得到了顯著提升，按照某種評估方式[3]，在每行數據大小基本相同的情況下，90%的讀操作僅會訪問一個SSTable。
該策略下，Compaction的操作更加頻繁，帶來了更多I/O開銷，對寫密集型操作而言，最終結果是否能夠得到足夠的效率提升存在不確定性，需要在應用中權衡。
NewSQL的策略
NewSQL數據庫的存儲層普遍都採用K/V存儲，所以基本沿用了LSM Tree模型。其中CockroachDB和TiDB都在KV層使用RocksDB。OceanBase採用了不同的方法規避Major Compaction的影響，大體是利用閒置的副本（Follower）進行Compaction操作，避免了對讀操作的阻塞，在Compaction完成後，進行副本的角色的替換。
同時，K/V存儲引擎仍然在繼續發展中，一些其他的改進如分形樹(Fractal Tree)等，限於篇幅我們就不在此展開了。
2 分片
分片（Sharding）概念與RDBMS的分區相近，是分佈式數據庫或分佈式存儲系統的最關鍵特性，是實現水平擴展的基礎，也在NoSQL類系統中得到了大量運用。
分片的目標是將數據儘量均勻地分佈在多個節點上，利用多節點的數據存儲及處理能力提升數據庫整體性能。
Range&Hash
雖然不同的系統中對分片策略有很多細分，但大致可以歸納為兩種方式，Range和Hash。
Range分片有利於範圍查詢，而Hash分片更容易做到數據均衡分佈。在實際應用中，Range分片似乎使用得更多，但也有很多應用會混合了兩種分片方式。
HBase採用了Range方式，根據Rowkey的字典序排列，當超過單個Region的上限後分裂為兩個新的Region。Range的優點是數據位置接近，在訪問數據時，範圍查找的成本低；缺點也比較明顯，在容易出現熱點集中的問題。
例如，在HBase通常不建議使用業務流水號作為RowKey，因為連續遞增的順序號在多數時間內都會被分配到同一個RegionServer，造成併發訪問同時競爭這個RegionServer資源的情況。為了避免該問題，會建議將RowKey進行編碼，序號反轉或加鹽等方式。這種方式實質上是使用應用層的設計策略，將Range分片轉換成類似Hash分片的方式。
Spanner的底層存儲沿用了BigTable的很多設計思路，但在分片上有所調整，在Tablet內增加了Directory的動態調配來規避Range分片與操作熱點不匹配的問題，後續在事務管理部分再詳細描述。
靜態分片&動態分片
按照分片的產生策略可以分為靜態分片和動態分片兩類。
靜態分片在系統建設之初已經決定分片的數量，後期再改動代價很大；動態分片是指根據數據的情況指定的分片策略，其變更成本較低，可以按需調整。
傳統的DB + Proxy方案，進行水平分庫分表就是一種常見的靜態分片。我們熟知的幾個互聯網大廠在大規模交易系統中都進行過類似的設計，默認將數據做成某個固定數量的分片，比如100、255、1024，或者其它你喜歡的數字。分片的數量可以根據系統預期目標的整體服務能力、數據量和單節點容量進行評估，當然具體到100片合適還是1024片合適，多少還是有拍腦袋的成分。
在NoSQL中，Redis集群也採用同樣的靜態分片方式，默認為16384個哈希槽位（等同於分片）。
靜態分片的缺點是分片數量已經被確定，基於單點處理能力形成一個容量的上限；靈活性較差，後續再做分片數量調整時，數據遷移困難，實現複雜。優點也很明顯，靜態分片的策略幾乎是固化的，因此對分區鍵、分區策略等元數據管理的依賴度很低，而這些元數據往往會形成分佈式數據庫中的單點，成為提升可靠性、可用性的障礙。
相比之下，動態分片的靈活性更好，適用於更豐富的應用場景，所以NewSQL也主要採用動態分片方式，代價則是對元數據管理的複雜度增加。
在分片處理上，NoSQL與NewSQL面臨的問題非常接近。
3 副本
首先是由於通用設備單機可靠性低，必須要通過多機副本的方式。本文中關注兩個問題：一是副本一致性；二是副本可靠性與副本可用性的差異。
數據副本一致性
多副本必然引入了副本的數據一致性問題。之前已經有大名鼎鼎的CAP理論，相信大家都是耳熟能詳了，但這裡要再囉嗦一句，CAP裡的一致性和事務管理中的一致性不是一回事。我遇到過很多同學有誤解，用CAP為依據來證明分佈式架構不可能做到事務的強一致性，而只能是最終一致性。
事務的一致性是指不同數據實體在同一事務中一起變更，要麼全部成功，要麼全部失敗；而CAP中的一致性是指原子粒度的數據副本如何保證一致性，多副本在邏輯上是同一數據實體。
副本同步大致歸納為以下三種模式：
強同步：即在多個副本都必須完成更新，數據更新才能成功。這種模式的問題是高延時、低可用性，一次操作要等待所有副本的更新，加入了很多網絡通訊開銷，增加了延時。多個副本節點必須都正常運行的情況下，整個系統才是可用的，任何單點的不可用都會造成整個系統的不可用。假設單點的可用性是95%，則三個節點的構成的多副本，其可靠性為95% * 95% * 95% = 85.7%。因此雖然Oracle/MySQL等主流數據庫都提供了強同步方式，但在企業實際生產環境中很少有應用。
半同步：MySQL提供了半同步方式，多個從節點從主節點同步數據，當任意從節點同步成功，則主節點視為成功。這個邏輯模型有效規避了強同步的問題，多節點可用性的影響從“與”變為“或”，保障了整體的可用性。但遺憾的是在技術實現上存在瑕疵，會有退化為異步的問題。
Paxos/Raft：該方式將參與節點劃分為Leader/Follower等角色，主節點向多個備節點寫入數據，當存在一半以上節點寫入成功，即返回客戶端寫入成功。該方式可以規避網絡抖動和備節點服務異常對整體集群造成的影響。其他像Zookeeper的ZAB協議，Kafka的ISR機制，雖然與Paxos/Raft有所區別，但大致是一個方向。
副本可靠性與副本可用性
數據副本僅保證了數據的持久性，即數據不丟失。我們還面臨著副本的可用性問題，即數據是否持續提供服務。以HBASE-10070為例來說明這個問題：
HBase通過分佈式文件系統HDFS實現了數據多副本的存儲，但是在提供服務時，客戶端是連接到RegionServer進而訪問HDFS上的數據。因為一個Region會被唯一的RegionServer管理，所以RegionServer仍然是個單點。
在RegionServer宕機時，需要在一定的間隔後才被HMaster感知，後者再調度起一個新的RegionServer並加載相應的Region，整個過程可能達到幾十秒。在大規模集群中，單點故障是頻繁出現的，每個單點帶來幾十秒的局部服務中斷，大大降低了HBase的可用性。
為了解決這問題，HBase引入從RegionServer節點的概念，在主節點宕機時，從節點持續提供服務。而RegionServer並不是無狀態服務，在內存中存儲數據，又出現了主從RegionServer間的數據同步問題。
HBase實現了數據的可靠性，但仍不能充分實現數據的可用性。CockroachDB和TiDB的思路是實現一個支持Raft的分佈式KV存儲，這樣完全忽略單節點上內存數據和磁盤數據的差異，確保數據的可用性。
4 事務管理
分佈式事務處理由於其複雜性，是NoSQL發展中最先被捨棄的特性。但由於大規模互聯網應用廣泛出現，其現實意義逐漸突出，又重新成為NewSQL無法規避的問題。隨著NewSQL對事務處理的完善，也讓過去十餘年數據庫技術的演進終於實現了一個接近完整的上升螺旋。
鑑於分佈式事務管理的複雜性，我在本文中僅作簡要說明，後續文章中會進一步展開。
NewSQL事務管理從控制手段上分為鎖（Lock-Base）和無鎖（Lock-Free）兩種，其中，無鎖模式通常是基於時間戳協調事務的衝突。從資源佔用方式上，分為樂觀協議和悲觀協議，兩者區別在於對資源衝突的預期不同：悲觀協議認為衝突是頻繁的，所以會盡早搶佔資源，保證事務的順利完成；樂觀協議認為衝突是偶發的，只在可以容忍的最晚時間才會搶佔資源。
以下通過最經典的“兩階段提交協議”和具體的兩種應用實踐，來具體闡述實現方式：
兩階段提交協議（2PC）
兩階段提交協議（Tow phase commit protocol，2PC）是經典的分佈式事務處理模型，處理過程分為兩個階段：
請求階段：
事務詢問。協調者向所有參與者發送事務內容，詢問是否可以執行事務提交操作，並開始等待各參與者的相應；
執行事務。各參與者節點執行事務操作，並將Undo和Redo信息記入事務日誌中；
各參與者向協調者反饋事務詢問的響應。如果參與者成功執行了事務操作，那麼就反饋給協調者Yes，表示事務可以執行；如果參與者沒有成功執行事務，那麼就反饋給No，表示事務不可以執行。
提交階段：
提交事務。發送提交請求。協調者向所有參與者節點發出Commit請求；
事務提交。參與者接到Commit後，會正式執行事務提交操作，並在完成提交之後釋放在整個事務執行期間佔有的事務資源；
反饋事務提交結果。參與者在完成事務提交後，向協調者發送Ack消息；
完成事務。協調者收到所有參與者反饋的Ack消息後，完成事務；
中斷事務。發送回滾請求。協調者向所有參與者發出Rollback請求；
事務回滾。參與者接收到Rollback請求後，會利用其階段一記錄的Undo信息來執行事務回滾操作，並在完成回滾之後釋放在整個事務執行期間佔有的事務資源；
反饋事務回滾結果。參與者在完成事務回滾後，向協調者發送Ack消息；
中斷事務。協調者接收到所有參與者反饋的Ack消息後，完成事務中斷。
該模型的主要優點是原理簡單，實現方便。
缺點也很明顯，首先是同步阻塞，整個事務過程中所有參與者都被鎖定，必然大幅度影響併發性能；其次是單點問題，協調者是一個單點，如果在第二階段宕機，參與者將一直鎖定。
Spanner
根據Spanner論文[4]的介紹，其分佈式事務管理仍採用了2PC的方式，但創新性的設計是改變了Tablet的數據分佈策略，Tablet不再是單一的連續Key數據結構，新增了Directory作為最小可調度的數據組織單元。
通過動態的調配，降低事務內數據跨節點分佈的概率。
我將這種事務處理的設計思想理解為：“最好的分佈式事務處理方式，就是不做分佈式事務處理，將其變為本地事務”。在OceanBase的早期版本中也採用了一個獨立的服務器UpdateServer來集中處理事務操作，理念有相近之處。
Percolator
Percolator[5]是Google開發的增量處理網頁索引系統，在其誕生前，Google採用MapReduce進行全量的網頁索引處理。這樣一次處理的時間取決於存量網頁的數量，耗時很長；而且即使某天只有少量的網頁變更，同樣要執行全量的索引處理，浪費了大量的資源與時間。採用Percolator的增量處理方式後，大幅度減少了處理時間。
在這篇論文中給出了一個分佈式事務模型，是“兩階段提交協議”的變形，其將第二階段的工作簡化到極致，大幅提升了處理效率。
具體實現上，Percolator是基於BigTable實現分佈式事務管理，通過MVCC和鎖的兩種機制結合，事務內所有要操作的記錄均為新增版本而不更新現有版本。這樣做的好處是在整個事務中不會阻塞讀操作。
事務中的鎖分為主（Primary）和從鎖（Secondary），對事務內首先操作的記錄對加主鎖，而後對事務內的其他記錄隨著操作過程逐步加從鎖並指向主鎖記錄，一旦遇到鎖衝突，優先級低的事務釋放鎖，事務回滾；
事務內的記錄全部更新完畢後，事務進入第二階段，此時只需要更新主鎖的狀態，事務即可結束；
從鎖的狀態則依賴異步進程和相關的讀操作來協助完成，由於從鎖記錄上保留了指向主鎖記錄的指針，異步進程和讀操作都很容易判斷從鎖的正確狀態，並進行更新。
分佈式事務管理的其他內容，包括無鎖事務控制、全局時鐘的必要性等等，待後續文章中再討論。
二、結語
本文及其前文最初的立意是面向幾類典型技術背景的同學，對“分佈式數據庫”展開不同方向的解讀，並就其中部分技術要點進行闡述，使不同技術領域的同學能夠對相關技術有些許瞭解，為有興趣深入研究的同學做一個鋪墊。
隨著分析的深入愈發覺得文章框架過於龐大難於駕馭，因而對關鍵技術的解讀也存在深淺不一的情況。對於本文中未及展開的部分，我會盡力在後續系列文章中予以補充，水平所限文中必有錯漏之處，歡迎大家討論和指正。
更多金融科技專題分享可參與今年7月6日的DAMS中國數據資產管理峰會。
文獻參考：
[1] 姜承堯, MySQL技術內幕：InnoDB存儲引擎機, 械工業出版社, 2011
[2] Patrick O'Neil The Log-Structured Merge-Tree
[3] Leveled Compaction in Apache Cassandra
https://www.datastax.com/dev/blog/leveled-compaction-in-apache-cassandra
[4] James C. Corbett, Jeffrey Dean, Michael Epstein, et al. Spanner: Google's Globally-Distributed Database
[5] Daniel Peng and Frank Dabek, Large-scale Incremental Processing Using Distributed Transactions and Notifications
閱讀更多 dbaplus社群 的文章
