論文 / 著書情報
Article / Book Information
論題(和文)

並列 B-tree 構造における負荷分散処理時の並行性制御の評価

Title(English)

Evaluation of Concurrecy Control for Load-Balancing Operations on a
Parallel B-tree Structure

著者(和文)

吉原 朋宏, 小林大, 田口亮, 横田治夫

Authors(English)

Tomohiro Yoshihara, Dai Kobayashi, Ryo Taguchi, Haruo YOKOTA

掲載誌(和文)DEWS2007論文集

Citation(English)

Proceedings of DEWS2007

Vol, no, pages

Vol. , No. , pp. L5-2

発行日 / Pub. date2007, 3

URL

http://search.ieice.org/

権利情報 / Copyright

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

Powered by T2R2 (Science Tokyo Research Repository)

DEWS2007 L5-2

並列 B-tree 構造における負荷分散処理時の並行性制御の評価
吉原 朋宏†

小林

大†,††

田口

亮†††

横田 治夫††††,†† 東京工業大学大学院情報理工学研究科計算工学専攻 〒 152–8552 東京都目黒区大岡山 2–12–1†† 日本学術振興会特別研究員 DC††† 日本放送協会放送技術研究所 〒 157–8510 東京都世田谷区砧 1–10–11†††† 東京工業大学学術国際情報センター 〒 152–8550 東京都目黒区大岡山 2–12–1
E-mail: {†yoshihara, †,††daik}@de.cs.titech.ac.jp, †††taguchi.r-cs@nhk.or.jp, ††††,†yokota@cs.titech.ac.jp
あらまし 並列データベースや分散ストレージシステムのインデックス構造に並列 B-tree 構造を用いることは有効であり，我々はこれまで並列 B-tree 構造に適した並行性制御手法を提案してきた．また，データマイグレーションは並列データベースや分散ストレージシステムにおける負荷分散を行うための有効な技術であるが，並列 B-tree 構造を用いている場合，データマイグレーション時の並行性制御も重要となる．本稿では，我々が提案してきた並行性制御手法をデータマイグレーション時の並行性制御に適用する．並列 B-tree 構造である Fat-Btree を採用している自律ディ
スクにおいて，データマイグレーションが発生する環境で実験を行い，それらの手法が常にスループットを改善し，データマイグレーション時の並行性制御として有効であることを示す．
キーワード 並行性制御，アクセスパス，並列 · 分散 DB，並列 B-tree，データマイグレーション

Evaluation of Concurrecy Control for Load-Balancing Operations
on a Parallel B-tree Structure
Tomohiro YOSHIHARA† , Dai KOBAYASHI†,†† , Ryo TAGUCHI††† , and Haruo YOKOTA††††,†† Department of Computer Science, Graduate School of Information Science and Engineering,Tokyo Institute of Technology 2–12–1 Ookayama, Meguro-ku, Tokyo 152–8552, Japan†† Research Fellow (DC), Japan Society for the Promotion of Science††† Science and Technical Research Laboratories, Japan Broadcasting Corporation
1–10–11 Kinuta, Setagaya-ku, Tokyo 157–8510, Japan†††† Global Scientiﬁc Information and Computing Center, Tokyo Institute of Technology
2–12–1 Ookayama, Meguro-ku, Tokyo 152–8550, Japan
E-mail: {†yoshihara, †,††daik}@de.cs.titech.ac.jp, †††taguchi.r-cs@nhk.or.jp, ††††,†yokota@cs.titech.ac.jp
Abstract We have proposed concurrency control methods for parallel B-tree structures, which are used in parallel
databases and distributed storage systems. On the other hand, data migration is eﬃcient to handle the access skew
in these systems. Migrating data managed by parallel B-tree structures requires an eﬃcient concurrency control
for data migration. In this paper, we apply our methods to data migration. To compare the performance of our
methods and MARK-OPT, we implemented them on an autonomous-disk system adopting the Fat-Btree, a parallel
B-tree structure. The experiments on environments with data migration indicate that our methods always improves
the system throughput, and are also eﬀective as concurrency controls for data migration.
Key words Concurrency Control, Access Path, Parallel · Distributed DB, Parallel B-tree, Data Migration

1. は じ め に

上で並列に実行されることが望ましい．アクセス集中による負荷の偏りが存在する場合，負荷が大きい PE がボトルネックとデータベース用無共有並列計算機における検索，更新処理は，なり，全体の処理性能が低下してしまう．したがって，各 PE参照されるデータが配置されている各 PE（Processing Element）

で負荷を均等化することは処理性能の向上につながり，そのためのデータ分配方式が重要になる [1], [2]．

マイグレーション時の並行性制御として，MARK-OPT，LCFB

従来のデータ分配方式にはハッシュ分配方式や値域分配方

および LCFB-link を実装し，データマイグレーションを発生さ式 [3] などがあるが，ハッシュ分配方式では領域指定された問せた環境での実験から，LCFB 及び LCFB-link のデータマイグ

い合わせや，連続したアクセスの I/O 回数を削減するクラスタ

レーション時の並行性制御としての効果を示す．

化に対応できないという欠点がある．一方，値域分配方式では，以下に本稿の構成を述べる．まず 2 節で Fat-Btree とデータ静的決定された分割境界に沿って分割するため，データ更新にマイグレーションについて述べる．次に 3 節で従来の並行性制

