私は間違っていた。未来はCRDTです

数週間前、CRDTを介したリアルタイム編集へのアプローチに関するMartin Kleppmanのプレゼンテーションを見て、灼熱の絶望を感じました。彼のアプローチは非常に優れているため、過去10年間の私のすべての作業を上回り、将来的にはそのための場所はありません。 しかし、最初からやり直しましょう。







2010年、私はGoogle Waveで働きました。そこでは、メール、Googleドック、フォーラム、インスタントメッセージ、その他の多くのシングルタスクアプリケーションを置き換えるために、共同で編集可能なスペースを作成しようとしました。私のツールの中で、私は特に汎用環境が好きです。Waveのように、機能は当時定式化されていませんでした。他のほとんどのツールとは異なり、汎用環境は独自のワークフローを課さないため、休日の計画、Wikiの作成、友達とのボードゲームのプレイ、仕事の会議のスケジュールなどに使用できます。



内部的には、Waveの共同編集はOperational Transform（OT）の上で機能し、当時は何日も使用されていました。私たちのアルゴリズムは1995年の木星の話に基づいていました。アルゴリズムは、ドキュメントごとに、「位置0のタイプH」、「位置1のタイプi」などの変更の個別の時系列リストを保持します。ほとんどの場合、ユーザーはドキュメントの最新バージョンを変更し、ログは一連の変更のように見えますが、共同編集する場合、同時編集に直面します。



この場合、サーバーに到達した最初の編集は通常どおり記録され、次の編集が古くなっていることが判明した場合は、イベントログと比較されて、ユーザーの最初の目標が決定されます。 （多くの場合、すべては文字位置の更新に帰着します。）次に、アルゴリズムは、おそらく「これはユーザーが望んでいた結果です」と思われ、リアルタイムでgit-rebaseなどの新しい操作を追加します。



Google Waveの閉鎖に伴い、OTモデルをShareJSに移植しました。その時、ノードは新しくて奇妙に感じました、そして私が正しく覚えていれば、私はnpmリリースの前でさえShareJSを始めました。単純な共同編集者は1000行のコードしか必要とせず、デモではブラウザとアプリケーションでドキュメントを共同編集しました。



本質的に、OTは（）ループで装飾されています文字オフセットを更新するための複数のヘルプ機能を備えています。実際には、OTはシンプルで理解しやすく、すぐに運用でき、優れた機能を発揮します。（最適化されていないjavascriptでは1秒あたり10〜10万回の操作、最適化されたCでは1〜2,000万回）。イベントログは通常よりも多くのメモリを消費する可能性がありますが、特に古い編集を組み合わせることができなくなりますが、必要に応じてログを減らすことができます。オペレーションをグローバルに割り当てるには、一元化されたサーバーが必要ですが、ほとんどのシステムにはすでにそのようなサーバーまたはデータベースがありますね。

一元化されたサーバー

OTの重要な問題は、集中型サーバーへの依存です。ソーシャルネットワークを介してGoogleDocsドキュメントへのアクセスを許可すると、「このドキュメントが過負荷になり、編集が無効になっています」などの奇妙なメッセージが表示されたのはなぜだろうと思ったことはありませんか。その理由は（私の意見では）次のとおりです。ドキュメントを開くと、すべての編集を処理するために1つの特定のサーバーが選択され、多数のユーザーがドキュメントに飛びついた場合、システムはサーバーに過負荷をかけないように非常に努力する必要があります。



この問題を回避するには、いくつかの方法があります。サブドキュメントのシャーディング（Google Docksの場合のように）に加えて、データベーストランザクションをバイパスして、再試行ループを介して編集を行うことができるため、シリアル化の問題は同じデータベースで処理されます（これがFirepadの動作方法です）。およびShareDB）。



ただし、OTは完全ではありません。電子メールをWaveに置き換えたかったのですが、メールはマージをサポートし、1つの文字チェーンが多くの企業にまたがることができ、どういうわけかすべてが正常に機能します。さらに、Facebookメッセージとは異なり、「コピー」列に記載されている企業に電子メールを送信できます。 Waveでメールを置き換える場合は、たとえば次のテーブルで同僚に手紙を送るときに、外部ネットワークにアクセスせずにメッセージを送信する機能も必要になります。しかし、OTの上にこれらすべてをどのように実装できますか？私たちはどういうわけかそのようなプロセスを設定することができましたが、それは複雑すぎてエラーでいっぱいであることが判明しました：私たちは図を作成しました、各ウェーブプロトコルがウェーブサーバーのツリーをセットアップして操作を双方向に転送しましたが、完全には機能しませんでした。10年弱前のWaveProtocol Summitで、このようなネットワークの作成と構成の方法についてプレゼンテーションを行いましたが、準備と事前チェックをすべて行ったにもかかわらず、プレゼンテーション自体の各ステップを厳密に順守できず、ネットワークが機能しませんでした。なぜこれが起こったのかはまだわかりませんが、バグが何であれ、パブリックバージョンではほとんど修正されておらず、非常に困難でした。

離陸CRTD

すでに述べたように、メインのWaveアルゴリズムはかなり昔の1995年に作成されたもので、当時自宅にインターネットがあったことすら覚えていません。それ以来、研究者はOTのパフォーマンスを改善するためにたゆまぬ努力を重ね、最も有望な方向でCRTD（競合のない複製データタイプ）を使用しています。このアプローチは通常とは少し異なり、中央サーバーを必要とせずにリアルタイムでファイルを編集できます。マーティンのプレゼンテーションは、私が説明できるよりも彼らの仕事をよりよく説明しているので、詳細はスキップします。



人々は何年もの間CRTDについて私の意見を求めてきました、そして私の答えはいつもこのように聞こえます：

それらはきちんとしていて、人々がそれらに取り組んでくれてうれしいです、しかし：

