一、引子

最近一兩年里，每次做分布式數(shù)據(jù)庫的內(nèi)容分享活動時，總是會提及現(xiàn)在數(shù)據(jù)庫的兩個重要的存儲結(jié)構(gòu)，B-TREE和LSM-TREE。因為，我覺得作為數(shù)據(jù)庫的存儲根基，無論是要選型，或者是用好一個數(shù)據(jù)庫，清楚這兩的差別和各自特點，都特別重要。但是幾乎每一次都只能提一下，哪種數(shù)據(jù)庫用了哪個存儲。再多就是稍微介紹LSM-TREE的寫入友好。對于有些朋友，正面臨二選一項目抉擇時，這點信息顯然是不夠的。于是他們會想要知道，更多二者差異細(xì)節(jié)，以及到底哪一種適合自己的系統(tǒng)?？上铱偸侵荒苓z憾講個大概，并解釋要徹底講清楚的話，整個分享就只能光講這個可能時間還不太夠。然而，我還是覺得每次都含含糊糊的過去，未免也有點耍流氓的感覺?？偟谜覀€機會，把這里面一些有意思的內(nèi)容拿出來羅列一下。適逢國慶宅家，想想也是時候把這個坑給填一填了。

當(dāng)然，本文并不打算從0開始介紹LSM-TREE，那樣篇幅也太冗長了。本文默認(rèn)各位讀者具有一點B-TREE和LSM-TREE的基礎(chǔ)背景知識。

二、背景板-分布式關(guān)系型數(shù)據(jù)庫

其實，拋開分布式數(shù)據(jù)庫來純寫這兩個存儲引擎，似乎要更加簡明一點。但是，這樣的話實用性不太行。單機版LSM-TREE數(shù)據(jù)庫有排名在100名左右的ROCKSDB，LEVELDB。它們被劃分為KEY-VALUE類型，而且它們通常不會直接出現(xiàn)在我們的視野，也極少直接被使用在項目中。然而，基于LSM-TREE的分布式數(shù)據(jù)庫則是非常常見的，比如這些：

甚至可能有些人，是有用分布式數(shù)據(jù)庫的需求，才去學(xué)習(xí)和理解LSM-TREE的（比如說我就是先要使用CASSANDRA）。不過帶上分布式的這個背景，未免多少會使得存儲結(jié)構(gòu)差異比對，變得不那么純粹。因為分布式數(shù)據(jù)庫嘛，總是帶來了一些額外的開銷。比如說數(shù)據(jù)庫層面的SQL解析到分布式執(zhí)行計劃產(chǎn)生。再比如說分布式的場景下，分布式事務(wù)、全局時間戳獲取等等。不過這個還是可以大致對比一下基于B樹的分布式數(shù)據(jù)庫情況來說明一下。但就具體到每一個數(shù)據(jù)庫的話，因為各個數(shù)據(jù)庫的具體實現(xiàn)方式各有不同，實際情況就得看某一個具體的數(shù)據(jù)庫還做了些什么額外的動作，再把它附加上去。

還有關(guān)系型也算是一個重要背景。因為有些特殊項目場景、特殊的數(shù)據(jù)格式，使用某種數(shù)據(jù)庫或者存儲結(jié)構(gòu)時快得飛起，然而卻缺乏了一般通用性。其實，像REDIS和CASSANDRA這樣的數(shù)據(jù)庫已經(jīng)非常的熱門，使用范圍也非常的廣。但是我們在項目中使用這些數(shù)據(jù)庫，也還是充當(dāng)某種功能性的角色比較多，我們很難把它做成系統(tǒng)的主數(shù)據(jù)庫。尤其是那些有歷史包袱遷移而來的系統(tǒng)。無論如何，關(guān)系型模型，基本上還是我們見到的主要情況。

所以我準(zhǔn)備在分布式和關(guān)系型的數(shù)據(jù)庫大背景下，以最為常見的幾種數(shù)據(jù)訪問形態(tài)來描述一下，這樣就更加具有真實的參考性價值。先攤開來數(shù)據(jù)庫的主要操作都做了些什么。然后再套幾個經(jīng)典的案例場景進(jìn)去看看。這樣子的話，圍繞著分布式關(guān)系型數(shù)據(jù)庫來展開這兩顆樹的內(nèi)容，也就更貼近大家現(xiàn)實使用這兩存儲結(jié)構(gòu)的實際需求，起碼我感覺上是如此。

