論文 / 著書情報
Article / Book Information
論題(和文)OXTHAS: Webサービスベースのワークフロー管理における障害を考慮した負荷分散手法

Title(English)

OXTHAS: Failure-aware Activity Scheduling in Web Services Based
Workflow Management

著者(和文)

加藤英之, 小林 隆志, 横田 治夫

Authors(English)

Hideyuki Katoh, Takashi KOBAYASHI, Haruo Yokota

出典(和文)

電子情報通信学会和文論文誌（Ｄ）, Vol. J91D, No. 4, pp. 993-1003

Citation(English)

IEICE TRANS.INF.& SYST, Vol. J91D, No. 4, pp. 993-1003

発行日 / Pub. date2008, 6

URL

http://search.ieice.org/

権利情報 / Copyright

本著作物の著作権は電子情報通信学会に帰属します。
Copyright (c) 2008 Institute of Electronics, Information andCommunication Engineers.

Powered by T2R2 (Science Tokyo Research Repository)

論

文

OXTHAS：Web サービスベースのワークフロー管理における障害を考慮した負荷分散手法***
加藤 英之†∗

小林 隆志††∗∗

横田 治夫††,†OXTHAS: Failure-Aware Activity Scheduling in Web Services Based Workflow
Management∗∗∗
Hideyuki KATOH†∗ , Takashi KOBAYASHI††∗∗ , and Haruo YOKOTA††,†

あらまし ワークフロー管理システムでは，アクティビティを適切に割り当てることが処理効率の改善につながる．本研究では，近年注目されている Web サービスを用いたワークフローに着目し，その特徴を考慮したアク
ティビティの割当方法を提案する．Web サービスを前提とすると，一つの Web サービスが特定のワークフロー
エンジンのみから利用されるとは限らないため負荷状況を正確に把握できない．提案手法では，Web サービスの過去の処理履歴を利用して負荷状況を推定し，処理負荷サイズを考慮してアクティビティを効率良く割り当てる．
更に本研究では，より実際の環境に対応させるべく，ネットワークやハードウェア等の障害を考慮に入れ，タイ
ムアウトを設定し，効率の良い処理を可能にする再割当手法を提案する．そして，シミュレーションにより，提案手法の評価を行う．
キーワード

Web サービス，ワークフロー，Web とインターネット

る仕事量は膨大になってきており，負荷分散の重要性

1. ま え が きが増している．

プロセス（作業）の一部若しくはすべてを自動化す

一方，ネットワークを介して HTTP と SOAP をるものをワークフローと呼ぶ．ワークフローではプロ用い，ソフトウェアシステム間で通信を行うオープ

セスをアクティビティ（工程）の集合とし，実際に流ンな技術である Web サービスが注目されている [3]．
Web サービスは，実行環境に依存しないアプリケー
ションの連携が可能なため，CORBA や DCOM なれる具体的なプロセスやアクティビティをそれぞれ，
プロセスインスタンス，アクティビティインスタンスと呼び，その自動化された プロセスを管理するシス

どの分散オブジェクト技術よりも利用が容易である．

テムとしてワークフロー管理システムが提案されてい人的コストの削減など様々なメリットが期待できる．

Web サービスが登場した当初は，SOAP，WSDL，
UDDI などの基盤となる技術についての検証が行われ，その後 WS-Security，XML Signature などのセキュ

現在，商用・研究用を問わず多数のワークフロー管理

リティ・相互接続性の確保について研究されてきた．

システムが存在する．近年その普及に伴って，処理す

現在，BPEL4WS（注 1）, WS-BusinessActivity や WS-

る [1], [2]．ワークフロー管理システムの導入により，

AtomicTransaction（注 2）, WS-Choreography（注 3）, WSCAF（注 4）などを用いた Web サービスの実用化に向け† 東京工業大学大学院情報理工学研究科計算工学専攻，東京都

Department of Computer Science, Graduate School of Information Science and Engineering, Tokyo Institute of Technol-

た仕様の策定が行われている．

ogy, 2–12–1 Ookayama, Meguro-ku, Tokyo, 152–8552 Japan††

東京工業大学学術国際情報センター，東京都（注 1）：http://www-128.ibm.com/developerworks/library/

Global Scientific Information and Computing Center, Tokyo

specification/ws-bpel/

Institute of Technology, 2–12–1 Ookayama, Meguro-ku,（注 2）：http://www-128.ibm.com/developerworks/library/Tokyo, 152–8550 Japan
∗

現在，東芝ソリューション株式会社∗∗
現在，名古屋大学大学院情報科学研究科*** 本論文はデータ工学研究専門委員会推薦論文である．

電子情報通信学会論文誌 D Vol. J91–D

specification/ws-tx/（注 3）：http://www.w3.org/TR/ws-chor-reqs/（注 4）：http://www.oasis-open.org/committees/tc home.php?
wg abbrev=ws-caf

c （社）電子情報通信学会 2008
No. 4 pp. 993–1003 

993

電子情報通信学会論文誌 2008/4 Vol. J91–D No. 4

BPEL4WS は XML ベ ー ス の ワ ー ク フ ロ ー

以下では，まず，本研究の対象となるワークフロー

定 義 言 語 で あ り，WS-BusinessActivity や WS-

管理のアーキテクチャについて説明した後，Web サー

AtomicTransaction はアプリケーションの動作やトラビス利用を前提としたワークフロー管理の特徴につンザクションの信頼できる結果を調整する方法を提供

いて述べる．そして，その特徴を踏まえた上で，提案する．WS-Choreography は複数の Web サービスの手法である OXTHAS について述べる．次に，この協調動作を実現する．また，WS-CAF 仕様は，複数

ワークフロー管理アーキテクチャにおけるタイムアの Web サービス間でトランザクションに関する重要

