Reflect - Un framework pour applications web multijoueurs avec synchronisation de style jeu

 (rocicorp.dev)
7 points par GN⁺ 2023-10-19 | 1 commentaires | Partager sur WhatsApp
  • Reflect est un framework conçu pour créer rapidement des applications collaboratives comme Figma, Notion ou Google Sheets, en ajoutant à son serveur entièrement managé le moteur de synchronisation inspiré du jeu de Replicache
  • Une interface collaborative doit afficher immédiatement les changements locaux sans attendre la réponse du serveur ; la gestion des conflits lorsque plusieurs personnes modifient les mêmes données en même temps détermine donc largement l’expérience produit
  • Au lieu d’un CRDT, Reflect choisit la Transactional Conflict Resolution : clients et serveur rejouent le même historique d’appels de mutators, et le serveur construit l’état faisant autorité dans l’ordre d’arrivée
  • Les sequence CRDT comme Yjs excellent sur le texte, les listes et les maps, mais dans des cas qui demandent des règles de fusion spécifiques, comme un compteur, des incréments peuvent disparaître ; Reflect gère l’arithmétique, les opérations sur listes et les invariants de plus haut niveau par réexécution des mutators
  • Comme le serveur ne reçoit que le nom de la mutation et ses arguments avant de recalculer le résultat, il n’a pas à faire confiance aux résultats calculés côté client, ce qui facilite l’intégration des contrôles d’accès, de la validation de schéma et des migrations dans la conception

L’expérience de développement présentée par Reflect

  • Reflect propose une nouvelle manière de créer des applications web multijoueurs comme Figma, Notion ou Google Sheets
  • C’est une évolution de Replicache, framework historique de synchronisation côté client, et il utilise le même moteur de synchronisation inspiré du jeu vidéo
  • Contrairement à Replicache, il inclut un serveur entièrement managé avec pour objectif de permettre de créer en quelques minutes des applications multijoueurs de haute qualité
  • Reflect est disponible publiquement pour la première fois ; on peut découvrir la présentation sur reflect.net et démarrer sur hello.reflect.net

Pourquoi les conflits apparaissent en édition collaborative

  • En édition collaborative, les conflits sont inévitables
  • Pour produire une interface réactive immédiatement, il est impossible d’attendre le serveur, et les changements doivent d’abord se produire localement sur le client
  • Comme plusieurs utilisateurs peuvent modifier le même élément en même temps, il faut synchroniser les conflits et les résoudre naturellement pour que tout le monde voie le même résultat
  • Le moteur de synchronisation détermine l’expérience développeur, l’expérience utilisateur, les performances possibles et jusqu’au type d’applications qu’il est possible de construire

Les CRDT et l’exemple du compteur dans Yjs

  • Dans l’écosystème web, les CRDT sont largement utilisés comme méthode de synchronisation des données
  • Un CRDT est une structure de données qui converge vers la même valeur dès lors que tous les changements entre collaborateurs ont été échangés ; Yjs et Automerge en sont des bibliothèques open source emblématiques
  • Reflect n’est pas un CRDT ; il utilise une Transactional Conflict Resolution, adaptation du Server Reconciliation employé depuis longtemps dans l’industrie du jeu vidéo

  • Pourquoi un compteur simple se casse dans Yjs

    • Stocker une valeur count dans une Yjs Map puis réécrire prev + 1 peut faire perdre des incréments en situation de concurrence
    • L’exemple de compteur correct dans la documentation Yjs consiste à ajouter les nombres dans un tableau puis à calculer la somme
    • Yjs est un sequence CRDT : il est donc très bon pour les listes, les fragments de texte et les maps, mais il modélise difficilement un compteur de façon naturelle
    • L’algorithme de fusion de la Yjs Map fonctionne clé par clé en last-write wins ; si deux utilisateurs incrémentent en même temps, l’un des changements peut disparaître
    • Les CRDT conviennent très bien à certains problèmes, mais deviennent difficiles à étendre dès qu’on sort de ce cadre

