1. 哈希存儲(chǔ)引擎

介紹

• 哈希存儲(chǔ)引擎是哈希表的持久化實(shí)現(xiàn)，支持增、刪、改以及隨機(jī)讀取的操作。但不支持順序掃描。一般使用哈希存儲(chǔ)引擎的存儲(chǔ)系統(tǒng)為鍵值（K-V）類型。
• 對(duì)于key-value的插入以及查詢，哈希表的復(fù)雜度都是O(1)
• 代表性的應(yīng)用有：Redis，Memcache，以及存儲(chǔ)系統(tǒng)Bitcask。

基本實(shí)現(xiàn)

• Bitcask數(shù)據(jù)文件中的數(shù)據(jù)是采用不斷追加（順序?qū)懀┑男问綄?xiě)入的，記錄包含key、value、主鍵長(zhǎng)度、value長(zhǎng)度、時(shí)間戳以及crc校驗(yàn)值。
• Bitcask數(shù)據(jù)存儲(chǔ)所在服務(wù)器在內(nèi)存中采用基于哈希表的索引數(shù)據(jù)結(jié)構(gòu)。該哈希表索引保存了每個(gè)key到數(shù)據(jù)文件中value所在的位置的映射。
• 因此僅需所有的key可以放入內(nèi)存，value的實(shí)際內(nèi)容則可以超過(guò)內(nèi)存大小。- 每次讀取只需一次磁盤(pán)尋址，就可以將value從磁盤(pán)加載到內(nèi)存。如果那部分?jǐn)?shù)據(jù)文件已經(jīng)在文件系統(tǒng)的緩存中，則不需要任何的磁盤(pán)IO。每個(gè)寫(xiě)操作總共需要進(jìn)行一次順序的磁盤(pán)寫(xiě)入和一次內(nèi)存操作。

優(yōu)化和實(shí)現(xiàn)細(xì)節(jié)

• 為避免不斷追加最終用盡磁盤(pán)空間，可以將存于磁盤(pán)的value分解成一定大小的段。當(dāng)文件達(dá)到一定大小時(shí)，可以在這些段內(nèi)進(jìn)行壓縮（丟棄重復(fù)的鍵，僅保留每個(gè)鍵最新的值），同時(shí)可以對(duì)多個(gè)段進(jìn)行合并，最后將壓縮后的value寫(xiě)入最新的段。

  
  
  
  

• 數(shù)據(jù)庫(kù)重新啟動(dòng)后，內(nèi)存的hash map丟失，可通過(guò)重新掃描整個(gè)文件重建map file。Bitcask通過(guò)將每個(gè)段的hash map快照存儲(chǔ)在磁盤(pán)上，加快hash map索引重建速度。

• 由于寫(xiě)操作是以嚴(yán)格順序的順序附加到日志中的，所以常見(jiàn)的實(shí)現(xiàn)選擇是只有一個(gè)寫(xiě)入器線程。數(shù)據(jù)文件段是附加的，或者是不可變的，所以它們可以被多個(gè)線程同時(shí)讀取。

特點(diǎn)總結(jié)

• 適合key數(shù)量不多，但每個(gè)key的value頻繁更新的情況。
• 范圍查詢效率不高。不適合查找值在一定范圍內(nèi)的場(chǎng)景。
• 不是所有的數(shù)據(jù)都可以用哈希函數(shù)套用的，也不是所有鍵值數(shù)據(jù)都能很好處理沖突問(wèn)題。

2. LSM樹(shù)存儲(chǔ)引擎

介紹

• LSM樹(shù)存儲(chǔ)引擎可用于無(wú)法將所有key放入內(nèi)存的場(chǎng)景。
• 根據(jù)key-value對(duì)的鍵順序進(jìn)行存儲(chǔ)。適用于查找值在一定范圍內(nèi)的場(chǎng)景。
• 代表性的應(yīng)用有：LevelDB, RocksDB, Hbase, Cassandra 等大多數(shù) NoSQL 數(shù)據(jù)庫(kù)。

基本實(shí)現(xiàn)