ウトの概念について言及し，エグゼキュータやネットな情報を共有できるようにシステムの設定を行う．こ

ワークの障害に対応するためにタイムアウトを利用しれらの仕様の登場により，ワークフローを Web サー

た OXTHAS 再スケジューリング戦略と 2 種類の調

ビスを用いて実現することが盛んに研究されるように整法について説明する．そして，シミュレータを用いなってきた．

て，ランダムやラウンドロビンなどのアルゴリズムとどに関しては十分に言及されていない．ワークフロー

OXTHAS の比較評価を行う．更にタイムアウトを用いた OXTHAS の性能評価を行い，その効果を示す．

管理の一般的な実現方法としては，(1) 集中管理手法，

最後に本研究をまとめ，今後の課題について言及する．

(2) 分散管理手法，(3) エージェントによる手法，など

2. 対象となるワークフロー管理アーキテ

しかし，これらの仕様では，障害対策や負荷分散ながあり，障害対策，負荷分散ともにそれぞれで考慮すべき点が異なる．我々はこれまでに，Web サービスを用いたワークフローにおける障害対策手法として集中

クチャ
2. 1 プロセスモデル

管理に適した手法 [4]，分散管理，エージェントによるビジネスプロセスはグラフに例えられる（図 1）．ビ実現に適した手法 [5] を提案してきた．しかし，負荷

ジネスプロセスはノードと矢印から成り立っており，分散に関しては言及していなかった．

ノードはアクティビティを意味し，矢印は依存関係をそこで，本研究では Web サービス利用を前提とした集中管理型ワークフロー管理における負荷分散手法としてスケジューリング戦略 OXTHAS (Observed

意味する．複数のアクティビティが矢印でつながり，
それらがビジネスプロセスを構成する．

2. 2 ワークフロー管理アーキテクチャ

Execution Time History and Activity Size basedscheduling) [6]〜[8] を提案する．
OXTHAS では，エグゼキュータごとのワークフロー

フロー管理アーキテクチャは，主にワークフローエン

エンジンから観測した各アクティビティインスタンス

ジンとエグゼキュータから構成されている．ワークフの過去の実行時間の履歴とそのアクティビティインス

ローエンジンとは，前述したビジネスプロセスを自動

タンスの処理負荷サイズから，各アクティビティを実化するための制御や管理を行う部分である．このシス行する環境等の差異を含めた処理能力の推定値（推定テムの動作の概要は次のとおりである．

本研究では，図 2 のような集中管理型のワークフ
ロー管理アーキテクチャを対象とする．図 2 のワーク

処理能力）を算出し，その推定処理能力と各アクティ

2. 2. 1 動ビティインスタンスに対する処理負荷サイズを利用し（ 1 ） ワークフローエンジン内のスケジューラは，作て，新たなアクティビティインスタンスの割当先のエ
グゼキュータを決定することで負荷分散を実現する．
また，エグゼキュータの故障やネットワークの障害等を考慮し，それらに対応するために OXTHAS 再スケ
ジューリング戦略とその核となる 2 種類の調整法を提案する．ネットワークやエグゼキュータの障害に対応するために OXTHAS にタイムアウトの概念を導入し，タイムアウトが起こった場合には，そのエグゼキュー
タで発生したタイムアウトの回数も考慮に入れて推定処理能力を再計算，若しくはタイムアウトの値を調整し，再スケジューリングを行う．
994

図 1 ワークフローのプロセスモデル
Fig. 1 A process model of a workﬂow.

論文／OXTHAS：Web サービスベースのワークフロー管理における障害を考慮した負荷分散手法

ACK を受けたとき，次のアクティビティインスタンスについての割当を行う．
（ 7 ） 以上をすべてのプロセスインスタンスの処理が終わるまで繰り返す．

2. 2. 2 負荷分散と障害対策の前提
2.2.1 の手順において，各アクティビティインスタ
ンスをどのエグゼキュータに割り当てるかを考慮する
ことによって，システム全体の負荷分散を行うことが可能となる．手順 (2) のところで，一定時間を経過しても (3) が行われなかった場合，タイムアウトが発生しワークフローエンジンは別のエグゼキュータにアク
図 2 前提とするワークフロー管理アーキテクチャ
Fig. 2 Assumed workﬂow management architecture.

ティビティインスタンスを割り当てる（リトライ）．このとき，同じアクティビティインスタンスのリクエス
トが複数回発生することになるが，(4) により，そのう

クライアントからのキューに入ってきたプロセスイン

ちの一つだけを採用するようにしている．そして，リスタンスを一つずつ取り出し，その中で最初に実行すトライが起こった場合，最初に割り当てたエグゼキュー

べきアクティビティインスタンスを決める．それと同タから処理結果が返ってきてもそのエグゼキュータに時にスケジューラはそのプロセスインスタンスの情報

は NACK を送信し，必ず，最後に割り当てたエグゼ

をプロセスインスタンステーブルに格納する．あるい

キュータからの処理のみを採用する．このリトライのは，エグゼキュータから返ってきたアクティビティイ

際に，タイムアウトをどのように設定するか，どのよ

ンスタンスが入っているキューから一つずつ取り出し

うに再割当を行うかの戦略によってエグゼキュータ障て，そのアクティビティインスタンスが属するプロセ

害時の対策と障害を考慮したシステム全体の負荷分散

スインスタンスに関してプロセスインスタンステーを行うことが可能となる．

ブルから情報を取り出し，次に実行すべきアクティビ

ここでは，ワークフローエンジンは複数存在し，各ティインスタンスを決める．

ワークフローエンジンは任意のエグゼキュータを共用（ 2 ） スケジューラは，実行すべきアクティビティ

することができることを前提とする．また，ワークフ

インスタンスの情報と，各エグゼキュータが実行可能

