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

無料レッスン

マージできるテキスト: 列の CRDT

このレッスンのあとで: 文字が位置を持つテキストの、2つのレプリカをマージできる。

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

2人で1つの文を書く

2人の学生が、共有の文書でグループのレポートを書いています。1人は冒頭の言葉を直し、もう1人は最後に1文を足します。どちらもオフラインです。

テキストは、いちばんマージしにくいデータです。どの文字にも場所があり、誰かが入力すると場所が動くからです。

このレッスンのゴール

メモ

文字が位置を持つテキストの、2つのレプリカをマージできる。

キーワード

ことばいみれい
列の CRDTテキストのような、順番のあるリストのための CRDT
インデックス先頭から数えた文字の場所0, 1, 2
文字の IDほかのどの文字とも重ならない名前(6, 'ben')
トゥームストーン消した文字を、目印として残したもの
インターリーブ同時に入力した2つの単語が、1文字ずつ混ざること

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

インデックスの意味は変わる

編集を送るいちばん簡単な方法は、「インデックス0に a を挿入」や「インデックス2を削除」です。しかしインデックスは、相手のレプリカではもう変わっているテキストの先頭から数えます。

アナが先頭に挿入すると、うしろの文字はすべて1つずれます。ベンの「インデックス2を削除」は、別の文字を指すことになります。

試そう: インデックスによる2つの編集

コード: python
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

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

例: ラボの表示

時点アナベン
共有HelloHello
オフラインHello worldOh, ello (H を削除)
同期のあとOh, ello worldOh, ello world
保存しているものトゥームストーン1つ、Hトゥームストーン1つ、H

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

2つの単語が混ざるとき

アナが "cat" と、ベンが "dog" と、同じ場所に同時に入力します。隣のあいだの位置を使うと、2人は同じ数を選び、レプリカ名がそれぞれの組を並べます。

文字が交互に並んでしまいます。RGA は文字を1つ前の文字につなぐので、どちらの単語も崩れません。

2つの単語が混ざる様子を見る

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

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

よくある間違い

注意

「どのレプリカも同じテキストで終われば、マージは正しい」と考える人が多いです。"cdaotg" はどのレプリカでも同じですが、誰もそう入力していません。一致は必要条件です。よいテキスト CRDT は、それぞれの人が入力したものもまとまったまま残します。

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

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