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

無料レッスン

ベクタークロック、操作、デルタ

このレッスンのあとで: 2つのベクタークロックを比べ、どちらの変更が先に起きたかを言える。

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

質問より先に届く返事

グループチャットで、返事が元のメッセージより先に表示されることがあります。ネットワークが、間違った順番で届けたのです。

レプリカにも同じ問題があります。うまくマージするには、どの変更が先だったか、そして誰も順番を決めていない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} と ac があと (after)c は、a を聞いた b を聞いた
a と a のコピー等しい (equal)すべての場所が同じ

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

状態の代わりに操作を送る

状態ベースの CRDT は状態全体を送るので、大きくなることがあります。操作ベースの CRDT は、「milk を足す」のような操作を1つずつ送るので、小さく済みます。

しかし操作は、どれもちょうど1回届かなければなりません。そして変更は、それが見た変更のあとに届かなければなりません。そうでないと、削除が、消すはずの追加より先に届くことがあります。

試そう: 入れ替わった2つの操作

コード: python
# 操作ベース: レプリカは状態全体ではなく、操作を送ります。
# アナが 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

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

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

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