Google ドキュメントのシステム設計の詳細説明（共同ドキュメント編集）

1 共同文書編集サービスの設計方法

1.1 C/Sアーキテクチャによる集中型施設

すべてのユーザーにドキュメント編集サービスを提供します。すべてのユーザーは、ドキュメント データを保存および処理する中央サーバーに接続し、ユーザーはサーバーに接続して共同でドキュメントを編集します。セキュリティと制御性は向上するが、単一障害点の問題が発生する

1.2 ピアツーピア技術の設計

単一のドキュメントで共同作業を行う。ドキュメント データは複数のユーザー デバイスに保存され、各ユーザーはドキュメントを直接編集し、変更内容を他のユーザー デバイスに同期できます。柔軟性と拡張性は向上しますが、データ同期の遅延やデータの競合が発生する可能性があります。

ほとんどの商用ソリューションは、より洗練された制御を実現するために C/S アーキテクチャに重点を置いています。そのため、この記事でもC/Sアーキテクチャ設計サービスを利用しています。

2 要件

2.1 機能性

① ドキュメントコラボレーション

複数のユーザーが同時にドキュメントを編集できます。多数のユーザーがドキュメントを閲覧できる必要があります。

②紛争解決

システムは、1 人のユーザーが行った編集内容を他のすべての共同作業者にプッシュする必要があります。システムは、複数のユーザーがドキュメントの同じ部分を編集している場合に、ユーザー間の競合も解決する必要があります。

③ 提案

• 文書内の一般的な単語、フレーズ、キーワードの完全な提案
• 文法エラーを修正するための提案

④ 閲覧回数

ドキュメントの編集者は、そのドキュメントの閲覧回数を確認できる必要があります。

⑤ 歴史

ユーザーはドキュメントの共同作業履歴を表示できます。

2.2 非機能的

① 遅延

異なるユーザーが接続して同じドキュメントで共同作業を行うことができます。さまざまな地域のユーザーに対して低遅延アクセスを維持します。

②一貫性

システムは、ドキュメントを同時に編集しているユーザー間の競合を解決し、ドキュメントの一貫した表示を実現できる必要があります。異なる地域のユーザーには、ドキュメントの更新されたステータスが表示されます。

一貫性を維持することは、同じリージョンに接続するユーザーにとっても、異なるリージョンに接続するユーザーにとっても重要です。

③ 在庫状況

サービスは常に利用可能であり、障害に対する堅牢性を実証する必要があります。

④ スケーラビリティ

多数のユーザーが同時にサービスを利用できる必要があります。同じドキュメントを表示したり、新しいドキュメントを作成したりできます。

3 つのコンポーネント

3.1 データストレージ

• 権限制限を適用するためにユーザー情報とドキュメント関連情報を保存するリレーショナルデータベース
• ユーザーのコメントを保存してアクセスを高速化するNOSQL
• 時系列、ドキュメントの編集履歴を保存するために使用される
• ドキュメント内のビデオや画像を保存するためのBlobストレージ
• キャッシュ、Redis や CDN などの分散キャッシュは、エンドユーザーに優れたパフォーマンスを提供します。 Redis を使用して、ユーザー セッション、期待されるサービス タイプの関数、頻繁にアクセスされるドキュメントなど、さまざまなデータ構造を保存します。 CDN は、頻繁にアクセスされるドキュメントや、画像やビデオなどの重いオブジェクトを保存します。

3.2 処理キュー

小さな文字の変更ごとに HTTP 呼び出しを使用するのは非効率的です。したがって、WebSocket を使用してオーバーヘッドを削減し、さまざまなユーザーによるドキュメントの変更をリアルタイムで観察します。

3.3 その他

セッション サーバーは、ユーザー セッション情報を維持します。セッション サーバーを通じてドキュメントのアクセス権限を管理します。また、サーバー障害時のリーダーの監視と選出、ユーザー通知のキューイング、デバッグ情報のログ記録などの監視タスクを処理するための構成、監視、パブリッシュ/サブスクライブ、ログ記録サービスもあります。

共同文書編集サービスの詳細設計:

写真

4 ワークフロー

4.1 共同編集と競合解決

