Distributed systems Principles and Paradigms 6.

Distributed systems Principles and Paradigms
6. Consistency and Replication
B4. グェントアンドゥク
1
全体の内容




Replication と Consistency
Consistency models
Distribution protocols
Consistency protocols
2
1. Replication と Consistency




Replicationとは?
Replicationから生じる問題点
Consistencyとは?
Replication as Scaling technique
3
Replicationとは?

Replication(複製)


Replicationの理由



同じデータを複数にコピーする
Reliability(信頼性)を上げる
Performanceを良くする
例


Web serverをreplicateする
キャッシュ(memory, web pages…)
4
Replicationから生じる問題点


Replicationで信頼性と速度を得る
しかし、色々な問題が出てくる




資源がかかる
管理が難しい
Replicas(複製版)の間の矛盾性(inconsistency):
あるreplicaでのupdateが他のreplicaまですぐ伝達で
きない。その間にreplica毎に異なる
特にreplicas間の無矛盾性(consistency)が重要
5
Consistencyとは?


Replicasの間の無矛盾性
正確に保つと困難


コストが大きい
物理法則にも違反!!


通信速度は光の速度を超えない
色々なモデルがある、モデルごとに
consistencyの意味が違う
6
Replication as Scaling technique

Scaling technique



SystemのScaleに対する技術
Systemのサイズを大きくしても安全性、
performanceを保つ、分散しても小遅延など…
Replicationはscaling techniqueの一つで
ある。

データをそのデータを使用するプロセスの近く
まで持つ…
7
2. Consistency models



2.1. Consistency model とは?
2.2. Data-centric consistency
2.3. Client-centric consistency
8
2.1. Consistency model とは?


Consistencyは共有や複製したデータの
read/write操作での問題
データの全体をdata storeと呼ぶ


Distributed shared memory, distributed shared
database, distributed file system…は皆data store
である。
Consistency modelとは、processesとdata store
の間の契約である。

各プロセスはある規則群を守ったら、data storeは正
しく動作する
9
Consistency model



普通、プロセスのread操作はそのデータの最後
のwrite操作の結果を返す。Distributed
system(複数のreplicaと複数のプロセスがある)
の場合にもこのことを実現したい。
しかし、distributed systemで正確なクコックを実
現するのは困難ので、どのwrite操作が最後の
write操作か分からない。
その代わりに、色々なモデルがある


モデル毎に、read操作の返す結果の制約が違う
Read/write関係が厳密ほど使いやすいが、実現が難
しい
10
2.2. Data-centric consistency models

Data storeについてのシステム全体の
consistencyの表示を提供する



Concurrent processesが同時にdata storeをupdate
することが頻繁に起きると仮定している
そのconcurrencyの上でconsistencyを保つ
Data-centric consistency modelsの中でも、
色々な異なるサブモデルがある

その厳密さ(strictness)により区別する
11
2.2.Data-centric consistency models







Strict consistency
Linearizability & Sequential consistency
Causual consistency
FIFO consistency
Weak consistency
Release consistency
Entry consistency
12
Strict consistency(1)

Strict consistencyモデルでは:



あるデータxの全てのRead操作はそのデータの一番
最近のWrite操作で設定した値を返す(Any read on a
data item x returns a value corresponding to the
result of the most recent write on x)
当然の条件だと見える
このモデルでは、most recent writeを正確に記
述ために、絶対のグローバルな時計が必要
13
Strict consistency(2)

Distributed systemでは実現不可能
Machine
Machine
1
T1
T2(>T1)
Read(x)
Write(x)
2
x
Network
ネットワークでの通信時間がかかるので、T1 < T2と
しても、Machine 2では、WriteはReadより前に発行
14
Sequential & Linearizability Consistensy

Sequential consistency


全ての命令実行(並列命令も含む)がある順序で実行
する時と同じ結果。しかも、同じプロセスの命令は書
かれた順序を保つ。
例:

