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

並列Btree 構造 Fat-Btreeにおけるリクエスト委譲コストを削減する並行性制御手法

Title(English)

A Concurrency Control Method to Reduce the Cost of Request
Transfers on the Fat-Btree, Parallel Btree Structure

著者(和文)

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

Authors(English)

Tomohiro YOSHIHARA, Dai KOBAYASHI, Ryo Taguchi, Haruo
YOKOTA

掲載誌(和文)DEWS2006 論文集

Citation(English)

Proc. of DEWS2006

Vol, no, pages

Vol. , No. , pp. 7C-o3

発行日 / Pub. date

2006, 3

URL

http://search.ieice.org/

権利情報 / Copyright

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

Powered by T2R2 (Science Tokyo Research Repository)

DEWS2006 7C-o3

並列 Btree 構造 Fat-Btree におけるリクエスト委譲コストを削減する
並行性制御手法
吉原 朋宏†

小林

大†

田口

亮††

横田

治夫†††,†† 東京工業大学大学院情報理工学研究科計算工学専攻 〒 1528552 東京都目黒区大岡山 2121†† 日本放送協会放送技術研究所 〒 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
Fat-Btree に適した並行性制御手法として提案してきた MARK-OPT は，楽観的処理中にラッチカップリン

あらましグを行うため，Fat-Btree におけるリクエスト委譲時のコストが高い．本稿では，楽観的処理中にラッチカップリングを行わないことで，Fat-Btree において MARK-OPT より高い処理性能を得ることが可能な新手法を提案する．提案手法では，非ラッチカップリングに伴う経路誤りを検出するため，ページ両端に境界値を設けている．また，Fat-Btree
では，ページスプリット時にもページの削除が発生する可能性があるが，削除ページと非削除ページを交換すること
により，通常の削除より効率的な処理を行う．Fat-Btree を採用している自律ディスクに提案手法を実装し，様々な環
境における実験から，提案手法が常にシステムスループットを改善し ，大規模システムおよび高アクセス負荷環境において特に有効であることを示す．
キーワード

アクセスパス，並行制御とリカバリ，並列 · 分散 DB

A Concurrency Control Method to Reduce the Cost of Request Transferson the Fat-Btree, Parallel Btree 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†† Science and Technical Research Laboratories, Japan Broadcasting Corporation
11011 Kinuta, Setagaya-ku, Tokyo 1578510, Japan††† Global Scientic 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 As an effective concurrency control method for the Fat-Btree, the MARK-OPT method has been proposed. However, the latch-couplings in the method enlarge the costs of request transfers on the Fat-Btree. In thispaper, a new concurrency control method not latch-coupling during optimistic operations latch coupling is proposed
to improve the system performance. To detect access path errors in the proposed method, the index pages haveboundary values at both ends. In the Fat-Btree, a page split may cause a page deletion. Swap of deleted page andnon-deleted page in the method is more effective than normal page deletion. To compare the performance of the
proposed method and the MARK-OPT method, we implemented them on an autonomous-disk system adopting the
Fat-Btree. The experimental results on varied environments indicate that the proposed method always improves
the system throughput, and are especially effective for large scale configuration and high workloads.
Key words Access Path, Concurrency Control and Recovery, Parallel · Distributed DB

root page

1.

はじめに

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

なり，全体の処理性能が低下してし まう．したがって，各 PEで負荷を均等化することは処理性能の向上につながり，負荷を

PE0

PE1

PE2

図1

Fat-Btree 構造

PE3均等にするためのデータ分配方式が重要になる [1], [2]．
従来のデ ータ分配方式にはハッシュ分配方式や値域分配方
式 [3] などがあるが，ハッシュ分配方式では領域指定された問い合わせや，連続したアクセスの I/O 回数を削減するクラスタ化に対応できないという欠点がある．一方，値域分配方式では，プリングを用いているため，Fat-Btree では，他の PE にリクエ

静的決定された分割境界に沿って分割するため，データ更新にスト委譲が行われるとき，3 回のネットワークを介したメッセー

よってデータ配置の偏りが生じたときに均一化するコストが非ジ転送が必要となる．このように，分散環境でラッチカップリ

常に大きくなる欠点がある．

ングを用いることはコストが大きい．また，システム規模が大

データ分配方式として値域分配方式を採用し た上で，インデックス構造に並列 Btree を用いる研究がある．並列 Btree を

きくなるに従い，リクエスト委譲の頻度は大きくなるため，規模拡大によるスループット向上が小さくなる．

利用することによって，両方式の欠点が解消でき，同時に高速

本稿では，MARK-OPT と比べて，リクエスト委譲時のメッアクセスが可能になる．しかし ，従来の並列 Btree ではデ ィレ

セージ転送回数の削減することが可能である Fat-Btree に適した

クトリ更新によるスループットの低下や，少数の PE へのアク並行性制御方式を提案する．また，自律デ ィスク上に MARK-

セスの集中といった問題が生じる．

OPT および 提案手法を実装し ，システム規模を変化させた場

これらの問題を解決するために，新しい並列 Btree 構造とし合，更新要求の割合を変化させた場合およびクライアントのスて Fat-Btree が提案されている [4]〜[8]．ディレクトリ構成とし