在開始眼花繚亂的各種操作敘述之前，我們可以先草率的做一點假定。比如說，我們SQL的響應(yīng)時長，認(rèn)為是最關(guān)鍵的性能指標(biāo)。比如說，我們認(rèn)為內(nèi)存中的操作比較快，對性能的影響稍微小一些。而磁盤操作比較慢，比較可能影響交易時長。再比如，異步動作，基本不怎么影響交易性能。這些假定雖然草率，但是我認(rèn)為這可以使我們對一些數(shù)據(jù)庫操作的性能開銷，有一些更粗暴而直觀的感性認(rèn)知。

三、LSM-TREE之優(yōu)勢的寫

寫友好，幾乎是LSM-TREE的標(biāo)志性特點，那么我們就從寫流程開始。先來個經(jīng)典的LSM-TREE的圖。

STEP 1 WAL日志寫入(Write Ahead Log) 磁盤操作

這個步驟基本上各個數(shù)據(jù)庫都有，有各種各樣的叫法。比如說Innodb的Redo log，Cassandra 的Commit logs。但是，作用都是一樣的，在數(shù)據(jù)庫宕機之后，這份日志可以保證數(shù)據(jù)的恢復(fù)。而這個日志，都是以順序?qū)懭氲姆绞讲粩嘧芳?。所以，感覺上，這部分開銷應(yīng)該是非常的接近的。

我覺得MYSQL的BINLOG也可以放在這里提一下，從嚴(yán)格意義上來說，BINLOG不屬于存儲引擎而是屬于MYSQL，它與B-TREE這個存儲結(jié)構(gòu)沒有必然關(guān)系。功能上來看，我覺得它有點接近某些數(shù)據(jù)庫的歸檔日志。它開銷是顯然有的，但是我覺得應(yīng)該把這筆賬算在高可用的頭上去。

STEP 2 樹數(shù)據(jù)結(jié)構(gòu)維護

有觀點說B-TREE至少要寫兩次，一次是寫WAL日志，一次是寫B(tài)-TREE本身，以此推出B-TREE寫入比LSM-TREE更加慢。這個說法我覺得有些歧義的。因為LSM-TREE其實也是寫兩次，也是一次寫WAL，一次寫樹。如果非要說，LSM-TREE能少一次，除非是某種LSM-TREE數(shù)據(jù)庫在WAL寫完即認(rèn)為寫入成功返回，不需要等MemTable維護好，而這就意味著這種數(shù)據(jù)庫存在以提交的數(shù)據(jù)讀不到的情況。

我個人覺得比較精準(zhǔn)的說法應(yīng)該是，LSM-TREE中MemTable的追加寫入速度，要比B樹的維護快得多。首先無論是哪種樹，寫樹本身是個內(nèi)存操作，兩種結(jié)構(gòu)都不需要等樹結(jié)構(gòu)落盤數(shù)據(jù)庫才算Commit成功。數(shù)據(jù)庫臟頁通常都是異步進(jìn)程慢慢刷出的。所以單純的寫樹動作并不是關(guān)鍵。但是，B-TREE的寫樹動作，并非一個純粹內(nèi)存操作。因為只要從根節(jié)點開始，一直到數(shù)據(jù)頁。B-TREE這一條路上，無論是索引頁還是數(shù)據(jù)頁，有任何頁不在緩存里，數(shù)據(jù)庫都會觸發(fā)磁盤IO來讀取。所以在一般的寫入場景下，B樹的維護就慢了，它是一個先讀后寫的過程。

我們可以比對一下，在Cassandra的寫入步驟里面，資料上的描述，僅有ADD TO MEMTABLE這么簡單來描述。首先，它體現(xiàn)了這條數(shù)據(jù)是順序的追加上去的簡單性。如果說還要干點啥，就只剩下一句，如果在ROW CACHES里存在，廢棄存在的數(shù)據(jù)。對于LSM-TREE而言，MemTable寫完，交易就應(yīng)該是成功返回了。并且這些全都是內(nèi)存操作。

