世界を動かす技術を、日本語で。

Linuxにおけるデータベースの非同期I/O

概要

  • io_uring を活用した高速な非同期I/Oによるデータベース設計の実験
  • Intent/CompletionのデュアルWAL 方式による高スループットと堅牢な耐障害性の両立
  • Zig言語 とPoroデータベースでの実装例
  • バッチ処理 とハードウェア並列性の最大活用
  • 従来の同期I/O前提の設計 を覆す新たなアーキテクチャへの示唆

io_uringによるデータベースI/Oの再発明

  • io_uring はLinuxカーネルの非同期I/Oインターフェース
    • アプリケーションとカーネル間で リングバッファ を共有
    • Submission Queue (SQ) で一括操作登録、 Completion Queue (CQ) で結果取得
  • 従来のI/O は逐次システムコール、ハードウェアの並列性を活かしきれない設計
  • NVMe SSD などの現代ストレージは数千の同時I/Oを処理可能
  • io_uring で複数I/Oをまとめて非同期送信、スループット大幅向上

データベースでの耐久性と一貫性の課題

  • 非同期I/O では、書き込み完了前に応答すると耐久性保証が損なわれる
  • fsync() による逐次同期は遅いが、耐久性のためには必要だった
  • io_uring でも、完了通知を待たずに応答すると障害時にデータ損失リスク

デュアルWAL設計の発想

  • Intent WAL :操作意図の記録(非同期)
  • Completion WAL :操作完了の記録(非同期)
  • プロトコル:
    • Intent記録 (非同期)
    • メモリ上で操作実施
    • Completion記録 (非同期)
    • Completionの書き込み完了を確認後 クライアントへ成功応答
  • リカバリ時 はIntentとCompletion両方ある操作のみ適用

実装上の工夫

  • Zig言語 による実験的実装(Poro、Klay)
  • Intent/Completionそれぞれ専用のio_uringインスタンス を用意
    • ヘッド・オブ・ラインブロッキング 回避
  • サーキュラバッファ によるバッチ書き込み
    • バッファ容量の75%到達で一括flush
  • CompletionEntry にintent参照・タイムスタンプ・CRC32チェックサムを付与
  • リカバリ手順
    • Intentログ全読込→Completionログ全読込→IntentとCompletionの対応づけ
    • CompletionのあるIntentのみ再適用
    • チェックサム検証でデータ整合性担保

バッチ処理とパフォーマンス

  • 2回の書き込みが必要 なため単一操作のレイテンシは増加
  • バッチ処理 では
    • Intent記録をまとめて送信
    • メモリ操作を並列実施
    • Completion記録もまとめて送信
    • Completion完了を一括待機
  • 2N回の同期書き込み→2回のバッチ送信+完了待ち に変換
  • 高負荷時は スループット10倍以上 の改善を確認
  • CPUコア数に比例してスケール、I/Oシリアライズのボトルネック解消

得られた知見

  • ハードウェア並列性 を最大限活用する設計の重要性
  • バッチ化 によるI/Oオーバーヘッドの劇的削減
  • 意図と完了の分離 で一貫性と高性能を両立
  • 高度なリカバリロジック でランタイムの単純化と信頼性向上

新しいデータベースアーキテクチャへの示唆

  • I/Oが安価かつ並列的 になると、従来の前提が崩れる
  • バッファプール管理、トランザクションスケジューリング、並行制御 も非同期I/O前提で再考可能
  • 同期I/O=耐久性の必須条件 という思い込みの打破
  • ソフトウェアアーキテクチャの刷新 でハードウェア性能を最大限引き出す可能性

この実験は、 io_uringデュアルWAL設計 による新しいデータベースアーキテクチャの可能性を示し、今後のストレージシステム設計に大きな影響を与える知見を提供するものです。

Hackerたちの意見

回復プロセスは「意図と完了の両方のレコードがある操作のみを適用する」ってことなんだけど、じゃあ意図のレコードを別にログする意味がわからないよね。完了がログされてなければ、意図は無視されるわけだし。だから、2つを一緒にログしてもいいんじゃないかな。おそらく意図のレコードは大きくて(キーと値のデータを含んでいる)、完了のレコードは小さい(意図のレコードのインデックスだけを含んでいる)んだろうね。完了のレコードの書き込みがディスクセクタに収まるから原子性が保証されるってことなのかな?

記事ではあんまり明確じゃないけど、私の考えでは、WALがディスクに書き込まれている間にメモリ内で更新できるから、メリットがあるんじゃないかな(フラッシュを待たずに進められるし)。だから、提示されているプロトコルには重要なステップが欠けてると思う:意図のレコードを書き込む(非同期)→ メモリ内で操作を実行 → 完了のレコードを書き込む(非同期)→ * * 意図と完了がディスクにフラッシュされるのを待つ * * クライアントに成功を返す

おそらく意図の記録は大きく(キーと値のデータを含む)て、完了記録は小さいと思うけど、必ずしもそうとは限らないよ。なぜなら、操作が意図ログに記録される順序とは異なる順序で完了することもあるからね。

