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

バージョン管理を前提に負荷・容量均衡化を両立させる分散配置の応答性能への影響

Title(English)

The Effects on Access Latency of Distributed Version Management by
a Data-Placement Method Balancing Access Frequency and Data
Amount

著者(和文)

中野真那, 小林大, 渡邊明嗣, 横田治夫

Authors(English)

Mana NAKANO, Dai KOBAYASHI, Akitsugu WATANABE, Haruo
YOKOTA

掲載誌(和文)DEWS2006 論文集

Citation(English)

Proc. of DEWS2006

Vol, no, pages

Vol. , No. , pp. 4c-O2

発行日 / 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 4C-o2

バージョン管理を前提に負荷・容量均衡化を両立させる分散配置の応答性能への影響
中野 真那†

小林

大†

渡邊

明嗣†

横田

治夫††,†† 東京工業大学 大学院 情報理工学研究科計算工学専攻†† 東京工業大学 学術国際情報センター
E-mail: †{mana,daik,aki}@de.cs.titech.ac.jp, ††, †yokota@cs.titech.ac.jp
あらまし

我々が提案している COBALT は， 分散ストレージでバージョン管理を行う場合に，バージョンの新旧に依存したデータアクセス頻度の差を利用して，各ストレージのアクセス負荷とデータ格納量を同時に均衡化させる．ア
クセス頻度の高いデータに対する高速なアクセスと，データ格納量均衡化のための柔軟な配置を可能とするアクセス
パス構造を持つ．COBALT は旧バージョンへのアクセスにリンクの逐次探索を行うため，アクセスコストはリンクをたど る数とその際発生するデ ィスク通信コストに比例して高くなる．また，柔軟性の高い配置を可能にするアクセス
パス構造により，システム拡張時には配置決定のための計算量が増加すると考えられる．これらがシステムに与える影響を評価するために，本稿では COBALT を実装したシステムの応答性能や，ディスク情報を問い合わせるストレー
ジ数による処理コストの変化を調べ，その結果を報告する．
キーワード

アクセスパス， ストレージシステム， 並列・分散 DB

The Effects on Access Latency of Distributed Version Management by aData-Placement Method Balancing Access Frequency and Data Amount
†
†
†
††,†
Mana NAKANO , Dai KOBAYASHI , Akitsugu WATANABE , and Haruo YOKOTA† Department of Computer Science， Graduate School of Information Science and Engineering,Tokyo Institute of Technology†† Global Scientic Information & Computing Center，Tokyo Institute of Technology
E-mail: †{mana,daik,aki}@de.cs.titech.ac.jp, ††, †yokota@cs.titech.ac.jp
Abstract

We proposed the COBALT capable of balancing both access load and data amount within a distributed storage

system managing versions. It combines a parallel Btree structure and linked-lists to balance the access load and data amountsimultaneously by taking account of the difference of the access frequency depending on versions. The combination enables
fast access for frequently accessed data and exible data placement to balance amount of data. However, since the COBALT
sequentially traverses on the linked-lists across the storage devices to retrieve older version of les, the access latency for
retrieving the older versions may increase by the number of links and transfers between storage devices. Additionally, since it
can exibly place the older versions on a large number of candidate storage devices, the cost for deciding the placement tends
to be high. For these reasons, we evaluate the effects on access latency of a COBALT experimental system using a PC cluster.
We also evaluate the effect of a grouping method to reduce the placement cost.
Key words

1.

access path, storage system, concurrent and distributed DB

はじめにムは，履歴管理を行うためにバージョン管理下に置いたファイルの変更情報を保存しておき，必要に応じてそれらを提供する

ソフトウェアや CAD の開発環境，論文の作成などといったことで実現される．ファイル更新の差分を保存するバージョン

ファイルに対して変更が繰り返し発生する状況では，ファイル管理方法は，履歴管理のために保存しなければいけないデータの履歴管理を行ってデータを過去のある時点の状態に戻せるよ

容量が少なくてすむことから，広く利用されている [3]〜[9]．

うにしておくことが求められる [1], [2]．バージョン管理システ

変更履歴を蓄積し 続けるというバージョン管理の特性から，

バージョン管理下に置かれるデータは増え続ける [10], [11]．ま我々はこれまでに [17], [18] において COBALT の偏り制御機

た，バージョン管理対象ファイルの増加や，カーナビの地図配能をシミュレーション実験と PC クラスタ上に実装したプロト

信のように画像，動画，音声などの大容量ファイルに対してもタイプシステムを用いた実験のそれぞれで，データのアクセスバージョン管理を行いたいという要求により，データ量はさら頻度の差を考慮せずに通常の Btree を用いてすべてのデータをに増加する．こういった大量のデータを安定して格納し効率よ

一様に管理する従来の方法よりも，データ格納量の均衡化がよく管理するためには，大容量で高性能なストレージシステムがり効果的に行われることを示した．

必要である．ストレージシステムの性能や信頼性などの理由か
ら，並列分散構成システムが向いている．

本稿ではさらに COBALT を用いた分散ストレージシステムの応答性能を評価する．COBALT は過去のバージョンへアクセ

並列分散ストレージシステムの性能を維持するためには，シスする際に連結リストの逐次探索を行い該当する差分情報を読ステム内の個々のストレージ装置間でアクセス負荷やデータ格