よってデータ配置の偏りが生じたときに均一化するコストが非御方式と我々の提案する並行性制御について述べる．4 節では，常に大きくなる欠点がある．

それらのデータマイグレーション時の並行性制御への適用につデータ分配方式として値域分配方式を採用した上で，インいて述べる．5 節では提案手法と従来手法の実験による評価にデックス構造に並列 B-tree を用いる研究がある．並列 B-tree をついて述べる．最後に 6 節でまとめと今後の課題を述べる．

利用することによって，両方式の欠点が解消でき，同時に高速アクセスが可能になる．しかし，従来の並列 B-tree ではディレ

2. Fat-Btree とデータマイグレーション

クトリ更新によるスループットの低下や，少数の PE へのアク2. 1 Fat-Btree 構造

セスの集中といった問題が生じる．これらの問題を解決するた

Fat-Btree [4] は，B+ -tree 全体をページ単位で PE 間に分配す

めに，新しい並列 B-tree 構造として Fat-Btree が提案されている並列 B-tree の一種であり，データページである B-tree の葉る [4]．ディレクトリ構成として Fat-Btree を用いることで，他ページを各 PE に均等に分配する．ディレクトリ部分であるの並列 B-tree を用いるより高速なアクセスが可能であることがB-tree の葉ページ以外は，各 PE に配置されている葉ページへ実験により明らかにされている．また，アクセス集中による負のアクセスパスを含むインデックスページにのみ再帰的に配置

荷の偏りが発生した場合には，その負荷偏りを除去する必要がする．これにより，各 PE のディスクに格納されるのは，B-tree

ある．データマイグレーションは並列データベースや分散ストのルートページから均等に分配された葉ページまでの部分木でレージシステムにおける負荷分散を行うための有効な技術であある（図 1）．

るが，Fat-Btree では葉ページ単位の移動により，効率的なデー
タマイグレーションを行うことができる．

Fat-Btree を含めた並列 B-tree に適した並行性制御方式として，INC-OPT 方式 [5] や MARK-OPT 方式 [6] が提案されている．しかし，INC-OPT や MARK-OPT は木の降下中にラッチ更新頻度が高い下位のインデックスページほどそのコピーを持つ PE が減少していくため，ディレクトリ更新時に同期が必要となる PE 数が少なくなり，PE 間の局所的な通信によって更新処理を行うことができる．
また，各 PE では格納している葉ページの探索に必要のない

カップリングを用いているため，Fat-Btree では，他の PE にリインデックスページを持たないため，各 PE でインデックスペー

クエストを移譲するとき，3 回のネットワークを介したメッセー

ジのキャッシュを行った場合にキャッシュのヒット率を高く保つ

ジ転送が必要となり，リクエスト移譲コストが大きい．

ことができる．高いキャッシュヒット率により，更新処理だけ[7] において，この問題を解決する新たな並行性制御方式が提案されている．本稿ではこの方式を LCFB 方式を呼ぶ．LCFB
方式はラッチカップリングを行わないことで，リクエスト移でなく，探索処理も従来の並列 B-tree 構造と比較して高速に行うことができる．

2. 2 データマイグレーション

譲時の通信コストを減らし，ラッチカップリングを行っている

データマイグレーションは，並列データベースやストレージ

MARK-OPT より優れた性能を得ることが可能である．ラッチ

システムにおいてアクセス偏り除去のための有効な手段である．

カップリング省略に伴い発生する問題を解決するために，イン分散配置された PE に対して，各データのアクセス負荷を考慮

デックスページへの境界値の設置，ページ削除の遅延などをしてデータ配置を決定し，データ移動によりデータ再配置を行行っている．

うことで，システムの性能を大きく低下させるアクセス集中を

B-link アルゴリズムと LCFB を組み合わせた並行性制御手法

回避することができる．

が提案されている [8]．本稿ではこの方式を LCFB-link 方式と呼2. 3 Fat-Btree のデータマイグレーション

ぶ．B-link は単一 B-tree 上で優れた並行性制御が実現できるこ

値域分配方式では，ある PE（移動元）から論理的に隣接するとが知られている．B-link は，サイドポインタにより隣のイン

左右の PE（移動先）にのみデータマイグレーションを行うこ

デックスノードへのリンクをもっている．サイドポインタがあとができ，インデックスに Fat-Btree を用いる場合，移動元 PE

ることにより，ラッチカップリングを用いず，単一ノードラッ

でインデックスが端である葉ページをそのまま，移動先 PE にチによる並行性制御を行うことができ，X ラッチの獲得回数お移すことで，データマイグレーションを行うことができる (図よび範囲を小さくすることが可能である．LCFB におけるラッ2)．この場合，実際にデータマイグレーションに関わる PE は，

チカップリングの省略により複数 PE 間に跨る木降下コストを隣接する 2PE だけで済むので，他の PE の処理を妨害すること

減らし，単一 PE において B-link を用いることにより X ラッチ

なくデータマイグレーションを実現できる．

の獲得回数を減らすことができる．

以下，ノードを移動するアルゴリズム [4] の概要を述べる．こ

本稿では，LCFB 及び LCFB-link をデータマイグレーションの葉ページの移動の際，移動先の PE がその葉ページの上位の時の並行性制御に適用する．また，自律ディスク上にデータ

インデックスページを持たない場合，移動対象となる葉ページ

