DocBaseの同時編集機能を実現しているアルゴリズム このエントリをはてなブックマークに登録

2017年11月15日

takurutakuru

はじめに

皆さんはGoogleドキュメントやHackMDを使ったことはあるでしょうか。これらのツールは「ネット越しに同時に複数の人で1つのドキュメントを編集できる」という特徴を持っています。お互いの編集がリアルタイムに反映されるので、相手が何を書くのかを意識することなく、簡単にドキュメントを複数人で編集することができます。これを実現するためには、同時編集に参加しているユーザ全員の編集内容がネットワークの延滞に影響されることなく、それぞれの編集内容をうまい具合にマージして反映してくれるような賢いアルゴリズムが必要になります。今回はこのアルゴリズムに関して書きます。

編集内容のマージとは

編集内容をうまい具合にマージしなければいけないケースを考えてみます。

AさんとBさんが次のドキュメントを同時編集するとします。最初は、お互いブラウザ上では次のように見えています。当然、この状態ではお互いに見えているものは同じです。

Aさんのブラウザ

abcef

Bさんのブラウザ

abcef

ここでAさんが「cの次のdが抜けてるな。」と思い、cの次にdを追加しました。この時点では、まだBさんのブラウザにはAさんの変更がネットワークを通じて送られる前のため、次のような状態になります。

Aさんのブラウザ

abcdef

Bさんのブラウザ

abcef

このままBさんのブラウザにAさんが行った変更を反映すれば問題ないように思えます。ですが、Aさんが「cの次のdが抜けてるな」と思ったと同時に、Bさんが「fの次はgだな。」と思ってfの次にgを追加してしまったらどうなるでしょうか。

Aさんのブラウザ

abcdef

Bさんのブラウザ

abcefg

Aさんが見ているドキュメントの内容と、Bさんが見ているドキュメントの内容が食い違ってしまいました。この場合はどちらを優先すればよいのでしょうか。「Aさんがcの次にdを追加した」という操作と「Bさんがfの次にgを追加した」という操作、これら2つの操作はどちらが最初にサーバ、ないしは相手側に通信が到達するかはわかりません。また別のパターンとして、Aさんが文字を追加すると同時に、Bさんが全ての文字を削除する操作をしてしまったらどうすればよいでしょうか。

そこでOTですよ

前述のような複数ユーザの異なる操作をうまい具合に解決するアルゴリズムがあります。それはOperational Transformation（以下OT）、日本語では操作変換と呼ばれるアルゴリズムです。
OTでは、各ユーザの編集を「操作（Operation）」単位でやりとりします。テキストを対象にしたOT（OTは同じ考え方でDOMのOTも実装することが可能のようです）では、操作の種類、位置、文字の情報を１つの「操作」として処理をします。

先のAさんとBさんの編集が衝突してしまった問題を、OTを使って解決してみます。OTの考え方を使う場合は、２人の操作は次のように考えます。

  • 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-uml

このように、OTのアルゴリズムを正しく使用することにより、他の様々な操作の通信のタイミングに対応することができます。どこかの通信が延滞したとしても、最終的な結果は保証されるようになっているのです。

操作の変換を行う詳しい流れについては、Visualization of OT with a central 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も使用しています。

mkdir ot-app
cd ot-app
npm install --save express ot socket.io

サーバ

サーバ側のコードは次の通りです。OT.jsに関連するコードはEditorSocketIOserverのインスタンスを使用しているのみです。細かいことはOT.jsがやってくれます。

server.js

var app = require('express')();
var http = require('http').Server(app);
var io = require('socket.io')(http);

app.get('/', function(req, res){
  res.sendFile(__dirname + '/index.html');
});

http.listen(3000, function(){
  console.log('listening on *:3000');
});

var EditorSocketIOServer = require('ot/lib/editor-socketio-server');
var server = new EditorSocketIOServer("", [], 1);

