RustでMini-KVを実装してCrash Consistencyを検証してみた

Posted at 2026-02-27

はじめに

バッチ処理やタイマーベースの同期でどこまでスループットを改善できるのかを実験的に検証してみました。

今回作った Mini-KV は、プロダクション用途ではなく、以下の1つの問いに答えるための実験システムです：

fsyncの頻度とバッチングは、スループット・レイテンシ・耐久性にどう影響するのか？

アーキテクチャ

Mini-KVの構造はシンプルです。

┌─────────────────┐     ┌─────────────────┐     ┌─────────────────┐
│    put(key,val) │────▶│   ログへ追記    │────▶│  インデックス更新│
└─────────────────┘     └─────────────────┘     └─────────────────┘
                                 │
                                 ▼
                          ┌──────────────┐
                          │   fsync?     │
                          │ • Always     │
                          │ • Batch(N)   │
                          │ • Periodic(T)│
                          └──────────────┘

Append-only ログ: すべての書き込みを1ファイルに追記
オンメモリインデックス: HashMap<key, offset> でO(1)ルックアップ
リカバリ: 起動時にログを全スキャンしてインデックスを再構築
クラッシュ検出: CRC32 + 長さプレフィックス + 不完全書き込みのトランケーション

レコードフォーマット

┌────────────┬────────────┬──────────┬────────────┬────────────┐
│ key_len(4) │ val_len(4) │ key(K)   │ value(V)   │ crc32(4)   │
└────────────┴────────────┴──────────┴────────────┴────────────┘

整数はすべてリトルエンディアン。CRC32はそれより前のすべてのバイトをカバーします。

同期戦略の比較

3つの戦略を実装しました。

モード	動作	耐久性の保証
`Always`	書き込みごとにfsync	データロスウィンドウ = ゼロ（OSおよびハードウェアの保証に依存）
`Batch(N)`	N回書き込むごとにfsync	クラッシュ時に最大N-1件のロスあり
`Periodic(T)`	Tミリ秒ごとにfsync	最大Tミリ秒分の書き込みロスあり

実験環境

CPU: Intel Core i7-11800H @ 2.30GHz（8コア/16スレッド）
ディスク: WD_BLACK SN770 1TB NVMe SSD（理論値: Read 5,150 MB/s / Write 4,900 MB/s）
RAM: 32GB DDR4
OS: Windows 11 / NTFS
言語: Rust 1.70+

プラットフォームに関する注意

今回の測定はすべて Windows 11 + NTFS 上で行いました。この環境では File::sync_all() が FlushFileBuffers にマップされます。NTFSはフルデータジャーナリングではなくメタデータジャーナリングを採用しており、書き込み順序の保証はext4などのLinuxファイルシステムとは異なります。ext4、APFS、または他のファイルシステム上では挙動が異なる可能性があります。

このNVMe SSDはfsyncレイテンシが非常に低く（実測 ~276μs）、ソフトウェアオーバーヘッドの差異を可視化しやすい環境です。HDDやSATA SSDではディスクレイテンシが支配的になり、これらの差異が見えにくくなります。

パフォーマンス測定結果

スループット比較（128Bレコード、10,000件の書き込み）

モード	スループット (ops/sec)	Alwaysとの比較	P50レイテンシ	P99レイテンシ
Always fsync	3,387	1x	276μs	519μs
Batch 100	167,884	49.6x	1.6μs	292μs
Batch 1000	373,749	110.3x	1.5μs	6μs
Periodic 10ms	334,926	98.9x	1.6μs	12μs
Periodic 100ms	360,762	106.5x	1.6μs	13.4μs

耐久性を100ms緩和するだけで、スループットが110倍向上します。

数理モデルで理解する

変数を定義します：

T_write = 1レコードをページキャッシュへ書き込む時間（≈ 1.5μs）
T_fsync = ディスクへfsyncする時間（≈ 276μs）
N = バッチサイズ

スループット:

Throughput = N / (N × T_write + T_fsync)
           = 1 / (T_write + T_fsync/N)

P99レイテンシの分岐:

