在上一篇文章《從架構(gòu)特點(diǎn)到功能缺陷，重新認(rèn)識分析型分布式數(shù)據(jù)庫》中，我們完成了對不同“分布式數(shù)據(jù)庫”的橫向分析，本文我將講述拆解的第二部分，會結(jié)合NoSQL與NewSQL的差異，從縱向來談?wù)凮LTP場景“分布式數(shù)據(jù)庫”實(shí)現(xiàn)方案的關(guān)鍵技術(shù)要點(diǎn)。這樣的思考是前文的延伸，也是分布式數(shù)據(jù)庫專題文章的一個總綱，其中的要點(diǎn)我之后也會單獨(dú)撰文闡述。

一、NewSQL & NoSQL

NewSQL是本專題關(guān)注的重點(diǎn)，也是前文中特指的“分布式數(shù)據(jù)庫”，其適用于OLTP場景，具有高并發(fā)低延遲的特點(diǎn)，特性接近Oracle/DB2等傳統(tǒng)數(shù)據(jù)庫，依賴通用X86服務(wù)器實(shí)現(xiàn)性能上的水平拓展，能夠扛住海量交易的性能壓力。

目前具有較高知名度的NewSQL有Google的Spanner / F1、阿里的OceanBase、CockroachDB、TiDB。其中后兩者是正在成長中的開源項目，2018年相繼發(fā)布了2.0版本。

NewSQL與NoSQL有很深的淵源，所以下文在對NewSQL的介紹中會穿插一些NoSQL對應(yīng)的實(shí)現(xiàn)技術(shù)方式。

1、存儲引擎

B+ Tree

B+樹是關(guān)系型數(shù)據(jù)庫常用的索引存儲模型，能夠支持高效的范圍掃描，葉節(jié)點(diǎn)相關(guān)鏈接并且按主鍵有序，掃描時避免了耗時的遍歷樹操作。B+樹的局限在于不適合大量隨機(jī)寫場景，會出現(xiàn)“寫放大”和“存儲碎片”。

以下借用姜承堯老師書中的例子[1]來說明B+樹的操作過程

存在高度為2的B+樹，存儲在5個頁表中，每頁可存放4條記錄，扇出為5。下圖展示了該B+ Tree的構(gòu)造，其中略去了葉子節(jié)點(diǎn)指向數(shù)據(jù)的指針以及葉子節(jié)點(diǎn)之間的順序指針：

B+樹由內(nèi)節(jié)點(diǎn)（InterNode）和葉節(jié)點(diǎn)（LeafNode）兩類節(jié)點(diǎn)構(gòu)成，后者攜帶指向數(shù)據(jù)的指針，而前者僅包含索引信息。

當(dāng)插入一個索引值為70的記錄，由于對應(yīng)頁表的記錄已滿，需要對B+樹重新排列，變更其父節(jié)點(diǎn)所在頁表的記錄，并調(diào)整相鄰頁表的記錄。完成重新分布后的效果如下：

變更過程中存在兩個問題：

• 寫放大

本例中，邏輯上僅需要一條寫入記錄（黃色標(biāo)注），實(shí)際變動了3個頁表中的7條索引記錄，額外的6條記錄（綠色標(biāo)注）是為了維護(hù)B+樹結(jié)構(gòu)產(chǎn)生的寫放大。

注：寫放大（Write Amplification）：Write amplification is the amount of data written to storage compared to the amount of data that the application wrote，也就是說實(shí)際寫入磁盤的數(shù)據(jù)大小和應(yīng)用程序要求寫入數(shù)據(jù)大小之比

• 存儲不連續(xù)

新增葉節(jié)點(diǎn)會加入到原有葉節(jié)點(diǎn)構(gòu)成的有序鏈表中，整體在邏輯上是連續(xù)的；但磁盤存儲上，新增頁表申請的存儲空間與原有頁表很可能是不相鄰的。這樣，在后續(xù)包含新增葉節(jié)點(diǎn)的查詢中，將會出現(xiàn)多段連續(xù)讀取，磁盤尋址的時間將會增加。進(jìn)一步來說，在B+Tree上進(jìn)行大量隨機(jī)寫會造成存儲的碎片化。