然后我們隨便來看看B樹在這個階段的維護都做了什么：

1）寫Undo日志，內(nèi)存操作，一般只有Undo空間不夠才寫盤。

2）從索引根節(jié)點開始，找到記錄行應(yīng)該存儲的數(shù)據(jù)頁，內(nèi)存加磁盤操作。若為命中緩存，則可能促發(fā)多次磁盤IO。

3）可能B-TREE索引分裂，一大波內(nèi)存加磁盤操作。

突然感覺有點什么不對勁對不對，首先追加寫入MemTable顯然是做不了約束性檢查的，如果你的應(yīng)用想寫入重KEY回滾，那么在LSM-TREE的寫入這里擋不住。那么你需要，那么它需要以另一種方式實現(xiàn)，比如說：讀后寫。那這時候的時間，其實有點近似與UPDATE的操作。

這個地方顯然需要兩分的來看待LSM-TREE的優(yōu)勢。不需要約束性檢查的超大規(guī)模寫入場景有沒有？當(dāng)然有，而且還很多。比如一個專門寫入流水的數(shù)據(jù)表。在互聯(lián)網(wǎng)特別常見的記錄PV數(shù)據(jù)的表，只要有人點了某個頁面，就等于一條記錄。不需要約束，不需要事務(wù)。這樣的場景，這樣的系統(tǒng)，用LSM-TREE自然快得飛起。

然而，如果你的系統(tǒng)，幾乎每個寫入都要判定是不是重主鍵、重唯一索引的話。那么這個寫入優(yōu)勢顯然是有限的。

STEP 3 臟數(shù)據(jù)落盤 磁盤操作

由于這部分操作都是異步執(zhí)行，只要機器資源沒有問題的話，通常已經(jīng)不太影響交易響應(yīng)時間了。所以，這里的性能差別不是我想說的重點。我想說一些虛無縹緲的，想法。剛才說的這個臟頁落盤異步，其實是很多數(shù)據(jù)庫性能優(yōu)化的一個空間。很多數(shù)據(jù)庫的優(yōu)化思路都在基于這一點去展開。比如說INNODB的DOUBLE-WRITE，Merge Insert Buffer等等。這些優(yōu)化的核心思想都圍繞著落盤可以異步，如何減少磁盤交互而展開。在看到這個地方的時候，不知道有沒有隱隱約約的感受到，數(shù)據(jù)庫的千差萬別之中，總是存在著某些相似的地方。所以，接下來，我準(zhǔn)備一邊聊數(shù)據(jù)庫的更新（UPDATE）操作，一邊說一說這一條隱約的線索。

四、關(guān)于存儲結(jié)構(gòu)的思考

在其他枯燥的知識點對比介紹之間呢，讓我們先亂入一波。

在我沒有學(xué)過LSM-TREE之前，在B樹還是我腦子里，唯一占統(tǒng)治地位的存儲結(jié)構(gòu)的少年時代。我一直有一個潛在的觀念，即“數(shù)據(jù)庫的存儲結(jié)構(gòu)是為數(shù)據(jù)查詢服務(wù)的”。如果非要說的不那么武斷，也至少是主要為查詢服務(wù)的。比如說，最常見的索引吧。我們建立一個索引，損耗插入時索引維護的成本，使用額外磁盤空間。為啥？顯然是為了加快查詢。再比如說“聚簇”。維持?jǐn)?shù)據(jù)庫中數(shù)據(jù)某種維度的順序，為啥？顯然還是為了某種查詢。再往比如說列存儲，為了分析型SQL在計算過程中，減少無關(guān)列的讀取，還是為了查詢吧。這些概念沒有一個是為了數(shù)據(jù)寫入服務(wù)的吧。

正如上面所描述的，當(dāng)我接觸了LSM-TREE的存儲結(jié)構(gòu)之后，我有一個特別深刻而直觀的印象，這個“數(shù)據(jù)庫的存儲結(jié)構(gòu)是為數(shù)據(jù)寫入服務(wù)的”。它和B樹有根源性的不同，B樹的存儲結(jié)構(gòu)，處處損耗寫入的性能來提高查詢性能。而LSM-TREE在提高寫入性能，并且可能在某些時候損耗了讀取的性能。

