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

特別說(shuō)明：本文是原創(chuàng)文章侧纯，首發(fā)在DBAplus社群新锈，轉(zhuǎn)載須獲得作者同意。

一眶熬、NewSQL & NoSQL

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

目前具有較高知名度的NewSQL有Google的Spanner / F1、阿里的OceanBase绵疲、CockroachDB哲鸳、TiDB。其中后兩者是正在成長(zhǎng)中的開源項(xiàng)目盔憨，2018年相繼發(fā)布了2.0版本徙菠。

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

1.存儲(chǔ)引擎

B+ Tree

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

以下借用姜承堯老師書中的例子[1]來(lái)說(shuō)明B+樹的操作過(guò)程↓

存在高度為2的B+樹冰木，存儲(chǔ)在5個(gè)頁(yè)表中，每頁(yè)可存放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)插入一個(gè)索引值為70的記錄猴仑，由于對(duì)應(yīng)頁(yè)表的記錄已滿审轮，需要對(duì)B+樹重新排列肥哎，變更其父節(jié)點(diǎn)所在頁(yè)表的記錄，并調(diào)整相鄰頁(yè)表的記錄疾渣。完成重新分布后的效果如下：

變更過(guò)程中存在兩個(gè)問(wèn)題：

寫放大

本例中篡诽，邏輯上僅需要一條寫入記錄（黃色標(biāo)注），實(shí)際變動(dòng)了3個(gè)頁(yè)表中的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，也就是說(shuō)實(shí)際寫入磁盤的數(shù)據(jù)大小和應(yīng)用程序要求寫入數(shù)據(jù)大小之比

存儲(chǔ)不連續(xù)

新 增葉節(jié)點(diǎn)會(huì)加入到原有葉節(jié)點(diǎn)構(gòu)成的有序鏈表中吊圾，整體在邏輯上是連續(xù)的达椰；但磁盤存儲(chǔ)上，新增頁(yè)表申請(qǐng)的存儲(chǔ)空間與原有頁(yè)表很可能是不相鄰的项乒。這樣啰劲，在后續(xù)包 含新增葉節(jié)點(diǎn)的查詢中，將會(huì)出現(xiàn)多段連續(xù)讀取檀何，磁盤尋址的時(shí)間將會(huì)增加蝇裤。進(jìn)一步來(lái)說(shuō)，在B+Tree上進(jìn)行大量隨機(jī)寫會(huì)造成存儲(chǔ)的碎片化频鉴。

在 實(shí)際應(yīng)用B+Tree的數(shù)據(jù)庫(kù)產(chǎn)品（如MySQL）中栓辜，通常提供了填充因子（Factor Fill）進(jìn)行針對(duì)性的優(yōu)化。填充因子設(shè)置過(guò)小會(huì)造成頁(yè)表數(shù)量膨脹垛孔，增大對(duì)磁盤的掃描范圍藕甩，降低查詢性能；設(shè)置過(guò)大則會(huì)在數(shù)據(jù)插入時(shí)出現(xiàn)寫擴(kuò)大似炎，產(chǎn)生大量 的分頁(yè)，降低插入性能悯姊，同時(shí)由于數(shù)據(jù)存儲(chǔ)不連續(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(shí)由于大幅度降低了寫操作對(duì)磁盤的占用，使讀操作獲得更多的磁盤控制權(quán)垃僚，讀操作性能也并未受到過(guò)多的影響集绰。

寫操作簡(jiǎn)化過(guò)程如下：

當(dāng)寫入請(qǐng)求到達(dá)時(shí)，首先寫入內(nèi)存中Memtable谆棺，處理增量數(shù)據(jù)變化栽燕，同時(shí)記錄WAL預(yù)寫日志；

內(nèi) 存增量數(shù)據(jù)達(dá)到一定閾值后，當(dāng)前Memtable會(huì)被凍結(jié)碍岔，并創(chuàng)建一個(gè)新的Memtable浴讯，已凍結(jié)的Memtable中的數(shù)據(jù)會(huì)被順序?qū)懭氪疟P，形成有 序文件SSTable（Sorted String Table）蔼啦，這個(gè)操作被稱為Minor Compaction（在HBase中該操作稱為Flush操作榆纽，而Minor Compaction有其他含義）；

這些SSTable滿足一定的規(guī)則后進(jìn)行合并捏肢，即Major Compaction奈籽。每個(gè)Column Family下的所有SSTable被合并為一個(gè)大的SSTable。

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

NoSQL廣泛使用了LSM-Tree模型奉瘤，包括HBase勾拉、Cassandra、LevelDB盗温、RocksDB等K/V存儲(chǔ)藕赞。

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

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

注釋：

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

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

其次是對(duì)讀效率的影響仲锄，因?yàn)镾STable文件均處于同一層次劲妙，根據(jù)批量寫的執(zhí)行時(shí)序形成若干文件，所以不同文件中的Key（記錄主鍵）會(huì)出現(xiàn)交叉重疊儒喊，這樣在執(zhí)行讀操作時(shí)每個(gè)文件都要查找镣奋，產(chǎn)生非必要的I/O開銷。

