論文ざっくり和訳：Look Who’s Talking: Discovering Dependencies between Virtual Machines Using CPU Utilization(2010)

　私は、物理サーバやVMなどをメトリック情報などの時系列データを利用して特徴ベクトル化し、その特徴ベクトルに群知能に基づいたクラスタリングを適用することで、異常検知・可視化を実現する研究を進めています（詳しくはこちら：超個体型データセンターにおける群知能クラスタリングの利用構想 - クマガリウムぶろぐ）。

　そこで、少し古い論文ではありますが、私のやりたい研究に関連した研究論文を自分が理解できる程度にざっくり和訳したものをメモとして残しておきます。（一部理解できていないところは直訳的になっていますので、詳しくは元論文を参照してください）

　対象とする問題の設定やそれに対するシンプルな手法による解決策、何を評価するかなど、私自身の研究をまとめていく上で参考になりました。今後は、本研究に関連する最新論文の調査を進め、随時ブログにメモしていきたいと思います。

※以下、論文の和訳です。

Look Who’s Talking: Discovering Dependencies between Virtual Machines Using CPU Utilization

URL: http://users.cis.fiu.edu/~lhu/doc/look.pdf 
著者: Renuka Apte, Liting Hu, Karsten Schwan, Arpan Ghosh 

目次

0. 概要

　データセンターやクラウドでよく見られる問題は、それらを実現する一連の仮想マシン（VM）に対して外部ユーザーが提供、または実行しているサービスのマッピングに関する知識が不足していることである。そのため、特定のサービスで消費されるリソースを最小限に抑えたり、データセンターのマシンで消費される電力を削減したりするなど、プロバイダの目標を達成するためにVMの集合を管理することは困難である。本論文では、VM間の依存関係を特定するための、「LWT（Look Who's Talking）」という一連の方法とフレームワークを紹介する。 LWTでは、サービス自体の変更、ミドルウェアやオペレーティングシステムが不要であり、代わりに現在のマシンの使用に関するハイパーバイザーレベルの情報への特権アクセスを使用して管理VMで動作する。 LWTの現在の実装は、小規模プロトタイプデータセンターで実行されているXenハイパーバイザーに統合されている。そのため、実験的測定により、平均97.15％の正確さでVM間の依存関係を効率的に識別できる。また、アプリケーションやワークロードへの影響、およびシステムパフォーマンスへの影響を最小限に抑えている。

1.  背景

 　「非常に小さな変化が、非常に大きな結果をもたらす」。この「バタフライ効果」の有名なキャッチフレーズは、データセンターの管理者が直面しなければならないシステムにおける固有の複雑さによるジレンマを適切に捉えている。クラウドにおける仮想化は、サーバーの統合、ワークロードバランス、高可用性、マルチテナンシー、障害分離などの利点により、ますます一般的になっている。最近、シスコ、EMC、およびVMwareは、仮想化、ネットワーキング、コンピューティング、ストレージ、セキュリティ、および管理の各テクノロジをエンドツーエンドのベンダの説明責任とを完全に統合したインフラストラクチャパッケージを提供するための提携を発表した。このようなソリューションにより、顧客は新しい仮想クラウドデータセンターをプロビジョニングしたり、既存の仮想クラウドデータセンターを移動したりすることで、数分以内に多数のVMで構成されるワークロードを実行できる。

通常、このようなクラウドデータセンターで実行されているアプリケーションは、複数のVMにまたがって実行されている多数の連携コンポーネントで構成されている。図1は、3台の物理マシンに配置された多層アプリケーションを示している。たとえば、アプリケーションサーバーおよびデータベースサーバーバックエンドのサービスを利用するHTTPサーバーフロントエンドを持つ多層アプリケーションがある。一般にVMアンサンブルと呼ばれるこれらのVMは、多数のホストマシンに分散している可能性がある。

図１　VM依存性を示している多層アプリケーション