在實(shí)際應(yīng)用B+Tree的數(shù)據(jù)庫產(chǎn)品（如MySQL）中，通常提供了填充因子（Factor Fill）進(jìn)行針對性的優(yōu)化。填充因子設(shè)置過小會造成頁表數(shù)量膨脹，增大對磁盤的掃描范圍，降低查詢性能；設(shè)置過大則會在數(shù)據(jù)插入時出現(xiàn)寫擴(kuò)大，產(chǎn)生大量的分頁，降低插入性能，同時由于數(shù)據(jù)存儲不連續(xù)，也降低了查詢性能。

LSM-Tree

LSM-Tree（Log Structured-Merge Tree）由Patrick O'Neil首先提出，其在論文[2]中系統(tǒng)闡述了與B+樹的差異。而后Google在Bigtable中引入了該模型，如下圖所示：

LSM-Tree的主要思想是借助內(nèi)存將隨機(jī)寫轉(zhuǎn)換為順序?qū)懀嵘藢懭胄阅埽煌瑫r由于大幅度降低了寫操作對磁盤的占用，使讀操作獲得更多的磁盤控制權(quán)，讀操作性能也并未受到過多的影響。

寫操作簡化過程如下：

• 當(dāng)寫入請求到達(dá)時，首先寫入內(nèi)存中Memtable，處理增量數(shù)據(jù)變化，同時記錄WAL預(yù)寫日志；
• 內(nèi)存增量數(shù)據(jù)達(dá)到一定閾值后，當(dāng)前Memtable會被凍結(jié)，并創(chuàng)建一個新的Memtable，已凍結(jié)的Memtable中的數(shù)據(jù)會被順序?qū)懭氪疟P，形成有序文件SSTable（Sorted String Table），這個操作被稱為Minor Compaction（在HBase中該操作稱為Flush操作，而Minor Compaction有其他含義）；
• 這些SSTable滿足一定的規(guī)則后進(jìn)行合并，即Major Compaction。每個Column Family下的所有SSTable被合并為一個大的SSTable。

該模型規(guī)避了隨機(jī)寫的IO效率問題，有效緩解了B樹索引的寫放大問題，極大的提升了寫入效率。

NoSQL廣泛使用了LSM-Tree模型，包括HBase、Cassandra、LevelDB、RocksDB等K/V存儲。

當(dāng)然LSM-Tree也存在自身的缺陷：

• 首先，其Major Compaction的操作非常重影響聯(lián)機(jī)讀寫，同時也會產(chǎn)生寫放大。因?yàn)檫@個原因，HBase的使用中通常會禁止系統(tǒng)自動執(zhí)行Major Compaction。

注釋：

Major Compaction操作的意義是降低讀操作的時間復(fù)雜度。設(shè)系統(tǒng)包含多個SSTable文件，共有N數(shù)據(jù)，SSTable平均包含m數(shù)據(jù)。

執(zhí)行讀操作時，對單一SSTable文件采用折半查找方法的時間復(fù)雜度為O(log2m)，則整體時間復(fù)雜度為O(N/m* log2m)；合并為一個SSTable后，時間復(fù)雜度可降低到O(log2N)

• 其次是對讀效率的影響，因?yàn)镾STable文件均處于同一層次，根據(jù)批量寫的執(zhí)行時序形成若干文件，所以不同文件中的Key（記錄主鍵）會出現(xiàn)交叉重疊，這樣在執(zhí)行讀操作時每個文件都要查找，產(chǎn)生非必要的I/O開銷。
• 最后是空間上的放大（Space Amplification），最壞情況下LSM Tree需要與數(shù)據(jù)大小等同的自由空間以完成Compact動作，即空間放大了100%，而B+樹的空間放大約為1/3。

Leveled LSM Tree

Leveled LSM Tree 的變化在于將SSTable做了進(jìn)一步的分層，降低寫放大的情況，縮小了讀取的文件范圍，在LevelDB 中率先使用，隨后Cassandra 1.0也引入了該策略[3]。

SSTable的層次化設(shè)計策略是：