各リクエストは操作キューに転送されます。ここで、同じドキュメントの異なる共同作業者間の競合が解決されます。競合がない場合、データはセッション サーバーを介して時系列データベースにバッチで保存されます。ビデオや画像などのデータは圧縮されてストレージが最適化され、文字は即座に処理されます。履歴: 時系列データベースの助けを借りて、さまざまなバージョンのドキュメントを復元できます。 DIFF 操作を使用すると、バージョンを比較して相違点を識別し、同じドキュメントの古いバージョンを復元できます。

4.2 非同期操作

通知、電子メール、閲覧数、コメントはすべて、Kafka などのパブリッシュ/サブスクライブ コンポーネントを介してキューに入れることができる非同期操作です。 API ゲートウェイはこれらのリクエストを生成し、パブリッシュ/サブスクライブ モジュールに転送します。

4.3 推奨事項

提案は、よく使用される単語やフレーズの自動補完を提供する先行入力サービスの形式で提供されます。先行入力サービスでは、ドキュメントから属性やキーワードを抽出し、ユーザーに提案を提供することもできます。単語数が多くなる可能性があるため、この目的には NoSQL データベースを使用します。さらに、最も頻繁に使用される単語やフレーズは、Redis などのキャッシュ システムに保存されます。

4.4 ドキュメントのインポートとエクスポート

アプリケーション サーバーは、ドキュメントのインポートやエクスポートなど、多くの重要なタスクを実行します。アプリケーション サーバーは、ドキュメントをある形式から別の形式に変換することも行います。たとえば、.doc または .docx ドキュメントを .pdf に変換したり、その逆を行ったりできます。アプリケーション サーバーは、期待されるサービスのタイプの特性を抽出する役割も担います。

5 詳細設計

5.1 ドキュメントエディタ

文書は特定の順序で並べられた文字で構成されます。各文字には値と位置インデックスがあります。文字は、英字、数字、改行 ()、またはスペースになります。インデックスは、順序付けられた文字リスト内の文字の位置を表します。

テキスト エディターまたはドキュメント エディターの機能は、ドキュメント内の文字に対して insert()、delete()、edit() などの操作を実行することです。以下は、ドキュメントとエディターがこれらの操作を実行する方法の図です。

ドキュメントエディタがさまざまな操作を実行する方法

写真

5.2 並行性

異なるユーザーが同じドキュメントで共同作業を行うと、同時実行の問題が発生する可能性があります。複数のユーザーがドキュメントの同じ部分を編集すると、競合が発生する可能性があります。ユーザーはドキュメントのローカル コピーを持っているため、サーバー上の最終的なドキュメントの状態は、ユーザーが自分の側で見るものと異なる場合があります。サーバーが更新されたバージョンをプッシュすると、ユーザーは予期しない結果に遭遇することになります。

①同じ位置のインデックスに文字を追加する

2 人のユーザーが同じ文字を変更すると、同時実行の問題が発生する可能性があります。

写真

②同じ文字を削除する

同じ文字を削除すると、予期しない変更が発生する可能性があります。

写真

2 番目の例は、異なるユーザーによって適用された同じ操作がべき等ではないことを示しています。したがって、複数の共同作業者がドキュメントの同じ部分を同時に編集する場合は、競合の解決が必要になります。

共同編集における同時実行の問題の解決には、次のルールに従う必要があります。

• 交換法則: 演算を適用する順序は最終結果に影響を与えない
• 冪等性: 同様の操作を繰り返しても、一度だけ適用される

6つの紛争解決テクニック

6.1 業務変革（OT）

共同編集における競合解決に広く使用されている技術で、ロックフリーかつ非ブロッキングの競合解決方法です。共同作業者間の操作が競合する場合、OT は競合を解決し、正しい収束状態をエンド ユーザーにプッシュします。したがって、OT はユーザーに一貫性を提供します。

OT は、位置インデックス アプローチを使用して、上記のような競合を解決する操作を実行します。上記の問題は、交換法則とべき等性を維持することで解決されます。

OTの例:

写真

OT ベースの共同エディターは、次の 2 つのプロパティを満たす場合に一貫性があります。

• 因果関係は維持されます。操作aが操作bより前に発生した場合、操作aが最初に実行され、次に操作bが実行されます。
• 収束: 異なるクライアント上の文書のすべてのコピーは最終的に同一になる

