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

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がリソースを大量に消費しているのがわかるよ。その混乱を減らすことで、書き込みが多いサーバーからもっとパフォーマンスを引き出せるようになるんだ。

まず、この記事は誤った主張をしていると思う。解決策は耐久性を保証していない。次に、良い同期コードは悪い非同期コードよりも優れているし、特にio_uringを使うと、良い同期コードを書く方がずっと簡単だ。現代のNVMeは速いし、同期IOでもほとんどのアプリケーションには十分だよ。非同期を考える前に、まずはアプリケーションが同期IOをうまく使えているか確認してね。

経験から言うと、Postgres(例えば)を使うと、個別の挿入やバッチ挿入でシステムの使用がひどくなるのは簡単だよ。NVMeドライブはしばしば極端に過小利用されていて、ボトルネックは全体のfsyncレイヤーなんだ。次に、耐久性はfsyncと同じだよ。クライアントは、両方のWAL書き込みが完了した場合にのみ成功が報告される。これはfsyncと同じ保証だけど、fsyncのボトルネックを回避することで、NVMeドライブの利点をより良く活用できるようになるんだ(I/Oをブロックするfsyncからリソースをシフトさせることができる)。そう、もっと管理が必要になるけど、今は同期fsync操作の代わりに2つの状態を維持する必要があるからね。でも、並列プログラミングのいいところは、もっと複雑だけど、同期ボトルネックを回避することでたくさんの利点が得られることなんだ。

はっきり言って、これはTigerBeetleでやっていること(とその理由)とは違うよ。例えば、私たちは耐久性を保つために、フルfsyncなしでコミットを外部化することは決してないんだ[0]。さらに、TigerBeetleが準備WALとヘッダーWALの両方を持つ理由は、性能ではなく正確性のためだよ。「合意ベースのストレージのためのプロトコル対応リカバリ」を参照してね[1]。最後に、TigerBeetleのリカバリはもっと複雑で、TigerBeetleのストレージ障害モデルに耐えるためにこれを行っているんだ。実際のコードはここで読めるよ[2]。Kyle KingsburyのTigerBeetleに関するJepsenレポートも素晴らしい概要を提供しているよ[3]。 [0] https://www.youtube.com/watch?v=tRgvaqpQPwE [1] https://www.usenix.org/system/files/conference/fast18/fast18... [2] https://github.com/tigerbeetle/tigerbeetle/blob/main/src/vsr... [3] https://jepsen.io/analyses/tigerbeetle-0.16.11.pdf

記事では、io_uringに切り替えたときに、 > スループットがほぼ即座に桁違いに増加した と主張しているけど、実際の話はそのすぐ近くにある。同期版は、耐久性のためにログへの書き込みの後に > 伝統的なfsync()呼び出しがあったんだ。彼らは同期APIとio_uringの性能を比較しているわけじゃない。fsyncを使うのと使わないのを比較しているんだ! さらに、非同期APIの問題は、 > データベースを有用にする耐久性の保証を失うことだと言っている。...データはまだカーネルバッファに残っていて、安定したストレージに書き込まれていないかもしれない。違う!それはfsyncを使わなくなったからだよ。コードが非同期であることとは関係ない。もし同期コードからfsyncを取り除いたら、桁違いのスピードアップが得られるかもしれないし、非同期版にfsyncを戻せば(io_uringについては詳しくないけど、「io_uring_prep_fsync」で可能なようだ)それは元に戻るだろう。どちらにせよ、io_uring版はまだ速いのかな? 可能性はあるけど、彼らがリンゴとオレンジを比較しているから、この記事からはわからないね。(他のコメントでも指摘されているように、彼らの二相コミット戦略も保証を提供していない。データが本当にストレージメディアにあることを確認したいなら、fsyncを避けることはできないよ。)

OPの本当のポイントは、fsync()は現代のハードウェアの文脈ではクソだってことだ。数千のI/Oリクエストが同時に飛んでいるかもしれないからね。過度な直列化を導入せずに、書き込みが永続ストレージにコミットされることを保証するために、もっと細かいメカニズムが必要だよ。

