無料で試す

共同編集

共同作業ソフトウェアの基本的な概念と、その一般的な実装アプローチについて解説します。

執筆者
Craft Author: Levy Melnikov
Levy Melnikov
公開日
11/5/2024
Building Craft
共同編集

共同編集

共同編集とは、複数の人が同じドキュメントを同時に編集できる機能です。この機能を備えたアプリの例をいくつか挙げます：

  • Craft
  • Miro
  • Google Docs
  • Figma

まだ試したことのない方には、共同編集をぜひ体験してみることをお勧めします。同僚や友人に声をかけて、別々のデバイスで一緒に何かを編集してみてください。一方のデバイスで行った変更が他のデバイスにいかに素早く反映されるかに驚くはずです。他の人の編集を素早く表示する能力は、共同編集の根本的な側面です。

共同編集機能を持たない主要なアプリの例：

  • Git
  • Adobe Photoshop
  • FL Studio

これらのアプリでは、他の人との共同・同時編集は自動的には行えません。一般的なワークフローは、変更を加えてファイルを保存し、共同作業者に送るというものです。相手が変更を加えてから更新版を返してくる。この往復を何度も繰り返し、最終的にドキュメントをマージして完成させます。

Gitは興味深い例です。Gitは根本的に協調システムであり、コラボレーションを促進し、同じプロジェクトで人々が共同作業できるようにします。しかし、Gitには共同編集機能がないため、ユーザーは変更をプルおよびプッシュする必要があり、2人が同じファイルを同時に編集するとコンフリクトが発生することがあります。こうしたコンフリクトの解消には、多くの場合、手動での対応が必要になります。つまり、Gitは共同編集を持たない協調的なソフトウェアです。

コンフリクトの解消

コンフリクトとその解消は、共同編集に本質的に伴うものです。これらのコンフリクトはどのように発生するのでしょうか？AliceとBobがクラウドに保存されているドキュメントのバージョン1（V1）を更新したいとします。それぞれが自分のローカルデバイスにV1をダウンロードして変更を加えます。Bobが先に完了し、編集済みのV2をクラウドにアップロードします。一方、Aliceは自分のV2*を完成させ、後でアップロードしようとします。しかしAliceは自分のバージョンをクラウドに保存することができません。それをすると、Bobの変更を上書きしてしまうからです。これがコンフリクトの本質です。解消するために、AliceはV2をダウンロードし、V2とV2*の違いを調整して、両方の変更を含むV3を作成する必要があります。その後、V3をクラウドに保存できます。

Levy1.png

例：コンフリクトの解消

共同編集ソフトウェアは、全員が常に最新バージョンのファイルを確認できるよう、変更を素早く交換しなければなりません。そのため、コンフリクトが発生する機会は多く、自動的に解消されなければ、ソフトウェアを共同で使用することが極めて難しくなります。つまり、体験を機能させるために2つのメカニズムが不可欠であり、これらは共に「共同編集の公式」を形成します：

変更を素早く交換する + コンフリクトを自動的に解消する = 共同編集

操作変換（Operational Transformation）

自動コンフリクト解消の実装には、2つの一般的なアプローチがあります。1つは操作変換（OT: Operational Transformation）と呼ばれるものです。重要なアイデアは、ユーザーが他のユーザーから変更を受け取ったとき、それらの変更をローカルコピーと互換性のあるものにするために「変換」する必要があるというものです。このアプローチを使用する製品の例はGoogle Docsです。このアプローチのほとんどの実装では、中央のコーディネーターが必要になります。概念の詳細な説明は次のようになります：

  1. テキストを操作のシーケンスとして表現する
  2. 新しい編集が行われると、それらが操作として他者に送信される
  3. 受け取った編集を保存する前に、ローカルの状態と互換性を持つよう変換される

最も単純なケースでは、編集は2つの操作で表現できます：

  • ADD(Index, Ch) はテキストの指定されたインデックスに文字を挿入する
  • DEL(Index) は指定されたインデックスの文字を削除する

例えば、「Hello!」は追加の操作のシーケンスとして表現できます。

ADD(1, H)
ADD(2, E)
ADD(3, L)
ADD(4, L)
ADD(5, O)
ADD(6, !)

「Hello!」を操作のシーケンスとして表現したもの。

「Hello!」を「Hello :)」に変更するには、4つの新しい操作を適用する必要があります。

ADD(1, "H")
ADD(2, "E")
ADD(3, "L")
ADD(4, "L")
ADD(5, "O")
ADD(6, "!")
New Operations
DEL(6, !)
ADD(6, " ")
ADD(7, ":")
ADD(8, ")")

削除の表現

では、簡単な例でこれがどのように機能するか見てみましょう。AliceとBobは共通の状態、つまりスペルミスのある「Helo」から始まります。Bobは「l」を位置3に追加してこれを修正したいと思っています。Aliceは「!」を位置5に追加して末尾に感嘆符を付けたいと思っています。

Levy2.png

OTの例：開始状態と意図された変更

Aliceが自分の操作を追加してBobからの操作を受け取ると、期待通り「Hello!」になります。問題はありません。しかし、Bobが自分の操作を追加してAliceからの操作を受け取ると、「Hell!o」になってしまいます。これは意味をなさず、Aliceの状態とも異なります。