• LSM 樹(shù)由兩個(gè)或以上的存儲(chǔ)結(jié)構(gòu)組成，一個(gè)存儲(chǔ)結(jié)構(gòu)常駐內(nèi)存中，稱為內(nèi)存表（memtable）。另外一個(gè)存儲(chǔ)結(jié)構(gòu)常駐在硬盤(pán)中，稱為排序字符串表（SSTable）。
• 在內(nèi)存中維護(hù)順序結(jié)構(gòu)相比磁盤(pán)更加容易。常用數(shù)據(jù)結(jié)構(gòu)包括紅黑樹(shù)，AVL樹(shù)等。當(dāng)數(shù)據(jù)寫(xiě)入時(shí)，將其添加到內(nèi)存中的平衡樹(shù)數(shù)據(jù)結(jié)構(gòu)。
• 當(dāng)內(nèi)存表大于某個(gè)閾值（通常為幾兆字節(jié)）時(shí)，將其作為SSTable文件寫(xiě)入磁盤(pán)。這可以高效地完成，因?yàn)闃?shù)已經(jīng)維護(hù)了按鍵排序的鍵值對(duì)。新的SSTable文件成為數(shù)據(jù)庫(kù)的最新部分。當(dāng)SSTable被寫(xiě)入磁盤(pán)時(shí)，寫(xiě)入可以繼續(xù)到一個(gè)新的內(nèi)存表實(shí)例。
• 為了提供讀取請(qǐng)求，首先嘗試在內(nèi)存表中找到關(guān)鍵字，然后在最近的磁盤(pán)段中，然后在下一個(gè)較舊的段中找到該關(guān)鍵字。
• 有時(shí)會(huì)在后臺(tái)運(yùn)行合并和壓縮過(guò)程以組合段文件并丟棄覆蓋或刪除的值。

• 與使用散列索引的日志段相比，在SSTable合并段是簡(jiǎn)單而高效的，可使用歸并排序算法進(jìn)行合并。當(dāng)多個(gè)段包含相同的鍵時(shí)，我們可以保留最近段的值，并丟棄舊段中的值。

  
  

• 由于排序特性，不再需要保存內(nèi)存中所有鍵的索引。只需要一個(gè)內(nèi)存中索引來(lái)告訴您一些鍵的偏移量，它可以很稀疏。由于讀取請(qǐng)求無(wú)論如何都需要掃描所請(qǐng)求范圍內(nèi)的多個(gè)鍵值對(duì)，因此可以將這些記錄分組到塊中，并在將其寫(xiě)入磁盤(pán)之前對(duì)其進(jìn)行壓縮（下圖中的陰影區(qū)域所示） 。稀疏內(nèi)存中索引的每個(gè)條目都指向壓縮塊的開(kāi)始處。

  
  

優(yōu)化和實(shí)現(xiàn)細(xì)節(jié)

• 為避免數(shù)據(jù)庫(kù)重新啟動(dòng)后，內(nèi)存表數(shù)據(jù)丟失，可以在磁盤(pán)上保存一個(gè)單獨(dú)的日志，每個(gè)寫(xiě)入都會(huì)立即被附加到磁盤(pán)上。該日志不是按排序順序，因?yàn)樗奈ㄒ荒康氖窃诒罎⒑蠡謴?fù)內(nèi)存表。每當(dāng)內(nèi)存表寫(xiě)出到SSTable時(shí)，相應(yīng)的日志都可以被丟棄。
• 有不同的策略來(lái)確定SSTables如何被壓縮和合并的順序和時(shí)間。常見(jiàn)包括大小分級(jí)和分層壓縮。在大小分級(jí)壓縮中，較新的和較小的SSTable被連續(xù)合并到較舊和較大的SSTable。在分層壓縮中，鍵的范圍被分裂成更小的SSTables，而較舊的數(shù)據(jù)被移動(dòng)到單獨(dú)的“層級(jí)”，這樣壓縮可以逐步進(jìn)行并節(jié)省磁盤(pán)空間。
• 當(dāng)查找數(shù)據(jù)庫(kù)中不存在的鍵時(shí)，LSM樹(shù)算法可能會(huì)很慢：先檢查內(nèi)存表，然后將段一直回溯訪問(wèn)到最舊的段文件（可能必須從磁盤(pán)多次讀?。?，然后才能確定鍵不存在。為了優(yōu)化這種訪問(wèn)，存儲(chǔ)引擎通常使用額外的布隆過(guò)濾器。布隆過(guò)濾器只需占用極小的空間，便可給出鍵 “可能存在” 和 “肯定不存在”的判斷。從而可以提前過(guò)濾掉很多不必要的查詢，節(jié)省了大量的磁盤(pán)IO。
• Bloom過(guò)濾器是由一個(gè)長(zhǎng)度為N的01 數(shù)組組成的。首先將數(shù)組array每個(gè)元素初始設(shè)為0，對(duì)集合A中的每個(gè)元素w，做K次哈希，第i次哈希值對(duì)N取模得到一個(gè)index(i).即:

index(i) = Hash_i（w）% N

將array數(shù)組中的array[index(i)] 置為1.最終變?yōu)橐粋€(gè)這些元素為1的01數(shù)組。

特點(diǎn)總結(jié)

