JPH047652A - 分散データ制御装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、任意の粒度をもつデータ項目が一意に定まる
識別子を有し、該データ集合体がコンピュータネットワ
ーク上に複写分散して存在することが可能な分散データ
システムに利用する。特に、アプリケーションプログラ
ムからのデータアクセス要求に対して対応するデータが
自ノード内に存在すれば該データを、存在しなければ他
ノードから取得したデータを返却し、アクセスしたデー
タは、過去のアクセス傾向に基づいて将来性を予測する
優先度を設けて自ノード内に保持する分散データ制御装
置に関する。

〔概要〕

本発明は、データ集合体がコンピュータネットワーク上
に複写分散して存在する分散データシステムにおいて、 イ也ノードおよび自ノードからアクセスしたテ°−タを
過去のアクセス傾向に基づき将来性を予想する優先度を
設けて保持することにより、無駄なデータ通信を極小化
することができるようにしたものである。

〔従来の技術〕

従来、この種の分散データ制御装置は、コンビエータネ
ットワークを介して自ノードに存在しないデータを他ノ
ードから取得する手段がアプリケーションプログラムに
とってネットワーク透過的に提供されることに限られて
いて、他ノードから取得したデータはアプリケーション
プログラムに渡された後にアプリケーションプログラム
独自の管理に委ねられていた。一方、他ノードからのデ
ータをキャッシュする仕掛けを有するシステムも存在す
るが、データの母集団全体をかえる方法か、または、必
要な単位に細分して管理する場合でも、自ノードの限ら
れた容量内での保持優先度は一義的に定められていて、
実装の容易性からアクセスした順に置換するＦＩＦＯ置
換アルゴリズムやアクセスの古い（同一データに対して
は新しい方が有効）順に置換するＬＲＵ置換アルゴリズ
ムが単独で使用されていた。

〔発明が解決しようとする課題〕

このような従来の分散データ制御装置は、キャッシュ手
段が備わっていない場合に、アプリケーションプログラ
ムが独自にアクセスデータ管理を行わない限り自ノード
の分散データ管理システムは過去にアクセスしたデータ
を忘却しているので、アプリケーションプログラムが発
行するデータアクセス要求ごとにたとえ既にアクセスし
たデータに対しても他／−ドヘデータ取得要求を出して
データ通信を実行しなければならない欠点がある。

また、キャッシュ手段が備わっている場合でも、該デー
タを含む母集団全体をかかえる方式では、自ノードのデ
ータ保持容量の制限を受けて充分に機能しないこともあ
るし、アクセスすることのない不要なデータを通信する
無駄が生じること、マスクデータの更新の反映について
もアクセスすることのない不要なデータに対して実行し
なければならないことなどの欠点がある。

次に、必要な粒度でデータ置換を行うキャッシングを実
現している場合に上述した問題点は解決されるが、ＦＩ
ＦＯ置換方式では、アプリケーションプログラムが有す
るデータアクセスの局所性（過去よく使ったものは未来
もよく使う、先程使ったものは次にも使うといった性質
）が充分に活かせていない。また、ＬＲＵ置換方式では
、データアクセスの局所性を比較的よく反映しているも
のの一律に用いるには不適切であり、アプリケーション
プログラムの動作いかんにより予想が大幅にはずれてキ
ャッシュのヒツト率が悪くなることがありうる欠点があ
る。

本発明はこのような欠点を除去するもので、無駄なデー
タ通信を極小化することができる分散データ制御装置を
提供することを目的とする。

〔課題を解決するための手段〕

本発明は、分散データベースを有する複数のノードのそ
れぞれに含まれ、自ノードのアプリケーションプログラ
ムの要求データに対応する第一データが自ノードに存在
するときはこの第一データを取得し、自ノードに存在し
ないときは他ノードに要求して上記要求データに対応す
る第二データを取得する要求ステージング手段を備えた
分散データ制御装置において、上記第一データをアクセ
ス時系列に保持するアクセス履歴保持手段と、上記第二
データを上記第一データとして追加したデータ量が規定
容量を超えるときに上記アクセス時系列を参照してアク
セスが最古のデータを置換するＬＲＵデータ置換手段と
、このＬＲＵデータ置換手段での置換対象を最新のデー
タとするＭＲＵデータ置換手段と、区間アクセス頻度を
記録するアクセス傾向監視手段と、この区間アクセス頻
度を基準値と比較した結果に応じてデータ置換手段の切
替えを実行する置換方法適性化手段とを備えたことを特
徴とする。

