Get cached

逐次記録型の分散データ管理システムに関する研究
平成 25 年 9 月
大阪市立大学大学院
工学研究科
（やすだ ゆたか）
安 田 豊 i
目次
図
vi
表
vii
第 1 章 序論
1.1
1.2
1
背景 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.1.1
分散環境でのデータ管理手法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.1.2
非構造的なデータの管理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.1.3
構造的なデータの管理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.1.4
分散環境でのデータ更新 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
問題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.2.1
楽観的更新における更新衝突と修復 . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.2.2
修復処理のアプリケーション依存性 . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.2.3
追記に基づくアプリケーション . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
1.2.4
不要データの削除 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
1.2.5
キャッシュの利用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
1.3
研究の目的 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4
関連研究 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.5
論文の構成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
第 2 章 WOODS の基本構成
19
2.1
はじめに . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2
関連研究 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.1
更新の衝突と修復 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
目次
ii
2.3
2.4
2.5
2.6
2.7
2.2.2
ネットワーク分割時の書き込み . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2.3
ネットワーク再結合時のデータのマージ . . . . . . . . . . . . . . . . . . . . . . 21
設計 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3.1
データ構造 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.2
end record 管理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3.3
ストレージとの関係 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
特性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.4.1
Content Hash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.4.2
チェインのループ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.4.3
レコードの Read と Write . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
適用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.5.1
システム構成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.5.2
並行性のある記録とロック . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.5.3
チェインのマージ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
考察 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.6.1
衝突頻度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.6.2
end point の増大 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
まとめ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
第 3 章 削除機構の設計
41
3.1
はじめに . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.2
関連研究 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.3
設計 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.3.1
レコードの削除 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.3.2
参照カウンタの拡張 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.3.3
Lease time フィールド . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.3.4
Pending time フィールド . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.4
評価 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.5
まとめ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
第 4 章 キャッシュ機構の設計
49
4.1
はじめに . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.2
関連研究 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.3
キャッシュの手法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
目次
4.4
4.5
4.6
iii
4.3.1
基本的なデータの読み込み . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.3.2
プロアクティブ・キャッシュ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.3.3
キャッシュ管理手法への要求 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
参照カウンタの拡張 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.4.1
不完全なチェインの処理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.4.2
存在しないレコードのカウント . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.4.3
チェイン途中にあるレコードの削除 . . . . . . . . . . . . . . . . . . . . . . . . . 58
評価 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.5.1
システムモデル . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.5.2
シミュレーション . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
まとめ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
第 5 章 結論
65
5.1
まとめ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.2
残された課題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
参考文献
71
v
図目次
1.1
CFS のデータ構造 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.2
CVS における更新衝突の警告 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.3
Dropbox における更新衝突の警告 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.4
二つの並行する追記 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
1.5
衝突した更新結果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.1
システムの構成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2
基本的なデータ構造 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3
分岐するデータ構造 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.4
レコードの構造 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.5
チェインの構造 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.6
メイリングリストを実現するサンプルアプリケーション . . . . . . . . . . . . . . .
2.7
レコードの追加（左から図 a, b, c） . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.8
並行したデータの記録（左から図 a, b, c） . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.9
マージ処理の例（左から図 a, b） . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
26
2.10 debian-user メイリングリストの投稿間隔分布 . . . . . . . . . . . . . . . . . . . . . . . 35
2.11 end point の統合（左から図 a, b） . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.12 end point 数の分布 (1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.13 end point 数の分布 (2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.1
システムの構成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.2
レコードの削除 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.3
レコードの追加処理（左から図 a, b） . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.4
一日あたりのメンテナンスのためのメッセージ数 . . . . . . . . . . . . . . . . . . . . . 48
4.1
Read アクセス . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.2
二つの WOODS 空間 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
図目次
vi
4.3
チェインの共有 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.4
不完全なチェイン . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.5
チェイン途中にあるレコードの削除 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.6
モデルとするアーカイブシステム . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.7
キャッシュのヒット率 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.8
遅延の短縮 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
vii
表目次
2.1
end point の最大数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
1
第1章
序論
背景
1.1
1.1.1
分散環境でのデータ管理手法
近年の計算機システムの低価格・高性能化とネットワークシステムの広帯域化に伴い，分
散処理技術を用いたネットワークサービスの普及が進んでいる．広域に分散した多数かつ
不安定なノードの利用を前提とした Peer to Peer (P2P) システムはそうした分散処理技術
を用いたもののひとつである．P2P システムには Chord [1, 2] に代表される分散ハッシュ
テーブル (DHT) などの数学的なルールに基づいたノード配置を行う構造化オーバレイ技
術を用いるもの [3–10] や，そのようなルールによらずノードの参加順などによってノード
を組織する Freenet や PlanetP [11, 12] などの非構造化オーバレイシステムがある．
P2P 技術の適用分野の一つに分散ストレージシステムがある．これは多数のノードがそれ
ぞれに保持するストレージを結んで単一の大きなストレージシステムとして扱えるようにす
るもので，構造化オーバレイ技術を用いた例としては CFS [13], Ivy [14], OceanStore [15,16]
など，非構造化オーバレイによるものには Freenet などがある．
こうした分散ストレージシステムにおけるデータ管理手法の一つに，Content Hash ID
を利用するものがある．Content Hash ID とは，管理単位となるデータの内容すべてをハッ
シュ関数に掛けて得られたハッシュ値をそのデータの ID として用いる方法である．ハッ
シュ関数に高い衝突困難性と一方向性を備えたものを用いることによって，ID が同じデー
タは内容も同一であると見なすことが可能になる．その結果，全てのアプリケーションが
同じハッシュ関数を用いておれば，以下のような性質を得ることができる．
1) 同じ分散ストレージを共有する複数のアプリケーションが，ID を他のアプリケーショ
ンとの連携作業無しに自分自身で決定できる
2) 各データはその ID を保持したまま，作成されたストレージ空間とは異なる，別のス
第 1 章 序論
2
トレージ空間に移動させることができる
Content Hash ID に基づくデータ管理手法では，データはすべて immutable である．つ
まりデータ内容の変更はそのデータの ID そのものを変化させるため，既存のデータの内
容を部分的に書き替えることができない．そのような部分的な更新は異なる ID をもつ新
しいデータの作成，すなわち更新後のデータイメージをまるごと別のデータとして作成す
ることで実現される．
もし二つのアプリケーションから並行に「同一データに対する異なった内容の更新要求」
があった場合，それらは「独立した二つのデータの新規作成要求」として処理される．
また，二つのアプリケーションが並行に全く同じ内容のデータを分散ストレージシステ
ムに作成する場合は，その両方のアプリケーションが処理の正常終了をストレージシステ
ムから受け取るが，しかしストレージ上には一つのデータしか作成されない．この二つの
並行したデータ作成処理のうち，どちらがそのデータをストレージシステムに作成したと
しても結果は同じであり，どちらが一瞬先に処理を開始，あるいは完了したかは問題とな
らない．当該データは二つのアプリケーションから参照されることになるが，両アプリケー
ションがそのデータについて他のアプリケーションからの参照があるかないかを意識する
ことも無い．
これは一つのストレージ空間における複数の分散アプリケーションが他のアプリケーショ
ンの存在を意識すること無く稼働可能であり，互いに同期や調停のためのオーバーヘッド
などを必要としない状況があり得ることを意味する．つまり複数のアプリケーションが連
携して動作することで一つの機能を実現するような場合でも，本質的に必要な情報交換以
外のオーバヘッドを低く抑えた状態で機能し得る．
これは特に P2P 環境のようなノードが広域に分散した，大規模な構成で高いスケーラビ
リティの実現を目指す分散アプリケーションにとって優れた性質である．
1.1.2
非構造的なデータの管理
非構造的な，つまり互いに関連づけられていないデータをフラットな ID 空間上に配置
し，それら単一データの格納・取り出しだけを目的とする場合，Content Hash ID は直接
的かつシンプルに適用可能なデータ管理手法の一つである．
そのような分散アプリケーションの一つに，P2P ファイル共有サービスがある．その良
く知られた実装の一つである Freenet は共有するファイルのハッシュ値を利用して取得ファ
イルを特定することが可能である．Winny も同じくファイルのハッシュ値を検索キーに利
用できる．
非構造的なデータを個別に扱うだけの利用であれば，データはそれぞれの関連性を保持
1.1 背景
3
する必要がなく，システムがメンテナンスすべきデータ構造と呼べるようなものは存在し
ない．そうした状況では，Content Hash ID は 1.1.1 節の 1), 2) に示したように ID 決定
などを含めた多数ノードでの連携処理に関するオーバヘッドが低く，スケーラビリティに
優れたデータ管理手法である．
1.1.3
構造的なデータの管理
しかし非構造的なデータを静的に提供するだけでは，それを用いて実現できるサービス
の機能には限りがある．実用的なネットワークサービスを実現するためには何らかの形で
構造化された，すなわち互いに関連づけられたデータ群の管理が必要となる．しかし構造
的なデータを分散環境で管理するのは容易ではない．以下に BitTorrent と CFS を対象に，
それらのシステムが構造的なデータを管理するために採った設計上の工夫，あるいは制約
について述べる．
BitTorrent における解決：集中処理
P2P 環境で動作するよく知られたデータ交換システムである BitTorrent も，Content
Hash ID を部分的に利用したシステムの例である．
BitTorrent では提供されるファイルは piece と呼ばれる小さなデータ断片に分割される
が，この piece は Content Hash ID によって管理され，ファイルを交換するクライアント
間ではこの ID に基づいて互いに欠落したデータの交換処理が行われる．piece をユーザが
互いに交換するために必要なノード群に関する情報管理のためには，それらの情報を関連
づけて格納するためのデータ構造が必要であり，その構造化された管理データは P2P 的な
分散処理手法を用いずに Tracker と呼ばれる集中サーバで管理される．つまり交換の対象
となる piece データそのものは Content Hash ID に基づいて管理されているが，それだけ
では本来の目的であるファイル交換を実現することはできず，Tracker が提供する構造的な
管理データと合わせてようやく BitTorrent はシステムとして機能することができている．
そしてこの管理データを P2P ネットワーク上で分散管理せず単一のサーバである Tracker
上で集中管理するのは，それがノードの参加・離脱を含めた BitTorrent ネットワークに頻
繁に起きる状態変化に対応して情報を更新しなければならないためである．つまり分散環
境で構造的なデータを整合性を保ちながら更新するためのオーバーヘッドを避けるために，
BitTorrent はピュア P2P ではなく集中サーバに依存したシステム構造を選んだのである．
しかし BitTorrent では一時的なトラフィック集中 [17] も観測されており，こうした集中処
理はスケーラビリティを高めるための障害となりやすい．
第 1 章 序論
4
CFS における解決：Read Only
BitTorrent が要求したような更新の必要がなければ，構造的な，互いに関連づけられた
データを Content Hash ID によって管理することに問題はない．例えば CFS は Read
Only ではあるが従来的なファイルシステムをブロック単位のデータ管理によって提供する
ものである．CFS の構造と課題は 1.4 に詳しく述べるとして，ここでは Content Hash ID
をキーとして構造的なデータを扱う一例としてそのデータ構造とアクセス手法について説
明する．
b1
i1
(from
root-block)
hash(b1)
hash(b2)
d1
hash(i1)
hash(i2)
i2
directory block
hash(b3)
hash(b4)
hash(b5)
b2
b3
b4
inode block
b5
data block
図 1.1
CFS のデータ構造
図 1.1 に CFS の具体的なデータ構造を示す．CFS ではファイルをブロック単位で管理
し，directory block, inode block, data block とファイルシステムを構成するデータをすべ
てブロック化して分散ハッシュテーブル (DHT) によるデータストアである DHash [18, 19]
に保持する．DHash ではデータの探索アルゴリズムに Chord を用いており，CFS では
データブロックの Content Hash ID を Chord における探索キーとして利用している．各
ブロックはより下位のブロックの Content Hash ID を管理情報として持つことで関連づけ
られている．たとえば図 1.1 の inode block i1 はそれが含む data block b1, b2 の Content
Hash ID の値を保持している．
CFS はブロック単位のデータ管理を Content Hash ID で実現したシンプルな実装例で
あり，Content Hash ID に基づく分散ストレージ分野における早期の研究でありながら，
単純な構造で DHash による優れた分散効率と高いスケーラビリティを実現している．な
おこのデータ構造によってストレージ利用効率を高める重複排除記録を実現している．
1.2 問題
1.1.4
5
分散環境でのデータ更新
CFS はそのアクセスを Read Only に限定していたが，もちろん更新可能な分散ストレー
ジシステムに対する要求は以前から存在していた．そのため CFS の後には，さらに広範
囲な目的に適用可能なアプリケーションとして Ivy や ePOST [20] をはじめとした更新可
能な分散ストレージを利用したシステムが幾つも提案されることとなった．
しかし通信遅延が大きい環境でのスケーラビリティを第一とする分散環境では，更新処
理は楽観的 (optimistic) な更新手法をとらざるを得ず，そこで生じる更新衝突とその解決
が問題となってしまう．Ivy や ePOST などはいずれもこれを完全に解決することはでき
ず，一貫性管理に関する課題を残している．
次節以降にこの更新衝突にかかわる一貫性管理の問題について述べる．
1.2
1.2.1
問題
楽観的更新における更新衝突と修復
分散ストレージシステムにおけるデータの更新手法は一般に，単一の更新者が必要な資
源を事前にすべてロックし，他からのアクセスをブロックしてから更新処理を行う悲観的
(pessimistic) な手法と，同期なしの更新を認めるかわりに複数更新者による更新内容の衝
突を事後に検出・修復する楽観的 (optimistic) な手法に大別される．
この両者の間には性能，可用性の向上と整合性維持コストとのトレード・オフが存在す
る．分散環境，特に P2P 環境などではネットワークおよび各ノードの可用性を低く見積
もらざるを得ないために，データは常に複数箇所にそのコピーが用意される．悲観的手法
では複製を保持する全てのノードをロックした後に更新処理を開始する必要があるが，通
信の遅延が大きな環境ではこれらの処理には時間が掛かる．ノード数が増えて規模が大き
くなるにつれてこのオーバヘッドは大きくなり，結果的に悲観的手法では更新処理の性能
が低くなってしまう．楽観的手法は処理性能の問題を解決する一方で，複数更新者による
処理の競合・更新内容の衝突検出や，その修復処理を必要とする．
更新衝突は複数の更新者がストレージシステムに対して競合する処理を並行に発行する
ことによって生じる [21–24]．また一般に削除はメタデータに対する更新処理として実現さ
れることから，削除と上書きを異なる更新者が並行して発行した場合にも競合が生じる．
楽観的更新によって発生する矛盾の解決は通常，アプリケーションごとに特有の解決法
を用意するしか対処方法がなく，たとえ自動化できたとしても全てのシステムに対する一
般化は困難であると指摘されている [25]．単に衝突を検出するだけで矛盾解決は手作業で
行わせている場合も多い．典型的な例の一つは更新可能なファイルシステムの一つである
Coda [26] である．そこではファイルシステム側での完全な自動修復は考慮されておらず，手
第 1 章 序論
6
作業による修復作業を前提としている．むしろ設計者である Satyanarayanan は “Conflicts
are ultimately an application-specific concept” であるとして衝突そのものがアプリケー
ション側で考慮されるべきものだと主張している [27]．
また，解決そのものをあきらめて CVS [28] や塚田らによるファイル同期システム [29]
のように更新の衝突は検出可能でも防止はできず，修復は行わない例も少なくない．たと
えば CVS では衝突が生じた場合，更新処理の発行時に図 1.2 のようなメッセージを表示
してユーザに手作業での修復が必要であることを知らせるのみである．
$ cvs update pres.tex
RCS file: /home/techtalk/c/iOS/pres.tex,v
retrieving revision 1.1
retrieving revision 1.2
Merging differences between 1.1 and 1.2 into pres.tex
rcsmerge: warning: conflicts during merge
cvs server: conflicts found in pres.tex
C pres.tex
図 1.2
CVS における更新衝突の警告
2007 年にサービスを開始した比較的新しいシステムである Dropbox [30] でも同様に，
同一ファイルに対して異なる操作をした場合は検出と、矛盾を含む結果の保存だけを行い，
図 1.3 のようなメッセージを表示するだけで修復はユーザの手作業に任せている．
図 1.3
1.2.2
Dropbox における更新衝突の警告
修復処理のアプリケーション依存性
衝突した更新処理の自動修復について，そのアプリケーション依存性をなくして一般化
することが困難なのは事後の修復による処理結果の修正，つまりファイル内容の変化など
にアプリケーションが対応することを求めざるを得ないためである．
たとえば二つの更新アプリケーションがあるファイルの同一箇所を書き換える処理を並
行に実行した場合，楽観的手法ではまずこの両方の更新処理は個別に実行されてしまう．そ
の後，二つの更新結果はシステム内で統合されて衝突が検出される．このとき何らかの基
準で一方の更新処理が成功，他方の処理が無効となって，ファイルの内容は無効とされた
1.2 問題
7
アプリケーションが認識していた結果とは異なった内容に修復される．
この場合，更新成功後あるいは修復前のファイルの状態に基づいて処理を進めていたア
プリケーションが，そのまま処理を続行して良いかどうかはアプリケーションによる．修
復後の内容を新たな更新としてただ受け入れれば良い場合もあるだろうし，そのための処
理を追加するなり，更新処理そのものをやり直すなどの対応をしなければならない場合も
あり得る．つまりこれらの対応処置がアプリケーション依存であるために，更新衝突の解
決法もまたアプリケーションごとに用意せざるを得ない．
そこでアプリケーションに対する依存した復旧処理を不要にするために，更新成功が確
定するまで処理の進行を止めることも可能であるが，それは悲観的手法でのロックによる処
理のブロックと同等であり，性能などに関する楽観的な更新モデルの利点を失ってしまう．
こうした更新衝突の結果必要となる復旧処理のアプリケーション依存性が，楽観的更新
モデルでの汎用的なデータ管理モデルの構築を妨げている．つまり分散処理システムを構
築する際は，一般にそのアプリケーションの設計だけでなく，アプリケーション固有の修
復方法を組み込んだ専用のデータ管理機構の設計を必要とする．これに対して Stribling ら
はアプリケーションごとのデータ管理機構の再設計を必要としない汎用のデータ管理モデ
ルの必要性を主張しており [31]，実現すべき課題である．
1.2.3
追記に基づくアプリケーション
しかしアプリケーションによっては，必ずしもこうした問題の原因となる衝突や修復を
生じる更新処理を必要としない．
たとえば電子メイルやチャットなどのメッセージング・アプリケーションは送受信した
メッセージの内容を書き換えることがないため，まずデータの同一箇所を書きかえること
による更新衝突がもともと生じない．すなわちデータへのアクセスはメッセージ単位の追
記による Write Once, Read Many （本論文では WORM と略記する）タイプである．
こうしたデータの記録を追記によってのみ行うアプリケーションのうち，追記の要求が
複数の送信者によって並行して生じた場合にその処理順が必ずしも問題とならないものが
存在する．たとえば従来的な電子メイルにおいてもメイルの厳密な到着順は保証されてお
らず，単一の送信者からのメッセージであっても時として配送遅延のために到着順が前後
することがある．
このようなアプリケーションにおいては並行した追記処理のいずれかが無効となること
はないため，すべての要求に対して楽観的に更新成功と返答することに問題がない．
しかし追記そのものが無効にならないとしても，追記要求の順序を一意に決定する必要
があるアプリケーションにおいては修復処理が発生してしまう．たとえば図 1.4 に示したよ
うにファイル File X に対してデータ a, b の追記がそれぞれ二つのアプリケーション App
第 1 章 序論
8
A, App B から並行に行われた場合について考える．
App A
a
append
File X
append
b
App B
図 1.4
二つの並行する追記
このときファイルシステムは更新された結果として図 1.5 の点線より上の状態，つまり
アプリケーション App A に対してはファイルの内容を Xa1 ，App B に対しては Xb とし
て提示する．しかし事後に更新結果が統合されるとき，ファイルシステムはその内容とし
て Xab あるいは Xba のどちらかを選択せざるを得ない．
View of App A
File X
View of App B
File X
a
b
Right after append
After merged
File X
a
b
File X
normal append
図 1.5
a
b
conflicted result
(need recovery)
衝突した更新結果
たとえば Xab が選ばれた場合，すなわち図 1.5 の点線より下の状態となった場合は，ア
プリケーション App A は単に b の追記があったと解釈して処理を続行することが可能で
も，App B は処理のやり直しなどの対応が必要となる．
しかし Twitter [32] のタイムライン, Facebook [33] のニュースフィードやコメント処理
などでは，すべての利用者からメッセージの並び順が同一に見えることを保証しておらず，
こうした追記後のシリアライズを必要としない．そしてこうした性質のメッセージ処理は，
より大きなスケーラビリティを得るために今後増えていくと考えられる．
このようなアプリケーションに対して，更新処理が並行した状態で実行されたことをそ
のまま記録し得るデータ形式を用いれば，追記処理のシリアライズにともなう修復を回避
1
Xa はファイル X の末尾にデータ a が追記された状態を意味する．
1.2 問題
9
することが可能であり，これを基に衝突が無く，アプリケーションに対する依存性をもた
ないデータ管理構造を設計することが可能となる．
1.2.4
不要データの削除
分散ストレージシステムを用いて提供されていたサービスが終了すると，そこで利用さ
れていたデータは不要となり使用していたストレージ領域は解放されるべきである．しか
し CFS, ePOST や Ivy など，多くの Content Hash ID に基づく分散ストレージシステム
は不要データに関する削除機構について特別の配慮をしてこなかった．その理由は Content
Hash ID に基づくストレージシステムにおいては複数のアプリケーションが共用している
ストレージシステム内で偶発的に同じデータを記録し，互いにそれを知らずにアプリケー
ションあるいは他のデータから当該データを参照している可能性があるためである．
例えば図 1.1 に示した CFS のデータ構造に存在する data block は，この図に描かれて
いない他の inode block から参照されている可能性がある．典型的な例は複数のファイル
が data block のサイズを越える量の連続した空白 (0x20) を含んでいた場合である．それ
ら複数のファイルは空白だけでできた単一の data block を共用することになる．こうした
場合，あるアプリケーションが停止したからといって，それが参照していたブロックを単
純に削除することはできない．つまりあるアプリケーションから不要になったというだけ
の理由ではデータを削除することができず，そのデータに対して誰からの参照もないこと
を確かめなければならない．
既存のシステムでよく使われている不要データの検出法はリースタイムに基づくもので
ある [13, 34]．つまり全てのデータにリースタイムを設定し，アプリケーションは自身の必
要とするデータに対して継続的にリースタイムを更新し続ける．もしリース期限をすぎて
も更新されないデータがあれば，それはどのアプリケーションからも必要とされないこと
を意味し，削除の対象となる．
しかしリースタイム方式では一般に長い保持期間を設定するため迅速な削除ができない
うえに，リースタイムを更新するために継続的な通信を多数のストレージノードに対して
行う必要がある．ストレージシステムの利用効率を高めるためには，不要になったデータ
を明示的に削除することが可能で，メンテナンスコストが低くストレージシステムに負荷
を掛けないデータ管理手法が必要である．
1.2.5
キャッシュの利用
多くの P2P システムでは，ユーザは要求したデータに到達するまでに何度かのノード間
通信を必要とする．この通信に必要な遅延時間の累積が，ユーザにとってのデータ要求に
対するレスポンスタイムとなる．しかし余りにも遅すぎるレスポンスタイムはアプリケー
第 1 章 序論
10
ションのユーザビリティを悪化させる．つまりこのデータ要求に対するアクセス遅延は可
能な限り短縮することが重要である．
アクセス遅延短縮のための手段としてはアクセスの局所性を考慮したノードやコンテン
ツの配置を行うものもあるが [35–40]，それに加えて Content Hash ID に基づくデータ管
理ではキャッシュの利用が有効と考えられる．
その理由はすべてのデータは書き換えできないため，取得した全てのキャッシュデータは
オリジナルのデータのキャッシュコピーとして期限なく利用可能なためである．また 1.1.1
節の 2) で示したように同じハッシュ関数を用いる限り，別のストレージシステムからデー
タのコピーを持ってきたとしても内容が同じであればその ID は同じである．これは同じ
ハッシュ関数を用いた複数のストレージシステムから取得したキャッシュが，一つのキャッ
シュ管理機構によって共通に管理できることを示している．
しかし CFS, ePOST や Ivy など多くの分散ストレージシステムではそうした性質を活
かしたキャッシュ管理機構は用意されていない．また一般にキャッシュ機構はオリジナル
データに対するアクセス方法や利用傾向などによって最適な管理機構やアクセス手法が異
なる．つまり新しい Content Hash ID に基づく分散データ管理手法を提案する際にはそれ
に適したキャッシュシステムを検討することが重要である．
1.3
研究の目的
これまでに述べたように，Content Hash ID は P2P 的な広域分散環境において高いス
ケーラビリティを得られる性質をもちながら，既存の分散ストレージシステムでの応用に
おいては幾つかの課題を残している．つまり非構造的なデータを ID によって入出力する
だけ，あるいは Read Only のアクセスに限定された用途では問題がないが，構造的なデー
タの管理とその更新を要する応用では常に楽観的更新に由来するデータの更新衝突が生じ，
その修復についてはアプリケーションに依存した解決手段を必要としている．
しかしデータへのアクセスを追記と読み出しのみの WORM タイプに制限し，適用する
アプリケーションを例えば電子メイルをはじめとした並行性のある追記処理の順序を問題
としないメッセージング・サービスなどに限定すれば，楽観的更新に伴う更新処理の衝突
検出や，修復処理などの一貫性管理を必要としないデータ管理方式を設計し得る．
本論文ではこのような追記によるデータ記録法を逐次記録型と呼ぶ．逐次記録型データ
管理システムが解決すべき課題を以下にまとめる．
1) 楽観的更新に由来するデータの更新衝突と，その修復のために生じるストレージシス
テムのアプリケーションに対する依存性の排除
1.4 関連研究
11
2) 不要となったデータの迅速な削除
3) 逐次記録型システムに適したキャッシュ機構
これらの課題を解決するものとして，本論文では逐次記録型のデータ管理方式のひとつ
である WOODS (Write Once Oriented Data management Structure) を提案する．そこ
では更新の衝突が生じず修復処理が必要ないため，従来そのために必要となっていた分散
ストレージシステムに対するアプリケーションの依存性もまた存在しない．そのためアプ
リケーションごとにデータ管理機構を設計しなおす必要がなくなり，開発者は提供すべき
サービスの設計に集中することができる．
本論文ではまた WOODS においてアプリケーションの停止などによって不要となった
データを迅速に，かつ効率良く削除する機構について提案する．具体的には二つの参照カ
ウンタと二つの補助的なタイマーフィールドを組み合わせた新しいデータ管理手法によっ
てこれを実現する．
そして逐次記録型のデータ管理方式で有効に機能しうるキャッシュ機構についても提案
する．具体的には補助的なフィールドを一つ参照カウンタに付け加えてこれを実現する．
WOODS は既存の分散ストレージを利用するために設計されたデータ管理方式であり，
アプリケーションに対して，先に述べた一貫性管理を必要としないストレージへの WORM
タイプのアクセス機能を提供する．WOODS はまた不要データの削除と，キャッシュによ
るアクセス遅延短縮の機能も提供する．そのような汎用で高機能なデータ管理機構を提供
することが本論文の目的である．
1.4
関連研究
本論文が対象とする領域における先行研究について述べる．
CFS
P2P ファイルシステムの一つである CFS は従来的なディレクトリ・ファイルツリーの
イメージを提供する．各データブロックは Content Hash ID によって管理され，その記録
には DHash を用いている．CFS は 基本的に Read Only として設計されており，追加的
な更新などもサポートされていない．
具体的なデータ構造については既に 1.1.3 節に図 1.1 によって示したが，CFS では内部
データが root-block, directory block, inode block, data block と階層的に構成され，より
下位のブロックの Content Hash ID を管理情報として持つことで各ブロックが関連づけ
られている．このため下位のブロック，たとえば data block を更新すると，それより上位
12
第 1 章 序論
のブロックの ID が連鎖的に更新され，最終的には root block を付け直すことになる．そ
のためアプリケーションから見ると CFS は Read Only のファイルシステムであり，一部
データの更新は新しいファイルシステムの提供，すなわちファイルシステムそのものの付
け替えが行われたように見える．
CFS において，データの更新にともなってアプリケーションが最初にアクセスするデー
タの ID が付け替えられる点では WOODS と共通の処理方法をとる．しかし CFS では末端
のデータ更新によって連鎖的に多くの上位ブロックの ID が更新されるのに対し，WOODS
は一つのデータ追記に対して既存のデータの参照関係を変化させることはなく，そのため
のオーバヘッドを生じない．また CFS は単一の更新者すなわち管理者のみが更新処理を
おこなうモデルをとるが，WOODS では複数の更新者が共通のデータ群に対して並行した
追記を行う事が可能である．
Ivy
同じく Content Hash ID をキーとして DHash を用いる Ivy は NFS ライクなサービス
を提供する書き換え可能なファイルシステムである．Ivy はデータを二種類の形式に分け
て保持している．一つはデータの更新情報をログ形式で記録したデータ (log record) であ
り，もう一つはログの内容を統合して得た最新のファイルの状態を示すスナップショット
データである．更新情報を既存の log record に追加するときは，既存の log record の ID
をリンク情報として含む新しい log record を生成して記録する．最新の log record からリ
ンクをたどることで，全ての更新情報にアクセスすることができる．
Ivy は log records 部分に対して更新情報を Write Once な追記によって行う点と，各
log record を Content Hash による ID を用いたリンクで関連づけて管理する点において
WOODS と似るが，ログに追記される更新処理の順序の一貫性を保証するモデルを採って
いるために更新の衝突と修復が生じる点が WOODS とは異なる．またネットワーク分割
後の更新処理のマージでは修復不可能な衝突が発生し，その解決にはユーザの手作業を要
する．WOODS ではネットワークの分割・更新に対して自動的なマージが可能である．
スナップショットデータは図 1.1 に示した CFS のデータ構造と類似した構造をもち，各
データブロックや inode 情報が Content Hash ID によって管理されている．スナップショッ
トデータは CFS と同様に Read Only の従来的なディレクトリ・ファイルツリーのイメー
ジを提供するものであり，その性質もまた末端のデータ更新によって連鎖的に多くの上位
ブロックの ID が更新される点で同じである．CFS との比較で述べたように WOODS は
この連鎖的なオーバヘッドを生じさせない．ただし Ivy では最新のデータ更新情報を先に
述べたログ形式のデータから得るため，一つのデータ更新があるたびにこのスナップショッ
トを作り直す必要が無く，それにともなうオーバヘッドもより低く抑えられている．
1.4 関連研究
13
なお log record およびスナップショットのすべてのデータは Content Hash ID に基づい
たキーによって DHash に保存される．
ePOST
ePOST は分散メッセージング・インフラストラクチャである POST [41] およびその下
層を担う PAST [42–44] 上に構築されたメイル送受信アプリケーションである．メタデー
タの更新情報を Write Once なログの追記によって管理する点は Ivy に似るが，ファイル
システム・イメージを提供するのではなく，独自のデータ構造と管理手法によってメッセー
ジの送受信処理を実現する．
ePOST はネットワーク分割後のメイル送受信も可能にしているが，ネットワークの再結
合に伴う更新ログのマージについてはアプリケーションに依存した処理を必要とし，POST
上の他のアプリケーションとも共通に適用できる解決法は提供されない．
まず ePOST ではデータ管理システムそのものは並行する矛盾した更新に対する耐性を持
つようには設計されていない．その代わりに ePOST はメイルサービスのためのアプリケー
ションであることを利用して更新衝突の発生を回避する設計を採った．具体的には ePOST
ではデータの更新を宛先すなわち受信者となるメイルアドレスごとに隔離して行い，一つ
のメイルボックスに対しては更新者が単一となるよう配置する．つまり single writer モデ
ルをとることで衝突を回避した．
しかしネットワーク分割時に，あるメッセージ受信者が分割された両方のネットワーク
に対して異なる時間に個別に接続して更新を行った場合，その処理はネットワーク再結合
時に衝突する可能性を生じる．そして ePOST の運用経験ではこれを無視できないと結論
して，分割されたログのマージ処理でアプリケーション依存の解決法を導入することで更
新矛盾の自動処理を可能とした．
具体的に起きうる矛盾の例としては，あるメイルを別のフォルダへ移動する処理と，移
動先のフォルダを削除する処理の衝突が挙げられている．この場合 ePOST は矛盾した更
新ログをマージする過程で，メイル処理においては「よりユーザに対して与える不便さが
和らげられる」として削除処理を無視する．これはメイルサービスというアプリケーショ
ンの性質に依存した自動解決法を導入したことを意味しており，同時に解決処理自身には
アプリケーションの介入が必要であることを示している．事実，更新ログはストレージ層
に相当する PAST が管理しているが，ログの内容を解釈することができるのはアプリケー
ション層に相当する ePOST だけであるため，ネットワークの再結合時に PAST がログ
の fork を検出してもその解決を自身で処理することはできず，アプリケーションである
ePOST との連係動作を要する．
すなわち ePOST は衝突した更新の自動解決を可能にしているが，それはアプリケーショ
14
第 1 章 序論
ン依存のものである．WOODS におけるネットワーク分割・更新のマージ処理には個々の
アプリケーションに対する依存性はない．
OceanStore
OceanStore もまた更新可能なサービスを提供するが，それに伴う一貫性維持のために，
高帯域・低遅延な通信環境と高い可用性を構成するノード全体に要求する．それだけでは
拡張性に対する制約が大きくなるため，大規模化のためにネットワークを二層に分け，可
用性の低い周辺層では一貫性の不完全なキャッシュコピーの存在を許すなど，実装が複雑
になっている．また更新衝突の修復に際しては更新要求のシリアライゼーションを行う必
要がある [45]．WOODS は更新衝突に伴う一貫性管理の機構が不要であり，こうした実装
を複雑にする仕組みを必要としない．
Coda
1.2.1 節に示したように，Coda も更新可能なファイルシステムであるが，更新衝突の自
動修復はユーザの手作業による対応を減らすためのものと位置づけられ，完全な自動修復
はできない．具体的には，ディレクトリに対する更新衝突は自動的に修復されるが，ファイ
ルに対する更新衝突はそれを発生させたアプリケーションに依存した方法で処理されるか，
それが不可能な場合はユーザの手作業を要求する．WOODS では更新衝突がなく，ユーザ
の手作業を必要とする修復要求などが生じない．
WheelFS
WheelFS は，分散アプリケーションの実現に際して，それが利用するストレージシステ
ムに対するアプリケーション固有の要求のためにストレージ管理機構を毎回再発明しなけ
ればならないとして，アプリケーション依存性のない再利用可能なファイルシステムを提
案する試みである．
WheelFS において，通常のファイルおよびディレクトリに対するアクセスは，更新衝突
を防いでデータの一貫性を保持するために更新処理に対して責任を持つノードを固定して
処理をシリアライズして実行するアクセス・モードをデフォルトとしている．これでは更
新衝突が防げたとしても大規模広域分散環境ではスケーラビリティを保てず，性能が低下
してしまう．
逆に複数ノードが並行して更新を行うモードでは，性能は維持できるかもしれないが結
果的に並行する更新処理が矛盾を生じさせてしまう．そしてもし衝突した場合，その修復
はファイルシステム固有の方法で行われるためアプリケーションはそれを前提として設計
されなければならない．すなわち，自動修復の妨げとなっていたストレージシステムとア
1.4 関連研究
15
プリケーションの依存関係をなくし，それから生じる問題を解決することはできていない．
WOODS はアプリケーションに依存した一貫性管理などを必要としない．
オブジェクトベースストレージ
非構造的なデータを扱う共有ストレージサービスの一つで，近年になって広まりつつあ
るものにオブジェクトベースストレージがある [46, pp.171-177]．クラウドシステムが実現
する非常に大規模なネットワークサービスにおいては，SAN (Storage Array Network) な
ど従来的なブロックベースのストレージ共有システムは，そのスケーラビリティの限界が
問題となっている．そこでオブジェクトベースストレージは従来的なファイルシステムの
提供をあきらめ，分散処理の手法を取り入れてクラウドシステム向けに特化したストレー
ジサービスを提供するために設計されたものである．その実装例としては Amazon S3 [47]
や EMC Atom などがあり，既に実用化されている．
オブジェクトベースストレージが対象とするのはムービー，グラフィックス，ドキュメ
ントなどの比較的大きな粒度で管理されるデータであり，それらデータはオブジェクト ID
と呼ばれる一意な ID がつけられてフラットなアドレス空間に配置される．オブジェクト
ID は Content Hash によって生成される場合もあるが，それ以外の手法による実装もあり
得る．データへのアクセスはパス名やファイル名を用いる従来的なファイルシステムを通
さず，すべてオブジェクト ID を指定した格納・読み出し処理要求によって行われる．
純粋なオブジェクトベースストレージはデータの部分的な更新に対応しない．そのよう
な更新は異なる ID を持つ別のデータを新しいバージョンとして新規に作成することで対
応する．つまりオブジェクトベースストレージは Content Hash ID と同じく Write Once
指向であり，先に挙げた Freenet や Winny のような単純なファイル共有サービスと同様
に更新衝突を原理的に生じない．それが理由で高いスケーラビリティの実現を第一とする
分野での利用が進んでいるとも言える．
しかしオブジェクト ID を直接用いたキー指定によるデータ取得だけでは，単純なファ
イル共有サービスのような用途にしか利用することができない．それでは実用上の不便が
あるため，一般にオブジェクトベースストレージは多様なデータ検索の機能を持っている．
そのためにシステムは日付やデータサイズ，あるいはユーザが設定した属性データなどを
含んだメタデータを保持しており，これを管理しているメタデータサービスがアプリケー
ションからの検索要求に応じてオブジェクト ID を返すことでデータへのアクセスが行わ
れる．
このメタデータサービスは柔軟な検索を高速に実行する一方でクラウドのような LAN
ベースのクラスタ環境を必要とするものであり，P2P 環境などの広域分散環境でそのまま
この構造を導入することはできない．たとえば Freenet や Winny には広域分散環境で機
第 1 章 序論
16
能するように設計されたキーワードによる検索機能があるが，それらは低速でありまた柔
軟な検索条件を設定することもできない．逆にそうした性能や機能とのトレードオフとし
て大きなスケーラビリティを得ることに成功している．
つまりオブジェクトベースストレージは一般に Content Hash ID を含めたデータ固有
の ID を利用した，高いスケーラビリティをもつストレージシステムであると説明される
が，実際には従来的なデータ検索手法による高速なデータ検索サービスをもつメタデータ
処理によって補強された分散ストレージシステムと考えるべきである．このような Content
Hash ID あるいは Write Once 指向がもつスケーラビリティの高い性質をシステムの一部
に活かした応用は今後も増えていくと考えられる．
対して WOODS はデータの関連づけをデータそのものにリンクを含めることで実現し
ており，拡張性に対する制約となり得るメタデータサービスなどなしに構造的なデータ管
理が可能である．
Cloudy
近年ではクラウド・コンピューティングが普及し，Amazon Web Service (AWS) [48] な
どのクラウド事業者が提供するクラスタシステムによって，容易に大規模な分散システム
を構築することが可能になった．クラウド事業者が提供するシステムは一定の安定した処
理性能が期待できるため，広域に分散した不安定なノードを前提とするような P2P シス
テムの需要の一部はこうしたクラウドシステムに移っていく可能性がある．
ただしクラウドシステムにはその利用に料金が掛かるため，実現すべき分散アプリケー
ションが必要とする性能や安定性とコストのバランスを考慮してクラウドシステムと P2P
システムの適用範囲が決まっていくと考えられる．
Cloudy [49] はそうしたアイディアに基づく研究の一つであり，ノードを事業者が提供す
るクラウド環境と P2P ネットワーク環境の両方に配置して一つのサービスを実現する．運
用時にはそれぞれで稼働するノード数を動的に調整することで利用コストと安定性のバラ
ンスをとることが可能である．WOODS はこのような運用環境にも適用可能であり，むし
ろこうした研究によって WOODS を含めた分散システムの適用範囲は今後さまざまに拡
がっていくと考えられる．
1.5
論文の構成
本論文は序論，本論，結論の 3 編で構成されている．序論では本論文における背景と問
題について述べ，研究の目的を示した．
本論は 3 章に分かれている．
1.5 論文の構成
17
第 2 章では本論文が提案する分散データ管理手法 WOODS (Write Once Oriented Data
management Structure) の基本的な設計を示す．具体的にはチェインと呼ぶデータ構造と，
それによって生み出される WOODS の基本的な性質について述べるとともに，提案する
データ構造とアクセス手法に基づいたメイリングリスト・システムを設計し，それが分散
環境で問題なく動作し得ることを示す．また評価として実際に運用されているメイリング
リストのデータをもとに衝突やその修復処理が必要となる頻度について検討し，それが自
動修復なしの運用が困難と考えられる程度に高いことを示す [50]．
第 3 章では WOODS の基本機構に対して不要となったデータの削除機構を導入する．本
来 WOODS はアーカイブサービスのような削除を必要としない用途を主たる適用領域とし
て設計されているが，それでもサービスそのものの終了などによって不要となったデータ
を削除することは有限のストレージ領域を効率良く利用するためには重要である．具体的
には二つの参照カウンタと二つの補助的なタイマーフィールドを組み合わせた新しいデー
タ管理手法によってこれを実現する [51]．
第 4 章ではキャッシュシステムを実現するための機構について示す．Content Hash ID
ではすべてのデータは書き換えできないため，キャッシュとして取得したデータのコピー
は元のデータとの間に相違を生じさせることがない． また 1.1.1 節の 2) で示したように
同じハッシュ関数を用いる限り，別のストレージシステムにデータのコピーを持ってきた
としてもその ID が変わることは無く，そのまま透過的に利用することが可能である，と
いった優れた性質をもつ．具体的には補助的なフィールドを参照カウンタに追加すること
で，この性質を活かしたキャッシュシステムを実現する [52]．
そして結論で上記の研究結果をまとめる．
19
第2章
WOODS の基本構成
2.1
はじめに
データへのアクセスを WORM なものに制限し，適用するアプリケーションを並行性の
ある追記処理の順序を問題としないものに限定すれば，楽観的更新に伴う更新処理の衝突
検出や，修復処理などの一貫性管理を必要としないデータ管理方式を設計し得る．
本章ではこのようなデータ管理方式のひとつである WOODS の基本的な構成について
述べ，その性質について論じる．WOODS は既存の分散ストレージを利用するために設計
されたデータ管理方式であり，アプリケーションに対して，先に述べた一貫性管理を必要
としないストレージへの WORM タイプのアクセス機能を提供する．そのため WOODS
は図 2.1 に示すようにアプリケーションとストレージシステムの間で機能するミドルウェ
アとして実装される．
Node
図 2.1
Node
システムの構成
WOODS ではデータをリンクによって関係づけ，このリンクによって追記を表現する．
同一のデータに対する並行する追記を，一つのデータに対する複数のデータからのリンク
第 2 章 WOODS の基本構成
20
となるように表現することで，衝突の生じない更新処理を実現する．
また P2P 環境への適性を確認するために提案方式をメイリングリスト・システムに適用
し，それが並行するメイルの受信処理においてアプリケーション間の同期などを必要とせ
ず，ネットワークの分割・再結合にも対応可能であることを示す．
以下，2.2 節で関連研究との比較を行い，2.3 節で提案するデータ管理方式の設計を示し，
2.4 節でその特性について述べる．2.5 節では P2P 環境への適性を確認するために提案方
式を典型的な WORM タイプのアプリケーションのひとつであるメイリングリスト・シス
テムに適用し，2.6 節で提案方式の有効性について考察し，2.7 節で本章をまとめる．
2.2
関連研究
ここでは本章において解決すべき主な課題である楽観的更新にともなって生じる更新の
衝突とその検出・修復処置が他のシステムでどのように行われているか示す．また，本章
の後半で述べる分散処理システムで常に問題となるネットワーク分割・再結合時の処理に
関する他方式との比較を行う．
比較の対象には，複数の writer によるデータの更新が可能なシステムとして Ivy，メッ
セージ処理システムの例として ePOST をとりあげる．
2.2.1
更新の衝突と修復
ePOST はストレージ・システムではなくアプリケーションであるが，ストレージ部分
を担当するものとして POST に基づくメッセージ処理インフラストラクチャを利用して
おり，比較は主としてこの部分について行う．ただし他との機能比較においてアプリケー
ション層で対処する部分もあるため，その場合は ePOST の機能と比較を行う．
Ivy では通常時の更新によって発生する衝突，例えば並行性のある同一のファイルの delete
と rename については，更新時にはその衝突を防げず両方の writer に処理の成功を通知す
る．衝突の検出とその修復は事後に他の writer を含む全てのログをシリアライズして行う．
そのため，アプリケーションは事後に更新結果が異なったものに修復される可能性を考慮
して動作しなければならない．
ePOST ではメイル処理という性質上，通常ひとつの writer が自分のメイルまたはメイ
ルボックスだけを操作するため競合する箇所がない．複数メイルの同時受信処理もアプリ
ケーションレベル・マルチキャストによる通知システムを利用することで更新処理での競
合を避けている．しかしネットワーク分割時には複数の writer が独立に同じメイルボック
スを並行して更新する場合があり，そこでは衝突が発生する．これについては 2.2.3 に後述
する．
2.3 設計
21
WOODS では構造的に衝突する更新が発生しないため，その修復に対する対応などは不
要である．アプリケーションはレコードのチェインへの追記に成功した時点でその結果を
確定として良い．
2.2.2
ネットワーク分割時の書き込み
Ivy, ePOST ともにネットワーク分割時にもデータの書き込みを可能にしている．
WOODS においても分割時のデータの書き込みは可能である．例えば 2.5 節に示すメイ
リングリストシステムの場合，複数用意したリストサーバが一つでも分割されたパーティ
ションに含まれておれば，投稿アプリケーションは新規の投稿が可能であり，閲覧アプリ
ケーションはそうした新規の記事と，分割されたパーティションに残っている既存の記事
のうちチェインをたどれる範囲での閲覧が可能である．
2.2.3
ネットワーク再結合時のデータのマージ
パーティションごとに独立して行われた更新処理は衝突する内容を含んでいる可能性が
あるが，分割されたネットワークの再結合に際してはこれを解決して更新処理やデータの
マージを行い，各パーティションのデータを最新の状態に統合する必要がある．
Ivy では衝突となる更新をチェックするツールが提供され，これを使ってネットワーク再
結合時にデータの修復を行う必要があるが，それにはユーザの判断と手作業を要する．
ePOST では複数の分割されたパーティションで同一のユーザが更新処理を発生させた場
合，ePOST のストレージ部分を扱う POST はそれをネットワーク再結合後に検出するこ
とができる．しかしその修復のための更新ログのマージには ePOST すなわちアプリケー
ションに依存した作業を必要とし，その方法は POST 上で動作する ePOST 以外のアプリ
ケーションにはそのまま適用できない．
WOODS においても再結合時にはアプリケーション層でのチェインのマージ処理が必要
となるが，しかし個々のアプリケーションに依存した処理は不要である．具体的な手順に
ついては 2.5.3 節に示す．
2.3
設計
WOODS は分散ストレージを利用して，アプリケーションにストレージへの WORM タ
イプのアクセス機能を提供するデータ管理方式である．
以下にその設計について説明する．
第 2 章 WOODS の基本構成
22
2.3.1
データ構造
WOODS ではデータをリンクによって構造化する．リンクは単方向であり，追記をデー
タのリンクによって表現する．図 2.2 はリンクによって関連づけられた Ra, Rb, Rc, Rd
の四つのデータを表している．図中の Ra を指す Rb からのリンクはデータ Ra に対する
データ Rb の追記を意味する．
Rd
end
Rc
Rb
Ra
図 2.2
head
基本的なデータ構造
また並行性のある追記はリンクの分岐として表現される．2.3 の例は，データがまず Ra,
Rb の順に記録され，つぎに Rc1, Rc2 が並行に記録された後に，Rd が記録されたことを
示す．
Rd
Rc1
end
Rc2
Rb
Ra
図 2.3
head
分岐するデータ構造
データはすべて 2.4 に示すレコードと呼ぶデータ・フォーマットを用いて記録する．レ
コードは識別子となる ID，ボディ，そしてリンクからなる．本稿ではその ID が a である
データを「レコード Ra」と表記する．
I
B
L1 ... Ln
ID
body
link[s]
I = hash( B , L1 + ... + Ln )
図 2.4
レコードの構造
2.3 設計
23
レコードの識別子となる ID には一般的な Content Hash すなわちボディとリンクを合
わせたものの Hash コードを用いる．
ボディにはアプリケーションが利用する情報を記録する．バイト長を含め，フォーマッ
トはアプリケーションが自由にしてよい．
リンクは対象となるレコードの ID を記録することで表現する．リンクはあってもなく
ても良いし，複数あっても良い．複数あった場合は ID によって昇順となるよう配置する．
WOODS ではリンクによって結ばれたレコードのリストをチェインと呼ぶ．チェインは
まずリンクを持たないレコードを先頭として書き込み，それを指すリンクを持つレコード
を追加する形で，つまり図 2.2 および図 2.3 ではレコード Ra からレコード Rd に向かっ
て成長する．チェインの先頭を head, 末尾を end と呼ぶ．
図 2.5 はレコードを用いてチェインを構成した例である．図 2.5 の左側にグラフの形に
表現したチェインを，右側にレコードのフォーマットで表現したものを示す．
ID
link
Rc
c
... the lazy dog.
b
Rb
b
.. fox jumps over..
a
Ra
a
The quick brown..
in graph
notation
in record format
図 2.5
2.3.2
body
チェインの構造
end record 管理
アプリケーションはその動作に必要な情報の一つとして，現在のチェインの末尾つまり
end record の ID を保持する．これを end point と呼ぶ．end point の情報を失うと，ア
プリケーションはチェインに再びアクセスできなくなる．
図 2.3 におけるレコード Rc1, Rc2 記入時点のように end record が複数存在する場合も
あるため，アプリケーションは複数の end point を管理できなければならない．
2.3.3
ストレージとの関係
本章で述べる WOODS の基本的な機構を実現するために図 2.1 に示した分散ストレー
ジシステム（以後単にストレージ層と表現する）に要求する機能は ID つきデータの記録
第 2 章 WOODS の基本構成
24
と，ID によるデータの参照のみである．そのため，さまざまなタイプの分散ストレージシ
ステムで WOODS データ管理方式が適用できると考えられる．
2.4
特性
まず Content Hash に基づく幾つかの特性について 2.4.1 節に説明したのち，WOODS
に由来する特性について述べる．
2.4.1
Content Hash
良質で充分に大きな空間をもつ Hash 関数を利用することにより，データを書き込むア
プリケーションは衝突を周囲と確認する負担なしに，自身で ID を決定できる．
ストレージ層に ID を示してデータを求めた時，他のノードから提供されたレコードが
正しいものか偽造されたものかを，ID について hash の再計算をすることによりデータ自
身で検証できる．データはレコードのチェインとなるため，さらにリンクをたどるときも
同様にして head record まですべてのデータの正しさを検証できる．
2.4.2
チェインのループ
チェインがループを構成した場合，検索などのチェイン中の全てのレコードをたどる処
理が終了しなくなる可能性が生じる．ループの検出には通過した全てのレコードの ID を
記憶する必要があり，実装上検出可能なリンクの段数には限界があるためである．
しかしどのように複雑なデータ構造ができたとしてもチェインにはループは発生しない．
ただレコードを追加するだけではループが生じないのは自明であるが，意図的にもループ
を発生させることはできない．
まず最も単純なループ，すなわち任意のレコード自身に対するリンクは ID からの逆算，
言い換えれば図 2.4 に示した
I = hash(B, I)
(2.1)
となる ID I とボディ B の組を求められないため，発生させることができない．
任意の n 個のレコードを使ったループを発生させることも同様で，
I = hash(B1 , hash(B2 , ....hash(Bn , I)...)
(2.2)
を満たす ID I と B1 から Bn の複数のボディを逆算することが困難であるため，ループ
を発生させられない．
2.5 適用
2.4.3
25
レコードの Read と Write
データの書き換えは Content Hash による ID の変更を意味するため，レコードは作成
のみが可能であり，書き換えできない．
レコードは更新されることがないため，ストレージ層からレコードを取得した時には無
制限のキャッシュ・コピーが可能である．
レコードの書き込み（作成）では同一 ID のレコードがストレージ層に既に存在してい
た場合でもこれを拒否せず，単に書き込み成功と同一視する．ID は Content Hash によっ
て求められるため，それが同じであることはレコード全体が同一であるためである．アプ
リケーションも新規に作成したつもりのレコードが既存だったかどうかに頓着する必要は
ない．
2.5
適用
電子メイルやチャットなどのメッセージ処理は送受信したメッセージの内容を書き換え
ることはなく，並行して送信された複数のメッセージの受信処理の順が重要でない点で
WOODS に適している．そこで本節では WOODS データ管理方式をメイリングリストを
実現するシステムに適用し，提案方式が問題なく機能し得ることを確認する．
なおメイリングリストを例に用いるのは，WOODS が既存のデータに次々と新しいデー
タを追記する形式のシステムであり，その際に用いた ID が将来にわたって変更されるこ
とがない性質から，新しいメッセージをそのままアーカイブとして蓄積することを前提と
したメイリングリストのような用途に適しているためである．
以下， 2.5.1 節にその概要を説明する．つぎに P2P 環境への適性を確認するために，2.5.2
節では並行するデータの追記においてアプリケーション間の同期を必要とせず，2.5.3 節で
はアプリケーションがネットワーク分割・再結合に対応可能であることを示す．
2.5.1
システム構成
図 2.6 に WOODS を用いてメイリングリストを実現するシステムの構成を示す．シス
テムは受信したメイルをリストとして管理するメイリングリスト・サーバ・アプリケーショ
ン（以後単にリストサーバ）と，メイリングリスト参加者の手元で動作するメイルの投稿
および閲覧アプリケーション，投稿されたメイルを格納・維持する共有ストレージ（スト
レージ層）からなる．リストサーバおよび投稿・閲覧アプリケーションは WOODS データ
管理方式を用いてストレージ層への記録・参照を行う．
投稿アプリケーションは，まずリストサーバと通信しながらストレージ層に記事データ
を記録し，その ID をリストサーバに通知して記事を管理するチェインに加えるよう依頼
第 2 章 WOODS の基本構成
26
list
server(s)
poster
check &
answer
viewer
check &
answer
post
write
access
end point(s)
read
access
messages
storage
system
WOODS data structure
図 2.6
メイリングリストを実現するサンプルアプリケーション
する．閲覧アプリケーションはユーザの操作によって随時リストサーバに最新記事の ID を
問い合わせ，そこからチェインをたどってメイルデータを取得する．
投稿・閲覧アプリケーションとリストサーバは直接通信しながら投稿や最新記事のチェッ
クを行うが，そこで交換されるのはデータの ID 情報のみであり，各アプリケーションの
メイルデータそのものへのアクセスは常にストレージ層に対して行われる．
あるいは投稿アプリケーションとリストサーバが直接通信できることから，リストサー
バが SMTP で投稿者からメイルを受信し，自身でストレージ層に書き込む設計も可能で
ある．しかし本適用例ではリストサーバの負荷を減じるために，分散している投稿側がス
トレージ層に書き込む設計とする．
これによって通常のメイリングリストサーバに集中する記録と各メンバーへの配送の負
荷を減じ，従来的なメイリングリストシステムでは各受信者ごとに蓄積されていた過去の
メイルを共有し，システム全体でのストレージ利用量の削減とリスト・アーカイブの構築
が可能になる．
可用性の向上および負荷分散のために，リストサーバはネットワーク上の異なる場所に
複数用意し，それらが共有するストレージ層にある一つのメイルデータのチェインを管理
する．リストサーバを実行しているホストの選択は通常のメイル配送と同様に DNS の MX
情報に列挙するなどして投稿・閲覧者に行わせるものとする．
2.5.2
並行性のある記録とロック
すべての追記処理要求が順序よく発生する場合に更新に際しての資源競合や一貫性維持
が問題となることがないのは当然であるが，一般にネットワークアプリケーションは処理
2.5 適用
27
が並行に行われる．
WOODS においてもレコードの並行的な追記ではアプリケーションの end point 情報の
更新処理に資源競合が発生し得る．end point の更新は頻繁に発生する処理であり，もし
これが同期処理によって重い負荷を生じさせるようでは現実のアプリケーションに適用で
きない．
以下に並行性のある追記処理について複数の投稿アプリケーションからの同時投稿を例
に検証し，アプリケーション間での同期処理などが必要ないことを示す．なお検討する処
理方法はメイリングリスト・システムに限らず一般的に適用が可能である．
まず単に一通のメイルを投稿，受信する際の処理手順を示す．図 2.7 は投稿アプリケー
ション App A が新しい記事としてレコード Ra を作成し，それをリストサーバ App S が
管理する記事のチェインに加える場合を示している．図 2.7(a) は初期状態であり，リスト
サーバ App S は最後に追加した記事であるレコード Rz を end point として保持している．
この end point 情報を図ではアプリケーションからレコードに対して伸びる矢印によって
示す．レコード間の矢印はリンクを意味する．
App A
App S
App S
App A
App A
Ra
Ra
Rz
Rz
(a)
図 2.7
App S
(b)
Rz
(c)
レコードの追加（左から図 a, b, c）
処理は以下のようにして行われる．
step 1 投稿アプリケーション App A は新しい記事をリストサーバ App S が管理する記
事のチェインの末尾（end）に追記するために，App S に対して現在の end point の
内容を全て返答するよう問い合わせ，z を得る
（以後単に end point を問い，z を得ると表現する）
step 2 App A はメッセージをボディ，z をリンク先とするレコード Ra を生成してスト
レージ層に書き込み，図 2.7(b) の状態となる
step 3 App A は自身の end point の情報 a を App S に伝え，チェインへの追加要求を
行う
step 4 App S は end point をレコード Ra に付け替える
第 2 章 WOODS の基本構成
28
step 5 追加処理が終われば App A はレコード Ra を自身の end point から切り離し，図
2.7(c) の状態となる
この状況ではデータの更新者が一つしか存在しないため，検討すべき競合などはない．
つぎに更新者が複数存在する例として，ほぼ同時に二つの投稿アプリケーションが同じ
リストサーバに投稿処理を行った場合について図 2.8 を用いて説明する．
App S
App A
App B
App S
App A
Rb
Ra
Rb
Ra
Rz
App B
App S
図 2.8
Rb
Ra
Rz
Rz
(b)
(a)
App B
App A
(c)
並行したデータの記録（左から図 a, b, c）
処理は以下のようにして行われる．
step 1 二つの投稿アプリケーション App A, B がリストサーバ App S に end point を問
い，同じ値 z を得る
step 2 取得した end ponit である z をリンク先とするレコード Ra, Rb を App A,B がそ
れぞれ独立に生成し，ストレージ層に書き込む（図 2.8(a) の状態になる）
step 3 App S に対して App A,B がほぼ同時にチェインへの追加要求を行う
step 4 結果，偶発的に App A の要求が先に受理され，App S の end point はレコード
Rz から Ra に変更され，図 2.8(b) の状態になったとする．つぎに App S は App
B の要求にしたがってレコード Rb をチェインに加えようとするが，end point から
レコード Ra を外してレコード Rb に付け替えることはできない．レコード Ra が
チェインから外れてしまうためである．このような場合 App S はレコード Ra を end
point から外さず，単純にレコード Rb を end point に加えることによってレコード
Rb をチェインに取り込めばよい．最終的に図 2.8(c) の状態になる．
step 4 に示したように，end point の付け替えは，新しいレコードを追加する際に既存
のレコードがチェインから外れないように行う必要がある．ここで追加されるレコードが
もつリンク先やアプリケーションの保持する end point が複数であることを意識したうえ
で，step 4 の end point の更新処理の詳細を以下のように整理する．
2.5 適用
29
step 4.0 あるレコード（R）をチェインに追加する要求があれば，
step 4.1 現在のチェインの end point を得る（集合 A とする）
step 4.2 R がもつリンク先情報を得る（集合 B とする）
step 4.3 積集合 P = A ∩ B を求め，
step 4.4 end point に R を加え，P を取り除く
step 4.2 で必要となるため，step 3 では追加すべきレコード，たとえば図 2.7 の Ra の
ID 情報 a だけでなく，そのレコード Ra が内包するリンク先であるレコード Rz の ID 情
報すなわち z を含めて要求依頼を出すものとする．もし依頼元のアプリケーションが信頼
できない場合は，step 4.2 では該当レコードをストレージ層から読み込んでそのリンク情
報を取り出すこともできる．
これまでに示した通り，チェインへのレコードの追記処理においては，競合の可能性が
ある更新処理は end point に対するもののみであり，step 4.4 だけがそれを内包する，排
他的ロックを要する対象となる．その step 4.4 の処理内容はアプリケーション内部のデー
タの書き換えだけであるため，ロックは短時間で済む．
それ以外の step 1∼3 および step 4.1∼4.3 の処理については，アプリケーションは単に
その処理要求が発生した時に実行するだけでよく，またそれらの処理は並行して行われて
も良い．
長時間に及ぶロック処理や，アプリケーション間での同期処理などを必要としないこと
は，ノードやネットワークの信頼性を低く，処理遅延を大きく見積もらざるを得ない P2P
環境に適したものといえる．
2.5.3
チェインのマージ
リストサーバはネットワーク障害時の可用性向上のために複数用意される．複数用意し
たリストサーバは互いに独立に投稿を受けて，チェインに並列に追記を行うが，一定時間
ごとに直接通信して互いの持つ end point 情報を交換することで，全体として一つのチェ
インを新しい状態に維持するものとする．以降この作業をチェインのマージと呼ぶ．
マージは一定時間ごとにしか行われないため，最近の投稿については各リストサーバに
よって閲覧できる記事が異なる場合が生じる．しかしそれらの投稿記事も以後のマージ処
理によって全てのサーバで閲覧可能となる．結果的に，このリストサーバによる閲覧可能
な記事の相違は，閲覧アプリケーションには各サーバでの受信順の違いと認識される．し
かし 2.5 節のはじめに述べたように受信処理の順は重要でないため問題とはならない．
第 2 章 WOODS の基本構成
30
この方法は投稿ごとにその記事の情報を他リストサーバへ通知する方法に較べ，最新状
態の伝達が遅くなる可能性があるが，ネットワーク障害・復旧に際して行うべき処理に同
様の方法で対応できるという利点がある．
以下に故障やネットワーク障害がない正常な状態でのチェインのマージ処理手順につい
て説明し，それがリストサーバ内での短時間のロックのみで実行できることを示す．また
リストサーバの離脱・追加やネットワーク障害によってネットワークの分割や再結合が生じ
た時の処理手順についてもそれぞれ説明し，分割されたネットワークで独立に追記が行わ
れたチェインのマージでも解決できない衝突が発生せず，マージ処理が自動的に完了でき
ることを示す．ただしここで検討する故障や障害は，サーバについては停止故障を，ネッ
トワーク障害についてはサーバの集合が幾つかに分割され，各部分集合内ではサーバ間の
直接通信が可能だが自己の属する部分集合に含まれないサーバとは通信できない状態をそ
れぞれ仮定する．
なおリストサーバの故障は一台だけが分割されたネットワーク分割・再結合と見なせる
ため，同じ手順で処理すれば良い．また検討する各処理方法はメイリングリスト・システ
ムに限らず一般的に適用が可能である．
正常時のマージ処理
具体的なチェインのマージ方法について図 2.9(a) に例を示して説明する．
App S1
a, b
Ra
App S3
a
図 2.9
App S3
z
App S2
(a)
Rb
Rz
(b)
マージ処理の例（左から図 a, b）
存在するリストサーバにはあらかじめ通し番号をつけ，リング状となるよう関係づける．
このリングをマージ処理が巡回することによって，各リストサーバの更新情報が全体に伝
達される．例では三台のリストサーバを想定し，それぞれ App S1, S2, S3 とする．全ての
リストサーバは互いのアドレス等通信に必要な情報を把握しているものとする．
初期状態は全リストサーバの end point が z だったとして，これを各リストサーバは記
憶しておく．その後 App S2 ではレコード Ra，App S3 ではレコード Rb をそれぞれが
保持するチェインの end point である z に対して追記したとする．すなわちこの時点での
2.5 適用
31
各リストサーバのチェインの end record はそれぞれ異なり，App S1 においてはレコード
Rz，App S2 ではレコード Ra，S3 ではレコード Rb である．この状態から App S1 を起
点にトークンを発生させてマージ処理を始める．
App S1 は次のリストサーバである App S2 に App S1 自身の現在の end point である
z を通知する．図 2.9(a) に示した App S1 から App S2 に伸びる矢印の上にある記号 z は
この通知される end point 情報を意味している．この通知がトークンの受け渡しとなって
App S2 のマージ処理が開始される．
App S2 にとって z は初期状態の end point にかつて存在し，現在の end point には存
在しないものである．これは App S2 自身がレコード Rz をリンク先とするレコード Ra
を追記したことによって，Rz は end point には不要となり外したためである．
そこで App S1 のもつチェインと，App S2 のもつチェインをマージするための end point
は，App S1 から取得した z と App S2 の現在の end point の a の集合和である z, a から，
不要となった z を除いた a となる．これを App S2 の新たな end point とし，次のリスト
サーバである App S3 に通知する．この通知によって App S3 でのマージが始まる．同時
に App S2 では初期状態の end point として記憶していた z を破棄し，代わりに最後に次
のリストサーバに通知した end point として a を記憶する．
マージ処理を開始した App S3 での処理手順は App S2 の場合と同様である．一つ前
のリストサーバである App S2 から取得した end point 情報 a と App S3 の現在の end
point である b の集合和 a, b を得る．App S2 同様に不要となった z はそこに含まれない
ため，そのまま a, b が App S3 の新たな end point となる．図 2.9(b) にこのときの状態
を示す．その後 App S3 は App S1 に現在の end point 情報として a, b を通知し，App
S3 は最後に通知した end point として a, b を記憶する．
App S1 のマージ処理では S2, S3 の場合と異なり，初期状態の（あるいは最後に通知し
た）end point である z が現在の end point としてまだ存在しているため，その対処が必
要である．App S1 は前回のマージ処理で次のリストサーバ App S2 に現在の end point
として z を通知したが，それが App S3 から取得した最新の end point である a, b に含
まれていないことから，z はマージ処理が全リストサーバを一巡する間に他のリストサー
バによって不要とされたことがわかる．そこで App S1 では App S3 から取得した a, b と
現在の end point である z の集合和 a, b, z から不要となった z を除いた a, b を新たな
end point とすれば良い．
このようにしてマージ処理はリング状に配置された全てのリストサーバを継続的に巡回
し続ける．これによって各リストサーバはチェインをなるべく新しい状態に維持すること
ができる．もしマージ処理がリングを一周する間に一通も新しい投稿がなかった場合，す
べてのリストサーバは最新の end point 情報を共有することになるが，それ以降も投稿に
第 2 章 WOODS の基本構成
32
備えてトークンの巡回は継続的に行う．
以下に，あるリストサーバアプリケーション App S が行うマージ処理の手順について整
理する．
step 0 各リストサーバは前回のマージ処理で他のリストサーバに通知した end point 集
合（L とする）を記憶しているものとする．
step 1 App S は一つ前のリストサーバから現在の end point の集合（P とする）を受け
取る．
step 2 現在の App S が持つ end point の集合（C とする）と P の集合和をとり，次の
end point 集合の候補（N ）とする．
step 3 L の要素のうち，C に含まれていなかったものがあれば（ App S 自身が追記に
よって不要としたものであるため） N から取り除く．
step 4 L の要素のうち，P に含まれていなかったものがあれば（ App S 以外のリスト
サーバが不要としたものであるため） N から取り除く．
step 5 N を現在の App S 自身の end point とする．
step 6 次のリストサーバに現在の App S 自身の end point の集合を通知し，その内容を
L として記憶する．
step 2 から 5 までの処理を行う間，S はメイルの受信による end point の更新を行わな
いようにロックする必要があるが，処理は end point に関する演算のみであり短時間で完
了する．それ以外の処理の間では受信処理による end point の更新が可能である．
また，メイリングリスト・システムの運用者が望むマージの頻度に応じて，step 5 と 6
の間には待ち時間を設定できる．
リストサーバの離脱と追加
既存のリストサーバ，たとえば図 2.9(a) の S2 が離脱する場合，まず App S2 は新規の
投稿を受け付けない状態にする必要がある．つぎに正常なマージ処理，すなわち 2.5.3 節
における step 1∼6 を実行する際に，自身の前後のサーバ App S1, App S3 に対して両者
が直接接続するようリングの構成変更を指示すれば良い．
新しいリストサーバ（App Sn とする）を加える場合，App Sn は任意の既存サーバ，た
とえば App S1 に対して参加要求を行う．App S1 はまず次回の step 6 の処理の際に App
Sn が App S1 と App S2 の間となるようリングの構成変更を App Sn, S2 に指示し，それ
が完了した後に step 6 を実行する．このとき App S1 は現在の end ponit だけでなく保持
していた L も Sn に通知し，App Sn は受け取った L を自身の L の初期値とする．
2.5 適用
33
ネットワーク分割時の処理
まずネットワーク分割に備えて，あらかじめチェインのマージ処理にはシーケンス番号
を付けておくこととする．すなわち各リストサーバは 2.5.3 節の step 1 の際に前のリスト
サーバからシーケンス番号を受け取り，1 を加えた番号を自己の処理番号として次回のマー
ジ処理に成功するまで記憶しておくものとする．
ネットワーク分割によってトークンの受け渡しができなくなると，トークンを持ってい
る，または一定時間を経てもトークンを貰えなかったリストサーバは他の全てのリストサー
バに通信を試みて分割を確認し，通信可能なリストサーバを集めてリングの再構成を行う．
再構成では各リストサーバを各自が記憶している最後に成功したシーケンス番号で昇順に
並べて，これをリング上の並び順とする．このリング内で最も大きなシーケンス番号をも
つリストサーバが，トークンを発生させ，最も小さなシーケンス番号をもつリストサーバ
に対して 2.5.3 節の step 6 の処理からマージ処理を再開する．
ただしネットワーク再結合によるリングの結合処理のために，各リストサーバは正常状
態で最後に他のリストサーバに通知した end point，すなわち 2.5.3 節の step 6 における
L を結合処理時まで保持しておく．
この一連の処理の間を含めて，各リストサーバは分割されたネットワーク内での投稿を
正常時と同様に受信し続けることができる．
ネットワーク再結合時の処理
ネットワーク分割後，各リングに属する最大の通し番号をもつリストサーバは，自リン
グに属さない他のリストサーバと定期的に通信を試み，ネットワークの再結合を検出する
ものとする．再結合を検出すると全リストサーバ中最大の通し番号をもつリストサーバが
代表となって，分割されたリングの結合処理を開始する．
代表リストサーバは各リングにおける最大の通し番号をもつリストサーバに各リング内
の情報抽出を指示する．指示されたリストサーバはまず自分が属するリングの他のリスト
サーバに新規のメイル受信処理を一旦保留するよう通知し，その状態でチェインのマージ
処理を一巡させてそのリング内のリストサーバに共通となる最新の end point（Npart とす
る）を得る．このとき各リストサーバが保持している，正常状態で最後に他のリストサー
バに通知した end point を集めて，その集合和を求める（Lpart とする）．処理がおわれば
Npart と Lpart を代表リストサーバに通知する．
各リングにおいて Lpart に存在して Npart に含まれない要素があれば，それは分割以
降にそのリングに含まれるいずれかのリストサーバでの追記によって外された end point
（Xpart とする）であることを意味する．この Xpart は分割時には他のリングの end point
第 2 章 WOODS の基本構成
34
に含まれていた可能性があり，それが結合時にもまだ end point に残っている場合がある
が，再結合したリングの各リストサーバが初期値とすべき end point には不要である．再
結合後に用いられる新しい end point は，すべての分割されたリングから集めた Npart の
集合和から，同じくすべての分割されたリングから集めた Xpart の集合和を除いたものと
なる（Nall とする）．
Nall が得られた後，代表リストサーバはすべてのリストサーバを再び一つのリングとな
るよう関係づけ，全リストサーバに Nall を新しい end point として通知し，新規のメイル
受信処理を再開させる．その後，全リストサーバ中最小の通し番号をもつリストサーバに
対してマージ処理を開始することで結合処理は完了する．
2.6
考察
本節では，まず 2.6.1 節で実際に運用されているメイリングリストのデータを用いて，そ
こで発生し得る更新衝突の頻度について検討し，WOODS による衝突・修復処理の回避効
果を確認する．また，2.6.2 節では並行した write のために発生する end point の増大に
ついて検証し，同じくメイリングリストの運用において大きな問題とならないことを確認
する．
2.6.1
衝突頻度
WOODS は更新衝突を生じず，修復処理もないデータ管理方式であるため，他の楽観的
更新モデルに基づく P2P 分散ストレージシステムと比べて効果的に機能するのはそこで発
生する衝突・修復処理の頻度が高い場合である．
以下に実際のメイリングリストのデータを用いて，投稿処理の衝突頻度について検討する．
分析には，比較的投稿が多いメイリングリストのサンプルとして，debian-user メイリン
グリスト [53] を選び，ここに 2007 年 1 月から 2007 年 9 月末までの 9ヶ月間に投稿された
約 3.6 万通のメイルのタイムスタンプを利用する．期間中の一日あたりの投稿数は平均で
133 通，最大数は 382 通である．購読者数はおよそ 2900 程度（2007 年 10 月）で運営さ
れている．
このメイリングリストに対する各投稿の時間差（間隔）の分布について 2.10 に示す．横
軸は次のメイルまでの時間差（秒）を，縦軸はその発生数，つまりその秒差となったケー
スが期間中に何件あったかを示し，打点はタイムスタンプに基づく実際の投稿時間差の分
布を示す1 ．実線は，同期間に同数の投稿がランダムに行われた場合の理論値を示し，以
下のようにして求めた．
1
横軸については紙面の制限から 1000 秒以下についてのみ示す．なお発生数は漸減傾向にあることを確認
している．
2.6 考察
35
Number of incidents
200
timestamps
random
150
100
50
0
0
100 200 300 400 500 600 700 800 900 1000
Interval time of posting [s]
図 2.10
debian-user メイリングリストの投稿間隔分布
投稿の発生がポアソン過程に従うと仮定すると，単位時間中に平均で λ 回発生する事象
が時刻 t より前に k 回発生する確率は次の 2.3 で表される．
Pt (k) =
e−λt (λt)k
k!
(2.3)
時刻 t までに事象が一回以上発生する確率 Q(t) は，k = 0 とした場合，すなわち一回
も事象が発生しない場合の裏であり，
Q(t) = 1 − Pt (0) = 1 − e−λt
(2.4)
となる．時刻 t に一回目の事象が発生する確率密度は 2.4 の t による微分すなわち，
Q0 (t) = e−λt λ
(2.5)
であり，これを用いて理論値を得た．
図 2.10 から短い時間間隔での投稿ほど数が多いことがわかる．理論値も同じ傾向である
が，実際のメイリングリストの方がより短時間に投稿が集中していることがわかる．投稿
者の行動に何らかの集中傾向，たとえば投稿時間帯の偏りなどがあるためと考えられる．
楽観的更新モデルではまず更新を行い，事後にその衝突を確認するため，更新のための
データの write と確認のための read 各一回に要した時間の合計より短い間隔で同一資源に
対する更新要求が発生した場合，それらは並行した更新処理となって衝突および修復処理
が生じる．
第 2 章 WOODS の基本構成
36
このメイリングリストを処理するシステムが，ストレージシステムに DHT に基づくも
のを利用した場合，各一回の write/read に必要な時間は文献 [18, 54–56] などからその中
央値は lookup を含めて 2 秒前後になると推測される．
このメイリングリストにおいて次のメイルまでの時間差が 0 秒，すなわち秒単位のタイ
ムスタンプで同時刻，あるいは 1 秒差となっていたものを合わせると 200 件程であること
から，3.6 万通のうち 200 件前後が衝突する可能性が高いと考えられる．
9 カ月で 200 回の衝突発生は，オペレータの介入を要さない完全な自動修復なしにアプ
リケーションを運用することが困難な値であると考えられる．しかし 1.2.1 節で述べたよ
うに自動修復の一般化は困難であり，アプリケーション依存性が生じてしまうという問題
がある．
同じ 9ヶ月間に 10.7 万通の投稿がある Linux-Kernel メイリングリスト [57] をはじめ，
更新頻度の高いメッセージング・アプリケーションは他にも存在する．従来の DHT を用
いた P2P 向け分散ストレージシステムはこうした更新頻度の高いアプリケーションには適
さなかったが，衝突・修復を生じず，それにともなう問題のない WOODS はこうした分野
への P2P 分散ストレージシステムの適用可能性を広げるものと言える．
2.6.2
end point の増大
チェインの分岐，すなわちアプリケーションが管理すべき end point 数が多くなりすぎ
ると，それがアプリケーションにとって負担となる可能性がある．
2.5.2 節で示したように end point 数は並行する追記によって増える．しかし逆にその後
の並行性の無い状態での追記によって，この増大した end point 数は減少する．
例えば図 2.11(a) はアプリケーション App A, B によるレコード Ra, Rb の並行的な追
記によってサーバ App S の保持する end point が二つに増えた状態を示している．これ以
降に App B によってレコード Rb2 の投稿が並行性の無い状態で行われた場合，レコード
Rb2 は App S がもっていた二つの end point であるレコード Ra, Rb1 をリンク先にもつ
ため，レコード Rb2 の追記後には App S が保持する end point はレコード Rb2 の一つ
だけとなる．
以下に実際のメイリングリストにおけるタイムスタンプを基にしたシミュレーションを
行い，この end point 数の増減について検証する．
比較的投稿が多いメイリングリストのサンプルとして，Linux-Kernel メイリングリスト
を選び，ここに 2006 年 8 月から 2007 年 5 月末までの 10ヶ月間に投稿された約 10.5 万通の
メイルのタイムスタンプを利用して分析する．期間中の一日あたりの投稿数は平均で 345
通，最大数は 763 通である．購読者数はおよそ 4500 程度（2007 年 5 月）で運営されて
いる．
2.6 考察
37
App S
App A
App B
App S
App A
App B
Rb2
Rb1
Ra
Rz
Rz
(a)
図 2.11
Rb1
Ra
(b)
end point の統合（左から図 a, b）
end point の数は投稿の間隔が 2.5.2 に示した step 1 から 4 までの処理時間より長い場
合に増大する．処理時間を上下させる主要な要素を以下に示す．
step 1 投稿アプリケーションによるリストサーバからの end point 情報取得
step 2 投稿アプリケーションによるストレージ層へのデータの書き込み
step 3 投稿アプリケーションからリストサーバ間に対する新 end point 情報の送付
step 4 リストサーバによるストレージ層からのデータの読み出し確認
step 4 のストレージ層からのデータの読み出しは 2.5.2 節で述べたように投稿アプリケー
ションが信頼できない場合にのみ必要となる．今回は条件の悪い場合について検討するた
め，この読み出し処理を含めることにする．
step 1 から 4 までの処理時間のうち支配的となるのはデータのストレージ層への書き込
み，読み出し時間であろう．ストレージ層に適用するストレージシステムによってこの時
間は大きく異なるものと思われるため，step 1 から 4 までの合計処理時間について最大
600 秒までの数通りを設定して end point の数についてシミュレートした．処理と分析を
単純にするために処理時間はどれも一定とする．
なお ID 生成にかかる処理時間は，Pentium 4 CPU 3GHz / Linux kernel 2.6 環境2 で
100KB のデータに対しても SHA-1 や SHA-2（256bit）ダイジェストを 2∼3ms 程度で生
成可能であるため，ここでは問題としない．
表 2.1 に各想定処理時間ごとの最大となった end point 数，図 2.12 に end point 数の
分布を示す．図 2.12 の横軸はメイルの受信が完了した時に必要となった end point の数，
縦軸はその累積的発生率，つまり 10.5 万通の処理のうちその end point 数以下となった割
合を示している．例えば 300 秒の処理時間を仮定した場合，全受信処理の約 70%を end
point 数が 2 以下で処理できたことがわかる．
第 2 章 WOODS の基本構成
38
表 2.1
end point の最大数
Processing time (sec)
10 50
Maximum number of the end points 10 11
1
5
1
10
15
20
100
11
300
21
25
600
32
30
10 sec
50 sec
100 sec
300 sec
600 sec
0.8
0.6
0.4
0.2
0
図 2.12
end point 数の分布 (1)
ハッシュ関数に SHA-2（256bit）を選択した場合でも ID のサイズは 32 バイトである
ため，もし 600 秒の待ちが発生して 32 個の ID 情報を保持，または交換することになっ
たとしても増加するデータ量は 1K バイトにしかならない．また，メイリングリストの投
稿量がサンプルに用いたデータの 10 倍となっても，処理時間 600 秒での最大数は 195 に
とどまることを確認した．図 2.13 にその分布を示す．
1
1
20
40
60
80
100
120
140
160
180
600 sec
0.8
0.6
0.4
0.2
0
図 2.13
end point 数の分布 (2)
以上の事から end point は一時的に増大することがあっても，それがアプリケーションや
ネットワークに過大な負担を掛け続けることなく処理を継続可能であることが確認できた．
2
2007 年の実験当時における比較的高速なシステム．
2.7 まとめ
2.7
39
まとめ
本章では，Write Once Read Many なアクセスモデルをもち，そこで発生する並行性の
ある追記処理の順序を問題としないアプリケーションを対象に，楽観的更新によって生じ
る衝突の検出や修復を必要としないデータ管理方式 WOODS を提案し，その設計と特性
について説明した．
また提案方式をメイリングリスト・システムに適用し，提案方式がデータ共有と更新の
要求を満たしながら，アプリケーション間での同期や長時間のロックを必要しないことを
示した．またアプリケーションが更新の衝突・修復処理を考慮する必要が無く，ネットワー
ク分割後の再結合に際してもアプリケーションに依存した処理を必要とせずに更新結果を
自動的にマージできることを示した．
例に用いたのはメイリングリスト・システムであったが，検討したレコードの追加処理や
チェインのマージ処理などはメイリングリスト・システムに限らない一般的な処理である．
また実際に運用されているメイリングリストのデータをもとに衝突やその修復処理が必
要となる頻度について検証し，それが自動修復なしの運用が困難と考えられる程度に高い
ことを示した．WOODS では衝突や修復処理が生じないため，こうした追記に基づく更新
頻度の高いアプリケーションは WOODS に適した応用領域であると考えられる．
41
第3章
削除機構の設計
3.1
はじめに
従来から，Content Hash ID 機構を用いた分散ストレージシステムの研究では不要になっ
たデータのストレージ領域を解放することへの検討はそれほど行われなかった．先行研究
の多くで用いられているのはリースタイムによる管理である．つまり全てのデータにリー
スタイムを設定し，アプリケーションが自身の必要とするデータに対して継続的にリース
タイムを更新し続ける．もしリース期限をすぎても更新されないデータがあれば，それは
もはやどのアプリケーションからも必要とされないことを意味するため，ストレージを保
持するノードがこれを定期的に検査して削除を行う方式である．
しかしリースタイム方式では一般に長い保持期間を設定するため迅速な削除ができない
うえに，リースタイムを更新するために継続的な通信を多数のストレージノードに対して
行う必要がある．ストレージシステムの利用効率を高めるためには，不要になったデータ
を明示的に削除することが可能で，メンテナンスコストが低くストレージシステムに負荷
を掛けないデータ管理手法が求められている．
この章では，二つの参照カウンターと二つの補助的なタイマーフィールドを組み合わせ
た，新しい不要データの明示的な削除方法について説明する．これによって高コストな手続
きや複数資源の同期的なロックなしに WOODS に削除機能を導入することが可能である．
導入されるデータ管理手法は以下の二つの要件についても満たす必要がある．
(1) アプリケーションの予期しない振る舞い，例えばアプリケーションの異常終了に対す
る頑健性があること．
(2) write や delete に際して追加的に必要となる操作は最小限に抑えられるべきである．
例えば複数ノードに存在する資源に対するネットワーク越しの同期的なロックなどは
すべきでない．
第 3 章 削除機構の設計
42
提案手法の詳細を WOODS に対する具体的な設計として以下に示す．まず 3.2 節で関
連研究における従来的なリースタイムにに基づく管理手法について検討し，3.3 節で提案
するデータ管理方式の設計を示す．続いて 3.4 節で提案方式の有効性について評価し，提
案手法がアーカイブを目的としたシステムに対して，従来的なリース法より効率良く機能
することを示し，3.5 節でこの章全体をまとめる．
3.2
関連研究
Content Hash ID によるリンクつきのデータ構造をもつ分散ストレージシステムを利用
するアプリケーションは幾つも提案されている．1 章の 1.2.1 節で示した CFS や ePOST な
どがそうしたインプリメンテーションの典型的な例である．Ivy もまたそのスナップショッ
トデータのために Content Hash ID に基づくデータ構造を用いている．これらのシステム
は例えば共有ファイルシステムや電子メイルサービスなどインターネットごしに提供され
る大規模な分散アプリケーションを対象として設計されている．
一般にストレージシステムにおいては，参照されなくなったデータは削除が可能であり，
またストレージリソースの有効利用のためにも削除する事が望ましいのは当然である．し
かし上に挙げた Content Hash ID に基づく研究例では，いままで明示的な削除機能につい
て特別の配慮はされてこなかった．
CFS は単純にリースタイムによる管理手法を持つだけである．
ePOST は当初削除の仕組みを持たなかった．日々ユーザが消費するストレージに対す
る必要量を，コンシューマ向けハードディスクの容量増加速度が上回ると考えられたため
である．しかし後の運用では不要となったはずのキー情報管理のためのオーバヘッドが無
視できなくなり，リースタイムによる不要データの削除機構を追加している [20]．
Ivy はストレージ層での削除機能を用意せず，すべてを永続的に保持しつづける．ログ
データ部分については悪意のある参加者やネットワーク分割からの復元に必要であり，ス
ナップショットデータについては Content Hash ID の性質から他の利用者とデータブロッ
クを共有する可能性があることを挙げ，どちらも永続的に保持することとしている [14]．
リース法では，アプリケーションが全ての参照されているデータのリースタイムをリフ
レッシュし続ける．そのために参照がないデータについてはリフレッシュされることがな
く，期限が切れたデータはいつか回収されることになる．
リース法はその単純さにおいてすぐれている．また予期しないアプリケーションの異常
終了に対して，何も特別なリカバリ処理を必要とせずに対応することができる．
しかしながら，リース法は継続的なメンテナンスコストを必要とすることと，そのメン
テナンス処理の効率の低さが問題となる．つまりリフレッシュ処理は参照がない状態にある
3.3 設計
43
データの有無にかかわらず，定期的に繰り返して実行する必要がある．そしてアプリケー
ションの異常終了によって不本意にも参照されているデータが削除されてしまうことを防
ぐために，リースタイムには異常をきたしたアプリケーションを復旧させるのに充分な長
い時間を設定する必要がある．例えば ePOST では一ヶ月が設定されている．
3.3
3.3.1
設計
レコードの削除
WOODS は図 3.1 に示すようにアプリケーションとストレージシステムの間で機能す
るミドルウェアとして実現される．この章で提案する不要データの削除機構はこのミドル
ウェアと各ストレージノード上に用意される管理プロセスの両方に実装される．
図 3.1
システムの構成
図 3.2 に全てのデータが一つのチェインとして格納されているような，WOODS を用い
た単純なアーカイブの構造を示し，これを用いて削除機能の必要性について説明する．
まずレコードがどこからも参照されなくなり，不要なものとして削除が可能になる最も
単純なケースは，アプリケーションが終了してそれまで使用していたチェインそのものが
不要となる場合であろう．図 3.2(a) において，アプリケーション App X が終了し，Rc へ
の参照情報を破棄してしまった場合がこれにあたる．チェインに含まれていたすべてのレ
コード Ra, Rb, Rc はもはやアプリケーション App X からアクセスされる可能性は無く，
すべてが削除の対象となる．
もう一つの削除が可能になるケースはデータの更新である．WOODS は Write Once 指
向でありデータは本来書きかえないことを前提としているが，改訂版となるレコードを新
規に記録してアプリケーションからは新しくなったレコードを参照することでデータの更
第 3 章 削除機構の設計
44
新が可能である．
例えば，図 3.2(a) に，アプリケーション App X がレコード Ra, Rb そして Rc からな
るチェインを保持している状態を示す．ここで アプリケーション App X がレコード Rb
を修正するためには，App X は改訂されたコンテンツをレコード Rb’ として新しく write
し，またレコード Rc と同じデータ・ボディ内容とレコード Rb’ へのリンクをもつレコー
ド Rc’ を write することになる．その後，図 3.2(b) のように App X はその end point を
レコード Rc から Rc’ に付け替えればよい．
図 3.2
レコードの削除
この状況においてレコード Rc は参照がなくなり，削除することが可能である．レコー
ド Rc の削除によって，連鎖反応としてレコード Rb もまた削除可能になる．
しかし上に示した二つのケースともに，各レコードは他のアプリケーションあるいは他
のレコードからも参照されている可能性について考慮しなければならない．つまりそうし
た参照が無く，確実に不要となったデータだけを削除するためにはデータ間の参照状態を
何らかの方法で把握する必要がある．
3.3.2
参照カウンタの拡張
提案手法ではレコード間の参照状態を参照カウンタによって把握する．一般に参照カウ
ンタを用いてデータの参照関係を把握する場合に問題となるのは循環参照に対する処置で
あり，通常はマーク・アンド・スイープ法などの高コストな方法と併用してこれを解決す
る．しかし Content Hash ID を用いたリンクによるデータの参照は常に DAG (Directed
Acyclic Graph) 構造をとり，循環参照が生じることがない．そのため参照カウンタはその
低いメンテナンスコストから WOODS における参照状態の管理に適した手法と言える．
しかし一般的な一つのカウンタからなる参照カウンタは 3.1 節に示した要求をすべて満
たすには不充分であるため，以下のように四つのフィールドをもつ拡張された参照カウン
タを設計した．
3.3 設計
45
1. permanent counter, 他のレコードからの参照を数えるカウンタ
2. end point counter, アプリケーションからの参照を数えるカウンタ
3. lease time, end point counter のリースタイム（有効期間）
4. pending time, 削除処理に対する猶予期間
なお，予期しないカウンタ制御メッセージの喪失などによる問題を防ぐために，幾らか
追加的な操作が必要となる点に注意されたい．例えばアプリケーションにデータとカウン
タの更新処理を一つのトランザクションとして扱わせ，かつロールバック可能な機構を持
たせる，といったことである．しかしながら問題の発生率の低さから，現実の動作環境に
おいてそのためのオーバーヘッドが極端に大きくなることはないと考えられる．
また，提案では図 3.1 に示すように，削除機構を実現するためにストレージ層を構成す
る各ノード上にデータ管理のための管理プロセスを導入する．各ノードが管理するローカ
ルなストレージへのアクセスは全てこの各ノード上の管理プロセスを通して行う．管理プ
ロセスはアプリケーションからの要求に応じてデータの read / write / delete を行うとと
もに，write と delete によって発生する参照カウンタの更新を行う．
3.3.3
Lease time フィールド
この節では Lease time フィールドによるアプリケーションの異常終了対応について説明
する．
まずアプリケーションが異常終了したとしても，そのアプリケーションが end point の
参照状態を正しく復旧する限りにおいては何も問題はない．しかしそれができなかった場
合，つまり異常終了の直前にはあるレコードを参照していたが異常終了によってその情報
が失われてしまった場合には，過去に end point から参照されていたレコードの参照カウ
ントを正しく減じる機会がなくなってしまう．その結果，参照されていたレコードはスト
レージシステムの中に永続的に残ることになる．
従来的な単一の参照カウンタを用いたのでは，この問題を正しく処理することはできな
い．そこでアプリケーションからの参照については，それ以外の参照とは別に end point
counter に数えることにする．そして各レコードの end point counter にはアプリケーショ
ンの異常終了に備えて有効期限を設定し，これを lease time フィールドに記録する．その
後，アプリケーションは end point から参照するレコードの lease time フィールドを定期
的に延長する．
上に述べたそれ以外の参照とはつまり他のレコードからの参照を意味するが，これは
permanent counter に数える．この permanent counter はアプリケーションの振る舞いに
よって参照状態が影響される事はないため，ここに有効期限を設定する必要はない．
第 3 章 削除機構の設計
46
この方法はリースタイムによる有効期限を設定する点では一般的なリースタイムによる
データ管理方法と同じであるが，end point counter を用いる事によってアプリケーショ
ンが正常に実行されている状況では不要になったデータが即座に削除できる点において優
れている．つまりもしアプリケーションが参照をあるレコードから外した場合，end point
counter は減算され，もし end point counter と permanent counter が共にゼロとなった
場合はそのレコードは即座に削除することが可能である．
（ただし 3.3.4 節で示す pending
time について考慮する必要がある．
）
もしアプリケーションが異常終了し，そのレコードがそれ以外のアプリケーションから
参照されていなかった場合，lease time はもはやアップデートされることがない．そのう
ちにこの lease time の期限をすぎると，各ストレージノードの管理プロセスが当該レコー
ドの end point counter の値をゼロに設定する．このときもし permanent counter もまた
ゼロであった場合はそのレコードは管理プロセスによって自律的に削除されることになる．
3.3.4
Pending time フィールド
この節では Pending time フィールドによる非同期的な参照カウンタの加減算処理につ
いて説明する．
WOODS における典型的なレコードの追加処理を図 3.3 に示す．図 3.3(a) に示すよう
に，まずレコード Ra, Rb からなるチェインがあり，アプリケーション App X は end point
としてその末尾のレコード Rb を参照している．ここでレコード Rc をチェインに追加す
るために，App X はレコード Rb をリンクにもつレコード Rc を write し，その後 App
X は図 3.3(b) のように end point の参照先をレコード Rb からレコード Rc に変更する．
図 3.3
レコードの追加処理（左から図 a, b）
レコード Rc の write はレコード Rb の permanent counter を加算する．そしてアプリ
ケーション App X の参照先変更はレコード Rb の end point counter の減算と，レコード
Rc の end point counter の加算を行う．これらの加減算処理は複数ノードに対する同期的
3.4 評価
47
なロックを避けるために非同期に行われる．しかしもしこの加減算処理の順序が入れ替わ
り，Rb に対する減算処理が加算処理より先に行われた場合，Rb の permanent counter と
end point counter の合計が一時的にゼロになってしまい，予期せず管理プロセスによって
削除されてしまう可能性が生じる．
この問題に対する完全な解決策はメッセージの配送順序が保証される環境を提供するこ
とであるが，それを実現するためのコストは一般に大きなものとなる [58]．そこで本論文
では pending time フィールドを参照カウンタに追加してこの問題をシンプルに解決する．
つまりメッセージ配送の遅延によって問題が出るような参照状態の変更をアプリケーショ
ンが行う場合，アプリケーションは非参照状態になるレコードの pending time を設定す
る．そして管理プロセスは，もし permanent counter と end point counter の合計カウン
トがゼロになったレコードを発見した場合でも，pending time が設定されていた場合はそ
の時刻をすぎるまで削除処理を待つものとする．なお pending time は遅延に対応するため
の十分な時間を設定する必要があるが，その時間は従来的なリースタイム法におけるリー
ス時間に較べると極めて短いもので済む．
3.4
評価
評価として，提案手法と従来的なリースタイムによる管理手法におけるメンテナンスコ
ストの比較を行う．シミュレーションには Debian users mailing list に 2012 年の 2 月から
11 月に投稿された約 20,000 メッセージを利用した．図 3.4 は，全てのメッセージをアー
カイブするとした場合の，日ごとのメンテナンスのための通信回数を示す．
予期せず終了したアプリケーションが復旧するための猶予期間として 30 日を確保する
ために，シミュレーションでは 30 日ごとに 60 日のリースタイムを設定するものとした．
伝統的なリースタイムによる管理では日ごとの通信量は最初の投稿から 30 日を過ぎて以
降，アーカイブしたメッセージの増加に伴って累積的に増えていく．対照的に提案手法は
3.3.4 に示したとおり各メッセージの投稿に対して 3 つのカウンタ制御メッセージが必要
となるものの，アーカイブしたメッセージの総量とともに通信量が増えることはない．シ
ミュレーションでは日ごとの通信量において 120 日を経過する頃から提案手法の方が従来
手法より少なくなっており，特にアーカイブ処理などにおいて提案手法が効率良く機能す
る事を示している．
3.5
まとめ
この章では拡張された参照カウンタによってレコードの参照関係を把握し，不要となっ
たレコードを削除する手法について提案した．この機構はアプリケーションの異常終了に
281
261
241
221
201
181
161
141
121
81
101
61
41
21
1
図 3.4
301
第 3 章 削除機構の設計
48
一日あたりのメンテナンスのためのメッセージ数
対応しながら，WOODS に不要データの削除機能を導入するものである．
提案手法が機能するために必要な要件はデータが DAG 構造に基づくことと，アーカイ
ブなど長期的なデータ保持を対象とした処理であることだけである．そのためこの機構は
Content Hash ID に基づく他のアーカイブシステムにも適用が可能であると考えられる．
49
第4章
キャッシュ機構の設計
4.1
はじめに
1 章の 1.2.1 節で示した CFS や ePOST, Ivy をはじめとした Content Hash ID による
リンクつきのデータ構造をもつシステムでは，ユーザは要求したデータに到達するまでに
幾つかのリンクをたどる必要がある．
このようなシステムにおいてユーザがデータに対するアクセス要求を出すと，管理シス
テム上で動作しているアプリケーションは複数のリンクを段階的にたどって要求されたデー
タに到達することになる．ユーザにとってはこのそれぞれのリンクを追跡するために必要
な遅延時間の累積が，データ要求に対するレスポンスタイムとなる．しかし余りにも遅す
ぎるレスポンスタイムはアプリケーションのユーザビリティを悪くしてしまう．特に上に
挙げた CFS, ePOST, Ivy そして WOODS 自身が前提とするような分散ストレージシステ
ムに対するアクセスは低速である場合も少なくないため，この遅延時間の累積は大きな問
題となる可能性がある．
あり得る解決法の一つはキャッシュシステムをユーザ近くのサイトに構築し，個々のリ
ンク追跡処理のアクセス時間を短縮することである．キャッシュシステムはある利用者の
データ要求のレスポンスタイム短縮に貢献するだけでなく，キャッシュしたデータを同一サ
イトにいる他の利用者とも共有することで，サイト全体の利用者のユーザビリティを向上
することが可能である．またオリジナルのデータを管理・提供しているシステムへのデー
タ要求トラフィックを減じる効果もある．
また，Content Hash ID を用いる場合，同じハッシュ関数を利用している限り内容が同
じデータは必ず同じ ID をもつ．そのため，もし複数のサービスサイトから同一の ID を
もつデータを取得するような場面が生じたとすると，それは同じ内容のデータであること
を意味する．この場合，取得したキャッシュデータはそのいずれのサイトに対するデータ要
求に対しても利用可能である．つまりキャッシュ対象となるデータがどこから来たのかと
第 4 章 キャッシュ機構の設計
50
関係なく，一つのキャッシュシステムでそれら複数のオリジナルサイトに対するキャッシュ
データをまとめて管理する事が可能である．
同様に，もしキャッシュシステムがキャッシュデータの保存先として，同じハッシュ関
数を利用した Content Hash ID に基づくローカルなストレージシステムを利用した場合，
キャッシュデータは他のサービスのオリジナルデータと共存させることが可能である．そ
の際にもキャッシュシステムの利用者からアクセス要求のあったあるデータがローカルス
トレージ内でヒットした場合，それが本来アクセスするはずだったオリジナルのサービス
から取得したキャッシュデータだったのか，偶然にもストレージシステムを共有していた
別のサービスがたまたまオリジナルのデータとして作成したものだったのかを意識する必
要は無い．
この性質はキャッシュ機構のために限りあるストレージ領域を効率良く利用するために
役立つ．それにしてもストレージ領域には上限があるため，不要になった，あるいは重要
度の低いキャッシュデータの削除機構は必要である．
こうした要件を満たすために，設計するキャッシュ管理システムは以下の二つの要求を
満たさなければならない．
1. データ全体のうち，最後に追加されたデータから，ある範囲までの古いデータだけを
部分的に保持することになるが，この範囲は利用可能なストレージ領域の変化に対応
して任意の時点で調整可能であること．
2. 削除対象となったレコードと他のレコードおよびアプリケーションとの参照関係につ
いて把握し，それがキャッシュ管理システム以外から参照されていないことを確実に
できること．
この章では，Content Hash ID に基づく分散ストレージシステムの一つである WOODS
に導入するためのキャッシュシステムを設計する．しかし現在のところ，WOODS のよう
なチェインタイプのデータ構造に適用可能なキャッシュ管理機構はない．そこで以下に新
しく拡張された参照カウンタに基づくキャッシュ管理機構を提案する．提案手法の詳細は
WOODS に対する具体的な設計として示す．
まず 4.2 節で関連する他の研究について示す．次にキャッシュ管理機構の振る舞いについ
て 4.3 節で示し，それに対する要求を満たすために必要な参照カウンタに対する拡張につ
いて 4.4 節で説明する．そして 4.5 節で Gnutella に対する query データを用いたシミュ
レーションによって提案手法の有効性を評価する．
4.2 関連研究
4.2
51
関連研究
3 章の 3.2 節で述べたように，CFS, ePOST や Ivy など，多くの Content Hash ID に
基づく分散ストレージシステムは不要データに関する削除機構について特別の配慮をして
こなかった．よく使われているのはリースタイムに基づく手法であるが，リースタイム法
はその単純さにおいてすぐれており，予期しないアプリケーションの異常終了に対して特
別なリカバリ処理を必要とせずに対応することができる一方で，迅速な不要データの削除
ができないこととリースタイム更新のための通信が継続的に必要となる点が問題である．
もちろんリースタイムに充分に長い時間を設定することによって，このメンテナンスの
ための通信を削減することは可能である．例えば ePOST ではリースタイムを一ヶ月に設
定しているが，しかしこのような長い遅延時間は不要なデータをそれだけ長くストレージ
に保持することを意味し，キャッシュの利用効率を低下させてしまう．また固定的なリー
スタイムによる管理では，ストレージ領域の残量変化などに対してキャッシュの使用量を
迅速に変化させて対応することができない．
それに対して提案する手法は参照カウンタに基づくものであり，このような問題が生じ
ない．カウンタは参照状態が変化したときに加減算すれば良いだけなので管理のためのメ
ンテナンスコストは低く，不要なデータはカウンタがゼロになったときに即時に削除する
ことが可能であるため，アーカイブシステムに適した方法であると言える．
参照カウンタに基づく分散システム上で機能するガベージコレクション・アルゴリズム
として，Weighted Reference Counting [59] などが存在する．しかしそれらはあるオブジェ
クトを作成したか，あるいは現在参照しているプロセスが，そのオブジェクトを新たに参
照したいと要求する他のプロセスにオブジェクト ID などの参照情報を渡すことを前提と
して設計されている [58–62]．しかし Content Hash ID に基づくシステムでは，複数のア
プリケーションが互いに連絡をとらず，独立に同一のデータを作成，あるいは参照するこ
とがあり得る．そのため Weighted Reference Counting あるいはその他の既存のアルゴリ
ズムをそのまま適用することができない．
提案する拡張参照カウンタはある種のプレースホルダーとして振る舞い，例えばまだス
トレージに書かれていないデータに対する参照処理を取り扱うことを可能にする．参照カウ
ンタを用いた一般的な分散ガベージコレクションのアルゴリズム，たとえば Plainfossé [60]
などもまたプレースホルダーとしてスタブを利用している．しかしスタブはリモートノー
ドに存在するデータの参照数との一貫性を維持するために用いられる．それに対して提案
する拡張参照カウンタはローカルノードのデータについて，しかしそのデータがまだ存在
しないときに発生する参照要求を処理するために用い，それによって参照数の一貫性を維
持するものであり，この点で異なる．
第 4 章 キャッシュ機構の設計
52
キャッシュのための戦略もまたキャッシュシステムの利用効率にとって重要である．典型
的なコンテンツのキャッシュ機構は，一つのコンテンツごとに一つのキャッシュコピーを作
成するものである．しかしながらある種のアプリケーションにおいては複数のコンテンツ
をキャッシュすることによってキャッシュの効率が高まる場合がある．例えばメイリングリ
ストのアーカイブシステムは Content Hash ID によるシステムの主たるアプリケーション
の一つであるが，一度あるメッセージが参照された場合，そのメッセージを参照する幾つ
かのメッセージは次に読まれる可能性がある．なぜならメッセージは時系列に並んでおり，
そのメッセージの並びは類似した話題を含んでいる傾向があるためである．そのため，そ
うしたシステムでは参照された単一のメッセージだけでなく一連のメッセージをキャッシュ
するほうが後のヒット率が高くなることが考えられる．これらの理由から，ここでは単一
のデータの代わりに一連のデータをキャッシュする手法について検討する．
4.3
キャッシュの手法
WOODS において，すべてのレコードは書き換えできない．このことはストレージシス
テムから取得した全てのレコードは，オリジナルのレコードのキャッシュコピーとして期
限なく利用可能であることを意味する．この節では WOODS における適切なキャッシュ方
法と，キャッシュされたデータの管理方法に対する要求について説明する．
4.3.1
基本的なデータの読み込み
WOODS はリンクされたデータ構造をもつ分散ストレージシステムの上で実行されてい
る．ユーザがあるデータに対するアクセス要求を出した時，WOODS 上のアプリケーショ
ンは要求されたデータに到達するために複数のリンクをたどる必要がある．それぞれのリ
ンクを追跡するためにかかった遅延時間は蓄積され，それをユーザは待たなければならな
い．余りにも遅すぎるレスポンスタイムはアプリケーションのユーザビリティを悪くして
しまう．
以下，図 4.1 に例を示しながら，典型的なアプリケーションのデータへの read アクセ
ス手順を説明し，具体的にどのようにしてリンクをたどりながらアプリケーションがデー
タに到達するのかを説明する．
まずビュワーアプリケーション App V は，たとえばアプリケーション App S によって
アーカイブされたメイリングリストのデータであるチェインを参照しているとする．この
場合にアプリケーションがレコード Rb を読むために必要となる処理の手順を以下に示す．
1. App V から App S に対して現在の end point について問い合わせを送る．App S
は “Rc” だと返答する．
4.3 キャッシュの手法
53
図 4.1
Read アクセス
2. App V からストレージシステムに対してキー “Rc” のデータの取得要求を送り，レ
コード Rc を得る．
3. App V は取得したレコード Rc に含まれるリンク情報 “Rb” を取り出し，レコード
Rb に対して 2) で示したのと同じ手順で Rb を取得する．
つまりアプリケーションがレコード Rb を取得するためには，レコード Rc, Rb を参照
するリンクをたどる必要があった．
なお，上に示したように，アプリケーション App S は初めに保持するチェインの end
point をクライアントアプリケーションに対して通知するだけである．それ以降の全ての
データ読み取りはクライアントアプリケーション App V とストレージシステムの間で処理
される．これは多くのクライアントが短い時間範囲で同時に実行されていた場合でもサー
バーアプリケーションの負荷を低く維持することに役立つ．
4.3.2
プロアクティブ・キャッシュ
ここに二つの WOODS システムがあったとする．一つはグローバルなサービスを広域
に分散したストレージノードによって提供している．もう一つはユーザのローカルサイト
で実行される，内部利用向けのものである．以後，この二つをグローバル WOODS とロー
カル WOODS と呼ぶ．
例えば，グローバル WOODS のサーバアプリケーションがメイリングリストのアーカイ
ブを構築し，公開していたとする．そのサーバアプリケーションは投稿があるたびにメッ
セージをアーカイブのチェインに追加する．ユーザがこれを閲覧するためのアプリケーショ
ンを起動した場合，閲覧アプリケーションはリンクを順にたどってチェインから最近に投
稿された未読のメッセージ群を取得する．もしチェインにそのユーザにとって未読のメッ
第 4 章 キャッシュ機構の設計
54
セージが 100 通含まれていた場合，ユーザはまず最も古い未読のメッセージから読みたく
なるだろう．そのためユーザは 100 個のメッセージを読むための遅延時間の累積ぶんだけ
待たなければならない．
しかしもしそのユーザのサイトにローカル WOODS があれば，それをキャッシュとして
利用することが可能である．そしてもしプロアクティブなキャッシュシステムがそのロー
カル WOODS で動作しておれば，それは一連のメッセージを取得するための遅延を低減
することができる．さらに，キャッシュされたレコードは同じサイトにいる他のユーザと
共有することも可能である．これはまたオリジナルのコンテンツを保持しているグローバ
ル WOODS に対するトラフィックも削減する．
図 4.2
二つの WOODS 空間
そのような状況を図 4.2 に示す．サーバアプリケーション App S はメイリングリストの
チェインをグローバル WOODS に保持している．キャッシュコントローラ Cont. C と，閲
覧アプリケーション App V はともに同じ LAN 内にあるローカル WOODS システム上で
実行されている．コントローラ Cont. C は最近のレコードを App S に定期的に問い合わ
せる．もしキャッシュコントローラ Cont. C がメイリングリストに対する新しい投稿を検
出すると，Cont. C はそのコピーをローカル WOODS 上に作成する．閲覧アプリケーショ
ン App V は起動するとキャッシュコントローラ Cont. C に最新のレコードを問い合わせ
る．このときコントローラ Cont. C はレコード Rc の ID を答え，アプリケーション App
V はレコード Rc をローカル WOODS から取得する．
ストレージ容量の限界から，キャッシュコントローラ Cont. C はオリジナル・チェインに
含まれる全てのレコードをコピーすることができないかもしれない．そのような場合，つ
まりもし閲覧アプリケーション App V からのローカル WOODS に対するレコードの読
み出し要求が，そのレコードが存在しないために失敗した場合，WOODS ミドルウェアは
4.3 キャッシュの手法
55
コントローラ Cont. C に対してグローバル WOODS からレコードを取得するように依頼
する．結果として閲覧アプリケーション App V は透過的にデータを取得する事が可能で
ある．
4.3.3
キャッシュ管理手法への要求
Content Hash ID に基づくデータ管理システムにおいてはデータの内容が書き替えられ
ることはないため，ストレージシステムから取得した全てのレコードは，オリジナルのレ
コードのキャッシュコピーとして期限なく利用可能である．しかしストレージ領域には限
りがあるため，キャッシュコントローラは不要な，あるいは重要性の低いキャッシュを積極
的に削除する必要がある．
4.1 節で述べたように，本論文では単一のデータをキャッシュするのではなく一連のデー
タをキャッシュする方針を採る．ここでは WOODS における各データアクセスの強い相関
について示す．例えば 4.3.1 節で説明したように，もし App V が図 4.1 のレコード Ra を
読もうとしたとき，App V はレコード Rc と Rb をそれに先んじて読まなければならない．
すなわち WOODS においてはチェインを部分的に，それもチェインの end point から先頭
に向かってある範囲についてキャッシュすることが適切である．また，その範囲は利用で
きるストレージ量に合わせていつでも調整可能でなければならない．
図 4.3
チェインの共有
Content Hash ID に基づくデータ管理システムにおいては，複数のアプリケーションが
偶然に一つのチェインをシェアしている場合について考慮が必要である．図 4.3(a) はその
ような状況を示している．キャッシュコントローラ Cont. C とアプリケーション App X は
それぞれが自分のチェインを保持しているが，レコード Ra についてはその両方のチェイ
ンから参照されている．
このような状況が発生する典型的なシナリオについて説明する．まずキャッシュコント
ローラ Cont. C はグローバル WOODS からレコード Ra を取得し，キャッシュしていた
とする．しかしレコード Ra が有名な楽曲の歌詞など，とてもポピュラーなコンテンツ
第 4 章 キャッシュ機構の設計
56
だった場合などでは，アプリケーション App X が完全に同じ内容のデータをコントロー
ラ Cont. C とまったく無関係に後から書き込むことが起き得る．
結果的にレコード Ra は二つのチェインから共有されることになり，そのためどちらか
一方から不要になったというだけの理由では削除する事が認められない．図 4.3(b) はその
単純な例を示している．キャッシュコントローラ Cont. C はキャッシュサービスを終了し，
チェインに対する参照を取り外したとする．レコード Rc と Rb はコントローラ Cont. C
に由来する参照しかもたず Cont. C の終了とともに不要になったため削除が可能である．
しかしレコード Ra はまだ App X からの参照があるため削除されてはならない．このよ
うな参照関係を検出するため，キャッシュ管理システムはレコードとアプリケーションに
ついてその参照関係を把握する必要がある．
ここで 4.1 節で示した，この章で設計するキャッシュ管理機構が満たすべき二つの要件
を，より具体的な表現で再提示する．
1. end point から先頭方向に向かって，ある範囲に限定した部分的なチェインのキャッ
シュを保持でき，またその範囲についてはキャッシュ使用量の限界に合わせていつ
でも調整可能であること
2. キャッシュ管理システムからの参照しかもたないデータだけを削除するために，ア
プリケーションとレコードの参照関係を完全に把握できること
LRU などの一般的なキャッシュ管理アルゴリズムは上に示したような参照関係を扱うこ
とができないため，それらの一般的なアルゴリズムをそのまま変更無しに適用することは
できない．
4.4
参照カウンタの拡張
ここでは 4.3 節で議論した要求を満たす，参照カウンタに基づくキャッシュ管理手法に
ついて提案する．参照カウンタを利用するのは 3 章の 3.3.2 節に述べたとおり，Content
Hash ID によるデータのリンクは常に DAG (Directed Acyclic Graph) タイプのデータ構
造を構成するが，このような場合には参照カウンタがメンテナンスコストの低い手法とし
て適用可能であるためである．
なお参照カウンタの加減算は 3 章における提案と同じく，アプリケーションではなく対
象レコードを保持しているストレージノードの管理プロセスが行うものとする．
4.4.1
不完全なチェインの処理
まず標準的な参照カウンタによる管理手法について説明する．例えば図 4.3(b) に示すよ
うに，キャッシュコントローラ Cont. C がサービスを終了し，レコード Rc への参照を取
4.4 参照カウンタの拡張
57
り外したとする．このとき Rc の参照数はゼロになり，Rc は削除可能な状態になる．レ
コード Rc がストレージシステムの管理プロセスによって削除されると，レコード Rb の
参照カウンタが減算されてゼロになる．そしてレコード Rb がまた削除されると，レコー
ド Ra の参照数もまた 2 から 1 に減算される．レコード Ra の参照数は引き続きゼロでは
ないため，こちらは正しく削除されない．
しかし標準的な参照カウンタは，4.3.3 節の 1) で示した条件を満たさない．つまり部分
的なチェインを正しく保持することができない．
一般にキャッシュシステムはストレージ領域の制約によって，オリジナルデータの部分
的なコピーを持っている．
図 4.4
不完全なチェイン
図 4.4(a) にそのような状況を示す．つまりキャッシュコントローラ Cont. C はレコード
Ra, Rb と Rc からなるチェインのうち，最近に追加されたレコードである Rc と Rb だ
けをコピーしている．この部分的なチェインにおいて，レコード Rb はローカル WOODS
内には存在しないレコード Ra へのリンクをもっている．一般的な参照カウンタはこのよ
うな不完全な参照状態を処理することができない．
この節では拡張された参照カウンタによってこの問題を解決する方法を示す．
具体的には参照数だけでなく，データの存在状態を表現する項目 data existence を参照
カウンタに追加することで，参照カウンタ自身を存在しないレコードのプレースホルダー
として機能させる．
以下に詳細な設計と，それがどのように機能するかを説明する．
4.4.2
存在しないレコードのカウント
一般的な参照カウンタによる手法においては，参照管理システムは存在するデータに対
する加減算を前提としていた．そのため図 4.4(a) に示したレコード Ra のような，存在し
ないデータに対する参照数を更新することができない．また Content Hash ID に基づくシ
ステムでは，既に 4.3.3 節で述べたように複数のアプリケーションが独立に同じデータを
第 4 章 キャッシュ機構の設計
58
write する場合がある．これが不完全なチェイン状態で起きた場合，正しく参照数をカウ
ント出来ない状況が生じる．
つまり図 4.4(a), (b) に示すように，まず不完全なチェインが存在し，レコード Rb はレ
コード Ra に対する参照を内包してストレージに存在しているが，参照先であるレコード
Ra そのものは存在しなかったとする．この状態でアプリケーション X がレコード Ra を
write すると，Ra の参照数は 1 にセットされる．しかし実際には Ra には Rb からの参照
があるため，その参照数は 2 になるべきである．
この誤ったカウント処理の結果，もしキャッシュコントローラ Cont. C がサービスをや
めて end point の参照をレコード Rc から取り外した場合，連鎖的な削除処理の結果とし
てレコード Ra もまた削除されてしまう．
この問題を解決するために新しく data existence フィールドを参照カウンタに追加する．
この data existence フィールドはレコードの存在状態を表しており，二つの値を持つ．一
つは通常の状態を意味する actual であり，参照カウンタとレコードそのものがともにスト
レージに存在することを示す．もう一つは provisional であり，こちらは参照カウンタは存
在するが，それに対応するレコードそのものがストレージに存在しない状態であることを
示す．
例えば図 4.4(a) では，キャッシュコントローラ Cont. C がレコード Rb を write すると，
レコード Ra の参照カウンタにに対して加算命令が発行される．通常の状態であればレコー
ド Ra を保持しているストレージノード上の管理プロセスは単に Ra の参照カウントを加
算するだけで良い．しかしもしレコード Ra が存在しなかった場合，管理プロセスはまず
レコード Ra のリファレンスカウンタだけを参照数ゼロとして作成し，その data existene
を provisional にセットする．その後受け取った加算命令を反映して参照数は 1 となる．
図 4.4(b) に示したように，もしいずれかのアプリケーションがレコード Ra を後で write
した場合，管理プロセスはレコード Ra を実体としてストレージに書き込み，その参照数
を 1 から 2 に変化させ，data existence を actual に書き替える．
これで最終的にレコード Ra の参照数は正しく 2 とすることができる．
4.4.3
チェイン途中にあるレコードの削除
チェインにおける不完全な参照状態は，チェインの途中にあるレコードを削除すること
によっても生じる．例えばあるメイリングリストについて，運営を開始した 1990 年から
今日までの完全なキャッシュコピーがあったとする．ここでキャッシュ管理システムがこの
キャッシュ範囲を 2000 年以降のものに短縮しようとした場合，その作業ではチェインの途
中から先頭までのレコードを削除することになる．
図 4.5 は中間に存在していたレコード Rb の削除について示しており，結果的にレコード
4.4 参照カウンタの拡張
59
(c)
図 4.5
チェイン途中にあるレコードの削除
Rc からレコード Rb への参照は不完全な状態になっている．しかし data existence フィー
ルドは，このような状況もまた正しく扱う事ができる．
キャッシュコントローラがレコード Rb のように参照数ゼロでないレコードを削除する
場合，そのレコードの参照カウンタの data existence は provisional にセットされ，レコー
ド Rb だけが削除されて参照カウンタは削除されない．
レコード Rb の実体を削除することによって，レコード Ra への参照数の減算が引き起
こされる．それによってもしレコード Ra の参照数がゼロになった場合，レコード Ra は
その実体と参照カウンタの両方が正しく削除される．その後もし図 4.5(c) に示すように，
別のアプリケーション App X がレコード Rb を write し，App X がそれに対する参照を
保持した場合，管理プロセスは Rb の実体をストレージに書き込み，参照数を 1 から 2 に
加算して，data existence を actual に変更する．
この状態でレコード Rb 自身の参照カウンタは正しく 2 にセットされたが，レコード Rb
はレコード Ra への参照を内包している点に注意が必要である．つまりレコード Rb の実
体を write することによって，レコード Ra に対する参照数の加算処理が発生する．しか
しレコード Ra はこの時点ではストレージシステム内に存在しないため，管理プロセスは
先に述べたのと同じようにレコード Ra の参照カウンタだけを provisional 状態として作
成し，その参照数を 1 にセットする．
結果として，図 4.5(c) の状態ではレコード Rc の参照数は 1，レコード Rb は 2，レコー
ド Ra については参照数は 1 だがその実体は存在せず，参照カウンタだけが data existence
フィールドを provisional とした状態で存在しており，これですべてのレコードについて正
しく参照関係を把握することができた．
第 4 章 キャッシュ機構の設計
60
4.5
評価
提案した拡張した参照カウンタに基づくプロアクティブなキャッシュ管理機構について，
Gnutella に対する検索 query を測定して得たデータを用いて評価する．
まず 4.5.1 節にモデルとするシステムについて述べ，4.5.2 節に Gnutella の検索 query
に基づくコンテンツアクセスデータを用いたシミュレーションによって，提案するプロア
クティブなキャッシュ管理機構がユーザのコンテンツへの平均アクセスタイムを減じてい
ることを示す．
4.5.1
システムモデル
図 4.6
モデルとするアーカイブシステム
図 4.6 に評価のための単純なアーカイブシステムの構造を示す．基本的な構造は 4.3.2 節
の図 4.2 に示した例と同じである．サーバアプリケーション App S はグローバル WOODS
にチェインを保持している．キャッシュコントローラ Cont. C はローカル WOODS にそ
のチェインの end point から先頭方向に向かってある範囲までの部分をコピーするものと
する．この状態で閲覧アプリケーション App V がこのチェインにアクセスするが，もし
App V がローカル WOODS 上に存在しないレコードを読もうとした場合，App V はコン
トローラ Cont. C にグローバル WOODS から読むように依頼する．
4.5.2
シミュレーション
以下に良く知られた P2P ファイル共有システムである Gnutella のデータを用いたシ
ミュレーションによって提案手法の有効性を評価する．データは中山らの実験 [63] による
もので，Gnutella クライアントである Phex [64] を加工して Gnutella へのコンテンツア
4.5 評価
61
クセスのための検索 query を計測・取得したものに基づいている．計測は 2012 年の 4 月
24 日から 8 月末にかけて行われた．
Gnutella に対する query はハッシュコードつきのキーワードを含んでいるものがある．
それらの query は特定のコンテンツに対するものであると考えられるため，そうした query
をアーカイブに含まれる特定のコンテンツに対するアクセスとみなして用いる．
シミュレーションは 1) 新しいコンテンツが登場し，2) それがアーカイブされ，3) 後に
アクセスされる，という状況を想定して行った．まずアーカイブが空の状態からはじめ，取
得した query データからを一つずつ query を取り出す．もし query が新しいコンテンツに
対するものであれば，それはアーカイブであるチェインに追加される．その後もし同じコ
ンテンツに対する query が再び現れれば，それがキャッシュにヒットするか否かを調べる．
あるコンテンツが調査期間中に Gnutella に新しく追加されたものかどうかを明らかに
するために，4 月と 5 月の query をコンテンツの学習期間とした．その後，6 月から 8 月
までの query から学習したコンテンツに関する query をすべて除いたものを用いてシミュ
レーションを行った．
18 週間の計測から得たデータからは 188 億 9300 万の query を得た．そのうち 450 万件
の query を特定コンテンツに対するものとして抽出したが，そこには 181,000 のユニーク
なコンテンツが含まれていた．これらの特定コンテンツに対する query からそれぞれ 5,000
コンテンツを含む 8 つのデータセットをランダムに選ぶことでコンテンツの違いから生じ
る偶発的な変動について調べる．それぞれのデータセットは約 50,000 の query を含んで
いる．
図 4.7 は 8 つのアーカイブデータセットにおけるヒットレートの変動を示している．横
軸は最大キャッシュ量を全コンテンツ量に対する比で示している．例えばキャッシュ量 0.1
はアーカイブに 1,000 レコード存在し，100 レコードだけがキャッシュされている状況を
意味する．縦軸はヒット率を示す．グラフには 8 データセットの平均ヒット率をプロット
し，縦のバーでヒット率の最大および最小ケースの幅を表現した．
グラフはたかだか 0.1 のキャッシュ量でヒット率 0.44 ポイント (+0.032, -0.031) が得ら
れることを示している．0.3 のキャッシュ量ではヒット率は 0.74 ポイント (+0.031, -0.035)
である．
図 4.8 はアクセス遅延の縮減について示している．
ユーザがいずれかのデータを読もうとしたとき，アプリケーションは当該データに到達
するために，複数のリンクをたどらなければならない．以下に提案手法がどの程度最終的
なレスポンスタイムを減少させるかを示す．
ここでは最大キャッシュ量について 5%, 10%, 20% および 40% の四種類で試した．縦軸
はキャッシュしない場合に対してアクセスの遅延を減少させる率を示す．例えば減少率 0.5
第 4 章 キャッシュ機構の設計
62
図 4.7
キャッシュのヒット率
図 4.8
遅延の短縮
はキャッシュしない場合と較べて，アクセスにかかる時間が 2 倍速くなった（50% 減少し
た）ことを意味する．グラフには 8 データセットの平均減少率を，最高・最低ケースの幅
を意味するバーとともに表示した．
4.6 まとめ
63
なおローカル WOODS はグローバル WOODS に対して平均レスポンスタイムが 10 倍
高速であるものとしてシミュレーションを行った．つまり最大の減少率は 0.1 であり，そ
れは query に対して必要なアクセスがすべてキャッシュの中で行われたことを意味する．
グラフから 5% のキャッシュによって平均 0.78 (+0.04, -0.10) ポイントの減少率が得ら
れることがわかる．20% のキャッシュであれば，平均で 0.48 (± 0.05) ポイントの減少率
となる．
それぞれの結果は実際のアーカイブされたコンテンツに対するアクセス状況において，
提案手法が有効に機能し得ることを示すものである．
4.6
まとめ
この章では拡張された参照カウンタによるキャッシュ管理機構について提案した．これ
は部分的で不完全なチェインに関する参照数の管理を可能にするものであり，その結果と
して WOODS にキャッシュ管理機構を導入するものである．
この章ではまた実際の Gnutella の query データを用いた評価を行い，提案手法が有効
に機能することを示した．提案手法が機能するために必要な要件はデータが DAG 構造に
基づくことだけである．そのためこの機構は Content Hash ID に基づく他のアーカイブシ
ステムにも適用が可能であると考えられる．
65
第5章
結論
5.1
まとめ
従来 P2P 指向の強い，つまり広域に分散した多数かつ不安定なノードの利用を前提とし
た分散ストレージシステムでは，楽観的更新に伴って生じる並行した更新処理の衝突検出
やその修復といった一貫性管理における課題があった．とくに修復処理はアプリケーショ
ンに依存した解決方法が必要となるため，一般的な自動化ができない．
しかしデータへのアクセスを追記と読み出しのみの WORM タイプに制限し，適用する
アプリケーションを例えば電子メイルをはじめとした並行性のある追記処理の順序を問題
としないメッセージング・サービスなどに限定すれば，楽観的更新に伴う更新処理の衝突
検出や修復処理などの一貫性管理を必要としない汎用のデータ管理方式を設計し得る．
本論文ではこのような逐次記録型の新しいデータ管理方式である WOODS を提案した．
WOODS においては，データの ID はデータ本体とリンク情報を含んだレコードそのもの
のハッシュ値である．そこでは，高い衝突困難性と一方向性を備えたハッシュ関数を用い
ることによって以下のような性質を得ることができる．
• 同じ分散ストレージを共有する複数のアプリケーションが，ID を他のアプリケー
ションとの連携作業無しに自分自身で決定できる
• 各データはその ID を保持したまま，作成されたストレージシステムとは異なるス
トレージ空間に移動させることができる
• チェインにおいて，そのデータ構造は自然と DAG (Directed Acyclic Graph) タイ
プのものになり，ループが生じない
WOODS はこれらの性質を活かして以下の課題をそれぞれ解決する．
1)楽観的更新に由来するデータの更新衝突と，その修復のために生じるストレージシ
ステムのアプリケーションに対する依存性の排除
第 5 章 結論
66
2)不要となったデータの迅速な削除
3)逐次記録型システムに適したキャッシュ機構の導入
まず第 2 章で，WOODS の基本的な設計とその特徴について示し，それが 1) の課題を
解決することを示す．つまりチェインによるデータ構造が生み出す性質について述べ，提
案するデータ構造とアクセス手法に基づいたメイリングリスト・システムを設計した．そ
こで通常状態での並行する追記要求処理だけでなく，ネットワークの分割・結合時の処理
についても検討し，それが更新衝突や修復などの問題を生じずに問題なく動作し得ること
を示した．また評価として実際に運用されているメイリングリストのデータをもとに衝突
やその修復処理が必要となる頻度について検討し，それが自動修復なしの運用が困難と考
えられる程度に高いことを示した．
続く第 3 章では，WOODS の基本機構に対して不要となったデータの削除機構を導入し
た．提案手法はアプリケーションの異常終了に対応しながら，レコードの参照関係を把握
して不要となったレコードの削除を実現する．具体的には以下のように四つのフィールド
をもつ拡張された参照カウンタを設計した．
1. permanent counter, 他のレコードからの参照を数えるカウンタ
2. end point counter, アプリケーションからの参照を数えるカウンタ
3. lease time, end point counter のリースタイム（有効期間）
4. pending time, 削除処理に対する猶予期間
この二つの参照カウンタと二つの補助的なタイマーフィールドを組み合わせた新しいデー
タ管理手法によってレコードの参照関係を把握し，不要となったレコードの削除を実現す
る．また評価として，提案手法と従来的なリースタイムによる管理手法におけるメンテナ
ンスコストの比較を行った．そこでは日ごとの通信量において 120 日を経過する頃から提
案手法の方が従来手法より少なくなることを示し，特にアーカイブ処理などデータを長期
保持する場合に提案手法が効率良く機能する事を示した．
そして第 4 章ではキャッシュシステムを実現する機構について示した．P2P 環境ではア
クセス遅延の短縮は重要であり，キャッシュは代表的なアクセス遅延短縮のための手段で
ある．特に WOODS では，すべてのデータは書き換えできないため，キャッシュとして取
得したデータのコピーは元のデータとの間に相違を生じさせることがない点でキャッシュ
の利用に適している．本論文では以下の補助的なフィールドを参照カウンタに追加するこ
とで，この性質を活かしたキャッシュシステムを実現する．
5. data existence, データの存在状態を示す (provisional あるいは actual)
5.2 残された課題
67
この補助的なフィールドは部分的で不完全なチェインに関する参照数の管理を可能にし，
それを用いて WOODS に適したキャッシュ管理機構を実現する．また実際の Gnutella の
query データを用いた評価を行い，提案手法が有効に機能することを示した．
5.2
残された課題
以下に本論文では扱わなかった，今後検討すべき課題について示す．
実装
まず本論文では WOODS の設計を提示するにとどまり，その実装は行われていない．し
かし一つのキーに対して複数のフィールドに分けてデータを保持できるキー・バリュータ
イプの分散ストレージとして mongoDB [65] などが存在し，それらを用いてデータ本体と
参照カウンタをそれぞれ同一のキーに割り付けながら実装することが可能であると考える．
マージ処理における参照カウンタの再計算
また，本論文ではネットワークの分割・再結合時の処理を 2.5.3 節で検討したが，そこで
示した分割されたリングのマージ処理と，第 3 章および第 4 章で提示した拡張参照カウン
タによる参照数の再計算処理に関して，整合性の高い，かつ効率の良いアルゴリズムにつ
いての検討が不充分である．
まず一般的なガベージコレクションアルゴリズムで用いられる Stop the world，つまり
全体の処理を停止して処理するのであれば参照数を正しく再計算することは容易である．以
下に簡単に手順を述べる．各ストレージノードが自身の保持しているすべてのレコードの
参照数をいったんゼロに戻し，その後各ノードが保持するレコードが含む全てのリンクに
対して permanent counter の加算要求を出す．それらが全て完了すれば 2.5.3 節で説明し
た分割されたリングの結合処理を担当する代表リストサーバに通知を行う．分散ストレー
ジシステムの多くは各ノードの保持するデータ数をできるだけ均等に配置しようとするた
め，各ストレージノードが分担するレコードの数はそれほど偏らず，各ノードの処理が完
了するタイミングも近い時間になることが期待できる．並行して各アプリケーションもま
た，自身の保持している end point に対応するレコードに end point counter の加算要求
を出し，完了すれば代表リストサーバに通知する．代表リストサーバに全てのストレージ
ノードとアプリケーションからの通知が集まればマージ作業は完了である．
しかしこの単純な参照数の再カウント法では全レコードに関して通信処理を行うため，
所要時間は 2.5.3 節で示したマージ処理，つまり各アプリケーションが保持する情報を集
めて整合させるだけの作業に較べて相当に長くなることが予想される．そこで on the fly，
68
第 5 章 結論
つまり全体の処理を停止させずに新規の投稿を受け付けながら実行できるアルゴリズムに
ついて検討すべきと考えられる．
69
謝辞
本論文をまとめるにあたりご指導いただいた大阪市立大学 大学院工学研究科 岡育生教
授に感謝致します．また，審査にあたっては大阪市立大学 大学院工学研究科 原晋介教授，
鳥生隆教授のお世話になりました．感謝致します。最後に，本研究を進めるにあたり直接
ご指導いただいた大阪市立大学 大学院工学研究科 阿多信吾教授には多くの時間を割いて
頂きました．有意義な議論・指摘をいただけたことに深く感謝致します．
71
参考文献
[1] D. Liben-Nowell, H. Balakrishnan and D. Karger :
of Peer-to-Peer Systems,
Analysis of the Evolution
Proceedings of the twenty-first annual symposium on
Principles of distributed computing (PODC), pp.232-242, July 2002
[2] I. Stocia, R. Morris, D. Karger, M. F. Kaashoek and H. Balakrishnan : Chord:
A scalable peer-to-peer lookup service for Internet applications, Proceedings of
the 2001 conference on Applications, technologies, architectures, and protocols for
computer communications (SIGCOMM 01), pp.149-160, August 2001
[3] P. Maymounkov and D. Mazières : Kademlia: A Peer-to-Peer Information System
Based on the XOR Metric, Proceedings of the First International Workshop on
Peer-to-Peer Systems (IPTPS 02), pp.53-65, March 2002
[4] J. Stribling, I. G. Councill, J. Li, M. F. Kaashoek, D. R. Karger, R. Morris and S.
Shenker: OverCite: a cooperative digital research library, Proceedings of the Third
international conference on Peer-to-Peer Systems (IPTPS 05), pp.69-79, February
2005
[5] M. J. Freedman, K. Lakshminarayanan, S. Rhea and I. Stoica. : Non-transitive
connectivity and DHTs, Proceedings of the 2nd conference on Real, Large Distributed Systems (WORLDS 05), Volume 2, pp.55-60, December 2005
[6] J. Stribling, J. Li, I. G. Councill, M. F. Kaashoek and R. Morris : OverCite: a
distributed, cooperative CiteSeer, Proceedings of the 3rd conference on Networked
Systems Design & Implementation (NSDI 06), Volume 2, pp.11-21, May 2006
[7] B. Y. Zhao, L. Huang, J. Stribling, S. C. Rhea, A. D. Joseph and J. D. Kubiatowicz
: Tapestry: a resilient global-scale overlay for service deployment, EEE Journal
on Selected Areas in Communications, Volume 22 issue 1, pp.41-53, September
2006
参考文献
72
[8] R. Jimenez, F. Osmani and B. Knutsson : Sub-Second Lookups on a Large-Scale
Kademlia-Based Overlay, Proceedings of the 11th IEEE International Conference
on Peer-to-Peer Computing (P2P11), pp.82-91, August 2011
[9] W. Rao, R. Vitenberg and S. Tarkoma : Towards Optimal Keyword-based Content Dissemination in DHT-based P2P Networks, Proceedings of the 11th IEEE
International Conference on Peer-to-Peer Computing (P2P11), pp.102-111, August 2011
[10] W. Danqi and C.K. Yeo : Exploring Locality of Reference in P2P VoD Systems,
IEEE Transactions on Multimedia, Volume 14 issue 4, pp.1309-1323 Aug. 2012
[11] F. M. Cuenca-Acuna C. Peery, R. P. Martin and T. D. Nguyen : PlanetP: Using
Gossiping to Build Content Addressable Peer-to-Peer Information Sharing Communities, Proceedings of the 12th IEEE International Symposium on High Performance Distributed Computing, pp.236-246, June 2003
[12] F. M. Cuenca-Acuna, R. P. Martin and T. D. Nguyen :
Autonomous Replica-
tion for High Availability in Unstructured P2P Systems, Proceedings of the 22nd
International Symposium on Reliable Distributed Systems (SRDS 03), pp.99-108,
2003
[13] F. Dabek, M. F. Kaashoek, D. Karger, R. Morris and I. Stoica :
Wide-area
cooperative storage with CFS, Proceedings of the eighteenth ACM symposium on
Operating systems principles (SOSP 01), pp.202-215, December 2001
[14] A. Muthitacharoen, R. Morris, T. M. Gil and B. Chen : Ivy: a read/write peerto-peer file system, Proceedings of the 5th symposium on Operating systems design
and implementation (OSDI 02), pp.31-44, December 2002
[15] J. Kubiatowicz, D. Bindel, Y. Chen, S. Czerwinski, P. Eaton, D. Geels, R. Gummadi, S. Rhea, H. Weatherspoon, C. Wells and B. Zhao : OceanStore: An Architecture for Global-Scale Persistent Storage, Proceedings of the ninth international
conference on Architectural support for programming languages and operating systems (ASPLOS), pp.190-201 December 2000
[16] S. Rhea, C. Wells, P. Eaton, D. Geels, B. Zhao, H. Weatherspoon and J. Kubiatowicz : Maintenance-Free Global Data Storage, IEEE Internet Computing, Volume
5 issue 5, pp.40-49, September 2001
参考文献
73
[17] B. Zhang, A. Iosup, J. Pouwelse, D. Epema : Identifying, Analyzing, and Modeling
Flashcrowds in BitTorrent, Proceedings of the 11th IEEE International Conference
on Peer-to-Peer Computing (P2P11), pp.240-249, August 2011
[18] F. Dabek, J. Li, E. Sit, J. Robertson, M. F. Kaashoek and R. Morris : Designing
a DHT for low latency and high throughput, Proceedings of the 1st Symposium on
Networked Systems Design and Implementation (NSDI ’04), pp.55-60 March 2004
[19] F. Dabek : A distributed hash table, PhD thesis, Department of Electrical Engineering and Computer Science, MIT, September 2005
[20] A. Mislove, A. Post, A. Haeberlen and P. Druschel :
Experiences in building
and operating ePOST, a reliable peer-to-peer application, Proceedings of the 1st
ACM SIGOPS/EuroSys European Conference on Computer Systems (EuroSys ’06),
pp.147-159, April 2006
[21] JM Busca, F. Picconi and P. Sens :
Pastis: a highly-scalable multi-user peer-
to-peer file system, Proceedings of the 11th international Euro-Par conference on
Parallel Processing (Euro-Par 05), pp.1173-1182, August 2005
[22] R. Hasan, Z. Anwar, W. Yurcik, L. Brumbaugh and R. Campbell :
A Survey
of Peer-to-Peer Storage Techniques for Distributed File Systems, Proceedings of
the International Conference on Information Technology: Coding and Computing
(ITCC 05), Volume 02, pp.205-213, April 2005
[23] Y. Saito, B. N. Bershad and H. M. Levy : Manageability, availability, and performance in Porcupine: a highly scalable, cluster-based mail service, ACM Transactions on Computer Systems (TOCS), Volume 18, Issue 3, pp.298-337, August
2000
[24] D. B. Terry, M. M. Theimer, Karin Petersen, A. J. Demers, M. J. Spreitzer and C.
H. Hauser : Managing update conflicts in Bayou, a weakly connected replicated
storage system, Proceedings of the fifteenth ACM symposium on Operating systems
principles (SOSP ’95), pp.172-182, December 1995
[25] Y. Saito and M. Shapiro :
Optimistic replication,
(CSUR), Vol. 37, No. 1, pp.42-81, March 2005
ACM Computing Surveys
参考文献
74
[26] J. J. Kistler and M. Satyanarayanan : Disconnected Operation in the Coda File
System, ACM Transactions on Computer Systems (TOCS), Vol. 10, No. 1, pp.3-25,
February 1992
[27] M. Satyanarayanan : The evolution of Coda, ACM Transactions on Computer
Systems (TOCS), Vol. 20, No. 2, pp.85-124, May 2002
[28] CVS - Concurrent Versions System, http://www.nongnu.org/cvs/
[29] 塚田 大, 鈴木 勝博, 阿部 洋丈, 加藤 和彦 : インターネットを介した協調作業のため
のファイル同期システム, 情報処理学会研究報告 Vol. 2005 No. 79, pp.33-40, 2005
年8月
[30] Dropbox, http://www.dropbox.com/
[31] J. Stribling, E. Sit, M. F. Kaashoek, J. Li, and R. Morris :
Don’t Give Up on
Distributed File Systems, Proceedings of the 6th International Workshop on Peerto-Peer Systems (IPTPS07), Volume 1, February 2007
[32] Twitter, http://www.twitter.com/
[33] Facebook, http://www.facebook.com/
[34] A. Haeberlen, A. Mislove and P. Drushel : Glacier: highly durable, decentralized
storage despite massive correlated failures, Proceedings of the 2nd conference on
Symposium on Networked Systems Design & Implementation (NSDI 05), Volume
2, pp.143-158, May 2005
[35] F. Dabek, R Cox, F. Kaashoek and R. Morris : Vivaldi: a decentralized network
coordinate system, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications (SIGCOMM 04),
pp.15-26, August 2004
[36] 山本 寛, 山崎 克之 : ネットワーク座標システムの課題 : 時間変動の影響とその評
価, 電子情報通信学会技術研究報告 : 信学技報, 112 巻 212 号, pp.47-52, 2012 年 9
月
[37] R. Cox, F. Dabek, F. Kaashoek, J. Li and R. Morris :
Practical, distributed
network coordinates, ACM SIGCOMM Computer Communication Review, Volume
34 Issue 1, pp.113-118, January 2004
参考文献
75
[38] A. Mislove and P. Druschel : Providing administrative control and autonomy in
structured peer-to-peer overlays, Proceedings of the Third international conference
on Peer-to-Peer Systems (IPTPS 04), pp.162-172, February 2004
[39] 上田 達也, 安倍 広多, 石橋 勇人, 松浦 敏雄 : P2P 手法によるインターネットノード
の階層的クラスタリング, 情報処理学会論文誌, 47 巻 4 号, pp.1063-1076, 2006 年 4
月
[40] 中内 清秀, 森川 博之, 青山 友紀 :
関連性を有するコンテンツのための分散スト
レージサービス, 電子情報通信学会技術研究報告. IN, 情報ネットワーク, 102(694),
pp.55-60, 2003 年 2 月
[41] A. Mislove, A. Post, C. Reis, P. Willmann, P. Druschel, D. S. Wallach, X. Bonnaire,
P. Sens, J. M. Busca and L. Arantes-Bezerra : POST: A secure, resilient, cooperative messaging system, The 9th Workshop on Hot Topics in Operating Systems
(HotOS IX), pp.25-30, May 2003
[42] A. Rowstron and P. Druschel : Storage management and caching in PAST, a largescale, persistent peer-to-peer storage utility, Proceedings of the eighteenth ACM
symposium on Operating systems principles (SOSP 01), pp.188-201, December
2001
[43] P. Druschel and A. Rowstron :
PAST: A Large-Scale, Persistent Peer-to-Peer
Storage Utility, Proceedings of the Eighth Workshop on Hot Topics in Operating
Systems (HOTOS 01), p.75-80, May 2001
[44] A. Rowstron and P. Druscheln : Pastry: Scalable, distributed object location and
routing for large-scale peer-to-peer systems, Proceedings of the 18th IFIP/ACM
International Conference on Distributed Systems Platforms (Middleware 2001),
pp.329-350, November 2001
[45] S. Rhea, P. Eaton, D. Geels, H. Weatherspoon, B. Zhao and J. Kubiatowicz : Pond:
The OceanStore Prototype, Proceedings of the 2nd USENIX Conference on File
and Storage Technologies (FAST 03), pp.1 - 14, March 2003
[46] EMC Education Services : IT 技術者なら知っておきたい ストレージの原則と技術,
インプレスジャパン, pp.171-189, 2013
[47] Amazon Simple Storage Service (Amazon S3), http://aws.amazon.com/jp/s3/
参考文献
76
[48] Amazon Web Service, http://aws.amazon.com/
[49] A. Montresor and L. Abeni : Cloudy Weather for P2P, with a Chance of Gossip,
Proceedings of the 11th IEEE International Conference on Peer-to-Peer Computing
(P2P11), pp.250-259, August 2011
[50] 安田豊 : P2P 環境に適した追記に基づくデータ管理方式 WOODS, システム制御情
報学会論文誌, 第 21 巻 第 6 号, pp.33-40, 2008 年 6 月
[51] Y. Yasuda, S. Ata and I. Oka : Introducing delete feature for unnecessary data to
content-hash based distributed archive system, IEICE Communications Express,
Vol. 2 No. 1, pp.12-17, January 2013
[52] Y. Yasuda, S. Ata and I. Oka : Proactive cache management method for content
hash based distributed archive system, The International Conference on Information Networking (ICOIN 2013), pp.456-461, January 2013
[53] debian-user-mailing list, http://lists.debian.org/debian-user/
[54] S. Rhea, B. G. Chun, J. Kubiatowicz and S. Shenker : Fixing the Embarrassing
Slowness of OpenDHT on PlanetLab, Proceedings of the 2nd conference on Real,
Large Distributed Systems (WROLDS ’05), pp.25-30, December 2005
[55] S. Rhea, B. Godfrey, B. Karp, J. Kubiatowicz, S. Ratnasamy, S. Shenker, I. Stoica
and H. Yu : OpenDHT: a public DHT service and its uses, Proceedings of the 2005
conference on Applications, technologies, architectures, and protocols for computer
communications (SIGCOMM 05), pp.73-84, August 2005
[56] K. P. Gummadi, S. Saroiu and S. D. Gribble : King: estimating latency between
arbitrary internet end hosts, Proceedings of the 2nd ACM SIGCOMM Workshop
on Internet measurment (IMW 02) , Volume 1, pp.5-18, November 2002
[57] The Linux kernel archives, http://www.kernel.org/
[58] D. Kogan and A. Schuster :
Remote reference counting: distributed garbage
collection with low communication and computation overhead, Journal of Parallel
and Distributed Computing - Special Issue on Java on Clusters, Volume 60 Issue
10, pp.1260-1292 October 2000
参考文献
[59] D I Bevan :
77
Distributed garbage collection using reference counting, PARLE
Parallel Architectures and Languages Europe Lecture Notes in Computer Science,
Volume 259, pp.176-187, March 1987
[60] D. Plainfossé and M. Shapiro :
A Survey of Distributed Garbage Collection
Techniques, Proceedings of the International Workshop on Memory Management
(IWMM 95), pp.211-249, September 1995
[61] M. Shapiro, P. Dickman and D. Plainfossé :
SSP Chains: Robust, Distributed
References Supporting Acyclic Garbage Collection, Institut National de Recherche
en Informatique et en Automatique, August 1993
[62] Y. Ichisugi and A. Yonezawa : Distributed Garbage Collection Using Group Reference Counting, Technical report, Dept. of Information Science of Univ. of Tokyo,
Volume 90 issue 14, 1990
[63] H. Nakayama, S. Ata and I. Oka :
On Comparison of the Efficiency of Auto
Regressive Estimation Methods for Predicting Traffic Trends Patterns, in Proceedings of the 14th Asia-Pacific Network Operations and Management Symposium
(APNOMS’12), Septmeber 2012
[64] Phex, http://www/phex.org/mambo/
[65] mongoDB, http://www.mongodb.org/