Wi(x)a: i番目のプロセスがxに値aを書き込む
×
○
P1: W(x)a
P2:
W(x)b
P3:
R(x)b
R(x)a
P4:
R(x)b R(x)a
W(x)a
W(x)b
R(x)b
R(x)a
R(x)a R(x)b
時間
15
Linearizability consistency


Sequential consistencyと同じ条件かつ、
各操作にtimestampが付いて、
tsOp1(x) < tsOp2(x) ⇒ Op1(x)はOp2(x)より
前に実行順序に出現する（tsOp1(x)は操作
Op1のtimestamp)

Sequential consistencyより強い(厳しい)
16
Causal consistency(1)

因果関係のある事象(causally related)



Read(x) … Write(x) (potentially causal related)
Write(x) … Read(x) (causal related)
Causal consistency:

因果関係のある可能なWritesは全てのプロセ
スで同じ順序で見える。因果関係の可能性の
ないWrites(concurrent writes)はどうでも良
い。
17
Causal consistency(2)

例
P1: W(x)a
W(x)c
P2:
R(x)a W(x)b
P3:
R(x)a
R(x)c R(x)b
P4:
R(x)a
R(x)b R(x)c
 W1(x)a と W2(x)bは因果関係になる可能性がある.
W2(x)b と W1(x)cは因果関係可能性がない。

上記の例はsequential consistencyを違反
18
FIFO consistency


同じプロセスのWritesは全てプロセスで書かれ
た順序で見える。異なるプロセスのWritesは各プ
ロセスで順序が違っても良い
例:
P1: W(x)a
P2:
R(x)a W(x)b W(x)c
P3:
R(x)b R(x)a R(x)c
P4:
R(x)a R(x)b R(x)c
上記の例はcausal consistency を違反(W1(x)a と W2(x)bは因果関係可能性
がある)
19
Weak consistency(1)

FIFO consistencyなどでは、あるプロセスでの
Writesは全てのプロセスで同じ順序で見える。




そのWritesに関係ない (最終結果だけ関係ある)プロ
セスにも影響される
Weak consistencyは最終結果だけ伝播する。途
中の過程は伝播しない
Synchronization variable を使う
Synchronization variable Sにはsynchonizeとい
う操作を適用すると、呼ぶプロセスのlocal データ
は全部updateされる(最近の状態になる)
20
Weak consistency(2)

Weak consistencyの性質:



Synchronization variable のaccessはsequentially
consistent (P1とP2が同時にsynchronize(S1),
synchronize(S2)を呼ぶと、その２つ操作の順序は大
切ではない)
Synchronization variableの操作を実行するために、
全てのcopiesで前のWritesが完了しなければならな
い
Synchronizeが完了する前に、read/writeが禁止され
る
21
Weak consistency(3)


Weak consistencyの例
P1: W(x)a W(x)b S
P2:
R(x)a R(x)b S
P3:
R(x)b R(x)a S
Weak consistency違反の例
P1: W(x)a W(x)b S
P2:
S R(x)a
22
Release consistency(1)



Weak consistencyではcritical regionに入ろうと
するか、出ようとするか分からないので、local
writesを全部伝播するかつ他からのwritesを全
部gatherする必要
Release consistencyでは、critical regionに入る
ときに、Acquireという操作をして、出るときに
Release操作をする。
Acquireすると、localデータはupdateされる


Local updateを伝播する必要はない
Releaseすると、local updateは伝播される

Localデータがupdateされない
23
Release consistency(2)

例
P1: Acq(L) W(x)a W(x)b Rel(L)
P2:
P3:



Acq(L) R(x)b Rel(L)
R(x)a
XはLでprotectedされているという
Releaseするときに、updateを全て伝播する必要
はない(他のプロセスはそのデータをまだ使わな
いかもしれない)
そこで、Releaseのときに、updateを伝播しない。
他のプロセスがAcquireするときに、そのプロセス
がupdateを集める