レッド 数を変化させた場合のスループットを測定し，提案手法て Fat-Btree を用いることで，単一キー問い合わせ，レンジ問の効果を示す．

い合わせが並列に高速実行できることが確率モデルの検証 [4]，以下に本稿の構成を述べる．まず 2. 節で Fat-Btree と従来のおよび nCUBE3 [6] や LAN 環境での PC クラスタ [7] 上への実並行性制御方式について述べる．次に 3. 節で提案する並行性制装による実験により明らかにされている．
Fat-Btree を含めた並列 Btree に適し た並行性制御方式として INC-OPT 方式が提案されている [9]．無共有並列計算機向けに設計されている INC-OPT は，従来の Btree の並行性制御方

御方式について述べる．4. 節では提案手法と従来手法の実験による評価について述べる．最後に 5. 節でまとめと今後の課題を述べる．
2.

Fat-Btree と並行性制御

ンスを示すことが明らかにされている [9]．しかし ，INC-OPT

2. 1

Fat-Btree 構造

は Btree の構造変化を起こす操作（ SMO: Structure Modication+
Fat-Btree [4]〜[8] は，B -tree 全体をページ単位で PE 間で分

Operation ）が広範囲で行われるとき，ルートページからの木の配する並列 Btree の一種であり，データページである Btree の再降下（ リスタート ）が多数必要となり，システム処理性能の葉ページを各 PE に均等に分配する．デ ィレクトリ部分である低下をもたらす．

Btree の葉ページ以外は，各 PE に配置されている葉ページへの式である B-OPT [10] や ARIES/IM [11] より優れたパフォーマ

そこで我々は，並列 Btree 構造の新たな並行性制御として，

アクセスパスを含むインデックスページにのみ再帰的に配置す

INC-OPT を 改良し た MARK-OPT 方式を 提案し てい る [12]．

る．これにより，各 PE のディスクに格納されるのは，Btree のMARK-OPT は，楽観的なラッチカップ リング 中に SMO が発

ルートページから均等に分配された葉ページまでの部分木であ生するポイントのマーキングを行う．これにより，従来の INC-る（ 図 1 ）．

OPT と比較して，SMO 発生時のリスタート回数を少なく抑え，更新頻度が高い下位のインデックスページほどそのコピーを

SMO のための排他ラッチ獲得時間を短縮することができる．分持つ PE が減少していくため，デ ィレクトリ更新時に同期が必散ディレクトリ構造として並列 Btree である Fat-Btree を用いて要となる PE 数が少なくなり，PE 間の局所的な通信によって更いる自律デ ィスク [13]〜[15] 上での実験から，MARK-OPT が新処理を行うことができる．

並列 Btree 上において優れた性能を示すことが明らかにされてまた，各 PE では格納している葉ページの探索に必要のないいる [12]．また，データマイグレーションは，アクセス偏り除インデックスページを持たないため，各 PE でインデックスペー

去のための有効な手段であるが，MARK-OPT がデータマイグ

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

レーションの並行性制御としても有効であることも明らかにさことができる．高いキャッシュヒット率により，更新処理だけれている [16]．しかし，MARK-OPT は木の降下中にラッチカッでなく，探索処理も従来の並列 Btree 構造と比較して高速に行

表 1 ラッチマトリクス
Mode

IS

IX

S

SIX

件 2.1 を満たしていない．B-OPT は（２）を，OPT-DLOCK は
X

IS（ １ ）を満たさず，ARIES/IM は（ ３）を満たさない．よって，これらは Fat-Btree に適さない．

IX

上記の条件を満たす並行性制御方式として INC-OPT 方式がS提案されている [9]．Fat-Btree を含めた並列 Btree に適した並SIX

行性制御方式として設計されている INC-OPT 方式は，従来のX

Btree の並行性制御方式である B-OPT [10] や ARIES/IM [11] より優れたパフォーマンスを示すことが明らかにされている [9]．

うことができる．
2. 2

しかし ，INC-OPT は，SMO 発生時にリスタートを繰り返し

リクエスト 委譲

Fat-Btree では，検索処理を実行する PE 上にデ ィレクトリが一部しか存在しない．もし，必要なローカルインデックスペー
ジがその PE 上に存在しない場合は，そのインデックスページを格納している PE にリクエストを委譲するのだが，そのためには，他 PE のリモートページへのポインタを保持する必要がある．また，リクエスト委譲時，各 PE 同士はネットワークによって接続されているため，ネットワークを介したメッセージ

このことは更新命令のレスポンスタイムを増加させるとともに，上位ページで複数回 X ラッチを獲得することで，システム全体のスループットも低下させる．
2. 4

MARK-OPT 方式

向けとして我々が提案した並行性制御手法である．従来の INC-

並行性制御

木構造の一貫性を保証するために，Btree に並行性制御は必須である．通常，Btree および他のアクセスパスには，ロックの代わりにデッド ロック検出機構を持たない高速かつ単純なラッチが用いられる．ラッチはセマフォの一種である．従って，ア
クセスパスの並行性制御はデッド ロックフリーでなければなら

