使用 WAL 構(gòu)建你自己的 KV 存儲

這篇文章將主要描述，如何使用我最近新開發(fā)的 WAL（Write Ahead Log）構(gòu)建屬于你自己的 KV 存儲引擎。

wal 地址：https://github.com/rosedblabs/wal

什么是 WAL？

wal，即 Write Ahead Log，通常叫做預(yù)寫日志，在一般的數(shù)據(jù)庫或者存儲系統(tǒng)中，是為了預(yù)防崩潰恢復(fù)而存在的，以傳統(tǒng)的 LSM 和 Bitcask 存儲引擎為例，數(shù)據(jù)首先進(jìn)入存儲引擎時(shí)，會先寫到 WAL 中，然后再更新內(nèi)存索引，LSM 一般是跳表，而 Bitcask 一般是哈希表，當(dāng)然你也可以選擇其他的內(nèi)存數(shù)據(jù)結(jié)構(gòu)。

這樣當(dāng)系統(tǒng)重啟時(shí)，會通過重放 wal 日志來構(gòu)建內(nèi)存數(shù)據(jù)結(jié)構(gòu)中的內(nèi)容。

在 Bitcask 存儲引擎中，有一個(gè)非常特殊的地方在于，預(yù)寫日志 wal 和實(shí)際存儲數(shù)據(jù)的日志文件，其實(shí)就是同一個(gè)文件，這樣便帶來一個(gè)極大的好處，那就是我們可以直接基于 wal 構(gòu)建出一個(gè)輕量、快速、簡單可靠的 KV 存儲引擎。

而在 LSM 存儲引擎中，會稍微復(fù)雜點(diǎn)，因?yàn)槠浜筮€有 SSTable 這一大塊內(nèi)容，所以本文將會簡單起見，只介紹下如何構(gòu)建 Bitcask 存儲，當(dāng)然如果你在 LSM 中使用了 Wisckey 這樣的優(yōu)化技術(shù)后，也可以使用 wal 來存儲 kv 分離之后的 Value Log 文件。

WAL 的由來

最開始想開發(fā)這個(gè)項(xiàng)目，其實(shí)主要是想到要重構(gòu) rosedb 和 lotusdb，然后這其中有很多重復(fù)的內(nèi)容，rosedb 的數(shù)據(jù)文件可以用 wal 來存儲，lotusdb 中 Memtable 對應(yīng)的預(yù)寫日志，和 Value Log 也可以用 wal 來存儲。

因?yàn)檫@幾種類型它們的存儲格式都是一樣的，即日志追加（append only）。所以我將這個(gè)公共的部分單獨(dú)提取出來，形成了一個(gè)新的項(xiàng)目。

WAL 的大致結(jié)構(gòu)

然后我們再來看一下 wal 項(xiàng)目的大致結(jié)構(gòu)，一個(gè) wal 實(shí)例，其實(shí)分為了多個(gè)文件，每個(gè)文件叫做一個(gè) Segment，這個(gè) Segment 具體有多大，是可以在啟動(dòng)時(shí)配置的，默認(rèn)是 1GB。

Segment 文件是分為了多個(gè)舊的文件，和一個(gè)當(dāng)前活躍的文件，新寫入的數(shù)據(jù)，會寫到活躍的 Segment 文件中。

一個(gè) Segment 文件內(nèi)部，又分為了 n 個(gè)等分的 block 塊，每一個(gè) block 塊的大小是 32 KB。block 寫的是變長的 chunk 數(shù)據(jù)，一個(gè) chunk 主要是有固定的 7  字節(jié)的頭部，以及其后的實(shí)際的用戶存儲的數(shù)據(jù)。每個(gè) chunk 都分為了四種類型，分別是 FULL、FIRST、MIDDLE、LAST，這主要是借鑒了 Leveldb/RocksDB 中的 wal 的設(shè)計(jì)。

數(shù)據(jù)在寫入到 wal 中后，會得到一個(gè) ChunkPosition，這個(gè) Position 是描述數(shù)據(jù)在 wal 中的位置信息，你可以直接使用這個(gè)位置信息從 wal 中通過 Read 方法讀取到寫入的數(shù)據(jù)。

如何基于 wal 構(gòu)建 KV 存儲

從前面的描述中，可以看出，wal 其實(shí)就是由多個(gè) Segment 文件組成，支持日志追加寫數(shù)據(jù)，并且可以從中讀數(shù)據(jù)的一個(gè)服務(wù)。

這幾天集中優(yōu)化了一下 wal 的讀寫性能，目前的讀寫速度很快，并且?guī)缀醪辉趺凑紦?jù)內(nèi)存。

有了這個(gè) wal 組件之后，我們再基于此構(gòu)建一個(gè) Bitcask 存儲引擎，將會變得極其的簡單。

首先，我們要做的就是選擇一個(gè)內(nèi)存數(shù)據(jù)結(jié)構(gòu)，比如 B-Tree、跳表、紅黑樹、哈希表等等都是可以的，只要是能夠存儲一個(gè) KV 值即可。

用戶寫入數(shù)據(jù)，實(shí)際就是先寫入到 wal 中，寫到 wal 之后，你會得到一個(gè)位置信息 ChunkPosition，然后把 Key+ChunkPosition 存儲到內(nèi)存數(shù)據(jù)結(jié)構(gòu)中即可。

然后是讀數(shù)據(jù)，直接根據(jù) Key 從內(nèi)存數(shù)據(jù)結(jié)構(gòu)中獲取到對應(yīng)的 ChunkPosition，然后根據(jù)這個(gè)位置從 wal 中讀取到實(shí)際的 Value 即可。

最后是重啟數(shù)據(jù)庫，需要調(diào)用 wal 中的 NewReader 方法，這個(gè)方法可以遍歷 wal 中的所有數(shù)據(jù)，并返回 Key+ChunkPosition 信息，你只需要把這個(gè)數(shù)據(jù)再次存放到內(nèi)存數(shù)據(jù)結(jié)構(gòu)中就可以了。

這幾個(gè)主要的步驟一完成，一個(gè)最基礎(chǔ)的 KV 存儲引擎就構(gòu)建起來了，當(dāng)然你還可以基于此做很多的完善和優(yōu)化。

好了，這就是基于 wal 這個(gè)組件來構(gòu)建你自己的 KV 存儲引擎的大致流程，大家可以自己去嘗試動(dòng)手寫一下，對自己的實(shí)戰(zhàn)能力提升應(yīng)該還是很大的。如果項(xiàng)目對大家有幫助的話，可以給個(gè) star 支持下哦！

有人任何問題都可以在群里交流，可以掃碼加入 rosedb&lotusdb 的社區(qū)群，有任何問題都可以進(jìn)行交流。