Comment fonctionne la Transactional Conflict Resolution

  • Dans Reflect, les changements sont implémentés via des fonctions JavaScript spéciales appelées mutators
  • Une copie de chaque mutator existe sur tous les clients et sur le serveur
  • Lorsqu’un utilisateur produit un changement, Reflect crée une mutation, c’est-à-dire un enregistrement d’appel de mutator
    • Une mutation ne contient que le nom du mutator et ses arguments, comme increment(delta: 1)
    • Le contenu des changements produits n’est pas inclus dans la mutation
  • Reflect applique immédiatement la mutation localement pour mettre à jour l’interface, ce qui permet à l’utilisateur de voir son changement sans délai

  • Linéarisation côté serveur et réexécution

    • Chaque client continue d’ajouter des mutations sans attendre le serveur
    • Les mutations sont envoyées en flux vers le serveur, qui les linéarise dans leur ordre d’arrivée afin de produire l’état faisant autorité suivant
    • Par exemple, si le client 1 exécute increment(1) et le client 2 increment(2) au même moment, le compte final est construit côté serveur selon l’ordre d’arrivée
    • Le serveur fusionne les conflits en linéarisant l’historique d’exécution, sans connaissance spécifique de ce que fait increment ni de la manière de le fusionner
    • L’état faisant autorité le plus récent est ensuite diffusé en continu vers chaque client
    • Lorsqu’un client voit qu’une de ses mutations en attente a été appliquée à l’état faisant autorité, il la retire de sa file locale
    • Les mutations restantes en attente sont rebasées par réexécution du code du mutator au-dessus du dernier état faisant autorité
    • Ce cycle complet peut se produire jusqu’à 120 fois par seconde et par client

Coût d’implémentation et avantages généralisables

  • Mettre en œuvre cette approche nécessite un datastore rapide capable de remonter le temps, de créer des forks et des branches
  • Côté serveur aussi, il faut un stockage rapide capable de traiter les mutations entrantes
  • Il faut également un mécanisme de synchronisation des mutators et une logique de récupération quand des conflits apparaissent pendant la synchronisation côté client ou serveur
  • En échange, la linéarisation de fonctions arbitraires devient une stratégie de synchronisation assez générale

  • Exemples gérés sans code de synchronisation séparé

    • Les opérations arithmétiques sont gérées naturellement
    • setHighScore enregistre la plus grande valeur entre high-score existant et le score proposé
    • La plupart des manipulations de listes fonctionnent aussi
    • append ajoute un élément à la fin d’une liste de courses
    • insertAt insère un élément à une position donnée, tandis que splice() ajuste la position
    • remove doit prendre en argument l’élément lui-même ou un identifiant stable, car l’index peut changer
    • Il est également possible d’imposer des invariants de plus haut niveau
    • addChild met à jour ensemble les childIDs du parent et le parentID de l’enfant afin qu’ils restent toujours cohérents
    • Ces exemples se fusionnent raisonnablement sans code supplémentaire spécialement pensé pour la synchronisation

Autorité du serveur et contrôle d’accès

  • Dans Reflect, le serveur fait autorité
  • Ce que le client pense être le résultat d’un changement n’est partagé ni avec le serveur ni avec les autres clients
  • Seuls le nom de la mutation et ses arguments sont envoyés au serveur, qui recalcule lui-même le résultat
  • Le serveur n’a même pas besoin d’exécuter exactement le même code que le client ; il peut aussi interroger des services externes ou utiliser des nombres aléatoires

  • Autorisations fines

    • Cette conception permet d’intégrer naturellement des contrôles d’accès fins
    • Exemple : dans un outil de design collaboratif, on peut autoriser un invité à commenter et surligner, tout en lui interdisant de modifier réellement le design
    • Avec un CRDT, il est difficile d’implémenter ce comportement car il n’existe pas d’endroit clair où rejeter un changement non autorisé
    • Avec Reflect, le mutator exécuté sur le serveur peut vérifier une valeur comme tx.user.canEdit et lever une erreur unauthorized si l’utilisateur n’a pas les droits
    • Il n’y a aucun problème à ce qu’un mutator exécute un code différent sur le serveur et sur le client, puisque le serveur prend la décision finale

Validation de schéma et indications d’usage

  • Dans l’approche de Reflect, la validation de schéma et les migrations s’intègrent aussi naturellement à la conception
  • Le choix d’une stratégie de synchronisation est au cœur des systèmes multijoueurs, et Reflect considère la Transactional Conflict Resolution, héritée de l’industrie du jeu, comme une approche simple, flexible et puissante
  • Si vous développez une application multijoueurs, vous pouvez l’essayer depuis la page de démarrage de Reflect
  • Pour parler avec l’équipe de développement, vous pouvez utiliser discord.reflect.net ou @hello_reflect

À lire aussi