• 單個SSTable文件大小是固定的，在Cassandra中默認(rèn)設(shè)置為5M；
• 層級從Level 0開始遞增，存儲數(shù)據(jù)量隨著層級的提升而增長，層級之間有一致的增長系數(shù)（Growth Factor）。Cassandra中Growth Factor設(shè)置為10，Level 1文件為1-10M則Level 2 文件為10-100M，這樣10TB數(shù)據(jù)量會達(dá)到Level 7；
• Level 0的SSTable比較特殊，固定為4個文件，且文件之間存在Key交叉重疊的情況，從Level 1開始，SSTable不再出現(xiàn)Key交叉情況；
• Level 0層的SSTable超過容量大小時，向Level 1 Compaction，因?yàn)榇嬖贙ey交叉，所以要讀取Level 0的所有SSTable；當(dāng)Level 1 的文件大小超過閾值時，將創(chuàng)建Level 2的SSTable并刪除掉Level 1原有的SSTable；當(dāng)Level 1的Key范圍對應(yīng)Level 2的多個SSTable時，要重寫多個SSTable，但由于SSTable的大小固定，所以通常只會涉及少數(shù)的SSTable。

Level間Compact操作

多個有序的SSTable，避免了Major Compaction這樣的重量級文件重寫，每次僅更新部分內(nèi)容，降低了寫放大率。

對于讀取元數(shù)據(jù)來鎖定相關(guān)的SSTable，效率顯然超過了對所有SSTable的折半查找和Bloom Filter。因此，讀取效率得到了顯著提升，按照某種評估方式[3]，在每行數(shù)據(jù)大小基本相同的情況下，90%的讀操作僅會訪問一個SSTable。

該策略下，Compaction的操作更加頻繁，帶來了更多I/O開銷，對寫密集型操作而言，最終結(jié)果是否能夠得到足夠的效率提升存在不確定性，需要在應(yīng)用中權(quán)衡。

NewSQL的策略

NewSQL數(shù)據(jù)庫的存儲層普遍都采用K/V存儲，所以基本沿用了LSM Tree模型。其中CockroachDB和TiDB都在KV層使用RocksDB。OceanBase采用了不同的方法規(guī)避Major Compaction的影響，大體是利用閑置的副本（Follower）進(jìn)行Compaction操作，避免了對讀操作的阻塞，在Compaction完成后，進(jìn)行副本的角色的替換。

同時，K/V存儲引擎仍然在繼續(xù)發(fā)展中，一些其他的改進(jìn)如分形樹(Fractal Tree)等，限于篇幅我們就不在此展開了。

2、分片

分片（Sharding）概念與RDBMS的分區(qū)相近，是分布式數(shù)據(jù)庫或分布式存儲系統(tǒng)的最關(guān)鍵特性，是實(shí)現(xiàn)水平擴(kuò)展的基礎(chǔ)，也在NoSQL類系統(tǒng)中得到了大量運(yùn)用。

分片的目標(biāo)是將數(shù)據(jù)盡量均勻地分布在多個節(jié)點(diǎn)上，利用多節(jié)點(diǎn)的數(shù)據(jù)存儲及處理能力提升數(shù)據(jù)庫整體性能。

Range&Hash

雖然不同的系統(tǒng)中對分片策略有很多細(xì)分，但大致可以歸納為兩種方式，Range和Hash。

Range分片有利于范圍查詢，而Hash分片更容易做到數(shù)據(jù)均衡分布。在實(shí)際應(yīng)用中，Range分片似乎使用得更多，但也有很多應(yīng)用會混合了兩種分片方式。

HBase采用了Range方式，根據(jù)Rowkey的字典序排列，當(dāng)超過單個Region的上限后分裂為兩個新的Region。Range的優(yōu)點(diǎn)是數(shù)據(jù)位置接近，在訪問數(shù)據(jù)時，范圍查找的成本低；缺點(diǎn)也比較明顯，在容易出現(xiàn)熱點(diǎn)集中的問題。