ローエンジン同士，エグゼキュータ同士は独立しておなアクティビティの情報から，そのアクティビティイ

り，ワークフローエンジンは自分が処理しているプロ

ンスタンスをどのエグゼキュータに割り当てるかのス

セスインスタンスやアクティビティインスタンスに関ケジューリングを行い，対応するエグゼキュータの処して，どこのエグゼキュータに処理のリクエストを渡理キューに入れる．

しているかについては把握しているが，他のワークフ（ 3 ） 各エグゼキュータもキューをもち，キューのローエンジンが処理しているプロセスインスタンスや先頭にあるアクティビティインスタンスから一つずつ

アクティビティインスタンスに関しての情報は知らな処理していき，処理が終了したとき，ワークフローエ

いものとする．

ンジンのキューにその処理結果を返す．
（ 4 ） ワークフローエンジンはエグゼキュータから

2. 3 Web サービスベースのワークフロー管理で考慮すべき点の処理結果について，ACK（処理結果の受理）若しく

前述のワークフロー管理アーキテクチャをもととしは NACK（処理結果の拒否）を同一のエグゼキュータ

た Web サービスベースのワークフロー管理を対象とのキューに入れる．

するとき，以下のような特徴が考えられる．

（ 5 ） エ グ ゼ キュー タ は ACK/NACK を 受 け た（ 1 ） 一つのエグゼキュータの行うアクティビティ

ことをワークフローエンジンに知らせるために，

インスタンスの処理が一つの Web サービスである．

ACK/NACK の受理をワークフローエンジンのキュー（ 2 ） 個々のワークフローエンジンはエグゼキューに入れる．

タの内部情報を知ることができない．

（ 6 ） ワークフローエンジンはエグゼキュータから

まず (1) については，エグゼキュータは 1 種類以上
995

電子情報通信学会論文誌 2008/4 Vol. J91–D No. 4のアクティビティインスタンスの処理を Web サービスも考慮したものとなる．なお，これらの情報は，ワーとして提供することが考えられる．そのため，個々のクフローエンジンごとに異なるものとなる．

アクティビティインスタンスごとにエグゼキュータの処理能力を考慮して割当を行う必要がある．なお，こ3. OXTHAS スケジューリング戦略

こではエグゼキュータ内で同時に処理できるアクティ

ここでは，我々が提案する OXTHAS スケジューリ

ビティインスタンスは一つに限ることとして議論する．

ング戦略について説明する．2. で挙げた点を前提と複数のアクティビティインスタンスを実行する環境は，し，本研究では，各 プロセスインスタンスごとにア

物理的なプロバイダに複数の論理的なエグゼキュータ

クティビティインスタンスの数や種類は同一であるとをマップすることでモデル化できる．

する．アクティビティインスタンスの数や種類が同一

また，個々のアクティビティインスタンスの入力デーでない場合についての妥当性の証明は今後の課題とす

タのファイルサイズが一定でないことが処理時間に影るが，本手法では，該当アクテビティを実行できるエ

響を与える場合について考慮する必要がある．本研

グゼキュータを対象とした推定処理能力計算と，アク

究では，処理時間はファイルサイズに比例すると考えティビティインスタンスごとの割当を行っており，アる．入力データには様々な種類が考えられるが，あるクティビティインスタンスの数及び種類には依存してアクティビティインスタンスにおいて入力データの種いないため，数及び種類が同じではなくても適用でき類は一つであり，処理時間は比例されると前提する．

ると考える．

更に，各エグゼキュータの能力や環境が一定でないこ

3. 1 推定処理能力とが処理時間に影響を与えることが考えられる．これ

まず以下のように変数を定義する．

は，単純にあるアクティビティインスタンスの処理能•••力が Web サービスを提供するプロバイダの環境等によって異なる場合や，ネットワークの良否による処理

プロセスインスタンス：P = {p1 , . . . pi , . . . pl }プロセスインスタンス番号：i
アクティビティインスタンス ： A = {a1 , . . . aj ,そのため，ワークフローエンジンはエグゼキュータの. . . am }• アクティビティインスタンス番号：j• エグゼキュータ：E = {e1 , . . . ek , . . . en }• エグゼキュータ番号：k• pi における aj の処理負荷サイズ：si,j• pi における aj が ek で処理可能であるかどう

キュー長を知ることができない．このとき，ワークフ

かを示すマッピング：mi,j,k

ローエンジンが知ることのできる情報は，ワークフ

エグゼキュータで処理可能な場合は 1，そうでない場

ローエンジンがエグゼキュータにリクエストを出し合は 0 となる．

の遅延やタイムアウトの発生などの場合が考えられ，これらを考慮する必要がある．

(2) に関しては，複数のワークフローエンジンが共存することを想定する場合，いくつかのワークフロー
エンジンがエグゼキュータを共用する可能性がある．

てからエグゼキュータから処理が終わってそのワーク•

pi における aj の観測実行時間：ti,jフローエンジンに戻ってくるまでの時間になる．そして，この時間にはエグゼキュータ内の処理時間のほか処理負荷サイズ si,j は，アクティビティインスタンにキューでの待ち時間やネットワークの遅延時間など

ス aj の入力データのファイルサイズを表し，観測実も含まれる．

行時間 ti,j はワークフローエンジンがエグゼキュータ

以上の前提を踏まえて，我々はワークフロー管理シにリクエストを出してから，エグゼキュータで処理がステムで負荷分散を行うためのスケジューリング戦

終わってワークフローエンジンに返ってくるまでの実

略 OXTHAS を提案する．各ワークフローエンジン

際に観測した時間を表す．つまり，処理時間のほかにが利用できる情報は，処理が完了したアクティビティ

エグゼキュータのキュー内での待ち時間，ネットワー