root page

表 1 ラッチマトリクスMode
index page

PE1

PE2

PE3

IX

S

SIX

X

IX

leaf page

PE0

IS

IS

PE0

PE1

m ig ra te

S
PE2

PE3

SIX
X

図 1 Fat-Btree 構造

図 2 Fat-Btree におけるデータ移動の方法

からルートページまでのアクセスパス上のインデックスページ
を，移動先の PE が持っていないページ分は移動元の PE からコピーする．逆に葉ページの移動によって移動元の PE から移動した葉ページの上位のインデックスページからその PE 内のが明らかにされている．

3. 2 データマイグレーション時の並行性制御
データマイグレーションでは他の更新処理と同様に SMO 発
生範囲に X ラッチを獲得することが必要である．

下位のインデックスページのエントリーがなくなる場合，その挿入に関してはノードのエントリー制限を超えた場合に SMO

インデックスページを削除する．この操作でそれより上位のイが発生し，削除に関してはノードのエントリーが存在しなくなっンデックスページからローカルページのエントリーがなくなった場合に SMO が発生する．それに対し，データマイグレーショ

た場合，再帰的に上位のインデックスページを削除する．

ンは葉ページを移動するため，葉ページとその親のインデック

3. 並行性制御

スページでは必ず SMO が発生する．それより上位のページで

SMO が発生するのは，データマイグレーション先の PE でロー

木構造の一貫性を保証するために，B-tree に並行性制御は必

カルエントリーが発生して，必要になったインデックスページ

須である．通常，B-tree および他のアクセスパスには，ロックのが作成される場合，または，データマイグレーション元の PE

代わりにデッドロック検出機構を持たない高速かつ単純なラッのインデックスページでローカルエントリーがなくなり，不要チが用いられる．ラッチはセマフォの一種である．従って，アになったインデックスページが削除される場合である．

クセスパスの並行性制御はデッドロックフリーでなければならない．

このように，挿入及び削除に関しては，X ラッチ獲得範囲を判断する条件が 1 つのみであるのに対し，データマイグレー

本稿では，5 種類のモードを持つラッチを仮定する．各モーションに関しては，2 つの条件が存在する．それぞれの条件は

ドは IS，IX，S，SIX，X であり，これらのモードの適合性は表独立であるため，MARK-OPT をデータマイグレーション時の1 に示される [9]．表中の “ ” は同時に複数のラッチが獲得可並行性制御に適用する場合，マーキングも 2 種類用いる必要

能なモードである．あるインデックスページの複製が複数の PEがある．2 種類のマーキングを更新しながら木を降下し，リスに存在する場合を考える．もしラッチ処理が各 PE で分散してタート時には SMO 発生範囲が広い条件に合わせるために小さ行われるならば，表 1 より，IS および IX モードはローカル PE

いほうの値を用いる．

のみで獲得するだけでよい．しかし，S，SIX および X モード

3. 3 LCFB 方式

は，コピーを持つすべての PE でラッチを獲得する必要がある．

LCFB 方式 [7] は，Fat-Btree 向けの並行性制御方式として提3. 1 従来の並列 B-tree 並行性制御方式

案されている MARK-OPT の Fat-Btree 上での性能を改善する

Fat-Btree を含めた並列 B-tree に適した並行性制御方式とし並行性制御方式である．

て INC-OPT 方式 [5] が提案されている．しかし，INC-OPT は，

MARK-OPT では，目的の葉ページまでの経路においてラッSMO（Structure Modiﬁcation Operation）発生時にルートページ

チカップリングが用いられる．そのため，Fat-Btree における PE

からの木の再降下であるリスタートを繰り返しながらラッチ範

間でリクエスト移譲が発生するとき，一回のリクエスト移譲ご囲を順次広げていくという手順をとるため，リスタートが多数とに，逐次的なネットワーク通信が三回必要となる．それに対必要になり，システム処理性能の低下をもたらす．

し提案手法は，MARK-OPT で用いられているラッチカップリ

この問題を解決する並行性制御方式として，MARK-OPT 方ングを行わないことにより，リクエスト移譲時のネットワーク

式 [6] が提案されている．MARK-OPT は，SMO が発生する木

通信を一回に抑えることができるので，ネットワークを介したの高さをマークすることにより，広範囲に SMO が発生すると通信回数を削減することが可能である．よって，ネットワーク

きでも，ほとんどの場合 1 回のリスタートで更新フェーズに移を介した通信回数を削減することによるレスポンスタイム向上

ることができる．よって，リスタート回数を少なく抑えることが期待できる．

によるレスポンスタイムの向上と，中間の X ラッチ拡大フェー

LCFB のようにラッチカップリングを用いない場合，誤った場ズの除去による不必要な X ラッチの獲得の減少から，高更新環所へのポインタに従う可能性がある．このとき，LCFB はルー

境において INC-OPT より高いスループットを獲得できること

トページからリスタートする．また，経路誤りを検出するため

Key_h i g h

Key_n

Key_2

Key_1

(2, 1)(1, 1)(1, 2)…

図 3 Blink -tree のノード…

(1, 3 )…

(2, 5 )

(3 , 1)(2, 3 )
(3 , 3 )(2, 6 )…

(3 , 4 )…

…

