2人で1つの文を書く
2人の学生が、共有の文書でグループのレポートを書いています。1人は冒頭の言葉を直し、もう1人は最後に1文を足します。どちらもオフラインです。
テキストは、いちばんマージしにくいデータです。どの文字にも場所があり、誰かが入力すると場所が動くからです。
このレッスンのゴール
メモ
文字が位置を持つテキストの、2つのレプリカをマージできる。
キーワード
| ことば | いみ | れい |
|---|---|---|
| 列の CRDT | テキストのような、順番のあるリストのための CRDT | |
| インデックス | 先頭から数えた文字の場所 | 0, 1, 2 |
| 文字の ID | ほかのどの文字とも重ならない名前 | (6, 'ben') |
| トゥームストーン | 消した文字を、目印として残したもの | |
| インターリーブ | 同時に入力した2つの単語が、1文字ずつ混ざること |
学生が入力するセルは、このプレビューでは空白です。
インデックスの意味は変わる
編集を送るいちばん簡単な方法は、「インデックス0に a を挿入」や「インデックス2を削除」です。しかしインデックスは、相手のレプリカではもう変わっているテキストの先頭から数えます。
アナが先頭に挿入すると、うしろの文字はすべて1つずれます。ベンの「インデックス2を削除」は、別の文字を指すことになります。
試そう: インデックスによる2つの編集
def apply(text, edit):
kind, index, char = edit
if kind == "insert":
return text[:index] + char + text[index:]
return text[:index] + text[index + 1:]
start = "cat"
ana = ("insert", 0, "a") # アナが先頭に a を入れる: "acat"
ben = ("delete", 2, "") # ベンが位置2の t を消す: "ca"
# どちらも自分の編集を先に適用し、そのあと相手の編集を適用します。
on_ana = apply(apply(start, ana), ben)
on_ben = apply(apply(start, ben), ana)
print("アナの画面:", on_ana)
print("ベンの画面:", on_ben)
# ベンが消したかった文字はどれでしょう。アナのコピーではどの文字が消えたでしょう。
考え方1: 隣のあいだの位置
文字ごとに位置の数を付け、その順に並べます。0.4 と 0.5 のあいだに入力するなら 0.45 を選びます。ほかの文字は動きません。
実際のシステムは [4, 5] のような整数のリストを使うので、もう1つ入れる余地がいつもあります。同点はレプリカ名で決めます。これが Logoot の考え方です。
考え方2: ID と親
RGA は文字ごとに、カウンターとレプリカ名でできた ID を付け、どの文字のあとに入力されたかを覚えます。テキストは先頭からたどって読み、新しい子を先に読みます。
削除は文字にトゥームストーンの印を付けるだけです。ほかのレプリカが、まだその文字のあとに入力するかもしれないからです。ラボの rga.py はこの方法で動きます。
1行への2つの編集をマージする
docker exec jupyter python3 steps/text.pyここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。
例: ラボの表示
| 時点 | アナ | ベン |
|---|---|---|
| 共有 | Hello | Hello |
| オフライン | Hello world | Oh, ello (H を削除) |
| 同期のあと | Oh, ello world | Oh, ello world |
| 保存しているもの | トゥームストーン1つ、H | トゥームストーン1つ、H |
学生が入力するセルは、このプレビューでは空白です。
2つの単語が混ざるとき
アナが "cat" と、ベンが "dog" と、同じ場所に同時に入力します。隣のあいだの位置を使うと、2人は同じ数を選び、レプリカ名がそれぞれの組を並べます。
文字が交互に並んでしまいます。RGA は文字を1つ前の文字につなぐので、どちらの単語も崩れません。
2つの単語が混ざる様子を見る
docker exec jupyter python3 steps/interleave.pyここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。
よくある間違い
注意
「どのレプリカも同じテキストで終われば、マージは正しい」と考える人が多いです。"cdaotg" はどのレプリカでも同じですが、誰もそう入力していません。一致は必要条件です。よいテキスト CRDT は、それぞれの人が入力したものもまとまったまま残します。