　VMアンサンブル内のVM間には複数の依存関係（特に、1つのVMが別のVMによって使用されるサービスを提供するため、2つのVMが通信する「いわゆる利用」の関係によって定義されるもの）がある。管理者がデータセンターを正常に管理（リソースの最適割り当て 、ワークロードのバランスと移行 、サービスレベル契約の遵守 、重大な障害の検出と軽減）するために VM間に存在する依存関係を識別できることが重要である。これは、どのVMが依存しているかを知ることによって、管理者が次のリストまたはこれに限定されないより高度な決定を下すことができるためである。

•仮想マシンを別の物理マシンに移行するかどうか：2つの仮想マシンが相互に依存している場合は、物理的に離れた別の物理マシンが空いていても、同じ物理マシンに配置することをお勧めする。
•あるVMからリソースを放棄すると別の依存サービスに影響を与える可能性があるかどうか：リソースの割り当てと管理をよりインテリジェントにすることができる。 VMがオーバープロビジョニングされているように見えるかもしれないが、このVMのサービスは複数の依存VMによって使用される可能性がある。
•障害の原因の特定：管理システムは依存関係の知識に基づいて因果関係をより適切に判断し、障害がどのように発生する可能性があるかを判断できる。

　本論文では、仮想マシン間の依存関係を識別するための一連のメソッドとフレームワークを紹介する。 LWTは、アプリケーションやシステムコードを計測したり、変更したりすることなく実現する。また、 監視対象のゲストOS、ランタイム環境、アプリケーション、またはサービスから独立している。これは、管理者からの必要な入力を最小限にし、最小限のパフォーマンスペナルティをももたらす。

　LWTは、クライアントVMがサーバーに要求を出しサーバーが何らかの計算を実行して応答する、要求/応答タイプの対話を行う多層アプリケーションに適用される。クライアントのワークロードが重いほど要求が高まる。その結果、クライアントのCPU使用率が急上昇するのとほぼ同時に、サーバーのCPU使用率が急上昇することが予想される。 そのため、VMのCPU使用率をモデル化し、これらのモデル間の類似性に基づいてそれらをクラスタ化することで、それらの間の依存関係を高い精度で予測できる。

　LWTは、モニタリング、モデリング、およびクラスタリングの3つの段階で構成されている。まずxentopベースのモニターを使用して、VMごとのCPU使用率を記録および抽出する。次に、VMごとに自己回帰（AR）モデルを推定する。最後に、ARモデルをクラスタ化するためにK-meansを使用する。自己回帰モデルは、系列における1つ以上の前の値に対する現在値の単純な線形回帰である。通信中の仮想マシン群が同様のスパイク（急増）を示す場合、ARモデルは「近い」と予想される。したがってK-meansは、相互依存しているVMが1つのクラスタ内に収まるようなクラスタを作り出すことができる。また、ランダムに選択されたいくつかのVMを明示的に乱すことで、結果をさらに改善することができる。図2に、LWTシステム図を示す。

図2　LWTシステムの概略図

　現在のLWTの実装は、5台の物理マシンと31台のVMで構成される小規模システムで実行されているXenハイパーバイザーに統合されている。 VMは、RUBiS、Hadoop、およびIperfの3つの異なるアプリケーションのインスタンスを実行する。それにより、トータルの精度は97.15％、真陽性率は91.67％、そして真陰性は99.08％で依存性を識別することができる。

2. 関連研究

　関連する研究を4つのカテゴリ（手動、トレースベース、ミドルウェアベース、および摂動ベースの手法）に分類する。

　手動技術：

　Mercury MAMやMicrosoft MOMのような管理システムは、トポロジマップを維持することによって依存関係モデルを指定するためのサポートをアプリケーション設計者に提供する。ただし、この方法では大規模システムにおけるアプリケーションの動的な性質に追いつくためにかなりの手作業が必要であり、多くの場合同じベンダーの特定のアプリケーションに限定される。

　トレースベースの技術：

　Project5とWAP5 [17]は、ブラックボックスネットワークのトレースから因果パスを推論する。送信されたタイムスタンプと受信されたタイムスタンプの両方と共に各ホストでメッセージを記録する。そして、Project5はオフラインのネスティングと畳み込みアルゴリズムを使って因果関係を推論し、WAP5はメッセージリンクアルゴリズムを使ってタイムラインと因果ツリーを生成する。これらのアプローチは、個々のアプリケーションのデバッグとプロファイリングを対象としているという点で我々の研究とは異なる。したがって、主な関心事は、どの着信パケットがどの発信パケットをトリガーしたかを解決することである。一方、我々はリアルタイムにVM上で実行されている多層アプリケーションのサービスの依存関係を発見することに焦点を当てている。