図 4 Fat-Blink -treeに，ページ両端の境界値が設けられているインデックスページ
を用いる．このような境界値をもつ構造を用いることで，経路ない．これにより，ルートページから葉ページまでの経路内の誤りの有無を判別できる．また，削除ページへのアクセスといページのみ更新により，サイドポインタの一貫性保持が可能にう問題も発生するが，ドレイン手法 [10] と delete bit を組み合なる．

わせることで，この問題を解決している．スプリット時に発生

図 4 の構造を用いた場合，コピーページが存在するインデッ

するページの削除には，そのページを指すポインタがまだない

クスノードでは，サイドポインタのないページが存在する．し非削除ページのエントリーを，ローカルエントリーが無くなったがって，コピーページが存在するノードでは，B-link アルゴ

たページにコピーし，指すポインタがないページの方を削除す

リズムを用いることはできない．そこで，LCFB-link は，コピーることで，より効率的に処理を行っている．

ページが存在するノードの処理に他の手法を用いる．この手法

3. 4 Blink -tree
linkB

として，全 SMO に必要な X ラッチを獲得した後に更新を行う-tree [11], [12] では，各レベルの全ノードがリンクしている．各ノードは，同レベルの次ノードを指すこのサイドポイン
タとポインタに割り当てらたキー（high key）を保持している．

Blink -tree におけるポインタは，ページスプリットを 2 フェーズ
（分割と適切な親へのインデックスエントリーの挿入）で処理す
link

ることを可能にする．図 3 は B-tree のノードを示している．

LCFB を選択することで，コピーページが存在するインデック
スノードでも更新処理を行うことが可能である．

4. LCFB 方式のデータマイグレーション時の処理
4. 1 LCFB 方式
LCFB のデータマイグレーション時の並行性制御への適用は“high key” より大きい検索キーを持ったプロセスは，右リンク容易である．不要になったページの削除以外は，LCFB の更新を用いて適切なページを獲得する．このような木を横へ辿る操処理とデータマイグレーション時の MARK-OPT の処理を組み

作はリンクチェイスと呼ばれる．また，B-link 方式では，検索，合わせるだけである．

更新プロセスともに，葉ノードまでの過程でラッチカップリン

LCFB のデータマイグレーション時のプロトコルは，ラッチ

グを用いない．また，SMO を実行するとき，各ページで X ラッの獲得及び解放に関しては他の更新処理と同様である．ただし，チを獲得するが，ラッチカップリングは用いない．B-link アルマーキングに関しては MARK-OPT 同様に 2 種類のマーキング

ゴリズムでは，同時に 1 つのラッチしか獲得されない．

が必要となる．また，LCFB のデータマイグレーションにおい3. 5 LCFB-link 方式て，必要なページが作成されることに関しては，特に問題は発LCFB-link 方式 [8] は，単一 B-tree 上で優れた並行性制御を生しない．ラッチカップリングを行っていないために作成され実現できる B-link を Fat-Btree に適用し，Fat-Btree 向けの並行たばかりのそのページにアクセスできなくても，コピーページ

性制御方式である．

が存在すれば，そのページを経由して目的の葉ページに辿り着

LCFB では，ラッチカップリングを省略することにより木のくことができるためである．このとき，そのページにアクセス

降下コストを削減し，高速な検索を可能にした．しかし，更新できなかったために，リクエスト移譲の回数が増える可能性が処理では SMO に関連する全ノードに X ラッチを獲得する必要あるが，非常に稀であるため，大きな影響はないと考える．そがある．そのため，更新処理時のコストは依然大きい．X ラッ

れに対し，不必要なページの削除に関しては，LCFB ではラッチの獲得回数や範囲が小さく，更新コストが小さい手法としチカップリングを行っていないため，削除したページへのアクて，B-link アルゴリズムが知られているが，並列 B-tree 全体でセスが発生する可能性がある．そのため，LCFB のページ削除

B-link アルゴリズムを用いることは難しい．LCFB-link では，時に用いられるドレイン手法と delete bit を組み合わせた手法

LCFB と組み合わせることにより，更新コストの小さい B-linkを用いる．これにより，データマイグレーションを行ったときを並列 B-tree で利用することを可能にする．これにより，並列にも，目的の葉ページへの正しい経路を保証する．

B-tree において，ラッチカップリング省略による効率的な検索4. 2 LCFB-link 方式

だけでなく，ラッチ獲得数及び範囲を小さくすることによる効

LCFB-link 方式を用いてデータマイグレーションを行おうと率的な更新が可能になる．

すると，同じ PE 内のページのみをサイドポインタでリンクし

LCFB-link では，同じ PE 内のページ間はサイドポインタでている構造では，B-link の特徴であるサイドポインタの一貫性リンクさせ，異なる PE のページ間はサイドポインタを用いなを保持するためのコストが非常に高い．LCFB-link 方式を用いい（図 4）．スプリット時に削除されない同じ PE 内の (1, 2) かて効率的なデータマイグレーションを行うためには，この問題

ら (1, 3) のみをリンクさせ，(1, 2) から異なる PE の (2, 3)，(3,を解決しなければならない．

3) をリンクさせないことで，(1, 3)，(2, 3)，(3, 3) のスプリット

4. 2. 1 マイグレーション時のサイドポインタの更新時には (3, 3) が削除されるが，サイドポインタの削除は発生しB-link を用いている場合のデータマイグレーションにおいて

