自分だけのデータベースを作ってみる

• キー・バリュー・データベースの基本原理と実装過程を説明する
• ファイルシステムを使った永続保存と検索方式から始める
• データの追加、更新、削除処理時に非効率な問題が発生する
• Append-Onlyファイル、インデックス、ソート、セグメント圧縮などを段階的に加え、より効率的な構造へと進化する
• これらは最終的にLSMツリーのような現代的構造として知られ、実際の大規模システムで利用されている

---

導入: データベースを自分で作る始め方

データベースという概念がないと仮定し、独自のデータベースをどのように作れるかを段階的に探る。 最もシンプルな形のキー・バリューデータベースを直接実装する過程を見ていく

基本アイデア: ファイルを活用した永続保存

• データベースの目的は、データを永続的に保存し、後で効率的に検索すること
• 最も一般的な方法は、ファイルシステムを用いて各キー・バリューペアをファイルに記録すること
• データを保存するときは、たとえば $ db set 1 "Lorem ipsum" の形式でファイルに追記する
• データを検索するには、ファイル内のすべてのキー・バリューペアを順次確認し、目的のキーを見つける方法を使う
• 更新時は対象キーの値をファイル内で直接入れ替え、削除時はそのレコードをファイルから削除する方式である

改善点: 非効率なインプレース更新

• ファイル内データを直接更新・削除する方式は非常に非効率
• ファイルは単なるバイトストリームなので、途中データを変更すると、その後ろのデータをすべて移動させる必要がある
• たとえば特定のレコードを新しい値に変更する際、データ長が変わるとその後の内容をすべて移動しなければならない負荷が発生する
• データ量が増えるほど、速度と効率に大きな影響が生じる

改善1: Append-Onlyファイル構造

• 更新や削除時は既存データをそのまま残し、新しい記録だけをファイル末尾に追加する方式を採用する
• データが変更されるたびに新しいレコードを追加し、最新のキー値を検索するようにアルゴリズムを変更する
• 削除は特殊な"tombstone"値（NULLなど）で表示する
• 長所: 既存データの移動なしで効率的に記録可能
• 短所: 重複データや削除マーカーにより、ファイルが徐々に大きくなる
• 検索速度は依然遅い（全件走査が必要）

改善2: ファイルサイズ管理とコンパクション（compaction）

• ファイルが無限に大きくなる問題を解決するため、一定サイズ以上になったら新しいファイル（セグメント）に移行し、以前のファイルから不要データ（重複/削除済み）を除去してサイズを縮小する（コンパクション）
• コンパクション時は、必要なデータだけを残し、古いレコードや削除マーカーだけが残ったものを削除する
• 複数のセグメントファイルとして管理し、必要に応じてこれらをマージ（merge）する構造へ発展する

改善3: インデックス（Index）による高速検索

• キーごとにファイル内位置（オフセット）を格納したインメモリ（ハッシュテーブル）インデックスを作成して高速検索を可能にする
• 検索時はインデックスを優先して参照し、すぐにファイル内の該当位置を読む
• トレードオフ: 検索速度は速いが、インデックスがインメモリにあるため、キー数が増えるとメモリ上限に達する可能性がある
• インデックス管理のため、書き込み性能はやや低下する

改善4: ソート（Sorted String Table）とスパースインデックス

• キーを基準として常にソートされた状態で保存すると、**範囲クエリ（range query）**時に高い効率を実現できる
• ソートされた状態を利用すると、インデックスをすべてのキーではなく一部のキーに対してのみ（スパースインデックス）保持すればよい
• インデックスの密度を調整することで、メモリ使用量と検索効率の間でトレードオフを調整可能

実装方法: インメモリとディスク連携・永続性の確保

• 新規データは最初にソートされたインメモリリストに記録し、さらにappend-onlyファイルに記録してバックアップの役割を担う
• インメモリリストが大きくなると、これをオンディスクファイル（SST）としてソートして保存し、インデックスを更新する
• 参照時はまずメモリを確認し、なければインデックスを使ってディスクで検索する
• オンディスクファイルは**不変（immutable）**で管理し、更新・削除も新規データ追加で処理する
• 不要な重複/削除済みデータは定期的にコンパクションしてファイルサイズを管理する

LSMツリー（Log-Structured Merge Tree）の登場

