Gitの「ステー...DocBaseの同時編集機能を実現しているアルゴリズム2017年11月15日takuruTweetはじめに皆さんはGoogleドキュメントやHackMDを使ったことはあるでしょうか。これらのツールは「ネット越しに同時に複数の人で1つのドキュメントを編集できる」という特徴を持っています。お互いの編集がリアルタイムに反映されるので、相手が何を書くのかを意識することなく、簡単にドキュメントを複数人で編集することができます。これを実現するためには、同時編集に参加しているユーザ全員の編集内容がネットワークの延滞に影響されることなく、それぞれの編集内容をうまい具合にマージして反映してくれるような賢いアルゴリズムが必要になります。今回はこのアルゴリズムに関して書きます。編集内容のマージとは編集内容をうまい具合にマージしなければいけないケースを考えてみます。AさんとBさんが次のドキュメントを同時編集するとします。最初は、お互いブラウザ上では次のように見えています。この状態ではお互いに見えているものは同じです。AさんのブラウザabcefBさんのブラウザabcefここでAさんが「cの次のdが抜けてるな。」と思い、cの次にdを追加しました。この時点では、まだBさんのブラウザにはAさんの変更がネットワークを通じて送られる前のため、次のような状態になります。AさんのブラウザabcdefBさんのブラウザabcefこのままBさんのブラウザにAさんが行った変更を反映すれば問題ないように思えます。Aさんが「cの次のdが抜けてるな」と思ったと同時に、Bさんが「fの次はgだな。」と思ってfの次にgを追加してしまったらどうなるでしょうか。AさんのブラウザabcdefBさんのブラウザabcefgAさんが見ているドキュメントの内容と、Bさんが見ているドキュメントの内容が食い違ってしまいました。この場合はどちらを優先すればよいのでしょうか。「Aさんがcの次にdを追加した」という操作と「Bさんがfの次にgを追加した」という操作、これら2つの操作はどちらが最初にサーバ、ないしは相手側に通信が到達するかはわかりません。別のパターンとして、Aさんが文字を追加すると同時に、Bさんが全ての文字を削除する操作をしてしまったらどうすればよいでしょうか。そこでOTですよ前述のような複数ユーザの異なる操作をうまい具合に解決するアルゴリズムがあります。Transformation(以下OT)、日本語では操作変換と呼ばれるアルゴリズムです。OTでは、各ユーザの編集を「操作(Operation)」単位でやりとりします。テキストを対象にしたOT(OTは同じ考え方でDOMのOTも実装することが可能のようです)では、操作の種類、位置、文字の情報を1つの「操作」として処理をします。先のAさんとBさんの編集が衝突してしまった問題を、OTを使って解決してみます。OTの考え方を使う場合は、2人の操作は次のように考えます。Aさんがcの次にdを追加したという操作は、「3文字目にdを追加した」という操作(Operation)Bさんがfの次にgを追加したという操作は、「5文字目にgを追加した」という操作(Operation)この2つの操作はOTのサーバに送られますが、操作の通信が到達するタイミングの様々な組み合わせによってサーバで操作を変換するタイミングが変わってきます。一例として、Aさんの操作が先に到達した場合を考えます。この場合、サーバには他の操作は到達していませんから、Bさんにはそのまま「3文字目にdを追加した」という操作を送れば問題ありません。その後、Bさんの操作がサーバに到達します。Bさん側ではgは5文字目でしたが、Aさん側では3文字目に文字が追加されているので、Aさんに送るべき操作の情報は「6文字目にgを追加した」という情報です。これをまとめると、Aさん、Bさん、サーバのそれぞれで保持しているテキストは、次のように移り変わります。※0文字目から数えていますこのように、OTのアルゴリズムを正しく使用することにより、他の様々な操作の通信のタイミングに対応することができます。どこかの通信が延滞したとしても、最終的な結果は保証されるようになっているのです。serverのページで色々試してみると理解が深まると思います。OTを実装したOT.jsを使ってみるOTについてざっくり理解したところで、実際に使ってみたいと思います。今回はOTのJavaScript実装であり、HackMDでも使われているライブラリであるOT.jsを使用し、とても単純な同時編集を実装します。簡単なサンプルのため、次の制約を持ちます。必要なツールをインストールします。OT.jsでは、クライアントとサーバ間のプロトコルに関してAjaxのアダプタとSocket.IOのアダプタが用意されています。今回はより良いパフォーマンスを出すことができるため、Socket.IOのアダプタを使用してSocket.IOで実装します。そのため、npmでsocket.ioをインストールします。socket.ioさえあれば実装できますが、より簡単に実装するためにexpressも使用しています。socket.ioサーバサーバ側のコードは次の通りです。OT.jsに関連するコードはEditorSocketIOserverのインスタンスを使用しているのみです。細かいことはOT.jsがやってくれます。server.addClient(socket);});クライアントサーバ側のコードでは、「/」へのアクセスに対してindex.htmlを返すように設定したので、index.htmlを用意します。OT.jsは、エディタとしてCodeMirrorを使用しており、OT.jsで用意されているCodeMirrorへのアダプタを使用することにより他のユーザのカーソルの表示やテキストのマージを全てやってくれます。</body></html>socket.onでdocイベントに対するリスナを登録しています。このイベントが発行されるタイミングは、サーバ側(server.js)のserver.addClient(socket);の内部です。docイベントには現在のドキュメントの情報などが含まれているため、それを利用してエディタの初期化を行います。エディタの初期化が終われば、OT.jsのSocketIOAdapterとCodeMirrorAdapterをEditorClientに渡すだけで動作します。アクセスすると同時編集を試すことができます。server.js複数ブラウザを起動してアクセスしてみると、片方のブラウザで操作した内容がもう一方のブラウザに反映されることがわかると思います。リポジトリ今回のコードはこちらで公開しています。https://github.com/ttakuru88/ot_sampleまとめるとネット越しのドキュメントの同時編集に必要なのはOTというアルゴリズム。そのアルゴリズムを実装したOT.jsを使用することにより、わずか数行のJavaScriptを書くだけで簡単に同時編集を行えるエディタを実装することができました。当然ながら、実際に運用されるサービスに実装する場合にはこんなに簡単にはいかないですが、OTや同時編集の動作をプラグイン側がほとんどやってくれるというのは、実装する難易度がグッと下がります。みなさんもOTを使用して、同時編集のできる便利なツールを作ってみるのはいかがでしょうか。クローズドβ開始!DocBaseでメモの同時編集が行えるようになりました。本記事で作成したサンプルでは同時編集のバックエンドにはNode.jsを使用していますが、DocBaseではバックエンドにElixirを使用してOTを実現しています。Gitの「ステー...「いいね!」で応援よろしくお願いします!このエントリーに対するコメントコメントはまだありません。date*日本語が含まれない投稿は無視されますのでご注意ください。fax.0422-26-9781お問い合わせはこちらからどうぞ。