み出す．このため，古いバージョンを読み出す際のコストはリ納量が偏らないようにデータの配置を管理することが重要となンクをたど る数とその際発生するデ ィスク間通信コストによっる [12]〜[14]．しかし ，デ ィレ クト リ構造やデータ分配方法なて増加する．また，リストを用いたアクセスパス構造は，シスどによってデータ配置が制限されたり，アクセス量を均等にす

テム内の任意のディスクにデータを配置することを可能にする

るデータ配置がデータ格納量を均等にするデータ配置と一致す

ため，システム規模が大きくなった場合にはデータマイグレー

るとは限らないといった理由から，アクセス負荷とデータ格納

ション時にデータの移動先候補となるディスクが増加すること

量の均衡化を両立させることは困難である．

により，配置決定までの処理コストが増加すると考えられる．

並列分散ストレージシステムの拡張性を重視したデータ管理

このため，実際にストレージ間の通信コストやアクセスオーバ

方法として，並列 Btree と値域分割を併用する方法 [15], [16] がヘッド が存在する環境で COBALT の応答性能を調査し ，偏り有効である．値域分割は静的に決められたパーティションによ除去機能と応答性能の関係を調べる必要がある．

りシステム中の各ストレージ装置へのデータ配置を決定する．

以下に本稿の構成を示す．次章では提案手法の概要について

パーティションの位置を動的に変更してストレージに格納され説明する．3. では提案手法の応答時間の見積もりを行い，4. でるデータを調整することで，各ストレージ装置のアクセス負荷は実装システムの説明を行う．5. では実験とその結果についてやデータ格納量を調整できる．しかし，値域分割ではデータをの考察を行い，6. で成果についてまとめる．

一次元的に管理するため，アクセス負荷とデータ格納量のど ち
らかのバランスが崩れてしまい，両方を均衡化させることは難2.

COBALT(CombinationOf

Btee-nodeAnd

Linked list Transfer)

しい．また，バージョン管理のために用いられるデータには，ファイルのバージョンの数や生成された時期によってアクセス

ここでは COBALT の概要について説明する．

頻度に差があると考えられる．このため，より効率の良いデー

2. 1

タアクセスを実現するために，アクセス頻度の高いデータに

2. 1. 1

管理モデル
Reverse-delta

はより高速なアクセスを可能にすることが望ましい．さらに，

COBALT は Reverse-delta [3] によるバージョン管理方法を想バージョン管理のためにはあまり使われない履歴データであっ

定している．Reverse-delta はバージョン管理下におかれたファたとしても保存しておく必要があるため，そのデータへのアク

イルの最新のバージョンを基準ファイルとして保持し，ファイ

セスパスを保持できることが必要である．

ルが更新されたときには最新のバージョンから一つ前のバー

これらの問題を解決するために，我々は基準となるファイル

ジョンに戻るための差分を保存する．ファイルの最新バージョにファイル更新差分を適用して行うファイルバージョン管理方

ンにアクセスするときには基準ファイルにアクセスし ，古い法で用いられるデータの特性に注目し，このデータが置かれるバージョンにアクセスするときには，基準ファイルに対して，

レポジトリを分散ストレージシステムに格納するときに，スト取り出したいバージョンまでの差分を順に適用する．

レージ装置間のデータ配置を管理する COBALT(Combination Of

2. 1. 2

Btree-node And Linked list Transfer) を提案している．COBALTCOBALT で前提としているバージョン管理モデルでは，ファバージョン管理モデル

は，ファイルの更新時と読み出し時のデータアクセスによって，イルのある時点の状態のことをバージョンと呼ぶ．また，バー

基準ファイルと新しい差分情報はアクセス頻度が高く，差分情

ジョン管理下に置かれるファイルをバージョンファイルと呼ぶ．

報は古いほどアクセス頻度が低くなるという傾向があることをバージョンファイルの最新バージョンのファイル内容が書き込利用する．アクセス量の多いデータをアクセス負荷分散に, ア

まれている最新版オブジェクトと，一つ前の版に戻るための差

クセス量の低いデータをデータ格納量分散にそれぞれ用いるこ

分情報が書き込まれている差分オブジェクトが配置される領域とで，ストレージシステムにおける二つの均衡化を同時に実現

をレポジトリと呼ぶ．バージョン管理機能はレポジトリから必させる．また，アクセスパス構造を変更し ，並列 Btree と連結

要なデータを取り出してユーザーに提供する．バージョンファ

リストを組み合わせた構造を用いて，基準ファイルと差分情報イルを構成する差分オブジェクトのうち，あるバージョン verを別々に管理することにより，アクセス負荷分散とデータ格納よりも新しいバージョンのファイルを構成するために必要な差

量分散という異なる目的のデータ配置戦略を同時に満たす柔軟

分オブジェクト群を Newer(ver) と呼ぶ．また古いほうの差分オな配置を可能にする．

ブジェクト群を Older(ver) と呼ぶ．

   !  "#$%&('   , J  LKNM  

る．このストレージ装置は通信機能を持ち，制御クエリによっ

てその動作が決まる．ストレージ装置にはクエリやオブジェク  

トを処理するためのモジュール群があり，ストレージ装置同士がそれぞれのディスク情報をやり取りし，クエリを処理するこ




FGIHデ ィレクトリを持つことにより，オブジェクトの位置を管理すとでクライアントの要求に答える．
負荷管理のためには，システム内で動的に定められるコー)+*,*$-$..0/213-54768-:9;*</>=?1@-,A5*B C:A$DEA

デ ィネータの役割をするストレージ装置がデータ移動戦略を決定し，該当ストレージ装置にデータマイグレーションクエリを



;

