# Cloud Service Reliability: Modeling and Analysis > [!abstract] 概要 > クラウドコンピューティングは、グリッドコンピューティングの資源共有とは異なり、大規模なサービス共有を可能にする新しい技術である。クラウドの信頼性の分析とモデル化は、システムの複雑さと規模のために容易ではない。本論文はクラウドコンピューティングを体系的に分析し、クラウドサービスの信頼性をモデル化する。クラウド環境では、オーバーフロー障害、タイムアウト障害、資源欠落障害、ネットワーク障害、ハードウェア障害、ソフトウェア障害、データベース障害といった多様な障害が絡み合って生じる。本論文はそれらをすべて調べてクラウドサービスの信頼性の全体像を得るとともに、Markov モデル、待ち行列理論、グラフ理論を用いてこれらの障害を統合的にモデル化する。提案モデルに従い、Bayes 的手法とグラフ理論を統合した新しい評価アルゴリズムをさらに開発する。 ## 論文情報 - 題名: Cloud Service Reliability: Modeling and Analysis - 著者: Yuan-Shun Dai(テネシー大学 ICL・産業情報工学科)、Bo Yang(電子科技大学)、Jack Dongarra(テネシー大学 ICL)、Gewei Zhang(テネシー大学産業情報工学科) - 発表: PRDC 2009(15th IEEE Pacific Rim International Symposium on Dependable Computing) - 全 17 ページ。実験を含まない解析モデルの提案論文である。 - 資金: 米 NSF(0831609)、中国 NSFC・教育部 ## 概要 クラウドサービスの信頼性を「ユーザが指定した期間内にサービスが成功裏に完了する確率」と定義し、障害を要求段階と実行段階の 2 群に分けて解析するモデルを提案する。要求段階は待ち行列の Markov モデル、実行段階は仮想ノード付きグラフと Bayes 的評価アルゴリズムで扱い、両者の積でサービス信頼性を得る。検証は今後の課題である。 ## 問題設定 - クラウドは大規模なサービス共有、広域ネットワーク、異種のソフトウェア・ハードウェア、それらの複雑な相互作用を特徴とし、純粋なソフトウェア・ハードウェアや従来のネットワークの信頼性モデルをそのまま適用できない。 - 著者らはグリッドがユーザにとって資源よりもサービスが関心事であるとの立場をとり、クラウドをグリッド・ユーティリティ・トランスペアレントコンピューティングの自然な次段階と位置づける。 - 各障害種別の個別研究は存在するが、それらを一括して扱うモデルはない。しかも障害は互いに相関する。例えばスケジューラ障害は待ち時間を延ばしてタイムアウトとオーバーフローに波及し、大きな待ち行列上限はオーバーフローを減らすがタイムアウトを増やす。データベース障害はソフトウェアを完了不能にし、ネットワーク障害はソフトウェア間の通信を止める。 システムは、要求キュー・スケジューラ・計算資源管理・データ資源管理を持つ Cloud Management System(CMS)と、インターネット上の計算資源・データ資源から成る(VGrADS プロジェクトで開発し [[Amazon EC2]] と連携している)。 ![[_attachments/2009__PRDC__Cloud-Service-Reliability-Modeling-and-Analysis/fig01-cloud-service-system.png]] *Figure 1: Cloud Service System(原文 Fig. 1)* ユーザのサービスはサブタスク(S1〜S4)とデータ依存のワークフローで表され、スケジューラが計算資源とデータ資源に割り当てる。資源同士はネットワークの到達性に従って網を成す。 ![[_attachments/2009__PRDC__Cloud-Service-Reliability-Modeling-and-Analysis/fig02-workflow-scheduling.png]] *Figure 2: Workflow of a Cloud Service and Scheduling(原文 Fig. 2)* 想定する障害は 8 種である。 - オーバーフロー: キューが満杯のときに到着した要求が捨てられる。 - タイムアウト: キューでの待ちが締切を超えて要求が捨てられる。 - データ資源欠落: 登録済みデータが消えたのにデータ資源管理が更新されていない。 - 計算資源欠落: 通知なく電源が切られた PC など。 - ソフトウェア障害、データベース障害、ハードウェア障害、ネットワーク障害。 ## 提案手法 サービス信頼性 R_service は、要求段階の信頼性と実行段階の信頼性の積で表す(式 21)。要求段階の障害(オーバーフロー・タイムアウト)は資源割当前に起こり、実行段階の障害は割当後に起こるため、2 群は独立とみなし、群内の相関は各群のモデルで扱う。 ### 要求段階 - 到着は率 λa の Poisson 過程、スケジューラは同質な S 台で各サービス時間は率 µr の指数分布、待ち行列の容量は N、締切超過による打切り率は µd とする。 - 状態 n(キュー内の要求数)の Markov 連鎖を立て、Chapman-Kolmogorov 方程式(式 2〜6)から定常確率 q_n を解く。オーバーフローが起きない確率は q_0 から q_(N−1) の和である(式 7)。 - 到着時にキュー長が n ≥ S であれば、待ち時間の確率密度は式 8 の形となり、待ち時間が締切 Td 以内である確率を積分する(式 9)。n < S なら待ちなしで処理される。 - 要求段階の信頼性 R_request は、n < S の q_n の和と、n ≥ S の q_n に締切内確率を掛けた和との合計である(式 10)。 ![[_attachments/2009__PRDC__Cloud-Service-Reliability-Modeling-and-Analysis/fig03-request-queue-markov.png]] *Figure 3: Markov model for the request queue(原文 Fig. 3)* ### 実行段階のグラフモデル - ハードウェア(計算機)は実線ノード、通信路は実線リンクとし、ノードやリンクに障害・処理速度・帯域などの特性を付ける。 - データベースとソフトウェアは、ハードウェアノードに従属する**仮想ノード**(破線円)とし、仮想リンクで載っているハードウェアへ結ぶ。物理構造を裏返す発想であり、ハードウェア・ソフトウェア・データベースの異質性を別々の特性として持たせられる。ハードウェアが落ちれば載っている仮想ノードがすべて外部から孤立する形で、障害の相関も表せる。 - データ・計算資源の欠落は、実行開始時点でその資源が故障している特殊なハードウェア障害として扱う。 ![[_attachments/2009__PRDC__Cloud-Service-Reliability-Modeling-and-Analysis/fig04-execution-graph-model.png]] *Figure 4: A graph model integrating different types of failures at the execution stage(原文 Fig. 4)* ### 要素の信頼性 - ハードウェア i の処理速度 ps_i、データ資源の転送量 sd_j、ソフトウェアの負荷 wp_k(命令数)、リンク帯域 bw_m を定義する。 - 運用段階では故障率が一定とみなし、要素 n の信頼性は R = exp(−λ·Tw)(式 11)とする。稼働時間 Tw は、ソフトウェアで負荷 ÷ 処理速度(式 12)、通信で転送量 ÷ 帯域(式 13)、ハードウェアでは載るソフトウェアの実行時間と通過する通信時間の総和(式 14)、データ源では通信時間の総和(式 15)で与える。 - 従来手法 [17] のような「ノードは常に 90% 信頼できる」といった定数信頼度の仮定より現実的であると主張する。 ### 評価アルゴリズム 1. **MSST(最小サブタスク全域木)**: 特定のサブタスクの成功を保証する最小の要素集合。各 MSST は重複のないデータ資源の組をちょうど 1 つ含む。深さ優先探索で、サブタスクを載せた各ノードから必要データ資源と先行サブタスクへの経路を辿って列挙する。要素は待機中もホットスタンバイとして故障しうるので、要素の稼働時間は、含まれる通信のうち最大の時間を用いる(式 16)。 2. **MEST(最小実行全域木)**: サービス全体の成功を保証する最小の要素集合。各サブタスクの MSST 集合から 1 つずつ選んで重ね合わせて作る(式 17)。共通要素の稼働時間は大きい方を採り、信頼性は式 18 で求める。 3. **実行信頼性**: N 個の MEST の和事象の確率(式 19)を、Bayes の定理で条件付き確率の和(式 20)に展開する。条件付き確率 Pr(E1 の否定, ..., E(j−1) の否定 | Ej) は、先行 MEST を壊し MEST j に影響しない「臨界要素」を特定し、その障害組合せを二分探索で生成して足し上げる 2 段階で計算する。 ## 新規性 - 障害を要求段階と実行段階に分ける階層的・サービス指向のモデルで、8 種の障害を一つの枠組みに収めた点。 - データベースとソフトウェアを仮想ノードにしたグラフ表現により、物理構造では表せない異質性と障害相関を表した点。 - 要素信頼性を負荷・処理速度・帯域から導く稼働時間依存の指数モデルとし、従来の定数信頼度仮定を外した点。 - MSST・MEST の列挙と Bayes 的評価を組み合わせた点。 ## 実験設定 なし。本論文はモデルとアルゴリズムの提案に留まり、シミュレーションも実データも用いていない。 ## 実験結果 なし。結論で、提案モデルと評価アルゴリズムは未検証であり、シミュレーションと実運用データによる検証が今後の課題であると明言している。 ## 考察 - 提案モデルは実運用の観測(障害ログ・インシデント)から導かれたものではなく、故障率 λ、到着率 λa、処理率 µr などのパラメータをどう得るかは示されていない。 - 要求段階と実行段階を独立とみなす仮定は、スケジューラ障害が実行段階の資源選択へ及ぼす影響のような跨段階の相関を落とす。著者ら自身、段階内の相関しか扱っていない。 - 要素を稼働時間中は常に故障しうる(ホットスタンバイ)と置くため、待機中の要素の故障を過大に見積もる保守的な評価になる。 - 式 8 の待ち時間密度は、打切り率 µd を含まない M/M/S 系の単純化になっている。 ## 強み / 弱点・課題 - 強み: クラウド信頼性を初期に体系化し、障害の種類と相関を明示的にモデルへ入れた。仮想ノードの発想は後続のサービス依存グラフや障害伝播モデルの先駆けとして読める。 - 弱点: 検証がなく、MEST の組合せ爆発への計算量の見積りもない。障害を 8 種に固定しており、性能劣化などの部分障害や復旧・冗長化は扱わない。パラメータ推定の手順もない。 ## 関連 - 概念: [[クラウドコンピューティング]] / [[グリッドコンピューティング]] / [[待ち行列理論]] / [[ソフトウェア信頼性]] / [[可用性]] - エンティティ: [[Yuan-Shun Dai]] / [[Jack Dongarra]] / [[University of Tennessee, Knoxville]] / [[Amazon EC2]]