インスタンスの入力データのファイルサイズと観測

クの遅延の時間などを含む．また，リトライが起こっされた実行時間（観測実行時間）の履歴であるため，た場合，そのアクティビティインスタンス処理がその

OXTHAS ではそれらの情報からアクティビティイン

エグゼキュータから返ってくるまでは，タイムアウト

スタンスの割当を決定する．それらは，ネットワークの値を暫定的な観測実行時間として推定処理能力を計の状況やエグゼキュータ上での他の処理といった環境

算する．アクティビティインスタンスの処理時間はエ996

論文／OXTHAS：Web サービスベースのワークフロー管理における障害を考慮した負荷分散手法

グゼキュータによって異なるが，ti,j は過去に処理されたアクティビティインスタンスの観測実行時間であるため，k には依存されない．
以上の変数を用いて，エグゼキュータ ek における各アクティビティaj の推定処理能力 ck,j を以下の式で算出する．
l
si,j(ck,j =

i=1

ti,j

l


· mi,j,k )mi,j,ki=1

この推定処理能力 ck,j は単位時間当りの仕事量の平均値を過去の処理時間から求めている．
推定処理能力 ck,j は，値が大きいほど，そのエグゼ
キュータの処理能力が大きいことを示す．しかし，ck,j

図 3 OXTHAS-N スケジューリングの例 (N = 3)
Fig. 3 An example of OXTHAS-N scheduling. (N =3)の大きい方からではなく，小さい方から例えば 3:2:1に分割する方法である．c 値分割（逆）も同様である．
等分割は，処理負荷サイズの大きい方から 1:1:1・・・と
分割する方法である．

の値が大きいことには他の要因も考えられる．例えば，

本研究では，どの方法が適しているか実験を行い，そのエグゼキュータがあまり使用されていないために，

整数比分割が最適であったため，以下ではこれを用い待ち時間がほとんどない場合，他のエグゼキュータよる．実験の詳細な結果に関しては，5.2.1 で述べる．

りも ck,j の値が大きくなることがある．また，そのエ

整数比分割では，アクティビティインスタンスのグゼキュータで処理をしていたアクティビティインス

処理負荷サイズを分割するためのしきい値は，wi =タンスはそのエグゼキュータの得意なアクティビティ(処理負荷サ イズのボーダライン)，n = (分割数)，
Smax = (過去の履歴の中でのアクティビティインスタ
ンスの最大サイズ) とし，次のように定める．

インスタンスを多く処理していたため，他のアクティ
ビティインスタンスの ck,j の値も相乗して大きくなってしまう場合もある．

3. 2 OXTHAS-N

i
j
j=1

· Smaxwi =nk=1

アクティビティインスタンスの処理負荷サイズが大k

きい場合は，当然 ck,j の値が最も大きいところに割り

例えば，OXTHAS-3 では，推定処理能力の値が高当てるべきだが，逆に処理負荷サイズが小さい場合は，

い上位 3 台のエグゼキュータを対象として，過去の履必ずしも ck,j の値が最も大きいところに割り当てなく歴から最も大きい処理負荷サイズを取り出して，処理ても，次に ck,j の値が良いところに割り当てる方が偏を担当する処理負荷サイズの幅が 3:2:1 の比率になるりが減って効率的である．そこで，OXTHAS-N ではように処理負荷サイズのしきい値を決定する（図 3 を候補となる ck,j の値の高い N 台のエグゼキュータに参照）．

対し，アクティビティインスタンスの処理負荷サイズを分割するためのしきい値を設け，処理負荷サイズに応じた割当を行う．

4. 障害の考慮
3. で説明した OXTHAS スケジューリング戦略でこのとき，しきい値の決定方法は等分割，整数比分

は，障害対策に関して言及しなかった．そこで，この割，ck,j の値に応じた分割（c 値分割）等いくつか考章ではエグゼキュータやネットワークの障害に対応すえられる．

るための OXTHAS 再スケジューリング戦略と調整法

整数比分割とは，OXTHAS-N に対して処理負荷サ
イズを大きい方から N:N-1:・・・：1 と分割する方法でに関して説明を行う．

4. 1 OXTHAS 再スケジューリング戦略

ある．c 値分割とは，分割する際の比率を候補となる

エグゼキュータからの応答がない場合，その理由

エグゼキュータの推定処理能力の値によって決定するとしてネットワークの混雑とネットワーク若しくはエ方法である．整数比分割（逆）とは，処理負荷サイズ

グゼキュータの故障が考えられる．その理由がネット
997

電子情報通信学会論文誌 2008/4 Vol. J91–D No. 4

ワークの混雑の場合，処理が遅くなるだけで，処理自4. 2. 2 タイムアウト値調整法

体はそのうち行われ，その混雑の程度に関しては既にタイムアウトが発生した場合はそれ以降に割り当て

推定処理能力で対応されている．しかし，ネットワー

るアクティビティインスタンスに関して，タイムアウ

クやエグゼキュータの故障が理由の場合，処理が停止

トの値 Tk を次のように定める．
（β ，Tinit は定数）してしまうことが予想される．そこで，我々はタイムアウトの概念を導入し，ネットワークやエグゼキュー
タの故障に対応する．このとき，タイムアウト発生時

Tk = Tinit − β · Rk
タイムアウトの値は Tinit = 1000，β = 100 とするの再割当方法を OXTHAS 再スケジューリング戦略とと 900，800・・・と減っていき，故障したエグゼキュー

呼ぶ．

タに割り当てられてもすぐにタイムアウトが発生し，

OXTHAS 再スケジューリング戦略では，タイムア
ウトが発生してアクティビティインスタンスを再び割再割当が起こる．

4. 2. 3 故障傾向の考慮

り当てるときに，再割当を行うアクティビティインス

