電車で編集して、家で同期する
電波の届かない電車の中で、スマートフォンから共有のメモを書き換えたとします。家では、誰かがノートパソコンで同じメモを書き換えていました。スマートフォンがつながったとき、どちらの変更も残ってほしいはずです。まずオフラインで動き、あとで同期するアプリをローカルファーストと呼び、そのマージを安全にするデータ型を CRDT と呼びます。
このレッスンが終わると
メモ
同じデータをオフラインで変えた2つのレプリカが、最後に一致する仕組みを説明できます。
キーワード
- レプリカ:1台の端末にある、データの1つのコピー。
- 同期:レプリカのあいだで変更を送り合うこと。
- マージ:2つのレプリカを1つの状態にまとめること。
- CRDT:どんな順番でマージしても、いつも同じ答えになるデータ型。
- 並行:2つの変更が、お互いを知らずに行われたこと。
- トゥームストーン:何かが消されたことを示す目印。
はじめに:もう知っていること
メモ
頭の中で答えてください。1. 2台のパソコンで同じファイルを保存しました。どちらのコピーが正しいでしょうか。2. 3 + 5 と 5 + 3 は同じですか。3. 4、9、2 のうち、いちばん大きいのはどれですか。答え: それぞれで何を変えたかによる。同じで、順番は関係ない。9。あとの2つの考え方が、CRDT のマージの土台です。
始める前に
メモ
レッスンの上のバーにある ラボを開始 を押し、動いていると表示されるまで待ちます。コンテナはひとつ、jupyter だけで、ターミナルからは docker exec jupyter でその中の Python を使います。これはコンテナの中でコマンドをひとつ実行する命令です。JupyterLab のリンクを押すと、ポート 8888 の画面が開きます。下の 実行 ボタンは、それぞれのコマンドをラボのターミナルに、同じセッションの中で順番に入力します。様子を見たいときや自分で入力したいときは、バーの ターミナルを開く(新しいタブ) を押します。
素朴な同期は編集を失う
スマートフォンは 10:05 にタイトルを、ノートパソコンは 10:07 に本文を変えました。素朴な同期は、最後に保存したメモをまるごと残すので、スマートフォンのタイトルの変更が消えます。表示は True です。項目ごとにマージすると、タイトル "Trip to York" と本文 "Pack bags, book hotel" の両方が残ります。表示は英語で、title はタイトル、body は本文、lost は「消えた」です。
docker exec jupyter python3 steps/lostedit.pyここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。
安全にマージできるカウンター
3つのレプリカが、オフラインでページの閲覧を数えます。3、5、2 です。G-Counter はレプリカごとに1つの数を持ち、レプリカごとに大きい方を取ってマージします。違う順番で同期しても、どのレプリカにも 10 が見え、同じ状態をさらに2回マージしても 10 のままです。報告をそのまま足していくただの数は、同じメッセージを2回数えて 19 になります。
docker exec jupyter python3 steps/gcounter.pyここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。
共有のリストでは、並行な追加が勝つ
アナとベンは、milk(牛乳)と eggs(卵)が入った買い物リストを共有しています。オフラインで、アナは牛乳を消し、ベンは牛乳をもう一度足します。同期のあと、どちらのリストにも卵と牛乳があります。この集合は OR-Set といい、追加のたびにタグを付け、削除は自分が見たタグだけを消します。ベンの新しいタグをアナは一度も見ていないので、牛乳は残ります。
docker exec jupyter python3 steps/orset.pyここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。
確認
ヒント
G-Counter を2回マージしても、何も二重に数えないのはなぜですか。答え: マージはレプリカごとに2つの数の大きい方を取り、5 と 5 の大きい方はやはり 5 だからです。
1行のテキストへの2つの編集
どちらのレプリカも "Hello" から始まります。オフラインで、アナは最後に " world" を足し、ベンは先頭に "Oh, " を足して H を消します。同期のあと、どちらも "Oh, ello world" になります。どの文字にも ID があり、どの文字のあとに入力されたかを覚えているので、挿入はどのレプリカでも同じ意味になります。消した H は、トゥームストーンとして1つ残ります。
docker exec jupyter python3 steps/text.pyここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。
ベクタークロックで、どちらが先かが分かる
どのレプリカも、自分の変更の回数をベクタークロックで数えます。a が書き、b が a から聞かずに書くと、2つのクロックは concurrent(並行)です。そのあと b が a から聞いてもう一度書くと、a は b より before(先)になります。クロックを自分自身と比べると equal(等しい)です。
docker exec jupyter python3 steps/clocks.pyここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。
3つのレプリカ、たくさんの編集、1つの答え
スマートフォン、ノートパソコン、タブレットが、オフラインのあいだに、共有のリストとカウンターをそれぞれ30回ランダムに変えます。そのあとランダムな順番で互いに同期します。3台とも、同じ5つの品物と同じ数 28 で終わります。
docker exec jupyter python3 steps/offline.pyここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。
よくある間違い
注意
いちばん新しい変更がいつも勝つべきだ、と考える人は多いです。スマートフォンの時計は狂うことがあり、「いちばん新しい」はもう一方の編集を捨ててしまいます。CRDT はできるかぎり両方の変更を残し、1つを選ぶときも、どのレプリカも同じように当てはめる決まりで選びます。
ノートブックでの同じ作業
バーから JupyterLab を開き、start.ipynb をダブルクリックします。2つのカウンター、2つの買い物リスト、1行のテキストの2つのコピーをマージします。セルをクリックして Shift と Enter を押すと実行します。最後のセルは自分の問いを書く場所で、crdt.py は全部を読み通せる短さです。
最後の確認
ヒント
見返さずに答えてください。1. 素朴な同期は何を失いましたか。2. G-Counter はどうマージしますか。3. OR-Set で、削除した人が見ていなかった追加はどうなりますか。4. 2つのベクタークロックが concurrent とはどういう意味ですか。答え: スマートフォンのタイトルの変更。レプリカごとに大きい方の数を取る。生き残る。どちらの変更も、もう一方を知らなかった。
先生へ
ヒント
このレッスンは、ラボで進めるレッスンの小さな例です。手順と実行ボタンがレッスンで、ラボは生徒ひとりひとりのコピーです。ラボはサービスがひとつで、Python の標準ライブラリだけで書いた CRDT が入った JupyterLab です。自動採点はありません。生徒は自分のノートブックを JupyterLab からダウンロードして、分かったことの一文といっしょに提出します。学習のポイント:1. 素朴な後勝ちの同期は編集を失う。2. CRDT のマージは、どんな順番でも、繰り返しても同じ答えになる。3. ベクタークロックで「先」と「並行」を見分けられる。よくある思い込み:いちばん新しい変更がいつも勝つべきだと考えること。ラボでは本物の CRDT ライブラリは動きません。Automerge と Yjs は大学向けのモジュールで説明します。用意するもの:ラボとブラウザー。ヒント:2人の生徒に1枚の紙のメモを編集してもらい、2つのコピーを声に出してマージしてください。ご自分のモジュールにコピーして変更するか、レッスンビルダーのラボメニューから一から作ってください。