例如，在HBase通常不建議使用業(yè)務(wù)流水號作為RowKey，因?yàn)檫B續(xù)遞增的順序號在多數(shù)時間內(nèi)都會被分配到同一個RegionServer，造成并發(fā)訪問同時競爭這個RegionServer資源的情況。為了避免該問題，會建議將RowKey進(jìn)行編碼，序號反轉(zhuǎn)或加鹽等方式。這種方式實(shí)質(zhì)上是使用應(yīng)用層的設(shè)計策略，將Range分片轉(zhuǎn)換成類似Hash分片的方式。

Spanner的底層存儲沿用了BigTable的很多設(shè)計思路，但在分片上有所調(diào)整，在Tablet內(nèi)增加了Directory的動態(tài)調(diào)配來規(guī)避Range分片與操作熱點(diǎn)不匹配的問題，后續(xù)在事務(wù)管理部分再詳細(xì)描述。

靜態(tài)分片&動態(tài)分片

按照分片的產(chǎn)生策略可以分為靜態(tài)分片和動態(tài)分片兩類。

靜態(tài)分片在系統(tǒng)建設(shè)之初已經(jīng)決定分片的數(shù)量，后期再改動代價很大；動態(tài)分片是指根據(jù)數(shù)據(jù)的情況指定的分片策略，其變更成本較低，可以按需調(diào)整。

傳統(tǒng)的DB + Proxy方案，進(jìn)行水平分庫分表就是一種常見的靜態(tài)分片。我們熟知的幾個互聯(lián)網(wǎng)大廠在大規(guī)模交易系統(tǒng)中都進(jìn)行過類似的設(shè)計，默認(rèn)將數(shù)據(jù)做成某個固定數(shù)量的分片，比如100、255、1024，或者其它你喜歡的數(shù)字。分片的數(shù)量可以根據(jù)系統(tǒng)預(yù)期目標(biāo)的整體服務(wù)能力、數(shù)據(jù)量和單節(jié)點(diǎn)容量進(jìn)行評估，當(dāng)然具體到100片合適還是1024片合適，多少還是有拍腦袋的成分。

在NoSQL中，Redis集群也采用同樣的靜態(tài)分片方式，默認(rèn)為16384個哈希槽位（等同于分片）。

靜態(tài)分片的缺點(diǎn)是分片數(shù)量已經(jīng)被確定，基于單點(diǎn)處理能力形成一個容量的上限；靈活性較差，后續(xù)再做分片數(shù)量調(diào)整時，數(shù)據(jù)遷移困難，實(shí)現(xiàn)復(fù)雜。優(yōu)點(diǎn)也很明顯，靜態(tài)分片的策略幾乎是固化的，因此對分區(qū)鍵、分區(qū)策略等元數(shù)據(jù)管理的依賴度很低，而這些元數(shù)據(jù)往往會形成分布式數(shù)據(jù)庫中的單點(diǎn)，成為提升可靠性、可用性的障礙。

相比之下，動態(tài)分片的靈活性更好，適用于更豐富的應(yīng)用場景，所以NewSQL也主要采用動態(tài)分片方式，代價則是對元數(shù)據(jù)管理的復(fù)雜度增加。

在分片處理上，NoSQL與NewSQL面臨的問題非常接近。

3、副本

首先是由于通用設(shè)備單機(jī)可靠性低，必須要通過多機(jī)副本的方式。本文中關(guān)注兩個問題：一是副本一致性；二是副本可靠性與副本可用性的差異。

數(shù)據(jù)副本一致性

多副本必然引入了副本的數(shù)據(jù)一致性問題。之前已經(jīng)有大名鼎鼎的CAP理論，相信大家都是耳熟能詳了，但這里要再啰嗦一句，CAP里的一致性和事務(wù)管理中的一致性不是一回事。我遇到過很多同學(xué)有誤解，用CAP為依據(jù)來證明分布式架構(gòu)不可能做到事務(wù)的強(qiáng)一致性，而只能是最終一致性。

事務(wù)的一致性是指不同數(shù)據(jù)實(shí)體在同一事務(wù)中一起變更，要么全部成功，要么全部失敗；而CAP中的一致性是指原子粒度的數(shù)據(jù)副本如何保證一致性，多副本在邏輯上是同一數(shù)據(jù)實(shí)體。

副本同步大致歸納為以下三種模式：