上記のプロパティは、共同編集における一貫性維持のためのモデルである CC 一貫性モデルの一部です。

OTのデメリット

文字に対する各操作では、位置インデックスの変更が必要になる場合があります。これは、操作間に順次的な依存関係があることを意味します。開発と実装は困難です。

OT は複雑なアルゴリズムのセットであり、実際のアプリケーションでは正しく実装することが困難であることが証明されています。 Google Wave チームは OT の実装に 2 年を費やしました。

6.2 競合のない複製データ型 (CRDT)

OTを改善することです。 CRDT には次の機能があります。

• 複雑なデータ構造
• しかし、簡略化されたアルゴリズム

CRDT は、各文字に 2 つの重要なプロパティを割り当てることで、可換性と冪等性を満たします。

• 各文字にグローバルに一意の識別子を割り当てる
• 各文字をグローバルに順序付ける

各操作のデータ構造が更新されました: CRDT の簡素化されたデータ構造

写真

SiteID は、値と PositionalIndex を使用して、操作を要求しているユーザー サイトを一意に識別します。 PositionalIndex 値は小数にすることができます:

• 一部の操作では他の文字のPositionalIndexは変更されません
• 異なるユーザーアクション間の順序依存性を回避する

この例では、サイト ID 123e4567-e89b-12d3 のユーザーが、位置 1.5 に値 A を持つ文字を挿入しています。新しい文字が追加されても、既存の文字の位置インデックスは小数インデックスを使用して保持されます。したがって、操作間の順序依存性は回避されます。以下に示すように、O と T の間に () を挿入しても、T の位置は影響を受けません。

操作間の順序依存性を防ぐ:

写真

CRDT はユーザー間の強力な一貫性を保証します。一部のユーザーがオフラインの場合でも、オンラインに戻ると、エンド ユーザーのローカル コピーが収束されます。

Google Docs、Etherpad、Firepad などの有名なオンライン編集プラットフォームは OT を使用していますが、CRDT を使用すると、共同ドキュメント編集における同時実行性と一貫性が容易になります。実際、CRDT を使用すると、サーバーレスのピアツーピア共同ドキュメント編集サービスを実装できます。

6.3 注記

OT と CRDT は共同編集における競合解決に適したソリューションですが、共同編集者のカーソルを強調表示するために WebSocket を使用します。他のユーザーも、共同作業者の次の行動を予測し、自然かつ意識的に衝突を回避することができます。

7 結論

7.1 一貫性

操作変換 (OT) と競合不確定解決データ型 (CRDT) により、ドキュメント内の競合解決における強力な一貫性が実現します。

時系列データベースはイベントの順序を保持します。 OT または CRDT が競合を解決すると、最終結果がデータベースに保存されます。これにより、個々の操作の一貫性を実現できます。

IDC 内の異なるサーバー間でドキュメント ステータスの一貫性を維持します。更新されたドキュメントのステータスを同じ IDC 内で同時に複製するには、Gossip プロトコルなどのピアツーピア プロトコルを使用できます。これにより、一貫性が向上するだけでなく、可用性も向上します。

7.2 可用性

当社の設計では、レプリカの使用と、監視サービスを使用したプライマリレプリカサーバーの監視を通じて可用性を確保します。操作キューやデータ ストアなどの主要コンポーネントは、独自のレプリケーションを内部で管理します。

WebSocket を使用して、WebSocket サーバーはユーザーをセッション維持サーバーに接続し、ユーザーがドキュメントをアクティブに表示しているか共同作業しているかを判断します。

したがって、複数の WebSocket サーバーを維持することで、設計の可用性が向上します。最後に、キャッシュ サービスと CDN を使用して可用性を向上させます。

7.2 スケーラビリティ

マイクロサービスを使用しているため、操作キューへのリクエスト数が容量を超えた場合でも、各コンポーネントを個別に簡単に拡張できます。複数の操作キューを使用できます。この時点で、各操作キューは 1 つのドキュメントを担当することになります。異なるユーザーによって要求された単一のドキュメントに関連する操作を特定のキューに転送できます。生成されるキューの数は、アクティブなドキュメントの数と等しくなります。したがって、水平方向のスケーラビリティを実現できます。

参照:

• プログラミング選択ネットワーク