クリーム色の背景、色付き表示、高コントラスト、大きな文字のほうが読みやすいですか?配色と文字を選ぶと、すべてのページに一度で反映されます。

無料レッスン

レジスタと集合: 「追加が勝つ」とは何か

このレッスンのあとで: 観測削除集合の2つのレプリカをマージできる。

65分のレッスンコマンド2件CRDT ラボ:カウンター、集合、ベクタークロック、テキストで学ぶローカルファーストの同期

戻ってきた牛乳

アナとベンは買い物リストを共有しています。バスの中で、アナは牛乳を買ったのでリストから消します。同じころ、ベンは冷蔵庫が空に見えたので牛乳を足します。

スマートフォンが同期したとき、牛乳はリストにあるべきでしょうか。正解は1つではありません。しかし、どのスマートフォンも同じ答えを出さなければなりません。

このレッスンのゴール

メモ

観測削除集合の2つのレプリカをマージできる。

キーワード

ことばいみれい
レジスタ値を1つだけ持つ CRDT
増えるだけの集合足せるが、決して消せない集合G-Set
タグ1回の追加に付ける、ほかと重ならない名札
OR-Set観測削除集合。削除は自分が見たタグだけを消す
追加が勝つ並行な追加が削除に勝つことadd wins

学生が入力するセルは、このプレビューでは空白です。

レジスタは大きいスタンプを残す

第1回で、後勝ちレジスタに出会いました。CRDT としての状態は、値と、時刻とレプリカ名のスタンプです。マージでは、スタンプの大きい組を残します。

大きい方を取るのは結びなので、レジスタはいつも一致します。ただし、値を1つ捨てることで一致します。色ならそれでよくても、買い物リストでは困ります。

集合を共有する3つの方法

増えるだけの集合: マージは和集合です。何も消せません。 2相集合: 追加の集合と削除の集合を持ち、どちらも和集合でマージします。一度消した要素は、二度と戻りません。 OR-Set: 追加のたびに新しいタグを付けます。削除は、見たことのあるタグを消します。生きたタグがあるあいだ、要素は集合にあります。

試そう: 2相集合

コード: python
# 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、milkeggs、milk
ベンが ben:1 を見て milk を消すeggseggs

学生が入力するセルは、このプレビューでは空白です。

よくある間違い

注意

「削除は、どこから来た要素でも消す」と考える人が多いです。OR-Set の削除は、そのレプリカが見たことのあるタグだけを消します。同じころ別の場所で行われた追加はタグを持ち続けるので、要素は残ります。

多くの編集のあと3つのレプリカを同期する

コマンド
docker exec jupyter python3 steps/offline.py

ここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。

このラボとソースについて: CRDT ラボ:カウンター、集合、ベクタークロック、テキストで学ぶローカルファーストの同期

授業で使いますか?このモジュールを学生に割り当てると、教員用ガイド、自動採点つきの課題、学生ごとのラボを使えます。