No | 116672 | |
著者(漢字) | フイーリフル ヒシャム サイド | |
著者(英字) | FEELIFL HISHAM SAIED | |
著者(カナ) | フイーリフル ヒシャム サイド | |
標題(和) | 並列データベースにおける実行時データ再配置手法に関する研究 | |
標題(洋) | Online Data Placement Reorganization for Parallel Database Systems | |
報告番号 | 116672 | |
報告番号 | 甲16672 | |
学位授与日 | 2001.09.28 | |
学位種別 | 課程博士 | |
学位種類 | 博士(工学) | |
学位記番号 | 博工第5084号 | |
研究科 | 工学系研究科 | |
専攻 | 情報工学専攻 | |
論文審査委員 | ||
内容要旨 | 近年データベースシステムの高性能化に対する要求は著しく高く、並列データベースシステムの導入が進みつつある。並列化により、多大なる性能向上が期待されるものの、ノード間の負荷の偏りにより必ずしもノード数に比例した性能を得ることは容易ではない。当該問題は、ノード間でデータの再配置を行うことにより改善されるが、全ノードにわたっての大量なデータの授受が発生する為一般にその負荷は小さくなく、通常処理効率を向上させるべくオフライン処理がなされることが想定されている。これに対し、最近の電子商取引サイト等では24時間の運用が通常化しており、システムの無停止性は必須要件となりつつある。この様な背景から、本論文では、通常のサービス処理と並行してデータ再配置の為の処理を行うオンラインデータ再配置技術について新しい手法を提案するものである。 並列データベースシステムでは各ノード間におけるデータアクセス負荷が異なると、一部のノードにアクセスが集中するため並列処理効率が低減する。そこで、並列データベースを構築するにあたっては、あらかじめ、各ノード間でのアクセス負荷が均等になるようデータの配置を行う。しかしながら、データアクセス特性はデータベースの利用目的により異なるが、多くは時間とともに変化し、データの再構成を行う必要が生じる。特にオンラインサービス処理では繰り返されるデータの更新により頻繁にデータ再配置を行う必要がある。さらに通常のサービス処理を停止せず並行してデータ再配置を行う必要があるため、データの再配置コストを最小にしスループットを維持しなくてはならない。また、オンライン処理では効率よくアクセスを行うために通常インデクスを構築しているため、データ再配置とともにインデクスの変更コストも考慮する必要がある。以上より、並列データベースシステムにおけるオンラインデータ再配置技法として、1)インデクス再構築技法、2)データアクセス特性の変化への対応、3)データ再配置処理パラメタ、4)データ再配置における構成技法の4点について論じる。 第一にインデクス再構築について論じる。オンライン処理におけるインデクスの再構築はインデクス木構造の多くの枝にまたがって行うと非常にコストがかかる。そこで、提案するデータ再配置技法では、各ノード間での再配置データの粒度をインデクスの変更コストを最小にするため、対象となるデータを含むインデクス木構造の最小の枝を転送の単位とする。この結果、ノード間データ転送は、元のノードにおける枝刈りおよびその配下のデータのバルク転送、転送先での枝の接合となり、インデクスの変更コストを最小限に押さえられる。しかしながら、データの動的再配置が収斂しない場合にデータ転送単位を比較的大きなサイズで行うと性能が逆に大きく劣化することとなる。すなわち、大きなデータ粒度における収束しないデータ再配置方式ではインデクス再構築コストおよびデータ転送コストが大幅に高くなり、システムの性能向上が得られないばかりか逆に性能低下を招く恐れがあるため、再配置のオーバーヘッドコストを考慮し、システム処理として一定の性能を保証しなくてはならない。 そこで、データ再配置コストとのトレードオフを考慮し、データマイグレーションが収束することを保証できるデータ再配置決定方式を提案する。その結果、マイグレーション粒度として選択されたインデクス枝が決まるため、再配置の収束が保証されることになる。本方式により、再配置要求が生じた場合に、処理エレメント間での負荷分散が可能なかぎり均等かつ高速に行われることとなる。 第三に、データ再配置時のデータ配置のチューニングに関して論じる。データ再配置処理性能をあらわすパラメタを導入することで、各サービス処理が要求するデータ再配置処理を可能とする。たとえば、データ再配置時の性能低下を調整するために、処理スピードパラメタを導入する。このパラメタを設定することにより、1ステップの再配置あるいは複数ステップの再配置を行うなどの調整が可能となる。このように、パラメタを導入することで、多くのデータ再配置手法を選択することが可能となり、容易にオンラインデータ再配置処理を導入することが可能となる。 第四にデータマイグレーション処理に関する設計方針に関して論じる。ここでは、リニアおよびリング構成の場合のデータマイグレーションについて検討を行う。リニア構成は初期データ配置方式として、また、レンジ分割方式に基づくマイグレーション方式として良く知られた方式であり、すでに多くの処理技法が提案されている。そこで、より多くのデータマイグレーション方針を可能とするリング構成を導入する。その結果、より再配置コストをおさえることが出来る。実験結果から、双方の構成とも、処理負荷を均等にするといく観点からは同等であるが、再配置コストはリング構成の場合がはるかに良いことが確認できた。この結果より、オンラインデータ再配置コストに対して、データ移動時のノード間構成も大きな要素のひとつであることが確認できた。 以上、本論文は並列データベースシステムにおけるオンラインデータ再配置技法に関して検討を行い、高性能な新しい処理技法を提案し、提案された処理技法の有効性について実証した。 | |
審査要旨 | 本論文は「並列データベースにおける実行時データ再配置に関する研究」と題し、複数ノードから構成される並列データベースシステムにおいて、特定のノードにデータアクセスが集中するとシステムの性能が大幅に低下することから、常時アクセス頻度情報を維持し、負荷が全ノードに対して均衡化するように、通常のデータベースアクセス処理と並行してデータ再配置を行う手法を提案している。再配置のためのデータ移送機構、データ移送速度の調整機構などに関して種々の要素技術を提案すると共に、シミュレーションにより定量的にその有効性を論じており、7章から構成される。 第1章は序論であり、本研究の背景および目的について概観し,本論文の構成を述べている。 第2章は「研究の背景および関連研究」と題し、並列データベースシステム上における実行時データ再配置技法に関し、現時点までに提案されている各種データ再配置技法についてその得失を纏めるとともに、従来の手法におけるデータ再配置の非効率性等、種々の問題点を明らかにしている。 第3章は「オンラインデータ再配置方式」と題し、実行時データ再配置方式について論じている。並列データベースシステムにおける複数ノードに分割して配置されたインデクスの役割を明らかにすると共に、実行時再配置処理における再編成コストを詳細に検討し、インデクス構造の変更を低減するべく、粒度の大きいインデクスの枝を移送対象とする負荷均衡化手法について定量的に評価を行っている。又、従来の手法では、アクセス頻度分布によっては不要なデータ移送が繰り返し発生し、データ再配置コストが高くなる問題点を指摘し、当該問題を回避する新しい再配置手法を提案している。 第4章「実行時データ再配置方式における再配置速度の調整」では、再配置処理に起因する通常データベースアクセスに関する性能劣化について論じている。データ再配置処理の速度を調整するパラメタを導入することにより、通常のデータベースアクセス性能への影響を制御可能とする手法を提案するとともに、その有効性を明らかにしている。 第5章は「再配置コストの考察」では、3章、4章において提案した一次元状に結合された複数のノードから成る並列データベースシステムに対する実行時再配置手法を拡張し、リング結合された並列データベースシステムに関する再配置手法に関して検討している。リング結合された場合のデータ再配置アルゴリズムを提案すると共に、当該手法により、一次元結合されたシステムに比べ大幅に再配置コストを低減出来ることを明らかにしている。 第6章は「性能評価」と題し、詳細なシミュレーションにより、種々の状況において、従来手法と比較し、提案手法の有効性を明らかにしている。実行時データ再配置処理によって大きく性能を向上出来ることを明らかにすると共に、当該処理による通常データベースアクセス処理への影響を評価している。また、第4章で提案した再配置処理速度パラメタの効果を定量的に明らかにしている。さらに、第5章で提案したリング結合による性能向上に関しても詳細な比較を行い、その効果を明らかにしている。 第7章「結論」は本論文の成果と今後の課題について総括している。 以上要するに、本論文は、複数ノードから構成される並列データベースシステムにおいて、特定ノードに対する負荷集中による性能劣化の問題を取り上げ、アクセス頻度情報を維持し、負荷が全ノードに対して均衡化するように、通常のデータベースアクセス処理と並行してデータ再配置を行う手法を提案し、シミュレーションにより定量的にその有効性を明らかにしており、情報工学上貢献するところが少なくない。 よって本論文は博士(工学)の学位請求論文として合格と認められる。 | |
UTokyo Repositoryリンク |