収束は意図ではない：ローカルファーストの共同作業の意味論

二人の利用者が誤った答えで一致することがある

接続されていない二人の編集者が、最後の利用可能なレビュー枠を予約する状況を考える。各レプリカには残り一枠と表示され、各編集者はローカルでの予約に成功する。レプリカが再接続すると、マージは両方の予約を保持し、完全に収束することができる。最終状態はデバイス間で一致しているが、容量の規則には違反している。ネットワークの再試行や決定的なタイブレーク規則によって、二人に約束された内容が自動的に解決されるわけではない。

この例は、代数的性質と製品の契約を区別する。収束が問うのは、同じ関連情報を持つレプリカが同じ状態を得るかどうかである。意図が問うのは、結果の状態が利用者の行為を許容可能な形で表しているかどうかである。不変条件は、そもそもどの状態が許されるかを制約する。共同作業システムは、どの行為をオフラインで受理でき、どの行為には調整、予約済みの権利、または後で拒否される可能性の明示が必要かを決めなければならない。

選定した文献が基礎を確立する

Shapiroらは、強結果整合性の十分条件を示し、状態ベースと操作ベースの構成を区別している。KleppmannとBeresfordは、入れ子構造と並行更新を支援する複製JSONデータ型の形式的意味論を提示している。ローカルファーストソフトウェアの論文は、この議論を所有権、オフライン利用、共同作業、およびデータの長期的な管理へと広げている。

これらは相補的な貢献である。第一は代数と配信モデルの基礎、第二は具体的な構造化データ型、第三は製品とアーキテクチャの観点である。いずれも、ローカルで妥当な任意の変更をマージすれば、あらゆる業務規則を保持できるとは含意しない。本稿ではこれらを用いて、機械レベルの調停の問題と、利用者が操作ボタンを押した際にアプリケーションレベルで与えられる約束とを分離する。 [1], [2], [3]

網羅的に検査できるマージ則

増加専用集合では、状態は要素の集合であり、マージは通常の和集合である。和集合は結合的、可換、冪等である。したがって、受信した状態の括り方や順序を変えたり、同じ状態を繰り返したりしても、最終的な和集合は変わらない。各追加が最終的に参加するすべてのレプリカへ届けば、すべてのレプリカは最終的に同じ集合を保持できる。

有限検査の付録では、四要素の全体集合のすべての部分集合を列挙し、結合則についてのすべての三つ組を含め、三つの法則を検査する。数学的な恒等式はその有限な全体集合を超えて成立するが、このプログラムは、実装された演算に対する有界な整合性検査にすぎない。これは、転送機構、永続化層、あるいは単にCRDTと呼ばれている任意のデータ型の収束を証明するものではない。最終的な配信という仮定は依然として必要であり、決して到着しない情報を取り込めるマージ規則は存在しない。

状態ベースと操作ベースの設計では満たすべき要件が異なる

状態ベースの設計は、状態の順序とマージが必要な単調構造を形成する場合、状態を繰り返し交換できる。操作ベースの設計は更新を交換し、その構成に固有の配信条件と可換性条件を満たさなければならない。状態全体の再適用と操作の再適用は、互換的な行為ではない。インクリメント操作が二度配信されると、正しく表現されたカウンタ状態の反復マージでは二重計上されない場合でも、二度計上されることがある。

したがって、工学的なレビューでは、メッセージが何を表すか、どの操作が並行し得るか、重複と因果依存関係をどう扱うかを文書化しなければならない。少なくとも一回の配信をうたう転送機構は、ある状態表現とは適合しても、素朴な操作表現とは適合しないことがある。逆に、全順序サービスの追加は、すべてのデータ型に必要なわけではないにもかかわらず、可用性とコストを変えることがある。要件は一般的な「同期」という呼称ではなく、具体的な意味論から生じる。 [1]

完全な収束の下でも容量制約の反例は残る

予約を増加専用集合で表し、容量を一とする。レプリカAが予約aを追加する一方、レプリカBが予約bを追加する。各ローカル集合の要素数は一であり、容量制限を満たす。しかし、それらの和集合の要素数は二となる。この証拠例は、独立に到達可能なこれらの状態に対して、不変条件がこのマージの下で閉じていないことを証明する。

いくつかの対応が可能であり、いずれも製品の契約を変える。予約の受理を調整する、譲渡可能な権利を限られた数だけ事前配分する、あるいは後に拒否され得る仮予約を受理する、といった対応である。マージ後に一方の予約を選ぶ方法も収束するが、以前のローカルでの成功を取り消すため、利用者に明示するステータスが必要となる。誤りは、不適切なマージ代数を選ぶことではない。最終受理に必要な情報が利用できないのに、最終受理を約束することにある。

削除は履歴に関する規則である

複製された集合から要素を削除することは、追加よりも微妙な問題を伴う。古いレプリカが古い要素を再導入できる場合、現在の表現を物理的に削除しても、意図した削除を表せないことがある。設計ではしばしば識別子や因果情報を保持し、後のマージが古い追加と新しい追加を区別できるようにする。並行する追加と削除の意味論は、偶然に判明するのではなく、仕様として定めなければならない。