• 強(qiáng)同步：即在多個副本都必須完成更新，數(shù)據(jù)更新才能成功。這種模式的問題是高延時、低可用性，一次操作要等待所有副本的更新，加入了很多網(wǎng)絡(luò)通訊開銷，增加了延時。多個副本節(jié)點(diǎn)必須都正常運(yùn)行的情況下，整個系統(tǒng)才是可用的，任何單點(diǎn)的不可用都會造成整個系統(tǒng)的不可用。假設(shè)單點(diǎn)的可用性是95%，則三個節(jié)點(diǎn)的構(gòu)成的多副本，其可靠性為95% * 95% * 95% = 85.7%。因此雖然Oracle/MySQL等主流數(shù)據(jù)庫都提供了強(qiáng)同步方式，但在企業(yè)實(shí)際生產(chǎn)環(huán)境中很少有應(yīng)用。
• 半同步：MySQL提供了半同步方式，多個從節(jié)點(diǎn)從主節(jié)點(diǎn)同步數(shù)據(jù)，當(dāng)任意從節(jié)點(diǎn)同步成功，則主節(jié)點(diǎn)視為成功。這個邏輯模型有效規(guī)避了強(qiáng)同步的問題，多節(jié)點(diǎn)可用性的影響從“與”變?yōu)?ldquo;或”，保障了整體的可用性。但遺憾的是在技術(shù)實(shí)現(xiàn)上存在瑕疵，會有退化為異步的問題。
• Paxos/Raft：該方式將參與節(jié)點(diǎn)劃分為Leader/Follower等角色，主節(jié)點(diǎn)向多個備節(jié)點(diǎn)寫入數(shù)據(jù)，當(dāng)存在一半以上節(jié)點(diǎn)寫入成功，即返回客戶端寫入成功。該方式可以規(guī)避網(wǎng)絡(luò)抖動和備節(jié)點(diǎn)服務(wù)異常對整體集群造成的影響。其他像Zookeeper的ZAB協(xié)議，Kafka的ISR機(jī)制，雖然與Paxos/Raft有所區(qū)別，但大致是一個方向。

副本可靠性與副本可用性

數(shù)據(jù)副本僅保證了數(shù)據(jù)的持久性，即數(shù)據(jù)不丟失。我們還面臨著副本的可用性問題，即數(shù)據(jù)是否持續(xù)提供服務(wù)。以HBASE-10070為例來說明這個問題：

HBase通過分布式文件系統(tǒng)HDFS實(shí)現(xiàn)了數(shù)據(jù)多副本的存儲，但是在提供服務(wù)時，客戶端是連接到RegionServer進(jìn)而訪問HDFS上的數(shù)據(jù)。因?yàn)橐粋€Region會被唯一的RegionServer管理，所以RegionServer仍然是個單點(diǎn)。

在RegionServer宕機(jī)時，需要在一定的間隔后才被HMaster感知，后者再調(diào)度起一個新的RegionServer并加載相應(yīng)的Region，整個過程可能達(dá)到幾十秒。在大規(guī)模集群中，單點(diǎn)故障是頻繁出現(xiàn)的，每個單點(diǎn)帶來幾十秒的局部服務(wù)中斷，大大降低了HBase的可用性。

為了解決這問題，HBase引入從RegionServer節(jié)點(diǎn)的概念，在主節(jié)點(diǎn)宕機(jī)時，從節(jié)點(diǎn)持續(xù)提供服務(wù)。而RegionServer并不是無狀態(tài)服務(wù)，在內(nèi)存中存儲數(shù)據(jù)，又出現(xiàn)了主從RegionServer間的數(shù)據(jù)同步問題。

HBase實(shí)現(xiàn)了數(shù)據(jù)的可靠性，但仍不能充分實(shí)現(xiàn)數(shù)據(jù)的可用性。CockroachDB和TiDB的思路是實(shí)現(xiàn)一個支持Raft的分布式KV存儲，這樣完全忽略單節(jié)點(diǎn)上內(nèi)存數(shù)據(jù)和磁盤數(shù)據(jù)的差異，確保數(shù)據(jù)的可用性。

4、事務(wù)管理

