單機(jī)存儲引擎是一個(gè)研發(fā)門檻非常高的基礎(chǔ)組件鬼贱，開源的項(xiàng)目中吧秕，只有rocksdb是功能比較全面惨寿，應(yīng)用最為廣泛的邦泄，但隨著使用場景越來越廣，硬件條件也比rocksdb設(shè)計(jì)之初發(fā)生了翻天覆地的變化裂垦，現(xiàn)在企業(yè)服務(wù)器的內(nèi)存可以做到非常大顺囊，ssd的性能也有了飛躍提升，許多場景下蕉拢，rocksdb的讀性能距離理想表現(xiàn)有巨大的差距特碳。另一方面，最近幾年出現(xiàn)了非常多基于rocksdb構(gòu)建的分布式存儲系統(tǒng)晕换，但在一些功能的銜接上也會顯得生硬午乓。本文希望基于作者多年在推薦系統(tǒng)中使用kv存儲的經(jīng)驗(yàn)和思考，重新設(shè)計(jì)一套單機(jī)存儲引擎闸准，在保留rocksdb主要功能的基礎(chǔ)上益愈，達(dá)到理想的讀性能，并且能夠基于它更優(yōu)雅夷家、更低損耗地構(gòu)建分布式存儲系統(tǒng)蒸其。

零拷貝讀

Rocksdb現(xiàn)在每次讀都需要將結(jié)果拷貝一份，這是一個(gè)開銷比較高的操作库快，如果所有數(shù)據(jù)在memtable中都用share_ptr維護(hù)摸袁，查詢結(jié)果只需返回智能指針，這樣就可以減少一大筆開銷缺谴。只是使用方持有智能指針時(shí)但惶，需要注意內(nèi)部數(shù)據(jù)可能發(fā)生修改耳鸯。

自定義Value

Rocksdb支持使用方自定義MergeOperater，從而定制修改邏輯膀曾，但value和operate都是字符串县爬，許多邏輯需要先做反序列化，然后再計(jì)算添谊，再將結(jié)果序列化后輸出财喳，這對許多需求來說是非常低效的。對于一個(gè)完整存在于memtable的數(shù)據(jù)斩狱，沒必要把結(jié)果序列化存在內(nèi)存中耳高，可以讓用戶自己實(shí)現(xiàn)value在內(nèi)存中的結(jié)構(gòu)，并且正常情況下所踊，可以直接做原地修改泌枪，不必把operate序列化后，當(dāng)成一條kv寫進(jìn)去秕岛。零拷貝讀拿到的智能指針內(nèi)容碌燕，也是使用方自己定義的結(jié)構(gòu)〖萄Γ基于這個(gè)設(shè)計(jì)修壕，使用方可以自己實(shí)現(xiàn)類似redis的復(fù)雜數(shù)據(jù)結(jié)構(gòu)，預(yù)計(jì)內(nèi)存操作性能不會遜于redis遏考。

但rocksdb的Snapshot功能對此模式是一個(gè)麻煩慈鸠，如果要保留Snapshot功能，需要做許多額外設(shè)計(jì)灌具，這里就不詳述了青团。

在設(shè)計(jì)Value格式的時(shí)候，可以考慮網(wǎng)絡(luò)傳輸?shù)男士ч梗ㄟ^網(wǎng)絡(luò)傳輸一個(gè)復(fù)雜結(jié)構(gòu)一般是需要序列化和反序列化的計(jì)算開銷的壶冒，如果能把Value的定義封裝成一個(gè)類似ProtoBuf的庫，從db讀出到真正使用前截歉，都是以序列化的形式傳遞，在真正使用的時(shí)候再做反序列化烟零，這樣可以大大降低中間鏈路的開銷瘪松。

外置Write Ahead Log

現(xiàn)在主流的分布式kv存儲架構(gòu)，一般是在上層搭建paxos锨阿、raft之類的分布式有序隊(duì)列宵睦，然后每條隊(duì)列下面掛一個(gè)單機(jī)存儲引擎，這與rocksdb這類存儲引擎的WAL功能上有很大的重復(fù)墅诡，但要關(guān)掉WAL又需要做額外的開發(fā)壳嚎，在存儲引擎中專門維護(hù)一個(gè)Sequence Number，非常地生硬，所以筆者認(rèn)為保證數(shù)據(jù)可靠性的關(guān)鍵不在于WAL烟馅，而是Sequence Number说庭，存儲引擎要求每次寫入傳入Sequence Number，并且檢查它單調(diào)增郑趁，每次flush記錄下數(shù)據(jù)庫持久化部分的Sequence Number刊驴。這樣使用方就可以定制自己系統(tǒng)的有序隊(duì)列，通過Sequence Number和存儲引擎對齊寡润。