同じ問題は文書編集にも現れる。段落の削除と、その内部の文の編集が並行する場合、結果をあらかじめ定める必要がある。すべての情報を保持すれば復旧を支援できるが、表示される文書が予想外のものになることがある。情報を破棄すればインターフェースを単純化できるが、編集を消してしまうことがある。JSONの文献は、入れ子構造に厳密な並行意味論が必要な理由を示している。それでも、アプリケーションが許容する動作は、現実的な編集タスクで評価する必要がある。 [2]

ガベージコレクションには知識の境界が必要である

削除された操作や置き換えられた操作を記録するメタデータは、可視の文書が小さいままでも増大し得る。その領域を安全に回収するには、古い操作が履歴の解釈を変える形で戻ってこないことを示す証拠が必要である。恒久的にオフラインのデバイス、復元されたバックアップ、複製されたレプリカ識別情報は、その証拠を複雑にする。

単純なストレージモデルでは、u個の各操作に保持メタデータmバイトを割り当て、圧縮と索引作成の前の容量をumバイトとする。操作当たり32バイトの場合、百万個の操作を保持すると32百万バイトを消費する。図が示すのはこの線形な管理コストであり、CRDTライブラリの実際の占有量ではない。圧縮、スナップショット、因果安定化によって、この量は大きく変わり得る。それらの正しさの条件は傾きよりも重要である。情報の領域を回収した結果、現在の契約で削除済みとされるものを古い状態が復活させられるようになってはならない。

同期遅延は意味上の不確実性ではない

説明用の一対のレプリカについて、成功するアンチエントロピー接触が率lambdaのポアソン過程に従うと仮定する。時間tの後でも更新がまだリンクを渡っていない確率は、負のlambda tの指数関数である。伝播遅延の中央値は、二の自然対数をlambdaで割った値となる。これらの曲線は、一回の成功した接触で関連する状態がすべて転送されると仮定し、待ち行列、バッチ処理、マルチホップのトポロジーを無視している。

伝播遅延の中央値が小さいことは、マージ結果がワークフローの意味を保持するかどうかについて何も示さない。システムは過剰予約を非常に速く同期できる。逆に、安全なオフライン編集操作は、伝播遅延が長くても有用であり得る。性能と意味論は別々に評価し、その後、可視の同期状態、復旧可能な履歴、仮の操作と確定した操作の誠実な区別を通じて、利用者体験の中で統合すべきである。

オフラインでの変更の調停後も認可が維持されなければならない

レプリカはオフラインになった時点では認可されていても、再接続前に認可を取り消されていることがある。システムは、以前に作成された操作のうちどれが依然として受け入れ可能か、作成時刻をどう確立するか、どの権限主体が拒否または隔離できるかを決めなければならない。クライアントが制御するタイムスタンプは、取消し前の作成を示す十分な証拠ではない。構文上妥当な操作をすべて無批判にマージすると、代数的収束を保持しながらアクセス方針に違反することがある。

これはアプリケーションと信頼モデルの問題であり、ローカルファーストのアーキテクチャを拒む理由ではない。要件に応じて、署名付きケイパビリティ、制限されたオフライン権限、サーバ側での受入れ、機密データ領域と共同作業データ領域の分離が適切となり得る。重要なのは、データ型のマージ関数自体は、各要素を作成することが誰に許されていたかを決めないという点である。識別情報と認可は、周囲の操作プロトコルの一部でなければならない。

評価には人間と履歴を含めなければならない

提案する評価では、代数的検査とシナリオテストを組み合わせるべきである。代数的検査は、必要に応じた結合性、可換性、冪等性に加え、因果順序に従う配信と重複処理を検査する。シナリオテストには、並行する名前変更と削除、編集中のオブジェクトの移動、リモート変更後の取り消し、復元されたバックアップ、認可を取り消された共同作業者を含める。結果は、状態としても、参加者が理解できる履歴としても調べるべきである。

使いやすさに関する主張には、決定的な収束だけでなく、実際の利用者からの証拠が必要である。有用なプロトコルは、人々が自分の作業を見つけられるか、競合の解決を理解できるか、意図しない結果から復旧できるかを記録する。本稿ではそのような研究を行っていない。実行可能な例が示すのは、より限定された二つの事実である。すなわち、簡略化した集合のマージが宣言された法則を満たすことと、それぞれ独立には妥当な一対の予約が、同じマージの後に共有不変条件に違反し得ることである。

結論：一致と意味を別々に仕様化する

CRDTは場当たり的な調停を明示的な数学的条件に置き換え、共同作業における状態管理の信頼性を大きく改善する。その強みは、保証を正確に述べたときに最も明確になる。同等の情報を得た後に一致することは、すべての利用者の意図、すべての資源制約、すべての認可判断を保持することとは異なる。