　Magpieは、OSレベルのイベント追跡に基づいて因果経路を再構築する。 Windows OSに組み込まれているWindows用のイベントトレースを使用して、スレッドレベルのCPUおよびディスク使用量の情報を収集することにより、現実的な動作条件下でシステムのワークロードを自動的に抽出できる。ただしMagpieでは、トレースされた情報を要求パターンにまとめるために、アプリケーションの専門家によって書かれたアプリケーション固有のイベントスキーマが必要となる。

　Orionは、異なるサービス間のメッセージの時間相関を使用して、エンタープライズアプリケーションの依存関係を発見した。 「時間相関」とは、サービスAがサービスBに依存している場合、AとBの間のメッセージ遅延が遅延分布における「特徴的な」急上昇を示す「特徴的な」値が似ていることを意味する。同様に、Sherlockは推論グラフを計算する。ただし、この規則は仮想マシンプラットフォームでは失敗する可能性がある。

　Gaoらは、リソースを監視し、監視されたパラメータ間のペアワイズ相関を追跡して確率モデルを作成し、観測データがモデルに準拠していない場合はアラームを発生させることにより分散システムの問題を検出する。

　ミドルウェアベースの技法：

　Pinpointは、各J2EE呼び出しに一意の要求IDをタグ付けすることによって、分散システムを通過するクライアント要求のエンドツーエンドのトレースを収集する。彼らのアプローチの鍵は、これらのトレース（経路）を使用して意味のある自動統計分析を可能にすることであり、例えば経路異常および待ち時間プロファイルを使用してシステム障害を検出することができる。 Pinpointでは、すべての分散アプリケーションを適切なロギング機能を備えた同種のプラットフォームで実行する必要があるが、実際の大規模エンタープライズデータセンターは、さまざまなベンダーの多数のオペレーティングシステムを使用しており、ほぼ不均一である。

　摂動ベースのテクニック：

　Bagchi らは、フォルトインジェクションを使用して積極的なアプローチをとることでリソースの依存関係を明らかにしている。ブラウンらは、特定のデータベーステーブルをロックして特定のコンポーネントからのクエリを拒否するなど、システムの応答を監視しながらシステムコンポーネントを明示的に乱すことで、ドメイン間の依存関係を識別する。正確性を向上させるために摂動を使用するが、依存関係を見つける唯一の手段としてそれを当てにすることはしない。 Pipは、アプリケーションを修正または少なくとも再コンパイルすることで、因果経路を抽出するための高い精度を得ることができる。

3. LWTの設計

　前述の目標に達成するために、我々のアルゴリズムは次の特性を持つ必要がある。アプリケーションやシステムにとらわれず、邪魔にならず、スケーラブルで、コンポーネントの故障や設定変更に抵抗し、そして計算上効率的であるべきである。

3.1 直感と概要

　要求応答型のアーキテクチャでは、クライアントの作業負荷が増加すると、一般にそれが依存しているサーバーに対してより多くの要求が行われ、サーバーの作業負荷も増加する。したがって図3に示すように、この増加に比例して、クライアントとサーバーの両方のCPU使用率が同時にスパイクすることが予想される。各スパイクの時間的な類似性に基づいてVMをクラスタ化する。

　各VMのCPU使用率を時系列信号としてモデル化し、この情報を使用してVMを分類する。アルゴリズムは3つのステップ「監視、モデリング、そしてクラスタリング」 から成る。さらに、結果を改善するためにランダムに選択されたVMのアクティブ摂動を使用する。

図３　依存関係にあるVM間のCPU利用率における同じスパイク

3.2 モニタリング

　VMは、アプリケーション全体を実行する、あるいはWebサーバーのようなサービス（アプリケーションのコンポーネント）を実行すると想定している。最近のほとんどの仮想化データセンターにおける展開モデルを考えると、これは合理的な仮定である。監視モジュールは、xentopを使用してホストごとのVMのリソース使用率を記録する。記録された情報は、VMごとのCPU利用率の詳細を抽出するために解析される。