最后是空間上的放大（Space Amplification）怀愧，最壞情況下LSM Tree需要與數(shù)據(jù)大小等同的自由空間以完成Compact動(dòng)作唆途，即空間放大了100%富雅，而B+樹的空間放大約為1/3。

Leveled LSM Tree

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

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

單個(gè)SSTable文件大小是固定的，在Cassandra中默認(rèn)設(shè)置為5M陶贼；

層 級(jí)從Level 0開始遞增啤贩，存儲(chǔ)數(shù)據(jù)量隨著層級(jí)的提升而增長(zhǎng)，層級(jí)之間有一致的增長(zhǎng)系數(shù)（Growth Factor）拜秧。Cassandra中Growth Factor設(shè)置為10痹屹，Level 1文件為1-10M則Level 2 文件為10-100M，這樣10TB數(shù)據(jù)量會(huì)達(dá)到Level 7枉氮；

Level 0的SSTable比較特殊志衍，固定為4個(gè)文件，且文件之間存在Key交叉重疊的情況聊替，從Level 1開始楼肪，SSTable不再出現(xiàn)Key交叉情況；

Level 0層的SSTable超過(guò)容量大小時(shí)惹悄，向Level 1 Compaction春叫，因?yàn)榇嬖贙ey交叉，所以要讀取Level 0的所有SSTable泣港；當(dāng)Level 1 的文件大小超過(guò)閾值時(shí)暂殖，將創(chuàng)建Level 2的SSTable并刪除掉Level 1原有的SSTable；當(dāng)Level 1的Key范圍對(duì)應(yīng)Level 2的多個(gè)SSTable時(shí)当纱，要重寫多個(gè)SSTable呛每，但由于SSTable的大小固定，所以通常只會(huì)涉及少數(shù)的SSTable惫东。

Level間Compact操作

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

對(duì)于讀取元數(shù)據(jù)來(lái)鎖定相關(guān)的SSTable徐矩，效率顯然超過(guò)了對(duì)所有SSTable的折半查找和Bloom Filter滞时。因此，讀取效率得到了顯著提升滤灯，按照某種評(píng)估方式[3]坪稽，在每行數(shù)據(jù)大小基本相同的情況下曼玩，90%的讀操作僅會(huì)訪問(wèn)一個(gè)SSTable。

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

NewSQL的策略

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

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

2.分片

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

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

Range&Hash

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

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

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

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

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

靜態(tài)分片&動(dòng)態(tài)分片

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

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

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

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

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

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

在分片處理上掉丽，NoSQL與NewSQL面臨的問(wèn)題非常接近。

3.副本

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

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

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

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

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

強(qiáng)同步：即 在多個(gè)副本都必須完成更新析恢，數(shù)據(jù)更新才能成功墨坚。這種模式的問(wèn)題是高延時(shí)、低可用性映挂，一次操作要等待所有副本的更新泽篮，加入了很多網(wǎng)絡(luò)通訊開銷盗尸，增加了延時(shí)。 多個(gè)副本節(jié)點(diǎn)必須都正常運(yùn)行的情況下帽撑，整個(gè)系統(tǒng)才是可用的泼各，任何單點(diǎn)的不可用都會(huì)造成整個(gè)系統(tǒng)的不可用。假設(shè)單點(diǎn)的可用性是95%亏拉，則三個(gè)節(jié)點(diǎn)的構(gòu)成的多 副本扣蜻，其可靠性為95% * 95% * 95% = 85.7%。因此雖然Oracle/MySQL等主流數(shù)據(jù)庫(kù)都提供了強(qiáng)同步方式及塘，但在企業(yè)實(shí)際生產(chǎn)環(huán)境中很少有應(yīng)用莽使。

半同步：MySQL提供了半同步方式，多個(gè)從節(jié)點(diǎn)從主節(jié)點(diǎn)同步數(shù)據(jù)笙僚，當(dāng)任意從節(jié)點(diǎn)同步成功吮旅，則主節(jié)點(diǎn)視為成功。這個(gè)邏輯模型有效規(guī)避了強(qiáng)同步的問(wèn)題味咳，多節(jié)點(diǎn)可用性的影響從“與”變?yōu)椤盎颉北硬Ｕ狭苏w的可用性。但遺憾的是在技術(shù)實(shí)現(xiàn)上存在瑕疵槽驶，會(huì)有退化為異步的問(wèn)題责嚷。

Paxos/Raft：該 方式將參與節(jié)點(diǎn)劃分為L(zhǎng)eader/Follower等角色，主節(jié)點(diǎn)向多個(gè)備節(jié)點(diǎn)寫入數(shù)據(jù)掂铐，當(dāng)存在一半以上節(jié)點(diǎn)寫入成功罕拂，即返回客戶端寫入成功。該方式可 以規(guī)避網(wǎng)絡(luò)抖動(dòng)和備節(jié)點(diǎn)服務(wù)異常對(duì)整體集群造成的影響全陨。其他像Zookeeper的ZAB協(xié)議爆班，Kafka的ISR機(jī)制，雖然與Paxos/Raft有所 區(qū)別辱姨，但大致是一個(gè)方向柿菩。