図 5 右 PE へのマイグレーションにおけるインデックスページの削除

図6

右 PE へのマイグレーションにおけるインデックスページの作成

図 7 左 PE へのマイグレーションにおけるインデックスページの作成

dummy

は，必要になったページの作成および不必要になったページの削除におけるサイドポインタの更新が問題になる．B-link のサ

dummy

イドポインタは単方向リンクであるため，論理的に右の PE へのマイグレーションか左の PE へのマイグレーションかによっ

dummyて，異なる問題が発生する．

図 8 ダミーページを備えた Fat-Blink -tree

まず，右 PE へのマイグレーションについて述べる．右 PE
へのマイグレーションでは，不必要になったページを削除する
場合は，図 5 のように，図中の破線で囲われた左ページからのサイドポインタが存在するため，そのポインタを削除しなければならない．しかし，この左のページは，ルートページから葉ページまでの経路上になく，左隣にあるページはサイドポイン
タによっても辿れないため，このページを更新するためのコストは非常に高い．
この問題を解決するために，各 PE の各レベルの最右ページの右隣にダミーページを設ける．マイグレーションによって最右ページが削除される場合には，このダミーページを削除し，本来削除されるべきページは削除せず，削除されるダミーペー
ジの代わりにダミーページに設定する．これにより，経路外のページの更新は発生せず，効率的にサイドポインタの更新を行うことが可能になる．ダミーページであるか否かは，1 である
ときにダミーページであることを示すビット（dummy bit）によって区別される．ダミーページは，dummy bit が 1 にセットされている以外は，通常のページと同様である．そして，マイグレーションによって，各ページはダミーページになったり通常のページになったりする．
また，右 PE へのマイグレーションにおいて必要になったページを作成するとき，図 6 のように，図中の破線で囲われた作成
されたページから右のページへのサイドポインタを作成する必要がある．しかし，この右ページへのポインタ情報は，親ページから得られる場合もあるが，最悪の場合はルートページから再び辿らないと得られないため，ポインタを作成するコストが非常に高い．
この問題を解決するために，論理的に隣り合う PE 間で左 PEの最右ページから右 PE の最左ページへのサイドポイントをリンクさせる．先の問題を解決するためにダミーページを設けているため，最右ページであるダミーページからのサイドポイン
タとなる．このポインタにより，上位ページからの再降下を行うことなく更新を行うことができる．また，PE 間をポインタでリンクさせたことにより，ポインタの変更が問題になる．この変更は，左 PE へのマイグレーション時に，ポインタでリンクしていた移動元の PE でインデックスページが削除される場
合にのみ発生する．このとき，削除されるページの右ページへのポインタに変更する必要がある．また，そのような場合には，変更されるポインタのあるダミーページの両隣のインデックス
ページに X ラッチが獲得されるので，ダミーページの更新も容易である．
続いて，左 PE へのマイグレーションについて述べる．左のPE へのマイグレーションでは，必要なページを作成するとき，
図 7 のように，図中の破線で囲われた作成されたページに左のページからサイドポインタを作成する必要がある．しかし，この左のページは，ルートページから葉ページまでの経路上になく，左隣にあるページはサイドポインタによっても辿れないため，このページを更新するためのコストは非常に高い．
この問題を解決するために，論理的に隣り合う PE 間で左 PEの最右ページから右 PE の最左ページへのサイドポイントをリンクさせる．一つ目の問題を解決するためにダミーページを設けているため，最右ページであるダミーページへのサイドポイ
ンタとなる．このポインタを辿ることにより更新を行えるため，他の経路を辿る必要がなくなる．
上記の解決方法をすべて適用した場合の B-link を備えた Fat-

Btree の構造は図 8 のようになる．破線枠のページがダミーペー
ジである．この図からもわかるように PE 間に双方向リンクが存在する．このリンクはマイグレーションのためだけに使用されるのだが，上記の解決方法では，双方向リンクの両側のページにそれぞれの方向から X ラッチを獲得する．そのため，デッドロックが発生する可能性がある．デッドロックを回避するため，左右どちらかの PE にラッチ獲得順序の権利を表すラッチを設ける．これにより，マイグレーションの効率が悪くなることが考えられるが，ある PE 間のマイグレーションが左右双方向同時に発生すること自体が問題である．基本的にはそのような命令は発生せず，このラッチによる待ちはないと考える．

00

a b

10

00

10

00

00

00

00

cd

10

00

a b

00

e f

10

00

10

00

10

(1 )
(2 )

a b

00

00

cd

00

e f

10

00

10

00

10

00

00

00

cd

e f

10

00

00

表 2 実験システムの構成#Nodes:128 (Storages), 16 (Clients)

CPU:

AMD Athlon XP-M 1800+ (1.53 GHz)

Memory:PC2100 DDR SDRAM 1 GB

Network

1000BASE-T

HDD:

TOSHIBA MK3019GAX (30 GB, 5400 rpm, 2.5 inch)

OS:Linux 2.4.20

Java VM: Sun J2SE SDK 1.5.0 03 Server VM

(3 )

00

00

11

00

11

図9

00

a b

00

10

00

10

00

00

cd

11

00

e f

表3

00

実験システムのパラメータ

Page size:

4 KB

Tuple size:

350 B

Max No. of entries in an index node (fanout): 64

左の PE から右の PE へのマイグレーション

