在這篇文章中，我將會講解一些數(shù)據(jù)庫存儲的內(nèi)部機(jī)制，數(shù)據(jù)庫是如何進(jìn)行優(yōu)化操作來提供驚人速度及其優(yōu)勢和缺點。

當(dāng)我們談起數(shù)據(jù)庫內(nèi)部存儲結(jié)構(gòu)時，人們都會想到B樹或者B+樹，但是我們在這里并不會談?wù)撨@些數(shù)據(jù)結(jié)構(gòu)的原理，我們會展示這些數(shù)據(jù)結(jié)構(gòu)為什么適合作為數(shù)據(jù)庫存儲的內(nèi)部結(jié)構(gòu)以及使用這些數(shù)據(jù)結(jié)構(gòu)的目的。

傳統(tǒng)的關(guān)系型數(shù)據(jù)將數(shù)據(jù)以B樹的形式存儲在磁盤上，它們也會在RAM上使用B樹維護(hù)這些數(shù)據(jù)的索引，來保證更快的訪問速度。插入的行存儲在B樹的葉子節(jié)點上，所有的中間節(jié)點用來存儲用于導(dǎo)航查詢語句的原數(shù)據(jù)。因此，當(dāng)有數(shù)以百萬計的數(shù)據(jù)被插入到數(shù)據(jù)庫中時，索引和數(shù)據(jù)存儲會變得十分大。因此，為了快速的訪問，需要從磁盤中加載所有數(shù)據(jù)到內(nèi)存，但是RAM一般沒有這么大的空間來存儲所有的數(shù)據(jù)。因此，數(shù)據(jù)庫必須從磁盤中讀取部分?jǐn)?shù)據(jù)。這種加載數(shù)據(jù)的場景如下圖所示：

磁盤I/O花費的時間很長，是影響數(shù)據(jù)庫性能的主要原因之一。B樹是支持隨機(jī)讀寫，in-place 替換，十分緊湊并且自平衡的數(shù)據(jù)結(jié)構(gòu)，但是受磁盤I/O速度的限制。隨機(jī)讀意味著當(dāng)訪問磁盤數(shù)據(jù)時，磁頭必須移動到柱面上的指定位置，因此會消耗大量時間。

B樹被設(shè)計為使用block的形式存儲數(shù)據(jù)，因為操作系統(tǒng)讀取讀取一個block的數(shù)據(jù)要比讀取單獨字節(jié)數(shù)據(jù)要快的多。MySQL的InnoDB存儲引擎的block大小為16KB。這意味著每次你讀取或者寫入數(shù)據(jù)時，大小為16KB的block數(shù)據(jù)會被從磁盤加載到RAM中，它會被寫入新的數(shù)據(jù)，并且再次寫回到磁盤上。假設(shè)數(shù)據(jù)庫表的每一行數(shù)據(jù)為128字節(jié)（實際大小會變化），一個block（葉子節(jié)點）為16KB，存儲了（16 * 1024） / 128 = 128行數(shù)據(jù)。B樹的高度一般小于10，但是每一層的節(jié)點數(shù)量卻很多，由此可以管理數(shù)以萬計的數(shù)據(jù)。基于上述特性，B樹適合作為數(shù)據(jù)內(nèi)部存儲結(jié)構(gòu)。

因此，在B樹上進(jìn)行讀操作是相對來說比較快速的，因為該操作只需要遍歷一些節(jié)點并且進(jìn)行較少次數(shù)的磁盤I/O請求。而且，范圍查詢因為可以將數(shù)據(jù)以block的形式進(jìn)行獲取和操作而速度更快。你可以進(jìn)行下列操作來讓基于B-Tree的數(shù)據(jù)庫性能更好：

減少索引節(jié)點數(shù)量：這是提升關(guān)系型數(shù)據(jù)庫性能的常用策略。索引越多，插入和更新操作需要管理的索引數(shù)量也越多。當(dāng)數(shù)據(jù)庫數(shù)據(jù)運行時間越來越久時，就需要刪除一些老舊或者無用的索引，并且謹(jǐn)慎地添加新的索引。但是你也要注意，索引越少意味著查詢性能越差，你需要在查詢性能和插入更新性能之間進(jìn)行取舍（譯者注：可以考慮數(shù)據(jù)庫的讀寫比率）。

順序插入：如果你能以主鍵大小為基礎(chǔ)進(jìn)行大量數(shù)據(jù)的順序插入，那么插入數(shù)據(jù)的速度會十分的快。因為在插入過程中，插入行所屬的block已經(jīng)在內(nèi)存中，所以數(shù)據(jù)庫可以直接將行插入到內(nèi)存的數(shù)據(jù)結(jié)構(gòu)中，然后通過一次磁盤I/O提交到數(shù)磁盤中。當(dāng)然，這些都取決于數(shù)據(jù)庫的具體實現(xiàn)，但是我認(rèn)為現(xiàn)代的數(shù)據(jù)庫一般都會進(jìn)行類似的優(yōu)化。