• . . , 100 Delta-CRTD . (: B4.)
• - CRTD , , 100 automerge master 83 . , , , , . ( automerge 1.1 .)
• 何年もの間、OTに存在する機能はCRDTに存在しませんでした。たとえば、/ object move /（JSONツリーのある部分から別の部分に何かを転送する）をサポートするCRDTをまだ作成していません。このような手順はWorkflowyのようなアプリケーションに必要であり、OTはそれらをうまく処理します。
• CRDTはそれ自体が複雑であり、推論するのが困難です。
• あなたはおそらくすでに一元化されたサーバー/データベースを持っています。

私はすべての批判に対してCRDTを無視しましたが、そうすることで関連する文献を無視し、驚いたことに、CRDTの静かで知覚できない改善を見逃しました。マーティンは彼のプレゼンテーション（注目に値する以上のもの）で主なポイントを取り上げています。

• : CRDT (Automerge / RGA Y.js / YATA) [log(n)] . ( .)
• : - , 54- . automerge , Y.js, Y.js 100 160 3 . .
• : , .
• : , CRDT OT. , automerge .

速度の理由は私を納得させなかったので、アイデアをテストするために、自動マージからのアイデアを使用して、Bツリーを介してRustでCRDTを独自に実装してテストしました。機能（文字の削除、競合）はありませんでしたが、1秒あたり600万回の編集を処理できました。 （各反復で、2人の交互のユーザーが空白のドキュメントを2000回編集し、合計で330マイクロ秒、つまり1秒あたり606万回の編集が行われました。）したがって、CRDTは大幅に改善され、それらとOTの速度差はRustとOTの速度差よりもさらに小さくなりました。 Javascript。



これらの修正はすべて、自動マージパフォーマンスブランチの「近日公開」セクションに長い間含まれていますが、結局のところ、自動マージだけがCRDTではありません。Y.jsはそれ自体が価値があることを証明し、テストで現在のバージョンの自動マージを簡単にバイパスします。私が興味を持っている機能が欠けていますが、一般的に、新しいアルゴリズムを作成するよりも、既存の実装を修正する方が確かに簡単です。

未来を発明する

私は進歩することを非常に心配しています。百年も使わないのは何がおかしいのでしょうか。もちろん、リアルタイムで編集する予定ですが、OTを介した実装と、この点に関して私が行ったすべての作業については、もう確信が持てず、悲しむしかありません。



最近、JSONとRESTはどこにでもあります。 15年後には、リアルタイムの共同編集がどこにでもあるとしましょう。プロジェクトに簡単に転送するための共同編集に関して、JSONに相当するものは何ですか？この輝かしい未来には、CRDTの高品質な実装が必要になります。これは、一部のアプリケーションではOTが機能せず、それを介してGItのリアルタイムバージョンを作成したり、GoogleWaveの単純なバリエーションが機能しなくなったりするためです。しかし、すでに優れたCRDT実装がある場合、OT実装も必要ですか？ OTからCRDTへのすべての機能の転送（ちなみに、トリミング操作を含む）は難しくありませんが、その逆は当てはまらないため、私はそうではないと思います。賢い人は私に同意しませんが、私の意見では、言語ごとに優れた高速のCRDTがあることを考えると、OTの必要性は完全になくなります。



OTの利点の1つは、ほとんどの最新のアプリケーションと同様に、集中型システムに簡単に実装できることですが、分散型アルゴリズムも同様に実装されます。（たとえば、Githubを見てください。）私の意見では、wasmでの高品質のCRDTは、JSでのOT実装よりも高速です。また、集中型システムのみに関心がある場合は、次の点に注意してください。OTの制限により、GoogleはGoogleDocsのスケーリングの問題を引き起こしました。



ですから、今が小さくて速いCRDTに切り替える時であるように私には思えます。ほとんどの場合、学術的な作業はすでに行われており、実装を成功させるための問題が残っています。

次は何ですか

私は集中型アプリケーションの世界にますます関心を持っていません。アプリケーションは私のデバイス上で私のデータと相互作用し、これらのアプリケーションがそれに応じてそのような接続に反応する時が来ます。ラップトップと電話が、データを別の国のサーバーにアップロードするのではなく、wifiを介して相互にデータを転送できるようにしたいと考えています。特に、これらのサーバーが私の注意を競う広告の巨人によって資金提供されている場合。



哲学的には、Google Docsでドキュメントを編集すると、コンピューターがGoogleにファイルの編集許可を求めます（何らかの理由でサーバーが「いいえ」と言った場合、すべての編集内容が失われるため）。比較のためにgit push、githubにいるときは、通知するだけです私のコードの編集についてのgithub。私のリポジトリは、それが置かれているすべてのデータとハードウェアと同様に、まだ私のものであり、これが私のアプリケーションの動作方法です。マーティンのような人々のおかげで、私たちは今、良いCRDTを作る方法を知っています。ただし、ローカルファーストのアプリケーションがベースとして受け入れられる前に、より多くのコード行を記述する必要があります。



全体として、運用の変革に別れを告げる時が来ました。私が書いたすべての中で、私たちは一緒に素晴らしい時間を過ごしました。運用変換コード は、最も困難で興味深いものの1つでした。あなたは賢くて素晴らしいです、OT、しかしCRDTはあなたが決してできないことをすることができます。そして、CRDTが必要です。いくつかの良い実装で、本当に特別なことを達成できると思います。



私は何年にもわたってOTに費やしたすべての作業を悼みますが、OTはもはや私の将来のビジョンに適合しません。CRDTを使用すると、Waveをより簡単かつ迅速に再構築し、ユーザーをデジタル農民ではなくデジタル市民のように扱うアプリを作成できます。そして、これは重要です。



作成する時が来ました。