〔作用〕

コンビコータネットワーク上で自ノードのアプリケーシ
ョンプログラムが発行するアクセス要求に基づいて他ノ
ードから得たデータを自ノードに取り込む際に、自ノー
ドのデータ保持容量制限および更新情報反映効率化への
対処として置換すべきデータから不要データを選択する
ために、ＬＲＵデータ置換法およびＭＲＵデータ置換法
をその実システムに対する適合性に応じて使い分けるこ
とにより、また、アプリケーションプログラムによるデ
ータ保持優先度指定を採用して補正する。

これにより、最適データ置換アルゴリズムへのより良い
近似を実現する。

〔実施例〕

以下、本発明の一実施例について図面を参照して説明す
る。

第１図は、この実施例の構成を示すブロック図である。

第２図は、分散データベースの構造図である。第３図は
、アクセス傾向監視手段および置換方法適正化手段の動
作を表すフローチャートである。

まず、本実施例の構成を第１図および第２図に基づいて
説明する。この実施例は、分散データ管理システム１と
、アプリケーションプログラム２および分散データベー
スとで構成されている。分散データ管理システム１は、
アクセス要求解析手段１１と、要求ステージング手段１
２と、ＬＲＵデータ置換手段１３と、ＭＲＵデータ置換
手段１４と、アクセス履歴保持手段１５と、アクセス傾
向監視手段１６と、置換方法適正化手段１７と、アクセ
スデータ返却手段１８とで構成される。アプリケーショ
ンプログラム２は、データアクセス要求手段２１と、ア
クセスデータ受取手段２２とで構成される。ここで、要
求ステージング手段１２は、存在ノード判定手段１２１
　と、自ノードデータアクセス実行手段１２２と、他ノ
ードデータ取得要求受取手段１２３とから構成され、ア
クセス履歴保持手段１５は、自動優先度設定手段１５１
と、指定優先度設定手段１５２とから構成される。また
、分散データベースは、アクセス時系列部と、インデク
ス部と、データ部とで構成され、データ部は、任意の粒
度のデータ項目（たとえば、フィールド、レコード、ブ
ロック、テーブル、ファイルなど）が順不同に並んでい
て、データ識別子（以下、キーという）により一意に定
まるデータの集合である。インデクス部は、キーと対応
するデータを指すポインタとの対の配列でできていて、
キーの値でソーティングされている。

アクセス時系列部は、対応するデータがアクセスの新し
い順（同一のデータに対しては新しい方を採る）になる
ようなキーの連鎖でできていて、特別な２つのポインタ
、最新ポインタと最古ポインタが設けられていて、前者
はキ一連鎖の最も新しいエントリを、後者は最も古いエ
ントリを指す。

また、ｎ個のエントリ（データの個数をｎ個とする）の
内、連鎖の新しい方からｎ／２（端数は切上げ）番目ま
でのものに対応するデータのアクセス回数を数えるカウ
ンタとして前半アクセスカウンタＣ１を、残りに対する
ものとして後半アクセスカウンタＣ２を、自ノード内に
データが存在せずに他ノードに対してアクセスした回数
を数えるカウンタとして外部アクセスカウンタＣ３を、
すべてのアクセス回数を数えるカウンタとして総アクセ
スカウンタＣＯを備える。ただし、上記の分散データベ
ースは必ずしも二次記憶上に存在するものとも限らず、
必要に応じて主記憶にロードされるし、主記憶にのみ存
在することもある。