これは、Bobが編集を行った後、Aliceの変更がBobのバージョンと互換性がなくなったために起きました。これは操作の正確なシーケンスを示す図で説明できます。

Levy3.png

OTの例：Bobのバージョンにコンフリクトがある

図から、Aliceの操作を変換する必要があることは明らかです。「!」を位置5に追加するのではなく、位置6に追加する必要があります。BobがAliceからの操作を変換した後、正しい状態「Hello!」を得られます。

Levy4.png

OTの例：Bobがaliceの操作を変換して正しい状態を得る

これが操作変換の要点です。他者から来た変更を調整して、全員が同じファイル状態になるようにしなければならない場合があります。OTは、ローカルとリモートのあらゆる操作の組み合わせに対してどのように変換するかを定義しなければなりません。ローカルの追加がadd(pos1, chr1)でリモートがadd(pos2, chr2)の場合、ルールは次のようになります：

transform(add(pos1, chr1), add(pos2, chr2)):
    if pos1 > pos2:
        return ins(pos1, chr1)
    else:
        return ins(pos1 + 1, c1)

2つの追加を変換するルールの例

最も単純なOT実装では、残りの可能な操作の組み合わせに対してさらに3つのルールが必要です。それらを定義した後、OTは完成します。上記の例はOTアプローチのコアなアイデアを示しています。もちろん、実際の実装は「元に戻す」操作やスタイリングなど、より複雑なシナリオを伴うため、これよりも複雑になります。

コンフリクトフリーの複製データ型

コンフリクトフリーの複製データ型（CRDT: Conflict-free Replicated Data Types）は、自動コンフリクト解消を実装するためのもう一つのアプローチです。重要なアイデアは、そもそもコンフリクトを許さない構造でデータを表現することです。OTと同様に、これは万能ソリューションではありませんが、さまざまなユースケースに合わせたさまざまな実装を持つ概念です。これらの実装は通常、中央サーバーを必要とせずにピアツーピアのトポロジーで動作できます。ユーザーが切断しても、後から追いつくことができます。

CRDTの一例がTwo Phase Set（二相集合）です。これは特別な集合で、以下のように機能します。集合に項目を追加したり削除したりでき、一度削除された項目は再度追加できません。これをイメージするのによい例が、各項目に印をつけて完了を示せるチェックリストです。Two Phase Setは、「チェックを外す」機能が不要であれば、チェックリストとして有効な構造です。

Levy5.png

Two Phase Setの例：観たい映画リスト

Two Phase Setは2つの集合で表現できます。1つは追加された項目用、もう1つは削除された項目用です。ユーザーは「追加」集合に追加することで新しい項目を追加するか、「削除」集合に追加することで既存の項目に印をつけることのみが許可されています。つまり、許可されたすべての操作は「追加」集合または「削除」集合への追加のみとなります。AliceとBobの例を再び使ってみましょう。彼らは上に示した共通の状態、観たい映画リストを編集しています。

今、Aliceはリストに新しい映画「グラディエーター」を追加したく、Bobは「インターステラー」をすでに観たとして削除したいと思っています。

Levy6.png

Two Phase Setの例：変更を加える

それぞれのローカル状態に変更を加えた後、互いに状態を交換してそれぞれの集合をマージする必要があります。マージは可換操作なので、AliceがBobに状態を送るかその逆かに関わらず、結果は同じになります。

Levy7.png

Two Phase Setの例：状態のマージ

ご覧のとおり、「追加」集合と「削除」集合をマージすると、AliceとBobが望んでいた通りの結果が得られます。グラディエーターが追加され、インターステラーに削除マークがつきます。Two Phase Setのために定義されたルールにより、設計上コンフリクトが防止されています。

Two Phase Setは、理解しやすい便利なCRDTの好例です。実際のユースケースでは、以前削除した項目を再度追加できる構造が必要になるでしょう。そのような構造は存在し、テキスト、チャート、グラフなどを表現できますが、その設計はより複雑になります。実際のアプリケーション向けのCRDTベースの共同編集機能を作成するための優れたオープンソースライブラリを2つお勧めします：

一部のCRDTでは、全員が状態に関する情報を共有し続けることで、最終的に全員が同じ状態に収束することが証明されており、それがコンフリクト解消の目的です。証明へのリンクはこちら：https://github.com/trvedata/crdt-isabelle。この証明は定理証明ソフトウェアを使用して作成され、GitHubでホストされています。

まとめ

この記事をまとめましょう！共同編集ソフトウェアが効果的に機能するためには、リアルタイムで編集を素早く交換し、発生するコンフリクトを自動的に解消する必要があります。これを実現するための2つの最も注目すべきアプローチが、操作変換（OT）とコンフリクトフリーの複製データ型（CRDT）です。OTは受信した編集をその場で変換し、CRDTはそもそもコンフリクトが発生しないよう設計された構造を使用します。

Craftの共同編集ソリューションの歴史について学びたい方は、今後の投稿をお楽しみに。

ブログをもっと読む

Building CraftLife at CraftNewsCommunity StoriesFuture of Work