共同編集可能なドローイングツールをイチから作ってみたお話

はじめまして！株式会社ハイヤールーの新谷（@s__shintani）です。先日HireRooに新しくシステムデザイン形式の問題が追加されました。本記事ではシステムデザイン形式の問題で使用するドローイングツールの共同編集機能を実現する技術とその設計について執筆いたします。

f:id:s__shintani:20220406223249p:plain — 図1: システムデザイン形式の問題回答画面。候補者はテキストやコンポーネントを自由に配置できる。

共同編集技術の歴史は古く、ユーザー間における処理の競合を解消するためにOperational Transform（OT）をはじめとする様々なアルゴリズムが考案されてきました。私たちが今回のドローイングツールを設計する際もいくつかのアルゴリズムを参考にし、その一部をユースケースに合わせて取り入れることで共同編集機能を実現しました。当記事が同様の機能を開発したいと考えている開発者の助けとなれば嬉しく思います。

全体像

f:id:s__shintani:20220406222855p:plain — 図2: ユーザーAの変更がFirebaseを介してユーザーBに同期される

図2はユーザーの変更がピアに同期されるまでの処理の流れを示したものです。以下、順を追って説明させていただきます。

描画エリア

描画エリアはSVGの座標平面です。テキストやノードなどの配置可能なオブジェクトは全てSVG要素であり、一つ一つのSVG要素をラベルや座標などの情報をもつ構造体（Element）として表現し、ReduxのStateで管理しています。

Elementの構造

{
   "id":"35681a",
   "type":"node",
   "category":"messaging",
   "label":"queue",
   "geometry":{
      "minX":920,
      "minY":1000,
      "maxX":1080,
      "maxY":1160
   },
   "updatedAt":1648886122314
}

描画エリアに登録されているイベントハンドラがマウスの移動やクリックといったユーザーの動きを検知し、その変更内容をFirebaseに保存した上、最終的にReduxのStateを更新することで描画エリアに変更内容が反映されます。

Firebase Realtime Databaseを用いた状態の同期

ユーザーの動きを検知したイベントハンドラは直接ReduxのStateに更新をかけるのではなく、Firebase Realtime Databaseに変更内容をHistoryとして保存します。ユーザーの変更を操作単位で保存する際、反転した操作をスタックに保持しておくことでUndo/Redoを簡単に実現できます。

Elementの追加操作をFirebaseに保存する関数

const addElement = useCallback(
 (id: string, label: ElementLabel, x: number, y: number, operationType: OperationType) => {
   // Hisotryに保存される操作
   const operation: AddElement = {
     s: FLOW_ACTION.addElement,
     v: {
       id,
       l: label,
       x,
       y,
     },
     a: uid,
     t: timeInSeconds(),
   };
   // Undo, Redo用にStackに保持される操作
   const inverseOperation: DeleteElements = {
     s: FLOW_ACTION.deleteElements,
     v: {
       ids: [id],
     },
     a: uid,
     t: timeInSeconds(),
   };
   if (operationType === 'do' || operationType === 'redo') {
     setUndoStack(draft => {
       draft.push(inverseOperation);
     });
   }
   if (operationType === 'undo') {
     setRedoStack(draft => {
       draft.push(inverseOperation);
     });
   }
   // FirebaseのHistoryに操作を保存する処理
   historyRef.current?.push(operation);
 },
 [setRedoStack, setUndoStack, uid],
);

Firebase Realtime Databaseでは子ノードの追加や変更などのイベントにリスナーを登録することができます。Historyにイベントリスナーを登録しておけば、ユーザーAが何らかの操作を加えてHistoryに新しくノードが追加されたとき、ユーザーBもそのイベントを検知してユーザーAの操作内容を知ることができます。またユーザーA自身の操作もこのイベントリスナーを経由してReduxのStateに反映されますが、楽観的更新により即座にリスナー関数が呼ばれるためラウンドトリップは発生しません。

編集過程の再現

システムデザイン形式選考ではアルゴリズム形式選考と同様に候補者の問題を解く過程を見ることができるプレイバック機能が搭載されています。プレイバック機能を実現するために、Firebase Realtime Databaseに保存されているユーザーの操作のログからElementの状態を復元する関数を用意しています。

Historyからチャートの状態を復元する関数

export const elementsFromFirebase = (
 histories: FlowHistory[],
 at?: number,
): { elements: Record<string, FlowElement>; elementIds: string[] } => {
 const elements: Record<string, FlowElement> = {};
 let elementIds: string[] = [];
 // 時間軸におけるtを指定してHistoryをsliceする
 const sliced = at !== undefined ? histories.slice(0, at + 1) : histories;

 sliced.forEach(history => {
   switch (history.s) {
     // 操作がElementの追加だった場合このcase節に入る
     case FLOW_ACTION.addElement: {
       const element = createElementFromlabel(history.v.id, history.v.l, history.v.x, history.v.y, history.t);
       elements[element.id] = element;
       elementIds.push(element.id);
       return;
     }
　  // 中略...
   }
 });

 return { elements, elementIds };
};