但是B樹并不是適合所有情景的最優(yōu)存儲結(jié)構(gòu)。對B樹結(jié)構(gòu)的寫操作性能很差，比隨機(jī)讀還要差，因為數(shù)據(jù)庫必須從磁盤中加載數(shù)據(jù)對應(yīng)的頁，然后修改它并沖洗新寫入到磁盤中。隨機(jī)寫入時平均有100字節(jié)每秒寫入速度，這個限制是由于磁盤的基本工作原理。事實上，簡單依賴于緩存的使用，索引搜索和更多的內(nèi)存可以處理更多的讀操作，但是應(yīng)付更多的寫操作就比較麻煩。當(dāng)你需要寫入或更新大量的數(shù)據(jù)時，B樹結(jié)構(gòu)并不是最正確的選擇。長久以來，傳統(tǒng)數(shù)據(jù)庫進(jìn)行了大量的優(yōu)化，比如說InnoDB嘗試使用緩沖來減少磁盤I/O操作。具體操作如下所示：

數(shù)據(jù)庫寫操作可以通過提升磁盤的帶寬來提升速度，但是目前關(guān)系型數(shù)據(jù)庫都沒有這樣做。而且關(guān)系型數(shù)據(jù)庫管理系統(tǒng)一般都是十分復(fù)雜的，因為他們使用鎖，并發(fā)，ACID事務(wù)等操作，這使得寫入操作更加復(fù)雜。

當(dāng)今信息時代，在比如消息、聊天、實時通訊和物聯(lián)網(wǎng)等客戶為中心的服務(wù)和大量無結(jié)構(gòu)化數(shù)據(jù)的分布式系統(tǒng)中，每小時都會進(jìn)行數(shù)百萬計的寫入操作。因此，這些系統(tǒng)是以寫為主的系統(tǒng)，為了迎合這些系統(tǒng)的需要，數(shù)據(jù)庫需要能夠擁有快速插入數(shù)據(jù)的能力。典型的數(shù)據(jù)庫并不能很好的滿足類似的場景，因為它們無法應(yīng)付高可用性，盡可能的最終一致性，無格式數(shù)據(jù)的靈活性和低延遲等要求。

LSM樹（Log Structured Merge Tree）應(yīng)運而生。LSM并不是一種類似于B樹的數(shù)據(jù)結(jié)構(gòu)，而是一個系統(tǒng)。在LSM系統(tǒng)中，并沒有對數(shù)據(jù)的in-place替換；一旦數(shù)據(jù)被寫入磁盤，它就再也不會被修改。顯然，它是一種只能在末尾添加（append only）的寫入系統(tǒng)。一些日志結(jié)構(gòu)的文件系統(tǒng)比如ext3/4也使用類似的原理。因此，該系統(tǒng)就如同順序的記錄數(shù)據(jù)日志一般。基本上，LSM系統(tǒng)利用了順序?qū)懙膬?yōu)勢。傳統(tǒng)的磁盤驅(qū)動的寫操作最高可以達(dá)到100MB/s，現(xiàn)代的固態(tài)硬盤在順序?qū)憰r的速度則更快。事實上，固態(tài)硬盤驅(qū)動有一些內(nèi)置的并行機(jī)制來讓它可以同時寫入16到32MB的數(shù)據(jù)。LSM樹和固態(tài)硬盤的特性十分匹配。順序?qū)懸入S機(jī)寫快很多。

為了正確地理解上述場景，讓我們簡單的看一下Facebook的Cassandra數(shù)據(jù)庫是如何使用LSM原則的。

Cassandra或者任何LSM系統(tǒng)都會維護(hù)一個或者多個用來在寫入磁盤前存儲數(shù)據(jù)的內(nèi)存數(shù)據(jù)結(jié)構(gòu)（如上圖中的memtable），比如說子平衡樹（AVL）、紅黑樹、B樹或者跳表。該內(nèi)存數(shù)據(jù)結(jié)構(gòu)維護(hù)一個排序的數(shù)據(jù)集。不同的LSM實現(xiàn)互使用不同的數(shù)據(jù)結(jié)構(gòu)來適應(yīng)不同的需求，并不存在標(biāo)準(zhǔn)的LSM實現(xiàn)。當(dāng)內(nèi)存中存儲的數(shù)據(jù)超過配置的閾值時，內(nèi)存中存儲的數(shù)據(jù)就會被放置在將會被寫入磁盤的隊列中。為了flush數(shù)據(jù)，Cassandra順序地寫入排序的數(shù)據(jù)到磁盤中。磁盤維護(hù)一個叫做“SSTable”（Sorted Strings Table）的數(shù)據(jù)結(jié)構(gòu)，該數(shù)據(jù)就是寫入文件數(shù)據(jù)的有序的快照，SSTable是不可變的。LSM系統(tǒng)可以管理磁盤上的多個文件。