もし，タイムアウトが発生した後にそのエグゼキュー

タンスを既に割り当てたエグゼキュータには基本的にタから処理が返ってきた場合，故障検知ミスか故障かは割り当てないようにする．そのため，もしエグゼらの復旧を意味するため，ck,j や Tk の値を最初に定キュータが 10 台の場合，同じアクティビティインスタ

義した値に戻す．この方法をとることで，一時的な故ンスで再割当が発生するたびに割当対象となるエグゼ

障に対応することが可能となり，更に故障傾向が高い

キュータの数も 9 台，8 台・・・と減っていく．そして，場合は，タイムアウトのペナルティを大きくするとい

再割当対象エグゼキュータ台数 Nexe と OXTHAS-N

う効果がある．

の N の関係が，Nexe < Nとなってしまった場合，OXTHAS-Nexe で再割当を行う．

4. 2 調 整 法
タイムアウトを導入する際，故障の影響をなるべく抑える必要がある．故障の影響を抑える方法としては，故障の可能性があるエグゼキュータにアクティビティ
インスタンスをなるべく割り当てないようにする方法と，たとえ故障の可能性のあるエグゼキュータに割り当てられてもすぐにタイムアウトを発生させることで故障の影響を抑える方法が考えられる．前者を推定処
理能力調整法，後者をタイムアウト値調整法と呼ぶ．

4. 2. 1 推定処理能力調整法
先ほど定義した推定処理能力にタイムアウトの発生時を考慮に入れて，ck,j を以下のように再定義する（Rk はそのエグゼキュータでタイムアウトが発生した
回数．α は定数）．

ck,j =ck,j
1 + α · Rk

タイムアウトの発生時，その推定処理能力は α = 1

5. 評

価

5. 1 シミュレーション内容
前述した OXTHAS スケジューリング戦略の有効性と OXTHAS におけるタイムアウトの利用方法の検証と再スケジューリング戦略の有効性を示すために 2.2で説明した対象となるワークフロー管理アーキテク
チャに基づいたシミュレータを作成し，シミュレーショ
ンを行った．最初に，OXTHAS-N の領域分割方法の違いによる総処理ステップ数を比較し，最適な領域分割方法を決定する．次に，OXTHAS スケジューリン
グ戦略とランダムやラウンドロビンを比較する．まずエグゼキュータの処理能力の値をいろいろ変化させた
ときについて，総処理ステップ数を比較し，その後プ
ロセスインスタンスの数を変化させたときの総処理ス
テップ数について比較する．各シミュレーションに関しては，それぞれ 20 回の測定を行い，その平均をとる．また，ここまでのシミュレーションでは故障を考慮しないため，ワークフローエンジンがエグゼキュー
タに ACK/NACK を通知する部分を省いた処理プロ
トコルになっている．
次に，1 台のエグゼキュータを途中で故意に故障

キュータにアクティビティインスタンスを割り当てなさせたときのタイムアウトの効果を，OXTHAS-N(N = 3) において通常の OXTHAS-N と提案した二つの調整法を用いた OXTHAS-N を比較する．更に調いようになる．

整法の効果について検証する．

とすると 2 分の 1，3 分の 1・・・となり，そのエグゼ

998

論文／OXTHAS：Web サービスベースのワークフロー管理における障害を考慮した負荷分散手法
表 1 エグゼキュータの性能設定（ケース 1）
Table 1 Settings of executor’s performance. (case1)
a1
a2
a3
a4
a5

e1
10
4
5
1
5

e2
2
5
10
5
4

e3
4
4
3
3
10

e4
4
10
2
5
5

e5
5
4
5
10
1

e6
5
1
10
4
4

表 2 エグゼキュータの性能設定（ケース 2）
Table 2 Settings of executor’s performance. (case2)

しきい値 w の設定の違いによる総処理ステップ数の比較
Fig. 4 Comparison of the number of total processing
steps between load balancing strategies.
図 4

推定処理能力は過去の履歴から求められるものであるため，はじめの 1000 ステップまでは，ランダム割
当を用いる．それぞれ 10 回測定を行い，その平均を

a1 − a5 の平均

a1 − a5 の平均

a1 − a5 の値処理するかなどはそのワークフローエンジンしか管理していない．ビジネスプロセスは分岐などのない単純なものとした．エグゼキュータの処理性能や，プロセ

e2 , e55

e3 , e62

e1 − e64-6

表 5 エグゼキュータの性能設定（ケース 5）
Table 5 Settings of executor’s performance. (case5)を処理し，プロセスインスタンスは 10 ステップに一つ到着し，それぞれのプロセスインスタンスをどこで

e1 , e48

表 4 エグゼキュータの性能設定（ケース 4）
Table 4 Settings of executor’s performance. (case4)

エグゼキュータは 6 台，ワークフローエンジンは 2
スインスタンス（プロセスインスタンス数は 200 個）

e2 − e63

表 3 エグゼキュータの性能設定（ケース 3）．
Table 3 Settings of executor’s performance. (case3)

とる．誤差棒は 95 パーセント信頼区間を表す．
台とし，各ワークフローエンジンでは同じ数のプロセ

e1
8

a1
a2
a3
a4
a5

e1
9
1
9
1
9

e2
1
9
1
9
1

e3
5
5
5
5
5

e4
7
3
7
3
7

e5
3
7
3
7
3

e6
5
5
5
5
5

スインスタンス，アクティビティインスタンスのサイズなどはランダムで決定される．また，すべてのプロ

アクティビティに関してのみ，処理性能を非常に高く

セスインスタンスがもつアクティビティインスタンス

してある．処理内容によって得意であるかそうでないの数は 5 として，すべて同じにしてある．そして，各かが分かれるケースである．ケース 2 は表 2 のように

エグゼキュータではすべてのアクティビティインスタ

