本文重點談交易型分布式資料庫的關鍵設計點，這裡并不針對具體的産品而是以普适性的結構，結合NoSQL與NewSQL的差異，從縱向來談談OLTP場景“分布式資料庫”實作方案的關鍵技術要點。算是分布式資料庫專題文章的一個總綱，其中的要點Ivan之後也會單獨撰文闡述。
在上一篇文章《從架構特點到功能缺陷，重新認識分析型分布式資料庫》中，我們完成了對不同“分布式資料庫”的橫向分析，本文Ivan将講述拆解的第二部分，會結合NoSQL與NewSQL的差異，從縱向來談談OLTP場景“分布式數 據庫”實作方案的關鍵技術要點。本文既是前文的延伸，同時也算是分布式資料庫專題文章的一個總綱，其中的要點Ivan之後也會單獨撰文闡述。
特别說明：本文是原創文章，首發在DBAplus社群，轉載須獲得作者同意。
一、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裡的一緻性和事務管理中的一 緻性不是一回事。Ivan遇到過很多同學有誤解，用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對事務處理的完善，也讓過去十餘年資料庫技術的演進終于實作了一個接近完整的上升螺旋。
鑒于分布式事務管理的複雜性，Ivan在本文中僅作簡要說明，後續文章中會進一步展開。
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作為最小可排程的資料組織單元。
通過動态的調配，降低事務内資料跨節點分布的機率。
Ivan将這種事務處理的設計思想了解為：“最好的分布式事務處理方式，就是不做分布式事務處理，将其變為本地事務”。在OceanBase的早期版本中也采用了一個獨立的伺服器UpdateServer來集中處理事務操作，理念有相近之處。
Percolator
Percolator[5] 是Google開發的增量處理網頁索引系統，在其誕生前，Google采用MapReduce進行全量的網頁索引處理。這樣一次處理的時間取決于存量網頁 的數量，耗時很長；而且即使某天隻有少量的網頁變更，同樣要執行全量的索引處理，浪費了大量的資源與時間。采用Percolator的增量處理方式後，大 幅度減少了處理時間。
在這篇論文中給出了一個分布式事務模型，是“兩階段送出協定”的變形，其将第二階段的工作簡化到極緻，大幅提升了處理效率。
具體實作上，Percolator是基于BigTable實作分布式事務管理，通過MVCC和鎖的兩種機制結合，事務内所有要操作的記錄均為新增版本而不更新現有版本。這樣做的好處是在整個事務中不會阻塞讀操作。
事務中的鎖分為主（Primary）和從鎖（Secondary），對事務内首先操作的記錄對加主鎖，而後對事務内的其他記錄随着操作過程逐漸加從鎖并指向主鎖記錄，一旦遇到鎖沖突，優先級低的事務釋放鎖，事務復原；
事務内的記錄全部更新完畢後，事務進入第二階段，此時隻需要更新主鎖的狀态，事務即可結束；
從鎖的狀态則依賴異步程序和相關的讀操作來協助完成，由于從鎖記錄上保留了指向主鎖記錄的指針，異步程序和讀操作都很容易判斷從鎖的正确狀态，并進行更新。
分布式事務管理的其他内容，包括無鎖事務控制、全局時鐘的必要性等等，待後續文章中再讨論。
二、結語
本文最初的立意是面向幾類典型技術背景的同學，對“分布式資料庫”展開不同方向的解讀，并就其中部分技術要點進行闡述，使不同技術領域的同學能夠對相關技術有些許了解，為有興趣深入研究的同學做一個鋪墊。
随着分析的深入愈發覺得文章架構過于龐大難于駕馭，因而對關鍵技術的解讀也存在深淺不一的情況。對于本文中未及展開的部分，Ivan會盡力在後續系列文章中予以補充，水準所限文中必有錯漏之處，歡迎大家讨論和指正。
文獻參考：
[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