1 commentaires

 
GN⁺ 2023-10-19
Avis sur Hacker News

  • La démo en haut de la page d’accueil (https://reflect.net/) est assez amusante.
    Quand on la regarde, à chaque fois qu’un puzzle est terminé, les gens semblent agiter leur curseur en mode « on l’a fait ! »

    • J’ai commencé à former le mot FUCK avec les pièces, et quand d’autres personnes l’ont remarqué et se sont jointes à moi, c’est devenu une expérience étonnamment chaleureuse.
    • Il y a un bug visuel qui permet de cacher une pièce e derrière la partie e déjà terminée.
      Pour les autres lettres, le contour reste visible, donc ça ne marche pas de la même façon.
    • Je ne pense pas que cette démo soit un très bon exemple pour montrer les fonctionnalités de la bibliothèque.
      Quand on attrape une pièce, elle semble être verrouillée pour cet utilisateur, donc il y a très peu de conflits à résoudre ; il ne reste guère que le cas où deux personnes la prennent en même temps et où elle revient au premier.
      J’aimerais voir une meilleure démo où une vraie résolution de conflits se produit.
    • C’est vraiment une expérience amusante.
      La vidéo de la scène décrite est ici : https://streamable.com/asu261

  • Vous vous souvenez peut-être que c’était déjà passé une ou deux fois sous le nom Replicache.
    Reflect y ajoute un serveur de synchronisation entièrement managé et très rapide.
    Le domaine local-first / temps réel est assez encombré en ce moment, mais Replicache/Reflect vaut le détour parce que son modèle de données et son modèle de programmation sont magnifiquement simples.
    Par rapport aux CRDT, l’avantage est de pouvoir gérer soi-même les conflits avec du simple code séquentiel ; ajouter une résolution de conflits propre à l’application à des CRDT peut devenir complexe quand les règles intégrées ne conviennent pas.

  • Il y a environ 15 ans, chez ma grand-mère, j’avais creusé ce sujet assez loin pour tromper l’ennui, et j’en avais même fait une implémentation JavaScript.
    Dire que « les opérations arithmétiques fonctionnent tout simplement » est évidemment assez facile à obtenir avec des opérations idempotentes, mais j’ai du mal à accepter l’idée que « les opérations sur les listes fonctionnent aussi tout simplement ».
    Par exemple, prenons un tableau comme [1, 2, 3, 4, 5] : A supprime la plage 2–4, B supprime la plage 3–5, et C insère quelque chose entre 3 et 4. Si les trois mises à jour arrivent simultanément au serveur, la solution est ambiguë.
    S’appuyer sur des timestamps ou sur le « dernier écrivain gagne » (Last Write Wins) casse le modèle transactionnel, et si l’on choisit un gagnant, il reste à savoir ce que les autres utilisateurs verront et comment le leur communiquer.
    Si la réponse est « renvoyer tout le tableau », alors là encore le modèle transactionnel est cassé.

    • La remarque est juste.
      En réalité, la formulation visée était plutôt « beaucoup d’opérations sur les listes fonctionnent tout simplement ».
      Dans Reflect, on ne peut pas utiliser des index de liste comme identifiants pour modifier/supprimer, car les index ne sont pas stables ; c’est pourquoi il est recommandé d’utiliser l’élément lui-même s’il est atomique, ou généralement un ID stable : https://i.imgur.com/IKzmf0q.png
      Il existe aussi le problème où l’insertion de C peut être supprimée, mais dans un contexte de collaboration temps réel, aucun protocole ne peut le résoudre complètement.
      Du point de vue de C, voir disparaître ce qu’il vient d’écrire peut être triste ; ce genre de chose vient du fait que des humains travaillant simultanément dans le même espace ont des intentions différentes, et des dispositifs sociaux comme l’annulation et l’indication des personnes actuellement actives aident.
    • Même sans parler de suppressions, si « simultanément » A ajoute « a » à la liste L, B ajoute « b » et C ajoute « c », le serveur applique les ajouts dans un ordre arbitraire puis envoie le résultat aux clients.
      Pendant ce temps, chaque client peut avoir appliqué localement son propre ajout : A voit [« a »], B voit [« b »], C voit [« c »]. Quand le serveur envoie l’état [« c », « b », « a »], j’imagine que les clients abandonnent les changements en attente et prennent l’état du serveur comme vérité du monde.
      Mais si chaque ajout a un effet du type « je gagne si mon changement est appliqué en premier », je me demande si, pendant les 300 ms d’attente de la mise à jour serveur, tout le monde voit « you win ».
    • La plupart de ces systèmes gèrent les suppressions avec des tombstones.
      On peut alors insérer en toute sécurité derrière ou entre des éléments supprimés.
    • Dans une application collaborative, le serveur peut résoudre les trois opérations dans n’importe quel ordre.
      Les trois utilisateurs verront le résultat, comprendront qu’ils ont modifié les mêmes données simultanément et que l’état est devenu bancal, puis le corrigeront.
      Pensez à l’édition de documents.
      S’ils ne peuvent pas voir que les autres sont en train de travailler, cela peut surprendre, mais ils peuvent au final corriger l’état souhaité.
      Si le résultat n’est pas vérifié, ou ne peut pas l’être, l’état ne sera pas correct ; mais dans des applications interactives comme l’édition collaborative ou les jeux, les choses ne se passent généralement pas ainsi.

  • Je fais partie des personnes qui ont participé à ce projet, et je peux répondre aux questions s’il y en a

    • Aaron est modeste, donc je vais le dire à sa place : il a créé Greasemonkey et a été impliqué pendant des années dans plusieurs innovations majeures côté navigateur
    • Par le passé, j’ai créé plusieurs systèmes de synchronisation multijoueur dans des bases de code privées, et j’ai suivi ce domaine
      J’ai aussi créé une bibliothèque « redux-pubsub » avec rebase et source de vérité serveur ; d’après ce que j’en comprends, c’est similaire à TCR
      Il y a beaucoup de choses que j’aime dans ce modèle, et l’article lié est aussi très clair
      Vous dites que « la validation de schéma et les migrations viennent naturellement, presque gratuitement, de la conception » ; je me demande quelle approche a réellement bien fonctionné pour les migrations
      Et, pour un cas d’usage TCR qui traite une quantité importante d’édition de texte partagée, on pense généralement par défaut à Yjs et Tiptap/ProseMirror ; je me demande si le mieux est de conserver un document CRDT et un document TCR en parallèle
    • Je me demande ce qu’il adviendra du développement de Replicache
      J’aimerais savoir si, comme la base de code côté client est en grande partie partagée, on peut s’attendre à ce qu’elle continue d’être mise à jour, ou s’il est plus probable que Reflect devienne l’objectif principal à sa place
    • Je me demande ce que vous pensez d’ElectricSQL
    • Je me demande quel est le nombre maximal d’utilisateurs pouvant se trouver simultanément dans une même room

  • La terminologie prête un peu à confusion
    Dans les jeux, il y a des « joueurs », donc on appelle le système de synchronisation « multijoueur » ; mais dans les logiciels généraux, il y a des « utilisateurs », donc multi-utilisateur me semblerait plus juste
    Sur la page, l’alternance entre « utilisateur » et « multijoueur » se lit de manière un peu étrange

    • C’est possible, mais « utilisateur » sonne comme un consommateur
      HN est un service multi-utilisateur, mais il serait bizarre de qualifier HN de multijoueur
      L’interaction simultanée en temps réel a quelque chose de plus fort que le simple multi-utilisateur, et multijoueur, au sens où plusieurs utilisateurs agissent et interagissent, me semble un usage acceptable
    • Cette logique est basée sur celle utilisée depuis des décennies dans les jeux multijoueurs
      À l’inverse, tous les logiciels web sont multi-utilisateurs, donc ce terme seul n’apporte aucune information
    • De nos jours, le terme s’est tout simplement imposé ainsi
      Multijoueur désigne du multi-utilisateur live où l’on visualise ce que font les autres utilisateurs à chaque instant

  • Cela fait environ deux ans que je regarde les CRDT de loin en loin, et je me suis toujours demandé comment se gérait l’autorisation
    Cet article semble suggérer qu’avec de simples bibliothèques CRDT comme Y.js, il est difficile de gérer correctement des applications où les changements doivent passer des contrôles d’autorisation
    Parce qu’il n’y a pas d’autorité centrale, c’est-à-dire de serveur ; et Reflect semble partir du principe que le serveur arbitre les interactions client. Est-ce bien la bonne compréhension ?

    • Dire que c’est « impossible » est un peu fort
      Avec des efforts, on peut gérer les autorisations avec des CRDT ; par exemple, en plaçant un serveur entre tout le monde et en lui faisant annuler les changements non autorisés qu’il observe
      Mais à mesure que l’application grossit, cela demande plus de maintenance, devient fragile, et on perd d’emblée une partie des avantages des CRDT
      Si le serveur est déjà au milieu, il est beaucoup plus simple d’utiliser dès le départ un protocole où le serveur peut rejeter les messages
    • Les CRDT peuvent aussi inclure un serveur ; simplement, le serveur n’a pas nécessairement besoin d’être au centre de tout
      Par exemple, le serveur peut se charger de l’authentification des connexions
      Si quelqu’un se connecte en P2P et revendique certains droits, on peut vérifier cette revendication auprès du serveur
      De plus, CRDT ne signifie pas forcément P2P : on peut faire transiter les messages par un serveur central tout en conservant un modèle CRDT où l’état courant est résolu à la fois côté serveur et côté client
    • On peut gérer les autorisations en signant chaque opération ou message et en vérifiant que cela correspond à la clé publique d’une liste de contrôle d’accès
      Cette approche permet aux CRDT de fonctionner aussi dans un contexte P2P
      Cela dit, si le serveur fait autorité, il suffit de rejeter les messages des clients non autorisés

  • Je me demande comment sont gérées les mises à niveau de mutators
    Si un client exécute du vieux code, ses opérations divergeront de celles du serveur ; la réponse évidente est de versionner indépendamment, comme increment_v1, increment_v2, mais je me demande s’il existe une meilleure méthode

    • Pour l’instant, il n’y a pas de meilleure réponse que de ne pas supprimer les anciens mutators tant que l’on ne sait pas qu’il n’y a plus de clients avec des changements en attente
      Comme nous n’avons pas encore activé la persistance, cette période est actuellement assez courte

  • Félicitations pour le lancement
    Je me demande si cela appartient à la même famille que https://partykit.io/

    • C’est dans le même domaine
      La différence clé, c’est le degré auquel chacun adopte une conception opinionated
      PartyKit est très peu prescriptif, et ressemble davantage à un serveur JavaScript léger, permettant de démarrer vite et de passer automatiquement à l’échelle
      La plupart des gens semblent exécuter yjs sur PartyKit, mais on peut aussi y faire tourner automerge ou Replicache
      Reflect se concentre entièrement sur la meilleure expérience multijoueur possible, avec l’objectif d’intégrer fortement de nombreux choix sur toute la stack afin que le multijoueur fonctionne tout simplement, et que l’on puisse se concentrer sur l’implémentation de l’application

  • À noter que cette stratégie est appelée lockstep déterministe dans le développement de jeux, et qu’elle est particulièrement utilisée dans les jeux comportant de nombreuses entités dont l’état doit être synchronisé.
    L’exemple typique, ce sont les jeux de stratégie en temps réel, qui utilisent presque tous cette approche.

    • Plus précisément, comme le client n’attend pas la réponse du serveur avant d’afficher les changements locaux, cela se rapproche davantage du rollback déterministe.
      Il existe une excellente présentation GDC qui explique en profondeur les implémentations de Mortal Kombat et Injustice 2 : https://youtu.be/7jb0FOcImdg
    • Ce n’est pas du lockstep déterministe.
      Le lockstep déterministe est un algorithme de jeu P2P où chaque participant attend les entrées de tous les autres joueurs avant de faire avancer la simulation du jeu.
      Il est « déterministe » parce qu’on partage les entrées, et non le résultat de la simulation, et que la simulation est déterministe pour des entrées identiques ; il est en « lockstep » parce que tous les clients avancent à un rythme coordonné.
      La série Age of Empires utilise cette méthode, ce qui explique que les unités ne se déplacent pas immédiatement quand on clique ; StarCraft l’utilise aussi, avec des astuces pour rendre la sensation de jeu plus fluide.
      Reflect s’apparente plutôt à une simulation à autorité serveur qu’à du P2P.
      Le client envoie ses entrées au serveur, mais prédit localement sans attendre le résultat ; le serveur remonte le temps et rejoue les entrées pour compenser la latence de chaque client.
      Ensuite, quand le client reçoit le résultat du serveur qui inclut ses propres entrées, il corrige sa simulation locale.
      Les mots-clés de cet algorithme sont : autorité serveur, prédiction, compensation de latence et réconciliation de prédiction.
      Je ne sais pas si Reflect l’implémente, mais dans les FPS, il est aussi courant d’utiliser une interpolation côté client, où, lorsqu’une mise à jour du monde est reçue, les entités sont interpolées pendant un certain temps vers leur nouvelle position et rotation.
      Comme il n’y a qu’une seule autorité — le serveur —, le déterminisme n’est pas absolument crucial, mais il est utile pour réduire les mauvaises prédictions côté client.
      Les mauvaises prédictions surviennent quand la simulation n’est pas déterministe, par exemple parce que les entrées d’autres clients modifient fortement l’état du monde ou que la génération de nombres aléatoires n’est pas synchronisée.
      Counter Strike offre aussi un exemple où l’aléa de dispersion des balles n’est pas synchronisé afin d’empêcher les cheats « nospread ».
      https://www.gabrielgambetta.com/client-side-prediction-live-...
      https://developer.valvesoftware.com/wiki/Latency_Compensatin...
      https://developer.valvesoftware.com/wiki/Source_Multiplayer_...

  • Reflect est excellent.
    Nous utilisons actuellement la version alpha en production, et nous sommes très satisfaits non seulement du système, mais aussi d’Aaron et de son équipe.
    Je peux répondre aux questions du point de vue d’un client.