3.2.1 サンプリング周期

　サンプリング周期が短すぎると、アルゴリズムによって実行される計算量が増加する。また、読み取り値にノイズが載ってしまう（ノイズの影響を過大評価してしまう）可能性もある。同様に、サンプリング期間が非常に長いと、重要なスパイクを見逃す可能性がある。

　少数のVMには10ミリ秒から7秒のサンプリング周期を使用し、結果を分析するために単純な相関を使用した。次に、相関係数としてカットオフCを選択した。これ以上の相関係数を持つVMは依存型とマークされる。３秒のサンプリング周期に対する一例が図４に示されており、それはＣ ＝ 0.9を使用している。図に示すように、Apache Webサーバー、Tomcatサーバー、MySQLサーバー、おせよびRUBiSクライアントはしきい値を超える相関を示しているため、依存関係がある。同様に、Iperfクライアントとサーバーの間には依存関係があるが、CPUベンチマークであるNbenchは他のVMと依存していない。これらの実験を通じて、1秒のサンプリング周期が最適な選択であることが確認できた。

図4　サンプリング周期=3病におけるVMの相互相関

3.2.2　サンプルサイズ

　監視対象のVMの数を増やすと、必要なサンプルサイズは徐々に増加する。現在の実装では、31個のVMを使用して、サンプルサイズ300（サンプリング周期1秒）で十分であると経験的に判断した。さらに、この手法をリアルタイム環境で使用するため、継続的に監視して300秒以上の依存関係を計算できる。そして、システムに存在する現在の依存関係を改善し続けることができる。このアプローチは、VMが動的に作成、または破棄される可能性がある環境に対応できるだけでなく、各反復で見つかった依存関係を実証または無効化することもできる。これはまたアプローチがサンプルサイズにあまり敏感ではなくなることにもなる。

3.2.3 アクティブ摂動

　摂動（乱すこと）とは、サービスの提供能力に影響を与えるために、利用可能なCPUのタイムスライスなどのVMのいくつかの要素を意図的に変更することである。具体的には、ホストシステムにアイドル状態のCPUサイクルがある場合でも、ドメインで使用できるCPUの量に上限を設定する。これはXenでxmコマンドを使用して、VMに付与できる「クレジット」の量を変更することで行う。仮想マシンを乱す（摂動）ことで、依存する仮想マシンのCPU使用率が変化することが予想される。たとえば、VMの上限を引き下げることで、要求を処理する容量を抑制する。したがって、そのCPU使用率の低下は、サービスを受けるのを待っている依存VMに伝播される。ランダムに選択されたVMのサブセットでこの上限を定期的に変更することで、サンプルセットに時間依存のスパイクを追加する。

3.3　自己回帰モデリング

時系列データセットXのの自己回帰モデルは、pこの前の値の荷重和で与えられる。ここで、pはモデルの次数である。モデルは以下の式で与えられる。

ここで、φpはモデルのパラメータ、cは定数、εtはホワイトノイズである。各VMの時系列CPU使用量をこのようなモデルに合わせることで、時間内の1つのスパイクが以前のスパイクによってどのように影響されるかを把握できる。このモデルを予測に使用しているわけではないが、観察結果を効果的にまとめることができる。 ARモデリングはホストごとに実行でき、特定のオーダーに対して有限の時間がかかる。

3.3.1　自己回帰モデルのオーダー

　この文脈では、モデルの次数を選択することが、どれだけ要約したいのかという選択を意味する。このモデルが予測に使用されることを想定していないため、次数を選択するために予測誤差または同様の手法を使用しない。また、この問題はサンプルサイズの選択の問題と似ている。システムがより複雑になるにつれて、pの値は着実に増加すると予想される。ただし、pが大きすぎると過剰適合になる。この傾向は図5に確認することができる。異なるpに対する予測精度の依存性を示している。

　実験的な設定の大きさでは、40〜50の範囲のオーダーがうまくいくことがわかった。

図５　自己回帰モデルのオーダーを変化させたときの精度