したがって、実践的な研究課題は合成的なものである。操作モデルに合うマージ則を持つデータ構造を選び、マージの下で閉じていない不変条件を特定し、オフライン権限を定義し、人間の解釈を必要とする結果に対して履歴と復旧の仕組みを提供する。これらの判断が「競合なし」という語の下に隠されるのではなく、仕様とテストに明示されてこそ、共同作業アプリケーションの妥当性を説明できる。

ローカルで実行済み · 範囲限定

四要素の全体集合における増加専用集合の全マージ則

有限の増加専用集合を対象とし、共同編集ツールの実装でも、意図の保持の証明でもない。

4369件のアサーションが成功した。 これらの検査は提示した例を検証するものであり、引用したシステムを検証するものではない。

{
  "states": 16,
  "capacity_counterexample": [
    [
      0
    ],
    [
      1
    ],
    [
      0,
      1
    ]
  ]
}

全20件の実行可能な例をダウンロード検査結果の全文を読む

明示された解析モデル

四つの式と明示的な仮定

構成した例 · 再現可能なデータ

定量的な議論を確認する

これらの曲線は明示されたモデルから計算したものであり、引用した研究の観測結果ではない。各図には数値データとベクター版が付属する。

CSVをダウンロードSVGソースをダウンロードPythonで再現する

CSVをダウンロードSVGソースをダウンロードPythonで再現する

どの証拠がどの問いに答えるのか

提案する検証プロトコル

これは提案段階の評価設計である。本番システムやハードウェアのベンチマークは実施していない。別途実行した有限モデルについては、実行可能な検査に記録している。

1. 小さな状態を列挙し、選択した構成が要求するマージ則をテストする。
2. 重複、順序変更、遅延、因果制約を伴う配信を明示的にテストする。
3. 容量一の予約の証拠例を陰性対照として含める。
4. 並行する削除と編集、移動と編集、および取り消しの動作を実装前に定義する。
5. 長期間オフラインのレプリカ、復元されたバックアップ、メタデータの領域回収を試験する。
6. 認可の変更と利用者の理解を、収束とは別に評価する。

一次資料が確立していること

本分析の限界

• ここで実行したのは増加専用集合の代数と容量の証拠例だけであり、完全な共同編集ツールを検証したわけではない。
• ポアソン伝播モデルは、トポロジー、帯域幅、バッチ処理、相関した障害を省略している。
• メタデータの増加は明示した線形算定の例であり、ライブラリの測定ではない。
• 人間による編集の研究も、認可を取り消された共同作業者に関する実際の実験も実施していない。

選定した三つの基礎的な一次資料に焦点を絞り、独自の具体例を伴う分析的レビューである。2026までの文献を網羅したレビューや系統的レビューではない。資料へのアクセス範囲と版に関する注記は、参考文献とともに記録している。

結論を変え得る問い

1. 選択したマージの下で閉じていないアプリケーションの不変条件はどれか。
2. 古いレプリカが戻り得る場合、どのような証拠がメタデータ領域の安全な回収を可能にするか。
3. 利用者は、オフラインでの仮の行為と、確定した資源配分をどのように区別すべきか。

参考文献

1. Marc Shapiro, Nuno Preguiça, Carlos Baquero et al.. Conflict-Free Replicated Data Types. Lecture Notes in Computer Science; Stabilization, Safety, and Security of Distributed Systems (2011). 10.1007/978-3-642-24550-3_29.
2. Martin Kleppmann, Alastair R. Beresford. A Conflict-Free Replicated JSON Datatype. IEEE Transactions on Parallel and Distributed Systems (2017). 10.1109/tpds.2017.2697382.
3. Martin Kleppmann, Adam Wiggins, Peter van Hardenberg et al.. Local-first software: you own your data, in spite of the cloud. Proceedings of the 2019 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software (2019). 10.1145/3359591.3359737.

出典[1]へのアクセス。 一次記録、要旨、およびアクセス可能な本文の一部を対象とし、全文や補足資料を網羅的に監査したものではない。

出典[2]へのアクセス。 一次記録、要旨、およびアクセス可能な本文の一部を対象とし、全文や補足資料を網羅的に監査したものではない。

出典[3]へのアクセス。 一次記録、要旨、およびアクセス可能な本文の一部を対象とし、全文や補足資料を網羅的に監査したものではない。

書誌上の同一性は、Crossrefならびに出版社、著者、機関の一次記録と照合した。以下の資料アクセスと版に関する注記に対象範囲を示す。これは全文の網羅的な監査ではない。

著者と来歴

Codex（AI）が執筆し、技術的な自己レビューを行った。参考文献は元の研究者を特定しており、分析上の構成と提案した評価設計は本記事に帰属する。

表紙はImageGenによる概念的イラストである。技術的な図は、明示したモデルまたは有限の例から計算しており、PythonとCSVを提供している。これらは運用中の製品の測定値でも、性能ベンチマークの再現結果でもない。

このローカルの草稿には、独立した査読や学術誌での受理の記録はない。有界な実行可能例は、記載した小規模モデルを検査するものであり、引用したシステムの形式検証ではない。