因此，如果數(shù)據(jù)在內(nèi)存中沒有被發(fā)現(xiàn)，Cassandra需要掃描所有磁盤上的SSTables來搜索該數(shù)據(jù)。因此，Cassandra的讀操作相對來說要比寫操作慢，但是這里有一些可以處理的方法。Cassandra或者其他LSM系統(tǒng)會在后臺運行壓縮程序來減少SSTable的數(shù)量。壓縮程序?qū)STable進(jìn)行歸并排序，在新的SSTable找那個插入新的排序數(shù)據(jù)并且刪除老的SSTables。但是使用壓縮程序有時候無法應(yīng)付數(shù)據(jù)庫中數(shù)以百萬計的更新操作。

因此，一些概率數(shù)據(jù)結(jié)構(gòu)（probabilistic data structures）比如Bloom filters被應(yīng)用來快速判斷是否一些數(shù)據(jù)存在于SSTable。Bloom filters十分適合對內(nèi)存中的數(shù)據(jù)進(jìn)行判斷，因為它需要進(jìn)行大量的隨機(jī)查詢來進(jìn)行數(shù)據(jù)是否存在的概率性判斷。Bloom filters算法可以極大地減少遍歷查詢SSTables的花費。因此，LSM系統(tǒng)解決了在大數(shù)據(jù)中寫操作需要花費大量時間的問題。LSM系統(tǒng)也有Read amplification的問題-會讀取出比它實際需要更多的數(shù)據(jù)。因此，還有介于B Tree和LSM Tree之間的解決方法來給出我們最優(yōu)（不一定準(zhǔn)確）的讀寫效率嗎？

Fractal Tree Index是基于B-Tree的數(shù)據(jù)結(jié)構(gòu)。依據(jù)開發(fā)人員給出的benchmark，該數(shù)據(jù)結(jié)構(gòu)有比B-Tree更優(yōu)良的性能。Fractal tree支持在非葉節(jié)點上的信息緩存。MySQL的高性能存儲引擎Tokudb就使用了Fractal tree。

如上圖所示，在Fractal Tree中，你進(jìn)行的添加列，刪除列，插入，更新等任何操作都會被當(dāng)做操作消息存儲在非葉節(jié)點上。由于操作只是被簡單地存儲在緩存或者任何次級索引緩存（secondary index buffer）中，所以，所有的操作都會被迅速執(zhí)行結(jié)束。當(dāng)某一個節(jié)點的緩存滿了之后，這些操作消息會依次從根節(jié)點，經(jīng)過非葉節(jié)點，向葉節(jié)點進(jìn)行傳遞。葉節(jié)點仍然存儲著真實數(shù)據(jù)。當(dāng)進(jìn)行讀時，讀操作會考慮查詢路徑節(jié)點上的所有操作消息來獲取真實的數(shù)據(jù)狀態(tài)。但是由于tokudb會盡力將所有非葉節(jié)點緩存在內(nèi)存中，所以這一過程也很快。

tokubd中的block最大可以達(dá)到4MB，而不是InnoDB中的16KB。這樣的大小可以允許一次I/O操作時加載或?qū)懟馗嗟臄?shù)據(jù)，這也有助于一次壓縮更多數(shù)據(jù)來減少磁盤上數(shù)據(jù)的存儲大小。因此，tokudb強調(diào)借助更大的block大小能夠?qū)崿F(xiàn)更好的數(shù)據(jù)壓縮和更少的磁盤I/O。tokudb宣稱它們的存儲引擎比InnoDB更快，提供比InnoDB更快的讀寫吞吐，并且tokudb也宣稱自己有更少的碎片（fragmentation）問題，它也支持多集群索引等。下圖是benchmark的相關(guān)統(tǒng)計圖：

只有你系統(tǒng)中的benchmark可以幫助你判斷正確的數(shù)據(jù)點和需求解決方案。但是MySQL的存儲引擎會持續(xù)地不斷改進(jìn)和支持新出現(xiàn)的需求。LSM樹是為了高寫入場景的系統(tǒng)，然而B樹是為了傳統(tǒng)的場景應(yīng)用。Fractal樹的索引改進(jìn)了B樹索引存在的一些缺陷。因此，未來會不斷地出現(xiàn)技術(shù)上的革新，包括數(shù)據(jù)庫存儲技術(shù)，硬件，磁盤驅(qū)動和操作系統(tǒng)，讓我們拭目以待。
責(zé)任編輯人：CC