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

無料レッスン

G-Counter と PN-Counter のマージ

このレッスンのあとで: 2つのカウンターのレプリカをマージし、どのレプリカも同じ合計にできる。

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

3台のスマートフォンで「いいね」を数える

ある投稿に、3台のスマートフォンから「いいね」が付きます。どの端末も、しばらくオフラインです。同期したとき、合計はすべての「いいね」を1回ずつ数えるべきです。数え漏れも、二重に数えることもあってはいけません。

共有する数が1つあるだけでは、これはできません。CRDT のカウンターならできます。

このレッスンのゴール

メモ

2つのカウンターのレプリカをマージし、どのレプリカも同じ合計にできる。

キーワード

ことばいみれい
CRDTレプリカがいつも同じ状態にマージされるデータ型
状態ベースレプリカが状態全体を送り、それをマージする方式
結び順番に関係なく、繰り返しても安全なマージjoin
G-Counter増えるだけのカウンター。レプリカごとに1つの数を持つ
PN-Counter増える分と減る分の、2つの G-Counter

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

失敗しようのないマージ

状態ベースの CRDT は状態全体を送り、受け取ったレプリカがそれをマージします。マージは結びでなければならず、3つの性質を持ちます。

可換: a に b をマージしても、b に a をマージしても同じです。 結合的: 3つをマージするとき、どこから組んでも同じ結果です。 冪等: 同じ状態を2回マージしても、何も変わりません。

これなら、メッセージが遅れても、2回届いても、順番が入れ替わっても、レプリカは一致します。

G-Counter はレプリカごとに数を持つ

どのレプリカも、自分の欄にだけ足します。値は、すべての欄の合計です。

マージでは、レプリカごとに大きい方の数を取ります。2つの数の大きい方を取る操作は可換で、結合的で、冪等なので、マージ全体が結びになります。大きい方を取る代わりに足すと、冪等ではなくなります。

3つの G-Counter を2通りの順でマージする

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

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

例: ラボの表示

時点スマートフォンノートパソコンタブレット
同期の前352
同期の後、どの順番でも101010
スマートフォンがさらに2回マージ101010
ただの数で、同じ報告が2回届く19なしなし

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

試そう: 6通りの順番、1つの合計

コード: python
from itertools import permutations

def merge(a, b):
    out = dict(a)
    for name, count in b.items():
        out[name] = max(out.get(name, 0), count)
    return out

# オフラインの3台のスマートフォンが数えた歩数
ana = {"ana": 4}
ben = {"ben": 7}
cai = {"cai": 2, "ana": 1}   # cai は前に ana から聞いている

for order in permutations([ana, ben, cai]):
    state = {}
    for replica in order:
        state = merge(state, replica)
    print(sum(state.values()), state)
# どの順番でも合計は同じです。merge を max ではなく足し算にしてみましょう。

よくある間違い

注意

「マージでは2つのカウンターを足せばよい」と考える人が多いです。それでは、同じ状態が2回届いたときに二重に数えます。ネットワークでは実際に起きます。代わりにレプリカごとに大きい方を取れば、マージを繰り返しても害はありません。

減らすには2つ目のカウンターが要る

G-Counter は減らせません。小さい数は、マージのたびに負けてしまうからです。そこで PN-Counter は、G-Counter を2つ持ちます。1つは増えた分を、もう1つは減った分を数えます。

どちらも、レプリカごとに大きい方を取ってマージします。値は、増えた分から減った分を引いた数です。

「いいね」と取り消しをマージする

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

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

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

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