収束だけでは不十分
Convergence Is Not Enough (inkandswitch.com)
要約
Livelymergeプロジェクトは、プログラムのヒープ全体をAutomergeドキュメントとして扱い、リアルタイムでのマージを目指しています。しかし、Automergeの収束保証だけでは、プログラムの不変条件(例: リストの循環がない、各要素が一意である)を満たせない問題が発生します。本稿では、この「意図」ではなく「書き込み」をマージする問題点を具体例で示し、高レベルな操作をマージする「マージ対応型データ構造」という解決策の方向性を提案しています。
全文翻訳
収束だけでは不十分
はじめに
Livelymerge プロジェクトにおいて、Dan Ingalls、Peter van Hardenberg、そして私(Alex Warth)は、Lively Kernelライクなシステムを構築しています。このシステムのヒープ — すべてのオブジェクト、クラス、メソッド — はAutomergeドキュメントとなります。このシリーズの最初のノートでの提案は、これによりマージが「無料」で得られるというものでした。複数のユーザーが同じオブジェクトメモリを共有し、(オフラインでも)同時に作業でき、Automergeがすべてを調和させます。
また、ライブシステムの状態をマージすることは簡単な問題ではなく、オブジェクトの不変条件が侵害されない保証はないとも書きました。このノートでは、具体的な例を挙げて、その問題に正面から向き合います。まだ解決策はありません — これは認識であり、勝利宣言ではありません — しかし、有望だと考えている解決策の可能性をスケッチします。皆さんのアイデアもぜひお聞かせください。
例A:連結リスト
Automergeの約束は収束です。2つのクライアントが変更を交換した後、それらが同じ状態に到達することは保証されます。しかし、その状態がプログラムが許容できるものであるとは限りません。公平を期すために言うと、多くのアプリケーション — ドキュメント、ToDoリスト、スケッチ — では、Automergeのマージは期待どおりに機能します。しかし、LMではもっと奇妙なことをしています。それは、実行中のプログラムのヒープ、ポインタも含めてマージすることです。これはAutomergeの快適ゾーンを大きく外れており、このノートはその領域で何が起こるかについてです。
ノードが別のノードを指すnextプロパティを持つ、プログラマーがLMで構築するであろう方法で構築された、1 → 2 → 3 → 4 を含む素朴な連結リストを考えてみましょう。次に、2つのクライアントがこれを同時に変更すると仮定します。
- クライアントAは2と3をスワップします。
1.next ← 3、2.next ← 4、3.next ← 2と書き込みます。彼らのリストは 1, 3, 2, 4 となります。 - クライアントBは3と4をスワップします。
2.next ← 4、3.next ← null、4.next ← 3と書き込みます。彼らのリストは 1, 2, 4, 3 となります。
これらの変更が同期したときに何が起こるか見てみましょう。Automergeがそれらをどのようにマージするかは次のとおりです。各クライアントの変更はトランザクションであり、マージは一方のトランザクションの書き込みが適用され、次に他方の書き込みが適用されるかのように動作します — Automergeは決定論的に2つの順序のいずれかを選択し、両方のクライアントは同じ順序を取得します。(したがって、個々の書き込みの任意のインターリーブは不可能であり、最終的に到達できる状態の数が制限されます。)後続のトランザクションが触れなかった書き込みは、先行するものから生き残ります。両方のトランザクションが書き込んだ場所では、後続のものが勝ちます。
[画像: Automergeのマージプロセスを示す図]
2つの可能な順序が実際に何を生み出すか見てみましょう。1.nextはどちらの場合もAから来ます(Bはそれを書き込んでいません)、4.nextはどちらの場合もBから来ますが、3.next — 両方のトランザクションが書き込んだもの — は後から来た方に渡されます。
- Aの後にB (
3.next = null): 1からたどると 「1, 3」 — リストが切り詰められ、ノード2と4は脇に追いやられます。 - Bの後にA (
3.next = 2): 1からたどると 「1, 3, 2, 4, 3, 2, 4, …」 — リストにサイクルが含まれ、それを歩くコードは決して終了しません。
強調させてください:Automergeはここで何も間違ったことはしていません。両方のクライアントは、約束どおり、決定論的に同じ結果に収束します。問題は、Aの後にBの書き込みを再生することが、Aの後にBの意図を実行することと同じではないということです。クライアントBは、元のリスト、1 → 2 → 3 → 4 — マージ後にはもはや存在しない状態 — を見て、これらの3つの書き込みを計算しました。もしAの変更の後にBの「3と4のスワップ」が実際に実行されていれば、それは異なる書き込みと完全に正常なリストを生成したでしょう。マージは意図ではなく効果を再生し、プログラマーの不変条件 — 各ノードは正確に1回出現する、サイクルがない、リストは終了する — は、Automergeが見ることができるどこにも書き込まれていませんでした。収束だけでは不十分なのです。
これは連結リストだけの問題ではない
nextポインタで連結リストを構築しないことで、この特定の問題を回避できます。Automergeには、うまく機能するマージセマンティクスを持つ組み込みデータ型があります — その配列(私たちのオブジェクトモデルが直接公開しているもの)は、期待どおりの挿入と削除をマージし、さまざまな種類のマップは簡単に表現できます。私たちは、システムの中心にあるグラフィカルフレームワークであるMorphicで、これを実践で強く活用しています。(MorphicはSelfプログラミング言語で生まれ — Maloney et al.を参照 — 後にSqueakとDanのLively Kernelで使用されました。Morphicでは、画面上のすべてがmorphです。これは他のモーフを含むことができるオブジェクトであり、ボタンやテキストまで続きます。)各モーフのsubmorphsリストはAutomerge配列であり、2人のユーザーからの同時追加はうまくインターリーブされます。
しかし、これらのデータ型を組み合わせると、すべてが不確かになります — そして、プログラミングではこのようなことが非常に頻繁に起こります!マージはトランザクション全体を順序付けしますが、それでも書き込みを盲目的に再生するため、複数のプロパティまたはオブジェクトにまたがる不変条件はすべて、それに不可視です。
- 二重連結リスト(
nextとprevは互いに鏡像である必要があります)。 - ツリー(Morphic自体:各モーフの
ownerは、そのオーナーのsubmorphsと一致する必要があります — 同じモーフを同時に再親化する2人のユーザーは、今日これを壊す可能性があります)。 - 要約するコレクションと一致する必要があるキャッシュされたカウントまたはインデックス。
- 何かに対する「各要素は正確に1回出現する」という制約。
LMのようなシステム — ヒープがドキュメントそのものであり、ユーザーが好きなデータ構造を構築することが奨励される — では、これはコーナーケースではありません。これは私たちが積極的に考えている問題です。
とはいえ、予想よりも頻繁に私たちを悩ませることはありませんでした。注意深いプログラミング — 可能な限りAutomergeの組み込みデータ型に依存し、矛盾する可能性のある冗長な表現を避ける — により、日常的なマルチユーザー使用でうまく機能するシステムを構築することができました。(注意深いプログラミングは解決策ではありませんが、解決策を待っている間に行うことです。)
私たちが好む方向性:マージを意識したデータ構造
今日、マージはプログラマーが実際に気にする抽象化の下の、生のオブジェクトグラフのレベルで発生します。上記の診断を考慮すると、自然な動きは、それがコンパイルされた書き込みではなく、意図をマージすることです。そして、意図は「3.nextをnullに設定する」ではなく、ましてや「3と4をスワップする」 — これもまだ実装ですが、1レベル上です — ではありません。意図とは、プログラマーが抽象型のレベルで言うであろうことです。「この値をリストから削除する」、「この値をその値の後ろに挿入する」。
Automergeはすでに正確にこの方法で動作します — ただし、組み込み型に対してのみです。Automergeリストへの変更は、ポインタ書き込みではなく、挿入および削除の操作(それが実際のAutomerge用語です)としてドキュメントの履歴に記録されます。そして、まさにそれが、これらのリストに対する同時編集がうまくマージされる理由です。そこで、私たちが興味深いと考えているアイデアは次のとおりです。もしAutomergeが、プログラマー定義のデータ構造がそれらであると宣言できる型 — リストのような、マップのような、カウンターのような — の概念を公開したらどうなるでしょうか?ドキュメント内の表現はプログラマー次第ですが、読み書きはその型のインターフェースを通過し、操作として記録されるのは、型のより高レベルの語彙になります。マージは、それらの操作のマージを意味し、セマンティクスは型ごとに1回定義されます。プログラマーが組み込み型を採用するだけでなく、完全に新しい型を定義できるなら、さらに良いでしょう。 nontrivialな型に対して厳密に行うことができるという励みになる先例があります。Kleppmann et al.のツリーの移動操作は、「再親化がサイクルを作成しない」ことをマージに直接組み込んでいます。そのアルゴリズムの基盤となる技術は驚くほど広く一般化されます。すべての操作を単一の決定論的な順序(例:タイムスタンプによる)で再生し、各操作を不変条件に対してチェックし、違反する操作をスキップします。すべてのクライアントが同じ操作を同じ順序で再生するため、収束は無料で得られ、不変条件は構築によって保持されます。(ECROもこのアイデアに基づいたシステムです。)ただし、これは完璧な答えではありません。実行時に有効だった操作が、より低いタイムスタンプを持つ操作が遅れて到着したときに遡って無効になる可能性があるため、ユーザーは以前に受け入れられた作業がロールバックされるのを見る可能性があります。そして、ユーザー定義型に関するより広範な未解決の質問は残ります。型の操作は交換可能でなければならないか、交換できない場合の解決策を決定論的に提供しなければなりません。システムがプログラマーがその基準を満たす(またはチェックする)のをどのように助けるかは明らかではありません。
私たちはこの領域をさまよっている唯一の人々ではありません。Martin Kleppmann、Vincent Liu、Owen Lynch、およびその共同研究者は、スキーマ、クエリ、およびマイグレーションのための表現力豊かな言語を備えたマージ可能なデータベースであるColnで、この問題に正面から取り組んでいます。Colnでは、データに対する制約を宣言できます — 例えば「これは二重連結リストです」 — そして、違反に対して非常に厳格な方針をとります。マージが制約を壊す場合、マージは単純に拒否され、マージが許可される前にデータを制約を満たす状態に戻すのはユーザー(またはAI)次第です。MartinのConvergence読書リストも、不変条件と調整の間のつながりへの良い入り口です。この問題について考えたことがある場合 — または、より良い解決策を持っている場合 — 話しましょう!
次回
次のノートでは、これらすべてを具体化するオブジェクトモデルについて説明します。Automergeドキュメントを、オブジェクトテーブル、プロキシ、ガベージコレクションなど、通常のJavaScriptヒープのように見せ、感じさせる方法です。