容我大膽的在這里丟一個問題和一個猜想。

問題：為什么數(shù)據(jù)庫的發(fā)展歷史中，是先有B樹而后有LSM樹？只是偶然的巧合嗎？

猜想：在古老的數(shù)據(jù)庫使用場景時，絕大部分?jǐn)?shù)據(jù)產(chǎn)生的是比較慢的，這些數(shù)據(jù)變化也比較慢，但是他們反反復(fù)復(fù)的被使用和讀取。于是，數(shù)據(jù)庫使用了B樹的存儲結(jié)構(gòu)。后來，隨著時間的變遷。有些新興的應(yīng)用場景數(shù)據(jù)產(chǎn)生的速度，大幅度的加快了，數(shù)據(jù)的更新速度也加快了。甚至于出現(xiàn)了超大量的數(shù)據(jù)產(chǎn)生，但是這些數(shù)據(jù)快速的產(chǎn)生出來，但是被反復(fù)讀取的使用的次數(shù)大幅度減少了，于是LSM樹出現(xiàn)了。

為什么要寫這個猜測？因為，如果我的猜想是對的，那么就是時候反問一句，你的數(shù)據(jù)庫系統(tǒng)哪一種？你系統(tǒng)的數(shù)據(jù)是相對穩(wěn)定的還是快速膨脹的？你系統(tǒng)的數(shù)據(jù)是反復(fù)讀取嗎？那么你感覺它更適合哪種存儲引擎呢？

先別感覺豁然開朗，故事當(dāng)然沒有這么簡單，選擇也當(dāng)然沒有這么容易。注意，我描述LSM-TREE用的詞匯是“可能”在某些時候損耗了讀取性能。這個地方有破綻的點起碼有兩條。第一，既然是可能，那有沒有什么情況沒有損耗。那就變成，用LSM-TREE我的系統(tǒng)可能寫入變快了，讀取沒變慢。第二個大破綻是，這個損耗沒有量化。不同的系統(tǒng)對于損耗的容忍程度天差地別。有的項目一個交易慢幾毫秒都會被人盯著追殺，而有的場景SQL語句跑個幾秒幾十秒都不叫事。

所以，要做出更準(zhǔn)確的選擇，我們還需要把自己系統(tǒng)的實際情況往里帶入并量化差異。最佳的選擇當(dāng)然是實測。因為它優(yōu)勢的地方你的系統(tǒng)不一定優(yōu)勢，它劣勢的地方你的系統(tǒng)也不一定就劣勢，就是這么神奇。

五、寫流程的衍生-更新動作

回到前面介紹寫流程的主線上來。數(shù)據(jù)庫的增刪改查，并稱數(shù)據(jù)庫的四大操作。但是我覺得把UPDATE當(dāng)作是寫流程的某種衍生是合適的。我們前面講了，在B樹數(shù)據(jù)寫入維護B樹的過程，其實是一個先讀后寫的過程。如果我們把INSERT一條記錄，看成是要更新這條記錄所在的數(shù)據(jù)頁的內(nèi)容。假設(shè)空間夠用，也沒有分裂等等，那INSERT和UPDATE動作可不就是一個流程嗎？

另一方面，你會發(fā)現(xiàn)我在描述LSM-TREE寫優(yōu)的反例竟然用的是約束性檢查，而并沒有用UPDATE操作來反例讀后寫。因為純粹的LSM-TREE的UPDATE更加是一個純純的INSERT動作，不存在半點讀后寫。來看一下引用于2020年VLDB論文《LSM-based Storage Techniques:A survey》中的描述和圖。

“通常，索引結(jié)構(gòu)可以選擇兩種策略之一種來處理更新，即就地（in-place）更新和非就地（即異位，out-of-place）更新。就地更新結(jié)構(gòu)，如B+樹，直接覆蓋舊記錄來存儲新更新。例如，在圖1a中，為了將key k1的值從v1更新到v4，索引條目(k1, v1)被直接修改以應(yīng)用該更新。這些結(jié)構(gòu)通常是讀優(yōu)化的，因為只存儲每個記錄的最新版本。然而，這種設(shè)計犧牲了寫性能，因為更新會導(dǎo)致隨機I/O。此外，索引頁可以被更新和刪除所分割，從而減少空間利用率。

