RocksDB 的范圍查詢是如何優(yōu)化的?

MySQL 的存儲引擎除了最常用的是 InnoDB 引擎之外還有一個 MyRocks 引擎也經(jīng)常會用到，它是基于 RocksDB 開發(fā)的一套存儲引擎，比 InnoDB 性能要高出 N 倍。

在索引實(shí)現(xiàn)上，InnoDB 的索引使用 ?B+ 樹實(shí)現(xiàn)，B+ 樹的葉子節(jié)點(diǎn)上存儲了索引的 key，所有的葉子結(jié)點(diǎn)使用指針串了起來，非常易于索引的遍歷操作。比如下面這個語句（key1 字段加了索引）的范圍查詢就可以很好的利用這個特性

select key1 from t where key1 > 'abc'and key1 < 'def'

但是 MyRocks 的索引實(shí)現(xiàn)不一樣，MyRocks 的索引使用 LSM Tree 來實(shí)現(xiàn)，通常 LSM Tree 都不支持高效的范圍遍歷。原因在于 LSM Tree 是多層結(jié)構(gòu) —— 內(nèi)存里的 MemTable 和磁盤上的 7 層 SST 文件，范圍遍歷需要對內(nèi)存里的多個 MemTable 和這磁盤上的 7 層文件都需要讀取后 Merge 在一起才能拿到最終的范圍遍歷的結(jié)果。如果查詢范圍比較窄，其中 0 層文件可能需要全部讀取，其它 6 層通常只需要讀取一個文件，因?yàn)?0 層文件的多個文件 Key 之間是有重疊的，而其它 6 層中每層的多個文件之間是嚴(yán)格根據(jù) Key 范圍切割的。即使對應(yīng) SST 文件里面不存在目標(biāo)范圍的 Key，這樣的磁盤讀取還是不可避免。

我們知道 RocksDB 磁盤上的每個SST 文件里面里面都存了一個布隆過濾器，布隆過濾器的內(nèi)容通常是緩存（固定）在內(nèi)存中的。如果布隆過濾器能幫我們提前把查詢范圍過濾掉，判斷出目標(biāo) SST 文件是否存在目標(biāo)查詢范圍，這樣就可以減少磁盤讀取了。

但問題是布隆過濾器也是不存在范圍查詢的能力的，通常也只能判斷一下過濾器中是否存在某個 Key。為了解決這個問題，RocksDB 引入了 prefix_extractor ，它可以很好的解決這個難題。那這個 prefix_extractor 又是個什么高深的技術(shù)呢？其實(shí)也很簡單，它就是 prefix bloom filter。

這個「前綴布隆過濾器」 Add 進(jìn)來的 Key 不再是原來的 Key，而是 Key 的固定長度的前綴，它帶來的好處之一是布隆過濾器占用的空間變小了，壞處是誤判率也會跟著提高了一點(diǎn)。假設(shè)前綴長度是 3，那么把 abcd 這個 Key 加進(jìn)去后會認(rèn)為 abce 也在里面，因?yàn)樗鼈児蚕砹?abc 這個前綴。這省下來的空間可以用來存儲一個附加的數(shù)據(jù)結(jié)構(gòu) —— Key 前綴 的有序集合，它里面容納了所有的 Key 前綴的值。通過這個有序的 Key 前綴集合可以快速判斷出目標(biāo)范圍是否存在于當(dāng)前的 SST 文件中。

和布隆過濾器的數(shù)據(jù)一樣，這個 Key 前綴的有序集合也是緩存（固定）在內(nèi)存中的。因?yàn)閱蝹€ ?SST 文件的 Key 數(shù)量是有限的，前綴設(shè)置的比較短的話，對應(yīng)的的前綴數(shù)量也會非常少，消耗的內(nèi)存就可以忽略不計了。

聰明的同學(xué)可能想到了，這個前綴的長度取多少比較合適呢？要是用戶的索引字段值上自帶了前綴字符串，那切割出來的前綴有可能完全一樣，這前綴布隆過濾器豈不是要形同虛設(shè)么？