知的分散システム IDPS における データベース処理機構 IDPS

DEIM Forum 2012 C4-2
知的分散システム IDPS における
データベース処理機構 IDPS-DB に関する研究
原嶋
秀次†
大森
匡‡
†（株）東芝 ソフトウェア技術センター 〒212-8582 神奈川県川崎市幸区小向東芝町１
‡電気通信大学大学院情報システム学研究科 〒182-8585 東京都調布市調布ヶ丘 1-5-1
E-mail: †[email protected], ‡[email protected]
あらまし 知的分散システム IDPS は東芝が 1990 年代に開発・商用化した自律分散システムであり、主に制御用
を想定した耐障害分散処理システムである。IDPS 上で動作する自律分散データベースシステムとして原嶋ら
は、’87-‘97 まで IDPS-DB と呼ばれるデータベース処理機構を設計・開発してきた。本稿では、IDPS-DB の設計
をまとめ、その特徴的な技法として、自律分散システムに適したデータモデル、問い合わせ処理方式、トランザ
クション処理制御の各設計を述べる。また、実際に運用をおこなった結果から、自律分散システムにおけるデー
タベースシステムの要件を述べ、今日の広域データ管理技法への示唆としたい。
キーワード 分散データベース，自律分散システム，知的分散システム
Database system IDPS-DB on Intellectual Distributed Processing
System IDPS
Shuji HARASHIMA†
Tadashi OHMORI‡
†Corporate Software Engineering Center, TOSHIBA
1 Komukaitoshiba-cho, Saiwai-ku, Kawasaki-shi, Kanagawa, 212-8582 Japan
‡Graduate School of Information Systems, The University of Electro-Communications,
1-5-5 Chofugaoka, Chofu-shi, Tokyo, 182-8585 Japan
E-mail: †[email protected], ‡[email protected]
Abstract Intellectual Distributed Processing System (IDPS) is the autonomous distributed system developed in TOSHIBA
which is a fault-tolerant system mainly used as a control system. This paper summarizes a design of the IDPS-DB which is a
data management system on the IDPS. A data model of IDPS-DB which is suitable for autonomous distributed processing
systems, query processing, and transaction management on the IDPS are also described. An evaluation of those designs is
shown based on the practical use. Finally, we show the necessary properties to realize the flexible and reliable database system
on an autonomous distributed system.
Keyword Distributed Database，Autonomous Distributed System，IDPS
1. は じ め に
1990 年 代 に 開 発 し た 自 律 分 散 シ ス テ ム で あ る [4]-[9]。
1980 年 代 、 コ ン ピ ュ ー タ シ ス テ ム は LAN の 普 及 と
本 稿 で は 、IDPS 上 で 動 作 す る デ ー タ ベ ー ス 機 構 と し て
共に業務インフラとして急速に普及した。負荷分散や
原 嶋 ら が ’97 ま で 開 発 し た IDPS-DB と 呼 ば れ る 自 律 分
信頼性向上などの研究が各所で行われ実用化された
散データベースシステムの設計を述べる。特に、その
[1]。自 律 分 散 シ ス テ ム は こ の よ う な 背 景 に お い て 提 案
特徴的な技法として、自律分散処理に適したデータベ
されたシステムアーキテクチャで、集中管理部が存在
ース処理用のプロセス構成、問い合わせ処理方式、ト
せず自律的な機能要素の動的な連携で、求められる機
ランザクション処理方式を述べる。そして、実際の運
能を実現する。業務インフラとして使われるシステム
用結果から、これらの設計の有効性や留意すべき点を
の機能要件や負荷をあらかじめ明確にするのは現実的
述 べ て 、現 在 の 分 散 デ ー タ 管 理 技 法 へ の 示 唆 と し た い 。
ではなく、段階的な開発に適したシステムアーキテク
以 下 、 ２ 章 で IDPS の 概 要 を 述 べ 、 ３ 章 で IDPS-DB
チ ャ で も あ る [2],[3]。知 的 分 散 シ ス テ ム IDPS は 東 芝 が
の 設 計 を 述 べ る 。４ 章 で は IDPS-DB の 高 信 頼 化 技 法 を
紹 介 し 、５ 章 で シ ス テ ム 適 用 を 通 し て の 評 価 を 述 べ る 。
共 通 知識
・ 機 能 配分
・ 負 荷 分散
・ 共 有 資源 管 理
・ 故 障 管理
2. 知 的 分 散シ ス テ ム IDPS
知 的 分 散 シ ス テ ム IDPS は 東 芝 に お い て 研 究 ・ 開 発
固 有 知識
・ ジ ョ ブ仕 様
・ 機 能 仕様
・ 処 理 内容
した自律分散システムで、高い信頼性と可用性と共に
柔軟性のあるシステムを構築可能なプラットフォーム
図 2.2
で あ る 。IDPS-OS は 、IDPS を 構 成 す る 分 散 オ ペ レ ー テ
知的分散システムのオブジェクト
ィングシステムであり、オブジェクトの多重化や高信
頼 な 同 報 メ ッ セ ー ジ 通 信 を 提 供 す る [7],[8]。
2.1
知 的 分 散 シ ス テ ム IDPS の 基 本 構 成
図 2.1 に 知 的 分 散 シ ス テ ム IDPS の 構 成 を 示 す 。ハ ー
図 2.3 に IDPS の 構 成 例 と 処 理 の 特 徴 を 示 す 。シ ス テ
ムへの処理要求は、オブジェクト間の協力・協調によ
り実行される。
ド ウ ェ ア 的 に は 同 一 LAN 下 に 接 続 さ れ た 複 数 の コ ン
ピ ュ ー タ で 構 成 さ れ る 。 各 コ ン ピ ュ ー タ に は IDPS-OS
高信頼放送メッセージ通信
LAN （10Mbps)
が搭載され、サイト内のオブジェクト管理や後述する
LAN 上 の 高 信 頼 放 送 通 信 を 実 現 す る 。知 的 分 散 デ ー タ
IDPS-OS
IDPS-OS
協力
ベースの研究開発期間で用いたハードウェアは次の通
IDPS-OS
り。
協調
（排他制御や負荷分散など）
コンピュータ：
東 芝 パ ソ コ ン J-5030(CPU： 80386、 OS： C-DOS)
多重化による信頼度向上
産 業 用 コ ン ピ ュ ー タ ： G200、 G300(CPU： 80386、
OS：RTUX/386)（ 最 終 的 に は SUN OS 上 に 移 植 ）.
自律オブジェクトの集合で構成
サイトの追加・削除が可能
ネ ッ ト ワ ー ク ： イ ー サ ネ ッ ト 10Mbps
図 2.3 知 的 分 散 シ ス テ ム IDPS の 構 成 と 特 徴
各コンピュータ（サイト）には、自律オブジェクト
を搭載する。各オブジェクトは、まわりの状況から自
こ こ で 、「 協 力 」 と は 要 求 を オ ブ ジ ェ ク ト 群 が 互 い
身のとるべき動作を判断し、処理を実行する。新たな
に処理結果をやりとりすることにより、遂行すること
機能が必要となった際には、新たなオブジェクトを追
であり、
「 協 調 」と は オ ブ ジ ェ ク ト 間 で の 処 理 の 競 合 を
加することで、オブジェクト間の連携により、新規機
調整し、システム資源の有効かつ正しい利用（排他制
能が実現される。
御、負荷及び機能配分）することである。これらによ
りオブジェクトの追加や変更、削除、サイト間移動な
どが局所的な操作で実行できるのみならず、サイトダ
ウンなどのハードウェアの故障に対しても柔軟に対応
でき、拡張性、適応性、信頼性に優れたシステムの構
築が可能になる。
各オブジェクトの多重度を変更することで、機能単
位で信頼度の設定をおこなうことができる。また、シ
ステム稼働中のサイト追加やオブジェクトのコピー作
図 2.1
知 的 分 散 シ ス テ ム （ IDPS） の 構 成
成も可能である。
図 2.2 に オ ブ ジ ェ ク ト の 構 成 を 示 す 。 各 オ ブ ジ ェ ク
トは、すべてのオブジェクトが同様に有する共通知識
と、個別の固有知識からなる。固有知識はオブジェク
2.2 IDPS に お け る 高 信 頼 化 技 法
2.2.1
オブジェクトの多重化支援
IDPS で は 複 数 サ イ ト で オ ブ ジ ェ ク ト を 多 重 化 す こ
トに固有な機能を実現するためのデータと手続き群か
とにより、一部のサイトに障害が発生しても残りのサ
らなる。共通知識は排他制御、負荷分散などのシステ
イトに存在するオブジェクトにより処理の継続が可能
ム 全 体 の 管 理 に 必 要 な デ ー タ と 手 続 き 群 か ら な る (各
となる。
オブジェクトは共有メモリを有する複数のプロセスで
図 2.4 に 多 重 化 さ れ た オ ブ ジ ェ ク ト 間 で の メ ッ セ
構成され、メソッドに対応したプロセスがメッセージ
ージ通信例を示す。オブジェクト A と C が３重化、B
に応じて処理を行う構成であった。後に一部はマルチ
が ２ 重 化 さ れ て い る 。A か ら B お よ び 、B か ら C へ の
スレッド化された。) 。
メッセージは多重化されたレプリカから放送で送られ
る。このためいずれかのレプリカに故障が生じても、
期でそれぞれに独立して発行することが可能である。
少なくとも１つのレプリカが動作していればシステム
2.2.2
は止まることなく動作する。原則、通信は論理オブジ
フェイルストップ放送通信機構について
IDPS に お い て 、オ ブ ジ ェ ク ト の 正 し い ふ る ま い を 保
ェ ク ト 名 （ A,B,C な ど ） 指 定 で 行 な わ れ る 。 レ プ リ カ
証 す る た め 、LAN で 接 続 さ れ た 計 算 機 は 同 じ メ ッ セ ー
は非同期に動作し、相手オブジェクトの多重度や位置
ジ を 同 じ 順 序 で 受 信 す る こ と が 必 要 で あ る 。 IDPS-OS
を知る必要もない。
ではフェイルストップ放送通信プロトコルを導入して
多重化されたオブジェクトのレプリカ間の整合性
いる。動作は次の通りである。
は、フェイルストップ放送通信機構と、メッセ―ジ選
各 計 算 機 の 通 信 ユ ニ ッ ト は LAN 上 の メ ッ セ ー ジ
択 機 構 で あ る First-CN-Come に よ っ て 保 証 さ れ る 。 フ
を 常 に カ ウ ン ト し て お り 、 Accumulated Message
ェイルストップ放送通信とは、サイト間の各メッセー
Number (AMN)と し て 記 憶 し て い る 。あ る オ ブ ジ ェ ク ト
ジを放送通信によって全順序をつけてアトミックに行
がメッセージを送信する際には、そのオブジェクトが
う機構であり、障害サイトを自動停止させる通信機構
存 在 す る 計 算 機 の 通 信 ユ ニ ッ ト は AMN を メ ッ セ ー ジ
である。これを使うことで、複数サイト上で多重化さ
に 付 加 し て LAN に 放 送 す る 。も し 、受 信 し た い ず れ か
れ た オ ブ ジ ェ ク ト の 各 レ プ リ カ は 、 (メ ッ セ ー ジ ID に
の 計 算 機 で 送 ら れ た メ ッ セ ー ジ の AMN と 自 身 の AMN
よ っ て 同 一 と 判 定 さ れ る )メ ッ セ ー ジ を 、必 ず 、同 じ 順
が一致しなければ、どちらかの計算機が正常でないこ
番 で 受 信 す る こ と が 保 証 さ れ る 。一 方 、First-CN-Come
とを意味する。この場合、メッセージを送信した計算
は、全ての正常なレプリカが、他の多重化されたオブ
機 に「 site fail」メ ッ セ ー ジ を 送 出 し 、受 信 メ ッ セ ー ジ
ジェクトからの送出された同じメッセージに対してコ
をキューイングする。
ミットすることを保証する機構である。これら２つの
いずれかの通信ユニットがあらかじめ決められ
機構によって、レプリカ間での整合性と正しい結果を
た 一 定 期 間 内 に 事 前 に 決 め ら れ た 数 (Pre-Defined
得ることが保証される。
Number : PDN)の 「 site fail」 を 受 信 し た 場 合 は 、 自 身
が故障と判断し処理をただちに停止するか受信に失敗
したメッセージの再送を要求する。
A1
C1
B1
A2
PDN の 設 定 に よ っ て シ ス テ ム の 信 頼 性 を 設 定 す る
こ と が で き る 。 図 2.6 に IDPS-OS に よ る メ ッ セ ー ジ 受
C2
信 失 敗 の 検 出 プ ロ セ ス の 一 例 を 示 す 。(a)で は 、メ ッ セ
ー ジ を 受 信 ミ ス し た サ イ ト（ Site1）が 、他 の サ イ ト へ
B2
A3
メ ッ セ ー ジ を 送 付 す る こ と で AMN 不 一 致 を 検 出 す る
C3
ケ ー ス を 示 し て い る 。(b)で は 同 じ く 受 信 ミ ス し た Site1
が 他 の サ イ ト か ら の メ ッ セ ー ジ で AMN 不 一 致 を 検 出
図 2.4 放 送 通 信 に よ る 多 重 化 オ ブ ジ ェ ク ト の 起 動
し、それを他のサイトに知らせることで自身の受信ミ
スを検出するケースを示している。
Site 2
Site 1
・・・
Site N
Recv. Miss
図 2.5
メ ッ セ ー ジ ID
AMN Mismatch
Site-fail(1)
具 体 的 に は 、 First-CN-Come で は 、 あ ら か じ め 決 め
ら れ た confirmation number (CN)個 の 同 じ 内 容 の メ ッ セ
(a) 受 信 ミ ス サ イ ト か ら の 送 信 に よ る 検 出
し 処 理 ） す る 。 CN の 値 は オ ブ ジ ェ ク ト の 多 重 度 と は
独立して定義することができるので、関連するオブジ
Site 2
Site 1
ージを受信したときそのメッセージをコミット（受信
・・・
Site N
Recv. Miss
AMN Mismatch
ェクトの多重度に関係なく定義することができる。メ
Site-fail(1)
ッセージコミットまでの時間的な遅れも従来からの多
Site-fail(N)
数決を用いた方法より短くすることができる。メッセ
ー ジ を 認 識 す る た め の メ ッ セ ー ジ ID（ 図 2.5） も 、 各
レ プ リ カ (決 定 的 動 作 を す る こ と が 前 提 )に よ り 、 非 同
(b) 受 信 ミ ス サ イ ト で の 受 診 に よ る 検 出
図 2.6
フェイルストップ放送通信プロトコル
このプロトコルでは、集中管理部が存在せず、同期
動作も不要である。
提供するデータオブジェクト、内部ビューを提供する
ファイル処理オブジェクト、外部ビューを提供する質
問処理オブジェクトの３種類のオブジェクトである。
IDPS-DB に お け る 各 オ ブ ジ ェ ク ト を 図 3.1 に 、 こ れ
3.知
知 的 分 散 デ ー タ ベ ー ス IDPS-DB の 基 本 設 計 と 提 案
らオブジェクトとその機能を実現するメソッド群の対
方式
3.1
自律分散データ管理の課題
応 を 表 3.1 に 示 す 。
IDPS は 集 中 管 理 部 を 持 た ず に 信 頼 性 、拡 張 の 高 い シ
ステムの実現が可能であり、要求や負荷が常に変化す
表 3.1
IDPS-DB に お け る 各 オ ブ ジ ェ ク ト の メ ソ ッ ド
るシステムのプラットフォームとして開発された。
オブジェクト
メソッド
IDPS の デ ー タ 管 理 機 構 で あ る IDPS-DB 設 計 に 際 し て
質問処理オブジェクト
は、この特徴を継承し、かつ汎用性の高いデータ管理
質問文処理メソッド
最適化メソッド
自動結合メソッド
など
機能の実現を目標とし、次の設計方針とした
[10]-[12],[15],[16]：
・
データオブジェクト
関係操作メソッド
など
ファイル処理オブジェクト
データ検索メソッド
データ整列メソッド
など
自 律 オ ブ ジ ェ ク ト が デ ー タ を 管 理 し 、IDPS 上 の ア
プリケーションオブジェクトからの要望に応じてオブ
その後、効率性、管理の容易性などを考慮し、デー
ジェクト間の協力・協調でデータ操作を実現する。
データモデルは、開発時主流となりつつあったリ
タオブジェクトにファイル処理オブジェクトの機能も
レーショナルモデルとした。但し、マルチメディアデ
統合し、さらに複数リレーションを１つのデータオブ
ータなどの普及状況を踏まえ、新たなデータモデルの
ジェクトが管理する方式とした。
・
導入を可能な形とした。
・
データ（＝オブジェクト）の多重化により、信頼
3.3
IDPS － DB に お け る デ ー タ モ デ ル と 問 い 合 わ せ
性・可用性を確保する。
能力の設計
3.2 IDPS-DB の デ ー タ モ デ ル
わせ機能を有する。具体的には、
IDPS-DB は 、 リ レ ー シ ョ ナ ル モ デ ル 上 の 拡 張 問 い 合
IDPS-DB で は 、基 本 デ ー タ モ デ ル と し て リ レ ー シ ョ
－ドット表現を使った入れ子リレーショナルモデル
ナルデータモデルを採用した。オブジェクトの管理単
－ 不 完 全 な SQL 記 述 か ら 自 動 的 に 正 確 な SQL 文 を 作
位はリレーションとした。当初、データ独立性やビュ
成する自動検索機能
ーの変化に対する適応性などを満足させるため、いわ
の２つである。
ゆる３層スキーマにおける各層の機能を有するオブジ
前者は、リレーションの属性値としてのリレーショ
ェクトを設けた。すなわち、リレーショナルビューを
ン名の記述を許すもので、構造データの自然な表現を
可能とする。後者は、質問文における条件属性（群）
と、結果である目的属性（群）の間の結合パスの候補
をオブジェクト間のメッセージ交換により探索する機
能で、オブジェクト構成すなわちスキーマ構成が動的
に変化し得る自律分散システムでは有用な機能である。
詳 細 に つ い て は [10],[11]を 参 照 さ れ た い 。
3.4 シ ス テ ム 構 成 の 管 理 と 関 係 演 算 の 自 律 分 散 処 理 方
式
図 3.2 に IDPS-DB の シ ス テ ム 構 成 例 を 示 す 。 UNIX
や RTUX 上 に 実 現 さ れ た ミ ド ル ウ ェ ア で あ る 知 的 分 散
システムをベースとし、以下に示す 3 種類のオブジェ
クトによりデータベースを構成している。
図 3.1
IDPS-DB オ ブ ジ ェ ク ト 構 成
で処理を継続する。
システム状況の把握を都度行うには、処理効率が低
下 し な い こ と が 必 要 で あ る 。IDPS-DB の 処 理 効 率 に つ
いては次節で性能評価を、4 章で適用を通しての評価
を述べる。
LAN
図 3.2 IDPS-DB の オ ブ ジ ェ ク ト 構 成
UNIX/RTUX
UNIX/RTUX
IDPS-OS
IDPS-OS
・ サ イ ト マ ネ ー ジ ャ オ ブ ジ ェ ク ト （ SMGR）
システムを構成する各マシンに存在し、そのマシンに
3.処理方針の決定
SMGR
QPO
1.質問受付
アプリケー
ション
SMGR
2.状況の把握
DTO
R
DTO
R
DTO
S
DTO
S
部 を 管 理 す る 。各 サ イ ト に は IDPS-DB 以 外 の 機 能 や 役
IDPS-OS
SMGR
存在するリレーション名やオブジェクト数といったマ
シンに固有なデータベースのディクショナリ情報の一
UNIX/RTUX
(a) 状 況 の 確 認
割を与えられえていることが通常であり、それらを含
め た サ イ ト 情 報 管 理 機 能 と し て SMGR を 設 け た 。
・ 質 問 処 理 オ ブ ジ ェ ク ト （ QPO）
）
LAN
アプリケーションからの問い合わせ処理を受け持つ。
4.処理の依頼
QPO は 複 数 存 在 し 、 各 QPO は 同 時 に 複 数 の ア プ リ ケ
ーションの処理を行うことはない。アプリケーション
UNIX/RTUX
UNIX/RTUX
からの処理要求を受けつけるとその時点での各サイト
IDPS-OS
IDPS-OS
UNIX/RTUX
IDPS-OS
5.結果のマージと返答
のリレーション構成と負荷状況を同報メッセージで全
アプリケー
ション
QPO
サ イ ト の SMGR に 問 い 合 わ せ る 。そ の 結 果 を 受 信 後 に
最適な処理方法を決定し、関連するデータオブジェク
ト DTO へ 処 理 を 依 頼 す る 。結 果 は マ ー ジ な ど を お こ な
SMGR
SMGR
SMGR
DTO
R
DTO
S
4.処理の依頼
DTO
S
DTO
R
いアプリケーションに返答する。アプリケーションは
(b) 処 理 の 実 行
QPO と の や り と り だ け を 行 な え ば 良 い 。
図 3.3
・ デ ー タ オ ブ ジ ェ ク ト （ DTO）
）
IDPS-DB の 処 理 方 式 詳 細
データベースで使用されるデータを管理するオブジェ
クトであり、リレーションのスキーマや実データおよ
びインデックス用のデータ等を管理する。信頼性や性
3.4 IDPS－
－ DB に お け る 並 列 分 散 問 い 合 わ せ 処 理
ここでは、自律分散並列演算の例として、共通属性
能に対する要求に応じて複数のサイトにコピー（レプ
ｘを有する２つのリレーション R と S の結合を考える。
リカ）を配置することが可能である。同一オブジェク
ここで、R はｍ重化されており、S はｎ重化されてい
ト 名 の DTO は レ プ リ カ と し て 認 識 さ れ る 。
るとする。すなわち、R を管理するｍ重化されたデー
タオブジェクトと S を管理するｎ重化されたデータオ
IDPS-DB に お け る 処 理 方 式 は 、(a)質 問 を 受 け 付 け た
際 に シ ス テ ム 状 況 把 握 を 行 う ス テ ッ プ と 、(b)状 況 把 握
ブ ジ ェ ク ト が 存 在 す る 。リ レ ー シ ョ ン R と S の 間 の 並
列 結 合 は 準 結 合 (semi-join)を 用 い て 次 の 様 に 実 行 す る 。
の結果にもとづき最適な処理方法を決定・実行するス
テ ッ プ の ２ 段 階 に 分 け る こ と が で き る 。 (a)の 状 況 の
Step 1.
把 握 で は 、 QPO が SMGR に 対 す る 確 認 依 頼 を 放 送 し 、
当 て ら れ る 。割 り 当 て ら れ た QPO は 、質 問 と し て 結 合
一定時間内に返答のあったサイトが処理対象となる
属 性 ｘ に よ る R と S の 間 の 結 合 文 を 受 け 取 る 。こ れ を
ユ ー ザ か ら の リ ク エ ス ト に よ り 、QPO が 割 り
（ 図 3.3 (a)）。(b)で は QPO が コ ー デ ィ ネ ー タ と な っ て
受けると R と S を有するサイトへの負荷問い合わせを
(a) の 結 果 を 踏 ま え た レ プ リ カ の 利 用 に よ る 高 速 処 理
ブ ロ ー ド キ ャ ス ト す る 。 R と S、 そ れ ぞ れ の 多 重 度 、
を お こ な う （ 図 3.3 (b)）。 処 理 中 の サ イ ト ダ ウ ン な ど
結合にあたっての選択率を考慮して、R の値集合と
が 発 生 し た 場 合 は 、DTO か ら の 返 答 に 対 す る タ イ ム ア
TID の 集 合 を S の す べ て の レ プ リ カ に 送 る か 、 そ の 逆
ウ ト を QPO が 検 出 し 他 の レ プ リ カ に 振 り 替 え る こ と
にするかを決める。ここでは、R から S に送ると仮定
す る 。 QPO は 、 R の 各 レ プ リ カ Ri に つ い て 、 そ の 負
Step 3.
S の 各 レ プ リ カ は 、 QPO に よ っ て あ ら か じ め
荷 に 応 じ て Ri が 担 当 す る べ き 結 合 属 性 x の 値 の 範 囲 を
決 め ら れ た TID の 担 当 範 囲 内 で 、送 ら れ た ｘ の 値 と の
決 め て 、 当 該 範 囲 の 値 を 有 す る タ プ ル の TID を S の n
比 較 を お こ な う 。マ ッ チ し た S タ プ ル と R の TID の 対
個 の レ プ リ カ に 送 付 す る よ う 指 示 す る (R.x に イ ン デ ッ
の 集 合 を R に 返 答 す る （ 図 3.4 (c)）。
ク ス が あ る 場 合 で あ る 。 R.x に イ ン デ ッ ク ス が な け れ
Step 4.
R の 各 レ プ リ カ は 結 合 対 象 の TID を 受 け 取 る
ば 、 単 純 に R の タ プ ル ID の 範 囲 で 分 担 す る )。 指 示
の で 、そ の デ ー タ を 読 み 出 し 、 送 ら れ て き た S の タ プ
は R の 全 DTO へ マ ル チ キ ャ ス ト で 送 ら れ る（ 図 3.4 (a)）。
ル と の 結 合 を お こ な う (図 3.4 (d))。
同様に、S の各レプリカに、結合を実行する S のタプ
Step 5.
ル の TID の 担 当 範 囲 を 決 め て 伝 え る 。
からの結果をすべて受け取った後に重複を削除してマ
Step 2.
R の 各 レ プ リ カ は QPO か ら の メ ッ セ ー ジ を 受
リ ク エ ス ト を 出 し た QPO オ ブ ジ ェ ク ト は 、 R
ー ジ し て 最 終 結 果 を 得 る (図 3.4 (d))。
けると、属性ｘが指定された範囲の値を有するタプル
結合演算は、S の結合属性ｘにインデックスがあれ
を 読 み 出 し 、ｘ の 値 と 読 み 出 し た タ プ ル の TID の 対 の
ば index nested loop、 な け れ ば nested loop join を お こ
集 合 を S の ｎ 個 の レ プ リ カ に 送 付 す る 。す な わ ち 、R1
なう実装とした。
→ S1… Sn、 R2→ S1… Sn、 ・ ・ ・ 、 Rm→ S1… Sn と い
う メ ッ セ ー ジ が 送 付 さ れ る (図 3.4 (b))。 Ri か ら の 各 メ
ッセージは放送通信であり、１回のメッセージですべ
ての S のレプリカに送付することができる。
3.5 性 能 評 価
3.4 で 述 べ た 並 列 結 合 を IDPS-DB に 実 装 し 、 性 能 測
定 を お こ な っ た 結 果 を 示 す 。評 価 は 1990 年 の と き の も
の で あ る 。各 サ イ ト は イ ー サ ネ ッ ト で 結 合 さ れ て い る 。
各 サ イ ト は イ ン テ ル の 16 ビ ッ ト マ イ ク ロ プ ロ セ ッ サ
QPO
レプリケーションの存在と
負荷の問い合わせ（ブロードキャスト）
担当範囲通知
ー （ 80286 ） の ワ ー ク ス テ ー シ ョ ン 、 ネ ッ ト ワ ー ク は
10Mbps の イ ー サ ネ ッ ト で あ っ た 。
回答
対 象 リ レ ー シ ョ ン R と S は 、 共 に 1,000 タ プ ル を 有
R1
・・・
(a)
Rｍ
S1
Sｎ
・・・
し 、R は 12 バ イ ト 、S は 24 バ イ ト の タ プ ル 長 と し た 。
レプリケーションの状況とレプリカサイト
の 負 荷 の 把 握 と TID 範 囲 の 割 り 当 て
結 合 属 性 ｘ は 整 数 型 で 共 に B+木 型 の イ ン デ ッ ク ス を
有 す る （ 多 ： 多 結 合 ）。 結 合 率 は 10%と し て い る 。 実
験によると各サイトでの処理時間は、データの転送時
QPO
間より多くかかっており、サイト数の増加が処理時間
（属性値、TID）の集合送付
R1
・・・
Rｍ
S1
500
の短縮に効果があることが判明した。
Sｎ
・・・
▲
○
□
◆
●
450
(b) R か ら S へ 、 ｘ の 値 と TID の 対 の 集 合 を 送 付
R: n site, S: 1 site
R: 1 site, S: n sites
R: 2 sites, S: 2 sites
R: 3 sites, S: 2 sites
R: 2sites, S: 3 sites
Rｍ
・・・
S1
・・・
Sｎ
（ c） 選 択 さ れ た S の タ プ ル と R の TID の 対 の 集 合 を
400
350
R1
Time (sec)
QPO
Siでの結合結果として
（Sのタプル、Rの対応TID）の集合返送
300
R に返送
1
QPO
Riの結合結果
R1
・・・
2
3
4
5
6
Total number of sites
重複のマージと重複削除
図 3.5 IDPS-DB に お け る 並 列 結 合 の 性 能
Rｍ
S1
・・・
Sｎ
なお、選択演算などの 1 リレーションへの関係演算に
(d) R で の 結 合 実 行 と 結 果 マ ー ジ
ついても、当該リレーションがレプリカｍ個になって
m 個 の DTO に 管 理 さ れ て い る こ と を 使 っ て 、 DTO 間
図 3.4 IDPS-DB に お け る 並 列 結 合
で 演 算 実 行 す る TID 範 囲 を 分 担 し て 並 列 実 行 し 、最 終
的 に QPO で 結 果 を マ ー ジ す る よ う に な っ て い る 。
4. 高 信 頼 化方 式
るよう設計した。
IDPS-DB が 想 定 し た 業 務 系 シ ス テ ム へ の 適 用 で は 、
トランザクション管理によるデータ一貫性の確保は必
5. 適 用 に よる 評 価
IDPS-DB の 大 規 模 プ ラ ン ト 開 発 時 の コ ン カ レ ン ト エ
須である。
IDPS-DB で は 、２ 相 ロ ッ ク 及 び ２ 相 コ ミ ッ ト 規 約 で
ンジニアリング支援システムへの適用についてその概
各トランザクションを実行する。すなわち、トランザ
要 を 述 べ る 。大 規 模 プ ラ ン ト で は 、建 築 物 や 電 気 回 路 、
ク シ ョ ン 要 求 に 対 応 す る QPO が 2 相 ロ ッ ク 及 び ２ 相 コ
配管などを並行して数百名規模の技術者で設計し、図
ミ ッ ト 規 約 の コ ー デ ィ ネ ー タ と し て 動 作 し 、DTO へ の
面 の 規 模 は 数 千 枚 に お よ ぶ 。個 々 の 技 術 者 は 、CAD な
必要なロックの獲得、問い合わせ・更新処理の実行指
どの設計支援システムを使って設計を行う。設計は、
示 、コ ミ ッ ト 、ロ ッ ク 解 放 を 指 揮 す る 。各 DTO は 、自
各種の法令や社内基準にもとづく仕様を満たしていな
分が管理するリレーションに相当するファイルをロッ
ければならず、設計支援システムは設計結果がこれら
ク単位としている。したがって、ロック管理について
を満たしているかどうかをチェックする機能を有して
集 中 管 理 部 は 存 在 し な い 。 図 4.1 に 概 要 を 示 す 。
いる。また、各技術者による設計は他の設計と矛盾し
ていてはならず、そのチェックも必要である。これら
QPOが各トランザクショ
ンのコーディネータとな
り２相コミットを実行
の要求に対応するため、設計支援システムのデータ管
1.リクエスト アプリケーション
理システムに対しては次が求められる。
質問処理オブジェクト
QPO
SMGR
SMGR
アクセス速度：設計の実施や検証はトライアル＆エラ
3.ロック要求 2.オブジェクトの存在確認 質問処理オブジェクト
QPO
ーの繰り返しであり、数百名規模の技術者がストレス
4.アクセス
なく利用できることが求められる。
データオブジェクト A
DTO
データオブジェクト B
DTO
拡張性：対象プラントの規模により大きく変わる設計
データオブジェクト A
DTO
規模への柔軟な対応が必要。
分散対応：設計作業は地理的に分散して多くの拠点で
２相ロックにより、トランザ
クション間の競合を制御
進められるため、これへの対応も必要となる。
信頼性：承認済みの図面、設計中の図面、技術的難易
図 4.1
IDPS-DB に お け る ト ラ ン ザ ク シ ョ ン 管 理
度の高いもの、そうでないものなどをそれぞれの重要
度に応じた信頼度で管理できることが必要である。
ロック失敗などの際のアボートに対応するため、ファ
データ構造の透過性：設計支援システムからはデータ
イルシステムとしてシャドウファイルを採用し、迅速
の位置や多重度を意識することなく、データにアクセ
な処理を可能としている。
スできることが求められる。
自律分散システムで必須となるサイト構成の運転
時変化に対しても、矛盾のない対応を次のように実現
こ れ ら を 解 決 す る 手 段 と し て IDPS-DB を 用 い た プ
している。すなわち、サイト追加の際は、処理スター
ロ ト タ イ プ の 構 築 と 評 価 を 試 み た 。SunOS 上 の プ ロ セ
ト 時 に そ の 都 度 、シ ス テ ム 状 況 の 確 認 を し て い る の で 、
スとして動く設計支援システムをそのまま利用するこ
追加後の構成に応じた管理が自動的になされる。ある
と と し 、デ ー タ 管 理 と 検 索 を IDPS-DB で 行 う シ ス テ ム
トランザクションを処理中にいずれかのサイトが削除
と し て 大 規 模 プ ラ ン ト 顧 客 に て 運 用 し た 。IDPS-DB と
された場合は、タイムアウトによる検出をおこない、
の I/F に は RPC(Remote Procedure Call)を 利 用 し た 。 各
アボートを行うことで対応している。
設 計 支 援 シ ス テ ム は RPC を 介 し て IDPS-DB の QPO を
QPO に つ い て は 、IDPS 外 部 か ら の 利 用 を 考 慮 し て 、
呼 び 出 し 、 必 要 な デ ー タ の 検 索 や ロ ー ド 、 DB 書 き 換
多 重 化 し な か っ た 。こ の た め 、ト ラ ン ザ ク シ ョ ン T の
え （ 図 面 の セ ー ブ ） を お こ な う 。 当 該 シ ス テ ム は Sun
処 理 中 に 担 当 の QPO が 障 害 を 起 こ す と 、T は 中 断 と な
ワ ー ク ス テ ー シ ョ ン 相 当 （ 東 芝 AS シ リ ー ズ ） 2 ノ ー
る 。DTO は タ イ ム ア ウ ト 検 査 を 行 っ て お り 、コ ミ ッ ト
ドから始めて適宜増設する構成であった。
前なら矛盾の無い状態で自動アボートする。一方、コ
１つの図面に関するデータは複数のリレーション
ミ ッ ト 途 中 の QPO 障 害 で は 、 一 部 の DTO が ロ ッ ク 保
に 格 納 し 、 設 計 支 援 シ ス テ ム は こ れ ら を 検 索 (結 合 な
持のまま判定待機になる不定状態になる可能性がある。
ど )し て 図 面 を 構 成 す る 。新 た な 設 計 が 追 加 さ れ た 際 に
IDPS-DB で は 、こ の 場 合 の 処 理 は オ ペ レ ー タ 回 復 と し 、
は、データオブジェクトの追加で対応可能である。
シ ャ ド ウ フ ァ イ ル の 機 能 を 用 い て 全 DTO を ア ボ ー ト
プロトタイプの構築により、基本動作の確認と前述
またはコミットすることで整合性のある状態に復旧す
の要件をほぼクリアできることを確認した。アクセス
速 度 に つ い て は 、 当 時 の RDBMS 製 品 と 同 等 以 上 の 結
果を得た。拡張性については、リレーションの追加を
おこないつつ適宜サイトの追加をおこなうことで容易
に対応可能であることを確認した。これにより、管理
対 象 の 図 面 が 増 え た 場 合 に 、 RDBMS の 停 止 ・ 構 成 変
更やアプリケーションの変更無しで対応可能である。
信頼性はデータオブジェクトの多重化で、データ構造
の透過性は（既に対応済みである）設計支援システム
の RDBMS へ の 対 応 機 能 に よ り 解 決 で き た 。 分 散 対 応
については、データ管理システムとしては明らかに
IDPS-DB は 対 応 済 み で あ る
この事例に代表されるように、実際の運用時には、
IDPS-DB に は 一 貫 性 を 保 証 し た デ ー タ 管 理 能 力 と 結 合
演算を介したコンテンツデータの再構成能力や検索能
力 が 強 く 求 め ら れ た 。IDPS の オ ブ ジ ェ ク ト や 外 部 ア プ
リケーションへ一貫したデータを供給することが主な
役割であったからである。
質問受付時の動的システム状況の把握や関係演算
の並列分散実行、トランザクション管理の自律分散化
は、当初考えられた長期間運用時のシステム拡張でも
有 効 で あ っ た 。一 方 、IDPS-DB の 実 装 で は 、オ ブ ジ ェ
ク ト 管 理 や メ ッ セ ー ジ 配 信 の 高 信 頼 化 な ど 、 IDPS-OS
に依存した部分がある。特にメッセージ到着順序の同
一性保証はレプリカ同時更新やコミット処理の簡素化
と効率化の点で重要であった。
6. ま と め
本 稿 で は 、1990 年 代 に 東 芝 で 開 発・商 用 化 さ れ た 知
的 分 散 シ ス テ ム IDPS の デ ー タ 管 理 機 構 に 求 め ら れ た
課 題 と 、そ の 実 現 方 法 と し て の IDPS-DB に つ い て 設 計
の概要と評価をまとめた。前章で述べたように、自律
分散システムにおけるデータ管理機能方式と、適用を
通した有効性の確認について述べた。
本稿で述べたレプリカを利用した並列分散結合は、
現 在 の map/reduce ア ー キ テ ク チ ャ で 通 信 負 荷 が 高 い と
き の 結 合 方 式 [13],[14]に 近 い 。 ま た 、 自 律 分 散 シ ス テ
ムが耐障害分散アプリケーションを動かすため、デー
タベース側には一貫したデータ管理やスキーマ変化へ
の 対 応 能 力 が 強 く 求 め ら れ た こ と も 留 意 さ れ る 。IDPS
の 多 重 化 プ ロ セ ス で QPO を 実 現 す れ ば 耐 障 害 処 理 は
も っ と 見 通 し が 良 か っ た と は 言 え る 。IDPS-DB は 同 一
LAN 下 の ク ラ ス タ で あ り 、 IDPS の fail-stop 放 送 通 信
メッセージ機構のため、本質的にデータベースのネッ
トワーク分割を想定せずに済んだ点も指摘しておきた
い。
参
考
文
献
[1] A.S.タ ネ ン バ ウ ム 他 ： “ 分 散 シ ス テ ム 原 理 と パ
ラ ダ イ ム ” , ピ ア ソ ン エ デ ュ ケ ー シ ョ ン , 2003.10.
[2] 伊 藤 ： “ 自 律 分 散 シ ス テ ム 研 究 の 課 題 と 将 来 ” 、
計 測 と 制 御 、 vol.32, No.10、 pp.789-796, 1993.10.
[3] 森：“ 自 律 分 散 シ ス テ ム と 制 御 分 野 で の 実 用 例 ”、
計 測 と 制 御 、 vol.29, No.10, pp.923-928, 1990.10.
[4] 関 、長 谷 川：“ 高 信 頼 分 散 シ ス テ ム 構 築 支 援 OS：
知 的 分 散 OS” 、 情 報 処 理 学 会 誌 、 vol.36, No.8.,
pp.764-768, 1995.8.
[5] 田 村 他：”知 的 分 散 シ ス テ ム の ア ー キ テ ク チ ャ ”、
電 気 学 会 誌 108-C[6]、 1988.6.
[6] T.Seki et.al. : ”An Operating System for the
Intellectual Distributed Processing System –An
Object Oriented Approach Based on Broadcast
Communication-“, Journal of Information Processing,
vol.14, no.4. 1991.
[7] 関 他 ：“ 知 的 分 散 シ ス テ ム に お け る 高 信 頼 放 送
通 信 機 構 ” 、 電 子 情 報 通 信 学 会 論 文 誌 D-I,
vol.J73-D-I, no.2, 1990.
[8] 関 他 ：“ オ ブ ジ ェ ク ト 指 向 分 散 シ ス テ ム に お け
る 放 送 待 機 冗 長 処 理 方 式 ” 、 電 気 学 会 論 文 誌 D,
vol.114, no.3, 1994.
[9] S.Harashima, et.al. :”A Fault-Tolerant Subway
Passenger Information Control System –An Object
Oriented
Approach
Based
on
Broadcast
Communication-“, Proc. of 2nd ISADS, 1995.4.
[10] K.Nagase et. al: “IDPS Database System”, Proc. of
the 6th International Joint Workshop on Computer
Communication (JWCC-6), 1991.7.
[11] A.Howells et. al.: “ Partial Queries in a Dcentralised
Distributed Relational Database.”, Proc.of Future
Database, pp.97-105, World Scientific Publishers,
1992.4.
[12] S.Harashima et.al.: “Concurrency Control in IDPS
Database System”, Proc. of the 6th International
Joint Workshop on Computer Communication
(JWCC-6), pp.167-172, 1991-7.
[13] DM. AL Hajj Hassan, M.Bamha: “Semi-join
Computation on Distributed File Systems Using
Map-Reduce-Merge Model”, ACM Proceedings of
the 2010 ACM Symposium on Applied Computing,
pp.406-413, 2010.3.
[14] S.Blanas,J.M.Patel,V.Ercegovac,J.Rao:
”A
Comparison of Join Algorithms for Log Processing in
MapReduce”, ACM Proceedings of the 2010
international conference on Management of data,
pp.975-986, 2010.6.
[15]原 嶋 ： “ 知 的 分 散 シ ス テ ム IDPS に お け る デ ー タ
ベ ー ス 処 理 機 構 IDPS-DB に 関 す る 研 究 ”、 電 気
通信大学大学院情報システム学研究科博士論文,
2011.9.
[16]永 瀬 他 ： “ 知 的 分 散 デ ー タ ベ ー ス に お け る デ ー タ
管 理 方 式 ”、情 報 処 理 学 会 デ ー タ ベ ー ス シ ス テ ム
研 究 会 資 料 、 pp.49-57、 1993.9.