相反，異位（out-of-place）的更新結(jié)構(gòu)，例如LSM-tree總是將更新存儲到新的位置，而不是覆蓋舊的條目。例如在圖1b中，更新(k1, v4)被存儲到一個新的位置，而不是直接更新舊的條目(k1, v1)。這種設(shè)計提高了寫性能，因為它可以利用順序I/O來處理寫。它還可以通過不覆蓋舊數(shù)據(jù)來簡化恢復(fù)過程。然而，這種設(shè)計的主要問題是犧牲了讀取性能，因為記錄可能存儲在多個位置中的任何一個。此外，這些結(jié)構(gòu)通常需要一個獨立的數(shù)據(jù)重組過程，以不斷提高存儲和查詢效率。順序的、異位的更新并不是新的想法；自20世紀(jì)70年代以來，它已成功地應(yīng)用于數(shù)據(jù)庫系統(tǒng)。”

可以看出LSM-TREE的異位（OUT-OF-PLACE）更新結(jié)構(gòu)，壓根就不是讀后寫，它就是一個INSERT動作。那這樣子來看，是不是感覺把更新動作當(dāng)作是一個寫流程的衍生物，無論是對于B-TREE而言，還是LSM-TREE而言，基本上是沒有什么違和感的。

然而，在這一堆反反復(fù)復(fù)的文字中，你可能已經(jīng)建立起一個LSM-TREE讀取性能被犧牲的概念，并且可能認(rèn)為讀取性能不佳，可能會是阻礙你的系統(tǒng)選取LSM-TREE的重要障礙。因為，哪怕你就是簡簡單單的看最前面那個彩圖，也能知道，你的一條記錄可能要讀好幾個文件才能得到，從而質(zhì)疑它的讀取性能。

如果你內(nèi)心敏感，你也許能從我舉得例子中察覺到另一朵重要的烏云。這個烏云是資源的沖突。LSM-TREE的寫優(yōu)勢根源是，用追加寫取代讀后寫。如果，你的系統(tǒng)有任何主要的場景，避免不掉讀后寫。那這個優(yōu)勢的根基便被動搖了。約束性檢查，是最容易想到的場景之一，因為不讀，就不能確定能不能寫。繼而，我們很容易的想到另一個重要更新場景，悲觀鎖和事務(wù)。為啥？長期的B-TREE經(jīng)驗告訴我們，SELECT FOR UPDATE，得先SELECT才能上鎖FOR UPDATE。那不然我異位INSERT的時候，我去哪檢查這條記錄有沒有鎖呢？我怎么確定我INSERT的時候，別人不能INSERT呢？那這一部分內(nèi)容，我們放在后面的章節(jié)里再去展開。先把基本的動作來看完。

六、B-TREE之優(yōu)勢的讀

再看一下這個圖：

數(shù)據(jù)讀取，數(shù)據(jù)庫通常視為最最主要的能力。就像我前面說的，有一段時間我都一直覺得，數(shù)據(jù)如何寫，如何擺放最終都是為了讀起來方便。從圖上看的感覺總是直觀的，前面提到了，很多人眼看著LSM-TREE那張圖讀取動作出現(xiàn)了5條讀取線，得出了LSM-TREE讀取性能不行的結(jié)論（很顯然，我初看這張圖，也是這么認(rèn)為的）。當(dāng)然，讀多次，性能是不是受損，那肯定是受損的。損得大不大？那就不好說了。

在來來回回看這張圖之后，我不再緊盯那五根線，而是開始細(xì)細(xì)的觀察Level 1開始往下的這些SSTABLE文件。這些文件由異步的Compaction操作產(chǎn)生。這個動作有很多文檔都把它翻譯成數(shù)據(jù)壓縮，我覺得這很容易和數(shù)據(jù)庫的DATA COMPRESS概念混淆。我更喜歡把它譯為數(shù)據(jù)整理。我們看看它做了什么，去重多版本數(shù)據(jù)、刪除多余的老數(shù)據(jù)、數(shù)據(jù)按KEY排序。沒錯，它竟然是排序的。如果說SSTABLE的文件頭里面，標(biāo)上了起止的KEY，它像不像一個小小的B樹呢？還記得我在前面說那個隱隱約約的線索嗎？數(shù)據(jù)庫總是把一些異步操作，作為一些優(yōu)化的空間。LSM-TREE的Compaction就絕不是僅僅為了防止數(shù)據(jù)量不斷增長而設(shè)計的清理機制。它的存在還有更重要的意義。LSM-TREE其實并沒有自暴自棄的在優(yōu)化寫入的時候就放棄查詢。其實它遵循了我們之前那個現(xiàn)索，數(shù)據(jù)庫在異步的流程中，暗暗的優(yōu)化數(shù)據(jù)查詢時的速度。