OPT は，広範囲に SMO が発生するとき，X ラッチ拡大のために複数回のリスタートが必要だった．それに対し MARK-OPT
は，SMO が発生する木の高さをマークすることにより，広範囲に SMO が発生するときでも，ほとんどの場合 1 回のリスター
トで更新フェーズに移ることができるので，リスタート回数を少なく抑えることが可能である．よって，リスタート回数を少ない．
2. 3. 1

スタートが複数回必要になることがある．ルートページまで更新が及ぶ場合には，木の高さと同じフェーズ数が必要となる．

MARK-OPT（ MARKing OPTimistic ）方式 [12] は，並列 Btree

転送が発生することになる．
2. 3

ながらラッチ範囲を順次広げていくという手順をとるため，リなく抑えることによるレ スポン スタイムの向上と，中間の X

ラッチモード

本稿では，5 種類のモード を持つラッチを仮定する．各モー
ドは IS，IX，S，SIX，X であり，これらのモード の適合性は表1 に示される [17]．表中の  は同時に複数のラッチが獲得可

能なモード である．IS，S モード のラッチは，検索処理に用いラッチ拡大フェーズの除去による不必要な X ラッチの獲得の減
少から，高更新環境において従来手法より高いスループットを得ることが期待できる．
MARK-OPT の検索時のプロトコルは，IS モード によるラッチカップリング（ 注 ）が使用される．まず，ルートページを IS モー
1

られ，S とは共有を意味する．IX，X モード のラッチは，更新処理に用いられ，X とは排他を意味する．SIX モード のラッチ
は，本稿では用いられない．
あるインデックスページの複製が複数の PE に存在する場合

ド でラッチした後，以下の処理を繰り返す．
（ 1 ） 親ページのキーを比較して，子ページのポインタを取得（ 2 ） 子ページの IS ラッチを取り，親ページのラッチを解放を考える．もしラッチ処理が各 PE で分散して行われるならば，
表 1 より，IS および IX モード はローカル PE のみで獲得するだけでよい．しかし ，S，SIX および X モード は，コピーを持
つすべての PE でラッチを獲得する必要がある．
2. 3. 2

Fat-Btree の並行性制御

Fat-Btree を含む並列 Btree の並行性制御は，一般に次の条件

葉ページまで辿り着けば，葉ページに S ラッチを獲得しデータを読む．
MARK-OPT での更新処理時のプロトコルは，次のように二つのフェーズで行われる．
第 1 フェーズ :IX ラッチカップ リングで葉ページまで辿るを満たすことが望まれる [9], [12]．

（ 葉ページは X ラッチが獲得される）．フルエントリー（ 次［ 条件 2.1 ］ 並列 Btree の並行性制御には以下の三点を満たすにエントリーが増えたときにスプリットする状態のこと）でことが要求される．

はないインデックスページが存在したら，そのページのルー
トページからの高さをマークする．マークする高さは，フル（ 1 ） デッド ロックフリーである（ 2 ） ルートおよび木の上位ページにできる限り S，SIX および X ラッチを獲得しない（ 3 ） 短時間であっても木全体をラッチすべきではない

エント リーではないページに遭遇するたびに逐次更新される．もし，SMO が起きないならば葉ページを更新して終了．
もし 葉ページがスプ リットを起こし SMO が起こるならば ，葉ページの X ラッチを解放し，第 2 フェーズに移行する．

優れ た Btree の並行性制御方式とし て ，B-OPT [10]，OPTDLOCK [18] および ARIES/IM [11] などがあるが，これらは条（ 注 1）： [17] においては，ラッチカップリングはクラビングと呼ばれている．

+ !"% $ !"%

     

 


 

 

















  



































&'( $#%!

 $     

   "!
&

 （ b ）スプリット後（ a ）スプリット前  

図3

インデックスページのスプリット  *)  !"#  $ !"#  $










図2










（ a ）ラッチカップリング使用時 （ b ）ラッチカップリング不使用時








































リクエスト委譲プロトコル
図 4 境界値のあるインデックスページのデータ構造

第 2 フェーズ : 第 1 フェーズと同様に木の高さのマークは行
う．前フェーズでマークした高さ以下のインデックスページ

経路誤りが発生する手法として B-link [19], [20] を用いた手と葉ページを X モード でラッチする．もし獲得した X ラッ

法や ARIES/IM [11] がある．B-link を用いた手法では，同時にチの範囲が SMO の範囲に対して十分でなければ ，同様にマークを用いて X ラッチの範囲を変化させていく．十分な
X ラッチが獲得されたならば更新操作を実行する．

1 つのページにしかラッチを獲得しないため，経路誤りが発生する．このとき，B-link という同じ高さの兄弟ページをつなぐ
ポインタによって正しい経路に復帰する．また，ARIES/IM は，
目的の葉ページまでの経路ではラッチカップ リングを行うが，この手続きの厳密な定義は [12] を参照されたい．
MARK-OPT はマークした前フェーズの状態をもとにラッチ

SMO 発生時に，更新のための X ラッチ獲得にはラッチカップ

リングを用いないため，経路誤りが発生する．このとき，LSN

