?我一直以來都在不斷的研究和探索數(shù)據(jù)庫的內部存儲原理。我認為這個話題是非常巨大且復雜的，我努力所學也只占其千萬分之一。我將會講解一些數(shù)據(jù)庫存儲的內部機制，數(shù)據(jù)庫是如何進行優(yōu)化操作來提供驚人速度及其優(yōu)勢和缺點。

?當我們談起數(shù)據(jù)庫內部存儲結構時，人們都會想到B樹或者B+樹，但是我們在這里并不會談論這些數(shù)據(jù)結構的原理，我們會展示這些數(shù)據(jù)結構為什么適合作為數(shù)據(jù)庫存儲的內部結構以及使用這些數(shù)據(jù)結構的目的。

?傳統(tǒng)的關系型數(shù)據(jù)將數(shù)據(jù)以B樹的形式存儲在磁盤上，它們也會在RAM上使用B樹維護這些數(shù)據(jù)的索引，來保證更快的訪問速度。插入的行存儲在B樹的葉子節(jié)點上，所有的中間節(jié)點用來存儲用于導航查詢語句的原數(shù)據(jù)。

    因此，當有數(shù)以百萬計的數(shù)據(jù)被插入到數(shù)據(jù)庫中時，索引和數(shù)據(jù)存儲會變得十分大。因此，為了快速的訪問，需要從磁盤中加載所有數(shù)據(jù)到內存，但是RAM一般沒有這么大的空間來存儲所有的數(shù)據(jù)。因此，數(shù)據(jù)庫必須從磁盤中讀取部分數(shù)據(jù)。這種加載數(shù)據(jù)的場景如下圖所示：

 

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

?B樹被設計為使用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ù)據(jù)庫表的每一行數(shù)據(jù)為128字節(jié)（實際大小會變化），一個block（葉子節(jié)點）為16KB，存儲了(16 * 1024) / 128 = 128行數(shù)據(jù)。

    B樹的高度一般小于10，但是每一層的節(jié)點數(shù)量卻很多，由此可以管理數(shù)以萬計的數(shù)據(jù)。基于上述特性，B樹適合作為數(shù)據(jù)內部存儲結構。

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

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

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

?但是B樹并不是適合所有情景的最優(yōu)存儲結構。對B樹結構的寫操作性能很差，比隨機讀還要差，因為數(shù)據(jù)庫必須從磁盤中加載數(shù)據(jù)對應的頁，然后修改它并沖洗新寫入到磁盤中。隨機寫入時平均有100字節(jié)每秒寫入速度，這個限制是由于磁盤的基本工作原理。

    事實上，簡單依賴于緩存的使用，索引搜索和更多的內存可以處理更多的讀操作，但是應付更多的寫操作就比較麻煩。當你需要寫入或更新大量的數(shù)據(jù)時，B樹結構并不是最正確的選擇。長久以來，傳統(tǒng)數(shù)據(jù)庫進行了大量的優(yōu)化，比如說InnoDB嘗試使用緩沖來減少磁盤I/O操作。具體操作如下所示：

 

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

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

?LSM樹(Log Structured Merge Tree)應運而生。LSM并不是一種類似于B樹的數(shù)據(jù)結構，而是一個系統(tǒng)。在LSM系統(tǒng)中，并沒有對數(shù)據(jù)的in-place替換；一旦數(shù)據(jù)被寫入磁盤，它就再也不會被修改。顯然，它是一種只能在末尾添加(append only)的寫入系統(tǒng)。一些日志結構的文件系統(tǒng)比如ext3/4也使用類似的原理。

    因此，該系統(tǒng)就如同順序的記錄數(shù)據(jù)日志一般?；旧希琇SM系統(tǒng)利用了順序寫的優(yōu)勢。傳統(tǒng)的磁盤驅動的寫操作最高可以達到100MB/s，現(xiàn)代的固態(tài)硬盤在順序寫時的速度則更快。事實上，固態(tài)硬盤驅動有一些內置的并行機制來讓它可以同時寫入16到32MB的數(shù)據(jù)。LSM樹和固態(tài)硬盤的特性十分匹配。順序寫要比隨機寫快很多。

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

 

?Cassandra或者任何LSM系統(tǒng)都會維護一個或者多個用來在寫入磁盤前存儲數(shù)據(jù)的內存數(shù)據(jù)結構(如上圖中的memtable)，比如說子平衡樹(AVL)、紅黑樹、B樹或者跳表。該內存數(shù)據(jù)結構維護一個排序的數(shù)據(jù)集。

    不同的LSM實現(xiàn)互使用不同的數(shù)據(jù)結構來適應不同的需求，并不存在標準的LSM實現(xiàn)。當內存中存儲的數(shù)據(jù)超過配置的閾值時，內存中存儲的數(shù)據(jù)就會被放置在將會被寫入磁盤的隊列中。為了flush數(shù)據(jù)，Cassandra順序地寫入排序的數(shù)據(jù)到磁盤中。

    磁盤維護一個叫做“SSTable”(Sorted Strings Table)的數(shù)據(jù)結構，該數(shù)據(jù)就是寫入文件數(shù)據(jù)的有序的快照，SSTable是不可變的。LSM系統(tǒng)可以管理磁盤上的多個文件。

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

    因此，一些概率數(shù)據(jù)結構(probabilistic data structures)比如Bloom filters被應用來快速判斷是否一些數(shù)據(jù)存在于SSTable。Bloom filters十分適合對內存中的數(shù)據(jù)進行判斷，因為它需要進行大量的隨機查詢來進行數(shù)據(jù)是否存在的概率性判斷。Bloom filters算法可以極大地減少遍歷查詢SSTables的花費。因此，LSM系統(tǒng)解決了在大數(shù)據(jù)中寫操作需要花費大量時間的問題。

    LSM系統(tǒng)也有Read amplification的問題-會讀取出比它實際需要更多的數(shù)據(jù)。因此，還有介于B Tree和LSM Tree之間的解決方法來給出我們最優(yōu)（不一定準確）的讀寫效率嗎？

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

 

?如上圖所示，在Fractal Tree中，你進行的添加列，刪除列，插入，更新等任何操作都會被當做操作消息存儲在非葉節(jié)點上。由于操作只是被簡單地存儲在緩存或者任何次級索引緩存(secondary index buffer)中，所以，所有的操作都會被迅速執(zhí)行結束。

    當某一個節(jié)點的緩存滿了之后，這些操作消息會依次從根節(jié)點，經(jīng)過非葉節(jié)點，向葉節(jié)點進行傳遞。葉節(jié)點仍然存儲著真實數(shù)據(jù)。當進行讀時，讀操作會考慮查詢路徑節(jié)點上的所有操作消息來獲取真實的數(shù)據(jù)狀態(tài)。但是由于tokudb會盡力將所有非葉節(jié)點緩存在內存中，所以這一過程也很快。

?tokubd中的block最大可以達到4MB，而不是InnoDB中的16KB。這樣的大小可以允許一次I/O操作時加載或寫回更多的數(shù)據(jù)，這也有助于一次壓縮更多數(shù)據(jù)來減少磁盤上數(shù)據(jù)的存儲大小。

    因此，tokudb強調借助更大的block大小能夠實現(xiàn)更好的數(shù)據(jù)壓縮和更少的磁盤I/O。tokudb宣稱它們的存儲引擎比InnoDB更快,提供比InnoDB更快的讀寫吞吐,并且tokudb也宣稱自己有更少的碎片(fragmentation)問題，它也支持多集群索引等。下圖是benchmark的相關統(tǒng)計圖：

 

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