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

無料レッスン

トゥームストーンと CRDT ライブラリ

このレッスンのあとで: どのトゥームストーンをすべてのレプリカが見ていて、安全に捨てられるかを判断できる。

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

言葉より重い文書

共有のレポートの画面に、4000字が表示されているとします。裏では、これまでに入力して消したすべての文字を保存しているかもしれません。

消したテキストを残すのは、マージを安全に保つためです。このレッスンでは、それをいつ捨ててよいか、そして本物のローカルファーストのライブラリがどう扱うかを考えます。

このレッスンのゴール

メモ

どのトゥームストーンをすべてのレプリカが見ていて、安全に捨てられるかを判断できる。

キーワード

ことばいみ
コンパクションもう誰も必要としないデータを捨てること
安定すべてのレプリカが見たこと
ガベージコレクション何も使っていないメモリを解放すること
AutomergeJSON のような文書のための CRDT ライブラリ
Yjsエディターのための共有型をそろえた CRDT ライブラリ

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

トゥームストーンが残る理由

RGA では、どの文字も、そのあとに入力された文字を覚えています。削除をまだ聞いていないレプリカは、消された文字のあとに入力するかもしれません。

その挿入が届いたとき、ぶら下げる先として消された文字がまだ必要です。だからトゥームストーンは、すべてのレプリカが削除を見るまで残ります。

試そう: 1時間の編集

コード: python
import random

rng = random.Random(3)
stored = 0       # これまでに入力した文字、項目として残る
visible = 0      # 今もテキストにある文字

for minute in range(60):        # 1時間の編集
    typed = rng.randint(20, 40)
    deleted = min(visible + typed, rng.randint(10, 35))
    stored += typed
    visible += typed - deleted

tombstones = stored - visible
print("見えている文字:", visible)
print("保存している項目:", stored)
print("トゥームストーン:", tombstones)
print("トゥームストーンの割合:", round(100 * tombstones / stored), "%")
# 削除を rng.randint(25, 40) にしてみましょう。割合はどうなるでしょうか。

捨てるための2つの決まり

安定: すべてのレプリカが削除を見ていること。すべてのレプリカのベクタークロックについて、場所ごとに最小の数を取ります。トゥームストーンのカウンターがそれ以下なら、安定です。

何もぶら下がっていない: テキストに残す文字の中に、そのあとに入力されたものがないこと。あれば、その文字が居場所を失います。

2つの文書をコンパクションする

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

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

例: ラボの表示

文書見える文字トゥームストーンコンパクションで捨てた数
200文字を入力し、最後の190文字を削除10190190
200文字を入力し、最初の190文字を削除101900

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

ラボのテキスト CRDT の機能を一覧にする

コマンド
docker exec jupyter grep -n "def " rga.py

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

本物のライブラリが加えるもの

Automerge は文書を JSON のように扱い、マップ、リスト、テキスト、カウンターを持ちます。変更の履歴を残すので、誰が何を変えたかが分かります。レプリカは同期のプロトコルで変更を交換します。

Yjs は、テキスト、配列、マップなどの共有型を、エディター向けに用意しています。レプリカは状態ベクトルを送り、足りない更新だけを受け取ります。状態ベクトルは、ベクタークロックによく似たレプリカごとの数です。

おもちゃ、Automerge、Yjs を並べる

ラボの rga.py と同じく、どちらのライブラリも、挿入した要素ごとに ID を付け、消した要素を残してマージを安全に保ちます。Yjs は小さな目印を残したまま、消したテキストの中身を捨てられます。

おもちゃと違うのは速さと大きさです。小さなバイナリ形式、続けて入力した文字をまとめて保存する工夫、テスト済みのコードがあります。固定したイメージにどちらも入っていないので、ラボでは言葉で比べます。

よくある間違い

注意

「削除すれば、すぐに容量が空く」と考える人が多いです。CRDT では、削除はたいてい目印を1つ足すので、文書は大きくなります。容量が戻るのは、すべてのレプリカが削除を見たとコンパクションが証明できたときだけです。

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

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