教科書5章: Synchronization 後半

同期
教科書５章後半
1
同期
プロセス間の同期
実際の時刻(actual time, absolute time)に基づく同期(physical clock
synchronization)
プロセス間の相対的な時刻(relative time)に基づく同期(logical clock
synchronization)
分散システムのグローバル状態(global state)の概念の導入、および、
同期によるグローバル状態の記録手法
プロセスのグループから特定のプロセスをコーディネータとして選び出
す手法(leader election algorithm)
分散排他制御(distributed mutual exclusion)
分散トランザクション(distributed transaction)
2
グローバル状態
グローバル状態(global state)
分散システム全体が現在どのような状態にあるかを
表す
各プロセスのローカル状態の組、および、伝送中の
（送信されたがまだ受信されていない）メッセージの集
合からなる
グローバル状態を知ることが有用な理由
もし局所状態が全て停止中で、伝送中のメッセージも
無い場合、分散システムはデッドロックに陥ったこと
（あるいは、分散計算の場合は計算が終了したこと）
が分かる
3
分散スナップショット
分散スナップショット(distributed snapshot)[Chandy and
Lamport 1985]
グローバル状態を記録するアルゴリズム
一貫性のあるグローバル状態を記録
あるプロセスPが別のプロセスQからあるメッセージを受信したと記録
しかし、QはPに対してそのメッセージを送信したことが記録されていない
一貫性が無い
グローバル状態の概念: カット(cut)によって図示
4
分散スナップショットアルゴリズム
仮定：各プロセスは相互に1対1単方向FIFO通信チャネル(TCPな
ど)で結合
メッセージは必ず送信順に受信される
C12
P1
P2
C21
C32
C13
C31
C23
P3
5
分散スナップショットアルゴリズム
アルゴリズムを開始するプロセスＰ1（Ｐ1は任意）は、
まず自分の現在のローカル状態を記録
C12
P1の状態記録
P1
C21
C31
1
C32
C13
1
2
P2
C23
P3
6
分散スナップショットアルゴリズム
次に、マーカー(marker)を各出力チャネルに送信
マーカーを受信するプロセスはスナップショットの記録に参加しなければ
ならない
同時に、状態記録してから各チャネルから受信したメッセージ
列を記録
C12
P1の状態記録
1
P1
2
C31の
状態記録
C31
P2
C21
1
C32
C13
3
C23
P3
7
分散スナップショットアルゴリズム
マーカーを受信したプロセスは（下図ではP2）
まだローカル状態を記録していないならば、
ローカル状態を記録
マーカーを送信
P1の状態記録
P1
1
1
2
C31の
状態記録
C12
C21の
状態記録
3
C31
P2
C21
2
C32
C13
4
C23
P3
8
分散スナップショットアルゴリズム
マーカーを受信したプロセスは（下図ではP2）
まだローカル状態を記録していないならば、
ローカル状態を記録
マーカーを送信
P1の状態記録
P1
1
1
2
3
C31の
状態記録
C12
C21の
状態記録
C21
C31
P2
2
C32
2
C13
4
5
P2の状態記録
1
1
C23
P3
9
分散スナップショットアルゴリズム
マーカーを受信したプロセスは（下図ではP2）
まだローカル状態を記録していないならば、
ローカル状態を記録
マーカーを送信
P1の状態記録
P1
1
2
3
C31の
状態記録
C12
C21の
状態記録
1
4
5
C31
P2の状態記録
P2
C21
2
C32
2
C13
P3
1
1
C23
10
分散スナップショットアルゴリズム
状態記録後に受信したメッセージ
既にマーカーを受信したプロセスからのメッセージ
無視
まだマーカーを受信していないプロセスからのメッセージ
記録
C12の
状態記録
C12
P1の状態記録
P1
1
2
3
1
4
C31の
状態記録
空
C21の
状態記録
5
C31
2
C21
1
P3
P2C32の
状態記録
2
C32
3
C13
P2の状態記録
1
C23
11
分散スナップショットアルゴリズム
プロセスP3がマーカーを受信すると
まだP3のローカル状態を記録していない
記録して、マーカーを送信
ローカル状態記録後に受信したメッセージを記録
C12の
状態記録
C12
P1の状態記録
P1
1
2
3
4
C31の
状態記録
空
C21の
状態記録
1 2
5
P2
2 1
C21
C32
C13
C31
P3
P3の状態記録
P2の状態記録
1
3
C32の
状態記録
C23
12
分散スナップショットアルゴリズム
プロセスP3がマーカーを受信すると
まだP3のローカル状態を記録していない
記録して、マーカーを送信
ローカル状態記録後に受信したメッセージを記録
C12の
状態記録
C12
P1の状態記録
P1 1 2
1
2
空
C21の
状態記録
5
3
C31の C31
4 状態記録
P2
3 2 1
C21
C13
C13の
状態記録
P3
C32の
状態記録
C32
空
P3の状態記録
P2の状態記録
C23
1
C23の
状態記録
13
分散スナップショットアルゴリズム
全ての入力チャネルからマーカーを受信したプロセスは
アルゴリズムを終了し、記録したプロセスの状態と各入力チャネルの状
態をスナップショットとする
C12の
状態記録
C12
P1の状態記録
1
空
C21の
状態記録
P1 1 2
2
3
C31の C31
4 状態記録
5
P2
3 2 1
C21
C13
C13の
状態記録
空
P3
P3の状態記録
P2の状態記録
C32の
状態記録
C32
C23
1
C23の
状態記録
14
(リーダー)選任アルゴリズム
多くの分散アルゴリズム：ある一つのプロセスを取りまと
め役(リーダー、コーディネーター)として選ぶ必要
どのプロセスでも構わないが１つ選ぶ必要がある
（リーダー）選任アルゴリズム(leader election
algorithm): 複数プロセスからリーダー（コーディネー
ター）を選ぶアルゴリズム
仮定：
各プロセスには一意の番号(ID)が割り振られている
任意のプロセスは他の全てのプロセスの番号を知っている
目標：
全てのプロセスが、誰がコーディネーターになったかに関して合意
さまざまな選任アルゴリズムが提案されてきている
[Fredrickson and Lynch 1987], [Garcia-Molina 1982], [Singh and Kurose
1994]
15
選任アルゴリズムの応用
セキュアなグループ通信のための暗号鍵配布
B. DeCleene et al. Secure Group Communication for Wireless Networks.　In Proc. of
MILCOM 2001, VA, October 2001.
経路制御
C. Perkins and E. Royer. Ad-hoc On-Demand Distance Vector Routing. In Proc. of the 2nd
IEEE WMCSA, New Orleans, LA, February 1999, pp. 90-100.
センサネットワーク制御
W. Heinzelman,A. Chandrakasan and H. Balakrishnan. Energy-Effcient　Communication Protocol for Wireless Microsensor Networks. In Proc.of HICSS,
2000.
その他の制御
K. Hatzis, G. Pentaris, P. Spirakis, V. Tampakas and R. Tan. Fundamental Control
Algorithms in Mobile Networks. In Proc. of 11th ACM SPAA, pages 251-260, March 1999.
N. Malpani, J. Welch and N. Vaidya. Leader Election Algorithms for　Mobile Ad Hoc
Networks. In Fourth International Workshop on Discrete Algorithms and Methods for
Mobile Computing and Communications, Boston, MA, August 2000.
など
16
ブリーアルゴリズム
ブリーアルゴリズム(bully algorithm):
[Garcia-Molina 1982]で提案された選任アルゴリズム
あるプロセスPが現在のコーディネータが反応しない（障害など
で停止した）ことに気づいたときに、選任(election)を開始
以下の例では、プロセス７がクラッシュしたコーディネータで、プロセス４
が選任を開始
選任を開始するプロセスP
クラッシュしたコーディネータ
17
ブリーアルゴリズム
Pは次のように選任の作業を行う
PはELECTIONメッセージを、自分より上の番号の全てのプ
ロセスに対して送信
P
18
ブリーアルゴリズム
もし誰も応答しなければ、Pは選挙に勝ったと見なし、自分
がコーディネータとなる
誰か上位の番号のプロセスが応答すれば、（選挙に負けた
と判断し）Pの仕事は終了
P
19
ブリーアルゴリズム
ELECTIONメッセージに応答したプロセスは、それぞれ自分
が選任アルゴリズムを開始する
20
ブリーアルゴリズム
もし誰も応答しなければ、Pは選挙に勝ったと見なし、自分
がコーディネータとなる
以下の例では、プロセス６が勝つ
21
ブリーアルゴリズム
任意のプロセスは自分より下位の番号のプロセスから
ELECTIONメッセージを受信する可能性がある
もし受信したならば，自分が生きていることを示すOKメッセージを返
信
そして、今度は自分が（上記の）選任の仕事を実行
いつかは、１つを除いた全てのプロセスが選任の仕事を終え、ある1
つのプロセスがコーディネータとなる
選挙に勝ったプロセスは、他の全てのプロセスに対して自分の勝利
を通知
番号が上位のプロセスが常に勝利するので、 “bully(ガキ
大将) algorithm”と呼ばれる
22
リングアルゴリズム
リングアルゴリズム(ring algorithm): リングを用いた選任アルゴ
リズム
他のリングアルゴリズムとは異なり、トークンは使用しない
仮定：プロセス群は順序付けられており、各プロセスは自分の次の順番の
プロセス(後続者、successor)を知っている
23
リングアルゴリズム
動作手順
コーディネータが機能していないことに気づいたプロセスは、ELECTION
メッセージに自分のプロセス番号を付けて、後続者に送信
24
リングアルゴリズム
もし後続者がダウンしていたら、一つとばした次のプロセスに送信（生き
ているプロセスが見つかるまで繰り返す）
25
リングアルゴリズム
ELECTIONメッセージを受信したメッセージは、自分が生きていることを
示す返事を返すとともに、受信したELECTIONメッセージに自分のプロセ
ス番号をリストに追加して、自分の後続者に転送
26
リングアルゴリズム
いつかは自分が送信したELECTIONメッセージが自分に返ってくる（リス
トに自分の番号があることにより認識）
今度はメッセージタイプを
COORDINATORに変更してもう一度回覧
今度は誰がコーディネータであるか（リストのうち最も大きな番号の
プロセス）、および、リングを構成する新しいメンバーが誰であるかを
知らせるため
COORDINATORメッセージの回覧が終了すると、それぞれが自分の
仕事に戻る
27
リングアルゴリズム
複数のプロセスが同時にELECTIONメッセージの回覧を始めることがあ
る
最終的に選ばれるコーディネータは一意なので実害は無い
メッセージが重複するがトラフィックに与える影響はわずか
28
拡散計算に基づく選任アルゴリズム
拡散計算(diffusing computation) [Dijkstra
and Scholten 1980]
一つのノードから始まって、グラフの全ノードへと拡
散させていく計算
E.W. Dijkstra and C.S. Scholten. Termination detection for
diffusing computations. In Information Processing Letters, vol.
11, no. 1,pp. 1-4, August 1980.
29
拡散計算に基づく選任アルゴリズム
仮定：
ネットワークトポロジが有向グラフで与えられる
近くのノード(neighbor)＝直接リンクで接続されたノード
ノードとリンクは障害なし
各ノードは、コーディネータへの適性度をあらわす
値（ノードの価値）を保持
この値が最も大きいノードが選任される
30
拡散計算に基づく選任アルゴリズム
アルゴリズムの概要
選任アルゴリズムを起動したノード(ソースノード)から、メッ
セージを拡散させていき、スパニングツリーを構成(成長相：
growing phase)
拡散させたメッセージの応答を集め、誰がコーディネータか
を判断する情報をソースノードに集約(縮退相：shrinking
phase)
ソースノードは選出されたコーディネータ(リーダー)を全ノー
ドにアナウンス
使用するメッセージ：３種類
Election
Ack
Leader
31
拡散計算に基づく選任アルゴリズム
(growing phase)
ソースノードはElectionメッセージを近くのノードに
送信
ソースノード
Election
Election
32
拡散計算に基づく選任アルゴリズム
(growing phase)
Electionを受信したノードは、最初にElectionを受信
したノードを自分の親ノードとし、親ノード以外の近
くのノードにElectionメッセージを送信
ソースノード
Election
Election
Election
Election
33
拡散計算に基づく選任アルゴリズム
(growing phase)
親ノード以外からElectionを受信したノードは、Ack
メッセージで応答
親ノードには、この時点では応答しない
ソースノード
Election
Election
Election
Election
Ack
34
拡散計算に基づく選任アルゴリズム
(growing phase)
親ノード以外からElectionを受信したノードは、Ack
メッセージで応答
親ノードには、この時点では応答しない
ソースノード
Election
Election
Election
Election
Election
Ack
35
拡散計算に基づく選任アルゴリズム
(shrinking phase)
親ノード以外の全ての近くのノードからAckを受信したノード
は、親ノードにAckメッセージを応答
このとき、選任に必要な情報（各ノードの価値のリスト）をメッセージ
に含める
ソースノード
3
Election
Election
7
Election
Election
Ack([2])
Election
5
4
Ack([5])
2
Ack
36
拡散計算に基づく選任アルゴリズム
(shrinking phase)
親ノード以外の全ての近くのノードからAckを受信したノード
は、親ノードにAckメッセージを応答
このとき、選任に必要な情報（各ノードの価値のリスト）をメッセージ
に含める
Ack([5,4])
ソースノード
3
Election
Election
7
Election
Election
Ack([2])
Election
5
4
Ack([5])
2
Ack
37
拡散計算に基づく選任アルゴリズム
(shrinking phase)
親ノード以外の全ての近くのノードからAckを受信したノード
は、親ノードにAckメッセージを応答
このとき、選任に必要な情報（各ノードの価値のリスト）をメッセージ
に含める
Ack([5,4])
Ack([5,4,7])
ソースノード
3
Election
Election
7
Election
Election
Ack([2])
Election
5
4
Ack([5])
2
Ack
38
拡散計算に基づく選任アルゴリズム
ソースノードが全ての子ノードからAckを受信
に必要な情報を全て収集
選任
最も価値が高いノードをコーディネータに選出
誰がコーディネータに選任されたかを、全ノードに
ブロードキャスト
Leader(7)
ソースノード
3
Leader(7)
Leader(7)
7
5
4
Leader(7)
2
新しいコーディネータ
39
モバイルアドホックネットワークでの選
任アルゴリズム
アドホックネットワーク(Ad-hoc Networks)
各ノードが無線などの通信手段で近くのノードと通信リンクを自律的に
構成するネットワーク
通信インフラストラクチャが不要
その場限りの(Ad-hoc)ネットワーク
モバイルアドホックネットワーク(Mobile Ad-hoc Networks,
MANET)
各ノードの移動を許容するアドホックネットワーク
モバイルアドホックネットワークでの選任問題
ネットワークの各強連結成分に対してコーディネータを選任する必要
コーディネータの選任中にネットワークトポロジの動的な変化を許す必
要
選任されるコーディネータは以下の意味で最も優れたノードである必要
バッテリ残量が多い、計算能力が大きいなど
40
モバイルアドホックネットワークでの選
任アルゴリズム
[Vasudevan, Kurose, Towsley 2004]の手法
Sudarshan Vasudevan, Jim Kurose, Don Towsley,
Design and Analysis of a Leader Election Algorithm for
Mobile Ad Hoc Networks, in Proc. of 12th IEEE Int. Conf.
on Network Protocols, (ICNP'04) , pp. 350-360, 2004.
41
モバイルアドホックネットワークでの選
任アルゴリズム
拡散計算に基づく選任アルゴリズムを拡張
５種類のメッセージを使用
Election,Ack,Leader,Probe,Reply
ノードの移動によるスパニングツリーの変化を検出
各ノードはElectionを送信して、まだAckを受信していないノード群に
対して、定期的にProbeメッセージを送信
Probeを受信したノードはReplyメッセージを応答
一定のタイムアウトでReplyを受信しない場合、そのリンクは切断と
判断
検出したノードは適切な処理を行う
もしAck待ちのノードと切断したならば、そのノードからのAckを無視
して、他の全てのAckがそろった段階で親ノードにAckを送信
もし親ノードと切断したならば、自分を親とするサブツリーの中でコー
ディネータを選任し、アナウンスを行う
42
モバイルアドホックネットワークでの選
任アルゴリズム
新たにリンクが生成され、２つのネットワークがマージ
された場合
生成されたリンクの両側のノード(下図ノードA,U)はそれぞ
れのネットワーク内でコーディネータを持つ場合
ノードA,Uはそれぞれのコーディネータの情報を交換し、より優れて
いる方(ノードC)を、新しいコーディネータに選任
新しいコーディネータを残りの全ノードにアナウンス
43
モバイルアドホックネットワークでの選
任アルゴリズム
新たにリンクが生成され、２つのネットワークがマージ
された場合
どちらかが属するネットワークがコーディネータを持たない
（選出中の）場合
下図のノードA,B,Cはまだコーディネータを持たない
ノードAとUの間にリンク生成
ノードUは自分が属するネットワークのコーディネータ(W)をノードAに
通知
ノードAは現在進行中の選任アルゴリズムを中断し、ノードB,Cに新し
いコーディネータをアナウンス
44
排他制御
複数プロセスからなるシステム
クリティカルリージョン(critical region)を用いて容易に
プログラム可能
共有データを読んだり更新したいとき、クリティカルリージョ
ンに入り、その中では他のプロセスが共有データにアクセス
できないこと（相互排他、mutual exclusion）を保証
単一プロセッサシステム
クリティカルリージョンはセマフォやモニターなどの機構によ
り、他のプロセスからのアクセスから保護
分散システムにおけるクリティカルリージョンおよび排
他制御の実現法を紹介
45
排他制御：集中アルゴリズム
単純なアプローチ：単一プロセッサでの排他制御をシミュレート
あるプロセスをコーディネータに選出
クリティカルリージョンに入りたいプロセスはコーディネータにリクエストを送
信し許可を求める
コーディネータは、既にクリティカルリージョンに入っているプロセスが無け
れば許可のメッセージを返信
許可のメッセージを受信したプロセスはクリティカルリージョンに入る
46
排他制御：集中アルゴリズム
もし、既に他のプロセスがクリティカルリージョンに入ってい
たら、
返信をしない、または、拒否のメッセージを返信
リクエストを待ち行列に入れる
47
排他制御：集中アルゴリズム
プロセスがクリティカルリージョンから出ると、ロックを解放するメッセー
ジをコーディネータに送信
ロックが解放されたら、コーディネータは待ち行列の先頭のリクエストを
処理し，そのプロセスに次のアクセス許可を与える
欠点
コーディネータがクラッシュすると機能しない
コーディネータに処理が集中
性能のボトルネックになる恐れ
48
排他制御：分散アルゴリズム
Ricart and Agrawalaのアルゴリズム[Ricart and
Agrawala 1981]
排他制御を実現する分散アルゴリズム
仮定：システムの全イベントに全順序が付いている
Lamportのタイムスタンプで実現可能
49
排他制御：分散アルゴリズム
動作手順
クリティカルリージョンに入りたいプロセスは、入りたいクリティカルリー
ジョンの名前，自分のプロセス番号、および、現在時刻（Lamportの
タイムスタンプ）を含むリクエストメッセージを全てのプロセス（自分自
身を含む）に送信
通信にはエラーが無いと仮定
50
排他制御：分散アルゴリズム
リクエストメッセージを受信したプロセスは以下のいずれか
の動作を行う
もし受信プロセスがクリティカルリージョンに入っておらず、
これから入りたくも無ければ、OKメッセージを返信
51
排他制御：分散アルゴリズム
もし既にクリティカルリージョンに入っているならば、返信は行わず、
メッセージをキューに入れる
もし自分もクリティカルリージョンに入りたいならば、受信メッセージと
自分が送信したリクエストメッセージのタイムスタンプを比較
もし受信メッセージの方が早ければ、OKを返信（自分は負け）
さもなければ（自分が勝ちなので）、返信を行わずメッセージを
キューに入れる
52
排他制御：分散アルゴリズム
もし既にクリティカルリージョンに入っているならば、返信は行わず、
メッセージをキューに入れる
もし自分もクリティカルリージョンに入りたいならば、受信メッセージと
自分が送信したリクエストメッセージのタイムスタンプを比較
もし受信メッセージの方が早ければ、OKを返信（自分は負け）
さもなければ（自分が勝ちなので）、返信を行わずメッセージを
キューに入れる
プロセス２のリクエストを
キューに格納
53
排他制御：分散アルゴリズム
他の全てのプロセスからOKメッセージを受信したらクリティ
カルリージョンに入る
54
排他制御：分散アルゴリズム
クリティカルリージョンから出るとき、キューに入れた全ての
メッセージの送信プロセスにOKを返信
55
排他制御：分散アルゴリズム
Ricart and Agrawalaのアルゴリズムは、（クリティカルリージョンが一つ
のみならば）デッドロックに陥らない
Ricart and Agrawalaのアルゴリズムは、飢餓状態(starvation)に陥らな
い、すなわち、クリティカルリージョンを要求したプロセスはいつか必ず
入れる
タイムスタンプが全順序であることから示される
必要なメッセージ数：2(n-1) （nはプロセスの総数）
nプロセスのうち１つでもクラッシュすると機能しない
リクエストに対して返事がない
リクエストを拒否されたのか、クラッ
シュしたのか区別不能
１つの改良：リクエストを拒否する場合も拒否メッセージで応答
集中アルゴリズムと比較して、利点は何も無い（効率面、耐障害性とも
に劣る）
少なくとも分散アルゴリズムの存在を示す 将来の改善に期待
56
トークンリングアルゴリズム
トークンリングアルゴリズム(Token Ring
Algorithm)
プロセス群を論理的なリング状に構成
ネットワークの物理トポロジとは無関係に構成可能
各プロセスは自分の後が誰かを知っておけばよい
57
トークンリングアルゴリズム
トークン(token)をリングに沿って回し、トークンを持ってい
るプロセスのみがクリティカルリージョンに入る権利を持つ
もしトークンを持っているプロセスがクリティカルリージョンに
入りたければ、入って処理を行い、終了したらトークンを次
のプロセスに回す
クリティカルリージョンに入りたくなければ、単に次のプロセ
スにトークンを回す
問題点：トークンが失われたら機能しない
失われたことの検出も困難（次のトークンが回ってくるまで
の時間に上限がない タイムアウトでは検出不可）
58
３つのアルゴリズムの比較
集中アルゴリズム
（クリティカルリージョンに1回入って出るのに）必要なメッセージ数＝３（リク
エスト、許可、解放）
分散アルゴリズム
必要なメッセージ数＝2(n-1) （リクエストと許可がそれぞれ(n-1)プロセス分）
トークンリングアルゴリズム
必要なメッセージ数＝1から∞ （不要なときもトークンを回し続ける必要があ
るので）
59
分散トランザクション
トランザクション(transaction)の概念：排他制御と
強く関連
排他制御: 共有リソースに高々1つのプロセスしかア
クセスしないことを保証
トランザクション: 同様に複数プロセスによる同時アク
セスから共有リソース（特に、共有データ）を守る機構
排他制御より多くのことが可能
一つのアトミックオペレーションで複数のデータを更新可能
もしトランザクションの途中で失敗したら、トランザクション実行前の
時点まで状態を戻す
60
トランザクションモデル
トランザクションの概念
商取引の世界がオリジナル
取引が成立するまでは、いつでも交渉を止めることが出来
る
止めた場合、取引は最初から無かったことに
一旦取引が成立して契約書にサインすると、後戻りできない
61
トランザクションモデル
計算機の世界でも同様
あるプロセスが他のプロセスとともにトランザクションを始
めたいことをアナウンス
プロセス間でさまざまな交渉や処理を行う
全てのプロセスが合意するとトランザクションは終了(＝
コミット：commit)
合意が成立しなければトランザクション開始前の状態に
戻る(＝アボート：abort)
このようなall or nothingの性質が有用
62
トランザクションの歴史
計算機の世界におけるトランザクションの利用：1960
年代に始まる
ファイルを磁気テープに記録していた時代
スーパーマーケットの在庫管理システム
閉店後に2本の入力テープ（前日の在庫情報、本日の更新内容）か
ら1本の出力テープ（本日の在庫情報）を生成
処理が失敗
入力テープは残るので、最初からやり直せばよい
実害は生じない
all or nothingの性質を持つ
63
トランザクションの利用
トランザクションを利用したプログラミング
特殊なプリミティブが必要
トランザクションプリミティブの例
64
トランザクションの利用例
例：フライト予約システム
White Plains
JFK
Nairobi
Malindiという乗り
継ぎで予約したい
一つでも予約できないと全ての予約をキャンセル
65
トランザクションの性質
トランザクションを特徴付ける４つの性質(ACID
property)
アトミック性（Atomic）: 外界からは、トランザクションは不可
分の動作として見える
一貫性（Consistent）: トランザクションはシステムの一貫性
を破壊しない
孤立性（Isolated）: 並列に実行される複数のトランザクショ
ンは互いに干渉しない
耐久性（Durable）: 一旦トランザクションがコミットされると、
その変更は永久となる
66
トランザクションの分類
トランザクションは以下の3種類に分類される
1. フラットトランザクション（flat transaction）
2. 入れ子トランザクション（nested transaction）
3. 分散トランザクション（distributed transaction）
67
フラットトランザクション
フラットトランザクション（flat transaction）
処理の系列で、ACID propertyを満たすもの
最も単純なトランザクション
幾つかの制限：
トランザクションの処理の一部のみをコミットできない
複数のフラットトランザクションに分割すると一貫性を保持できない
68
入れ子トランザクション
入れ子トランザクション（nested
transaction）
幾つかの部分トランザクション
（subtransaction）に分割し階層的に構成
トップレベルのトランザクション（top-level
transaction）はサブトランザクションを並列実
行
全てのサブトランザクションがコミットされると、
トップレベルのトランザクションをコミットする
トップレベルトランザクションがアボートし
た場合、コミットしたサブトランザクションを
元に戻せるようにしなければならない
ACID propertyはトップレベルトランザ
クションでのみ成立
サブトランザクションへの分割は論理的な分
割
69
分散トランザクション
分散トランザクション（distributed transaction）
物理的に分割された（論理的には同じ）データにアクセスす
るトランザクションを、物理的分割に従ってサブトランザクショ
ンに分割して構成
70
トランザクションの実装
トランザクションの実装手法を紹介
簡単のため、ファイルシステム上のトランザクションの
み考慮
71
プライベート作業空間
プライベート作業空間（private workspace）
による実装
トランザクションの開始時に、自分専用の作業領域
（private workspace）が与えられ，そこにアクセス
するデータのコピーを置く
トランザクション処理中は、プライベート作業空間に対し
て読み書きを行う
トランザクションをコミットすると、作業空間のデータをファ
イルシステムに書き戻す（アボートした場合は、単に破棄）
72
プライベート作業空間の効率化
(1/4)
プライベート作業空間の問題点：大量のファイル
をコピーするのはコストがかかる
解決法：
読むだけのファイルは作業空間にコピーしない（親トランザ
クションの作業空間へのポインタ（インデックス）のみ保持）
トップレベルトランザクションの親の作業空間は実ファイ
ルシステムに対応
作業空間
サブトランザクション
作業空間
実ファイルシステム
作業空間
トップレベルトランザクション
サブトランザクション
73
プライベート作業空間の効率化
(2/4)
更新するファイルに関しても実体はワークスペースにコ
ピーせず、インデックス(inode)のみを管理
１．読み込み時はインデックスを通じて実ファイルへアク
セス
74
プライベート作業空間の効率化
(3/4)
更新するファイルに関しても実体はワークスペースにコピーせず、イ
ンデックス(inode)のみを管理
２．最初の書き込み時に、(ディスク上の)実ファイルブロックをコピー
し、そこへデータを書き込み、ワークスペース上のインデックスを
そのブロック(シャドウブロック：shadow block)を指すように更新
75
プライベート作業空間の効率化
(4/4)
更新するファイルに関しても実体はワークスペースにコ
ピーせず、インデックス(inode)のみを管理
３．コミット後にはプライベート作業空間上のインデックス
を、親の作業空間にコピー
76
先行書き込みログ
先行書き込みログ（writeahead log）: もう一つのトランザクショ
ン実装法
ファイルは実際に更新される
ただし、何処をどのように変更したか（古い値と更新後の値の組）のログを
残す
コミットしたら、コミットしたことを示す記録をログに残す
もしアボートしたら、ログの情報に基づいてトランザクション実行前の状態に
戻す(ロールバック：rollback)
77
並行性制御
今までの話はアトミック性の実現手法
障害が起きうる状況でのアトミック性と耐久性の達成
7章で扱う
一貫性と孤立性
並行トランザクションを適切に制御
すること(並行性制御：concurrency control)で達成
78
並行性制御の目標
並行性制御の目標
複数のトランザクションを並行に実行しても、データの一貫
性を破壊しないようにする
トランザクションがデータにある特定の順序でアクセスする
ように制御し、トランザクションを逐次実行した場合と同じ最
終結果が得られるようにすることで達成
79
並行性制御のアーキテクチャ(1/2)
3層に分けたマネージャで構
成
最下層：データマネージャ
実際のデータの読み書きを実行
中間層：スケジューラ
どのトランザクションがいつデータ
の読み書きを行うかを決定
最上層：トランザクションマネー
ジャ
アトミック性を達成するための処理
を担当
並行性制御はスケジューラが
主に担当
80
並行性制御のアーキテクチャ(2/2)
分散トランザクションの場
合の構成
全体のトランザクション管理
は単一のトランザクションマ
ネージャで行う
各マシンはローカルの一貫
性を保つためのスケジュー
ラとデータマネージャを持つ
各スケジューラは並行性制
御のために、別のマシン上
のデータマネージャとも通信
81
逐次化可能性
並行性制御の目的
複数トランザクションを、相互に干渉しないように並行
に実行可能にする
最終結果は、逐次実行したときと同じになるように
並行実行されるトランザクションの各操作をどの
順で実行すべきかの概念(逐次化可能性：
serializability)が重要
82
逐次化可能性の例
3つの並行トランザクションのスケジュール例
スケジュール1は本当に逐次的にした場合(逐次化可能)
スケジュール2は逐次的ではないが、最終結果はスケジュール1と同
じ(逐次化可能)
スケジュール3は最終結果がスケジュール1と異なる(逐次化不能)
83
並行性制御の説明のための記法
スケジュールと並行性制御：計算される値自体は無関係
トランザクションを特定の変数に対するread,write操
作の系列として表現
以下の３つのトランザクションTi (i=1,2,3)の例では
write(Ti,x); read(Ti,x); write(Ti,x)
84
並行性制御の考え方
並行性制御： 競合するオペレーション（conflicting
operations）を適切にスケジュールすること
競合するオペレーション: 同じ変数に対する複数の操作
で、少なくとも一つがwrite操作
writeオペレーションが１つ 読み書き競合(read-write
conflict)
writeオペレーションが複数 書き書き競合(write-write
conflict)
readオペレーション同士は決して競合しない
85
並行性制御アルゴリズムの分類
read,writeオペレーションの同期方法による分類
排他制御(mutual exclusion)
タイムスタンプによる順序付け
悲観的か楽観的かによる分類
悲観的（pessimistic）アプローチ
競合が起こりそうな場合、適切な同期処理で未然に防ぐ
楽観的（ optimistic ）アプローチ
競合は滅多に起こらない前提で、単純に(read/writeオペレー
ションを)実行
トランザクションの最後で同期処理を実行
もし競合が起こっていたことが分かると、アボートさせる
86
2相ロッキング
ロッキング（locking）: 最も古く、よく用いられて
いる並行性制御アルゴリズム
変数xを読み書きしたいとき、その変数のロックをスケ
ジューラに要求
読み書きが終了すると、ロックを解放
スケジューラの仕事
逐次化可能なスケジュールでread/writeオペレーショ
ンが実行されるように、各プロセスに対してロックの許
可・解放を行う
2相ロッキング(Two-Phase Locking：2PL): 上記
を実現するアルゴリズムの一つ
87
2相ロッキングの動作原理
2相ロッキングの動作原理
スケジューラは、まずトランザクション実行に必要な全てのロッ
クを与える(成長相：growing phase)
トランザクション実行終了後、それらのロックを解放する(縮退
相：shrinking phase)
88
2相ロッキングの動作詳細
スケジューラは以下のルールに従う[Bernstein et al. 1989]
スケジューラがトランザクションマネージャからオペレーションoper(T,x)
の実行を依頼されたとき、既にロックを与えた他のオペレーションと競合
しているか否かを調査
もし競合していればその操作の実行は延期
さもなければ変数xのロックを与えてoper(T,x)の実行をデータマネー
ジャに依頼
スケジューラはデータマネージャが変数xに対する処理を終了するまで
決してxのロックを解放しない
一旦スケジューラがトランザクションTに関するロックを解放すると、それ
以降、Tに対して決してロックを与えない（変数名と無関係に）
定理：全てのトランザクションが2相ロッキングを用いるならば、
それによって形成される任意のスケジュールは逐次化可能で
ある [Eswaran et al. 1976]
89
厳密2相ロッキング
厳密2相ロッキング（strict two-phase locking）
トランザクション終了(コミットまたはアボート)後に縮退相を実行
２つの主な利点
任意のトランザクションは常に他のトランザクションがコミットした正式な
値を使うことができる
正式でない値を用いて計算したことが理由で、トランザクションをア
ボートさせる必要が無い（連鎖アボート（cascaded abort）を防止）
任意のロック要求及び解放をシステム側で自動的に実行可能（必要時
にロック要求、終了後に同時に解放）
90
2相ロッキングの分散実装法(1/3)
2相ロッキングの分散システムへの実装法
仮定：データは複数マシンに分散しているとする
集中2PL(centralized 2PL)
ある一つのマシン(Aとする)がロックの許可・解放に責任を持つ
各マシンのトランザクションマネージャは、マシンAのスケジュー
ラ（集中ロックマネージャ）に要求を出す
ロックマネージャがロックを許可すると、データマネージャに直
接データの操作を依頼
データ項目の複製が複数マシンに存在していても良い
91
2相ロッキングの分散実装法(2/3)
プライマリ2PL(primary 2PL)
各データ項目の幾つかの複製から一つを選びプラ
イマリコピー（primary copy）とする
各データ項目のロックの許可・解放は、そのプライ
マリコピーが存在するマシンが責任を持つ
基本的には集中2PLと同様だが、ロックを行うマシ
ンがデータ項目毎に異なるマシンに分散
92
2相ロッキングの分散実装法(3/3)
分散2PL(distributed 2PL)
仮定：データは複数マシンに渡って複製されている
各マシンのスケジューラは、ロックの許可・解放に責任を持
つことに加えて、実際の処理をローカルのデータマネージャ
にも依頼
データのある全てのマシン上で2PLを実行
93
悲観的なタイムスタンプ順序付け
(1/2)
悲観的なタイムスタンプ順序付け（pessimistic
timestamp ordering）
ロッキングとは全く異なる並行性制御アプローチ
トランザクションTに対して、開始した時刻のタイムスタンプts(T)
を割り当て
[重要]Lamportの論理クロックを用いることにより、タイムスタンプの一
意性は保証される
Tの全てのオペレーションにタイムスタンプts(T)を付加
全ての変数xに対して、読み取りタイムスタンプ tsRD(x)および
書き込みタイムスタンプ tsWR(x)を付加
読み取りタイムスタンプ: xを最も最近読んだトランザクションTのタイム
スタンプ ts(T)にセット
書き込みタイムスタンプも同様
94
悲観的なタイムスタンプ順序付け
(2/2)
もし２つのオペレーションが競合したならば、タイム
スタンプが最も早いものを先に処理
スケジューラがトランザクションTからread(T,x)の処理の
依頼を受ける
もし、ts(T)< tsWR(x) ならば、Tの開始後に既に他のトラ
ンザクションによってxに値が書き込まれている
Tをア
ボートさせる
ts(T)> tsWR(x) ならば、xの値を読み込んでもよい
このとき、tsRD(x)をmax{ts(T), tsRD(x)}に更新
writeの場合も同様
95
悲観的なタイムスタンプ順序付けの
動作例(1/2)
トランザクション T1,T2,T3
T1は既にコミット済み(tsRD(x)=
tsWR(x)=ts(T1)<ts(T2),ts(T3))
T2とT3が並行に実行中
(ts(T2)<ts(T3))
T2がxに書き込みたい場合
T3がまだコミットしていない場合
（(a),(b)）
ts(T2)> tsRD(x),
tsWR(x)(=ts(T1))なのでT2はx
へ書き込み可能
T3が既にxを読むか書き込むかし
てコミットした場合（ (c),(d)）
T2はアボートされる(ただし、新
しいタイムスタンプをもらってT2
を再実行すればよい)
96
悲観的なタイムスタンプ順序付けの
動作例(2/2)
T2がxから読み取りたい場合
競合が無い場合（(e)）、読み込み
は直ちに行える
ts(T3)<ts(T2)であるようなT3がx
に書き込んで、まだコミットしてい
ない場合（(f)）、T3がコミットするの
を待ってから読み込む
T3がxに書き込んで既にコミットし
ている場合（(g)）、T2はアボートさ
れる
T3がxに書き込んでまだコミットし
ていない場合（(h)）、T2はアボート
される
97
タイムスタンプ方式とロック方式の
比較
タイムスタンプ方式では、トランザクションが自分
より大きな（時間的に後の）タイムスタンプに遭遇
するとアボートするしかない
同じ状況で、ロック方式であれば、ロックを待つか、ロッ
クを獲得して処理を進めるか、いずれかが可能
タイムスタンプ方式は決してデッドロックしない
ロック方式は一般にデッドロックの可能性がある
98
楽観的タイムスタンプ順序付け
楽観的並行性制御（optimistic concurrency
control）[Kung and Robinson 1981]
基本方針：
とにかくやってみろ（他で何をやっているか気にするな）
何か問題が起きたらその時考えろ
多くの政治家はこのアルゴリズムを使用 ☺
競合が滅多に生じない場合、うまく動作する
99
楽観的タイムスタンプ順序付け
楽観的並行性制御（optimistic concurrency
control）[Kung and Robinson 1981]
競合が生じる場合の処理：
どの変数がread/writeされたかを追跡管理
コミット時に、それらの変数が他のトランザクションによって
変更されたか否かを調査
もし変更されていればアボート, さもなければコミット
利点：デッドロックフリー、並列度最大（どのプロセスにも待ちが
生じることが無い）
欠点：時々失敗（アボート）して最初からやり直す必要がある
システムの負荷が高い場合、失敗の可能性が高くなり、効
率が悪化
100
5章のまとめ
プロセスの同期：プロセス間通信と深く関連
分散システムにおける問題：大域的な時刻の概念が無い
分散システムにおける時刻同期手法
基本的に、時計の値をメッセージでやり取りし、メッセージの伝
送遅延を考慮することで達成
多くの場合、絶対時刻を知る必要が無い
イベント間の相対的な順序が重要
Lamportは論理クロック
の概念を導入し、イベントの順序を保証するメカニズムを提案
101
5章のまとめ（続き）
分散システムの現在状態を知ることは一般に困難
各プロセスが自分のローカル状態、および、伝送中のメッセージの情報を
集めることで、システム全体のグローバル状態を知ることができる
分散スナップショットをとることにより、システムが稼動中にグローバル状態
の情報を得ることが可能
プロセスの同期のためにコーディネータが必要な場合が多い
選任アルゴリズムによってコーディネータがクラッシュしても、代わりのコー
ディネータを選びなおすことが可能
排他制御アルゴリズム: 最も重要な同期アルゴリズム
共有リソースに同時に高々１つのプロセスしかアクセスしないことを保証
コーディネータを選ぶことにより容易に実現可能
完全な分散アルゴリズムは存在するが効率が悪い
トランザクション: 完全に実行するか、全く実行しないかいずれかであるような
処理の単位
並行性制御によって、お互いに干渉しないように並列に複数のトランザクショ
ンを分散実行することが可能
102
演習問題
1.
2.
3.
4.
[Chandy and Lamport 1985]の分散スナップショットアルゴリ
ズムが一貫性のあるグローバル状態を記録することを、本スラ
イドで示した例で記録したグローバル状態に対応するカットを
図示することにより確認せよ。
２つのプロセスが同時にコーディネータのクラッシュを知り、ブリー
アルゴリズムによって同時に選任を開始したら何が起こるか考
察せよ。
上記と同様の状況で、 [Dijkstra and Scholten 1980]の拡散
計算に基づくアルゴリズムによって複数プロセスが同時に選任
を開始したら何が起こるか考察せよ。
逐次化可能性の例（本スライド番号81、教科書図5-25(d)）で
は３つのスケジュールが示されているが、これら以外の可能な
スケジュールをすべて列挙し、それぞれ有効か無効かを示せ。
103