Reflect - ゲームスタイルの同期を適用したマルチプレイヤーWebアプリフレームワーク

 (rocicorp.dev)
7 ポイント 投稿者 GN⁺ 2023-10-19 | 1件のコメント | WhatsAppで共有
  • Reflectは、Figma、Notion、Google Sheetsのようなコラボレーションアプリを素早く作るためのフレームワークで、Replicacheのゲーム的な同期エンジンにフルマネージドサーバーを加えて公開された
  • コラボレーションUIはサーバー応答を待たずにローカルの変更を即座に表示する必要があるため、同時に同じデータを編集したときの競合処理の方式が製品体験を左右する
  • ReflectはCRDTの代わりにTransactional Conflict Resolutionを採用し、クライアントとサーバーが同じmutator呼び出し履歴を実行し、サーバーが到着順に権威ある状態を作る
  • Yjsのようなsequence CRDTはテキスト・リスト・マップに強いが、カウンターのように別個のマージ規則が必要な場合は増分が失われることがあり、Reflectはmutatorの再実行で算術・リスト操作・上位の不変条件を処理する
  • サーバーはmutation名と引数だけを受け取って結果を再計算するため、クライアントの計算結果を信頼せず、権限チェック、スキーマ検証、マイグレーションを設計に組み込みやすい

Reflectが公開した開発体験

  • Reflectは、Figma、Notion、Google SheetsのようなマルチプレイヤーWebアプリを作るための新しい方法
  • 既存のクライアントサイド同期フレームワークであるReplicacheの進化版で、同じゲーム的な同期エンジンを使う
  • Replicacheと違ってフルマネージドサーバーを含み、高品質なマルチプレイヤーアプリを数分で作れるようにすることを目指している
  • Reflectは今回初めて一般公開され、reflect.netで紹介を見て、hello.reflect.netから始められる

コラボレーション編集で競合が生じる構造

  • コラボレーション編集では必然的に競合が発生する
  • 即時に反応するUIを作るにはサーバーを待てず、変更はまずクライアントローカルで起こる必要がある
  • 複数のユーザーが同時に同じ項目を編集できるため、全員が同じ結果を見るように競合を同期し、自然に解決しなければならない
  • 同期エンジンは開発者体験、ユーザー体験、実現可能な性能、作れるアプリの種類まで左右する

CRDTとYjsカウンターの例

  • Webエコシステムでは、CRDTがデータ同期方式として広く使われている
  • CRDTは、共同編集者間の変更がすべて交換されると同じ値に収束するデータ構造で、YjsとAutomergeが代表的なオープンソースCRDTライブラリ
  • ReflectはCRDTではなく、ビデオゲーム業界で長く使われてきたServer Reconciliationを変形したTransactional Conflict Resolutionを使う

  • Yjsで単純なカウンターが壊れる理由

    • Yjs Mapにcount値を保存し、prev + 1を書き戻す方式は、同時実行の状況で増分を失う可能性がある
    • Yjsドキュメントにある正しいカウンターの例は、数値を配列に追加して合計を計算する方式
    • Yjsはsequence CRDTなので、リスト、テキスト断片、マップには強いが、カウンターを自然にモデル化するのは難しい
    • Yjs Mapのマージアルゴリズムはキーごとのlast-write wins方式なので、2人のユーザーが同時に増加させると、どちらか一方の変更が消える可能性がある
    • CRDTは特定の問題には非常によく適合するが、その問題でなければ拡張しづらいという限界がある