記事にあるTigerbeatleの動画リンクを見ることをおすすめするよ。そこでビットロットや「fsyncゲート」、Postgresが30年間fsyncを間違って使ってたことについて話してる。純粋にエンタメとしてもすごく面白いよ。

データが本当にストレージメディアにあることを確信したいなら、fsyncを避けることはできない。 それは違うよ。io_uringはO_DIRECT書き込みリクエストをちゃんとサポートしてるからね。キャッシュをバイパスするのは、ただフラッシュするのとは違う(それがfsyncのすること)。だから設計に影響が出る。でもデータベースエンジンは、io_uringの機能セットのターゲットだから、この複雑さを管理することが期待されてるんだ。

データベースが役立つための耐久性保証を失うことになる。... データはまだカーネルバッファに残っていて、安定したストレージに書き込まれていないかもしれない。 > いや!それはfsyncを使うのをやめたからだよ。君のコードが非同期であることとは関係ない。OPはio_uringのサブミッションキューにデータを投げ込んで、その時点で「完了」としていたように聞こえる(つまり、io_uringの完了キューが完了を示すのを待っていない)。だから、fsyncは必要だけど、成功を示す前にカーネルが書き込みを始めるのを待ってさえいなかったんだ。ある程度、io_uringには完了の概念があるから混乱していると思うけど、OPは彼らのデュアルWALデザインにも別の完了の概念を持っている(彼らが「完了」WALと呼ぶ2つ目のWAL)。でも、OPがio_uringの完了を無視したことから正しい理解を得られたかは疑問だね。彼らは5ステップの手順を作って、io_uringの完了を1つチェックするけど、もう1つは省略している。 > 1. 意図レコードを書き込む(非同期) > 2. メモリ内で操作を行う > 3. 完了レコードを書き込む(非同期) > 4. 完了レコードがWALに書き込まれるのを待つ > 5. クライアントに成功を返す 意図レコードのio_uring完了を待っていないことに注意してね(そして、fsyncや代替手段についての言及もまだないから、これも間違ってる)。独立したio_uring間には順序保証がない(OPは各WALに対して別々のio_uringインスタンスを使っていると言ってるし)、同じio_uring内でも完了に関する順序は限られている(IOSQE_IO_LINKは存在するけど、サブミッションの境界を越えることはできないから、ここでは機能しない。OPは作業を別々のタイミングで提出しているからね)。彼らはIOSQE_IO_DRAINを使う必要があると思うけど、これだと書き込みが効果的に直列化されることになる。だから、OPは実際に意図の書き込みの完了を待つ必要があるように思う。

この投稿にはいくつかの誤った推論があるね。コードがないと、どこで問題が起きたのか正確に特定するのは難しい。投稿で説明されているステップはこれだよ:1. 意図レコードを書き込む(非同期) 2. メモリ内で操作を行う 3. 完了レコードを書き込む(非同期) 4. 完了レコードがWALに書き込まれるのを待つ 5. クライアントに成功を返す もし4が正しく行われていれば、3は必要ないはずだよ。クライアントに返答する前に意図が耐久性を持つのを待てばいいんだから。WALがコミットされる前に操作を先行して実行する小さな利点があるかもしれないけど、私は懐疑的だし、4が正しく行われていないと思う。著者は記事にアップデートを追加したけど: > これはio_uringの完了キューを通じて追跡される - 完了レコードが安定したストレージに永続化されたことを確認してからのみ、成功レスポンスを送信する これだと、完了レコードの書き込み操作を提出して、その書き込みの完了キューを「レコードが耐久性のあるストレージにある」と誤解しているように聞こえるね。

  1. 意図を書く 2. 意図の書き込みを成功として使わない 3. 別の操作の完了を報告する。復元時:1. すべての意図を無視する 2. 対応する意図を持つ異なる操作のみを使う。この記事は混乱を招く情報が多すぎて、io_uringに関する「ほぼ」役立つ情報がたくさんあって、結局技術を傷つけてると思う。io_uringはクリーンでシンプルな例が欠けているし、また悪く説明された理論が出てきて、実際の内容が不足している。