範囲を決定している．そのため，前フェーズからの木構造の変（ Log Sequence Number ）の値が変更されていないページまで後化による SMO 範囲の拡大により，複数回リスタートが必要と退することで正しい経路に復帰する．これらの手法は，ボトムなる場合もあるが，INC-OPT 同様に最大フェーズ数は高々木のアップに SMO のための X ラッチを獲得し ，更新を行うため，

高さ H に抑えられる．短期間で SMO 範囲が拡大することは極トップダウンに行われる木の降下中に多くの経路誤りが発生す

めて稀であり，多くの場合は 1 回のリスタートで処理を完了でる．それに対し，提案手法はトップダウンに X ラッチを獲得す

きる．よって，上位ページまで SMO が及ぶときでも，INC-OPT

るため，それらの手法より経路誤りが発生する確率が低い（ 注 ）．

のように多くのリスタートを必要としない．
3.

提案手法

2

さらに，経路誤りが起こったときのレスポンスタイムの悪化も小さい．なぜなら，リスタート前のアクセスにより主記憶上にキャッシュされている確率が高いからである．また，リクエ

Fat-Btree 向けの並行性制御方式として提案されている MARKOPT の Fat-Btree 上での性能を改善する並行性制御方式を提案

する．

スト委譲の発生により，現 PE 上ではアクセスしていないページも存在するが，そのようなページはたいていアクセス頻度の高い木の上位ページであり，これも主記憶上にキャッシュされ

MARK-OPT では，目的の葉ページまで経路においてラッチている確率が高い．

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

図 3 のスプ リットにおいて，経路誤りが発生する例を示す．

間でのリクエスト委譲が発生するとき，一回のリクエスト委譲

スプリット前の図 3（ a ）において，検索キーが Key i であるごとに，図 2（ a ）のように逐次的なネットワーク通信が三回必プロセス a が存在したとする．プロセス a は，
（ I1 ）のラッチ獲要となる．それに対し 提案手法は，MARK-OPT で用いられて

得後，（ I1 ）から次のページが（ I2 ）であるという情報を得る．

いるラッチカップリングを行わないことにより，図 2（ b ）のよ

プロセス a はラッチカップリングを用いていないため，（ I2 ）の

うにリクエスト委譲時のネットワーク通信を一回に抑えることラッチを獲得する前に（ I1 ）のラッチを解放することになる．そができるので，ネットワークを介した通信回数を削減することのため，（ I2 ）のラッチを獲得する前に，他のプロセスによってが可能である．よって，ネットワークを介した通信回数を削減

図 3（ b ）のように更新される可能性がある．しかし，プロセスすることによるレスポンスタイム向上が期待できる．
しかし ，ラッチカップ リング以外の基本的な処理は MARKOPT と同じである．よって，条件 2.1 は満たしており，MARKOPT と同様に並列 Btree に適した並行性制御であるといえる．
3. 1

経路誤りの検出a は（ I2 ）のラッチを獲得し ，そのページを検索することにな

るが，検索キー Key i を含むキー範囲は，更新によって（ I3 ）に移っている．すなわち，プロセス a は正しい経路である（ I3 ）ではなく，誤った経路である（ I2 ）を辿っていることになる．
このような場合，提案手法では，プロセス a はルートページ

ラッチカップリングを用いない場合，誤った場所へのポイン
タに従う可能性がある．このとき，提案手法はルートページか（ 注 2）：経路誤りの確率は非常に低いため，正しい経路に復帰するための手続き

らリスタートを行う．

によって性能に差はでないと考えられる．節 4. 5 においてその値を示す．

1→からリスタートを行う．しかし ，図 3 のような通常の Btree の2

l := H;

Parent := null; Child := ROOT; h := 1; m := 1;

インデックスページのデータ構造では，経路誤りを検出できな

3

while h < l do begin

4

IX latch on Child;い．プロセス a の検索キー Key i は（ I2 ）のキー範囲外である

5が，そのことを（ I2 ）だけでは判別できないため，次のような

7The rst phase

問題が発生する．検索キーが Key i-1 より大きいときに経路誤り有と判断し，ルートページからのリスタートや上位ページに後退という手法をとると，検索キーが Key i-1 と Key i の間で

1011m := h;/* Marking */Determine NewChild;

Parent := Child; Child := NewChild; h := h + 1;
Unlatch Parent;

12

end;

13

X latch on Child and its copies;

14

17

if Access path error is detected thenRelease all granted latches; goto 2;
if Child is full thenRelease all granted latches; l := m;else begin

19

Update;

←

18
20

→

た場合，誤ったアクセスパスを辿ってしまう．

9

16に進めなくなる．一方，経路誤り無と判断し，その経路を辿り

Unlatch Child; goto 2;
if Child is not full then815

あるときのように正しい経路であった場合，そのページから先続けると，検索キーが Key i のときのように誤った経路であっ

if Access path error is detected then

6

22

21

Release all granted latches; operation completion;
end;

Parent := null; Child := ROOT; h := 1; m := 1;

23while h < l do begin

そこで，経路誤りを検出するために図 4 の構造のインデック

24

IX latch on Child;25

if Access path error is detected then

スページを用いる．このデータ構造には，通常のデータ構造に26は存在しないページ両端の境界値が設けられている．このよう28な境界値をもつ構造を用いることで，境界値を基にそのページ

