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

無料レッスン

CRDT の基本

レッスン全体が無料でインタラクティブです。ここで読むことも、「ラボを開始」を押してライブラボで実際に実行することもできます。アカウントは不要です。

コンテナラボ読了目安 13分コマンド6個

電車で編集して、家で同期する

電波の届かない電車の中で、スマートフォンから共有のメモを書き換えたとします。家では、誰かがノートパソコンで同じメモを書き換えていました。スマートフォンがつながったとき、どちらの変更も残ってほしいはずです。まずオフラインで動き、あとで同期するアプリをローカルファーストと呼び、そのマージを安全にするデータ型を 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つのコピーを声に出してマージしてください。ご自分のモジュールにコピーして変更するか、レッスンビルダーのラボメニューから一から作ってください。

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

授業で教えていますか?これらのレッスンを生徒に割り当て、採点と生徒ごとのラボを使えます。