3.4　クラスタリング

　最後のステップは、ARモデル間の距離に基づいてクラスタリングを使用し、依存VMをグループ化することである。ユークリッド距離を使用するため、履歴内の特定のサンプルについて同様の係数を持つモデル（時間内のスパイクに効果的に対応する）が近くなる。クラスタリングにはK-meansを使用する。
　K-meansは、データを複数のクラスター= Kに分割する。K-meansは、データに対してK個の中心または重心を選択することによってクラスタリングを行う。アルゴリズムを繰り返すたびに、クラスタ内の距離に対応するメトリックを減らし、クラスタ間の距離に対応するメトリックを増やすことによって、中心のポイントが改善される。 このKの値は管理者によって提供される。
　この最後のステップは集中的に実行する必要があるが、K-meansは非常に効率的である。 1000個のサンプルと500個の実数値属性（これはオーダ500のARモデルを持つ1000個のVMに対応する）を持つデータセットの場合、K-meansは数秒以内に計算を終了する。

4. 実験設定

　我々のテストベッドは、5基のデュアルコア、Intel Xeon 5150プロセッサを搭載したDell PowerEdge 1950コンピュートノード、4GBのメモリ、および80GBのハードドライブをギガビットネットワークで接続したものである。 31台の仮想マシンを持つクラスターをシミュレートした。各仮想マシンは512 MBのRAMを使用するように構成され、各ホストの仮想マシンモニターとしてXen 3.1.2を使用する。

　使用されるアプリケーションとワークロードは以下のとおりである。

　RUBiS は、オークションサイトの中核機能である販売、閲覧、入札を実行する、よく知られたeBayのようなベンチマークである。私たちは、サーブレットベースの4ノード構成のRUBiSを使用する。これは、Apache、TomcatおよびMySQLサーバー、4台のクライアントノードで構成されている。したがって、1つのRUBiSインスタンスは4つのVMで構成されている。 RUBiSによって提供されるさまざまな既存ワークロードを、そのさまざまなインスタンスに対して使用する。

　Hadoop MapReduceは、膨大な量のデータを大量の計算ノード上で並列に迅速に処理するアプリケーションを作成するためのプログラミングモデルおよびソフトウェアフレームワークである。 3つのVM、1つのマスター、3つの作業ノードを使用し、Hadoopの単一インスタンスを作成する（VMの1つはマスターとワークノードの両方）。 Hadoopインスタンス用のワークロードを作成するため、Hadoopで提供されている3つの既存のサンプルプログラム、wordcount、randomwriter、およびsortを使用する。

　Iperfは、TCPおよびUDPデータストリームを作成し、それらを伝送しているネットワークのスループットを測定できる、一般的に使用されているネットワークテストツールである。クライアントとサーバーの機能をベースにした2ノード構成のIperfを使用し、両端間のスループットを測する。 1つのIperfインスタンスは2つのVMで構成されている。 ARモデルとKMeansの計算にはMATLABを使用する。

5. 結果