1 台のエグゼキュータだけ処理性能が他のより良い場ンスに関して処理可能であるとする．また今回は，エ合である．ケース 3 は表 3 のようにエグゼキュータのグゼキュータの部分的な故障は考えず，故障のときは，処理性能を 2 台ずつ良いものと悪いものとその中間のそのすべてのアクティビティインスタンスの処理が不ものという設定にした場合である．ケース 4 は表 4 の可能であるとする．

ようにエグゼキュータの処理性能がどれもほとんど同

5. 2 結果と考察
5. 2. 1 OXTHAS-N に関する結果と考察じであることを表している．

図 4 は，OXTHAS-N における処理負荷サイズの領

べて同等性能・アクティビティごとに多少性能差があ

ケース 5 は表 5 のようにエグゼキュータごとに，す

域分割方法の違いによる総処理ステップ数を表す．エ

るもの・性能差が大きいもの，の 3 パターンが混在しグゼキュータの性能を表 1 から表 5 の 5 種類の特徴ているケースの場合である．

別に分けて測定を行った．各表の数値は 1 ステップに処理する処理負荷サイズを表す．プロセスインスタン
スの数は 1000 とした．
ケース 1 は表 1 のように各エグゼキュータに一つのこの 5 種類のケースに対して，3.2 で説明した五つの領域分割方法を用いて比較を行った．
グラフから分かるように整数比による分割と推定処理能力の値の比による分割が効果を上げている．等分999電子情報通信学会論文誌 2008/4 Vol. J91–D No. 4

図 5 エグゼキュータの性能差の違いによる総処理ステッ
プ数
Fig. 5 Comparison of the number of total processing steps between executor’s performance settings.

図 6 各プロセスインスタンス数における総処理ステッ
プ数
Fig. 6 Comparison of the number of total processing
steps for each method with varying number ofprocess instance.

割に比べて良かった理由としては，推定処理能力の高いエグゼキュータに多くのアクティビティインスタン
スを割り当てているからであるといえる．また，処理負荷サイズの領域を処理負荷サイズが小さい方から領域を分割する方法より処理効率が良かったことから，処理負荷サイズの大きいアクティビティインスタンス
は推定処理能力の高いエグゼキュータに割り当てる方がよいということが分かる．整数比による分割と推定処理能力の値の比による分割については，ケース 1 では推定処理能力の値の比による分割の方が若干効果を上げているが，ケース 5 のように各アクティビティイ
ンスタンスについてエグゼキュータの処理性能が全く

図 7

故障時における再割当手法の違いによる総処理ス
テップ数の比較
Fig. 7 Comparison of the number of total processing
steps for each adjustment method with varying setting of time-out steps.

異なるようなケースにおいては整数比による分割の方が効果を上げており，処理性能にばらつきが多い場合

図 6 は，各手法についてプロセスインスタンスのには整数比による分割が適していることが分かる．以

数を変えて処理時間を計測した結果である．エグゼ

下のシミュレーションでは整数比分割を用いることとキュータの性能はケース 3 を用いた．図 3 を見ると，する．

提案手法である OXTHAS-N はラウンドロビンやラン

図 5 は，エグゼキュータの性能を先ほどのようにダムを用いた手法よりも良い値を示している．更に，ケース別に分けて処理ステップを測定した結果である．

OXTHAS-N の N の値が大きいほど，その効果はより大きいことが分かる．図 5 と図 6 により，提案しグラフから，OXTHAS-1 はラウンドロビンやランダムの手法と比較すると良い結果とはいえない．しかし，た OXTHAS スケジューリング戦略が有効であること

エグゼキュータが 3 台のときはラウンドロビンやランがいえる．

ダムの手法とはそれほど差異は見られなかった．その5. 2. 2 調整法に関する結果と考察ため，これは前述したキュー長の偏りが出たと考えら

図 7 は，故障が発生する場合にタイムアウトを変れ，エグゼキュータが 6 台であったため，3 台のとき化させていったときの調整法を用いない OXTHAS とよりも，その傾向が強く出てしまったと考えられる．

二つの調整法をそれぞれ用いた OXTHAS について比N = 2 以降の場合は，OXTHAS-N の方が有効であ較したものである．エグゼキュータ 6 台中の 1 台（エり，特にエグゼキュータ間の性能が大きく異なる場合，

グゼキュータ 2）を，2000 ステップ目に故意に故障さ提案手法が有効であることが分かる．

せて測定を行った．推定処理能力調整法は α = 1 と1000

論文／OXTHAS：Web サービスベースのワークフロー管理における障害を考慮した負荷分散手法

図 8 推定処理能力調整法の有無による OXTHAS の故障したエグゼキュータ 2 のキュー長の変化
Fig. 8 Transition of queue length in the crashed executor.

図 9 タイムアウト値調整法の有無による OXTHAS の故障したエグゼキュータ 2 の累計リトライ数の変化
Fig. 9 Transition of aggregated number of retries in
the crashed executor.

し，タイムアウト値調整法は β = Tinit /100 とした．

合の図 9 では，累計リトライ数が全処理が終わるス「5 台，タイムアウトなし」の線は故障させた 1 台を最

テップ数まで増加している．一方，タイムアウト値調

初から抜かしてエグゼキュータを 5 台でタイムアウト

整法を用いる場合では，故障したエグゼキュータ 2 累なしで測定したときの結果である．調整法を用いない

計リトライ数の増加は 4000 ステップほどで止まって

OXTHAS よりも調整法を用いた場合の方が，タイムいる．これは，タイムアウト値調整法により，タイムアウトの値が長くなっていったときの総処理ステップ

アウトの値が短くなりエグゼキュータ 2 から他のエグ数の低下を抑えていることが分かる．更に，タイムア