我們來接著填一下前面的坑。如果說，相比B樹而言，LSM-TREE的讀取總是很慢的。是不是數(shù)據(jù)相對穩(wěn)定的系統(tǒng)就不能選LSM-TREE嗎？如果，我們的數(shù)據(jù)一次INSERT之后，就沒不動了，那會是什么情況？我們來細(xì)細(xì)的推敲一下，首先必然的，LSM-TREE寫優(yōu)勢用不上不對，因為你就不怎么寫嘛？但是讀的真的就慢嗎？我們來看看，首先，我們在內(nèi)存里找到了這條記錄，CACHE命中了，或者M(jìn)EMTABLE里有最新的數(shù)據(jù)，都沒有磁盤IO，那妥妥的快。假設(shè)沒命中，那么只做個一次INSERT的記錄，可能出現(xiàn)幾層的幾個SSTABLE里面？好像只有一個吧。當(dāng)然，這里會有一個疑惑，就是我沒讀這個SSTABLE，我怎么知道里面有沒有這條記錄？在我印象中，通常SSTABLE的數(shù)據(jù)文件，通常都要配一個BLOOM過濾器，來告訴你這條KEY它有沒有來解決這件事情。誒，這時候，再來整理整理感覺，是不是上面那兩根內(nèi)存里的線，還挺快的。下面指到磁盤上的三根線，好像也沒有三根線也就只有一根，剩下這一根，感覺還和B-TREE有那么一點點的像，搞不好在這一個SSTABLE里面，拿得還比B-TREE快。

好啦，這個例子其實有點過，我并不是要證明LSM-TREE的讀取性能要比B-TREE好，這是不可能的。我只是想再提醒前面那個觀點，它優(yōu)勢的地方你的系統(tǒng)不一定優(yōu)勢，它劣勢的地方你的系統(tǒng)也不一定就劣勢，就是這么神奇。比如我還常常被問到類似的問題，我的系統(tǒng)以更新為主，SSTABLE的線特別多是不是不能選LSM-TREE？那也不一定啊，如果你平時查都不查，那讀取有一百根線對你的系統(tǒng)性能又有什么影響呢？那我的系統(tǒng)又改得多又查得多，又不是以寫入為主呢？對的，它不適合，因為SSTABLE的讀取線很多，而且它的寫優(yōu)勢又發(fā)揮不出來。所以無論如何，你還是得把自己系統(tǒng)的場景往里面帶一帶，不要憑看圖的直覺。

LSM-TREE的讀取性能或許確實的受損的。但是顯而易見的是，對于很多時候，這種受損是可以通過各種各樣的手段優(yōu)化、緩解。使得這種受損處于可接受的范圍，不然LSM-TREE是怎么越來越火的呢？對吧。

而B樹的讀取方面，我覺得這里就不太需要再展開來討論了，因為前面在說明它寫的時候，其實也是要先完成讀取流程的，再者B樹大家也相對而言比較熟悉。

七、資源的沖突-數(shù)據(jù)鎖