5.1 パフォーマンス評価

 結果の概要を図5に示す。これは、ARモデルの次数を変化させたときの依存関係の予測精度、および真陽性、陰性の内訳を示している。セクション3.3.1で述べたように、過度に大きいオーダーの値は、オーバーフィットのために精度を低下させ始めることがわかる。また、この方法は特定の順序の値に対して極端に敏感ではないこともわかる。表1は、RUBiSとHadoopを個別に使用した場合と、合計31台のVM（3つのAll Workload）に対して3つのHadoopインスタンス、4つのRUBiSインスタンス、2つのIperfインスタンスを実行した場合の組み合わせの結果の内訳を示している。摂動を使用しなくても、RUBiS VM内の依存関係を100％の精度で識別できることがわかる。これは、RUBiSのようにコンポーネントVM間で多くの連携を必要とするアプリケーションが、我々のアプローチに特に適しているからである。また、依存関係を考慮することによって行われるプロビジョニング決定から最も利益を得るアプリケーションの種類である。 Hadoopでもこのアプローチがうまく機能する理由は、比較的直感的ではない。 Hadoopマスターはワークロードを分割し、タスクをワーカー（マッパーとリデューサー）に割り当てる。この時点の後、マッパーおよびリデューサーはファイルを介して通信する、すなわちマッパーは中間結果をファイルに格納し、それらの位置をマスターに通信する。マスターはこれらの場所についてレデューサーに順番に通知して、それらの場所を読み取って処理できるようにする。このセットアップでは、Hadoopインスタンスの3つのVMすべてがワーカーである（そのうちの1つはマスターとワーカーの両方です）。その結果、CPU使用率にはかなりの相関関係があり、図6で確認できる。この図は、Hadoopの2つのインスタンスのCPU使用率の時系列をプロットしている。最初のインスタンスに属する左側の列は、右側の列とは大幅に異なるパターンを示している。図7は、精度に対する摂動の影響を示している。セクション3.2.3で述べたように、サービス能力を定期的に変更することによってVMを摂動させると、依存VMのCPU使用率において顕著なスパイクが発生する。摂動により、Hadoopワークロードの精度は全体で25％上昇する（真陽性の場合は33.33％、真陰性の場合は23.23％）。同様に、すべてのワークロードの場合、精度の向上は約2.5％である。この一見したところわずかな増加は、摂動を使用せずに96.33％の真陰性がすでに識別されているという事実によるものである。

図6　HadoopインスタンスのCPU利用の時系列

表１　依存性を識別した結果

図7　予測精度における摂動の効果

　2つのアプリケーションインスタンスのARモデルを、時系列で前の値の係数をプロットすることによって図8に示す。同様の係数を持つモデルは、それらが時間内に同様のスパイクを示したことを意味する。同じアプリケーションインスタンスからのモデルは、他のモデルよりも係数が類似していることがわかる。その結果、それらは一緒にクラスタ化される。図9は、RUBiS VMの2次、3次、4次の係数に対する散布図を示している。従属VM（同じ色で表示）は互いに近い距離に位置していることがわかる。

図８　(a)RubiS モデル、(b)Iperfモデルの回帰モデル

図９　モデルの可視化

5.2 スケーラビリティおよび時間計算量

　アルゴリズムの時間計算量は3つの要素（VMの数N、次数pの選択、サンプルサイズWの選択）に依存する。特定のシステムにアルゴリズムを配置する前にpとWを選択するため、それらの効果を一定 （有限時間）にすることができる。 ARモデルを見つける最初のステップの計算量は、Nで線形である。モデルはホストごとに計算され、クラスタリングフェーズのために中央マシンに送信される。 k-meansの複雑度はΩ（N）である。この手順は集中的に実行されるが、1000個のサンプルと500個の実数値属性を持つデータセット（500のARモデルを持つ1000個のVMに対応）では、K-meansは数秒以内に計算を終了する。したがって、このアルゴリズムは、何千ものVMのデータセンターに容易に拡張できる。これをさらに確立するために、既存の使用率をコピーすることによって、1200 VMのCPU使用率をシミュレートした。次数p = 100を使用して、この人工のデータセットに対してアルゴリズムを実行した。 ARモデルを一元的に計算したにもかかわらず、アルゴリズムの合計実行時間は、1GBのRAMを搭載した2GHzで動作するIntel core2デュオマシンでわずか1.5分であった。

6. まとめと今後の課題

　本論文では、VM間の依存関係を識別するための一連のメソッドとフレームワークを紹介した。この方法は、邪魔にならず、アプリケーションにとらわれず、リアルタイムでスケーラブルであり、VMを変更することなく稼働中のデータセンターに簡単に展開できる。個々のVMのCPU使用率について自己回帰モデルを推定し、どのモデルが類似しているかに基づいてそれらをクラスタ化する。 LWTの現在の実装は、小規模プロトタイプデータセンターで実行されているXenハイパーバイザーに統合されている。実験測定により、VM間の依存性を平均97.15％の正解率で効果的に識別できる。この作業でまだ検討されていない側面の1つは、多数のVMが単一のVMに依存している場合にシステムがどのように反応するかということである。この場合、特徴的なスパイクがはっきりとは見えない。また、ARモデルの次数やサンプルサイズなどのパラメータの探索を自動化したいと考えている。