Max No. of tuples in a leaf node:
00

10

00

00

10

00

00

c d

00

e f

00

c d

00

01
10

e f

00

10

00

ab

c d

01
10

e f

00

うに適切にサイドポインタを更新する．
（ 3 ） その親ページにはコピーページが存在するため，リス
タートし，ルートページから再降下する．親ページとそのコピーに X ラッチを獲得した後，それらのページを更新し，

00

(3 )

00

00

8

00

10

00

(2 )

00

10

00

(1 )

00

10

00

ab

00

10

ab

00

00

10

00

00

ab

00

c d

00

00

00

10

01
10

e f

00

ラッチを解放する．
図 10 の左 PE へのマイグレーションの例を説明する．左 PE
へのマイグレーションでは，移動元 PE の左端の葉ページまで木を降下した後，以下の処理を行う．箇条書き番号は図中の遷移番号に対応する．

図 10

右の PE から左の PE へのマイグレーション（ 1 ） 移動先 PE のダミー葉ページと移動元 PE の左端の葉

4. 2. 2 ダミーページを用いたマイグレーション
上記で説明した解決方法を用いた場合のデータマイグレー
ションの処理を図 9, 10 の例を用いて示す．図 9, 10 における各ページの右肩の 2 つの数字は，左は dummy bit，右は delete bitを示す．また，破線枠のページはダミーページであり，鎖線で囲われたページ同士はコピー関係にある．
図 9 の右 PE へのマイグレーションの例を説明する．右 PE へのマイグレーションでは，移動元 PE の右端の葉ページまで木を降下した後，以下の処理を行う．箇条書き番号は図中の遷移番号に対応する．
（ 1 ） 移動元 PE の右端の葉ページとその右隣のダミー葉ペー
ジに X ラッチを獲得する．そして，葉ページのコピーを移ページに X ラッチを獲得する．そして，移動元 PE の葉ペー
ジのエントリーを移動先 PE のダミーページにコピーし，移動先 PE に新しいダミーページを作成し，元のダミーペー
ジのダミーページの dummy bit を 0 にセットする．そして，右上の図になるように適切にサイドポインタを更新する．
（ 2 ） 親ページとそのリンク先のダミーページに X ラッチを獲得した後，新たに作成した葉ページへのポインタを格納するインデックスページが移動先 PE に存在しないため，葉
ページのときと同様にダミーページにエントリーをコピー
し，新たにダミーページを作成する．そして，左下の図になるようにサイドポインタを更新する．
（ 3 ） その親ページにはコピーページが存在するため，リスタートした後，親ページとそのコピーを更新する．

動先 PE に作成する．作成したページの左右へのポインタを作成するとともに，移動先 PE の左端だった葉ページに X
ラッチを獲得し，左方向へのポインタを削除し，このページのラッチを解放する．その後，移動元の PE において，ダミー葉ページの delete bit を 1 にセットし，もとの葉ページの dummy bit を 1 にセットし，これらのページのラッチを解放する．
（ 2 ） 親ページとその右隣のダミーインデックスページに X
ラッチを獲得した後，新たに作成した葉ページへのポイン
タを格納するインデックスページが移動先 PE に存在しない
ため，このインデックスページのコピーを移動先 PE に作成する．そして，葉ページのときと同様，左下の図になるよ

5. 実

験

提案手法の有効性を示すために，Fat-Btree を採用している自律ディスク [13] に提案手法を実装し実験を行った．自律ディス
クは Linux クラスタ上に Java を用いて模擬実装されている．今回の実験では表 2 に示す構成の PC と十分なバックボーン性能を持つ 192 ポートのネットワークスイッチを用いて，実験環境を構成した．ストレージノードおよびクライアントは，1 つの同じスイッチに接続したスタートポロジとした．今回の実験における Fat-Btree の構成パラメータを表 3 に示す．
自律ディスク 1 台あたり 5120 タプルの初期 Fat-Btree を構築
した後，各クライアント PC（1 台あたり並行して 64 スレッド）

M A R K -O P T
I N C -O P T

A R IE S / IM20000
1 5 000
1 0000
5 000
0

0

2

4

8

N u m b e r o f S im u lta n e o u s P r o c e s s e s M ig r a tin g

1 6

データマイグレーションの頻度を変化させたときの比較
0. 4

I N C -O P T
M A R K -O P T
L C F BL C F B -l i n k

0. 3 5
0. 3

T h r o u g h p u t in M ig r a tio n s p e r S e c o n d

T h r o u g h p u t in O p e r a t io n s p e r S e c o n d

L C F B -l i n k
L C F B

25 000C o llis io n R a tio
in L a t c h C o llis io n s p e r O p e r a t io n s

図 113 00001 000

L C F B -l i n k
L C F BM A R K -O P T
I N C -O P T
A R IE S / IM

9 00
800
7 00
6 00
5 00
400
3 00
200
1 00
0

0

2

4

8

N u m b e r o f S im u lta n e o u s P r o c e s s e s M ig r a tin g

1 6

図 13 データマイグレーション処理性能の比較

れは，図 12 からも分かるように，MARK-OPT が X ラッチ獲得を削減し，ラッチ衝突が減少したためである．その MARK-OPT

0. 25と比べて，LCFB は常に高いスループットが得られている．マ

0. 2

イグレーションではリクエスト移譲は発生しないため，マイグ

