言葉より重い文書
共有のレポートの画面に、4000字が表示されているとします。裏では、これまでに入力して消したすべての文字を保存しているかもしれません。
消したテキストを残すのは、マージを安全に保つためです。このレッスンでは、それをいつ捨ててよいか、そして本物のローカルファーストのライブラリがどう扱うかを考えます。
このレッスンのゴール
メモ
どのトゥームストーンをすべてのレプリカが見ていて、安全に捨てられるかを判断できる。
キーワード
| ことば | いみ |
|---|---|
| コンパクション | もう誰も必要としないデータを捨てること |
| 安定 | すべてのレプリカが見たこと |
| ガベージコレクション | 何も使っていないメモリを解放すること |
| Automerge | JSON のような文書のための CRDT ライブラリ |
| Yjs | エディターのための共有型をそろえた CRDT ライブラリ |
学生が入力するセルは、このプレビューでは空白です。
トゥームストーンが残る理由
RGA では、どの文字も、そのあとに入力された文字を覚えています。削除をまだ聞いていないレプリカは、消された文字のあとに入力するかもしれません。
その挿入が届いたとき、ぶら下げる先として消された文字がまだ必要です。だからトゥームストーンは、すべてのレプリカが削除を見るまで残ります。
試そう: 1時間の編集
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文字を削除 | 10 | 190 | 190 |
| 200文字を入力し、最初の190文字を削除 | 10 | 190 | 0 |
学生が入力するセルは、このプレビューでは空白です。
ラボのテキスト CRDT の機能を一覧にする
docker exec jupyter grep -n "def " rga.pyここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。
本物のライブラリが加えるもの
Automerge は文書を JSON のように扱い、マップ、リスト、テキスト、カウンターを持ちます。変更の履歴を残すので、誰が何を変えたかが分かります。レプリカは同期のプロトコルで変更を交換します。
Yjs は、テキスト、配列、マップなどの共有型を、エディター向けに用意しています。レプリカは状態ベクトルを送り、足りない更新だけを受け取ります。状態ベクトルは、ベクタークロックによく似たレプリカごとの数です。
おもちゃ、Automerge、Yjs を並べる
ラボの rga.py と同じく、どちらのライブラリも、挿入した要素ごとに ID を付け、消した要素を残してマージを安全に保ちます。Yjs は小さな目印を残したまま、消したテキストの中身を捨てられます。
おもちゃと違うのは速さと大きさです。小さなバイナリ形式、続けて入力した文字をまとめて保存する工夫、テスト済みのコードがあります。固定したイメージにどちらも入っていないので、ラボでは言葉で比べます。
よくある間違い
注意
「削除すれば、すぐに容量が空く」と考える人が多いです。CRDT では、削除はたいてい目印を1つ足すので、文書は大きくなります。容量が戻るのは、すべてのレプリカが削除を見たとコンパクションが証明できたときだけです。