4.9万
TL;DR
Silkは、NUMAを考慮したワークスチール型ループ、I/Oのグラウンドトゥルースとしての io_uring、そして定常状態のホットパスにおけるヒープアロケーションゼロを特徴とする、スタックフルファイバーライブラリおよびスケジューラです。ClickHouse向けに構築したもので、最初に統合する予定なのは分散キャッシュです。
ファイバーとは？ Silkとは？
ファイバーは、スレッドに似た軽量なユーザー空間の実行単位です。スレッドとは異なり、ファイバーはスレッドが使うプリエンプティブなマルチタスクではなく、協調的マルチタスクに参加します。これによりファイバーは処理をブロックする代わりにyield（譲る）することができます。この特性は非同期I/Oに特に適しており、CPUが高速化し、クラスタが大規模化するにつれ、非同期I/Oは分散システムのボトルネックとなりつつあります。
スレッドとは違い、ファイバーには豊富な言語サポートエコシステムがありません。そこで我々はSilkを開発しました。SilkはC++ライブラリで、協調的なファイバースケジューラを提供します。その裏側にはCPUごとのスケジューラがあり、非同期I/Oには io_uring を使用し、ローカルキューが空になったコア間ではワークスチールを行います。高並列のネットワークI/O（察しの通り: ClickHouse）や、高並列のファイルI/O（もちろん: これもClickHouse）で卓越したパフォーマンスを発揮します。
名前は、1994年のMITによるワークスチール型スケジューラCilkへのオマージュです。Cilk自体は"silk" + Cのかばん語でした。Silkはその系譜に位置づけられることを意図しています。ファイバーを絹糸に喩えるメタファーは副次的な利点です。
既存のランタイムを使わず自作した理由は、必要としていた性質の組み合わせにあります:
- 数十ナノ秒でyieldするファイバー
- CPUトポロジを尊重するワークスチール
- 定常状態でのヒープアロケーションゼロ
io_uringを古いreactor設計にバックエンドとして後付けしたものではなく、I/Oのグラウンドトゥルースとして扱うこと
既存の選択肢はどれも4つすべてを満たしませんでした。そこで我々はすべてを満たすものを書き、ClickHouseで依存させるつもりであることを裏付けるハーネス、GDB拡張、BPFプロファイラも同梱して出荷します。
なぜファイバー、なぜこのファイバー、なぜ今か？
ClickHouseにはすでに並行モデルがあり、正しく機能しています。クエリ実行のように見えるエンジン部分——長時間動作するスレッドが実CPU仕事をこなし、スレッドごとのオーバーヘッドが数百万行の計算に償却されるような部分——には適切なモデルです。
しかしエンジンのそれ以外の部分にはSilkが必要です。ClickHouse Cloudでクエリを追跡すると、ますます長い柱となっているのは「1つのスレッドが大量の計算を行った」ではなく、「1万個の小さな操作が特定の順序で完了し、そのうち最も遅いものがテールを形作った」というものです。これはオブジェクトストレージI/O、分散キャッシュのルックアップ、レプリカ調整、HTTPファンアウトのパフォーマンス向上を狙うものです。いずれもI/Oバウンドで、高度に並列で、99パーセンタイルや99.9パーセンタイルで結果が決まるコンポーネントです。まさに、実行中のリクエスト1つのコストがカーネルスレッドではなくスタックポインタであるべきワークロードです。
OSスレッドやC++20のスタックレスコルーチンではなく、スタックフルファイバーを推す論拠は、要するにこうです: OSスレッドはデータベースエンジンにおける主要な並行単位として使うには高価すぎます。コンテキストスイッチあたり数マイクロ秒、スタックはキロバイト単位で、有限個しか作れず、カーネル自身がコンテキストスイッチで死にかけるまでです。スタックレスコルーチンは軽量ですが感染的です。サスペンションパス上のあらゆる関数を co_await 可能とマーキングする必要があり、コンパイラのヒープアロケーション省略最適化（HALO）は、コルーチンハンドルが実際のスケジューラキューにエスケープした瞬間、確実に動作しなくなります。スタックフルファイバーは、言語的な足跡なしに安価なサスペンションを提供します: 任意の関数がyieldでき、スタックは通常のスタックです。
スタックフルファイバーへの歴史的な反対論——AlibabaのPhoton論文にさかのぼる——はキャッシュエイリアシングです。スラブから割り当てたファイバーのスタックが同じL1キャッシュラインにマップされ、病的なエビクションを引き起こす可能性があるというものです。Photon論文はこれによるスケジューラレベルのコストを13%と測定しました。Silkの回答は、この問題はスラブ割り当てされたスタック特有の性質であり、一般にスタックフルファイバー自体の問題ではない、というものです。各ファイバーのスタックは、両側にガードページ付きでファイバーごとのプールから mmap されます。スラブもエイリアシングもありません。前提条件が存在しないため、我々のベンチマークで13%のコストは現れません。
Silkが自身のベンチマークで他勢と比較して提供するものは、おおよそ以下の通りです:
- クロスCPUワークスチールを伴うファイバーyieldあたり約3.6ナノ秒
io_uringピンポンで約7.6マイクロ秒- 動作構成で590万ファイルIOPS
- 1接続で
boost::asioの約15倍、高並列で約4倍のスループット - 32スレッドで
rseq経由、CPUごとのロックフリースタック性能はグローバルなロックフリースタックの最大2068倍
これらの数字を自分で試したいですか？ これらはリポジトリのベンチマークハーネス（./bb）から得られており、Silkと比較対象ツールに対してまったく同じワークロードを、制御されたCPUピニング、固定のウォームアップ期間、パーセンタイル追跡、そして誰でも再実行・検証できるJSON出力で実行します。この方法論こそが、Silkの自己表現において最も強力な単一の側面です。
Silkはどのように動作するのか？
スケジューラはCPUごとに1つのOSスレッドをピン留めして走らせます。各スケジューラスレッドは、CPUごとの ProcessorState を所有します。これには、境界のあるレディキュー（キャッシュラインアラインされたプロデューサー/コンシューマースロットを持つVyukov MPMCキュー）、非同期I/Oとタイマー満期用の io_uring リング、デッドラインで順序付けられたスリープツリー、ウェイクアップドアベルとしても機能するeventfdが含まれます。ファイバー関連のあらゆる操作（I/O発行、待機者の起床、新規ファイバーのスケジュール）は、可能な限りそれを発行したCPU上で行われます。CPUのレディキューが空になると、スケジューラスレッドはeventfd上の永続的な IORING_OP_POLL_ADD_MULTI 経由で起床し、CQリングをドレインし、期限切れのスリープを処理し、盗む仕事を探すサービスループを実行します。
ワークスチールはトポロジ対応です。起動時、Silkはシステムのトポロジを /sys から読み取り、CPUごとにスチール候補リストを構築し、推定コスト順にソートします: まずハイパースレッド兄弟（約1マイクロ秒）、次に同一ソケットのコア（約50マイクロ秒）、最後にクロスソケットのコア（約500マイクロ秒）です。CPUがスチールする際、コスト順に候補リストを辿り、ホットスポット化を避けるために各コスト階層内でランダムシャッフルします。この技術は「NUMA対応」スケジューラの具体的な実現であり、単に「別々のキューを持つ」ではなく、「どのCPUから盗むのが安いかを知っていて、それらを優先する」ということです。
トポロジ対応スケジューリングとは別に、Silkにはもう一つ重要なパフォーマンス特性があります: 定常状態のランタイムはヒープアロケーションを一切行いません。 ファイバースタックは、init時に mmap されて解放されないプールから供給されます。FiberFuture、IoFuture、SleepFuture、MultipleWaitState はすべて呼び出し元のスタック上に存在します。waitForMultiple の outstandingCount 会計処理は、状態がスタック上にあり、すべての進行中の信号が完了するまで関数がリターンしてはいけないからこそ存在します。すべてのコンテナはイントルーシブです: キューノード、サスペンド済みリストのエントリ、ロックフリースタックのフック、待機者テーブルのフックは、別々のアロケーションではなく、Fiber オブジェクト自体の中のフィールド です。1つのファイバーを同時に3つの異なるコンテナにエンキューすることができ、そのコストはヒープの追加0バイトです。同じことが SleepFuture にも当てはまり、キャンセルキューとデッドライン順ツリー用の独自の StackEntry と TreeEntry フィールドを持ちます。init後、ホットパスは一切アロケーションを行いません。他のライブラリよりも少ない、ではなくゼロです。
Silkに搭載した最後の重要なパフォーマンス特性: boost::asio は非同期操作ごとにアロケートします。C++20スタックレスコルーチンは、HALOが発火しない限りコルーチンフレームごとにヒープにアロケートします（実スケジューラでは通常発火しません）。プロダクショングレードの汎用非同期ランタイムの中で、ホットパスでのアロケーションゼロという特性は、ほぼ排他的にリアルタイム用途に工学的に設計されたシステムに属します: DPDK、Seastar、あるいはLinuxカーネル自体の一部です。Silkは意図的な設計選択によりそのカテゴリに属し、その結果、アロケータの挙動がSLAの一部となるような場所——メモリ圧下でのクエリ実行、カーネルバイパスパス、間違ったページフォルトでの malloc が期限逃しを意味するようなレイテンシ敏感なホットループ——にデプロイできます。高性能な分散データベースのすべての主要ホットスポットです。
設計上の選択にはどのようなものがあるか？
同期プリミティブは形状の点で教科書通りです。 FiberFuture のパック状態パターン、FiberSequencer のフラットコンバイニングループ、FiberMutex のロックアンドフラグ競合処理は、それぞれ、正しく実装されるよりもむしろ微妙な誤りに陥ることが多いパターンの正典的な実装です。すべてのメモリフェンスには対となる相手があります。すべてのCASは、必要最小限の順序を使い、それより強い順序は使いません。
プロダクションワークロードを処理するスケジューラではHALOは発火しません。 C++20スタックレスコルーチンの標準的な売り文句は「HALOによりゼロオーバーヘッド」です。HALOはコルーチンハンドルがスケジューラキューに決してエスケープしないことを要求します。実際のスケジューラはすべてこの条件を破るため、「ゼロオーバーヘッド」の主張はスケジューラが自明な合成ベンチマークでは成立し、スケジューラが実負荷を担う実アプリケーションでは崩れます。
park-then-wakeの競合処理がスループットの鍵です。 ファイバーをサスペンドするあらゆるプリミティブは同じ形状を持ちます: 楽観的に操作を試み、失敗時に待機者が存在することを示すフラグをセットし、ファイバーが完全にパークされた後に走るコールバック経由でファイバーをサスペンドし、そのコールバックでファイバーを待機者として登録し、見逃したウェイクアップを再チェックする。FiberFuture で注意深く読んだ後は、futex、mutex、sequencerもすべて素早く読めます。
同期層全体が1つのパターンです。 6つの同期プリミティブを700行で実装できるのは、それらがすべて「パック状態＋フラグCAS＋キューまたはテーブル＋再チェックするサスペンドコールバック」のバリエーションだからです。これは正しい抽象を見つけたということです。ライブラリの構築は、各プリミティブを意図的に前のプリミティブの上に構築しました。6つのプリミティブ、2つのパターン、1つの基盤となるサスペンドコールバック契約です。
公開APIは小さいです。 FiberScheduler には合計8つの動詞があります: initialize、destroy、run、schedule、yield、suspend、enqueue/release waiters、I/Oプリミティブです。ヘッダは400行未満で、APIリファレンスドキュメントのように読めます。スタックフル状態は実装詳細として扱われ、ユーザーが周りで構成するものとしては扱われません。
ベンチマークは再現可能です。 すべての比較はりんご対りんごで、すべての実行は1コマンドから再現可能です。silk対asio比較は、asioのより良い構成に対するsilkの比較です: asioのio_uringバックエンドを有効にしたら遅くなり、速くはなりませんでした。silk対fio比較は、psync ではなくfioの --ioengine=io_uring に対するsilkの比較です。
運用ツーリングはコードと同じくらい本格的です。 x86_64とaarch64の両方を扱う動作するGDB拡張、フレームレイアウトはBoost.Contextのアセンブリソースファイルから引き出しています。オンCPUおよびオフCPUサンプリング機能を持つBPFプロファイラ、非特権使用のためのケイパビリティゲート付き。各ワークロードのリファレンスツール（ネットワークI/OはASIO、ファイルI/Oはfio、TCPレイテンシはsockperf、HTTPはnginx）に対して比較を実行するベンチマークハーネス。GDB拡張にはCTest内に独自の統合テストがあります。我々は、著者自身以外にも役立つライブラリを出荷したいのです。
これはPhotonのキャッシュエイリアシングに対する反論です。 Photon論文は「スタックフルファイバーは遅い」の標準的な参照として何年も出回ってきました。測定された13%のスケジューラレベルミス率がスラブ割り当てされたスタックの産物であり、それ自体としてのスタックフルファイバーの産物ではないという議論、そしてガードページ付きプールからのmmapが完全に回避するという議論は、Silkが提示する形式では公表されていませんでした。ベンチマークがそれを裏付けています: Silkのyieldあたりのコストはナノ秒単位であり、13%のミス率のランタイムから予想されるマイクロ秒単位ではありません。
わかった、でも完璧ではないよね？
我々が作成したものを誇りに思っている一方で、限界と制約は認められます。
まず第一に、SilkはLinux専用です。io_uring、eventfd、ガードページ付きmmap、rseq、そしてモダンなLinuxのケイパビリティモデルに依存しています。macOS、Windows、または古いカーネル用の移植層はありません。これは意図的なスコープの選択であり、ターゲットはサーバクラスLinuxで、kqueueやIOCPをサポートすると、チームが持っていないユースケースのために表面積が倍増するためです。
第二に、スケジューラはプロセス全体のシングルトンで、FiberScheduler の静的メソッド経由でアクセスされます。同じプロセスに2つの分離されたスケジューラをインスタンス化する方法はありません。これによりAPIは使いやすくなりますが、テストシナリオや「レイテンシクリティカル向けに1つ、バッチ向けに1つ」といった高度な使い方は排除されます。マルチスケジューリングは意図的にライブラリの現在のスコープから外しました。後から追加すると破壊的なAPI変更になるためです。
第三に、ファイバーAPIはエントリポイントパラメータが64バイト（FIBER_PARAMETERS_SIZE）に収まることを要求します。それより大きいペイロードはヒープ割り当てしてポインタで渡す必要があります。これは一般的なケースでのファイバーごとのアロケーションの浪費を回避しますが、static_assert 経由でコンパイル時に表面化する実際の制約です。
そして最後に、ライブラリに同梱されているプロファイラは現在の形では汎用のオンCPUおよびオフCPUサンプリングプロファイラです。有用ですが、まだファイバーの識別を認識していません。ただしファイバーごとの帰属はロードマップにあります。アーキテクチャの基盤は整っています: Silkはどのファイバーが各スレッドで実行されているかを知っており（threadFiber TLS経由）、GDB拡張はサスペンド済みファイバーのスタックを外部からウォークできることをすでに示しており、BPFプロファイラは段階的なプローブ追加のために構造化されています。欠けているのは、TLSを読み取るためのBPFプログラム更新と、おそらくサスペンド/リジューム境界における1〜2個のUSDTプローブです。
ClickHouseはこれを最初にどこで活用するのか？
ファイバーがパフォーマンスを向上できる場所は多数ありますが、最初の可能性の高いターゲットは我々の分散キャッシュです。これはネットワークバウンドで高ファンアウトであり、単一のクエリが数百のキャッシュノードに触れる可能性があります。クエリレイテンシを決定するようなテールレイテンシに敏感です。すべてのキャッシュリクエストは単一のファイバーにきれいにマップされます: ファンイン、io_uring読み取り、ファンアウト、リターン。I/Oはすでにio_uring形状であり、ワーキングセットは長時間動作するクエリ作業ではなく短命なリクエストが支配しているため、Silkの定常状態でのゼロアロケーション特性はまさにここで最も可視化されます。最大の可視な勝利はテールで見られると予想しています: 99パーセンタイルと99.9パーセンタイルで、そこではOSスケジューラのジッタと数千の並行スレッド下でのアロケータの一時停止が支配的な要因であり、SilkのCPUごとのピニングとホットパスでのゼロアロケーションはカーネルとアロケータに動じる材料を与えません。我々はすでに内部ベンチマークでこの形状を目にしています: 1万の同時S3スタイルリクエストで、ファイバーエグゼキュータの99.9パーセンタイルは同等のスレッドプールエグゼキュータより約65%良好で、中央値スループットが同一でMinIOが両者のボトルネックである場合ですらそうです。分散キャッシュはSilkが最初に最もスムーズに走る場所です。エンジンの残りは別のタイムラインにあり、各統合が実装されるたびに書いていきます。
もっと見るにはどこへ？
Silkはgithub.com/ClickHouse/silkで公開されています。リポジトリにはライブラリ、ベンチマークハーネス、GDB拡張、BPFプロファイラ、そして最初に開く価値のある4つのドキュメント: docs/scheduler.md、docs/sync.md、docs/coroutines.md、docs/perf.mdが含まれています。この投稿のすべてのベンチマークはクリーンなチェックアウトから再現可能です。Linuxサーバクラスの C++システムで作業しており、ワークロードが厳しいテールレイテンシ要件を持つ高並列I/O（分散キャッシュ、オブジェクトストレージクライアント、RPCファブリック、HTTPファンアウト）のように見えるなら、Silkは叩かれることを歓迎する状態です。ドキュメントを読み、ベンチマークを走らせ、Issueを立ててください。ClickHouseが速く動くのは、その下の層が精緻だからです。Silkは次の下位層であり、我々が必要としていた層です。
最後に、SilkをClickHouseに織り込むにつれて、それがどのようにパフォーマンスを向上させたかについてさらに記事を執筆していきます。どうぞご期待ください！