ゼキュータに早期に再割当が行われ，その結果全体のウトの値が 500 ステップから 1400 ステップの間では，処理も早く終わる．

「5 台，タイムアウトなし」よりも提案した調整法の方以上のことから推定処理能力調整法とタイムアウト

が効率良く処理が行われている．このことは，低信頼値調整法がエグゼキュータの故障時に有効であるといなエグゼキュータを含んだ 6 台のエグゼキュータの処

うことが分かる．また，二つの調整法の間に有意な差

理が高信頼な 5 台のエグゼキュータの処理に匹敵，若は見られないため，推定処理能力調整法とタイムアウ

しくは勝る場合もあるということを示している．

ト値調整法の間に相乗効果は見られない．

図 8 は各エグゼキュータのキュー長の変化を表し，
図 9 は故障したエグゼキュータ 2 の累計リトライ数の6. 関 連 研 究

変化を表す．これらの図はタイムアウトの値が 1000

Lie-jie Jin らは，プロセスインスタンスを一定時間ステップのときの 10 回の試行のうちのある 1 回の試ごとにワークフローエンジンに投入する際にワークフ

行についてのグラフである．他の試行についても同様

ローエンジンでの処理前の待ち時間を減らすようにどの傾向を示している．まず，推定処理能力調整法の効のワークフローエンジンに入れるかについての負荷

果について説明する．処理前半のキュー長の変化の傾分散手法を提案している [9]．その中で分散ワークフ

向については，処理されたアクティビティインスタン

ロー管理システムにおけるワークフローエンジン間スの数が少ないため，割当にばらつきが生じている．

の負荷分散を行うために負荷指標を定義している．し推定処理能力調整法を用いない OXTHAS の場合のかし，今回のように複数のワークフローエンジンがエ

図 8 では，故障に対して早期に反応できていないた

グゼキュータを共用する場合には，それぞれのエグゼ

め，故障後も長いステップ数の間，エグゼキュータ 2

キュータの負荷を計算し，その負荷に応じて処理を振のキュー長が増加している．一方，推定処理能力調整

り分ける負荷分散が重要となってくるが，この研究で法を用いた場合では，故障に対して早く反応し，そのはエグゼキュータ間の負荷分散に関しては対応していエグゼキュータにアクティビティインスタンスが割りない．

当たらず，別のエグゼキュータに割り当てられ（このまた，Koji Nonobe らが提案している資源制約付図の場合はエグゼキュータ 1，3，4），全体の処理が早きスケジューリング問題に関するアルゴリズム [10] や

く終わる．また，タイムアウト値調整法を用いない場

Eitan Franchtenberg が提案している並列ジョブスケ1001

電子情報通信学会論文誌 2008/4 Vol. J91–D No. 4

ジューリングにおいて，ジョブをその性質に応じてい力調整法とタイムアウト値調整法を提案した．そしくつかのクラスに分類し，割当時のクラスタのワークて，シミュレーションを行うことにより，OXTHAS

ロードに応じて柔軟にジョブを割り当てるアルゴリズ

スケジューリング戦略では推定処理能力の高いエグゼ

ム [11] などスケジューリングに関する研究がある．こキュータに処理負荷サイズの大きいアクティビティイ

れらは，ワークフローエンジンが一つであるような閉ンスタンスを多く割り当てる整数比分割が最適な領域

じたワークフロー管理システムにおける仕事の割当に分割方法であることを示した．また，OXTHAS スケ

関しては最短で処理が完了する割当方を提供してくれ

ジューリング戦略はランダムやラウンドロビンよりもる．しかし，複数のワークフローエンジンがあり，そ

効率良く処理を行うことが可能であり，調整法を用いれぞれのワークフローエンジンが自身の仕事にのみ割ることで障害の発生時にもその処理効率をあまり低下

当や監視を行っているような場合や，ネットワークのすることなく処理可能なことを示した．更に，適切な環境が動的に変化するような場合，このアルゴリズム

タイムアウトの値を設定することにより，低信頼なエをそのまま利用することはできない．

グゼキュータを含んでいても調整法を用いることで効更に，ワークフローにおいてプロセスインスタンス

率の良い処理を行うことが可能であることを示した．

の処理の順番を動的に変更することにより期日に遅れ

今後の課題としては，より効率的な再スケジューリン

るプロセスインスタンスの数を減らすスケジューリン

グ戦略にするための提案手法の改良や，OXTHAS-N

グ手法を提案している [12]．これは処理時間とルートにおける N 分割する際の分割方法について，より良を推測しプロセスインスタンスの処理の順番を適切にい方法を検討することが挙げられる．また，様々なプ

決定している．しかし，本研究が目的としている負荷

ロセスインスタンスの到着率やプロセスインスタンス

分散や障害対策については述べていない．

ごとにアクティビティインスタンスの数や種類が異な

その他に，分野は異なるが，Wireless ネットワーク

るとき，アクティビティインスタンスの処理負荷サイにおける場所依存の通信路の容量とエラーを考慮しズに偏りがある場合等に対応する必要がある．更に，たスケジューリングアルゴリズムを提案し，遅延とパエグゼキュータが複数のアクティビティインスタンス

ケットロスを改善する研究 [13] や，Web サーバにおいを同時に処理できる場合，ビジネスプロセスが分岐なて，小さなファイルを求めるリクエストから優先的にどを含む複雑なものである場合，エグゼキュータの故処理することによりキューでの待ち時間を減らし，パ

障が多発する場合やエグゼキュータが一部の種類のア

フォーマンスを改善する研究 [14] や，分散システムにクティビティインスタンスの処理ができないような部

おいて，遅延予測方法と遅延時間のマージンの決定方

分故障が発生する場合などの様々な状況に対応するよ法を提案し，それらを組み合わせ障害を検知する研究