Lazy Release Consistencyと呼ぶ
24
Entry consistency


Release consistencyと似ているが、データ要素
毎に異なるsynchronization variableが永久に付
く。そのためAcquireとReleaseの時のコストが小
さい
保護されたデータを使いたいときに、そのデータ
のLockをAcqquireをしなければならない。
例

P1: Acq(Lx) W(x)a Acq(Ly) W(y)b Rel(Lx) Rel(Ly)
P2:
P3:
Acq(Lx) R(x)a R(y)NIL
Acq(Ly) R(b)b
25
2.3. Client-centric consistency models



データのupdateがあまり並列に行わない
(競合状態にならない)data storeでは、非
常に弱いconsistency modelしか要らない。
そのモデルはeventual consistency
modelと呼ぶ
Eventual consistencyモデルを実現するた
めに、client-centric consistency modelを
使う
26
Eventual consistency



WWWでweb pagesが変わっても、proxyや
cacheで変わらない(すぐ変える必要はない)。
しばらくの間に、だんだん最新の内容にupdate
する。
Eventual consistency


矛盾性が大きい(high degree of inconsistency)
しばらくの間、updateがなければだんだんconsistent
になる(gradually become consistent)
27
Client-centric consistency(1)



Eventual consistencyモデルでは、ある
clientが異なるreplicaと交信すると異なる
結果が出てくる可能性がある
それを解決するために、client-centric
consistencyを紹介
Client-centric consistencyは単一のclient
が data storeにaccessするときの無矛盾
性を保護する
28
Client-centric consistency(2)

記号:


Xi[t]: local copy Liで時刻 tでのxの値
最初状態からtまでのWrite操作の集合をWS
とする。


WS(x1[t1]): t1でL1のxの値がwriteされる
WS(x1[t1];x2[t2]): L1, t1, xのwrite, L2, t2, xの
writeがあった。
29
Client-centric consitency models




Monotonic Reads
Monotonic Writes
Read Your Writes
Writes Follow Reads
30
Monotonic Reads



あるプロセスがxをreadしたら、その後の(そのプ
ロセスの)xのreadが常に前回のreadより新鮮な
値を返す
Monotonic Readsの例
L1: WS(x1)
R(x1)
L2:
WS(x1;x2) R(x2)
Monotonic Reads違反の例
L1: WS(x1)
R(x1)
L2:
WS(x2)
R(x2) WS(x1;x2)
31
Monotonic Writes


あるプロセスのデータxのWrite操作はその
プロセスの次のWrite(x)より前に完了する。
Monotonic Writesの例
L1: W(x1)
L2:
W(x1)

W(x2)
Monotonic Writes違反の例
L1: W(x1)
L2:
W(x2)
32
Read Your Writes



あるプロセスのwriteの結果は常にその後の(同
じプロセスの)readに反映される
Read Your Writesの例
L1: W(x1)
L2:
WS(x1;x2) R(x2)
Read Your Writes違反の例
L1: W(x1)
L2:
WS(x2)
R(x2)
33
Writes Follow Reads



あるプロセスのread(x)の後にwrite(x)を実行し
たら、常にWriteでのxはそのreadした時点の値
より新鮮な値でwriteが行う
Writes Follow Readsの例
L1: WS(x1)
R(x1)
L2:
WS(x1;x2)
W(x2)
Writes Follow Reads違反の例
L1: WS(x1)
R(x1)
L2:
WS(x2)
W(x2)
34
3. Distribution protocols



3.1. Replicaの配置
3.2. Update の伝播
3.3. Epidemic protocols
35
3.1. Replicaの配置

Permanent Replicas(永久のreplicas)



Server-Initiated Replicas



Replicasの初期集合
Distributed data storeから構成する
Serverが開始したreplicas
多くのrequestが出されたところにreplicaを作る
Client-Initiated Replicas