30

27

The second phase29

だけで正確なキーレンジが判別できる．先ほどの例でも，検索キー Key i が境界値 Key i 以上であることを基に経路誤りであることを判別でき，上記のような問題は発生しない．
検

3. 2

索

Unlatch Parent;
X latch on Child and its copies;

34

if Access path error is detected then

36
37
38

42
43
44
45

←

Parent := Child; Child := NewChild; h := h + 1;

33
35

41

ド でラッチした後，以下の処理を繰り返す．

/* Marking */

end;

40

ラッチカップリングを用いない．まず，ルートページを IS モー

m := h;Determine NewChild;32

39

提案手法の検索処理時のプロトコルは MARK-OPT と異なり，（ 1 ） 経路誤り検出時，親ページのラッチを解放し ，ルート

31

Unlatch Child; goto 22;
if Child is not full thenRelease all granted latches; goto 22;
Determine NewChild;

Parent := Child; Child := NewChild; h := h + 1;
while h <= H do begin

X latch on Child and its copies;
Determine NewChild;

Parent := Child; Child := NewChild; h := h + 1;
end;

if X latch are not sufficient for SMOs thenRelease all granted latches; l := m; goto 22;

else begin

46

Update including the SMOs;

47

Release all granted latches; operation completion;

48

end;

図 5 提案プロトコル

ページから再処理（ 2 ） 親ページのキーを比較して，子ページのポインタを取得（ 3 ） 親ページのラッチを解放し，子ページの IS ラッチを獲得
目的の葉ページまで辿り着けば，葉ページに S ラッチを獲得しデータを読む．
更3. 3

新提案手法の更新処理時のプロトコルは，MARK-OPT と同様に二つのフェーズで行われるが，楽観的処理中にラッチカップ
リングは用いない．また，経路誤り検出によってリスタートした場合，その降下でのマークは無効になる．
更新処理時のプロトコルを厳密に定義する．木の高さを H とすれば ，ページのレベル（ h ）はルートが 1，葉ページが H となる．また，l を X ラッチを獲得し始めるページのレベルとす
れば，l は初め H にセットされる．そして，木の降下時にマークする値は m にセットされる．このとき，提案手法のプロトコ
ルは図 5 で定義される．
3. 3. 1

削

除

タプルの削除に伴いページのエント リーが 存在し なくなっ
（ 注 3）

た

ページは削除される．正しいポインタの参照を保証する

ラッチカップリングを行っている場合には，削除されるページ
へのポインタが獲得されることはないので，このことにより特に問題は発生しない．しかし，提案手法はラッチカップリングを行っていないため，削除したページへのアクセスが発生する可能性があり，この問題への対処が必要となってくる．
この問題を解決するために，ドレ イン手法 [22] と delete bit
とい う特別なビット を 組み合わせた手法を 用いる．通常時，delete bit は 0 にセットされていて，削除されるべきページのみ
delete bit を 1 にセットすることで，他のプロセスに経路誤りを知らせる．delete bit が 1 にセットされたページはすぐ には削除されず，ドレ イン手法によって削除される．ドレ イン手法では，削除されるべきノード へのポインタが存在したときに，すでに木の降下を行っていたすべてのプロセスが終了した後，そのページの削除を行う．
3. 3. 2

挿入

タプルの挿入に伴うページのエントリー超過によりインデックスページでスプリットが発生した場合，単一 Btree と異なり，
Fat-Btree では以下に述べるようなページの削除が起こる可能性がある．Fat-Btree では，ページのスプリットによって，エント リーがリモートページへのポ インタのみになることがある．
リモートページへのポインタのみを保持するページは，自 PEの葉ページへのアクセスパスを含まないことを意味するので，
Fat-Btree の規則により削除される．

スプリット発生時のページ削除の有無から図 6 のような三つのパターンに分けられる．パターン（ a ）はページの削除が起こらないため，問題は発生しない．パターン（ b ）はページの（ 注 3）：実用的なワークロード では，エント リーが fanout の半分未満になった

削除が起こるが，そのページへのポ インタは存在しないため，ページをマージするより，エントリーが存在しなくなったページをマージ（削除）問題は発生しない．パターン（ c ）はページの削除が起こり，そする方が効率が良い [21]．



  !"

表 2 実験システムの構成#$ %    



!"

#%$ &'   

  （ b ）右ページ削除

 !

 

No. of Nodes:

464 (Storages), 16 (Clients)

CPU:

AMD Athlon XP-M 1800+ (1.53GHz)

Memory:PC2100 DDR SDRAM 1GB

Network

1000BASE-T

Hard Drive:

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

OS:Linux 2.4.20

Java VM:

Sun J2SE SDK 1.5.0 03 Server VM!#" $表 3 実験システムのパラメータ





   （ a ）ページ削除無図6 



+,!

 (

!

8

)*#





! "



