On the Performance of User-Mode Threads and Coroutines

原文はこちら。
The original article was written by Ron Pressler (Consulting Member of the Technical Staff and technical lead for OpenJDK’s Project Loom, Oracle)
https://inside.java/2020/08/07/loom-performance/

Project Loom の仮想スレッド (virtual thread) やGoのgoroutinesのようなコルーチン (coroutine) やユーザモードスレッドの議論では、パフォーマンスの話題になることがよくあります。ここで私が答えようとしている疑問は、ユーザーモードスレッドがOSスレッドよりも優れたアプリケーションパフォーマンスを提供するにはどうすればいいのか、ということです。

State of Loom
http://cr.openjdk.java.net/~rpressler/loom/loom/sol1_part1.html

共通の前提として、これはタスク切り替えコストに関係しており、ユーザーモードスレッドとコルーチンのパフォーマンス上の利点は、OSスレッドに比べてタスク切り替えのオーバーヘッドが低いことに起因しているというものがあります。なお、ユーザーモードスレッドとコルーチンは、この議論においては十分に似ているので、互換的に扱います。結果として、ユーザーモードのスレッドが(コールバックやCompletableFutureとかFlow/reactive streamsのような非同期合成を使う)非同期プログラミングに比べてどのくらいのタスク切り替えのオーバーヘッドが追加されるのか、タスク切り替えのコストが非同期プログラミングに比べて害を与えるのか、パフォーマンスを向上させるのか、という疑問が出てきました。しかし、見ての通り、最も一般的で最も有用なユースケースでは、ユーザモードのスレッド(またはコルーチン)のパフォーマンス上の利点は、タスク切り替えのコストとはほとんど関係がありません。そのパワーは他のところから来ています。

パフォーマンスは複雑な問題なので、最初にいくつかの定義を説明します。スループットは時間単位で達成されるオペレーションの数として定義されるパフォーマンス指標です。例えば、ロンドンからニューヨークにデータをフラッシュ・ドライブに入れて747で輸送する場合、レイテンシーは悪い(大きい)ですが、スループットはかなり良い(高い)場合があります。

もう一つの重要な概念は、インパクトと呼ばれるものです。これは、全体のパフォーマンスに対するオペレーションの貢献度であり、オペレーションを最適化することがどれだけ重要であるかを示す指標です。あるオペレーションがアプリケーションに費やされた総時間の 1%を占めるとしたら、その操作を無限に高速化しても、アプリケーションの総パフォーマンスは 1%しか向上しないので、この操作のインパクトは低いでしょう。インパクトはアプリケーションに大きく依存しますが、一般的なタイプのアプリケーションについて説明し、ユースケースでインパクトを分類します。

例えば、イテレータを書くのに便利なgeneratorというコルーチンのユースケースを考えてみましょう。

Generators
https://wiki.python.org/moin/Generators

generatorが整数をインクリメントするシーケンスを合計するコンシューマーに送信するものとした場合、タスク切り替えは個々の数を生成するタイミングでgeneratorとコンシューマー間で発生します。重要なのは、このシナリオは純粋な計算以外の何物でもなく、非常に短命であるということです。これを純粋な計算 (pure computation) のユースケースと呼ぶことにします。スループットは、1 秒間に合計される整数の数です。このシナリオでは、タスクの切り替え操作が非常に大きな影響を与えます。処理時間(数値をインクリメントして合計する)をゼロにすると、タスク切り替えのオーバーヘッドの影響は100%になります。

ここで、トランザクション処理 (transaction processing) と呼ばれる別のユースケースを考えてみましょう。このユースケースではサーバーはネットワーク上に到着するリクエストを待ち、それに応答します。リクエストが到着すると、サーバは何らかの計算を行い、ネットワーク経由で他の補助サービス(おそらくデータベース)にアクセスしてそれを処理します。つまり、別のサービスにリクエストを送信し、レスポンスを集め、集積した結果で最終的にクライアントに応答を返します。このシステムのスループットは、サーバが1秒間に処理する受信リクエストの数のことです。

リクエストが無期限に積み重なっていなければ、サーバは安定しているので、レスポンスレートはリクエストレートに等しくなります。スループットを分析するために、リトルの法則に目を向けてみましょう。

リトルの法則 / Little’s Law
https://ja.wikipedia.org/wiki/リトルの法則
https://en.wikipedia.org/wiki/Little%27s_law

リトルの法則とは、安定したシステムにおいて、同時並行性の平均レベルL (サーバーが同時に処理するリクエストの数)は、リクエストの平均レート λに各リクエストを処理する平均持続時間Wをかけたものに等しい、という法則です。

L = λW

システムは安定しているので、そのスループットはλに等しく、最大達成可能なλはシステムのキャパシティです。この法則は単純ですが、結果がリクエストの到着の分布に依存しないので、実際には注目に値するものです。

問題を単純化するために、以前と同様に、すべての計算がゼロ時間で行われると仮定し、そのコストが待ち時間Wを支配すると予想しているので、ネットワーク越しに補助サービスにアクセスするのにかかる時間だけを考慮してみましょう。ここでは、2つのニュアンスを解決しなければなりません。1つは、サーバーが並列処理が可能な複数のコアを使用している場合、それぞれを別のサーバーと考えることができます。そのため、一般性を失わずに、サーバーがシングルコアであると仮定します(確かにコアはネットワークインターフェースを共有しますが、この複雑さは無視します)。第二に、リクエストを処理する過程で、例えば、ネットワーク上で3つのサービスを使用しなければならない場合、それぞれが1ミリ秒で応答するのであれば、それらを並列に実行することで、レスポンスを収集するための合計レイテンシを3ミリ秒から1ミリ秒に減らすことができます。これにより、Wは3分の1に削減されますが、リモートサービスとの相互作用により、さらに3つのサブオペレーションが実行中に追加され、同時実行性のレベルであるLも3倍に増加し、2倍分は相殺されます。したがって、リトルの法則を使用するために、Wはすべての送信リクエストの持続時間の合計であると考えるべきです。そうすると、スループットは以下のようになります。