すなわち、この実施例は、分散データベースを有する複
数のノードのそれぞれに含まれ、自ノードのアプリケー
ションプログラムの要求データに対応する第一データが
自ノードに存在するときはこの第一データを取得し、自
ノードに存在しないときは他ノードに要求して上記要求
データに対応する第二データを取得する要求ステージン
グ手段１２を備え、さらに、本発明の特徴とする手段と
して、上記第一データをアクセス時系列に保持するアク
セス履歴保持手段１５と、上記第二データを上記第一デ
ータとして追加したデータ量が規定容量を超えるときに
上記アクセス時系列を参照してアクセスが最古のデータ
を置換するＬＲＵデータ置換手段１３と、このＬＲＵデ
ータ置換手段１３での置換対象を最新のデータとするＭ
ＲＵデータ置換手段１４と、区間アクセス頻度を記録す
るアクセス傾向監視手段１６と、この区間アクセス頻度
を基準値と比較した結果に応じてデータ置換手段の切替
えを実行する置換方法適性化手段１７とを備える。

次に、この実施例の動作を第１図、第２図および第３図
に基づいて説明する。

最初にアプリケーションプログラム２から発行されるデ
ータアクセス要求に対してデータがいかにしてアプリケ
ーションプログラム２にわたされるしくみを説明し、次
に、自ノードでの保持データの置換方法適正化のしくみ
を説明する。

アプリケーションプログラム２がデータアクセス要求手
段２１によって分散データ管理システム１に対してキー
Ｘを介したデータアクセス要求を発行すると、アクセス
要求解析手段１１は、受は取った要求を解析してキー情
報を要求ステージング手段１２へ渡し、また、アクセス
データの自ノードでの保持優先度をアクセス履歴保持手
段１５に渡す。

存在ノード判定手段１２１は、キー情報に基づいて自ノ
ードの分散データベース内のインデクスを使ってキー検
索を実行する。キーはソーティングされているので、−
船釣な二分検索方（バイナリサーチ）を用いて高速化を
図る。自ノード内に対応するデータが存在すれば自ノー
ドデータアクセス実行手段１２２に制御を渡し、さもな
ければ他ノードデータ取得要求受取手段１２３に制御を
渡す。自ノードデータアクセス実行手段１２２は、キー
検索で得られたポインタに基づきデータ部から対応する
データの読み取りを実行してアクセス履歴保持手段１５
に制御を渡す。他ノードデータ取得要求受取手段１２３
は、あらかじめ定められた特定のノード（たとえば親コ
ンピユータ）か、または、複数の不特定のノードに対し
て（たとえばＬＡＮの同報）データ取得要求を出し、デ
ータを受は取る。

受は取ったデータを自ノードの分散データベースに登録
する際に、データ保持容量に余裕があれば（インデクス
のエントリ数がｎに満たない場合）データを書き込んで
対応するキーエントリを追加し、インデクス部全体をキ
ーの値でソーティングしておく。余裕がない場合（イン
デクスのエントリ数がｎ）には、ＬＲＵデータ置換運用
中ならば、ＬＲＵデータ置換手段１３によって、アクセ
ス時系列内の最古ポインタが示すエントリと、インデク
ス部の対応するエントリと、データ部の対応するデータ
とを削除した後に上述した余裕のない場合の処理を施し
、制御をアクセス履歴保持手段１５に移す。ＭＲＵデー
タ置換運用中の場合には、最新ポインタが示すエントリ
に対して同様に処置をする。アクセス履歴保持手段１５
は、アクセスしたばかりのデータに関する情報をアクセ
ス時系列部に反映させるために、該当するキーエントリ
をアプリケーションプログラム２からの保持優先度指定
がなければ、自動優先度設定手段１５１によって最新ポ
インタが指す最先頭に挿入し直しくもともと存在してい
るエントリは入れ替え、そうでない場合は追加をチェー
ンの張り替えにより行う）、保持優先度指定があれば、
指定優先度設定手段１５２によってあらかじめ定められ
た対応する位置（たとえば、最古ポインタが指す最後尾
）に挿入する。

以上の処理が終了すると、アクセスデータ返却手段１８
によってデータがアプリケーションプログラム２のアク
セスデータ受取手段２２に渡されてデータアクセス要求
処理が完結する。

次に、自ノードでの保持データの置換方法適正化のしく
みについて説明する。