送信する．
コーディネータはシステム中に一台以上存在する．また，コー

図 1 オブジェクトへのアクセス傾向

デ ィネータには監視領域が設定され，指定された範囲内のスト'   )(  *,+-$#.+  !/ ,0 #$#

レージ装置について負荷管理を行う．コーデ ィネータの故障を検出した際は , システムからランダムに選ばれたストレージ装" #$# !

%& 



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

置がコーデ ィネータの作業を行うものとする.



2. 2

 

図2

スナップショットを用いたバージョン管理モデル

アクセスパス構造

我々が比較対象とする従来手法では，オブジェクトを管理するために並列 B+ -tree を用いる．オブジェクトを値域分割で各ストレージ装置に配分し，ストレージ装置毎にオブジェクトを+B -tree の部分木によって管理する．オブジェクトは種類によら

COBALT はオブジェクトをデータ配置管理の単位として扱う．

ず，すべて B+ -tree の葉ノードに格納される．以下では，この従ファイル更新時は最新版オブジェクトの情報の更新と，差分情来手法を全 B+ -tree 管理手法と呼ぶ．各オブジェクトへアクセ

報を記述した差分オブジェクトが生成され，過去のバージョン

スするには，B+ -tree の根から探索を行う．葉ノード に到着後，ver を読み出す時は，そのバージョンファイルの最新版オブジェ

サイド リンクをたど ることで，名前が連続するオブジェクトをクトと Newer(ver) のすべてが読み出される．このため，レポジ

高速に読み出すことができる．

トリに対してこのようなアクセスが行われた結果，最新版オブ

これに対して，COBALT では上記のオブジェクトのアクセ

ジェクトへのアクセス量が最も多くなり，差分オブジェクトへス傾向を考慮し，管理のために，従来のアクセスパス構造を拡のアクセス量はそれが古くなるにつれて単調減少すると考えら張して並列 B+ -tree と連結リストを組み合わせた構造を用いる．

れる (図 1)．また，オブジェクトへのアクセス傾向には他にも

図 3 に COBALT のアクセスパス構造の概要を示す．

いくつかの性質 [17] が考えられる．COBALT では，このオブジェクト間のアクセス量の傾向を配置決定に利用する．
COBALT では，ファイルの古いバージョンのうち，ソフト

最新版オブジェクトは全 B+ -tree 管理手法と同じ く値域分割により各ストレージ装置に配置し，並列 B+ -tree の部分木が各ストレージ装置に置かれたオブジェクトを管理する．一方，差分ウェアの安定版のように，最新ではないがアクセス量が 多い

オブジェクトはバージョンファイル毎に新しい順にリンクノーバージョンが存在するときは，このバージョンをスナップショッ

ドを用いて管理し，B+ -tree の葉ノードからリンクノードをたどトの形で提供し，差分情報を介さずに直接アクセスが可能であることで差分オブジェクトの位置が分かるようにする．連結リ

るものとする．スナップショットに対して差分を適用すること

ストを用いるため，差分オブジェクトは任意のストレージ装置

により，さらに古い版を取り出すことは可能とする．これによに配置可能である．

り，バージョンファイルの最新版オブジェクトとスナップショッ

また，この構造では，Btree が最新版オブジェクトのみを保

トのアクセス頻度が極大となり, 最新版と各スナップショットの持するため，全 B+ -tree 管理手法に比べて木のサイズが小さく間に存在する差分オブジェクトへのアクセス頻度は単調減少すなる．このため，高速メモリ上に Btree 部分をおくことでアクるのみとなる (図 2)．COBALT では最新版オブジェクトと, ス

セス量の多い新しいオブジェクトに高速アクセスが可能になる．

ナップショットを同様に扱う. スナップショット作成のためには，

2. 3

データ配置方法

アクセスパスを探索して必要な差分オブジェクトを回収し，スストレージ装置間にアクセス負荷やデータ格納量の偏りが生ナップショットを含めたアクセスパスの再構成を行うという作じた場合にはデータマイグレーションを行って偏りを除去する．

業が別に発生するものとする．

アクセス負荷の均衡化のためにはアクセス量の多い，より新し2. 1. 3

システムモデルいオブジェクトを別のストレージ装置に移動させる．最新版オ

COBALT は，複数のストレ ージ装置をネットワークで接続

ブジェクトは値域分割により管理されているため，移動先は論したストレージシステム上にレポジトリを配置することを想定

理的に隣接したストレージ装置となる．また，同時にデータ格する．各オブジェクトは値域分割により各ストレージ装置に配納量を均衡化させるために，アクセス負荷分散に影響を与えな

置され，それぞれのストレージ装置が並列 Btree を用いた分散いアクセス量の少ない，より古いオブジェクトを移動する．オ

BDC)EGFIH+JLKMEONによって変化する．データマイグレーションが時点 t0 で発生し，#$%&% % '() 

移動境界の値を M, 時点 ti でのバージョンに対するアクセス頻
度 y が関数 f (v, ti ) にしたがって減少すると仮定する．y = M と!" AA A/010-2431565
78<;#"    

ションが行われてからのファイル更新回数 u が経過時間 ∆t に比例して u(t) = k × ∆t となるならば ，Pcobalt は P(u(t) + v0 > v)
をデータマイグレーションの発生数 N とその発生間隔 ∆ti 分だ

=?>
@:>

*+ !!,-. %

図3

なるバージョン v0 は v0 = f −1 (M, t0 ) である．データマイグレー/010-2431565
78:96;