接下來，是時候來講一講這一朵烏云了。資源沖突問題，一直以來都在數(shù)據(jù)庫的重要困難點附近出沒。而且，沖突問題又和分布式的問題互相之間有一些糾纏。舉個例子，在數(shù)據(jù)庫單機架構(gòu)往SHARE DISK的架構(gòu)演變過程中，它就一度成為了很多數(shù)據(jù)庫廠商搞不定的難點。比如，我在集群中的某一個數(shù)據(jù)庫實例上，上鎖并修改了數(shù)據(jù)。這個鎖和修改信息，就需要立刻在內(nèi)存中，直接通訊給其他的數(shù)據(jù)庫實例。最后比較成熟的方案只有幾個少數(shù)像ORACLE 的RAC，DB2的DATA SHARING這樣的能夠解決。這個例子特別清楚的能體現(xiàn)，資源沖突處理，要么要集中處理，要么需要特別靠譜的互相通信，這個通訊在分布式水平擴展的情況下會有所放大。所以，有一些SHARE NOTHING的數(shù)據(jù)庫產(chǎn)品，會選擇在數(shù)據(jù)存儲節(jié)點，來集中處理數(shù)據(jù)的上鎖問題。

對于基于LSM-TREE的數(shù)據(jù)庫產(chǎn)品而言，有的產(chǎn)品選擇不支持鎖和事務(wù)，有的選擇通過其它巧妙的手段來解決。而我們還是可以顯著的看到，B-TREE結(jié)構(gòu)中，上鎖與不上鎖，也許只是內(nèi)存里面一個記錄標(biāo)志位的修改差別，上鎖與不上鎖的性能差別似乎并不是很大。但是LSM-TREE結(jié)構(gòu)的數(shù)據(jù)庫里，似乎很有必要把上鎖流程的開銷拿出來額外關(guān)注一下。因為如果數(shù)據(jù)庫做的是一般性先讀后寫，那么寫優(yōu)勢沒了。如果是別的沖突處理機制，那這部分顯然屬于額外開銷。

為什么不支持，竟然也可以算一個出路，我們可以往回退一步。資源沖突問題的源頭是并行的處理。而在沖突的資源點上，我們需要轉(zhuǎn)并行為串行，其實大致上我覺得可以分開成兩個問題來看，第一個解決時序問題，就是我們認(rèn)為后面的更新才是對的，第二個是解決并發(fā)過程中更新丟失和臟讀問題。像CASSANDRA這樣的數(shù)據(jù)，用時間戳來解決時序問題，即改更新為追加，并在數(shù)據(jù)讀取合并時，以最新時間戳的數(shù)據(jù)為準(zhǔn)。再利用時間戳來實現(xiàn)多版本的讀取。算是解決半個資源沖突的本源問題。所以對沒有第二部分問題的系統(tǒng)，這的確也是一個解決方案。

另外半個問題，就比較棘手，比如說錢的轉(zhuǎn)入轉(zhuǎn)出模型，有的轉(zhuǎn)入有的轉(zhuǎn)出，若錢不夠就不能夠轉(zhuǎn)出。

我們來看一個我覺得比較優(yōu)秀的基于LSM-TREE存儲結(jié)構(gòu)的 Percolator模型的實現(xiàn)方案。比A有10塊錢，B有2塊錢，A向B轉(zhuǎn)7塊錢。

首先，使用三個列簇（COLUMN FAILY）來存三樣?xùn)|西，一個是數(shù)據(jù)本身，一個是鎖信息，一個是寫入的版本。要有一個時間戳和一個版本號來解決時序問題，那么在PREWRITE階段，數(shù)據(jù)庫除了寫入數(shù)據(jù)之外，還要寫入LOCK信息。最后再提交階段，把LOCK信息干掉，再寫一個版本信息。

作為讀后寫替代，那么這種方案下的沖突解決能不能比B樹的維護代價更小一點。我們先看看，在理想LSM-TREE的UPDATE只有一個追加寫 MEMTABLE的操作上，又附加了什么。首先，我們看A記錄，一共寫了 三次，最后COMMIT結(jié)束之后，還需要把鎖信息干掉。草算一算，好像時間翻了四倍。再細(xì)細(xì)的看一下，寫數(shù)據(jù)和寫版本看起來應(yīng)該是可以追加寫的。但是，這個鎖信息可不就是一個妥妥的讀后寫嗎？因為對一條記錄上鎖之前，起碼得看看前面有沒有鎖吧。但是感覺上，這個鎖的CF應(yīng)該不大，應(yīng)該基本上都是內(nèi)存操作。

