建站
咨詢
售后
建站咨詢
新聞中心
一、引子
最近一兩年里，每次做分布式數(shù)據(jù)庫(kù)的內(nèi)容分享活動(dòng)時(shí)，總是會(huì)提及現(xiàn)在數(shù)據(jù)庫(kù)的兩個(gè)重要的存儲(chǔ)結(jié)構(gòu)，B-TREE和LSM-TREE。因?yàn)?，我覺(jué)得作為數(shù)據(jù)庫(kù)的存儲(chǔ)根基，無(wú)論是要選型，或者是用好一個(gè)數(shù)據(jù)庫(kù)，清楚這兩的差別和各自特點(diǎn)，都特別重要。但是幾乎每一次都只能提一下，哪種數(shù)據(jù)庫(kù)用了哪個(gè)存儲(chǔ)。再多就是稍微介紹LSM-TREE的寫(xiě)入友好。對(duì)于有些朋友，正面臨二選一項(xiàng)目抉擇時(shí)，這點(diǎn)信息顯然是不夠的。于是他們會(huì)想要知道，更多二者差異細(xì)節(jié)，以及到底哪一種適合自己的系統(tǒng)?？上铱偸侵荒苓z憾講個(gè)大概，并解釋要徹底講清楚的話，整個(gè)分享就只能光講這個(gè)可能時(shí)間還不太夠。然而，我還是覺(jué)得每次都含含糊糊的過(guò)去，未免也有點(diǎn)耍流氓的感覺(jué)?？偟谜覀€(gè)機(jī)會(huì)，把這里面一些有意思的內(nèi)容拿出來(lái)羅列一下。適逢國(guó)慶宅家，想想也是時(shí)候把這個(gè)坑給填一填了。
創(chuàng)新互聯(lián)建站主營(yíng)臨漳網(wǎng)站建設(shè)的網(wǎng)絡(luò)公司,主營(yíng)網(wǎng)站建設(shè)方案,重慶APP開(kāi)發(fā)公司,臨漳h5重慶小程序開(kāi)發(fā)公司搭建,臨漳網(wǎng)站營(yíng)銷(xiāo)推廣歡迎臨漳等地區(qū)企業(yè)咨詢
當(dāng)然，本文并不打算從0開(kāi)始介紹LSM-TREE，那樣篇幅也太冗長(zhǎng)了。本文默認(rèn)各位讀者具有一點(diǎn)B-TREE和LSM-TREE的基礎(chǔ)背景知識(shí)。
二、背景板-分布式關(guān)系型數(shù)據(jù)庫(kù)
其實(shí)，拋開(kāi)分布式數(shù)據(jù)庫(kù)來(lái)純寫(xiě)這兩個(gè)存儲(chǔ)引擎，似乎要更加簡(jiǎn)明一點(diǎn)。但是，這樣的話實(shí)用性不太行。單機(jī)版LSM-TREE數(shù)據(jù)庫(kù)有排名在100名左右的ROCKSDB，LEVELDB。它們被劃分為KEY-VALUE類(lèi)型，而且它們通常不會(huì)直接出現(xiàn)在我們的視野，也極少直接被使用在項(xiàng)目中。然而，基于LSM-TREE的分布式數(shù)據(jù)庫(kù)則是非常常見(jiàn)的，比如這些：
甚至可能有些人，是有用分布式數(shù)據(jù)庫(kù)的需求，才去學(xué)習(xí)和理解LSM-TREE的（比如說(shuō)我就是先要使用CASSANDRA）。不過(guò)帶上分布式的這個(gè)背景，未免多少會(huì)使得存儲(chǔ)結(jié)構(gòu)差異比對(duì)，變得不那么純粹。因?yàn)榉植际綌?shù)據(jù)庫(kù)嘛，總是帶來(lái)了一些額外的開(kāi)銷(xiāo)。比如說(shuō)數(shù)據(jù)庫(kù)層面的SQL解析到分布式執(zhí)行計(jì)劃產(chǎn)生。再比如說(shuō)分布式的場(chǎng)景下，分布式事務(wù)、全局時(shí)間戳獲取等等。不過(guò)這個(gè)還是可以大致對(duì)比一下基于B樹(shù)的分布式數(shù)據(jù)庫(kù)情況來(lái)說(shuō)明一下。但就具體到每一個(gè)數(shù)據(jù)庫(kù)的話，因?yàn)楦鱾€(gè)數(shù)據(jù)庫(kù)的具體實(shí)現(xiàn)方式各有不同，實(shí)際情況就得看某一個(gè)具體的數(shù)據(jù)庫(kù)還做了些什么額外的動(dòng)作，再把它附加上去。
還有關(guān)系型也算是一個(gè)重要背景。因?yàn)橛行┨厥忭?xiàng)目場(chǎng)景、特殊的數(shù)據(jù)格式，使用某種數(shù)據(jù)庫(kù)或者存儲(chǔ)結(jié)構(gòu)時(shí)快得飛起，然而卻缺乏了一般通用性。其實(shí)，像REDIS和CASSANDRA這樣的數(shù)據(jù)庫(kù)已經(jīng)非常的熱門(mén)，使用范圍也非常的廣。但是我們?cè)陧?xiàng)目中使用這些數(shù)據(jù)庫(kù)，也還是充當(dāng)某種功能性的角色比較多，我們很難把它做成系統(tǒng)的主數(shù)據(jù)庫(kù)。尤其是那些有歷史包袱遷移而來(lái)的系統(tǒng)。無(wú)論如何，關(guān)系型模型，基本上還是我們見(jiàn)到的主要情況。
所以我準(zhǔn)備在分布式和關(guān)系型的數(shù)據(jù)庫(kù)大背景下，以最為常見(jiàn)的幾種數(shù)據(jù)訪問(wèn)形態(tài)來(lái)描述一下，這樣就更加具有真實(shí)的參考性價(jià)值。先攤開(kāi)來(lái)數(shù)據(jù)庫(kù)的主要操作都做了些什么。然后再套幾個(gè)經(jīng)典的案例場(chǎng)景進(jìn)去看看。這樣子的話，圍繞著分布式關(guān)系型數(shù)據(jù)庫(kù)來(lái)展開(kāi)這兩顆樹(shù)的內(nèi)容，也就更貼近大家現(xiàn)實(shí)使用這兩存儲(chǔ)結(jié)構(gòu)的實(shí)際需求，起碼我感覺(jué)上是如此。
在開(kāi)始眼花繚亂的各種操作敘述之前，我們可以先草率的做一點(diǎn)假定。比如說(shuō)，我們SQL的響應(yīng)時(shí)長(zhǎng)，認(rèn)為是最關(guān)鍵的性能指標(biāo)。比如說(shuō)，我們認(rèn)為內(nèi)存中的操作比較快，對(duì)性能的影響稍微小一些。而磁盤(pán)操作比較慢，比較可能影響交易時(shí)長(zhǎng)。再比如，異步動(dòng)作，基本不怎么影響交易性能。這些假定雖然草率，但是我認(rèn)為這可以使我們對(duì)一些數(shù)據(jù)庫(kù)操作的性能開(kāi)銷(xiāo)，有一些更粗暴而直觀的感性認(rèn)知。
三、LSM-TREE之優(yōu)勢(shì)的寫(xiě)
寫(xiě)友好，幾乎是LSM-TREE的標(biāo)志性特點(diǎn)，那么我們就從寫(xiě)流程開(kāi)始。先來(lái)個(gè)經(jīng)典的LSM-TREE的圖。
STEP 1 WAL日志寫(xiě)入(Write Ahead Log) 磁盤(pán)操作
這個(gè)步驟基本上各個(gè)數(shù)據(jù)庫(kù)都有，有各種各樣的叫法。比如說(shuō)Innodb的Redo log，Cassandra 的Commit logs。但是，作用都是一樣的，在數(shù)據(jù)庫(kù)宕機(jī)之后，這份日志可以保證數(shù)據(jù)的恢復(fù)。而這個(gè)日志，都是以順序?qū)懭氲姆绞讲粩嘧芳?。所以，感覺(jué)上，這部分開(kāi)銷(xiāo)應(yīng)該是非常的接近的。
我覺(jué)得MYSQL的BINLOG也可以放在這里提一下，從嚴(yán)格意義上來(lái)說(shuō)，BINLOG不屬于存儲(chǔ)引擎而是屬于MYSQL，它與B-TREE這個(gè)存儲(chǔ)結(jié)構(gòu)沒(méi)有必然關(guān)系。功能上來(lái)看，我覺(jué)得它有點(diǎn)接近某些數(shù)據(jù)庫(kù)的歸檔日志。它開(kāi)銷(xiāo)是顯然有的，但是我覺(jué)得應(yīng)該把這筆賬算在高可用的頭上去。
STEP 2 樹(shù)數(shù)據(jù)結(jié)構(gòu)維護(hù)
有觀點(diǎn)說(shuō)B-TREE至少要寫(xiě)兩次，一次是寫(xiě)WAL日志，一次是寫(xiě)B(tài)-TREE本身，以此推出B-TREE寫(xiě)入比LSM-TREE更加慢。這個(gè)說(shuō)法我覺(jué)得有些歧義的。因?yàn)長(zhǎng)SM-TREE其實(shí)也是寫(xiě)兩次，也是一次寫(xiě)WAL，一次寫(xiě)樹(shù)。如果非要說(shuō)，LSM-TREE能少一次，除非是某種LSM-TREE數(shù)據(jù)庫(kù)在WAL寫(xiě)完即認(rèn)為寫(xiě)入成功返回，不需要等MemTable維護(hù)好，而這就意味著這種數(shù)據(jù)庫(kù)存在以提交的數(shù)據(jù)讀不到的情況。
我個(gè)人覺(jué)得比較精準(zhǔn)的說(shuō)法應(yīng)該是，LSM-TREE中MemTable的追加寫(xiě)入速度，要比B樹(shù)的維護(hù)快得多。首先無(wú)論是哪種樹(shù)，寫(xiě)樹(shù)本身是個(gè)內(nèi)存操作，兩種結(jié)構(gòu)都不需要等樹(shù)結(jié)構(gòu)落盤(pán)數(shù)據(jù)庫(kù)才算Commit成功。數(shù)據(jù)庫(kù)臟頁(yè)通常都是異步進(jìn)程慢慢刷出的。所以單純的寫(xiě)樹(shù)動(dòng)作并不是關(guān)鍵。但是，B-TREE的寫(xiě)樹(shù)動(dòng)作，并非一個(gè)純粹內(nèi)存操作。因?yàn)橹灰獜母?jié)點(diǎn)開(kāi)始，一直到數(shù)據(jù)頁(yè)。B-TREE這一條路上，無(wú)論是索引頁(yè)還是數(shù)據(jù)頁(yè)，有任何頁(yè)不在緩存里，數(shù)據(jù)庫(kù)都會(huì)觸發(fā)磁盤(pán)IO來(lái)讀取。所以在一般的寫(xiě)入場(chǎng)景下，B樹(shù)的維護(hù)就慢了，它是一個(gè)先讀后寫(xiě)的過(guò)程。
我們可以比對(duì)一下，在Cassandra的寫(xiě)入步驟里面，資料上的描述，僅有ADD TO MEMTABLE這么簡(jiǎn)單來(lái)描述。首先，它體現(xiàn)了這條數(shù)據(jù)是順序的追加上去的簡(jiǎn)單性。如果說(shuō)還要干點(diǎn)啥，就只剩下一句，如果在ROW CACHES里存在，廢棄存在的數(shù)據(jù)。對(duì)于LSM-TREE而言，MemTable寫(xiě)完，交易就應(yīng)該是成功返回了。并且這些全都是內(nèi)存操作。
然后我們隨便來(lái)看看B樹(shù)在這個(gè)階段的維護(hù)都做了什么：
1）寫(xiě)Undo日志，內(nèi)存操作，一般只有Undo空間不夠才寫(xiě)盤(pán)。
2）從索引根節(jié)點(diǎn)開(kāi)始，找到記錄行應(yīng)該存儲(chǔ)的數(shù)據(jù)頁(yè)，內(nèi)存加磁盤(pán)操作。若為命中緩存，則可能促發(fā)多次磁盤(pán)IO。
3）可能B-TREE索引分裂，一大波內(nèi)存加磁盤(pán)操作。
突然感覺(jué)有點(diǎn)什么不對(duì)勁對(duì)不對(duì)，首先追加寫(xiě)入MemTable顯然是做不了約束性檢查的，如果你的應(yīng)用想寫(xiě)入重KEY回滾，那么在LSM-TREE的寫(xiě)入這里擋不住。那么你需要，那么它需要以另一種方式實(shí)現(xiàn)，比如說(shuō)：讀后寫(xiě)。那這時(shí)候的時(shí)間，其實(shí)有點(diǎn)近似與UPDATE的操作。
這個(gè)地方顯然需要兩分的來(lái)看待LSM-TREE的優(yōu)勢(shì)。不需要約束性檢查的超大規(guī)模寫(xiě)入場(chǎng)景有沒(méi)有？當(dāng)然有，而且還很多。比如一個(gè)專(zhuān)門(mén)寫(xiě)入流水的數(shù)據(jù)表。在互聯(lián)網(wǎng)特別常見(jiàn)的記錄PV數(shù)據(jù)的表，只要有人點(diǎn)了某個(gè)頁(yè)面，就等于一條記錄。不需要約束，不需要事務(wù)。這樣的場(chǎng)景，這樣的系統(tǒng)，用LSM-TREE自然快得飛起。
然而，如果你的系統(tǒng)，幾乎每個(gè)寫(xiě)入都要判定是不是重主鍵、重唯一索引的話。那么這個(gè)寫(xiě)入優(yōu)勢(shì)顯然是有限的。
STEP 3 臟數(shù)據(jù)落盤(pán) 磁盤(pán)操作
由于這部分操作都是異步執(zhí)行，只要機(jī)器資源沒(méi)有問(wèn)題的話，通常已經(jīng)不太影響交易響應(yīng)時(shí)間了。所以，這里的性能差別不是我想說(shuō)的重點(diǎn)。我想說(shuō)一些虛無(wú)縹緲的，想法。剛才說(shuō)的這個(gè)臟頁(yè)落盤(pán)異步，其實(shí)是很多數(shù)據(jù)庫(kù)性能優(yōu)化的一個(gè)空間。很多數(shù)據(jù)庫(kù)的優(yōu)化思路都在基于這一點(diǎn)去展開(kāi)。比如說(shuō)INNODB的DOUBLE-WRITE，Merge Insert Buffer等等。這些優(yōu)化的核心思想都圍繞著落盤(pán)可以異步，如何減少磁盤(pán)交互而展開(kāi)。在看到這個(gè)地方的時(shí)候，不知道有沒(méi)有隱隱約約的感受到，數(shù)據(jù)庫(kù)的千差萬(wàn)別之中，總是存在著某些相似的地方。所以，接下來(lái)，我準(zhǔn)備一邊聊數(shù)據(jù)庫(kù)的更新（UPDATE）操作，一邊說(shuō)一說(shuō)這一條隱約的線索。
四、關(guān)于存儲(chǔ)結(jié)構(gòu)的思考
在其他枯燥的知識(shí)點(diǎn)對(duì)比介紹之間呢，讓我們先亂入一波。
在我沒(méi)有學(xué)過(guò)LSM-TREE之前，在B樹(shù)還是我腦子里，唯一占統(tǒng)治地位的存儲(chǔ)結(jié)構(gòu)的少年時(shí)代。我一直有一個(gè)潛在的觀念，即“數(shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu)是為數(shù)據(jù)查詢服務(wù)的”。如果非要說(shuō)的不那么武斷，也至少是主要為查詢服務(wù)的。比如說(shuō)，最常見(jiàn)的索引吧。我們建立一個(gè)索引，損耗插入時(shí)索引維護(hù)的成本，使用額外磁盤(pán)空間。為啥？顯然是為了加快查詢。再比如說(shuō)“聚簇”。維持?jǐn)?shù)據(jù)庫(kù)中數(shù)據(jù)某種維度的順序，為啥？顯然還是為了某種查詢。再往比如說(shuō)列存儲(chǔ)，為了分析型SQL在計(jì)算過(guò)程中，減少無(wú)關(guān)列的讀取，還是為了查詢吧。這些概念沒(méi)有一個(gè)是為了數(shù)據(jù)寫(xiě)入服務(wù)的吧。
正如上面所描述的，當(dāng)我接觸了LSM-TREE的存儲(chǔ)結(jié)構(gòu)之后，我有一個(gè)特別深刻而直觀的印象，這個(gè)“數(shù)據(jù)庫(kù)的存儲(chǔ)結(jié)構(gòu)是為數(shù)據(jù)寫(xiě)入服務(wù)的”。它和B樹(shù)有根源性的不同，B樹(shù)的存儲(chǔ)結(jié)構(gòu)，處處損耗寫(xiě)入的性能來(lái)提高查詢性能。而LSM-TREE在提高寫(xiě)入性能，并且可能在某些時(shí)候損耗了讀取的性能。
容我大膽的在這里丟一個(gè)問(wèn)題和一個(gè)猜想。
問(wèn)題：為什么數(shù)據(jù)庫(kù)的發(fā)展歷史中，是先有B樹(shù)而后有LSM樹(shù)？只是偶然的巧合嗎？
猜想：在古老的數(shù)據(jù)庫(kù)使用場(chǎng)景時(shí)，絕大部分?jǐn)?shù)據(jù)產(chǎn)生的是比較慢的，這些數(shù)據(jù)變化也比較慢，但是他們反反復(fù)復(fù)的被使用和讀取。于是，數(shù)據(jù)庫(kù)使用了B樹(shù)的存儲(chǔ)結(jié)構(gòu)。后來(lái)，隨著時(shí)間的變遷。有些新興的應(yīng)用場(chǎng)景數(shù)據(jù)產(chǎn)生的速度，大幅度的加快了，數(shù)據(jù)的更新速度也加快了。甚至于出現(xiàn)了超大量的數(shù)據(jù)產(chǎn)生，但是這些數(shù)據(jù)快速的產(chǎn)生出來(lái)，但是被反復(fù)讀取的使用的次數(shù)大幅度減少了，于是LSM樹(shù)出現(xiàn)了。
為什么要寫(xiě)這個(gè)猜測(cè)？因?yàn)?，如果我的猜想是?duì)的，那么就是時(shí)候反問(wèn)一句，你的數(shù)據(jù)庫(kù)系統(tǒng)哪一種？你系統(tǒng)的數(shù)據(jù)是相對(duì)穩(wěn)定的還是快速膨脹的？你系統(tǒng)的數(shù)據(jù)是反復(fù)讀取嗎？那么你感覺(jué)它更適合哪種存儲(chǔ)引擎呢？
先別感覺(jué)豁然開(kāi)朗，故事當(dāng)然沒(méi)有這么簡(jiǎn)單，選擇也當(dāng)然沒(méi)有這么容易。注意，我描述LSM-TREE用的詞匯是“可能”在某些時(shí)候損耗了讀取性能。這個(gè)地方有破綻的點(diǎn)起碼有兩條。第一，既然是可能，那有沒(méi)有什么情況沒(méi)有損耗。那就變成，用LSM-TREE我的系統(tǒng)可能寫(xiě)入變快了，讀取沒(méi)變慢。第二個(gè)大破綻是，這個(gè)損耗沒(méi)有量化。不同的系統(tǒng)對(duì)于損耗的容忍程度天差地別。有的項(xiàng)目一個(gè)交易慢幾毫秒都會(huì)被人盯著追殺，而有的場(chǎng)景SQL語(yǔ)句跑個(gè)幾秒幾十秒都不叫事。
所以，要做出更準(zhǔn)確的選擇，我們還需要把自己系統(tǒng)的實(shí)際情況往里帶入并量化差異。最佳的選擇當(dāng)然是實(shí)測(cè)。因?yàn)樗鼉?yōu)勢(shì)的地方你的系統(tǒng)不一定優(yōu)勢(shì)，它劣勢(shì)的地方你的系統(tǒng)也不一定就劣勢(shì)，就是這么神奇。
五、寫(xiě)流程的衍生-更新動(dòng)作
回到前面介紹寫(xiě)流程的主線上來(lái)。數(shù)據(jù)庫(kù)的增刪改查，并稱(chēng)數(shù)據(jù)庫(kù)的四大操作。但是我覺(jué)得把UPDATE當(dāng)作是寫(xiě)流程的某種衍生是合適的。我們前面講了，在B樹(shù)數(shù)據(jù)寫(xiě)入維護(hù)B樹(shù)的過(guò)程，其實(shí)是一個(gè)先讀后寫(xiě)的過(guò)程。如果我們把INSERT一條記錄，看成是要更新這條記錄所在的數(shù)據(jù)頁(yè)的內(nèi)容。假設(shè)空間夠用，也沒(méi)有分裂等等，那INSERT和UPDATE動(dòng)作可不就是一個(gè)流程嗎？
另一方面，你會(huì)發(fā)現(xiàn)我在描述LSM-TREE寫(xiě)優(yōu)的反例竟然用的是約束性檢查，而并沒(méi)有用UPDATE操作來(lái)反例讀后寫(xiě)。因?yàn)榧兇獾腖SM-TREE的UPDATE更加是一個(gè)純純的INSERT動(dòng)作，不存在半點(diǎn)讀后寫(xiě)。來(lái)看一下引用于2020年VLDB論文《LSM-based Storage Techniques:A survey》中的描述和圖。
“通常，索引結(jié)構(gòu)可以選擇兩種策略之一種來(lái)處理更新，即就地（in-place）更新和非就地（即異位，out-of-place）更新。就地更新結(jié)構(gòu)，如B+樹(shù)，直接覆蓋舊記錄來(lái)存儲(chǔ)新更新。例如，在圖1a中，為了將key k1的值從v1更新到v4，索引條目(k1, v1)被直接修改以應(yīng)用該更新。這些結(jié)構(gòu)通常是讀優(yōu)化的，因?yàn)橹淮鎯?chǔ)每個(gè)記錄的最新版本。然而，這種設(shè)計(jì)犧牲了寫(xiě)性能，因?yàn)楦聲?huì)導(dǎo)致隨機(jī)I/O。此外，索引頁(yè)可以被更新和刪除所分割，從而減少空間利用率。
相反，異位（out-of-place）的更新結(jié)構(gòu)，例如LSM-tree總是將更新存儲(chǔ)到新的位置，而不是覆蓋舊的條目。例如在圖1b中，更新(k1, v4)被存儲(chǔ)到一個(gè)新的位置，而不是直接更新舊的條目(k1, v1)。這種設(shè)計(jì)提高了寫(xiě)性能，因?yàn)樗梢岳庙樞騃/O來(lái)處理寫(xiě)。它還可以通過(guò)不覆蓋舊數(shù)據(jù)來(lái)簡(jiǎn)化恢復(fù)過(guò)程。然而，這種設(shè)計(jì)的主要問(wèn)題是犧牲了讀取性能，因?yàn)橛涗浛赡艽鎯?chǔ)在多個(gè)位置中的任何一個(gè)。此外，這些結(jié)構(gòu)通常需要一個(gè)獨(dú)立的數(shù)據(jù)重組過(guò)程，以不斷提高存儲(chǔ)和查詢效率。順序的、異位的更新并不是新的想法；自20世紀(jì)70年代以來(lái)，它已成功地應(yīng)用于數(shù)據(jù)庫(kù)系統(tǒng)。”
可以看出LSM-TREE的異位（OUT-OF-PLACE）更新結(jié)構(gòu)，壓根就不是讀后寫(xiě)，它就是一個(gè)INSERT動(dòng)作。那這樣子來(lái)看，是不是感覺(jué)把更新動(dòng)作當(dāng)作是一個(gè)寫(xiě)流程的衍生物，無(wú)論是對(duì)于B-TREE而言，還是LSM-TREE而言，基本上是沒(méi)有什么違和感的。
然而，在這一堆反反復(fù)復(fù)的文字中，你可能已經(jīng)建立起一個(gè)LSM-TREE讀取性能被犧牲的概念，并且可能認(rèn)為讀取性能不佳，可能會(huì)是阻礙你的系統(tǒng)選取LSM-TREE的重要障礙。因?yàn)椋呐履憔褪呛?jiǎn)簡(jiǎn)單單的看最前面那個(gè)彩圖，也能知道，你的一條記錄可能要讀好幾個(gè)文件才能得到，從而質(zhì)疑它的讀取性能。
如果你內(nèi)心敏感，你也許能從我舉得例子中察覺(jué)到另一朵重要的烏云。這個(gè)烏云是資源的沖突。LSM-TREE的寫(xiě)優(yōu)勢(shì)根源是，用追加寫(xiě)取代讀后寫(xiě)。如果，你的系統(tǒng)有任何主要的場(chǎng)景，避免不掉讀后寫(xiě)。那這個(gè)優(yōu)勢(shì)的根基便被動(dòng)搖了。約束性檢查，是最容易想到的場(chǎng)景之一，因?yàn)椴蛔x，就不能確定能不能寫(xiě)。繼而，我們很容易的想到另一個(gè)重要更新場(chǎng)景，悲觀鎖和事務(wù)。為啥？長(zhǎng)期的B-TREE經(jīng)驗(yàn)告訴我們，SELECT FOR UPDATE，得先SELECT才能上鎖FOR UPDATE。那不然我異位INSERT的時(shí)候，我去哪檢查這條記錄有沒(méi)有鎖呢？我怎么確定我INSERT的時(shí)候，別人不能INSERT呢？那這一部分內(nèi)容，我們放在后面的章節(jié)里再去展開(kāi)。先把基本的動(dòng)作來(lái)看完。
六、B-TREE之優(yōu)勢(shì)的讀
再看一下這個(gè)圖：
數(shù)據(jù)讀取，數(shù)據(jù)庫(kù)通常視為最最主要的能力。就像我前面說(shuō)的，有一段時(shí)間我都一直覺(jué)得，數(shù)據(jù)如何寫(xiě)，如何擺放最終都是為了讀起來(lái)方便。從圖上看的感覺(jué)總是直觀的，前面提到了，很多人眼看著LSM-TREE那張圖讀取動(dòng)作出現(xiàn)了5條讀取線，得出了LSM-TREE讀取性能不行的結(jié)論（很顯然，我初看這張圖，也是這么認(rèn)為的）。當(dāng)然，讀多次，性能是不是受損，那肯定是受損的。損得大不大？那就不好說(shuō)了。
在來(lái)來(lái)回回看這張圖之后，我不再緊盯那五根線，而是開(kāi)始細(xì)細(xì)的觀察Level 1開(kāi)始往下的這些SSTABLE文件。這些文件由異步的Compaction操作產(chǎn)生。這個(gè)動(dòng)作有很多文檔都把它翻譯成數(shù)據(jù)壓縮，我覺(jué)得這很容易和數(shù)據(jù)庫(kù)的DATA COMPRESS概念混淆。我更喜歡把它譯為數(shù)據(jù)整理。我們看看它做了什么，去重多版本數(shù)據(jù)、刪除多余的老數(shù)據(jù)、數(shù)據(jù)按KEY排序。沒(méi)錯(cuò)，它竟然是排序的。如果說(shuō)SSTABLE的文件頭里面，標(biāo)上了起止的KEY，它像不像一個(gè)小小的B樹(shù)呢？還記得我在前面說(shuō)那個(gè)隱隱約約的線索嗎？數(shù)據(jù)庫(kù)總是把一些異步操作，作為一些優(yōu)化的空間。LSM-TREE的Compaction就絕不是僅僅為了防止數(shù)據(jù)量不斷增長(zhǎng)而設(shè)計(jì)的清理機(jī)制。它的存在還有更重要的意義。LSM-TREE其實(shí)并沒(méi)有自暴自棄的在優(yōu)化寫(xiě)入的時(shí)候就放棄查詢。其實(shí)它遵循了我們之前那個(gè)現(xiàn)索，數(shù)據(jù)庫(kù)在異步的流程中，暗暗的優(yōu)化數(shù)據(jù)查詢時(shí)的速度。
我們來(lái)接著填一下前面的坑。如果說(shuō)，相比B樹(shù)而言，LSM-TREE的讀取總是很慢的。是不是數(shù)據(jù)相對(duì)穩(wěn)定的系統(tǒng)就不能選LSM-TREE嗎？如果，我們的數(shù)據(jù)一次INSERT之后，就沒(méi)不動(dòng)了，那會(huì)是什么情況？我們來(lái)細(xì)細(xì)的推敲一下，首先必然的，LSM-TREE寫(xiě)優(yōu)勢(shì)用不上不對(duì)，因?yàn)槟憔筒辉趺磳?xiě)嘛？但是讀的真的就慢嗎？我們來(lái)看看，首先，我們?cè)趦?nèi)存里找到了這條記錄，CACHE命中了，或者M(jìn)EMTABLE里有最新的數(shù)據(jù)，都沒(méi)有磁盤(pán)IO，那妥妥的快。假設(shè)沒(méi)命中，那么只做個(gè)一次INSERT的記錄，可能出現(xiàn)幾層的幾個(gè)SSTABLE里面？好像只有一個(gè)吧。當(dāng)然，這里會(huì)有一個(gè)疑惑，就是我沒(méi)讀這個(gè)SSTABLE，我怎么知道里面有沒(méi)有這條記錄？在我印象中，通常SSTABLE的數(shù)據(jù)文件，通常都要配一個(gè)BLOOM過(guò)濾器，來(lái)告訴你這條KEY它有沒(méi)有來(lái)解決這件事情。誒，這時(shí)候，再來(lái)整理整理感覺(jué)，是不是上面那兩根內(nèi)存里的線，還挺快的。下面指到磁盤(pán)上的三根線，好像也沒(méi)有三根線也就只有一根，剩下這一根，感覺(jué)還和B-TREE有那么一點(diǎn)點(diǎn)的像，搞不好在這一個(gè)SSTABLE里面，拿得還比B-TREE快。
好啦，這個(gè)例子其實(shí)有點(diǎn)過(guò)，我并不是要證明LSM-TREE的讀取性能要比B-TREE好，這是不可能的。我只是想再提醒前面那個(gè)觀點(diǎn)，它優(yōu)勢(shì)的地方你的系統(tǒng)不一定優(yōu)勢(shì)，它劣勢(shì)的地方你的系統(tǒng)也不一定就劣勢(shì)，就是這么神奇。比如我還常常被問(wèn)到類(lèi)似的問(wèn)題，我的系統(tǒng)以更新為主，SSTABLE的線特別多是不是不能選LSM-TREE？那也不一定啊，如果你平時(shí)查都不查，那讀取有一百根線對(duì)你的系統(tǒng)性能又有什么影響呢？那我的系統(tǒng)又改得多又查得多，又不是以寫(xiě)入為主呢？對(duì)的，它不適合，因?yàn)镾STABLE的讀取線很多，而且它的寫(xiě)優(yōu)勢(shì)又發(fā)揮不出來(lái)。所以無(wú)論如何，你還是得把自己系統(tǒng)的場(chǎng)景往里面帶一帶，不要憑看圖的直覺(jué)。
LSM-TREE的讀取性能或許確實(shí)的受損的。但是顯而易見(jiàn)的是，對(duì)于很多時(shí)候，這種受損是可以通過(guò)各種各樣的手段優(yōu)化、緩解。使得這種受損處于可接受的范圍，不然LSM-TREE是怎么越來(lái)越火的呢？對(duì)吧。
而B(niǎo)樹(shù)的讀取方面，我覺(jué)得這里就不太需要再展開(kāi)來(lái)討論了，因?yàn)榍懊嬖谡f(shuō)明它寫(xiě)的時(shí)候，其實(shí)也是要先完成讀取流程的，再者B樹(shù)大家也相對(duì)而言比較熟悉。
七、資源的沖突-數(shù)據(jù)鎖
接下來(lái)，是時(shí)候來(lái)講一講這一朵烏云了。資源沖突問(wèn)題，一直以來(lái)都在數(shù)據(jù)庫(kù)的重要困難點(diǎn)附近出沒(méi)。而且，沖突問(wèn)題又和分布式的問(wèn)題互相之間有一些糾纏。舉個(gè)例子，在數(shù)據(jù)庫(kù)單機(jī)架構(gòu)往SHARE DISK的架構(gòu)演變過(guò)程中，它就一度成為了很多數(shù)據(jù)庫(kù)廠商搞不定的難點(diǎn)。比如，我在集群中的某一個(gè)數(shù)據(jù)庫(kù)實(shí)例上，上鎖并修改了數(shù)據(jù)。這個(gè)鎖和修改信息，就需要立刻在內(nèi)存中，直接通訊給其他的數(shù)據(jù)庫(kù)實(shí)例。最后比較成熟的方案只有幾個(gè)少數(shù)像ORACLE 的RAC，DB2的DATA SHARING這樣的能夠解決。這個(gè)例子特別清楚的能體現(xiàn)，資源沖突處理，要么要集中處理，要么需要特別靠譜的互相通信，這個(gè)通訊在分布式水平擴(kuò)展的情況下會(huì)有所放大。所以，有一些SHARE NOTHING的數(shù)據(jù)庫(kù)產(chǎn)品，會(huì)選擇在數(shù)據(jù)存儲(chǔ)節(jié)點(diǎn)，來(lái)集中處理數(shù)據(jù)的上鎖問(wèn)題。
對(duì)于基于LSM-TREE的數(shù)據(jù)庫(kù)產(chǎn)品而言，有的產(chǎn)品選擇不支持鎖和事務(wù)，有的選擇通過(guò)其它巧妙的手段來(lái)解決。而我們還是可以顯著的看到，B-TREE結(jié)構(gòu)中，上鎖與不上鎖，也許只是內(nèi)存里面一個(gè)記錄標(biāo)志位的修改差別，上鎖與不上鎖的性能差別似乎并不是很大。但是LSM-TREE結(jié)構(gòu)的數(shù)據(jù)庫(kù)里，似乎很有必要把上鎖流程的開(kāi)銷(xiāo)拿出來(lái)額外關(guān)注一下。因?yàn)槿绻麛?shù)據(jù)庫(kù)做的是一般性先讀后寫(xiě)，那么寫(xiě)優(yōu)勢(shì)沒(méi)了。如果是別的沖突處理機(jī)制，那這部分顯然屬于額外開(kāi)銷(xiāo)。
為什么不支持，竟然也可以算一個(gè)出路，我們可以往回退一步。資源沖突問(wèn)題的源頭是并行的處理。而在沖突的資源點(diǎn)上，我們需要轉(zhuǎn)并行為串行，其實(shí)大致上我覺(jué)得可以分開(kāi)成兩個(gè)問(wèn)題來(lái)看，第一個(gè)解決時(shí)序問(wèn)題，就是我們認(rèn)為后面的更新才是對(duì)的，第二個(gè)是解決并發(fā)過(guò)程中更新丟失和臟讀問(wèn)題。像CASSANDRA這樣的數(shù)據(jù)，用時(shí)間戳來(lái)解決時(shí)序問(wèn)題，即改更新為追加，并在數(shù)據(jù)讀取合并時(shí)，以最新時(shí)間戳的數(shù)據(jù)為準(zhǔn)。再利用時(shí)間戳來(lái)實(shí)現(xiàn)多版本的讀取。算是解決半個(gè)資源沖突的本源問(wèn)題。所以對(duì)沒(méi)有第二部分問(wèn)題的系統(tǒng)，這的確也是一個(gè)解決方案。
另外半個(gè)問(wèn)題，就比較棘手，比如說(shuō)錢(qián)的轉(zhuǎn)入轉(zhuǎn)出模型，有的轉(zhuǎn)入有的轉(zhuǎn)出，若錢(qián)不夠就不能夠轉(zhuǎn)出。
我們來(lái)看一個(gè)我覺(jué)得比較優(yōu)秀的基于LSM-TREE存儲(chǔ)結(jié)構(gòu)的 Percolator模型的實(shí)現(xiàn)方案。比A有10塊錢(qián)，B有2塊錢(qián)，A向B轉(zhuǎn)7塊錢(qián)。
首先，使用三個(gè)列簇（COLUMN FAILY）來(lái)存三樣?xùn)|西，一個(gè)是數(shù)據(jù)本身，一個(gè)是鎖信息，一個(gè)是寫(xiě)入的版本。要有一個(gè)時(shí)間戳和一個(gè)版本號(hào)來(lái)解決時(shí)序問(wèn)題，那么在PREWRITE階段，數(shù)據(jù)庫(kù)除了寫(xiě)入數(shù)據(jù)之外，還要寫(xiě)入LOCK信息。最后再提交階段，把LOCK信息干掉，再寫(xiě)一個(gè)版本信息。
作為讀后寫(xiě)替代，那么這種方案下的沖突解決能不能比B樹(shù)的維護(hù)代價(jià)更小一點(diǎn)。我們先看看，在理想LSM-TREE的UPDATE只有一個(gè)追加寫(xiě) MEMTABLE的操作上，又附加了什么。首先，我們看A記錄，一共寫(xiě)了 三次，最后COMMIT結(jié)束之后，還需要把鎖信息干掉。草算一算，好像時(shí)間翻了四倍。再細(xì)細(xì)的看一下，寫(xiě)數(shù)據(jù)和寫(xiě)版本看起來(lái)應(yīng)該是可以追加寫(xiě)的。但是，這個(gè)鎖信息可不就是一個(gè)妥妥的讀后寫(xiě)嗎？因?yàn)閷?duì)一條記錄上鎖之前，起碼得看看前面有沒(méi)有鎖吧。但是感覺(jué)上，這個(gè)鎖的CF應(yīng)該不大，應(yīng)該基本上都是內(nèi)存操作。
我們來(lái)細(xì)細(xì)推敲一下。普通更新的話，把A從版本5的10改為版本7的3。追加寫(xiě)數(shù)據(jù)，追加寫(xiě)版本，兩次內(nèi)存操作。檢查讀一次鎖，如果沒(méi)鎖，寫(xiě)一次鎖，先算他是內(nèi)存操作。如果在B樹(shù)上，一般隨機(jī)轉(zhuǎn)賬命中概率不大，把A讀起來(lái)，那么有一波磁盤(pán)IO，再加同樣的內(nèi)存上鎖放鎖，感覺(jué)還是B樹(shù)不一定快。為啥，因?yàn)橥瑯邮亲x后寫(xiě)，這個(gè)鎖CF信息的讀后寫(xiě)很可能是內(nèi)存里沒(méi)有磁盤(pán)操作的。而B(niǎo)樹(shù)的讀后寫(xiě)，那基本上磁盤(pán)IO跑不了的。在這樣的情況下，其實(shí)LSM基本上不落下風(fēng)的。
但是，程序可不一定是這么寫(xiě)的。比如說(shuō)，悲觀鎖。我相信很多時(shí)候，你很難把上面這個(gè)場(chǎng)景的SQL寫(xiě)成，UPDATE TABLE SET YUAN=YUAN-7 WHERE KEY=A吧。比較常見(jiàn)的寫(xiě)法不應(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)時(shí)間對(duì)比其實(shí)從單一的UPDATE對(duì)比變成了兩個(gè)SQL符合在一起的形態(tài)對(duì)比。首先，由于SELECT FOR UPDATE這個(gè)動(dòng)作出現(xiàn)，磁盤(pán)讀變成了一個(gè)跑不掉的步驟。B樹(shù)上，記錄會(huì)在SELECT FOR UPDATE的時(shí)候就被IO到內(nèi)存里面來(lái)。這時(shí)候，你再看B樹(shù)的UPDATE，那就純粹是個(gè)內(nèi)存操作，那應(yīng)該不會(huì)比寫(xiě)三個(gè)CF慢的。上鎖放鎖的內(nèi)存動(dòng)作，我們姑且認(rèn)為二者差不多，那這個(gè)場(chǎng)景就變成純粹的比讀取。而且，考慮的有沖突和并發(fā)，表示這是一個(gè)頻繁變更數(shù)據(jù)的情況，那么我會(huì)猜測(cè)LSM-TREE讀取的SSTABLE的線比較多，最終直接成為影響系統(tǒng)性能的重要因素。
再稍微說(shuō)一下分布式的疊加，如果A和B存在不同的節(jié)點(diǎn)里。B中的副鎖還要再跨網(wǎng)絡(luò)去訪問(wèn)A節(jié)點(diǎn)的主鎖有沒(méi)有釋放。感覺(jué)也是有一些跟硬件相關(guān)的開(kāi)銷(xiāo)在里面。但應(yīng)該不是重點(diǎn)，因?yàn)轭?lèi)比我們前面說(shuō)的，RAC各實(shí)例間也有基于網(wǎng)絡(luò)的鎖信息交互開(kāi)銷(xiāo)。
八、高可用附加
其實(shí)這個(gè)內(nèi)容，跟存儲(chǔ)引擎的聯(lián)系有限，但是前面寫(xiě)入的時(shí)候提到了BINLOG。MYSQL的BINLOG承擔(dān)了主備機(jī)同步的橋梁作用，但它對(duì)于很多重要系統(tǒng)來(lái)說(shuō)都是必開(kāi)的。最關(guān)鍵的是，再RPO=0的前提下，BINLOG的遠(yuǎn)程落盤(pán)，是COMMIT成功的必要條件。它的開(kāi)銷(xiāo)對(duì)性能影響是必然的，寫(xiě)B(tài)INLOG也幾乎寫(xiě)流程中的一部分。不過(guò)我覺(jué)得它還是可以剝離出來(lái)看，因?yàn)樗举|(zhì)并不是WAL日志。如果一定要對(duì)標(biāo)的話，我覺(jué)得它類(lèi)似于RAFT LOG的寫(xiě)入，這兩個(gè)東西都是圍繞著高可用和多節(jié)點(diǎn)數(shù)據(jù)復(fù)制展開(kāi)的。對(duì)于寫(xiě)入的性能開(kāi)銷(xiāo)增加，似乎也是差不多的。
九、結(jié)尾
終于把這個(gè)坑稍微填了一填，感覺(jué)說(shuō)了好多，又感覺(jué)好多內(nèi)容沒(méi)有說(shuō)。想必以我的認(rèn)知力，也并沒(méi)有能力把所有的內(nèi)容說(shuō)的很全?；旧习褜?shí)踐中，遇到過(guò)、顧慮過(guò)的一些我覺(jué)得的關(guān)鍵點(diǎn)整理了一下吧，也算可以給需要的朋友提供個(gè)參考。另外，從文中想必也能看得出來(lái)，有些內(nèi)容基本我全憑猜測(cè)，未必準(zhǔn)確，也期待有大佬看到并幫我指出其中的錯(cuò)漏。
作者介紹
宇文湛泉，現(xiàn)任金融行業(yè)核心業(yè)務(wù)系統(tǒng)DBA，主要涉及Oracle、DB2、Cassandra、MySQL、GoldenDB、TiDB等數(shù)據(jù)庫(kù)開(kāi)發(fā)工作。
網(wǎng)站題目：分布式數(shù)據(jù)庫(kù)存儲(chǔ)透析：B-TREE和LSM-TREE的性能差別
轉(zhuǎn)載源于：http://www.5511xx.com/article/cceiigp.html