け繰り替えす条件付確率で表現される．
応答性能に影響が大きいと考えられるのは，デ ィスク間通信

COBALT のアクセスパス構造

やデ ィスクアクセスである．u(t) に対して v がご く小さく通信が発生しない状況であるならば ，Btree の探索時間が応答性能ブジェクトの移動先にはデータ格納量の少ないいずれかのストレージ装置を選択する．差分オブジェクトの配置は値域分割の影響を受けないためにこのような配置戦略が可能となる．
移動させるオブジェクトを決定するために，移動境界 [17] を用い，配置決定アルゴ リズム [17] に従って，データマイグレー
ションを実行する．各バージョンファイルにおいて，最新版オ
ブジェクトとの比が指定された値になる差分オブジェクトが移動境界となり，移動境界よりも新しいオブジェクトと移動境界よりも古いオブジェクトをそれぞれまとめて配置決定アルゴ リ
ズムで用いる．
3.

時間を見積もる．
ND 台のストレージ装置を有するシステムに NO 個のオブジェ

クトが挿入されていて，そのうち a% が最新版オブジェクトであるとする．このときにバージョンを指定したファイル読み出しを行うときのコストを以下に示す．いずれの方法も Btree を
根から探索して最新版オブジェクトを見つけた後に，差分オブジェクトの探索を行う．取り出すバージョンは最新版から v 個
前のバージョンとする．データ読み出し時にかかるコストは以下の 4 つである．ディスクアクセス等のコストは，ファイル読
み出し時間に含めてある．
BtreeSearch

Btree 探索にかかる時間

LinkSearch

リンク探索にかかる時間

Transmission

デ ィスク間通信時間

この 4 点の合計を式で表し たものを，全 B+ -tree 管理手法と
COBALT のそれぞれについて以下に示す．
log f anout NOv
v+ f anout+ f anout
× Pbtree +FileI /Olog f anout

実装システム

我々はこれまでに Java を用いて COBALT のアクセスパス構
造と負荷管理機能を PC クラスタ上に実装した分散ストレージシステムのプロトタイプ [18] 上で，アクセス負荷分散とデータ
格納量分散の両立効果について調べてきた. クラスタ内の個々の PC が上記の機能を持つストレージ装置として動作する．ここではこのストレージシステムの応答性能を測定し，COBALT

NO ×a
100

アクセスパス構造

4. 1+

全 B -tree 管理手法のアクセスパス構造には，Fat-Btree の実
装 [19] に対して葉ノード にサイド リンクを追加し ，B+ -tree の形にしたものを用いた．
COBALT のアクセスパス構造には，この Fat-Btree に差分オ

ブジェクトを管理する連結リスト構造を付加したものを用いた．
連結リストを構成するリンクノード は，Btree の内部ノード と同様に fanout 個の差分オブジェクトを管理する．生成された差
分オブジェクトは，最新版オブジェクトから辿った一番新しい
リンクノードにその位置を管理される．ファイルのバージョンが増えて差分オブジェクトが fanout 個を超えたときには，新しいリンクノードが生成され，そのポインタがそれより一つ古い
リンクノード のアドレスを保持する．古いバージョンの読み出し時には，このポインタを辿り古いリンクノードに順次アクセ
スすることで必要な差分オブジェクトの位置を得る．

ファイル読み出し時間

COBALT：4.

以下に実装の概要を述べる．

+
COBALT と全 B -tree 管理手法によるデータアクセスの応答

全 B+ -tree 管理手法：

いと考えられる．

の偏り除去機能とそれがシステムに与える影響について調べる．

COBALT の応答時間

File I/Oに直接影響するため，これが小さい COABLT の方が応答が速v
v+ f anout+ f anout
× Pcobalt + FileI /O

f anout は内部ノード に保有可能なリンクの数，Pcobalt Pbtree は+
COBALT と全 B -tree 管理手法のそれぞれで読み出しクエリ中にディスク間通信が発生する確率をあらわす．Pbtree はパーティション境界のファイルを読む確率 NN とその時点で読み出すバー
DO

ジョン数が，そのノード の f anout より大きくなる確率の積となる．Pcobalt はそれまでに発生したデータマイグレーションの回数

COBALT が管理するオブジェクトはファイルシステムのファイルで表現される．COBALT のアクセスパスは差分オブジェク
トのストレージ内でのアドレスを管理し，デ ィレクトリ探索によって判明したオブジェクトのアドレスに対して再度ファイル
アクセスを行うことでデータの読み出しを行う．
4. 2

ストレージ装置内のモジュール

ここでは，COBALT を実現するために実装したモジュールの説明を行う (図 4)．
4. 2. 1

内部クエリ変換モジュール

クライアントからストレ ージシステムに送信されたクエリは，そのクエリを受け取ったストレージ装置の内部クエリ変換
モジュールによって内部クエリに変換され，変換後のクエリが)* +,&

    !"%$&'( !"     

図 5 サブグループの例

 #

図4

ストレージ装置内のモジュール図

発生しないようにマイグレーションを制御する．
5.

実

験

5. 1

実験方法

適切なストレージ装置に処理される．
内部クエリ変換モジュールは，クライアントがバージョンファ
イルに対して要求するファイル更新とファイル読み出しクエリに対して，バージョンファイルの差分オブジェクト生成とデ ィ
スクへの書き込み，最新版オブジェクトと差分オブジェクトの読み出しといった内部クエリに変換を行い，その内部クエリを処理を行うストレ ージ装置に送信するまでの作業をする．モ
ジュールは内部クエリへの変換のために，ファイルのバージョン情報やサイズなどのメタデータにもアクセスを行う．
このモジュールのインターフェースによって，ユーザーはシステム内部のバージョン管理手法を気にする必要がない．
4. 2. 2