アクセス傾向監視手段１６は、総アクセスカウンタＣＯ
と、前半アクセスカウンタＣ１と、後半アクセスカウン
タＣ２と、外部アクセスカウンタＣ３とを有し、アクセ
ス履歴保持手段１５内でそれぞれのカウントアツプを行
う。また、あらかじめ定められた運用上適正とみなせる
時間間隔てカウンタを０クリアし、置換方法適正化手段
１７の判断材料である運用中のデータ置換方式の適合度
を知るためのアクセス頻度のベースとなる監視区間を刷
新する。置換方法適正化手段１７は、ＬＲＵデータ置換
運用中にはアクセス時系列の新しいほうの半分が他方に
比べてヒツト率が高いか、すなわち、データアクセス傾
向がＬＲＵデータ置換方式に適合しているか否かを前半
アクセスカウンタｃ１と後半アクセスカウンタＣ２との
比較により判断し、そうであるなら運用状況良好とみな
し、さもなければ不適合と判断してＭＲＵデータ置換方
式に切り替える。ＭＲＵデータ置換運用中でも同様で、
不適合の場合にはＬＲＵデータ置換方式に切り替える。

また、これらの方策は、近い過去の状況は近い将来でも
継続するであろうとの推測に基づくものであるが、特殊
なアクセス傾向をもつアプリケーションプログラムに対
しては、個別に優先度を宣言することによりこの方策に
よる不都合な動作を補完する。

〔発明の効果〕

本発明は、以上説明したように、コンピュータネットワ
ーク上で自ノードのアプリケーションプログラムが発行
するアクセス要求に基づいて、データ所在場所の透過性
を保証する分散データ管理システムが他ノードがら得た
データを自ノードに取り込む際に、自ノードにおけるデ
ータ保持容量制限および更新情報反映効率化への対処と
して置換すべきデータから不要なデータを選定するため
に、近い将来のアクセス可能性を近い過去のアクセス傾
向から推定する方法として「さきほど使ったものはもう
すぐ使う」とするＬＲＵデータ置換方式と、「さきほど
使ったものはとうぶん使わない」とするＭＲＵデータ置
換方式とを実システム稼働中にそれぞれの方式適合性を
監視分析して使い分けることにより、さらに、アプリケ
ーションプログラムによる明示的なデータ保持優先度指
定を採用して補正することにより、未来のアクセスすべ
てを知ることができた場合の理想としての最適データ置
換アルゴリズムのよりよい近似となり、無駄なデータ通
信を極小化することができる効果がある。

【図面の簡単な説明】

第１図は、本発明実施例の構成を示すブロック構成図。 第２図は、分散データベースの構造図。 第３図は、アクセス傾向監視手段および置換方法適正化
手段の動作を示すフローチャート。 １・・・分散データ管理システム、２・・・アプリケー
ションプログラム、１１・・・アクセス要求解析手段、
１２・・・要求ステージング手段、１３・・・ＬＲＵデ
ータ置換手段、１４・・・ＭＲＵデータ置換手段、１５
・・・アクセス雁歴保持手段、１６・・・アクセス傾向
監視手段、１７・・・置換方法適正化手段、１８・・・
アクセスデータ返却手段、２１・・・データアクセス要
求手段、２２・・・アクセスデータ受取手段、１２１・
・・存在ノード判定手段、１２２・・・自ノードデータ
アクセス実行手段、１２３・・・他ノードデータ取得要
求受取手段、１５１・・・自動優先度設定手段、１５２
・・・指定優先度設定手段。

Claims (1)

1. 【特許請求の範囲】 １、分散データベースを有する複数のノードのそれぞれ
   に含まれ、自ノードのアプリケーションプログラムの要
   求データに対応する第一データが自ノードに存在すると
   きはこの第一データを取得し、自ノードに存在しないと
   きは他ノードに要求して上記要求データに対応する第二
   データを取得する要求ステージング手段を備えた分散デ
   ータ制御装置において、 上記第一データをアクセス時系列に保持するアクセス履
   歴保持手段と、 上記第二データを上記第一データとして追加したデータ
   量が規定容量を超えるときに上記アクセス時系列を参照
   してアクセスが最古のデータを置換するＬＲＵデータ置
   換手段と、このＬＲＵデータ置換手段での置換対象を最
   新のデータとするＭＲＵデータ置換手段と、区間アクセ
   ス頻度を記録するアクセス傾向監視手段と、 この区間アクセス頻度を基準値と比較した結果に応じて
   データ置換手段の切替えを実行する置換方法適性化手段
   と を備えたことを特徴とする分散データ制御装置。