分布式事務(wù)處理由于其復(fù)雜性，是NoSQL發(fā)展中最先被舍棄的特性。但由于大規(guī)模互聯(lián)網(wǎng)應(yīng)用廣泛出現(xiàn)，其現(xiàn)實(shí)意義逐漸突出，又重新成為NewSQL無法規(guī)避的問題。隨著NewSQL對事務(wù)處理的完善，也讓過去十余年數(shù)據(jù)庫技術(shù)的演進(jìn)終于實(shí)現(xiàn)了一個接近完整的上升螺旋。

鑒于分布式事務(wù)管理的復(fù)雜性，我在本文中僅作簡要說明，后續(xù)文章中會進(jìn)一步展開。

NewSQL事務(wù)管理從控制手段上分為鎖（Lock-Base）和無鎖（Lock-Free）兩種，其中，無鎖模式通常是基于時間戳協(xié)調(diào)事務(wù)的沖突。從資源占用方式上，分為樂觀協(xié)議和悲觀協(xié)議，兩者區(qū)別在于對資源沖突的預(yù)期不同：悲觀協(xié)議認(rèn)為沖突是頻繁的，所以會盡早搶占資源，保證事務(wù)的順利完成；樂觀協(xié)議認(rèn)為沖突是偶發(fā)的，只在可以容忍的最晚時間才會搶占資源。

以下通過最經(jīng)典的“兩階段提交協(xié)議”和具體的兩種應(yīng)用實(shí)踐，來具體闡述實(shí)現(xiàn)方式：

兩階段提交協(xié)議（2PC）

兩階段提交協(xié)議（Tow phase commit protocol，2PC）是經(jīng)典的分布式事務(wù)處理模型，處理過程分為兩個階段：

請求階段：

• 事務(wù)詢問。協(xié)調(diào)者向所有參與者發(fā)送事務(wù)內(nèi)容，詢問是否可以執(zhí)行事務(wù)提交操作，并開始等待各參與者的相應(yīng)；
• 執(zhí)行事務(wù)。各參與者節(jié)點(diǎn)執(zhí)行事務(wù)操作，并將Undo和Redo信息記入事務(wù)日志中；
• 各參與者向協(xié)調(diào)者反饋事務(wù)詢問的響應(yīng)。如果參與者成功執(zhí)行了事務(wù)操作，那么就反饋給協(xié)調(diào)者Yes，表示事務(wù)可以執(zhí)行；如果參與者沒有成功執(zhí)行事務(wù)，那么就反饋給No，表示事務(wù)不可以執(zhí)行。

提交階段：

• 提交事務(wù)。發(fā)送提交請求。協(xié)調(diào)者向所有參與者節(jié)點(diǎn)發(fā)出Commit請求；
• 事務(wù)提交。參與者接到Commit后，會正式執(zhí)行事務(wù)提交操作，并在完成提交之后釋放在整個事務(wù)執(zhí)行期間占有的事務(wù)資源；
• 反饋事務(wù)提交結(jié)果。參與者在完成事務(wù)提交后，向協(xié)調(diào)者發(fā)送Ack消息；
• 完成事務(wù)。協(xié)調(diào)者收到所有參與者反饋的Ack消息后，完成事務(wù)；
• 中斷事務(wù)。發(fā)送回滾請求。協(xié)調(diào)者向所有參與者發(fā)出Rollback請求；
• 事務(wù)回滾。參與者接收到Rollback請求后，會利用其階段一記錄的Undo信息來執(zhí)行事務(wù)回滾操作，并在完成回滾之后釋放在整個事務(wù)執(zhí)行期間占有的事務(wù)資源；
• 反饋事務(wù)回滾結(jié)果。參與者在完成事務(wù)回滾后，向協(xié)調(diào)者發(fā)送Ack消息；
• 中斷事務(wù)。協(xié)調(diào)者接收到所有參與者反饋的Ack消息后，完成事務(wù)中斷。

該模型的主要優(yōu)點(diǎn)是原理簡單，實(shí)現(xiàn)方便。

缺點(diǎn)也很明顯，首先是同步阻塞，整個事務(wù)過程中所有參與者都被鎖定，必然大幅度影響并發(fā)性能；其次是單點(diǎn)問題，協(xié)調(diào)者是一個單點(diǎn)，如果在第二階段宕機(jī)，參與者將一直鎖定。