我們來細(xì)細(xì)推敲一下。普通更新的話，把A從版本5的10改為版本7的3。追加寫數(shù)據(jù)，追加寫版本，兩次內(nèi)存操作。檢查讀一次鎖，如果沒鎖，寫一次鎖，先算他是內(nèi)存操作。如果在B樹上，一般隨機轉(zhuǎn)賬命中概率不大，把A讀起來，那么有一波磁盤IO，再加同樣的內(nèi)存上鎖放鎖，感覺還是B樹不一定快。為啥，因為同樣是讀后寫，這個鎖CF信息的讀后寫很可能是內(nèi)存里沒有磁盤操作的。而B樹的讀后寫，那基本上磁盤IO跑不了的。在這樣的情況下，其實LSM基本上不落下風(fēng)的。

但是，程序可不一定是這么寫的。比如說，悲觀鎖。我相信很多時候，你很難把上面這個場景的SQL寫成，UPDATE TABLE SET YUAN=YUAN-7 WHERE KEY=A吧。比較常見的寫法不應(yīng)該是，SELECT YUAN FROM TABLE WHERE KEY=A FOR UPDATE。然后IF YUAN>=7 YUAN_NEW=YUAN-7。再然后UPDATE TABLE SET YUAN=YUAN_NEW WHERE KEY=A。

這中間出現(xiàn)了什么變化，響應(yīng)時間對比其實從單一的UPDATE對比變成了兩個SQL符合在一起的形態(tài)對比。首先，由于SELECT FOR UPDATE這個動作出現(xiàn)，磁盤讀變成了一個跑不掉的步驟。B樹上，記錄會在SELECT FOR UPDATE的時候就被IO到內(nèi)存里面來。這時候，你再看B樹的UPDATE，那就純粹是個內(nèi)存操作，那應(yīng)該不會比寫三個CF慢的。上鎖放鎖的內(nèi)存動作，我們姑且認(rèn)為二者差不多，那這個場景就變成純粹的比讀取。而且，考慮的有沖突和并發(fā)，表示這是一個頻繁變更數(shù)據(jù)的情況，那么我會猜測LSM-TREE讀取的SSTABLE的線比較多，最終直接成為影響系統(tǒng)性能的重要因素。

再稍微說一下分布式的疊加，如果A和B存在不同的節(jié)點里。B中的副鎖還要再跨網(wǎng)絡(luò)去訪問A節(jié)點的主鎖有沒有釋放。感覺也是有一些跟硬件相關(guān)的開銷在里面。但應(yīng)該不是重點，因為類比我們前面說的，RAC各實例間也有基于網(wǎng)絡(luò)的鎖信息交互開銷。

八、高可用附加

其實這個內(nèi)容，跟存儲引擎的聯(lián)系有限，但是前面寫入的時候提到了BINLOG。MYSQL的BINLOG承擔(dān)了主備機同步的橋梁作用，但它對于很多重要系統(tǒng)來說都是必開的。最關(guān)鍵的是，再RPO=0的前提下，BINLOG的遠(yuǎn)程落盤，是COMMIT成功的必要條件。它的開銷對性能影響是必然的，寫B(tài)INLOG也幾乎寫流程中的一部分。不過我覺得它還是可以剝離出來看，因為它本質(zhì)并不是WAL日志。如果一定要對標(biāo)的話，我覺得它類似于RAFT LOG的寫入，這兩個東西都是圍繞著高可用和多節(jié)點數(shù)據(jù)復(fù)制展開的。對于寫入的性能開銷增加，似乎也是差不多的。

九、結(jié)尾

終于把這個坑稍微填了一填，感覺說了好多，又感覺好多內(nèi)容沒有說。想必以我的認(rèn)知力，也并沒有能力把所有的內(nèi)容說的很全?；旧习褜嵺`中，遇到過、顧慮過的一些我覺得的關(guān)鍵點整理了一下吧，也算可以給需要的朋友提供個參考。另外，從文中想必也能看得出來，有些內(nèi)容基本我全憑猜測，未必準(zhǔn)確，也期待有大佬看到并幫我指出其中的錯漏。

作者介紹

宇文湛泉，現(xiàn)任金融行業(yè)核心業(yè)務(wù)系統(tǒng)DBA，主要涉及Oracle、DB2、Cassandra、MySQL、GoldenDB、TiDB等數(shù)據(jù)庫開發(fā)工作。