io.on('connection', function(socket){
  server.addClient(socket);
});

クライアント

サーバ側のコードでは、「/」へのアクセスに対してindex.htmlを返すように設定したので、index.htmlを用意します。
OT.jsは、エディタとしてCodeMirrorを使用しており、OT.jsで用意されているCodeMirrorへのアダプタを使用することにより他のユーザのカーソルの表示やテキストのマージを全てやってくれます。

index.html

<!DOCTYPE html>
<html>
  <head>
    <meta charset="UTF-8" />
    <title>同時編集デモ</title>
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/codemirror/5.29.0/codemirror.css">
    <style></style>
    <script src="/socket.io/socket.io.js"></script>
    <script src="https://cdnjs.cloudflare.com/ajax/libs/codemirror/5.29.0/codemirror.js"></script>
    <script src="https://cdnjs.cloudflare.com/ajax/libs/ot.js/0.0.15/ot-min.js"></script>
    <script>
      var socket = io();
      socket.on('doc', function(data) {
        // CodeMirrorの初期化
        var cm = CodeMirror.fromTextArea(document.getElementById('note'), {lineNumbers: true})
        cm.setValue(data.str)
        // otの初期化
        var adapter = new ot.SocketIOAdapter(socket)
        var cmAdapter = new ot.CodeMirrorAdapter(cm)
        var client = new ot.EditorClient(data.revision, data.clients, adapter, cmAdapter)
      })
    </script>
  </head>
  <body>
    <textarea id="note"></textarea>
  </body>
</html>

socket.onでdocイベントに対するリスナを登録しています。このイベントが発行されるタイミングは、サーバ側（server.js）のserver.addClient(socket);の内部です。docイベントには現在のドキュメントの情報などが含まれているため、それを利用してエディタの初期化を行います。エディタの初期化が終われば、OT.jsのSocketIOAdapterとCodeMirrorAdapterをEditorClientに渡すだけで動作します。

動作確認

次のコマンドでサーバを起動し、 http://localhost:3000/ にアクセスすると同時編集を試すことができます。

node server.js

複数ブラウザを起動してアクセスしてみると、片方のブラウザで操作した内容がもう一方のブラウザに反映されることがわかると思います。次のような動作です。

0589a2af-0f63-493a-800a-17829b23692a

リポジトリ

今回のコードはこちらで公開しています。
https://github.com/ttakuru88/ot_sample

まとめると

ネット越しのドキュメントの同時編集に必要なのはOTというアルゴリズム。そのアルゴリズムを実装したOT.jsを使用することにより、わずか数行のJavaScriptを書くだけで簡単に同時編集を行えるエディタを実装することができました。
当然ながら、実際に運用されるサービスに実装する場合にはこんなに簡単にはいかないですが、OTや同時編集の動作をプラグイン側がほとんどやってくれるというのは、実装する難易度がグッと下がります。
みなさんもOTを使用して、同時編集のできる便利なツールを作ってみるのはいかがでしょうか。

DocBase 同時編集機能 クローズドβ開始！

DocBaseでメモの同時編集が行えるようになりました。
本記事で作成したサンプルでは同時編集のバックエンドにはNode.jsを使用していますが、DocBaseではバックエンドにElixirを使用してOTを実現しています。

ab024fd8-b29c-48d8-9980-ee1efacf6b34

https://help.docbase.io/posts/318474

Related posts:

  1. そろそろnode.jsについて一言書いておくか
  2. Electronを使ってJavaScriptでデスクトップアプリを作る
  1. メモからはじめる情報共有 DocBase 無料トライアルを開始
  2. DocBase 資料をダウンロード

「いいね!」で応援よろしくお願いします！

このエントリーに対するコメント

コメントはまだありません。

日本語が含まれない投稿は無視されますのでご注意ください。（スパム対策）

トラックバック

we use!!Ruby on RailsAmazon Web Services

このページの先頭へ