C++26でトイKVストア開発

LMDBやBoltDBを参考に、C++26でキーバリュー型DBのエンジンをゼロから実装します。ページ管理、B-tree、永続化、トランザクション、レプリケーションなど、実用的なKVストアの内部構造を段階的に組み上げていきます。

4件の記事

B+木をページに永続化する——ノードをバイト列にシリアライズしてPagerに載せる

オンメモリで実装したB+木を、Pagerが管理する4096バイト固定長のページへ永続化しました。ノードをリトルエンディアンの明示的なバイト列にシリアライズする設計、ページサイズから木の容量を逆算する方法、そしてプロセスを再起動してもキーが読み出せるところまでを実装した記録です。

std::variantでB+木のノードを表現し、分割アルゴリズムを実装する

LMDBやBoltDBと同じB+木を、まずはディスクに触れずオンメモリで実装しました。std::variantによるリーフ/内部ノードの表現、CLRSの「最小次数」に基づく容量設計、そして挿入時にオーバーフローしたノードをボトムアップで分割していくアルゴリズムを解説します。

固定長ページとpread/pwriteでファイルI/O層を作る——ストリームの共有シーク位置を避ける設計

LMDBやBoltDBのようなB-treeベースのKVストアエンジンを支えるページ管理層Pagerを実装しました。ファイルを4096バイト固定長のページの並びとして扱い、std::fstreamのシーク位置を共有しない設計にするため、あえてPOSIXのpread/pwriteを使った理由をまとめます。

std::expectedで返すオンメモリKVストアを実装する——例外を使わずに「キーが無い」を表現する

LMDBやBoltDBを参考にC++26でキーバリュー型DBエンジンをゼロから実装するプロジェクトの第一歩として、std::unordered_mapをラップしたオンメモリのKVストアを実装しました。「キーが見つからない」という日常的に起こる失敗を例外ではなくstd::expectedで表現する設計と、その上に載せた簡易CLIを紹介します。