Clientが開始したreplica(Cache)
Clientと同じまたはLAN内のmachineなどで置かれる
36
Server-Initiated replicas: どれをreplicateするか

Access counting: アクセス回数を記録する。
Thresholdを超えたらreplicate

Pの近くのclientsがQに対してファイルFを要求してい
る。その回数をcnt(P,F)とする。Cnt(P,F) > threshold
なら、FをPにコピーする
37
3.2. Update propagation



State vs. Operation
Pull vs. Push Protocols
Unicasting vs. Multicasting
38
State vs. Operations

何を伝播するか?

Updateのnotificationだけ伝播する





Invalidation protocols
Updateされたデータをinvalidateする
そのinvalidatedコピーに操作(write, read)がある
とき実際のupdateをする。
データのコピーを伝播する
Update操作を記録して、伝播する

Write/read列を伝播するなど
39
Pull vs. Push protocols

Push-based(server-based) protocols


Clientが要求しなくてもupdateを伝播する
Pull-based(client-based) protocols

Serverあるいはclientが他のserverにupdate
伝播を要求する
40
Unicasting vs. Multicasting

Unicasting


N個のserversにupdateを伝播したいとき、N
個のmessagesを送る(serverごとに1つ)
Multicasting

N個のserversにupdateを伝播したいとき、1個
のmessageをmulticastする(multicasting
serviceがあったら)。
41
3.3. Epidemic Protocols



Eventual-consistency system のupdate
の伝播はepidemic protocolsと呼ばれるア
ルゴリズムのクラスを使って実現する
Update Propagation Models(Updateの伝
播モデル)
Removing data
42
Update Propagation Models

定義




Infective server(感染server): updateを持って、他の
サーバに広げたいサーバ
Susceptible server: まだupdateされないサーバ
Removed server: もうupdateされた、updateを伝播
する志向のないサーバ
伝播モデル


Anti-entropy
Rumor speading (gossiping)
43
Anti-entropy

あるサーバPがランダム的にサーバQを選んで、
updateをする. ３つの方法:





P が自分のupdateをQにpushするだけ
PがQからのupdateをpullするだけ
PとQがupdateを交換する
感染サーバが多い時には、pushを使うと、
infective毎にsusceptibleを選べる確率が小さい
ので、update伝播が遅い。Pullを使うと、
susceptibleがinfectiveを選べる確率が大きいの
で、update完了が速い
どの方法でも、infectiveが一個あると、しばらく全
てのサーバがupdateされる
44
Rumor Spreading(Gossiping)



UpdateをもらったサーバPはランダムなサーバQを選んで、
updateを伝播する。もしQが既にそのupdateが分かった
ら、Pのupdateのinterestを減らす(Pがremovedになる確
率を1/kだけ増やす)
だんだんやるとPのupdateの伝播興味はなくなる。
Removedになる(Removed確率が1になったとき)。
Gossipingはupdateを速く広げるが、全部のサーバが
updateされる保証はない。
s  e  ( k 1)(1 s )
 残りの率:
 K = 3: s < 0.02
45
Removing data

Epidemicのside-effect: データの削除を広
げるのが難しい


削除したデータがupdateと間違って、再び保
存する
解決法:


削除したデータは記録する(death certificates
を作る)
他のサーバにdeath certificatesを伝播する
46
4. Consistency Protocols


Consistency protocolsはあるconsistencyモデル
の実装を記述する
Primay-based Protocols



Replicated-write Protocols



Remote-Write Protocols
Local-Write Protocols
Active Replication
Quorum-based Protocols
Cache-coherence Protocols
47
4.1.Primary-based Protocols


Data storeの中のデータxはあるprimary
に束縛され、そのprimaryがwrite(x)調整
する。
2種類ある


Remote-write Protocols
Local-write Protocols
48
Remote-write Protocols(1)

全てのread/write操作はある特定の
(remote)serverで行われる


ちょっと改良する ⇒ primary-backup protocols



