戻ってきた牛乳
アナとベンは買い物リストを共有しています。バスの中で、アナは牛乳を買ったのでリストから消します。同じころ、ベンは冷蔵庫が空に見えたので牛乳を足します。
スマートフォンが同期したとき、牛乳はリストにあるべきでしょうか。正解は1つではありません。しかし、どのスマートフォンも同じ答えを出さなければなりません。
このレッスンのゴール
メモ
観測削除集合の2つのレプリカをマージできる。
キーワード
| ことば | いみ | れい |
|---|---|---|
| レジスタ | 値を1つだけ持つ CRDT | |
| 増えるだけの集合 | 足せるが、決して消せない集合 | G-Set |
| タグ | 1回の追加に付ける、ほかと重ならない名札 | |
| OR-Set | 観測削除集合。削除は自分が見たタグだけを消す | |
| 追加が勝つ | 並行な追加が削除に勝つこと | add wins |
学生が入力するセルは、このプレビューでは空白です。
レジスタは大きいスタンプを残す
第1回で、後勝ちレジスタに出会いました。CRDT としての状態は、値と、時刻とレプリカ名のスタンプです。マージでは、スタンプの大きい組を残します。
大きい方を取るのは結びなので、レジスタはいつも一致します。ただし、値を1つ捨てることで一致します。色ならそれでよくても、買い物リストでは困ります。
集合を共有する3つの方法
増えるだけの集合: マージは和集合です。何も消せません。 2相集合: 追加の集合と削除の集合を持ち、どちらも和集合でマージします。一度消した要素は、二度と戻りません。 OR-Set: 追加のたびに新しいタグを付けます。削除は、見たことのあるタグを消します。生きたタグがあるあいだ、要素は集合にあります。
試そう: 2相集合
# 2相集合: 追加の集合と削除の集合を1つずつ持ちます。
# 追加されて、一度も削除されていない要素が集合に入っています。
def members(state):
return sorted(state["added"] - state["removed"])
def merge(a, b):
return {"added": a["added"] | b["added"],
"removed": a["removed"] | b["removed"]}
ana = {"added": {"milk", "eggs"}, "removed": set()}
ben = {"added": {"milk", "eggs"}, "removed": set()}
ana["removed"].add("milk") # アナがオフラインで milk を消す
ben["added"].add("milk") # ベンがオフラインで milk をもう一度足す
both = merge(ana, ben)
print("同期のあと:", members(both))
both["added"].add("milk") # もう一度 milk を足してみる
print("もう一度足すと:", members(both))
# このリストに milk を戻せる人はいるでしょうか。
新しい追加が生き残る理由
アナの削除が消せるのは、アナが見たことのあるタグだけです。ベンの追加は、アナが一度も見ていない新しいタグを作りました。だから、それは消されません。
マージのあとも牛乳には生きたタグがあり、リストに残ります。この決まりを「追加が勝つ」と呼びます。すべてのタグを見たあとの削除なら、要素はきちんと消えます。
OR-Set で牛乳を残す
docker exec jupyter python3 steps/orset.pyここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。
例: ラボの表示
| 時点 | アナ | ベン |
|---|---|---|
| はじめ | eggs、milk (タグ ana:1) | eggs、milk (タグ ana:1) |
| オフライン | milk を消す: ana:1 が消える | milk を足す: タグ ben:1 |
| 同期のあと | eggs、milk | eggs、milk |
| ベンが ben:1 を見て milk を消す | eggs | eggs |
学生が入力するセルは、このプレビューでは空白です。
よくある間違い
注意
「削除は、どこから来た要素でも消す」と考える人が多いです。OR-Set の削除は、そのレプリカが見たことのあるタグだけを消します。同じころ別の場所で行われた追加はタグを持ち続けるので、要素は残ります。
多くの編集のあと3つのレプリカを同期する
docker exec jupyter python3 steps/offline.pyここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。