より高速なSQLiteを求めて

• サーバーレス・エッジ環境で複数のSQLiteインスタンスを同時に動かすと、同期I/O待ちがテールレイテンシを悪化させるため、Helsinki大学とCambridge大学の研究者は、これを非同期I/Oとストレージ分離で緩和する方法を実験した
• Linuxのio_uringは、サブミッションキューとコンプリーションキューを通じて、I/O要求中でもアプリケーションが別の作業を続けられるようにし、スレッドのブロッキングを減らす基盤になる
• SQLiteでは、sqlite3_step()の実行中に必要なB-Treeページがキャッシュにない場合、POSIX read()のような同期I/Oでディスクを読み込み、I/Oが終わるまでスレッドが停止する
• 研究チームはPOSIX呼び出しだけを置き換えるのではなく、Rustベースの再実装プロジェクトLimboでVMとBTreeを非同期実行モデルに合わせて作り替えた
• ベンチマークでは、p999のテールレイテンシが最大100倍減少した一方で、p90・p99はSQLiteとほぼ同等であり、複数reader/writerの評価は今後の課題として残っている

---

SQLiteをより高速にしようとする研究

• University of HelsinkiとCambridgeの研究者は、“Serverless Runtime / Database Co-Design With Asynchronous I/O”で、SQLiteに非同期I/Oとストレージ分離を適用する方法を扱っている
• この論文は、RustベースのSQLite再実装プロジェクトLimboの基盤になっている
• ワークショップ論文のため分量は短く、焦点はサーバーレスとエッジコンピューティングに置かれている
• ポイントは、SQLite自体がすでに高速であっても、マルチテナント環境のテールレイテンシは実行モデルを変えることでさらに削減できる、という点にある

io_uringが減らすI/O待ち

• Linuxカーネルのio_uringは非同期I/Oインターフェースを提供する
• 名称はユーザー空間とカーネル空間が共有するリングバッファに由来し、両空間間のバッファコピーのオーバーヘッドを減らす
• アプリケーションはI/O要求を送信したあと、OSが完了を通知するまで別の作業を並行して進められる
• 動作の流れは次のとおり
  • io_uring_setup()システムコールで、サブミッションキューとコンプリーションキューという2つのメモリ領域を設定する
  • アプリケーションはサブミッションキューにI/O要求を入れ、io_uring_enter()でOSに処理開始を通知する
  • read()やwrite()のようにスレッドをブロックせず、制御をユーザー空間へ返す
  • アプリケーションは別の作業をしながら、コンプリーションキューを定期的にポーリングしてI/O完了を確認する

SQLiteクエリ実行における同期I/Oのボトルネック

• SQLiteアプリケーションはsqlite3_open()でデータベースファイルを開き、この過程でPOSIX openのような低レベルOS I/Oが呼び出される
• sqlite3_prepare()は、SELECTやINSERTのようなSQL文をバイトコード命令のシーケンスに変換する
• sqlite3_step()は、クエリが読み取る行を生成するか、実行が終わるまでバイトコード命令を実行する
  • 読み取る行があればSQLITE_ROWを返す
  • 文が完了するとSQLITE_DONEを返す
• 実行中にはバックエンドpagerが呼び出され、テーブルと行を表すB-Treeをたどる
• 必要なB-TreeページがSQLiteページキャッシュにない場合、ディスクアクセスが発生する
  • SQLiteはPOSIX readのような同期I/Oでページ内容をディスクからメモリへ読み込む
  • この間、sqlite3_step()はカーネルスレッドをブロックする
  • I/O待ち中にも並行作業を行うには、アプリケーション側でより多くのスレッドを使う必要がある

サーバーレス・エッジでSQLを埋め込みたい理由

• サーバーレスコンピューティングがエッジで実行され、データベースがクラウド環境にあると、サーバーレス関数とクラウドの間でネットワーク往復コストが発生する
• データをエッジに一緒に配置する方法もあるが、より良いアプローチとして、エッジランタイムの内部にデータベースを埋め込む方式が提案されている
• Cloudflare Workersはすでにこの形を実現しているが、公開しているのはKVインターフェースである
• KVはあらゆる問題領域に適しているわけではない
  • テーブル形式のデータをKVモデルに対応づけると、開発者体験が悪化する
  • シリアライズとデシリアライズのコストも発生する
• SQLのほうが適している場合があり、SQLiteは組み込みデータベースなのでサーバーレスランタイムに直接組み込める

SQLiteを単純にio_uringへ置き換えにくい理由

• SQLiteは従来のPOSIX read()とwrite()に基づく同期I/Oを使っている
• 小規模なアプリケーションでは大きな問題でなくても、1台のサーバーで数百個のSQLiteデータベースを動かすとボトルネックになりうる
• サーバー資源の利用率を最大化しなければならない環境では、同期I/Oが制約として働く
• SQLiteには並行性とマルチテナンシーの問題がある
  • I/Oが同期的かつブロッキングであるため、同じマシン上のアプリケーションが資源を奪い合う
  • その結果、レイテンシが増加する
• POSIX I/O呼び出しをio_uringへ単純に置き換えるのは難しい
  • ブロッキングI/Oを使うアプリケーションは、io_uringの非同期I/Oモデルに合わせて再設計する必要がある
  • SQLiteライブラリは、I/O進行中にアプリケーションへ制御を返せる必要がある
• 研究チームはSQLiteの一部呼び出しだけを置き換えるのではなく、RustでSQLiteを再実装し、io_uringを使うアプローチを選んだ

Limboの非同期実行モデル

• LimboはSQLiteをRustで再実装したプロジェクトで、VMとBTreeコンポーネントを非同期I/Oに対応するよう変更している
• 同期バイトコード命令は、非同期対応の命令へ置き換えられる
• たとえばNext命令はカーソルを進め、必要なら次のページを取得する
  • 従来の同期版では、ディスクI/Oが発生すると、ページを読み込んで呼び出し元へ返すまでブロックする
  • 非同期版では、NextAsyncが投入されたあと即座に戻る
  • 呼び出し元はその後、ブロックすることも、別の作業を行うこともできる
• 非同期I/Oはブロッキングをなくし、並行性を改善する
• 資源利用率をさらに高めるため、クエリエンジンとストレージエンジンを分離するストレージ分離も提案されている
• 関連説明としてDisaggregated Storage - a brief introductionも併せてリンクされている

ベンチマーク結果と残る疑問

• ベンチマークはマルチテナントのサーバーレスランタイムをシミュレートしている
• 各テナントは自身の組み込みデータベースを持つ設定である
• テナント数は1から100まで、10刻みで変更された
• SQLiteはテナントごとに別スレッドを使い、各スレッドでクエリを実行して測定した
• 実行クエリはSELECT * FROM users LIMIT 100で、1000回繰り返された
• Limboも同じ実験を行ったが、Rustコルーチンを使用した
• 結果として、p999でテールレイテンシが最大100倍減少した
• SQLiteのクエリレイテンシは、スレッド数の増加に応じて緩やかに悪化する形にはならなかった
• まだ作業は進行中であり、論文にはいくつか未解決の問いが残っている
  • Future Workでは、複数のreaderとwriterを含む追加ベンチマークを扱っている
  • 利点が顕著なのはp999以降に限られる
  • p90とp99の性能はSQLiteとほぼ同じである
• Limboのコードはオープンソースとして公開されている
• Limboは現在、公式のTursoプロジェクトであり、紹介記事も公開されている