Transactional Conflict Resolutionの動作方式

  • Reflectでは変更はmutatorという特別なJavaScript関数として実装される
  • 各mutatorのコピーは、すべてのクライアントとサーバーに存在する
  • ユーザーが変更を作ると、Reflectはmutator呼び出しの記録であるmutationを生成する
    • mutationにはincrement(delta: 1)のようにmutator名と引数だけが入る
    • 結果として生じた変更内容はmutationに含まれない
  • Reflectはmutationを即座にローカルへ適用してUIを更新し、ユーザーは自分の変更をすぐに見られる

  • サーバー線形化と再実行

    • 各クライアントはサーバーを待たずにmutationを追加し続ける
    • mutationはサーバーへストリーミングされ、サーバーは到着時刻順にmutationを線形化したうえで次の権威状態を生成する
    • たとえばクライアント1のincrement(1)とクライアント2のincrement(2)が同時に発生した場合、サーバー実行では到着順に応じて最終カウントが作られる
    • サーバーはincrementが何をするか、どうマージするかに関する別個の知識なしに、実行履歴を線形化することで競合をマージする
    • 最新の権威状態は各クライアントへ継続的にストリーミングされる
    • クライアントは、自分の保留中mutationが権威状態に適用されたと分かると、ローカルキューから削除する
    • 残っている保留mutationは最新の権威状態の上でmutatorコードを再実行してrebaseされる
    • この一連のサイクルはクライアントごとに毎秒最大120回発生する

実装コストと一般化できる利点

  • この方式を実装するには、巻き戻し、フォーク、ブランチを作れる高速なデータストアが必要になる
  • サーバー側でも、流入するmutationを処理できる高速なストレージが必要になる
  • mutatorを同期する方法と、クライアントまたはサーバーが同期中に競合したときの復旧処理が必要になる
  • その代わり、任意の関数の線形化はかなり汎用的な同期戦略として機能する

  • 別個の同期コードなしで処理できる例

    • 算術演算は自然に処理される
    • setHighScoreは既存のhigh-scoreと候補スコアのうち大きい方を保存する
    • ほとんどのリスト操作も動作する
    • appendはショッピングリストの末尾に項目を追加する
    • insertAtは指定位置に項目を挿入し、splice()が位置を補正する
    • removeはインデックスが変わりうるため、項目または安定したIDを引数に取る必要がある
    • 上位レベルの不変条件も強制できる
    • addChildは親のchildIDsと子のparentIDが常に一貫するように一緒に更新する
    • こうした例は、同期を意識した別個のコードなしでも合理的にマージされる

サーバー権威と権限チェック

  • Reflectではサーバーが権威者
  • クライアントが変更結果をどう考えているかは、サーバーや他のクライアントには共有されない
  • サーバーへ送られるのはmutation名と引数だけで、サーバーがmutation結果を自ら再計算する
  • サーバーはクライアントと同じコードを実行する必要もなく、外部サービスを照会したり乱数を使ったりすることもできる

  • きめ細かな権限付与

    • この設計では、きめ細かな権限チェックを自然に組み込める
    • 共同デザインプログラムで、ゲストにはコメントとハイライトは許可するが、実際のデザイン変更は禁止するケースが例として挙げられる
    • CRDTでは権限のない変更を拒否するロジックを置く場所がないため、実装が難しい
    • Reflectでは、サーバーで実行されるmutatorがtx.user.canEditのような値を確認し、権限がなければunauthorizedエラーを投げられる
    • mutatorがサーバー上でクライアントと異なるコードを実行しても問題はなく、サーバーが最終決定を下す

スキーマ検証と利用案内

  • Reflectのアプローチでは、スキーマ検証とマイグレーションも設計に自然に組み込める
  • 同期戦略の選択はマルチプレイヤーシステムの中核であり、Reflectはゲーム業界の方式から学んだTransactional Conflict Resolutionを、シンプルで柔軟かつ強力な方式と捉えている
  • マルチプレイヤーアプリを作っているなら、Reflectスタートページで試せる
  • 開発チームと話すには、discord.reflect.netまたは@hello_reflectを利用できる

関連記事