文件邊界對齊

rocksdb的文件文件切分只是根據(jù)大小限制捆憎，沒有做特殊策略，導(dǎo)致上下層的文件邊界并不對齊梭纹，compaction時(shí)躲惰，不在key range交疊范圍內(nèi)的數(shù)據(jù)也被迫參與，增加了寫放大变抽。諸如PebblesDB等項(xiàng)目注意到了這個(gè)問題础拨，將db做了切分，減少了這部分寫放大瞬沦，本文將給出一種設(shè)計(jì)太伊，對數(shù)據(jù)進(jìn)行更精細(xì)的切分，并且用B+樹將文件組織起來逛钻。

具體設(shè)計(jì)如下：除了第0層僚焦，其它第L層的文件不會與第L+1層的超過1個(gè)文件key范圍產(chǎn)生交疊，也就是第L+1層的所有文件的邊界曙痘，將第L層分割成若干區(qū)域芳悲，這樣第L層同一個(gè)區(qū)域里的文件，與第L+1層的一個(gè)文件边坤，就會形成一個(gè)被包含關(guān)系名扛，這個(gè)關(guān)系可以用一個(gè)B+樹來維護(hù)，如下圖所示：

compaction的過程與rocksdb有很大不同：compaction是以子樹為單位進(jìn)行的茧痒，當(dāng)發(fā)現(xiàn)某個(gè)子樹所有文件大小總和超過該子樹容量閾值后肮韧，子樹所有文件進(jìn)行一個(gè)compact，compaction的結(jié)果輸出到子樹根節(jié)點(diǎn)所在層旺订，compaction完成后整個(gè)子樹清空弄企，輸出時(shí)按照一定策略做文件切分（文件大小冯吓、冷熱區(qū)間切分）礁凡，如果發(fā)生文件切分叽奥，就要?jiǎng)h掉原節(jié)點(diǎn)膛薛，并插入新文件代表的節(jié)點(diǎn)菇夸。子樹compaction過程中胸完，子樹內(nèi)部禁止其它c(diǎn)ompaction妥凳，但可能發(fā)生flush贝攒，因此L0的文件可能會橫跨多個(gè)區(qū)域，這種情況可以使用硬鏈接圣猎，讓L0文件同時(shí)屬于多個(gè)節(jié)點(diǎn)就可以了士葫。

查詢過程也是比較清楚的，memtable查過之后样漆，就需要從B+樹定位到最上層文件的節(jié)點(diǎn)为障，然后逐層到對應(yīng)文件中查找。rocksdb的bloom filter是文件級別的放祟，最近有篇論文提出了全局過濾器鳍怨，和這個(gè)B+樹結(jié)合，每個(gè)子樹維護(hù)一個(gè)過濾器跪妥，或許會有驚喜鞋喇。

上面的設(shè)計(jì)能夠做到比較精細(xì)的切分，但是實(shí)現(xiàn)難度高眉撵，而許多場景冷熱數(shù)據(jù)并沒有那么強(qiáng)的局部性侦香，精細(xì)切分可能并沒有明顯效果，下面再給另外一種容易實(shí)現(xiàn)的設(shè)計(jì)：

一個(gè)db用B+樹管理多個(gè)region（與tikv的region類似）纽疟，每個(gè)region的規(guī)模不應(yīng)太大罐韩，每個(gè)region有獨(dú)立的memtable，除了L0其它每層只有一個(gè)文件污朽，region達(dá)到分裂條件散吵，或者由外部觸發(fā)，會進(jìn)行分裂蟆肆。

region是flush矾睦、compaction的基本單位，compaction的過程與rocksdb有很大不同：當(dāng)一層數(shù)據(jù)量超出該層目標(biāo)大小炎功，并不會立刻與下層做compact枚冗，而是會繼續(xù)等待上層數(shù)據(jù)溢出，當(dāng)L0溢出時(shí)蛇损，會把從L0往下赁温，所有連續(xù)的溢出層的所有文件和第一個(gè)沒溢出層做compact，這樣上層所有數(shù)據(jù)都被壓到了第一個(gè)沒溢出層淤齐，這個(gè)過程有點(diǎn)像漢諾塔束世。每個(gè)region的compaction是串行的，甚至db內(nèi)region數(shù)足夠多的情況下床玻，region內(nèi)的flush和compaction都可以串行，這樣許多邏輯都可以簡單很多沉帮。

更顯著的冷熱分層