• 適合高吞吐寫(xiě)的場(chǎng)景。它通過(guò)將數(shù)據(jù)增刪改全部轉(zhuǎn)化為順序?qū)懭霃亩@著提高寫(xiě)的性能。
• 基于 LSM-Tree 分層存儲(chǔ)能夠做到寫(xiě)的高吞吐，帶來(lái)的副作用是整個(gè)系統(tǒng)必須頻繁的進(jìn)行 compaction ，寫(xiě)入量越大， Compaction 的過(guò)程越頻繁。而 compaction 是一個(gè) compare & merge 的過(guò)程，非常消耗 CPU 和存儲(chǔ) IO ，在高吞吐的寫(xiě)入情形下，大量的compaction操作占用大量系統(tǒng)資源，必然帶來(lái)整個(gè)系統(tǒng)性能斷崖式下跌，對(duì)應(yīng)用系統(tǒng)產(chǎn)生巨大影響，當(dāng)然我們可以禁用自動(dòng) Major Compaction ，在每天系統(tǒng)低峰期定期觸發(fā)合并，來(lái)避免這個(gè)問(wèn)題。
• LSM-Tree 的更新、刪除全部是通過(guò)增加新數(shù)據(jù)間接實(shí)現(xiàn)，那么 Key 值必然存在多版本，而且事務(wù)鎖的機(jī)制與 B-Tree 相比而言會(huì)寬松很多，而且鍵值重復(fù)很多，這也就導(dǎo)致了它不適合事務(wù)要求非常強(qiáng)的結(jié)構(gòu)化數(shù)據(jù)處理場(chǎng)景。

3. B樹(shù)存儲(chǔ)引擎

介紹

• B樹(shù)將數(shù)據(jù)庫(kù)分解成固定大小的塊或頁(yè)面，傳統(tǒng)上大小為4KB（有時(shí)會(huì)更大），并且一次只能讀取或?qū)懭胍粋€(gè)頁(yè)面。這種設(shè)計(jì)更接近于底層硬件，因?yàn)榇疟P(pán)也被安排在固定大小的塊中。

• 每個(gè)頁(yè)面都可以使用地址或位置來(lái)標(biāo)識(shí)，這允許一個(gè)頁(yè)面引用另一個(gè)頁(yè)面 —— 類似于指針，但在磁盤(pán)而不是在內(nèi)存中。我們可以使用這些頁(yè)面引用來(lái)構(gòu)建一個(gè)頁(yè)面樹(shù)

  
  
• 一個(gè)頁(yè)面會(huì)被指定為B樹(shù)的根；在索引中查找一個(gè)鍵時(shí)，就從這里開(kāi)始。該頁(yè)面包含幾個(gè)鍵和對(duì)子頁(yè)面的引用。每個(gè)子頁(yè)面負(fù)責(zé)一段連續(xù)范圍的鍵，引用之間的鍵，指明了引用子頁(yè)面的鍵范圍。
• 在B樹(shù)的一個(gè)頁(yè)面中對(duì)子頁(yè)面的引用的數(shù)量稱為分支因子。例如，在上圖中，分支因子是 6 。在實(shí)踐中，分支因子取決于存儲(chǔ)頁(yè)面參考和范圍邊界所需的空間量，但通常是幾百個(gè)。

基本實(shí)現(xiàn)

• 如果要更新B樹(shù)中現(xiàn)有鍵的值，則搜索包含該鍵的葉頁(yè)，更改該頁(yè)中的值，并將該頁(yè)寫(xiě)回到磁盤(pán)（對(duì)該頁(yè)的任何引用保持有效） 。如果你想添加一個(gè)新的鍵，你需要找到其范圍包含新鍵的頁(yè)面，并將其添加到該頁(yè)面。如果頁(yè)面中沒(méi)有足夠的可用空間容納新鍵，則將其分成兩個(gè)半滿頁(yè)面，并更新父頁(yè)面以解釋鍵范圍的新分區(qū)
• 該算法確保樹(shù)保持平衡：具有 n 個(gè)鍵的B樹(shù)總是具有 O(logn) 的深度。大多數(shù)數(shù)據(jù)庫(kù)可以放入一個(gè)三到四層的B樹(shù)，所以你不需要遵追蹤多頁(yè)面引用來(lái)找到你正在查找的頁(yè)面。
• B樹(shù)的基本底層寫(xiě)操作是用新數(shù)據(jù)覆蓋磁盤(pán)上的頁(yè)面。假定覆蓋不改變頁(yè)面的位置;即，當(dāng)頁(yè)面被覆蓋時(shí)，對(duì)該頁(yè)面的所有引用保持完整。這與日志結(jié)構(gòu)索引（如LSM樹(shù)）形成鮮明對(duì)比，后者只附加到文件（并最終刪除過(guò)時(shí)的文件），但從不修改文件。

優(yōu)化和實(shí)現(xiàn)細(xì)節(jié)