しい経路に復帰することが可能である．よって，提案手法は経delete bit を 1 にセットすることによって，削除されるべきペー
 "

 (

- .

64

Max No. of tuples in a leaf node:

提案手法では，削除されるべきページをすぐ には削除せず，

!



350B

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

路誤りの問題を解決可能である．




! 

4KB

Tuple size:（ c ）左ページ削除

Fat-Btree におけるインデックスページのスプリット

Page size:# $ %$ &'$
! "





ジの検出を可能にしている．さらに，検出後は経路誤りの問題と同様に，ルートページから再降下を行うことで，正しい経路に復帰することが可能である．よって，提案手法は削除される
ページへのアクセス発生問題を解決可能である．

図7

スプリット時の削除ページの変更

また，ページスプリット時に削除ページを交換する手続きは，削除されるページへのアクセス発生問題の経路誤り問題への置のページへのポインタも存在するため，節 3. 3. 1 と同様の問題

換である．よって，経路誤りの問題と同様に解決可能である．
以上より，誤った経路を検出することができ，正しい経路へが発生する．
パターン（ c ）のスプ リット時の問題を解決するために，提案手法では次のような手続きを用いる．図 7 のように右ページのエントリーを左ページにコピーし，左ページは削除せず，右と復帰する手段が存在するため，提案手法は目的の葉ページまでの経路を保証している．
4.

実

験

ページを削除するようにする．右ページへのポインタは存在しないので，スプリット発生時の削除ページへのアクセスという問題は解決される．
スプリット時のページ削除の問題には，節 3. 3. 1 で述べる手法によって解決することも可能である．しかし，節 3. 3. 1 の手法では，ページにアクセスしたプロセスが必ずリスタートが発生するのに対し，本節の手法では，ページのレンジから外れた
ときのみリスタートが発生するので（ 確率は二分の一），こちらのほうが効率的である．
3. 4

正

当

性

Btree の並行性制御は，目的の葉ページまでの経路を保証しなければならない．その経路でラッチカップリングを行わない
場合，経路誤りや削除されるページへのアクセスが発生し，正しい経路が保証されない．よって，ラッチカップリングを用いない手法では，誤った経路を検出し，正しい経路へと復帰する手段が必要となる．
提案手法では，ページの両端に境界値を設け，そのページのキーレンジを明確にすることで，経路誤りの検出を可能にしている．さらに，経路誤りの検出後には，正しい経路に復帰することが必要である．提案手法では，検出後にルートページから再降下を行う．ルートページは必ず正しい経路であるため，正提案する新たな並行性制御方式の有効性を示すために，FatBtree を採用している自律デ ィスク [13]〜[15] に提案手法を実装し実験を行う．
4. 1

実験環境

実験は，我々の提案する分散ストレージ技術である自律デ ィ
スクの模擬実装上で行う．これは Linux クラスタ上に Java を用いて模擬実装されている．今回の実験では表 2 に示す構成のPC と十分なバックボーン性能を持つネットワークスイッチを用いて，実験環境を構成した．
初期 Fat-Btree として各 PE に葉ページを 1 ページずつ作成
し ，これらの葉ページのキーをその PE に格納されるキーの下限値とする．PE 番号の昇順に，初期葉ページのキーの値が大きくなるようにしておくことにより，以後の挿入処理では各 PEに格納される葉ページが静的に分割される．この初期 Fat-Btree
に対してランダムな要素を繰り返し挿入したものを実験に用いる．今回の実験における Fat-Btree の構成パラメータを表 3 に
示す．
4. 2

実験方法

このような環境下の自律デ ィスク上に上記の手法で，自律ディスク 1 台あたり 5120 タプルの初期 Fat-Btree を構築した後，

=  

? @
A


  >;  

4=>

<8



:2

9 47
8

  

5

1376

45



0132


!"#"$&%(')$*+$




  


図 8 自律デ ィスクの台数を変化させたときの並行性制御方式の比較

13 6 974=0<7
8;316 5702314: 04
316 9784316 57
0
2314
/10



  O 

CDFEHGJILK%MON  

@?
> =9





2:

69
83
74
6
1 54
23
01

 




BAC

FG/H&I-J&KFL-'&M"NP Q R
SUTVFXWZY\[^]L(

BAC  @BAC   !"$#$%&')(+* '-,.'     




Fat-Btree におけるリクエスト委譲頻度による比較

各クライアント PC から同時にリクエストを送信する．キーはランダムに選び，検索と挿入操作を実行したときのスループッ
トから性能を評価する．操作を送るのは，ランダムに選択した
PE（ 自律デ ィスク）に対してである．

以下に本実験の概要を述べる．まず，自律デ ィスクの台数を



図 11

2:
69

>3
7 =2
BAC  7 :
=
8 29
;7 3
BAC  2:
72
7:=
BACD E 9

 



<=

;7 3

 
<=

;7 3

図9



 !"# $%&')(#*,+.-/

図 10 更新要求の割合を変化させたときの並行性制御方式の比較? @ A B



D E

 


8;

C

FHG JILKM!ONQP  

:@
?

 

>

B



ABDCFEHGJILKNM  
<;
: 59
89
73 /
.6
25
4/
30
2
- 10
./
,-

>



 
 
 
  
 !#"$%'&)(+*, - . /

 

 

クライアントのスレッド 数を変化させたときの比較

また，今回の提案によって，委譲の頻度は変化しない．
4. 4

更新要求の割合を変化させたときの比較

クライアント PC（ 1 台あたり並行して 8 スレッド ）からリク
エストを送信し，10 秒間操作したときのスループットを測定した．図 10 は，自律ディスクの台数を 64 とし，横軸として更新操変化させたときの各手法のスループットを測定し，従来手法と作の割合を 0%から 100%に変化させ，提案手法と MARK-OPT

提案手法の比較を行う．また，Fat-Btree におけるリクエスト委を，スループットを縦軸として比較したグラフである．

譲の回数も測定する．次に，更新要求の割合を変化させたとき

更新要求の割合が小さいときには，提案手法は MARK-OPTのスループットの測定を行う．最後に，クライアントのスレッのスループットを大きく改善し ているが ，更新要求の割合がド 数を変化させたときのスループットおよび経路誤りによるリ

増えるに従い，MARK-OPT と提案手法の差は縮まる．これは，スタート回数の測定を行う．

全体の処理時間の多くを占める更新処理に対して，提案手法も

4. 3

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

クライアント PC（ 1 台あたり並行して 8 スレッド ）からリク
エストを送信し，10 秒間操作したときのスループットを測定しMARK-OPT と同じ 処理を行うためである．しかし ，更新処理の割合が 100%のときでも，提案手法は MARK-OPT の約 1.45
倍のスループットが得られた．
クライアント のスレッド 数を変化させたときの比較

た．図 8 は，更新比率を 20%とし，横軸として自律ディスクの4. 5

台数を 4 から 64 に変化させ，提案手法と MARK-OPT を，ス

クライアント PC からリクエストを送信し，10 秒間操作したループットを縦軸として比較したグラフで，図 9 は，PE 間のときのスループットを測定した．図 11 は，自律デ ィスクの台

リクエスト委譲回数を縦軸として比較したグラフである．

数を 64，更新比率を 20%とし ，横軸としてクライアントのス

MARK-OPT は，台数増加に伴うスループットの上昇が小さ

レッド 数を 32 から 4096 に変化させ，提案手法と MARK-OPT

い．これは，図 9 からもわかるように，台数増加に従い Fat-Btreeのスループット，及びそのときの経路誤りによるリスタートのにおけるリクエスト 委譲頻度が増加し たからである．ラッチ

回数を全リクエスト数で割った値を縦軸としたものである．

カップリングを行っている MARK-OPT は，リクエスト委譲に

MARK-OPT は，クライアントのスレッド 数の増加に伴うス

3 回のネットワーク通信が必要であるため，リクエスト委譲頻

ループット増加は小さく，また，スレッド 数 512 からスループッ

度が増加はネットワーク通信オーバーヘッド を増大させる．そトが低下し始める．これは，Fat-Btree におけるリクエスト委譲

れに対し，提案手法はリクエスト委譲を 1 回のネットワーク通

時のネットワーク通信回数が多いことで，アクセス高負荷時の信で行えるため，台数増加に伴うスループットの上昇が大きい．

PC 対する負荷が大きいためである．それに対し ，提案手法は

文

クライアントのスレッド 数の増加に伴うスループット増加は大きく，また，スレッド 数 512 までスループットが増加し続ける．

[1]

で，PC 対する負荷が小さいためである．

[2]

Shahram Ghandeharizadeh and David J. DeWitt. Hybrid-Range Par-

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]

まとめと今後の課題

本稿では，無共有並列計算機に適したディレクトリ構造であFat-Btree におけるリクエスト 委譲時の通信コストを減らすた

めに，楽観的処理中にラッチカップ リングを行わないように

[7]

[8]

[10]

Rudolf Bayer and Mario Schkolnick. Concurrency of Operations on
B-trees. Acta Inf., Vol. 9, No. 1, pp. 121, 1977.

[11]

C. Mohan and Frank Levine. ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging.
In Proc. of ACM SIGMOD'92, pp. 371381, 1992.

[12]

吉原朋宏, 小林大, 田口亮, 上原年博, 横田治夫. 並列デ ィレ クト
リ構造 Fat-Btree の並行性制御の改善とその評価. DEWS2005，
2A-o4, 2005.

[13]

Haruo Yokota. Autonomous Disks for Advanced Database Applications. In Proc. of DANTE'99, pp. 435442, 1999.

提案手法と従来手法との比較を行い，提案手法の有効性を確認
[14]

した．

IEICE Trans. Inf.

Syst., Vol. E85-D, No. 8, pp. 12691283, 2002.

指すポインタがないページの方を削除することで，より効率的に処理を行っている．さらに自律デ ィスク上での実験により，Availabilities and

Jun Miyazaki and Haruo Yokota. Concurrency Control and Performance Evaluation of Parallel B-tree Structures.

る．スプリット時に発生するページの削除には，そのページを指すポインタがまだない非削除ページのエントリーをコピーし，Jun Miyazaki, Yohei Abe, and Haruo Yokota.

2004.
[9]

削除ページへのアクセスという問題も発生するが，ドレ イン手法と delete bit を組み合わせることで，この問題を解決してい宮崎純, 横田治夫. 無共有並列計算機向けデ ィレ クト リ構造
Fat-Btree の実装とその評価. 情処研報 DBS-119-68, 1999.
風戸広史, 横田治夫. 並列ディレクトリ構造 Fat-Btree におけるレ
ンジ問い合わせの取り扱い. DEWS2001，7A-7, 2001.
Costs of Reliable Fat-Btrees. In Proc. of PRDC2004, pp. 163172,

グを行わないため，経路誤りという問題が発生するが，ページの両端に境界値を設けることで，問題を解決している．また，

Fat-Btree:

In Proc. of

ICDE'99, pp. 448457, 1999.
[6]

きい．これを除去することによって，提案手法は高いシステム
スループットを獲得できる．提案手法では，ラッチカップリン

Haruo Yokota, Yasuhiko Kanemasa, and Jun Miyazaki.
An Update-Conscious Parallel Directory Structure.

MARK-OPT を拡張した並行性制御方式である．無共有並列計

算機を用いた分散環境では，ラッチカップリングはコストが大金政泰彦, 宮崎純, 横田治夫. 並列データベースシステムにおける更新を考慮したデ ィレ クト リ構成. 信学技報 AI97-44, DE97-77,
1997.

[5]

る並列 Btree の並行性制御として新手法を提案した．これは，Daisuke Ito and Haruo Yokota. Automatic Reconguration of an Autonomous Disk Cluster. In Proc. of PRDC2001, pp. 169172, 2001.

今後の課題として，優れた並行性制御を実現できることが[15]

いる．B-link は，サイド ポインタにより隣のインデックスノー

ter 14, pp. 212230. Taylor & Francis, 2002.
[16]

吉原朋宏, 渡邊明嗣, 小林大, 田口亮, 上原年博, 横田治夫. 並列
Btree 構造における負荷分散処理の並行性制御への影響. 情処研
報 DBS-137-32, 2005.

[17]

Jim Gray and Andreas Reuter.

ド にリンクをもっている．サイド ポ インタがあることにより，ラッチカップリングを用いず，単一ノード ラッチによる並行性制御を行うことができる．また，リスタートを行うことはなく，すべての処理が 1 フェーズで行われる．B-link の Fat-Btree への[18]

650670, 1981.
[20]

科学省科学研究費補助金特定領域研究（ 16016232 ）及び東京工業大学 21 世紀 COE プログラム「大規模知識資源の体系化と活用基盤構築」の助成により行なわれた．

Theodore Johnson and Dennis Shasha.

Utilization of B-trees with

Inserts, Deletes and Modies. In Proc. of PODS'89, pp. 235246,
1989.
[22]

H. T. Kung and Philip L. Lehman. Concurrent Manipulation of Binary Search Trees. ACM Trans. Database Syst., Vol. 5, No. 3, pp.
354382, 1980.

[23]

Damdinsuren
Kanamori.

研究の一部は，独立行政法人科学技術振興機構戦略的創造研究推進事業 CREST，情報ストレージ研究推進機構（ SRC ），文部Vladimir Lanin and Dennis Shasha. A Symmetric Concurrent B-tree
Algorithm. In Proc. of FJCC'86, pp. 380389, 1986.

[21]

Fat-Btree の並行性制御に関して奈良先端科学技術大学の宮崎純助教授に助言を頂いた．ここに感謝の意を表します．また本Philip L. Lehman and S. Bing Yao. Efficient Locking for Concurrent
Operations on B-trees. ACM Trans. Database Syst., Vol. 6, No. 4, pp.

は，INC-OPT と PO [24] というトップダウン手法を組み合わせ辞

Performance of B-Tree Con-In Proc. of ACM SIGMOD'91, pp.

416425, 1991.

さらに，MARK-OPT や提案手法と同様に INC-OPT 方式の拡た並列 Btree に適した楽観的な並行性制御方式である．

V. Srinivasan and Michael J. Carey.
currency Control Algorithms.

[19]

張である PO-P 方式 [23] との比較を検討している．PO-P 方式

Transaction Processing: Concepts

and Techniques. Morgan Kaufmann, 1992.

適用方法を検討し，適用したものと従来手法との比較が必要である．

Haruo Yokota and Ryota Abe. Secondary Storage Conguration for
Advanced Data Engineering. In Nontraditional Database Syst., chap-

知られている B-link [19], [20] の Fat-Btree への適用を検討して

謝In Proc. of ACM SIGMOD'88,

titioning Strategy: A New Declustering Strategy for Multiprocessor

きでも，システム性能に大きな影響がないほど ，その値は十分5.

Data Placement in Bubba.

pp. 99108, 1988.

また，クライアントのスレッド 数が増えるに従い，提案手法のリスタート率は高くなる．しかし ，スレッド 数が 4096 のとGeorge Copeland, William Alexander, Ellen Boughter, and Tom
Keller.

これは，MARK-OPT よりネットワーク通信回数が少ないこと

献

Amarmend,

Masayoshi

Aritsugi,

andYoshinari

PO-P: A Concurrency Control Protocol for Parallel B-

trees. IPSJ Trans. Databases, Vol. 45, No. SIG14, pp. 3038, 2004.
[24]

Y. Mond and Yoav Raz. Concurrency Control in B+-Trees Databases
Using Preparatory Operations. In Proc. of VLDB'85, pp. 331334,
1985.