Rocksdb各層數(shù)據(jù)的分布锈死，完全是由寫操作決定的贫堰，讀操作額外靠block cache和page cache加速，這樣設(shè)計(jì)實(shí)現(xiàn)相對容易待牵，但仔細(xì)分析就會發(fā)現(xiàn)其屏，許多場景下會導(dǎo)致額外開銷。

筆者認(rèn)為Block Cache是一個(gè)多余的設(shè)計(jì)缨该，從下層文件中讀到的數(shù)據(jù)偎行，可以重新放進(jìn)memtable，如果直到它變成冷數(shù)據(jù)被淘汰贰拿，都沒有被更新過蛤袒，那么就直接從memtable刪掉就可以了。這個(gè)改進(jìn)對自定義MergeOperater的場景尤為重要膨更，因?yàn)橐粋€(gè)key的operater可能分布在多個(gè)sst中妙真，現(xiàn)在rocksdb并沒有把FullMerge的結(jié)果緩存的功能，每次讀都需要執(zhí)行FullMerge的計(jì)算荚守，這是非常大的開銷珍德。

對于持續(xù)有寫入的熱點(diǎn)數(shù)據(jù)，rocksdb仍然會把它的舊數(shù)據(jù)往下層compact矗漾，這筆開銷是完全浪費(fèi)的锈候，對于熱點(diǎn)數(shù)據(jù)，應(yīng)該讓它長期留在memtable中敞贡，不產(chǎn)生compaction的io泵琳。一篇叫TRIAD的論文中提出了這個(gè)問題的優(yōu)化方案，每次flush只將冷數(shù)據(jù)寫到L0嫡锌，而熱數(shù)據(jù)寫入一個(gè)commit log中虑稼，不參與compaction，并且會留在memtable中势木。但我感覺論文的設(shè)計(jì)還是有問題的蛛倦，TRIAD為了減少WAL占用空間，每次flush要將所有熱數(shù)據(jù)寫到commit log中啦桌，我認(rèn)為用這個(gè)這個(gè)io開銷換存儲空間是不合算的溯壶，TRIAD可能只考慮了kv rewrite的情況，但像上文提到的自定義Value甫男，可能絕大多數(shù)寫入是增量的且改，一個(gè)value的大小可能是一個(gè)operate的上百倍，這樣一個(gè)value寫commit log的開銷是很大的板驳。因此改成每次flush只需要將保留在要被淘汰那些commit log的數(shù)據(jù)再寫到新的commit log里又跛，那些暫時(shí)安全的熱數(shù)據(jù)不需要落盤，這樣WAL多占用一些空間若治，進(jìn)程重啟時(shí)間更長慨蓝，換來io的大幅降低感混，這在線上生產(chǎn)環(huán)境中應(yīng)該是合算的。熱數(shù)據(jù)寫到commit log的同時(shí)礼烈，應(yīng)該往L0的文件中寫入這個(gè)key的刪除標(biāo)記弧满，這樣如果數(shù)據(jù)存在于中上層的文件中，這個(gè)刪除標(biāo)記可以避免這條數(shù)據(jù)在后續(xù)的compaction中產(chǎn)生io此熬。

多種存儲介質(zhì)的組合

使用持久化內(nèi)存優(yōu)化LSM Tree是近期存儲方向的熱門方向庭呜，從已經(jīng)發(fā)表的成果來看，收益非诚溃可觀募谎，所以未來優(yōu)秀的存儲引擎應(yīng)該能夠?qū)?nèi)存、持久化內(nèi)存峡碉、固態(tài)硬盤三種存儲介質(zhì)都充分利用近哟，使用方能夠基于不同的硬件組合，構(gòu)建各種性能和成本的存儲系統(tǒng)鲫寄。比如數(shù)據(jù)量少吉执，但讀壓力特別大的場景，可以使用純內(nèi)存地来，而需要更大的存儲量戳玫，但單位存儲量的讀寫壓力較低的場景，就可以選擇搭配持久化內(nèi)存和固態(tài)硬盤未斑。

Rocksdb的純內(nèi)存方案咕宿，是基于shm的LSM Tree，ops大約只有幾十萬蜡秽，在內(nèi)存存儲引擎里性能算是相當(dāng)?shù)土烁В④浀膄aster能達(dá)到上億。上文提到memtable的設(shè)計(jì)目標(biāo)是達(dá)到內(nèi)存存儲的理想性能芽突，所以純內(nèi)存模式只需要memtable就可以了试浙，當(dāng)然相比持久化存儲的memtable，純內(nèi)存模式可能需要LRU淘汰這類特殊邏輯寞蚌，所以它可能只是復(fù)用了memtable核心代碼的另一個(gè)存儲引擎田巴，并不能和持久化引擎互相切換。