etcdストレージエンジン: BoltDBとMVCC

etcdのデータ保存とバージョン管理を担当するストレージエンジンの内部構造を見ていきます。BoltDB（bbolt）のB+ツリーベースストレージメカニズムとMVCCの多バージョン管理を詳細に分析します。

1. BoltDB（bbolt）内部構造

1.1 B+ツリー概要

BoltDBはB+ツリーをコアデータ構造として使用します:

• すべてのデータがリーフノードに格納
• 内部ノードはキーのみ含み分岐決定に使用
• リーフノードがリンクリストで接続され範囲スキャンに効率的
• 平衡木ですべてのリーフが同じ深さ

1.2 ページタイプ

BoltDBは4種類のページタイプを使用します:

• Meta Page: データベースメタデータ。2つのメタページが交互に更新
• Freelist Page: 使用可能な（解放された）ページリスト
• Branch Page: B+ツリー内部ノード。キーと子ページポインターを格納
• Leaf Page: B+ツリーリーフノード。キーバリューペアまたはサブバケット情報を格納

1.3 トランザクションモデル

BoltDBはACIDトランザクションをサポートします:

• 読み取りトランザクション: 複数同時実行可能。スナップショットベース読み取り
• 書き込みトランザクション: 一度に1つのみ。データベース全体に対する排他ロック
• Copy-on-Write: 書き込み時に修正されたページをコピーして新しい位置に作成

// BoltDBトランザクション使用例
db.Update(func(tx *bolt.Tx) error {
    b := tx.Bucket([]byte("myBucket"))
    return b.Put([]byte("key"), []byte("value"))
})

1.4 Copy-on-Writeメカニズム

BoltDBの書き込みは既存ページを修正せず新しいページにコピーします:

1. 書き込みトランザクション開始
2. 修正が必要なページを新しい位置にコピー
3. コピーされたページで修正を実行
4. メタページを更新して新しいルートを指す
5. トランザクションコミット時に新しいメタページをディスクにfsync

2. MVCC詳細分析

2.1 Revision概念

etcdのMVCCで最も重要な概念はRevisionです:

• グローバル単調増加カウンター
• すべてのトランザクションごとに1増加
• 各revisionはmainとsubの2部分で構成

Revision = (main, sub)
main: トランザクション番号（グローバル増加）
sub: トランザクション内操作番号（0から開始）

例:
Put("a", "1")  -> revision (2, 0)
Txn:
  Put("b", "2")  -> revision (3, 0)
  Put("c", "3")  -> revision (3, 1)

2.2 Key Index

Key Indexはキー名からそのキーのすべてのrevision情報へのマッピングです:

// keyIndex構造（簡略化）
type keyIndex struct {
    key         []byte
    modified    revision
    generations []generation
}

type generation struct {
    ver     int64
    created revision
    revs    []revision
}

キーのライフサイクル:

1. キー作成（Put）-> 新generation開始
2. キー修正（Put）-> 現在のgenerationにrevision追加
3. キー削除（Delete）-> 現在のgenerationにtombstone追加、generation終了
4. キー再作成（Put）-> 新generation開始

2.3 BoltDB内のデータ保存

etcdはBoltDBのkeyバケットに以下のように格納します:

• キー: revisionバイト列
• 値: KeyValueプロトコルバッファ

BoltDB key bucket:
  key=(2,0) -> KeyValue{key="a", value="1", create_revision=2, mod_revision=2, version=1}
  key=(3,0) -> KeyValue{key="a", value="2", create_revision=2, mod_revision=3, version=2}

3. コンパクション

3.1 コンパクションの必要性

MVCCはすべてのバージョンを維持するためデータが増え続けます。コンパクションは指定されたrevision以前の古いバージョンを削除してスペースを回収します。

3.2 自動コンパクションモード

Periodicモード: 指定された時間間隔でコンパクション実行 Revisionモード: 指定されたrevision数分のヒストリーを維持

3.3 コンパクション過程

1. コンパクションrevision決定
2. Key Indexから不要なrevision削除
3. 削除されたキーのgeneration整理
4. BoltDBから該当revision以前のエントリ削除
5. scheduled compact revision更新

4. デフラグメンテーション

4.1 コンパクション後のスペース問題

BoltDBのCopy-on-Write特性のため、コンパクションでデータを削除してもディスクスペースは即座に返却されません。

4.2 デフラグメンテーション過程

1. 新しい一時BoltDBファイル作成
2. 既存データベースのすべての有効なデータを新ファイルにコピー
3. 既存ファイルを新ファイルで置換
4. ファイルサイズが縮小

4.3 注意事項

• デフラグメンテーション中に書き込みパフォーマンスが低下する可能性
• 一度に1メンバーずつ実行を推奨
• ピーク時間を避けて実行
• 一時的に追加ディスクスペースが必要

5. バックエンドバッチ最適化

5.1 書き込みバッチ

etcdはパフォーマンスのため複数の書き込み操作を1つのBoltDBトランザクションにバッチします:

• デフォルトバッチ間隔: 100ms
• デフォルトバッチ制限: 10000操作

5.2 パフォーマンスチューニングパラメータ

• --backend-batch-interval: バッチコミット間隔
• --backend-batch-limit: バッチあたり最大操作数
• --quota-backend-bytes: バックエンドDB最大サイズ

6. ストレージモニタリング

6.1 主要メトリクス

• etcd_mvcc_db_total_size_in_bytes: 現在のDBファイルサイズ
• etcd_mvcc_db_total_size_in_use_in_bytes: 実際の使用中サイズ
• etcd_debugging_mvcc_keys_total: 保存されたキー数
• etcd_disk_backend_commit_duration_seconds: バックエンドコミットレイテンシー

6.2 スペース不足対応

etcdバックエンドがquotaに到達すると:

1. NOSPACEアラームが発生
2. 書き込みリクエストが拒否
3. コンパクションとデフラグメンテーションを実行
4. etcdctl alarm disarmでアラーム解除
5. quota増加を検討

7. まとめ

etcdのストレージエンジンはBoltDBの安定的なB+ツリーストレージとMVCCの多バージョン管理を組み合わせて一貫性とパフォーマンスの両方を達成します。コンパクションとデフラグメンテーションによる適切なスペース管理が運用で重要です。