負荷管理モジュール

負荷管理モジュールはそのストレージ装置のアクセス負荷とデータ格納量の総量を保持する．アクセス負荷としてはデ ィス
クの r/w サイズと発生頻度の積 [13] を用いる．
コーデ ィネータとなったストレージ装置は，監視対象のストレージ装置に対してアクセス負荷とデータ格納量の報告要求をブロード キャストで送信し，得られたデータを基にデータ配置
変更の方針決定とその実行指示を行う．コーデ ィネータの監視対象には任意のストレ ージ装置群を設定することが可能である．ストレージシステム中の一部のストレージ装置をそのコー
デ ィネータに対するサブグループとし，コーディネータはサブ
グループ中のストレージ装置間の偏りを減らすことを目指す．
システム規模が大きくなると，すべてのストレージ装置と負荷量のやり取りをするのはコストが高い．このため，グループ間に重複するストレージ装置があるようなサブグループを複数定義することで，システム全体の負荷管理を行いながら，ストレ ージ装置間の通信量を減らすことができる．図 5 にサブグループの例を示す．この例では，それぞれのストレージ装置に対して左右の論理的に連続した 4 台のストレージ装置をサブグループとして監視する．
4. 3

データマイグレーションの制御

COBALT では移動境界により移動させるオブジェクトを決定するが，バージョンファイルのバージョン数によっては大量のオブジェクトを一度に移動させることになり，その結果マイグ
レーションのアクセス負荷によるシステム性能低下が発生する．
本実装ではスピード ファクター [20] を導入して，一度のマイグ
レーションで移動可能なデータ量に制限を設け，過剰な負荷がシステムの応答性能を測定するために，以下の実験を行った．
上記のとおり実装した分散ストレージシステムに対してオブジェクトを挿入し初期木を構成したあと zipf 分布に従う偏りをもつ初期クエリを送信する．偏りはデータの値域の中央部にクエリが集中するものを用いる．送信されるクエリは，新規ファイルの挿入，既存ファイルの更新，バージョンを指定したファ
イルの読み出しとする．
このシステムにおいて，一定時間毎に偏り除去操作を実行する．偏り除去操作を簡略化し，データ格納量の均衡化のためのマイグレーション先は，システム内で一番格納量が少ないストレージ装置とする．
測定する応答時間は，内部クエリ変換モジュールが内部クエリを送信してから，目的のオブジェクトを保持するストレージ装置に到着して処理を行いその結果を受け取るまでの時間である．ただし，実験ではクライアントから受け取ったクエリを内部クエリに変換する動作を省略し，ストレージ装置が直接内部クエリを発行している．
クエリが到着するまでに発生するデ ィスク間通信によるネットワーク遅延の影響を除外するために，応答時間を測定するのは，送ったクエリが送り元のデ ィスク内でのみ処理されたときとする．ただし，COBALT の測定実験では，連結リスト探索の際に発生する通信コストは測定に含めている．実験の共通パラ
メタを表 1 に示す．また，今回の実験に用いた実験システムの構成を表 4 に示す．実験では，リンクをたど るためのコストを比較するために，葉ノード とリンクノード の fanout を通常よりも小さくした．
5. 1. 1

実験 1:バージョンを指定した読み出し 要求の応答時間の比較システムに初期木を構成し ，上記の初期クエリを送信する．
一定時間経過後に，初期クエリのうちバージョンファイルの挿入とファイル更新クエリを停止させる．この状態で，指定されたバージョンのバージョンファイルを取り出すのに必要な応答時間を測定する．全 B+ -tree 管理手法と COBALT の Btree が必要とするメモリ量の違いを比較するため，キャッシュされるページ数に対して初期木は十分大きい状態で実験を行う.
実験パラメータを表 2 に示す.

表 1 実験パラメタ (共通設定)
クエリ送信間隔
ページサイズ
ファイルサイズ
クエリ送信スレッド
送信間隔
データ測定スレッド

表 3 実験パラメタ (実験 3, 実験 4)1000msec

ストレージ装置台数
マイグレーション間隔
バージョンファイル数
測定期間
初期クエリ継続時間
偏り除去処理発動時間
移動境界
サブグループのストレージ装置台数

6KB
100KB（ 最新版オブジェクト ），10KB(差分オブジェクト )8 本
100msec
1 本

表 2 実験パラメタ (実験 1)
測定期間取り出すバージョン数
バージョンファイル数
キャッシュサイズ
送信クエリ
初期クエリの要求バージョン数
移動境界
ストレージ装置数
Btree ノード の fanout

5. 1. 2

実験 3

実験 4

32

32

3000msec

1000msec

64000/台32000/台1500sec

1500sec

1000sec

1000sec

500sec 後

200sec 後

80

80

32

8, 16, 32

500msec
0， 3， 9， 12， 17

表4 使用装置

64000/台Sun Microsystems Sun Fire B100x

32MB

CPU

AMD Athlon XP-M 1800+ (1.53GHz)

オブジェクト挿入 90%， 取り出し 10%
バージョンファイルのバージョン数 ∗zipf

MEM

PC2100 DDR SDRAM ECC 1GB

Network

1000BASE-T

80%

HDD

TOSHIBA MK3019GAX

32(30GB, 5400rpm, 2.5inch)