Batch Nの場合、1/N の割合の書き込みがfsyncを引き起こす
1/N ≥ 0.01（N ≤ 100）→ P99はスローパス（≈ T_fsync）に入る
1/N < 0.01（N > 100）→ P99はファストパス（≈ T_write）に入る

これが以下を説明します：

Batch 100のP99 = 292μs（スローパス）
Batch 1000のP99 = 6μs（ファストパス、fsync書き込みはP99.9以降）

双峰性のレイテンシ分布

Batch 100では99%の書き込みが1.6μsで完了しますが、残り1%はfsyncのため292μsかかります。これがバッチングのテールレイテンシコストです。

一方、Periodic 10msは334K ops/secを達成しつつ、P99が12μsと安定しています。双峰性分布がないのが大きな利点です。

クラッシュ一貫性の検証

パフォーマンスだけでなく、実際のクラッシュ時にデータがどれだけ保護されるかを実験的に検証しました。

テスト手法

子プロセスが10,000件のレコードを書き込む
親プロセスが「durable index（永続化確認済み件数）」がランダムな目標値（2000〜8000）に達するまで待機
親プロセスがSIGKILLを送信（プロセスの強制終了をシミュレート）
子プロセスが再起動してリカバリし、復元されたレコード数をカウント
コア不変条件の検証: recovered ≤ durable_at_crash
（durable_at_crash = fsync成功後にAckされた書き込みの件数）

結果

モード	試行回数	平均Durable	平均Recovered
always	10	4,838	4,839
batch_100	10	4,780	4,864
periodic_100ms	10	10,000	10,000

すべてのモードでデータ破損ゼロを確認。CRC32によるインテグリティチェックが正しく機能し、不完全なレコードは一切読み込まれませんでした。

CRCの意味についての注意

CRC32は破損の検出を提供しますが、論理的一貫性の保証ではありません。具体的には：

✅ Torn write（途中で中断された書き込み）の検出
❌ 書き込みの並べ替え（Reordered write）は防げない
❌ 上位レイヤーの意味的エラーは防げない

WALの整合性保証はCRCだけで成立しているわけではありません。

まとめ：何を学んだか

1. fsyncはボトルネック——ただし「帯域」ではなく「レイテンシ」が原因

各fsyncのコスト: ~276μs（NVMe）
373K ops/sec × 128B = 47.8 MB/s（ディスク理論値の約1%）
128Bの小レコードワークロードではレイテンシバウンド。4KBなどの大レコードになると帯域制約が支配的になり、この特性は変わる可能性がある。

2. バッチサイズがスループット/レイテンシのトレードオフを制御する

Batch  100: 167K ops/sec, P99 = 292μs  (双峰性あり)
Batch 1000: 373K ops/sec, P99 = 6μs    (双峰性なし)

3. 時間ベース同期がバランス最良

334K〜360K ops/sec、安定したP99（12〜13μs）
双峰性分布なし

4. シンプルなWALでクラッシュ一貫性は実現できる

不変条件: recovered ≤ durable_at_crash

50回以上のクラッシュテストですべてのモードでこの不変条件が成立。

5. 耐久性とパフォーマンスのトレードオフ

モード	スループット	ロスウィンドウ
Always	3.3K ops/sec	ゼロ
Batch 1000	373K ops/sec	最大999件
Periodic 100ms	360K ops/sec	最大100ms分

今後の課題

4KBレコードのベンチマーク（帯域制約のテスト）
O_DIRECTモード（ページキャッシュバイパス）
Group commitの実装
クロスプラットフォーム比較: ext4 vs NTFS vs APFS
クラッシュ一貫性のプロパティベーステスト
HDDやSATA SSDでのベンチマーク

おわりに

数字を可視化し、バッチングや時間ベース同期がどのようにそのコストを分散させるかを実験で確認できました。

プロダクションのデータベースが「耐久性のレベル」を設定可能にしているのは、こうしたトレードオフが現実に存在するからです。PostgreSQLの synchronous_commit、RocksDBのwrite bufferなど、多くのシステムが本質的に同じ問題を解いています。

ソースコードはGitHubで：https://github.com/otmojo/mini-kv

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up