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

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

什么是 WAL？

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

這樣當系統(tǒng)重啟時，會通過重放 wal 日志來構建內存數(shù)據(jù)結構中的內容。

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

而在 LSM 存儲引擎中，會稍微復雜點，因為其后還有 SSTable 這一大塊內容，所以本文將會簡單起見，只介紹下如何構建 Bitcask 存儲，當然如果你在 LSM 中使用了 Wisckey 這樣的優(yōu)化技術后，也可以使用 wal 來存儲 kv 分離之后的 Value Log 文件。

WAL 的由來

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

因為這幾種類型它們的存儲格式都是一樣的，即日志追加（append only）。所以我將這個公共的部分單獨提取出來，形成了一個新的項目。

WAL 的大致結構

然后我們再來看一下 wal 項目的大致結構，一個 wal 實例，其實分為了多個文件，每個文件叫做一個 Segment，這個 Segment 具體有多大，是可以在啟動時配置的，默認是 1GB。

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

圖片

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

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

如何基于 wal 構建 KV 存儲

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

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

圖片

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

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

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

然后是讀數(shù)據(jù)，直接根據(jù) Key 從內存數(shù)據(jù)結構中獲取到對應的 ChunkPosition，然后根據(jù)這個位置從 wal 中讀取到實際的 Value 即可。

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

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

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