8

OSLinux 2.4.20

Local File System

ReiserFS

Java VM

Sun J2SE SDK 1.5.0 05 Server VM

実験 2：偏り除去効果による応答時間の変化

システム上で偏り除去を行い, データマイグレーションによっ#て偏りが削減されることによる応答時間の変化を測定する．初!"期木構成後に初期クエリ送信を開始し，一定時間経過後にデー
タマイグレーションを行う. データマイグレーションは，初期クエリのオブジェクト挿入クエリの停止時に停止させる．その





  

$&%('*),+.-0/*/21436547

$&%('*),+.-0/*/21436547
8:9 <;4=>@?

  

ACB %EDGFIH






ACB %EDGFIH 89<;4=>?

 

後実験 1 と同様に指定されたバージョンのファイルを取り出すのに必要な応答時間を測定する．マイグレ ーション間隔を






 





3000msec とし ，応答測定開始は実験開始から 1000sec 経過後とした．その他のパラメータは実験 1 に従う．
5. 1. 3図 6 実験 1,2：マイグレーションの有無による応答性能の比較

実験 3：偏り除去操作中の応答時間

マイグレーション処理が応答時間に与える影響を調べるため，が生じるためである．

初期木構成後に初期クエリ送信とデータマイグレーションを行

実験では ，応答時間の差を強調するために ，fanout を通常

い，木の構造変化や偏り除去操作が行われている最中の応答時よりも減らし ，COBALT のアクセスパス構造の Btree の内部間を測定した．実験パラメータを表 3 に示す.

ノードが入りきる程度のページキャッシュ量を設定した．ペー5. 1. 4

実験 4：サブグループの導入による偏り除去方針決定までの処理時間の比較

ジキャッシュは LRU で管理される．
Btree に対してランダ ムにオブジェクトの挿入が行われていデータ格納量の偏りが発生している状況でデータマイグレー

る状況では，差分オブジェクトを読み出すときに経由する内部

ションを行う．各ストレージ装置の状態を調べ，データの移動

ノード と，最新版オブジェクトを読み出すときに経由する内部

量と移動先を決定するまでにかかる処理時間を測定する. コー

ノードが一緒に扱われる．このため，LRU に従うキャッシュア

ディネータに監視させるサブグループに含まれるストレージ装

ルゴ リズムでは，ファイル更新により追加された内部ノード

置数を変化させ，処理時間と偏り除去効果を観察する．コーによって，アクセス頻度の高いオブジェクトへのパス上にあるデ ィネータはサブグループ内でデータマイグレーションとコー

ページがディスクに書き出されてしまい，アクセスに長時間必デ ィネータの役割のローテーションを行う．このため，サブグ

要とすることが考えられる．差分オブジェクトはバージョン番

ループ同士の一部を重複させ，長期的に見て各ストレージ装置

号に基づいて順番に追加されるため，全 B+ -tree 管理手法ではがコーディネータになる確率が等しくなるようにする．実験でスプリット後に充填率が低いまま残るノードがあることも，総は，図 5 のように，左右の論理的に連続した N 台のストレージ

ノード 数の増加に影響する．

装置がサブグループに含まれるような構成を用いた．
実験パラメータを表 3 に示す.
5. 2

結果と考察

一方，COBALT では Btree の内部ノードは最新版オブジェク
トへのアクセスのためだけに使われるため，毎回のアクセスに必要な内部ノード は常にキャッシュにある可能性が高くアクセ

実験 1 と実験 2 の結果を図 6 に示す．実験 1 では，全 B+ -tree

スが短時間で行える．また，差分オブジェクトが追加されると管理手法，COBALT ともに読み出す差分オブジェクトの数が増きには，リンクノードがいっぱいになるまでひとつのノードに加することで平均応答時間は長くなり，また，全 B+ -tree 管理

オブジェクトを追加し，その後新しいリンクノードを作成する．

手法に比べて COBALT の読み出し 時間が短くなることが分か

このため，過去のバージョンにアクセスするときに読まなけれる．これは，COBALT と全 B+ -tree 管理手法のアクセスパス構

ばいけないリンクノード の数が全 B+ -tree 管理手法よりも少な造の違いによって必要なデータをアクセスするための時間に差くなり，短時間のアクセスが可能となる．読み出す差分の数が0 のときの応答時間の差は，Btree の根から葉までの探索を行う 

! "$#&% ' 

ための時間の差を示す．上で述べたように，内部ノード のアク 

セスのためにディスクアクセスを伴う可能性が相対的に高い全

 

+

 

B -tree 管理手法の方が応答時間が長くなる．また，読み出す



差分の数が増加することで，全 B+ -tree 管理手法と COBALT の

応答時間の差が増加しているが，これには，葉ノード やリンク

ノード を読み出すコストの影響だと考えられる．全 B+ -tree 管

理手法の方がひとつの差分情報を読み出す時間が長くなるため









 

 

 

 

に，読み出す差分の数が増えることで応答時間の差が広がる．
ただし ，読み出す差分の数がさらに増加すると，COBALT の

図 7 実験 3：偏り除去操作の応答性能への影響

リンクノードがキャッシュ上に見つからない率も増加するため，"  
(! "
(
'& "
'
B@ A %& "
%
#$ "
#
! "

"))
#*)&#$"+&-,/.012345687:9<;&=?>

全 B+ -tree 管理手法との応答時間の差が縮まっていく．
応答時間の差は内部ノードに使用されるメモリ量の差とオブジェクトへのキャッシュヒット率が影響していると考えられる
ため，さらにキャッシュ管理を含めた詳細な調査が必要である．
実験 2 では，応答時間を測定する前に偏り除去操作を行い，ストレージ装置間のアクセス偏りを減少させている．偏り除去

CED
FHG D
IKJ D
L MPORQTSVU
N

操作によってアクセス集中による応答性能劣化が減少したために，全 B+ -tree 管理手法，COBALT ともに応答時間が短縮され

図 8 実験 4:サブグループの導入による偏り除去効果の比較

る．COBALT では，マイグレーション実行により，必要なバージョンまでの間に存在する差分オブジェクトが異なるストレーためと考えられる．

ジ装置に移動された場合，読み出しの際にディスク間通信が発図 9 では，COBALT の偏り除去の際に負荷量を考慮するスト

生するために応答速度の劣化が予測された．しかし，今回の実レージ装置台数と，それらに対して負荷状況を聞き, 適切なス

験ではマイグレーション後も応答時間は劣化していない．理由

トレージ装置にデータマイグレーションを行うまでの処理コスとしては，偏り除去処理を行なうことによりストレージ装置のトの関係が示される．サブグループに含まれるストレージ装置

処理性能が改善されるため，通信コストを含めても応答時間が台数が増えることで，処理の平均時間が増加している．また，抑えられることがあげられる．

32 台のときには，処理が行われるまでに特に長い時間がかかる

実験 3 の結果を図 7 に示す．実験 3 では，初期木に対して初場合があることが分かる．処理コストに影響するのは，ネット

期クエリとデータマイグレーションが同時に発生している状況

ワーク状況や各ストレージ装置が処理しているクエリの状況とで読み出しクエリを送信し，応答時間を測定した．図中に示さ

いった，負荷量の応答を得るまでの時間や，コーデ ィネータがれた初期クエリと偏り除去処理の継続期間より，新規ファイル得られた回答を処理してデータの移動先と移動量を決定するまの挿入とデータマイグレーションによる木の構造変化が発生しでの計算コストなどである．台数が多いとこれらの要因によるているときには，応答時間が通常よりも長くなることが分かる．

遅延が大きくなるということが，実験結果の処理コストの平均

これは，Btree の構造変化によって内部ノード にアクセス制限とばらつきの増大によって分かる．さらに，サブグループに含がかけられるために発生する遅延である．また，偏り除去処理

まれるストレージ装置台数を減らすことで，このコストを削減の開始と終了前後で応答時間が増加傾向にあるが，これはマイできることが分かる． データマイグレーションのための処理コ

グレーションによってストレージ装置に格納されるオブジェク

ストの削減は，システムの通常動作に影響を与えずにデータマトが変化し ，オブジェクトや内部ノード のアクセスの際にデ ィ

イグレーションを行うために必要である．ストレージ装置の数

スクアクセスが発生するためである. 応答時間を測定するためが増え，数百台規模の大規模ストレージに COBALT を適用すのクエリは，初期木に対して行われるため，マイグレーション

るときには，偏り除去処理のコストはさらに増大すると予想さの結果構成された木へこのクエリを送信すると応答の挙動に差れるため，サブグループに含まれるストレージ装置台数を限定が生じる．

することで偏り除去処理のパフォーマンスを向上させることは実験 4 の結果を図 8，図 9 に示す．サブグループに含まれる有効である．より効果的な偏り除去処理のためには，アクセスストレージ装置台数を減少させることで，システム全体の偏りパターンも考慮に入れてサブグループの台数を調整するといっ除去効果が低下することが予想される．しかし，図 8 では，台たチューニング方法を考えることも必要である．

数を変更したことによる偏り除去効果の差は僅かである．これは，ストレージ装置に対して送信したクエリの偏りパターンの6.

結論と今後の課題

ピークがひとつであったため，マイグレーション方針決定時の本稿では，分散ストレージシステム上にファイルバージョン

マイグレーションの移動元と移動先の決定結果に影響が少ない

管理下にあるデータを置くレポジトリを構築する際に，データ手法で表現することが必要である．
 

謝

 
'
%&
!#"$




辞



本研究の一部は，独立行政法人科学技術振興機構戦略的創造

研究推進事業 CREST，情報ストレージ研究推進機構 (SRC)，文

部科学省科学研究費補助金特定領域研究 (16016232) および 東 



京工業大学 21 世紀 COE プログラム「大規模知識資源の体系化と活用基盤構築」の助成により行なわれた．
文

図 9 実験 4:サブグループの台数と偏り除去処理コストの比較[1]

D.B.Leblang.

献

The cm challenge: Conguration management thatworks, conguration management, ed. Wiley Co., pp. 138, 1994.

を各ストレージ装置上に効率よく配置するために我々が提案し[2]れまでに，PC クラスタ上に COBALT 機能を実装したプロトタ
イプシステムを用いた実験で，アクセス負荷とデータ格納量の[3]

Walter F. Tichy. RCS  a system for version control. Software 
Practice and Experience, Vol. 15, No. 7, pp. 637654, 1985.

[4]

M.J. Rochkind. The source code control system. IEEE Trans Software Eng SE-1, pp. 364370, 1975.

同時偏り除去について，すべてのデータを Btree によって管理する従来手法 (全 B+ -tree 管理手法) よりも効果があることを示

E. Change R.H. Katz. Managing change in computer-aided design
databases. Proc. of VLDB Conf., Brighton, England,, Sep. 1987.

ている COBALT の応答性能について評価を行った．我々はこ[5]

Brian Berliner. Cvs ii: Parallelizing software development. In Proceedings of the Winter 1990 USENIX Conference, 1990.

した．今回はさらに COBALT を用いたシステムの応答性能を[6]J. MacDonald. File system support for delta compression, 2000.

調べ，全 B+ -tree 管理手法の応答性能や，偏り除去戦略を変え[7]

Shu-Yao Chien, Vassilis J. Tsotras, and Carlo Zaniolo. Efficient management of multiversion documents by object referencing.

たときの結果と比較した．
COBALT のアクセスパス構造によって影響を受けると考えら[8]化を抑えることもできた．また，COBALT を適用するシステム[10]

天海良治, 一二三尚, 小西隆介, 佐藤孝治, 木原誠司, 盛合敏. Linux
用ログ構造化ファイルシステム nilfs の設計と実装. 情報処理学会, 第 2005 巻 of 2005-OS-099, 5 月 2005.
Sourceforge. http://www.sourceforge.net.

[11]

Yongqin Gao, Vince Freeh, and Greg Madey. Analysis and modelingof the open source software community. In NAACSOS Conferenceの規模が大きくなった際に，偏り除去のための配置決定コストが増加するという影響を軽減するため，負荷状況を監視する対2003, June 2003.
[12]

象のストレージ装置台数を変化させた実験を行った．監視対象のストレージ装置台数を減らしても偏り除去効果への影響の違

405415, May 1991.
[14]

the winter. In SOSP '05: Proceedings of the twentieth ACM symposium on Operating systems principles, pp. 177190, New York, NY,
USA, 2005. ACM Press.

サイズのファイルが混在する状況での評価や，ファイルの更新[15]445. ACM Press, 1991.
[16]

IEEE Computer Society, 1999.
[17]

トを回収し ，スナップショットを作成し ，アクセスパスを書き換える等のコストの評価が必要である．さらに，高速な応答を[18]

ンに応じてサブグループの規模を変更するなどの調整方法を考えることも必要である．また，COBALT は Reverse-delta によるバージョン管理方法を前提としているが，このアクセスパス[19]

構造は，Forward-delta [3] によるバージョン管理法や，その他の段階的にアクセス頻度が低下していくデータの管理にも用いることができると考えられる．このため，他種データに対して本手法を適用する際の配置戦略の変更や，それを一般的な計算

Haruo Yokota, Yasuhiko Kanemasa, and Jun Miyazaki. Fat-btree: An
update-conscious parallel directory structure. In ICDE, pp. 448457.

トを作成して Btree に挿入するという作業を行うことを前提に可能にするためのメモリチューニング方法や，アクセスパター

Bernhard Seeger and Per-Åke Larson. Multi-disk b-trees. In James
Clifford and Roger King, editors, SIGMOD Conference, pp. 436

評価が必要である．また，COBALT は過去のあるバージョンへしている．このため，リンクをたどりなおして差分オブジェク

Qingbo Zhu, Zhifeng Chen, Lin Tan, Yuanyuan Zhou, Kimberly Keeton, and John Wilkes. Hibernator: helping disk arrays sleep through

今後の課題としては，COBALT の更なる評価として，様々なアクセス量が増えた場合には，そのバージョンのスナップショッ

Gerhard Weikum, Peter Sabback, and Peter Scheuermann. Dynamic
File Allocation in Disk Arrays. Proceedings of ACM SIGMOD, pp.

わかった．

頻度やアクセス傾向などにより現実に近いパターンを使用した

H. Simitci. Storage Network Performance Analysis. Wiley Technology Publishing, 2003.

[13]

いがあまり見られなかったが，台数を削減することは偏り除去
方針決定までの処理コストを小さく抑えることができることがDelta algo-Vol. 7, No. 2, pp. 192214, 1998.
[9]

ときにも全 B+ -tree 管理手法より応答時間が抑えられることが示された．偏り除去操作を加えることで，さらに応答時間の劣James J. Hunt, Kiem-Phong Vo, and Walter F. Tichy.

rithms: an empirical analysis. ACM Trans. Softw. Eng. Methodol.,れる，バージョンを指定したファイル読み出しクエリの応答性能の評価では，COBALT は読み出すバージョン数が多くなった

In TheVLDB Journal, pp. 291300, 2001.

[20]

中野真那 , 小林大 , 渡辺明嗣 , 上原年博 , 田口亮 , 横田治夫. 分散
環境でのファイル版管理のためのアクセス頻度を考慮したデー
タ配置法. 第 16 回電子情報通信学会データ工学ワークショップ
論文集，DEWS2005，5B-i5. 電子情報通信学会, Feb. 2005.
中野真那, 小林大, 渡邊明嗣, 上原年博, 田口亮, 横田治夫. アクセ
ス頻度と容量分散を考慮した版管理用データ配置法の実装と評
価. 信学技報 Vol.105,No.337, 第 105 巻 of DE2005-130, pp. 3136,
東京, 10 月 2005.
吉原朋宏 , 渡邊明嗣 , 小林大 , 田口亮 , 上原年博 , 横田治夫. 並列
btree 構造における負荷分散処理の並行性制御への影響. 情処学会研究会報告, 2005-DBS-137. 情報処理学会, 2005.
Hisham Feeli and Masaru Kitsuregawa. Ring: A strategy for minimizing the cost of online data placement reorganization for btree
indexed database over shared-nothing machines.
190199. IEEE Computer Society, 2001.

In DASFAA, pp.