摘要：?它是一個(gè)高性能的Key-Value數(shù)據(jù)庫(kù)。設(shè)計(jì)了完善的持久化機(jī)制，同時(shí)保證性能和安全性。能夠良好的支持范圍查詢，因?yàn)镵-V記錄就是按照Key來排序的。 下圖為寫入的流程： 可以看到主要的三個(gè)組成部分，內(nèi)存結(jié)構(gòu)memtable，類似事務(wù)日志角色的WAL文件，持久化的SST文件。

它是一個(gè)高性能的Key-Value數(shù)據(jù)庫(kù)。設(shè)計(jì)了完善的持久化機(jī)制，同時(shí)保證性能和安全性。能夠良好的支持范圍查詢，因?yàn)?span>K-V記錄就是按照Key來排序的。

下圖為寫入的流程：

可以看到主要的三個(gè)組成部分，內(nèi)存結(jié)構(gòu)memtable，類似事務(wù)日志角色的WAL文件，持久化的SST文件。

數(shù)據(jù)會(huì)放到內(nèi)存結(jié)構(gòu)memtable，一定條件下觸發(fā)寫到到SST文件。寫入WAL文件是可選的，用來恢復(fù)未寫入到磁盤的memtable。

下圖展示了讀取的層次：

memtable和SST文件組成數(shù)據(jù)的全集。之上是緩存層，緩存為提升查詢性能做了分片，底層都采用hash查詢，不同緩存結(jié)構(gòu)的區(qū)別在于熱點(diǎn)數(shù)據(jù)的替換邏輯。訪問數(shù)據(jù)庫(kù)時(shí)，都是訪問的打開時(shí)間點(diǎn)的view（我猜測(cè)一個(gè)key有不同時(shí)間戳的多條記錄）。除了直接查詢db，還提供了查詢快照的機(jī)制。直接訪問db時(shí)，會(huì)持有文件句柄，這樣多個(gè)SST文件合并時(shí)，已經(jīng)被合并但被訪問的文件就不能被刪除。而快照機(jī)制保證了訪問過程中文件能被刪除（我并未想明白如何做到的），不過打開期間被刪除的key的記錄還會(huì)在新合并的文件里存在。

memtable的結(jié)構(gòu)有幾種可選，本質(zhì)都是排序的結(jié)構(gòu)（為了支持范圍查詢）

其中之一是上圖的跳躍表，不了解跳躍表機(jī)制的讀者可以簡(jiǎn)單理解為有序支持近似二分查找的時(shí)間復(fù)雜度為log2(N)的結(jié)構(gòu)

另外一種是hash結(jié)合跳躍表，是按照key的前綴做hash，單獨(dú)訪問一個(gè)key時(shí)性能更好，范圍查詢性能會(huì)差些

WAL文件結(jié)構(gòu)如下圖，按照寫入的順序來存儲(chǔ)變長(zhǎng)的K-V，按照固定長(zhǎng)度來分組存儲(chǔ)（可能一個(gè)K-V跨多個(gè)分組）的目的是便于讀取

支持幾種SST文件結(jié)構(gòu)

上圖為按照多塊來存儲(chǔ)的結(jié)構(gòu)。每塊的K-V都是有序的，而多塊也是有序的。文件中包含元數(shù)據(jù)相關(guān)的信息，包括數(shù)據(jù)壓縮字典、過濾器等。會(huì)按照數(shù)據(jù)塊所屬的K-V范圍來創(chuàng)建索引，為提升查詢性能會(huì)給索引分片。

另外一種結(jié)構(gòu)是每個(gè)K-V來存儲(chǔ)。它的索引比較特殊，由hash結(jié)構(gòu)和二進(jìn)制查找緩存兩部分組成。依然按照key的前綴做hash，如果桶對(duì)應(yīng)的K-V記錄很少，則直接指向第一個(gè)key（有多個(gè)key屬于該桶）的記錄位置。如果屬于桶的K-V記錄多于16條，或者包含多于一個(gè)前綴的記錄，則先指向二進(jìn)制查找緩存（先二分查找），而后指向第一個(gè)key的記錄位置。

隨著K-V的寫入，會(huì)生成很多的SST文件，這部分文件需要被合并到一起。從而降低打開文件數(shù)量，并且移除已經(jīng)不存在的記錄。通?？梢耘渲脙煞N方式，通用合并（下圖左側(cè)）與level合并（右側(cè)）。

其中一個(gè)概念是level，可以簡(jiǎn)單理解成越老的數(shù)據(jù)在越高的level（也就是數(shù)據(jù)最初寫入到最低的level，level0就是memtable）。

我將通用合并簡(jiǎn)單理解為一種簡(jiǎn)單粗暴的合并，可以盡量降低寫磁盤的壓力，會(huì)增大讀取的壓力，臨時(shí)空間占用大。

一般多采用level合并的方式。每個(gè)level都有max大小，超出后會(huì)觸發(fā)本level與下一level的文件合并到一起。不同level的合并是可以并發(fā)執(zhí)行的。

對(duì)rocksdb做個(gè)總結(jié)。所有記錄在業(yè)務(wù)上是有序的，對(duì)key的查詢其實(shí)會(huì)執(zhí)行類似二分查找。持久化是通過寫入有序文件來實(shí)現(xiàn)的。高性能的寫入是通過先寫入內(nèi)存結(jié)構(gòu)來保證的（寫滿的內(nèi)存結(jié)構(gòu)刷到持久化文件）。提供了level機(jī)制對(duì)數(shù)據(jù)做分層，優(yōu)先查詢最新寫入的level來優(yōu)化查詢性能。