• 為了使數(shù)據(jù)庫(kù)對(duì)崩潰具有韌性，B樹(shù)實(shí)現(xiàn)通常會(huì)帶有一個(gè)額外的磁盤(pán)數(shù)據(jù)結(jié)構(gòu)：預(yù)寫(xiě)式日志（WAL, write-ahead-log）（也稱為重做日志（redo log））。這是一個(gè)僅追加的文件，每個(gè)B樹(shù)修改都可以應(yīng)用到樹(shù)本身的頁(yè)面上。當(dāng)數(shù)據(jù)庫(kù)在崩潰后恢復(fù)時(shí)，這個(gè)日志被用來(lái)使B樹(shù)恢復(fù)到一致的狀態(tài)
• 更新頁(yè)面的一個(gè)額外的復(fù)雜情況是，如果多個(gè)線程要同時(shí)訪問(wèn)B樹(shù)，則需要仔細(xì)的并發(fā)控制 —— 否則線程可能會(huì)看到樹(shù)處于不一致的狀態(tài)。這通常通過(guò)使用鎖存器（latches）（輕量級(jí)鎖）保護(hù)樹(shù)的數(shù)據(jù)結(jié)構(gòu)來(lái)完成。日志結(jié)構(gòu)化的方法在這方面更簡(jiǎn)單，因?yàn)樗鼈冊(cè)诤笈_(tái)進(jìn)行所有的合并，而不會(huì)干擾傳入的查詢，并且不時(shí)地將舊的分段原子交換為新的分段。
• 一些數(shù)據(jù)庫(kù)（如LMDB）使用寫(xiě)時(shí)復(fù)制方案，而不是覆蓋頁(yè)面并維護(hù)WAL進(jìn)行崩潰恢復(fù)。修改的頁(yè)面被寫(xiě)入到不同的位置，并且樹(shù)中的父頁(yè)面的新版本被創(chuàng)建，指向新的位置。這種方法對(duì)于并發(fā)控制也很有用。
• 我們可以通過(guò)不存儲(chǔ)整個(gè)鍵來(lái)節(jié)省頁(yè)面空間，但可以縮小它的大小。特別是在樹(shù)內(nèi)部的頁(yè)面上，鍵只需要提供足夠的信息來(lái)充當(dāng)鍵范圍之間的邊界。在頁(yè)面中包含更多的鍵允許樹(shù)具有更高的分支因子，因此更少的層次
• 通常，頁(yè)面可以放置在磁盤(pán)上的任何位置；沒(méi)有什么要求附近的鍵范圍頁(yè)面附近的磁盤(pán)上。如果查詢需要按照排序順序掃描大部分關(guān)鍵字范圍，那么每個(gè)頁(yè)面的布局可能會(huì)非常不方便，因?yàn)槊總€(gè)讀取的頁(yè)面都可能需要磁盤(pán)查找。因此，許多B樹(shù)實(shí)現(xiàn)嘗試布局樹(shù)，使得葉子頁(yè)面按順序出現(xiàn)在磁盤(pán)上。但是，隨著樹(shù)的增長(zhǎng)，維持這個(gè)順序是很困難的。相比之下，由于LSM樹(shù)在合并過(guò)程中一次又一次地重寫(xiě)存儲(chǔ)的大部分，所以它們更容易使順序鍵在磁盤(pán)上彼此靠近。
• 額外的指針已添加到樹(shù)中。例如，每個(gè)葉子頁(yè)面可以在左邊和右邊具有對(duì)其兄弟頁(yè)面的引用，這允許不跳回父頁(yè)面就能順序掃描。

特點(diǎn)總結(jié)

• 適合結(jié)構(gòu)化的數(shù)據(jù)的隨機(jī)讀取方面。其隨機(jī)檢索能力非常強(qiáng)，因?yàn)橐环矫嫠梢酝ㄟ^(guò)平衡樹(shù)的算法，通過(guò)少數(shù)幾次二分法思想的查找就可以在索引定位數(shù)據(jù)的位置；另外一方面它也不用擔(dān)心像哈希存儲(chǔ)引擎那樣需要考慮沖突的解決辦法，需要考慮哈希函數(shù)的健壯性問(wèn)題。對(duì)于數(shù)據(jù)存取的模式來(lái)講， B+Tree 則是將數(shù)據(jù)拆分為固定大小的 Block 或 Page, 一般是 4KB 大小，和磁盤(pán)一個(gè)扇區(qū)的大小對(duì)應(yīng)， Page 是讀寫(xiě)的最小單位，更適合固定大小的結(jié)構(gòu)化數(shù)據(jù)結(jié)構(gòu)的存取。
• 不適合高吞吐寫(xiě)的場(chǎng)景。主要原因就是它的插入、更新、刪除的這些操作都是建立在檢索的前提之下的，雖然這種操作更適合事務(wù)型的業(yè)務(wù)場(chǎng)景，但是對(duì)于事務(wù)型不是非常強(qiáng)，但是吞吐量巨大的場(chǎng)景并不適合。