「意図のレコードを書き込む(非同期)→ メモリ内で操作を実行 → 完了のレコードを書き込む(非同期)→ クライアントに成功を返す。回復時には、意図と完了の両方のレコードがある操作のみを適用する。これにより、一貫性が保たれつつ、はるかに高いスループットが実現される。」ってことは、クライアントがリクエストの成功を受け取ったとしても、その後すぐにシステムがクラッシュした場合、再生されるときにそのリクエストが記録されてない可能性があるってこと?それってACIDに違反しないの?

私が理解する限り、著者は非同期書き込みが同期書き込みのような保証がないことを理解していて…それから非同期書き込みを2つの非同期書き込みに分けているんだけど…それでも同期版と同じような保証はないよね。だから、2つの非同期書き込みが全く保証になるとは思えない。単に、1つの非同期書き込みよりも一貫性が良くなるだけで、任意の時間が経過することを強制しているからって感じがする。

これは、クライアントがリクエストに対して成功を受け取ったとしても、その後システムがクラッシュした場合、再生したときにそのリクエストが記録されていない可能性があるということですか? そうだね。OPは「意図の記録はカーネルバッファにただ座っているだけかもしれない」と言っているけど、同じ問題が完了記録にも当てはまる。だから、完了記録が耐久性のあるストレージに書き込まれるまで、クライアントに確認を発行することはできない。このブログ記事のポイントがよく分からないな。

誰かがこれに取り組んでいるのを見るのは嬉しいね。私はZigでio_uringを使ってシンプルなLSMツリーを作りたいと思ってたけど、まだ手を出せてないんだ。クラッシュ耐性のためにいつもこのアプローチを使ってる:- データ(WAL)ファイルに通常通り追加する。- WALの状態用にハッシュ+長さのような別の小さなファイルを持つ。- まずWALファイルに追加する。- WALファイルでfsync呼び出しを開始し、新しいハッシュ/長さファイルを別名で作成して並行してfsyncする。- 長さファイルを実際のものにリネームして完全に原子性を確保する。- メモリ内の状態をファイルに反映させて、書き込み関数から戻る。これとダブルWALのトレードオフについて知っている人がいれば興味あるな。もしかして、すべてにfsyncをかけるのは速い書き込みを維持するには遅すぎるのかな?このアプローチについては、興味がある人のためにこの記事から学んだよ:- https://discuss.hypermode.com/t/making-badger-crash-resilien... - https://research.cs.wisc.edu/adsl/Publications/alice-osdi14....

WALとツリーを統合することは可能だよ。追加専用のBツリー実装もいくつかあるし。 https://github.com/Incubaid/baardskeerder

これがよくわからない。2つ以上のWAL操作が1つよりも速いってどういうこと?(同期IOPSの倍になるじゃん)このデータベースには耐久性が全くないと思う。

fsyncは、ドライブが書き込み成功を報告するのを待つんだよね。小さい書き込みをたくさんやると、fsyncがボトルネックになっちゃう。これはコンテキストスイッチやパイプラインの問題なんだ。非同期でデータを書き込むと、この確認を待つ必要がなくなるから、2つの非同期リクエストをダブルで書くことで、システムのCPUコアをうまく使えるようになるんだ。I/Oレスポンスを待っている間にストールしないからね。こういう方法を使うと、10倍のパフォーマンス向上が見られることも珍しくないよ。もちろん、両方のレコードが書き込まれたか確認して、クライアントに報告する必要があるけど、それは非fsyncリクエストだから、システムにかかる負担はfsyncの書き込みとは違うんだ。耐久性はfsyncの書き込みと同じくらいあるしね。ほとんどのデータベースは30年、40年前に作られたものだから、その頃はHDDが主流で、NVMEドライブなんて夢のまた夢だったんだよね。でも、ほとんどのDBは今でも同じように動いていて、NVMEドライブをHDDみたいに扱ってる。HDDでこの操作をやると、パフォーマンスが2倍になるけど、NVMEドライブなら簡単に10万IOPS出せるからね。もしNVMEドライブでデータベースの書き込みを監視してたら、そういうドライブが全然活用されてないのがわかると思う。だから、NVMEの能力をうまく活かすための新しいデータストレージレイヤーを開発する動きが増えてるんだよ(古いHDD時代のボトルネックを回避しようとしてる)。

このスキームが全く理解できない。プロトコルは耐久性に違反してる。クライアントがサーバーから成功を受け取ったら、それは耐久性があるべきだから。しかし、完了のレコードは非同期だから、完了しないままサーバーがクラッシュする可能性がある。回復時には、サーバーは両方のレコードがある操作のみを適用するから、クライアントに成功したレコードは回復されないことになる。

真ん中の部分を見逃してると思うよ: ----------------- プロトコルはこうなる: 意図の記録を書く(非同期) メモリ内で操作を実行 完了記録を書く(非同期) クライアントに成功を返す ----------------- つまり、クライアントは両方のWALファイルが書き込まれるまで成功だと認識しない。目標は、最初の意図の記録でクライアントに早く応答を提供することではなく、システムがI/Oで待機しないようにすることなんだ。データベースに大量のデータを書き込むと、コアの書き込みではなく、I/O > fsyncがリソースを大量に消費しているのがわかるよ。その混乱を減らすことで、書き込みが多いサーバーからもっとパフォーマンスを引き出せるようになるんだ。

Hacker Newsで議論の続きを見る