λ = L/W

タスク切り替えのインパクトを計算する準備ができました。Wはサービスリクエストのレイテンシの合計であり、ここでは平均値の話をしているので、 トランザクションあたりのサービス呼出しの平均数(ここではnと呼ぶことにします)にサービス呼出しの平均レイテンシ w をかけたもの、つまり以下のようになります。

W = nw

1つのコア上で複数のリクエストを同時に処理するためには、サービスからのレスポンスを待つ場合、別のトランザクションに切り替えるので、すべての発信コールは1つのタスク切り替えを伴います。タスク切り替えの平均レイテンシをt、サービスからのレスポンスの平均レイテンシをμとすると、w = µ + tW = n(μ + t) です。スループットλに対するタスク切り替えのインパクトtとは、タスク・スイッチングのコストが全くない場合にどれだけのキャパシティを得ることができるか、ということになります。

(L/n(µ + 0)) / (L/n(µ + t)) = n(µ + t)/nµ = (µ + t)/µ = 1 + t/µ

サービスを待つたびにブロックする単一の OS スレッドで各トランザクションを処理する場合、カーネルを使ったタスク切り替えが例えばt = 1us といった遅いオペレーションであり、サービスやネットワークが非常に高速で、サービスコールの平均レイテンシ µ が 20us であったとしても、タスク切り替えの影響は 1/20 になります。タスク切り替えを最適化することで期待できる最善の方法は、キャパシティを5%増加させることです。より一般的には、タスク切り替えの影響は、平均レイテンシ/平均待ち時間です。ネットワークIOの待機が関係している場合、タスク切り替えがあまり効率的でなかったとしても、この比率はかなり低くなる可能性があります。

明らかに、このようなシステムの容量を大幅に増加させるためには、t を下げることに焦点を当てるべきではありません。このやり方では、レイテンシ W をわずかに減らしてスループット λ を増加させるだけに過ぎないためです。その代わりに、同時に処理できるトランザクションの数である L を増加させることに焦点を当てるべきです。もし、単純なthread-per-request(リクエスト1個にスレッド1個)のプログラミングモデルを維持し、1つのスレッドで各トランザクションを処理するならば、Lは必要なアクティブスレッド数になります。ユーザーモードスレッドがどのように役立つかというと、OSがサポートできる数千のオーダーではなく、潜在的に数百万のユーザーモードスレッドでLを桁違いに増加させます(1000倍のキャパシティを期待してはいけません。計算コストを無視しているので、補助サービスのボトルネックにぶつかる可能性があるからです)。非同期プログラミングも同様に性能を向上させます。タスク切り替えのコストを削減するのではなく、同時に処理されるトランザクションの数であるLを増やすことでパフォーマンスを向上させますが、非同期プログラミングの場合、各トランザクションをスレッドで表現するのではなく、別のコンストラクトで表現しています。

それにもかかわらず、タスク切り替えのオーバーヘッドは依然として重要である可能性があります。N がトランザクションあたりのタスクスイッチの数であるとすると、W = nµ + Nt となり、タスクスイッチのスループットへの影響は以下の通りです。

Nt / nµ

サービス呼出しごとに1つのタスク切り替えを想定していたのでN = nでしたが、自由に使えるスレッドが非常に多い場合には、トランザクションを処理するために、メッセージを渡しあって互いに通信しながら、いくつかのスレッドを使うほうが都合がよいです。これにより、トランザクションあたりのタスク切り替えの件数はサービス呼出しあたりのタスク切り替えの件数をはるかに超える可能性があるため、タスクスイッチのコストを低く保つことは依然として良い考えです。これは重要なことですが、無邪気に考えるほどではありません。

純粋な計算に比べて、トランザクション処理はユーザーモードのスレッドやコルーチンの重要なユースケースであると考えています。そのため、Loomでは仮想スレッドのタスク切り替えコストを低く抑えるように努力していますが、念頭に置いているアプリケーションのパフォーマンスに対してこれが主たる貢献をするわけではなく、主たるパワーの源でもありません。とはいえ、対象とするトランザクション処理のユースケースの利便性とタスク切り替えのオーバーヘッドの間に衝突が生じた場合は、前者を優先します。その理由はここで明らかになったと思っています。

最後に、実装について少し触れておきます。ある言語でのコルーチンやユーザモードスレッドの実装の品質から別の言語に外挿できるものはほとんどありません。ある言語ではローカル変数へのポインタを許可していますが、他の言語では許可していません。ある言語では、代入のコストが低く隠せる一方で、他の言語ではコストがかかり、明示的な管理が必要になるかもしれません。また、これまで見てきたように、ターゲットとなるユースケースは様々です。例えば、あるジョブに参加しているすべてのコルーチンが CPU キャッシュに収まるように最適化するような設計は、(generatorのように)非常に多くのタスクが関与しており、タスクの切り替えによって常にキャッシュミスが起こるようなユースケースには最適ではないかもしれません。実装のメリットを判断するには、最適化しようとしているユースケースと、それが対象としている言語/ランタイムの固有の制約や強みを考慮して評価する必要があります。しかし、それは別の議論のテーマです。

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Google フォト

Google アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中