質問より先に届く返事
グループチャットで、返事が元のメッセージより先に表示されることがあります。ネットワークが、間違った順番で届けたのです。
レプリカにも同じ問題があります。うまくマージするには、どの変更が先だったか、そして誰も順番を決めていない2つの変更はどれかを、レプリカが知る必要があります。
このレッスンのゴール
メモ
2つのベクタークロックを比べ、どちらの変更が先に起きたかを言える。
キーワード
| ことば | いみ | れい |
|---|---|---|
| 先に起きた | 一方の変更を知ったうえで、もう一方の変更が行われたこと | happened before |
| ベクタークロック | レプリカごとに1つのカウンター。変更のたびに一緒に運ぶ | {"a": 1, "b": 2} |
| 操作ベースの CRDT | 状態全体の代わりに操作を送る CRDT | |
| 因果順の配送 | 変更を、それが見た変更のあとでだけ適用すること | |
| デルタ | 状態のうち、変わった部分だけ |
学生が入力するセルは、このプレビューでは空白です。
ベクタークロックはレプリカごとに数える
どのレプリカも、すべてのレプリカのカウンターを持ちます。変更の前に、自分のカウンターに1を足します。ほかのレプリカから聞いたら、カウンターごとに大きい方を取ります。
2つのクロックは場所ごとに比べます。a のすべての場所が b 以下で、どこか1つが小さければ、a は b より先に起きました。どちらにも相手より大きい場所があれば、並行です。
ベクタークロックを比べる
docker exec jupyter python3 steps/clocks.pyここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。
例: ラボの表示
| クロック | 比べた結果 | 理由 |
|---|---|---|
| a {a: 1} と b {b: 1} | 並行 (concurrent) | どちらにも大きい場所が1つある |
| a {a: 1} と b {a: 1, b: 2} | a が先 (before) | b は a を聞いてから書いた |
| c {a: 1, b: 2, c: 1} と a | c があと (after) | c は、a を聞いた b を聞いた |
| a と a のコピー | 等しい (equal) | すべての場所が同じ |
学生が入力するセルは、このプレビューでは空白です。
状態の代わりに操作を送る
状態ベースの CRDT は状態全体を送るので、大きくなることがあります。操作ベースの CRDT は、「milk を足す」のような操作を1つずつ送るので、小さく済みます。
しかし操作は、どれもちょうど1回届かなければなりません。そして変更は、それが見た変更のあとに届かなければなりません。そうでないと、削除が、消すはずの追加より先に届くことがあります。
試そう: 入れ替わった2つの操作
# 操作ベース: レプリカは状態全体ではなく、操作を送ります。
# アナが milk を足し、そのあと消します。カイは2つの操作を受け取ります。
def apply(items, op):
kind, item = op
if kind == "add":
return items | {item}
return items - {item}
first = ("add", "milk")
second = ("remove", "milk")
in_order = apply(apply(set(), first), second)
swapped = apply(apply(set(), second), first)
print("順番どおりに届く:", sorted(in_order))
print("逆の順番で届く: ", sorted(swapped))
# ネットワークが2つのメッセージを入れ替えました。先に届いた削除を、
# カイはどうすべきだったでしょうか。
よくある間違い
注意
「タイムスタンプがあれば変更を並べられる」と考える人が多いです。2台の端末の時計は食い違いますし、時刻では2つの変更が並行だったことを言えません。ベクタークロックなら言えます。各レプリカが何を聞いていたかを記録しているからです。
デルタ: 両方のよいところ
デルタ状態の CRDT は、相手のレプリカが最後に聞いたとき以降に変わった部分だけを送ります。マージには、状態全体と同じ結びを使います。
そのため、デルタが失われても繰り返されても、状態と同じく害はありません。それでいてメッセージは、操作と同じく小さいままです。相手がすでに何を持っているかは、ベクタークロックが教えます。
状態全体の代わりにデルタを送る
docker exec jupyter python3 steps/delta.pyここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。