KVSを自作するぞい (1) - スタート

勉強のため、C言語でKVSを実装していきます。
ちなみに、筆者はC言語の経験があまりありません。(せいぜい、一つのファイルで完結する数百行のプログラムを書いたことがあるくらい。)

仕様としてはだいたい以下のようなことを考えています。

  • キー・バリューとも型はバイナリのみ対応。(構造化したデータを入れたかったらProtocol BuffersなりMessagePackなり使ってくれ)
    • キーやバリューの大きさの上限は未定。(実装の難易度に依存する。現状どちらも大きさはsize_tの大きさになっている)
  • マルチスレッドには対応しない。(そもそもマルチスレッドに対応するためには何をどのようにすればいいか理解してない)
  • サーバーとして機能を提供。
    • 別途、クライアント用のライブラリも作成する。
    • サーバーとクライアントのやりとりはTCP
  • 基本メモリ上で読み書きする。
    • 新しく書き込んでメモリ上限に達した場合はメモリ上のデータを(全部)ディスクに書き出す。
    • キーに対応するデータを読み出す際はまずメモリ上を探して、見つからなかったらディスクに探しに行く。(ディスクから読み込んだデータはメモリ上にキャッシュ)
  • メモリ上のデータ構造はハッシュテーブル。
  • ディスク上のファイルレイアウトは未定。(どうすればいいかわからない)

メモリ上でデータを探す際に使うインデックスはどうしようかと色々考えていましたが、この記事(Redis core implementation)によるとRedisは巨大なハッシュテーブルとして実装されているらしいのでそれに従いました。
まだ読んでいませんが、実装する上でこちらの記事(Virtual Memory technical specification)も勉強になりそうです。

ちなみに、ハッシュテーブルのナイーブな実装はほぼ終わりました。
次回はその辺りのことについて書こうと思います。

ソースコードGitHubにて公開中です。
yk-twww/mem-freeze