副本可靠性與副本可用性

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

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

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

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

HBase實(shí)現(xiàn)了數(shù)據(jù)的可靠性，但仍不能充分實(shí)現(xiàn)數(shù)據(jù)的可用性潮剪。CockroachDB和TiDB的思路是實(shí)現(xiàn)一個(gè)支持Raft的分布式KV存儲(chǔ)涣楷，這樣完全忽略單節(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無(wú)法規(guī)避的問(wèn)題看疗。隨著NewSQL對(duì)事務(wù)處理的完善沙峻，也讓過(guò)去十余年數(shù)據(jù)庫(kù)技術(shù)的演進(jìn)終于實(shí)現(xiàn)了一個(gè)接近完整的上升螺旋。

鑒于分布式事務(wù)管理的復(fù)雜性两芳，Ivan在本文中僅作簡(jiǎn)要說(shuō)明摔寨，后續(xù)文章中會(huì)進(jìn)一步展開。

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

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

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

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

請(qǐng)求階段：

事務(wù)詢問(wèn)碾阁。協(xié)調(diào)者向所有參與者發(fā)送事務(wù)內(nèi)容输虱，詢問(wèn)是否可以執(zhí)行事務(wù)提交操作，并開始等待各參與者的相應(yīng)脂凶；

執(zhí)行事務(wù)宪睹。各參與者節(jié)點(diǎn)執(zhí)行事務(wù)操作，并將Undo和Redo信息記入事務(wù)日志中蚕钦；

各參與者向協(xié)調(diào)者反饋事務(wù)詢問(wèn)的響應(yīng)亭病。如果參與者成功執(zhí)行了事務(wù)操作，那么就反饋給協(xié)調(diào)者Yes嘶居，表示事務(wù)可以執(zhí)行罪帖；如果參與者沒(méi)有成功執(zhí)行事務(wù)，那么就反饋給No邮屁，表示事務(wù)不可以執(zhí)行整袁。

提交階段：

提交事務(wù)。發(fā)送提交請(qǐng)求佑吝。協(xié)調(diào)者向所有參與者節(jié)點(diǎn)發(fā)出Commit請(qǐng)求葬项；

事務(wù)提交。參與者接到Commit后迹蛤，會(huì)正式執(zhí)行事務(wù)提交操作民珍，并在完成提交之后釋放在整個(gè)事務(wù)執(zhí)行期間占有的事務(wù)資源；

反饋事務(wù)提交結(jié)果盗飒。參與者在完成事務(wù)提交后嚷量，向協(xié)調(diào)者發(fā)送Ack消息；

完成事務(wù)逆趣。協(xié)調(diào)者收到所有參與者反饋的Ack消息后蝶溶，完成事務(wù)；

中斷事務(wù)宣渗。發(fā)送回滾請(qǐng)求抖所。協(xié)調(diào)者向所有參與者發(fā)出Rollback請(qǐng)求；

事務(wù)回滾痕囱。參與者接收到Rollback請(qǐng)求后田轧，會(huì)利用其階段一記錄的Undo信息來(lái)執(zhí)行事務(wù)回滾操作，并在完成回滾之后釋放在整個(gè)事務(wù)執(zhí)行期間占有的事務(wù)資源鞍恢；

反饋事務(wù)回滾結(jié)果傻粘。參與者在完成事務(wù)回滾后每窖，向協(xié)調(diào)者發(fā)送Ack消息；

中斷事務(wù)弦悉。協(xié)調(diào)者接收到所有參與者反饋的Ack消息后窒典，完成事務(wù)中斷。

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

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

Spanner

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

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

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

Percolator

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

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

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

事務(wù)中的鎖分為主（Primary）和從鎖（Secondary），對(duì)事務(wù)內(nèi)首先操作的記錄對(duì)加主鎖赌结，而后對(duì)事務(wù)內(nèi)的其他記錄隨著操作過(guò)程逐步加從鎖并指向主鎖記錄捞蛋，一旦遇到鎖沖突，優(yōu)先級(jí)低的事務(wù)釋放鎖柬姚，事務(wù)回滾拟杉；

事務(wù)內(nèi)的記錄全部更新完畢后，事務(wù)進(jìn)入第二階段量承，此時(shí)只需要更新主鎖的狀態(tài)搬设，事務(wù)即可結(jié)束；

從鎖的狀態(tài)則依賴異步進(jìn)程和相關(guān)的讀操作來(lái)協(xié)助完成撕捍，由于從鎖記錄上保留了指向主鎖記錄的指針拿穴，異步進(jìn)程和讀操作都很容易判斷從鎖的正確狀態(tài)，并進(jìn)行更新忧风。

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

二、結(jié)語(yǔ)

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

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

文獻(xiàn)參考：

[1] 姜承堯, MySQL技術(shù)內(nèi)幕：InnoDB存儲(chǔ)引擎機(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

標(biāo)簽:?分布式數(shù)據(jù)庫(kù),?NewSQL,?事務(wù),?交易型,?NoSQL