Spanner

根據(jù)Spanner論文[4]的介紹，其分布式事務(wù)管理仍采用了2PC的方式，但創(chuàng)新性的設(shè)計是改變了Tablet的數(shù)據(jù)分布策略，Tablet不再是單一的連續(xù)Key數(shù)據(jù)結(jié)構(gòu)，新增了Directory作為最小可調(diào)度的數(shù)據(jù)組織單元。

通過動態(tài)的調(diào)配，降低事務(wù)內(nèi)數(shù)據(jù)跨節(jié)點(diǎn)分布的概率。

我將這種事務(wù)處理的設(shè)計思想理解為：“最好的分布式事務(wù)處理方式，就是不做分布式事務(wù)處理，將其變?yōu)楸镜厥聞?wù)”。在OceanBase的早期版本中也采用了一個獨(dú)立的服務(wù)器UpdateServer來集中處理事務(wù)操作，理念有相近之處。

Percolator

Percolator[5]是Google開發(fā)的增量處理網(wǎng)頁索引系統(tǒng)，在其誕生前，Google采用MapReduce進(jìn)行全量的網(wǎng)頁索引處理。這樣一次處理的時間取決于存量網(wǎng)頁的數(shù)量，耗時很長；而且即使某天只有少量的網(wǎng)頁變更，同樣要執(zhí)行全量的索引處理，浪費(fèi)了大量的資源與時間。采用Percolator的增量處理方式后，大幅度減少了處理時間。

在這篇論文中給出了一個分布式事務(wù)模型，是“兩階段提交協(xié)議”的變形，其將第二階段的工作簡化到極致，大幅提升了處理效率。

具體實(shí)現(xiàn)上，Percolator是基于BigTable實(shí)現(xiàn)分布式事務(wù)管理，通過MVCC和鎖的兩種機(jī)制結(jié)合，事務(wù)內(nèi)所有要操作的記錄均為新增版本而不更新現(xiàn)有版本。這樣做的好處是在整個事務(wù)中不會阻塞讀操作。

• 事務(wù)中的鎖分為主（Primary）和從鎖（Secondary），對事務(wù)內(nèi)首先操作的記錄對加主鎖，而后對事務(wù)內(nèi)的其他記錄隨著操作過程逐步加從鎖并指向主鎖記錄，一旦遇到鎖沖突，優(yōu)先級低的事務(wù)釋放鎖，事務(wù)回滾；
• 事務(wù)內(nèi)的記錄全部更新完畢后，事務(wù)進(jìn)入第二階段，此時只需要更新主鎖的狀態(tài)，事務(wù)即可結(jié)束；
• 從鎖的狀態(tài)則依賴異步進(jìn)程和相關(guān)的讀操作來協(xié)助完成，由于從鎖記錄上保留了指向主鎖記錄的指針，異步進(jìn)程和讀操作都很容易判斷從鎖的正確狀態(tài)，并進(jìn)行更新。

分布式事務(wù)管理的其他內(nèi)容，包括無鎖事務(wù)控制、全局時鐘的必要性等等，待后續(xù)文章中再討論。

二、結(jié)語

本文及其前文最初的立意是面向幾類典型技術(shù)背景的同學(xué)，對“分布式數(shù)據(jù)庫”展開不同方向的解讀，并就其中部分技術(shù)要點(diǎn)進(jìn)行闡述，使不同技術(shù)領(lǐng)域的同學(xué)能夠?qū)ο嚓P(guān)技術(shù)有些許了解，為有興趣深入研究的同學(xué)做一個鋪墊。

隨著分析的深入愈發(fā)覺得文章框架過于龐大難于駕馭，因而對關(guān)鍵技術(shù)的解讀也存在深淺不一的情況。對于本文中未及展開的部分，我會盡力在后續(xù)系列文章中予以補(bǔ)充，水平所限文中必有錯漏之處，歡迎大家討論和指正。

文獻(xiàn)參考：

[1] 姜承堯, MySQL技術(shù)內(nèi)幕：InnoDB存儲引擎機(jī), 械工業(yè)出版社, 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