0. 1 5

レーションのコストは基本的に同じである．よって，この結果

0. 1

は検索および更新におけるリクエスト移譲コストを削減してい

0. 05
0

るためである．また，図 12 からも分かるようにラッチ衝突率
0

2

4

8

N u m b e r o f S im u lta n e o u s P r o c e s s e s M ig r a tin g

1 6

も下がっており，LCFB はトランザクション自身のリクエスト
移譲コストを削減するとともに，他のトランザクションの待ち回数も減らしている．

図 12

ラッチ衝突比率の比較

LCFB-link は LCFB と比べてさらに高いスループットを得られている．これは，B-link による挿入処理の効率化が大きく影から同時にリクエストを送信した．キーはランダムに選び，ランダムに選択した PE（自律ディスク）に対して，検索と挿入操
作（挿入比率 40%）を実行したときのスループットから性能を評価した．また，20 ミリ秒に 1 回ずつ移動元 PE に一方向への
データマイグレーションのリクエストを送信した．100 回リク
エストを送信したら，先ほど移動先であった PE から逆方向へのデータマイグレーションのリクエストを送信した．リクエス
トを送る PE は，データマイグレーションの並列数に合わせて等間隔に PE を選んだ．
以下に本実験の概要を述べる．まず，データマイグレーショ
ンの頻度を変化させたときのスループットの測定し，各手法の比較を行う．また，ラッチ衝突回数の測定も行う．次に，デー
タマイグレーションを一定間隔ではなく，前リクエストのレス
ポンス後に次のマイグレーションをリクエストすることで，マ
イグレーションの処理性能の比較を行う．最後に，自律ディス
クの台数を変化させたときの各手法のスループットを測定する．

5. 1 データマイグレーションの頻度を変化させたときの比較
クライアント PC からリクエストを送信し，10 秒間操作したときのスループットを測定した．図 11 は，自律ディスクの台数を 32，横軸としてデータマイグレーションの同時リクエスト
数を 0 から 16 に変化させ，スループットを縦軸として比較したグラフである．また，図 12 は，1 命令あたりのラッチ衝突数
を縦軸として比較したグラフである．

ARIES/IM におけるマイグレーションでは常に木ラッチが獲得されるため，常にスループットが低い．また，INC-OPT と比べて，MARK-OPT は常に高いスループットが得られている．こ響している．また，マイグレーション頻度が大きい場合には，低いときに比べて高い改善が見られる．これは図 12 からも分かるように，マイグレーション頻度上昇によるラッチ衝突率の上昇を抑えているためである．LCFB は，葉ページのコピー等の更新時にも SMO の範囲全体に X ラッチを獲得する．それに対し，LCFB-link は 4. 2. 2 節の例からもわかるように，葉ページの更新時にインデックスページにラッチを獲得しない．よって，LCFB-link ではマイグレーション時のラッチ衝突が減少す
る．ただし，挿入操作頻度の増加に比べて，データマイグレー
ション頻度の増加による LCFB に対する LCFB-link のスルー
プットの改善は小さい．これは，データマイグレーションは複数の PE に跨る SMO が必ず発生し，LCFB-link は LCFB を用いた処理が必ず発生するためである．

5. 2 データマイグレーション処理性能の比較
クライアント PC からリクエストを送信し，10 秒間操作したときのスループットを測定した．本節では，20 ミリ秒間隔ではなく，前のリクエストのレスポンスが返ってきたら，次のマイグレーションをリクエストした．図 13 は，自律ディスクの台数を 32，横軸としてデータマイグレーションの同時リクエスト
数を 0 から 16 に変化させ，1 秒あたりのデータマイグレーショ
ンリクエスト数を縦軸として比較したグラフである．

MARK-OPT と LCFB のマイグレーションの処理性能はほぼ同じである．これは，この 2 手法の処理の大きな違いがラッチ
カップリングの有無だけで，リクエスト移譲の起きないマイグ
レーションではその違いは処理時間に影響を及ぼさないためでT h r o u g h p u t in O p e r a t io n s p e r S e c o n d

7 0000ンを発生させたが，本来は負荷値により負荷偏りを検出し，そL C F B -l i n k
L C F BM A R K -O P T
I N C -O P T
A R IE S / IM

6 00005 000040000

れに基づいたデータマイグレーションを行うべきである．実験に用いた自律ディスクには，それらの操作を自律的に行う機能を備えており，アクセス偏りのある環境で，その機能を用いて3 0000実験を行う必要がある．

2 0000

また，MARK-OPT と同様に INC-OPT 方式の拡張である PO-P

1 0000

方式 [14] との比較を検討している．PO-P 方式は，INC-OPT と0

PO [15] というトップダウン手法を組み合わせた並列 B-tree に
4

8

1 6

3 2

N u m b e r o f P E

6 4

1 2 8

適した楽観的な並行性制御方式である．

謝
図 14

辞

自律ディスクの台数を変化させたときの比較

本研究の一部は，独立行政法人科学技術振興機構戦略的創造ある．それに対し，LCFB-link は，マイグレーション同時リク研究推進事業 CREST，情報ストレージ研究推進機構 (SRC)，文

エスト数が 16 のときに LCFB の約 95%の処理性能である等，部科学省科学研究費補助金特定領域研究 (18049026) および東他の 2 手法と比べてわずかであるがマイグレーションの処理