• 上記の進化した構造は実際にLSMツリーという名称で広く使われている
• **インメモリ（memtable）とオンディスク（sorted string table, SST）**の組み合わせ構造で、迅速かつ大規模環境に適している
• LevelDB、Amazon DynamoDBなど、大規模なキー・バリュー・データベースシステムでコアデータ構造として利用されている
• デメリットと他構造（B-TreeベースのリレーショナルDBなど）との違いはあるが、大量トラフィック・拡張性の課題に対し高い性能を示している

結論

• 単純なファイルベースから始め、append-only、インデックス、ソート、セグメント圧縮、インメモリ-オンディスクの組み合わせを重ねて、より良いデータベース設計へと発展する
• データベースの内部動作と構造的な検討を、実装プロセスを通じて直接学習できる
• LSMツリー構造は現代の大規模データシステムで標準的な役割を果たしている
• 今後はリレーショナルデータベースのB-tree構造など、さまざまな方式をさらに探る余地が残る

[GN⁺]

Hacker Newsの意見

• この記事のデザインと例が本当に気に入った。読みやすい構成が印象的で、この練習自体もとても楽しい体験だ。何もない状態から始めると、自分がどれだけ知っているかを真に検証できる。
  • 私も以前は「データベースを直接作らないで、KVデータベースも使わず、ただSQLを使え」とせっかちな態度を示していた。だが、その考えさえ、実際にDBを設計したり、KVデータベースだけを使おうとしてSQLを避けていた結果、結局はSQLを粗雑に再実装したあとにようやく得られたものだった。実際に経験しながら学ぶ価値は明確にある。
  • 一つ残念なのは、例としてlorem ipsumを使っていることだ。せっかく集中しないでざっと読み流してしまう。実データの例のほうがずっと関心を引くだろう。その他は本当にすごい記事だ。
• 「LSMツリーはDynamoDBなどで標準的に使われるデータ構造で、非常に大規模な環境でも高いパフォーマンスを示す……毎秒8,000万リクエストまで可能」とされているが、少し誤解を招きやすい。LSMはノード単位のストレージエンジンで使われており、分散システム全体が8,000万RPSにスケールする過程は説明されていない。私の記憶では、もともとDynamo論文ではBerkeleyDB（B-treeまたはLSM）を使っており、2012年の論文で完全にLSMベースのエンジンに移行している。
• 記事一覧のいくつかのアーティクルをクリックしてみたが、デザインとアニメーションが本当に綺麗だった。
• 「Sorting in Practice」セクションの最初の例は壊れているように見える。説明文では、メモリ上でソートした後、ソート済みの状態でディスクに書き込むべきだと書かれているのに、実際の例ではディスクに書き込むときソートが崩れてしまっている。recapのflush例（2番目）も同様で、文言はソート済み状態でファイルに記録するとされている。
• 興味深い記事だった。最近、開発者の活動を時系列のキーバリューシステムとしてモデル化している。各開発者をキーに、コミットを値にする。似た問題に直面している：ログがすぐに増え、インデックスが重くなり、レンジクエリが遅くなる。セグメント圧縮（compaction）の際にどのデータを破棄するかどう決めるかが気になる。鮮度と保持期間のバランスを取るのは難しいと感じる。
• 過去4週間、トリプルストアを自分で作ることに夢中になっていた。この文章が少し早く出ていれば、もっと早く理解できた洞察がいくつかあっただろう。惜しい。
• もし著者がこの記事を見ているなら、サイトにRSSフィードを追加できるか知りたい。Feedlyに追加して読みたい。
• 自分のデータベースを作ってみたいなら、この無料オンライン書籍を必ずおすすめする。
  • 以前、誰かがbashの例でデータベースの基本概念を説明した記事（例："bashでDBを作る"）がこのサイトに紹介されていたのを覚えているが見つからない。誰かそのリンクを知っていたら共有してほしい。
• すでにトラフィックが多すぎて、サイトがアクセス不可になっている。
  • より速いデータベースが必要だろう。
• このように「ファースト・プリンシプル（First Principles）」から順を追って説明する進め方が本当に気に入る。この文章を追っていくと、各段階でどのような問題が発生し、またそれを解決する際にどのような追加問題が生まれるかを明確に理解できる。そうすることで、納得できる解決手法に到達できる。