標準的な MapReduce ジョブを 400 ワーカーで実行。
（Google Cloud Storage から読み取り、GroupByKey を適用し、Cloud Storage に書き込み）
ストラグラーを例示するために、動的なワーク リバランシングは無効化されている。
X 軸 : 時間（最長 20 分）、Y 軸 : ワーカー
ストラグラーにはさまざまな原因があります。たとえば、特定のワーカーが異常に遅いことや、データの特定部分の計算負荷が特に高いこと、入力の不均等な分割によってさまざまな部分ごとにデータ量が著しく異なることが挙げられます。
このうち最後のケースは、ファイルを処理する際は滅多に発生しませんが、キーバリュー ストアなどの複雑な入力ではかなりの頻度で発生します。入力を均等に分割するためのデータ分布に関する十分な情報が前もって得られないからです。
別のタイプの問題として、データ量は均等に分割されているものの、処理の複雑さが一様ではないという場合があります。
たとえば、コード変換されるビデオのファイル名を含むファイルを入力として受け取るパイプラインがあるとしましょう。負荷が均等に分散されたワークフローを実現するためには、各ワーカーに同じ数のビデオを割り当てるのは適切ではありません。ビデオの長さが非常にまちまちである可能性があるからです。
ストラグラーが存在するということは、逐次実行されて長時間を要する作業が並列ジョブの中で事実上発生しているということです。
アムダールの法則により、その影響はワーカーの数が増えるとともに、より顕著になります。
そのため、この問題の解決が Google の重要課題となったのは当然のことでした。Google では、人々が日常的に数千コアの規模でジョブを実行しているからです。
Cloud Dataflow が誰でもオンデマンドでこの機能にアクセスできるようにしているので、ストラグラーの問題を適切に解決することは、優れたユーザー エクスペリエンスを提供するための必要条件でもありました。
ストラグラー対策の現状
業界と学術界は、ストラグラーの問題に長年取り組んできました。
- 多くのフレームワークが、入力を分割する数を調整する仕組みを提供しています（たとえば、Cloudera のこの投稿や、Spark の正式なドキュメントは、Spark の並列処理のチューニングに関する幅広いアドバイスを提供しています）。一般に、細かく分割するとストラグラーは少なくなります。ただし、ある一線を超えると、分割数の多さによるオーバーヘッドの影響が出始めます。手動によるチューニングのデメリットは明らかです。手間がかかり、正確さに欠けます。さらに、入念に選んだ値がすぐに古くなってしまうおそれもあります。その原因としては、データセットに対する変更（特に、同じジョブがさまざまなデータセットに対して実行されている場合）、処理アルゴリズムに対する変更、ランタイム環境に対する変更、さらにはフレームワークの新バージョンへの移行が挙げられます。
- 一部のフレームワークは低速なワーカーを特定し、そのマシンを不良と見なして、それらをワーカー プールから予防的に排除します。しかし、この解決策はハードウェア ベースのストラグラーにしか対応しておらず、クラウド環境にはあまり適しません。
- 多くのシステムは投機的実行（バックアップとも呼ばれます）を実装しているか、または異常に遅いシャードを再起動します。これらの技術もあくまで低速なワーカーへの対策であり、不均等なデータ分割に対処するものではありません。
- サンプリングや類似の技術は、データの分布を推測して、データをより均等に分割するのに役立ちます。しかし、そうした技術による統計データは多くの場合、収集コストが高くつくか、正確さが足りないか、あるいは古いものです。さらには前述したように、データが均等に分割されていても、それらのさまざまな部分における処理の複雑さが一様ではないために、ストラグラーが発生することもあります。
- 学術界では、不均等なデータ分割に対処するため、より複雑な技術も研究されています。たとえば SkewTune は、ストラグラーの処理されていない入力を対象に統計データを収集し、この入力をより均等に分割します。これは正しい方向への一歩ですが、ストラグラーの未処理の入力を完全に読み取るには多大なコストがかかります。特に、ストラグラーが処理の一部を担当する入力の読み取りコストがもともと高い場合は、この技術は非現実的な選択肢になってしまいます。
動的なワーク リバランシングによるストラグラー対策
Google のサービスは他のデータ処理エンジンと同様に、さまざまなヒューリスティクス（発見的方法）を利用して、まず入力を複数の部分に分割します。しかし、さまざまなユースケースの大規模システム（たとえば
Cloud Dataflow）を運用してきた経験から、私たちは次のような理解に達しています。
- 前もってヒューリスティックなチューニングをどれだけ行っても（手動か自動かにかかわらず）、良好なパフォーマンスを保証するのに十分ではない。システムは実行時に、予測できない状況に必ず直面することが、その理由である。
- 悪い状況に動的に適応し、そこから脱却できるシステムのほうが、ヒューリスティックな方法でそうした状況を回避しようとするシステムよりも、はるかに強力である。
私たちはこうした理解に基づき、
Cloud Dataflow が実行中にワーク スティーリングやワーク シェディングと似た技術を使用して、分割を調整し続けるようにしています。このサービスは常に各ワーカーの処理の進捗状況を監視し、ストラグラーを特定します（予想完了時間が平均を上回っているワーカーなど）。
次に、
Cloud Dataflow はこのようなワーカーに対して、未処理作業の一部（ファイルやキー レンジのサブレンジなど）を切り離すよう求めます。さらに、こうした新しいワーク アイテムをアイドル ワーカーにスケジューリングします。
そして、特定されたストラグラーを対象に、このプロセスが繰り返されます。ワーカーから切り離される作業量は、そのワーカーが残りの作業を十分に速く完了し、ストラグラーでなくなるように選択されます。
0 件のコメント :
コメントを投稿