京工業大学 21 世紀 COE プログラム「大規模知識資源の体系化

性能が低い．これは，サイドポインタの一貫性を保持するためと活用基盤構築」の助成により行なわれた．

に，マイグレーションにおいて更新の必要なページ数が増えているためである．ただし，性能低下は無視できる範囲であり，

INC-OPT および ARIES/IM よりは高い処理性能が得られている．それに対し，前節の結果の通り，検索，挿入に関しては，

LCFB-link が最も高いスループットが得られている．
5. 3 自律ディスクの台数を変化させたときの比較
クライアント PC からリクエストを送信し，10 秒間操作したときのスループットを測定した．また，データマイグレーショ
ンの同時リクエスト数は自律ディスクの台数の 4 分の 1 にした．
図 14 は，横軸として自律ディスクの台数を 4 から 128 に変化
させ，LCFB-link，LCFB，MARK-OPT を，スループットを縦軸として比較したグラフである．

LCFB や LCFB-link は，ARIES/IM，INC-OPT および MARKOPT と比べて，台数増加に伴うスループット上昇が大きい．これは，LCFB や LCFB-link はリクエスト移譲のコストが低いからであり，データマイグレーションがある場合においても，その効果が大きいことを示している．したがって，LCFB と

LCFB-link はデータマイグレーションの発生する環境においても，ARIES/IM，INC-OPT および MARK-OPT より高い拡張性があることがわかる．

6. まとめと今後の課題
本稿では，我々の提案してきた並列 B-tree 向け並行性制御手法のデータマイグレーションへの適用方法を示した．delete bit
やダミーページを用いることで，通常の B-tree に対する命令だけでなくデータマイグレーションも処理可能になった．さらに，自律ディスクにおいるデータマイグレーションの発生する環境での実験により，従来手法との比較を行った．データマイ
グレーションの処理性能に関しては，LCFB と MARK-OPT はほぼ等しく，LCFB-link はやや低いが，無視できる程度であった．それに対し，検索，挿入に関しては，LCFB-link が最も高いシステムスループットが得られた．
本稿では，アクセス偏りのない環境で，クライアントからランダムにリクエストを送信することで，データマイグレーショ

文献[1] George Copeland, William Alexander, Ellen Boughter, and Tom
Keller. Data Placement in Bubba. In Proc. of SIGMOD Conference ’88, pp. 99–108, 1988.
[2] Shahram Ghandeharizadeh and David J. DeWitt. Hybrid-Range Partitioning Strategy: A New Declustering Strategy for Multiprocessor
Database Machines. In Proc. of VLDB ’90, pp. 481–492, 1990.
[3] David J. DeWitt and Jim Gray. Parallel Database Systems: The Future of High Performance Database Systems. Communications of theACM, Vol. 35, No. 6, pp. 85–98, 1992.
[4] Haruo Yokota, Yasuhiko Kanemasa, and Jun Miyazaki. Fat-Btree:
An Update-Conscious Parallel Directory Structure. In Proc. of
ICDE ’99, pp. 448–457, 1999.
[5] Jun Miyazaki and Haruo Yokota. Concurrency Control and Performance Evaluation of Parallel B-tree Structures. IEICE Transactions
on Information and Systems, Vol. E85-D, No. 8, pp. 1269–1283,
2002.
[6] 吉原朋宏, 小林大, 田口亮, 上原年博, 横田治夫. 並列ディレクトリ
構造 Fat-Btree の並行性制御の改善とその評価. DEWS2005 論文
集，2A-o4, 2005.
[7] 吉原朋宏, 小林大, 田口亮, 横田治夫. 並列 Btree 構造 Fat-Btree
におけるリクエスト委譲コストを削減する並行性制御手法.
DEWS2006 論文集，7C-o3, 2006.
[8] 吉原朋宏, 小林大, 田口亮, 横田治夫. Fat-Btree における B-link
を用いた並行性制御手法. 情処研報 DBS-140-90, 情報処理学会,
2006.
[9] Jim Gray and Andreas Reuter. Transaction Processing: Concepts
and Techniques. Morgan Kaufmann, San Francisco, California,
USA, 1992.
[10] H. T. Kung and Philip L. Lehman. Concurrent Manipulation of Binary Search Trees. ACM Transactions on Database Systems, Vol. 5,
No. 3, pp. 354–382, 1980.
[11] Philip L. Lehman and S. Bing Yao. Eﬃcient Locking for Concurrent Operations on B-trees. ACM Transactions on Database Systems,
Vol. 6, No. 4, pp. 650–670, 1981.
[12] Vladimir Lanin and Dennis Shasha. A Symmetric Concurrent B-tree
Algorithm. In Proc. of FJCC ’86, pp. 380–389, 1986.
[13] Haruo Yokota. Autonomous Disks for Advanced Database Applications. In Proc. of DANTE ’99, pp. 435–442, 1999.
[14] Damdinsuren Amarmend, Masayoshi Aritsugi, and Yoshinari
Kanamori. PO-P: A Concurrency Control Protocol for Parallel Btrees. IPSJ Transactions on Databases, Vol. 45, No. SIG14, pp. 30–
38, 2004.
[15] Y. Mond and Yoav Raz. Concurrency Control in B+-Trees Databases
Using Preparatory Operations. In Proc. of VLDB ’85, pp. 331–334,
1985.