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ここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。
例: ラボの表示
| 時点 | スマートフォン | ノートパソコン | タブレット |
|---|---|---|---|
| 同期の前 | 3 | 5 | 2 |
| 同期の後、どの順番でも | 10 | 10 | 10 |
| スマートフォンがさらに2回マージ | 10 | 10 | 10 |
| ただの数で、同じ報告が2回届く | 19 | なし | なし |
学生が入力するセルは、このプレビューでは空白です。
試そう: 6通りの順番、1つの合計
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ここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。