1件のコメント

 
GN⁺ 2023-10-19
Hacker Newsの意見

  • ホームページ上部のデモ（https://reflect.net/) がかなり面白い
    見ていると、パズルが完成するたびに人々が「やったぞ！」と言わんばかりにカーソルを振って喜んでいる

    • ピースで FUCK という単語を作り始めたら、ほかの人たちが気づいて一緒に参加してくれて、意外にもほっこりする体験になった
    • 完成した e の部分の後ろに e のピースを隠せる視覚的なバグがある
      ほかの文字は輪郭線がずっと見えるので、同じやり方ではできない
    • このデモはライブラリの機能をうまく示す例ではない気がする
      ピースをつかむと、そのピースがそのユーザーにロックされるように見えるので、解決すべき競合がほとんどなく、2人が同時につかんだときに先につかんだユーザーへ渡す程度しか残らない
      実際に競合解決が起きる、もっと良いデモ例を見てみたい
    • 本当に楽しい体験だ
      説明した場面を収めた動画はこちら: https://streamable.com/asu261

  • 以前 Replicache として1、2回取り上げられていたのを覚えているかもしれない
    Reflectは、完全マネージドで非常に高速な同期サーバーを追加した形だ
    ローカルファースト／リアルタイム分野は最近にぎわっているが、Replicache/Reflectはデータモデルとコーディングモデルが美しくシンプルなので確認する価値がある
    CRDTと比べた利点は、競合を単純な逐次コードで直接処理できる点で、組み込みルールが合わないときにアプリケーション固有の競合解決をCRDTに追加するのは複雑になり得ると思う

  • 約15年前、祖母の家で退屈しのぎにこのテーマをかなり深く扱い、JavaScript実装も試した
    「算術演算はそのまま動く」というのは、もちろん冪等演算にするのが非常に簡単だが、「リスト演算もそのまま動く」という話には同意しにくい
    たとえば [1, 2, 3, 4, 5] のような配列で、Aが2〜4の範囲を削除し、Bが3〜5の範囲を削除し、Cが3と4の間に何かを挿入するとしよう。この3つの更新が同時にサーバーへ到着したとき、解法はあいまいだ
    タイムスタンプや最後の書き込みを優先（Last Write Wins）に頼るとトランザクションモデルが壊れ、どれか1つを勝者にすると、ほかのユーザーが何を見るのか、それをどう伝えるのかも問題になる
    「配列全体を送り直す」が答えなら、やはりトランザクションモデルは壊れる

    • 指摘は妥当だ
      実際に意図していた表現は「多くのリスト演算はそのまま動く」に近かった
      Reflectでは編集／削除の識別子としてリストインデックスを使えない。インデックスは安定していないためで、アトミックであれば項目そのものを、通常は安定したIDを使うように述べた理由がここにある: https://i.imgur.com/IKzmf0q.png
      Cの挿入が削除され得る問題もあるが、リアルタイム共同作業の文脈では、どのプロトコルも完全には解決できない
      Cの立場では、今書いた内容が消えて悲しいかもしれない。こうしたことは、同じ空間で同時に作業する人間同士の意図が異なることで起きる現象なので、取り消しや現在の作業者表示のような社会的な仕組みが役に立つ
    • 削除を持ち出さなくても、「同時に」AがリストLに「a」を追加し、Bが「b」を追加し、Cが「c」を追加すると、サーバーは任意の順序で追加を適用してから結果をクライアントへ送る
      その間、各クライアントは自分の追加をローカルに適用して、Aは[“a”]、Bは[“b”]、Cは[“c”]を見ている可能性がある。サーバーが[“c”, “b”, “a”]の状態を送ると、クライアントは保留中の変更を捨て、サーバー状態を世界の真実とみなすことになりそうだ
      ただ、各追加が「自分の変更が先に適用されれば勝ち」のような効果を生むなら、サーバー更新を待つ300msの間、全員が「you win」を見るのか気になる
    • こうしたシステムの多くは、削除をトゥームストーンとして扱う
      そうすれば、削除された項目の後ろや間に安全に挿入できる
    • 共同作業アプリケーションでは、サーバーは3つの操作をどの順序でも解決できる
      3人のユーザーが結果を見て、同じデータを同時に触って状態がこじれたことに気づき、その後で直せばよい
      ドキュメント編集を思い浮かべればいい
      互いが作業中であることを見られないなら驚くかもしれないが、最終的には望む状態に直せる
      結果を確認しない、または確認できないなら状態は正しくないだろうが、共同編集やゲームのようなインタラクティブなアプリでは通常そういう流れにはならない

  • このプロジェクトに参加した一人で、質問があれば答えられる

    • Aaron は控えめなので代わりに言うと、彼は Greasemonkey を作り、長年にわたって複数の画期的なブラウザ革新に関わってきた
    • 以前、非公開のコードベースで複数の マルチプレイヤー同期システムを作りながら、この分野を見てきた
      リベースとサーバー正本性を備えた「redux-pubsub」ライブラリも作っていて、私の理解では TCR に似ている
      このモデルには気に入っている点が多く、リンク先の記事も非常に明快
      「スキーマ検証とマイグレーションは設計から自然に、ほぼ無料で付いてくる」とあったが、マイグレーションで実際にうまく機能したやり方が気になる
      また、TCR システムで相当量の共有テキスト編集を扱うユースケースなら、通常は Yjs と Tiptap/ProseMirror をまず思い浮かべるが、CRDT ドキュメントと TCR ドキュメントを並列に置く形が最善なのか気になる
    • Replicache の開発は今後どうなるのか気になる
      クライアント側のコードベースは大部分が共有されていて、引き続きアップデートを期待してよいのか、それとも Reflect が主な焦点に置き換わる可能性が高いのか知りたい
    • ElectricSQL についてどう考えているのか気になる
    • 1つの部屋に同時に入れる 最大ユーザー数はどの程度なのか気になる

  • 用語が少し紛らわしい
    ゲームには「プレイヤー」がいるので同期システムを「マルチプレイヤー」と呼ぶが、一般的なソフトウェアには「ユーザー」がいるので、マルチユーザーと呼ぶほうが適切に見える
    ページ内で「ユーザー」と「マルチプレイヤー」を混ぜて使っているので、読んでいて不自然に感じる

    • そうかもしれないが、「ユーザー」は消費者のように聞こえる
      HN はマルチユーザーサービスだが、HN をマルチプレイヤーと呼ぶのは変だ
      リアルタイムの同時インタラクションにはマルチユーザーより強い何かがあり、複数のユーザーが行動し相互作用するという意味での マルチプレイヤーは悪くない用法に見える
    • このロジックは何十年も マルチプレイヤーゲームで使われてきたロジックに基づいている
      逆に、すべての Web ソフトウェアはマルチユーザーなので、その言葉だけでは何の情報も与えない
    • 最近の用語は単にそう定着している
      マルチプレイヤーは、他のユーザーがその瞬間ごとに何をしているかを可視化する ライブなマルチユーザーを意味する

  • 2年ほど CRDT を軽く追っていて、いつも 認可はどうなるのか気になっていた
    この記事は、Y.js のような CRDT ライブラリだけでは、変更に権限チェックが必要なアプリケーションを適切に扱うのは難しいことを示唆しているように見える
    中央の権威、つまりサーバーがないためで、Reflect はサーバーがクライアント間のやり取りを仲介する前提のように見えるが、この理解で合っているのか気になる

    • 「できない」は強い言い方
      努力すれば CRDT でも権限処理は可能で、たとえばすべての間にサーバーを置き、サーバーから見て権限のない変更を巻き戻させることはできる
      しかしアプリケーションが大きくなるほど保守が増え、壊れやすくなり、そもそも CRDT の利点の一部も失われる
      サーバーがすでに途中にいるなら、最初からサーバーがメッセージを拒否できる プロトコルを使うほうがはるかに単純
    • CRDT もサーバーを含めることはできる。ただしサーバーが必ずすべての中心にいる必要はない
      たとえば接続の認証はサーバーが担当できる
      誰かが P2P で接続して特定の権限を主張したら、その主張をサーバーで検証できる
      また、CRDT が必ず P2P を意味するわけではなく、中央サーバーでメッセージを中継しつつ、サーバーとクライアントの両方で現在状態を解決する CRDT モデルを維持することもできる
    • 各操作やメッセージに 署名し、アクセス制御リストの公開鍵と一致するか検証する方法で権限を扱える
      この方法なら CRDT は P2P の文脈でも動作できる
      ただしサーバーが権威者なら、権限のないクライアントのメッセージを単に拒否すればよい

  • mutator のアップグレードはどう処理するのか気になる
    クライアントが古いコードを実行中だと操作がサーバーと異なるはずで、明白な答えは increment_v1, increment_v2 のように独立してバージョン管理することだが、もっとよい方法があるのか気になる

    • 今のところ、保留中の変更を持つクライアントがもう存在しないと分かるまで 以前の mutator を削除しない、という以上に良い答えはない
      まだ永続化を有効にしていないため、現時点ではその期間はかなり短い

  • リリースおめでとう
    https://partykit.io/ と似た系統なのか気になる

    • 同じ領域にある
      中心的な違いは、それぞれがどれだけ 意見の強い設計を持っているか
      PartyKit は非常に非規定的で、素早く始められ自動スケールする軽量な JavaScript サーバーに近い
      多くは PartyKit 上で yjs を動かしているようだが、automerge や Replicache も動かせる
      Reflect は可能な限り最高のマルチプレイヤー体験を提供することに完全に集中し、スタック全体で多くの選択を強く統合して、マルチプレイヤーがそのまま動作し、アプリケーション実装に集中できるようにする計画

  • 参考までに、この戦略はゲーム開発の分野では決定論的ロックステップと呼ばれており、状態を同期する必要があるエンティティが多いゲームで特によく使われる
    代表的な例は、ほぼすべてがこの方式を使っているリアルタイムストラテジーゲーム

    • より正確には、クライアントがローカルの変更を表示する前にサーバー応答を待たないため、決定論的ロールバックに近い
      Mortal Kombat と Injustice 2 の実装を深く説明した優れた GDC 講演がある: https://youtu.be/7jb0FOcImdg
    • これは決定論的ロックステップではない
      決定論的ロックステップは P2P ゲームのアルゴリズムで、各参加者が他の全プレイヤーの入力を待ってからゲームシミュレーションを進める
      「決定論的」なのはシミュレーション結果ではなく入力を共有し、同じ入力に対してシミュレーションが決定論的であるためで、「ロックステップ」なのはすべてのクライアントが調整された速度で前進するため
      Age of Empires シリーズがこの方式を使っているため、クリックしてもユニットはすぐには動かず、StarCraft もこれを使いつつ、プレイ感を滑らかにする工夫がある
      Reflect は P2P ではなく、サーバー権威シミュレーションに近い
      クライアントは入力をサーバーに送るが、結果を待たずにローカルで予測し、サーバーは個別クライアントの遅延を補正するために時間を巻き戻して入力を再生する
      その後、クライアントは自分の入力が含まれたサーバー結果を受け取ると、ローカルシミュレーションを補正する
      このアルゴリズムのキーワードは、サーバー権威、予測、遅延補正、予測の調整
      Reflect にあるかは分からないが、FPS ゲームではワールド更新を受け取ると、一定時間をかけてエンティティを新しい位置と回転へ補間するクライアント側補間も一般的
      権威者はサーバー1つだけなので決定性は非常に重要というわけではないが、クライアント予測で誤予測を減らすうえでは有用
      誤予測は、他のクライアント入力が世界状態を大きく変える場合や、乱数生成が同期されていないなど、シミュレーションが決定論的でない場合に発生する
      Counter Strike には、「nospread」チートを防ぐために弾の拡散の乱数を同期しない例もある
      https://www.gabrielgambetta.com/client-side-prediction-live-...
      https://developer.valvesoftware.com/wiki/Latency_Compensatin...
      https://developer.valvesoftware.com/wiki/Source_Multiplayer_...

  • Reflect は素晴らしい
    現在プロダクションでアルファ版を使用しており、システムだけでなく Aaron とチームにも非常に満足している
    顧客の立場から質問があれば答えられる