うにすることなどが挙げられる．そして，実際にこのなどがある [15]．しかし，エグゼキュータが複数存在

ワークフロー管理システムを実現し，実際のシステムする場合や依存関係のある連続した処理について言及

でも同様の有効性がいえるかを検証することが重要でしていないため，Web サービスベースのワークフロー

ある．

管理システムにこれらの手法をそのまま適用すること謝辞はできない．

7. む す び

本研究の一部は，文部科学省科学研究費補助金特定領域研究 (16016232)，独立行政法人科学技術振興機構 CREST，及び東京工業大学 21 世紀 COE プ
ログラム「大規模知識資源の体系化と活用基盤構築」

本研究では，Web サービスベースの集中管理型ワーの助成により行われた．

クフロー管理における障害を考慮した負荷分散手法を文提案した．まず，ワークフロー管理アーキテクチャを説明し，ワークフローと Web サービスの特徴について説明した．そして，その特徴を利用したエグゼキュー

[1]

1002

戸田保一，飯島淳一，速水治夫，堀内正博，ワークフロー—
ビジネスプロセスの変革に向けて，日科技連出版社，1998.

[3] （株）日本ユニテック DigitalXpress 編集部，SOAP UDDI
WSDL Web サービス技術基礎と実践徹底解説，技術評論

グゼキュータの障害を考慮に入れて，タイムアウトを考慮して再スケジューリング戦略として推定処理能

Workﬂow Management Coalition.
http://www.wfmc.org/[2]

タ間の負荷分散手法として OXTHAS スケジューリン
グ戦略を提案した．更に，OXTHAS に基づいて，エ献[4]社，2002.
加藤英之，小林隆志，横田治夫，“ワークフローの自動実論文／OXTHAS：Web サービスベースのワークフロー管理における障害を考慮した負荷分散手法
行における障害対策，” DEWS2004, I-12-02, 2004.
[5]

N.B. Lakhal, T. Kobayashi, and H. Yokota, “Throws:
An architecture for highly available distributed execution of web services compositions,” Proc. RIDE
2004, pp.103–110, March 2004.

[6]

加藤英之，小林隆志，横田治夫，“Web サービスを用いた
ワークフローにおける負荷分散手法，” 信学技報，DE200546(2005-7), July 2005.

[7]

加藤英之，小林隆志，横田治夫，“Web サービスベースのワークフロー管理における障害を考慮したアクティビティ[8]

スケジューリング手法，” DEWS2006, 7C-o1, 2006.
T. Kobayashi, H. Katoh, and H. Yokota, “Activity scheduling in web-service based workﬂow man-小林

隆志 （正員）平 9 東工大・工・情報工卒．平 16 同大
大学院・情報理工・計算工・博士課程了．平14 同大学術国際情報センター助手．平 19

より名大大学院・情報科学・特任准教授，
現在に至る．工博．ソフトウェア開発方法
論，ソフトウェア再利用技術，複合メディアコンテンツの管理・検索，Web サービス連携などの研究に従事．情報処理学会，日本ソフトウェア科学会，日本データベース学会，ACM 各会員．

横田治夫 （正員：フェロー）

agement for balancing load and handling failures,”
L.J. Jin, F. Casati, M. Sayal, and M.-C. Shan, “Load昭 55 東工大・工・電物卒．昭 57 同大大学院・情報・修士課程了．同年富士通（株）．

balancing in distributed workﬂow management sys-

同年 6 月（財）新世代コンピュータ技術開

FMUIT2006, IEEE, 2006.
[9]

tem,” SAC2001, Aug. 2001.
[10]

K. Nonobe and T. Ibaraki, “Formulation and tabu
search algorithm for the resource constrained project

平 10 東工大・大学院情報理工・助教授．平scheduling problem,” in Essays and Surveys in Meta-

13 より同大学術国際情報センター教授，現在に至る．工博．主heuristics, ed. C.C. Ribeiro and P. Hansen, pp.557–

として分散インデクシング，データ工学向けアーキテクチャ，

588, Kluwer Academic Publishers, 2002.
[11]

発機構研究所 (ICOT)．昭 61（株）富士通研究所．平 4 北陸先端大・情報・助教授．

E. Frachtenberg, D.G. Feitelson, F. Petrini, and J.
Fernandez, “Adaptive parallel job scheduling with
ﬂexible coscheduling,” IEEE Trans. Parallel Distrib.

高機能ストレージシステム，ディペンダブルシステム等に関する研究に従事．日本データベース学会理事．ACM SIGMOD
日本支部長．情報処理学会，人工知能学会，IEEE，ACM 各
会員．

Syst., vol.16, no.11, pp.1066–1077, Nov. 2005.
[12]

G. Baggio, J. Wainer, and C. Ellis, “Applying
scheduling techniques to minimize the number of latejobs in workﬂow systems,” SAC2004, March 2004.

[13]

S. Lu, V. Bharghavan, and R. Srikant, “Fair scheduling in wireless packet networks,” IEEE/ACM Trans.
Netw., vol.7, no.4, pp.473–489, Aug. 1999.

[14]

M. Harchol-Balter, B. Schroeder, N. Bansal, and M.
Agrawal, “Size-based scheduling to improve web performance,” TOCS2003, May 2003.

[15]

R.C. Nunes and I. Jansch-Porto, “Qos timeout-based
self-tuned failure detectors: The eﬀects of the communication delay predictor and the safety margin,”
DSN2004, June 2004.

（平成 19 年 3 月 22 日受付，10 月 29 日再受付）

加藤英之

平 16 東工大・工・情報工学卒．平 18 同大大学院・情報理工・計算工・修士課程了．
現在，東芝ソリューション（株）．ワークフ
ロー管理，Web サービス連携に関する研究に従事．

1003