データはreplicateしない
Writeは一つのサーバだけで行われるが、readは任
意のサーバでできる。Writeの後updateを伝播する必
要
Writeを開始したprocessは長く待たされる
Sequential consistencyを容易に実現できる
49
Remote write protocol(2)
Client
W1
W4
Single
Server
for data
item x
W2
W3
Client
x R1
R4
R2
R3
Data store
W1: Write request
R1: Read request
W2: Forward request to server
R2: Forward request to server
W3: Acknowledge request completed
R3, R4: response
W4: Acknowledge request completed
50
Primary-backup protocol
Client
W1
W5
Primary
server
for item
x
W4
W3
W2
Client
x R1
Backup server
R2
W4
W3
W3
W4
W1: Write request
R1: Read request
W2: Forward request to server
R2: Response
Data store
W3: Tell backup to update
W4: Acknowledge update
W5: Acknowledge write complete
51
Local-Write Protocols


Writeがlocalで行われる
2つの種類ある:

データが一つしかない(no replica)



そのデータを自分のlocalまで持って、writeする
Full migrationが必要
複数のデータがあるが、primaryでしかwrite
できない。


Primaryを自分のlocalまで持って、writeする
Non-blockなら、他のprocessがread可能
52
Local-write protocol(no
replica)
Client
Current Server
for item x
x 1
New server for
item x
4
2
3
1.
Read or Write request
2.
Forward request to current server for x
3.
Move item x to client’s server
4.
Return result of operation on client’s server
Data store
53
Local write protocol(replicas)
54
4.2.Replicated-Write Protocols


Write操作が複数のreplicasで行う可能
2種類ある


Active Replication
Quorum-based Protocols
55
Active Replication



Replica毎に付き一つの特定プロセスがwriteを
担当
Updateはoperationで伝播。つまり、データは伝
播しない、operationだけ伝播する。
操作は全てプロセスで同じ順序で行う必要



Totally-ordered multicastが必要
Coordinatorまで操作列を送って、番号をつけてから、
他のプロセスに送る(sequencer)
Relicated invocationが問題

Ojbect A invoke B.method, B.methodはC.methodを
invoke, Bがreplicatedなら、C.methodは何回も
invokeされる
56
Replicated invocationの解決法



BとCのcoordinatorを作る
B.method()が呼ばれたら、Bの
coordinatorまでforwadする。Coordinator
で操作番号を付けて、invokeする。
Cの帰り値もCのcoordinatorが送る
57
Quorum-based Protocols



Votingを使う
「Replicated itemをRead/Writeする前に複数のサーバ
のpermissionを得なければならない」という仕組み
例:Distributed file systemでファイルがN個にreplicated



あるファイルをwriteするために、[N/2]+1個のサーバのwrite許
可を得る。また、readのとき、version numberを[N/2]+1個の
サーバから得て、全て同じならばOK.
Read要求の途中で他からwriteできない([N/2]+1個の許可を得
られない)ので、常に最新のファイル
一般に、read quorum(Nr), write quorum(Nw)を設定、
それ以上許可があったらOK.
 Nr + Nw > N (read/write 競合を防ぐ)
 Nw > N/2
(write/write競合)
58
4.3.Cache-Coherence Protocols


Cache-coherence protocolsはcacheがserverinitiated replicaとの無矛盾性を保つ方法を記述
Coherence dection strategy

いつinconsistencyが実際にdetectする



Static solution: 例とえば、compilerがやる
Dynamic solution: runtime時にサーバがやる
Coherence enforcement strategy

どうやって無矛盾性を保つか


Updateがあったら、serverがinvalidateを送る
Updateを伝播する
59
まとめ





Replicationとconsistencyを調べた
Replicationで信頼性と高速が得られる
しかし、consistencyを保護しなければなら
ない
Consistencyは色々モデルがある。モデル
ごとにその意味が異なる
Consistencyを実装するために、
consistency protocolsがある。
60

Download Report