第一引数のhistoriesに全ての操作ログが含まれており、第二引数のatで時間軸におけるtを指定することにより、その時点でのElementの状態を出力します。関数内部では操作の種類ごとにSwitch文で処理が分岐し、操作内容に応じてチャートの状態を更新していきます。

時間軸をずらしながら繰り返し関数を呼ぶことにより、コマ送りで候補者の問題を解く様子を再現することができます。

以上、ドローイングツールの全体像を説明させていただきました。続いては共同編集技術とのコアとなる処理の競合を解消するアルゴリズムについて触れていきます。

処理の競合を解消する

共同編集では一方のユーザがオフラインになるようなケースにおいてユーザー同士で処理が競合する可能性があります。このような処理の競合を解消し、状態の整合性を保つアルゴリズムについて解説させていただきます。

Operational Transform（OT）

GoogleDocsなどの共同編集可能なテキストエディタで用いられているアルゴリズムにOperational Transform（OT）と呼ばれるものがあります。ユーザー間で競合する操作をマージして別の操作に変換することにより整合性を維持していくというのがOTの基本的なコンセプトです。

OTではユーザーの操作がピアによってACKされたタイミングで変更を適用するので、サーバーを経由してユーザー間で送受信の状態を同期する必要があり、また操作変換のアルゴリズム自体も複雑なものとなります。テキストエディタとは異なりドローイングツールではユーザーの変更内容が他方のユーザーの変更によって上書きされることも一定程度許容できるため、私たちのユースケースに対してOTはオーバースペックであると判断しました。

Conflict-free Replicated Data Type（CRDT）

ユーザー間で送受信の状態を同期させる必要があることから中央集権的なサーバーが必要となるOTに対して、Conflict-free Replicated Data Type（CRDT）は分散コンピューティングシステムを前提とし、ユーザー同士がサーバーを介することなく変更内容を送り合い、それぞれのユーザーが受けとった変更内容を自分自身の状態とマージします。

CRDTにはState-basedとOperation-basedの2つのアプローチが存在します。前者は変更を加えた際に変更後の状態そのものをピアに送信しますが、後者は更新操作のみをピアに送信します。

f:id:s__shintani:20220406230425p:plain — 図3: State-based CRDT

f:id:s__shintani:20220406230257p:plain — 図4: Operation-based CRDT

さらにOperation-based CRDTでは、全ての操作は可換（Commutative）である必要があります。可換とは操作の順序を入れ替えても結果が収束することを意味します。例えば、あるElementをx軸方向に20移動する操作と、y軸方向に20移動する操作は、どちらの操作から先に適用しても最終的にElementが（20, 20）の位置に存在するという1つの結果に収束します。

先にも述べた通り、私たちのユースケースとしてプレイバック機能で編集過程を再現する必要がありました。そこでOperation-based CRDTのアプローチを採用し、ユーザーの操作を可換な単位で定義することで、変更の反映順序を問わず最終的にユーザー間の状態が1つに収束することを目指しました。

エッジケース

上記のアプローチで開発を進める中でいくつかのエッジケースに直面したので、その中から2つ紹介させていただきます。

同じElementに対して更新が競合するケース

ユーザーAがあるElementの名前を「a」に変更し、ユーザーBが同じElementの名前を「b」に変更し、両者の変更が競合した場合、ピアの変更が自分自身の変更の後に反映されるので、最終的な結果はユーザーAは「b」、ユーザーBは「a」となります。

f:id:s__shintani:20220406224952p:plain — 図5: 更新が競合するケース

このようなケースにはLast one winsを適用し、Timestampが後の操作を優先することで対処しました。

同じElementに対して更新と削除が競合するケース

ユーザーAがあるElementの名前を「a」に変更し、ユーザーBがそのElementを削除し、両者の変更が競合した場合、ユーザーBは自分自身が削除したElementに対して後から更新がかかります。このときElementをStateから物理削除してしまうと、更新対象のElementが存在せずパニックを起こします。

f:id:s__shintani:20220406224907p:plain — 図6: 更新と削除が競合するケース

このようなケースではElementを論理削除して削除した後も更新ができるようにしておきます。こうしておくことで、例えばユーザーBがUndoで消されたElementを復活させた場合でも、ユーザーAとユーザーBの間でElementの名前の不整合を防ぐことができます。

まとめ

いかがだったでしょうか？OTのような複雑なアルゴリズムを実装しなくても、ユースケース次第では比較的シンプルに共同編機能を実現できることがお分かりいただけたかと思います。ドローイングツールについてはまだまだUX面で改善の余地があり、引き続きブラッシュアップを重ねながらシステムデザイン形式選考をより進化させていきますのでご期待ください。

HireRooでは私のように業務1年目のエンジニアやインターンの方でも裁量をもって大きなタスクを進めることができます。周りの優秀なメンバーから学ぶことも多く、成長環境としては打ってつけだと思います。レベルの高い環境で挑戦してみたいと思う方がいたらぜひ以下のリンクからご連絡ください！

HireRoo TechBlog

HireRooの技術ブログ