Encodage Delta pour les objets JSON

Question

Existe-t-il une bibliothèque ou un outil standard pour calculer et appliquer des différences aux documents JSON ? En gros, j'ai un tas de documents volumineux que je veux garder synchronisés sur un réseau, et je préférerais éviter d'avoir à renvoyer leur état complet chaque fois que je veux les synchroniser (puisque beaucoup de ces variables ne vont pas changer). En d'autres termes, je ne veux transmettre que les champs qui ont changé, et non pas retransmettre l'objet entier. Je pense qu'il serait pratique d'avoir quelque chose comme l'ensemble de méthodes suivant :

//Start with two distinct objects on the server
// prev represents a copy of the state of the object on the client
// next represents a copy of the state of the object on the server
//
//1. Compute a patch
patch = computePatch(prev, next);

//2. Send patch over the network

//3. Apply the patch on the client
applyPatch(prev, patch);

//Final invariant:
//   prev represents an equivalent object to JSON.parse(JSON.stringify(next))

Je pourrais certainement en implémenter un moi-même, mais il y a pas mal de cas limites à prendre en compte. Voici quelques-unes des méthodes simples (bien qu'un peu insatisfaisantes) auxquelles je peux penser :

1. Mettre en place mon propre correcteur JSON. Asymptotiquement, c'est probablement la meilleure façon de procéder, puisqu'il serait possible de supporter toutes les caractéristiques pertinentes des documents JSON, tout en supportant quelques méthodes spécialisées pour faire des choses comme différencier les ints, les doubles et les chaînes (en utilisant l'encodage relatif/la distance d'édition). Cependant, JSON a beaucoup de cas spéciaux et je suis un peu méfiant à l'idée d'essayer de faire cela sans beaucoup de tests, et donc je préférerais de loin trouver quelque chose qui résout déjà ce problème pour moi afin que je puisse lui faire confiance, et ne pas avoir à m'inquiéter de l'apparition de Heisenbugs réseau à cause d'erreurs dans mon JSON Parcheando.

2. Il suffit de calculer la distance d'édition directement entre les chaînes JSON en utilisant la programmation dynamique. Malheureusement, cela ne fonctionne pas si le client et le serveur ont des implémentations JSON différentes (c'est-à-dire que l'ordre de leurs champs pourrait être sérialisé différemment), et c'est également assez coûteux, étant une opération en temps quadratique.

3. Utilisez des tampons de protocole. Les tampons de protocole ont une méthode diff intégrée qui fait exactement ce que je veux, et ils constituent un format binaire sérialisable convivial pour le réseau. Malheureusement, parce qu'ils sont aussi strictement typés, ils n'ont pas les nombreux avantages de l'utilisation de JSON, comme la possibilité d'ajouter et de supprimer dynamiquement des champs. C'est l'approche vers laquelle je me tourne actuellement, mais elle pourrait rendre la maintenance future vraiment horrible, car je devrais continuellement mettre à jour chacun de mes objets.

4. Faire quelque chose de vraiment désagréable, comme créer un protocole personnalisé pour chaque type d'objet, et espérer que j'ai raison aux deux endroits (ouais, c'est ça !).

Bien sûr, ce que j'espère vraiment, c'est que quelqu'un ici, sur stackoverflow, vienne me sauver la mise en me donnant la référence d'un différentiateur/patcheur d'objets en javascript efficace et bien testé dans des environnements de production et sur plusieurs navigateurs.

* Mise à jour *

J'ai commencé à écrire mon propre patcheur, une première version est disponible sur github ici :

https://github.com/mikolalysenko/patcher.js

Comme il ne semble pas y avoir grand-chose, je vais plutôt accepter comme réponse alternative une liste de cas de test intéressants pour un correcteur JSON.

Answer 1

J'ai maintenu une bibliothèque de diff & patchs json sur github (oui, plug honteux) :

https://github.com/benjamine/JsonDiffPatch

il gère automatiquement les longues chaînes de caractères en utilisant la librairie diff_match_patch de Neil Fraser. il fonctionne aussi bien sur les navigateurs que sur le serveur (les tests unitaires fonctionnent sur les deux env). (la liste complète des fonctionnalités est sur la page du projet)

La seule chose dont vous auriez probablement besoin, et qui n'est pas implémentée, est l'option d'injecter des fonctions diff/patch personnalisées pour des objets spécifiques, mais cela ne semble pas difficile à ajouter, vous êtes le bienvenu pour le fork, et même mieux, pour envoyer une demande de pull.

Regards,

Answer 2

La norme JSON-patch a été mise à jour.

http://tools.ietf.org/html/draft-ietf-appsawg-json-patch-10

Vous trouverez une implémentation pour appliquer des correctifs et générer des correctifs à l'adresse suivante https://github.com/Starcounter-Jack/Fast-JSON-Patch

Answer 3

Je suis tombé sur cette question en cherchant des implémentations de json-patch. Si vous développez la vôtre, vous pourriez vouloir la baser sur ce projet.

http://tools.ietf.org/html/draft-pbryan-json-patch-00

Answer 4

Avant de commencer à écrire vos propres utilitaires de diff & patch JSON à partir de zéro, je vous suggère de tirer parti des utilitaires de diff & patch existants pour le texte brut. Tout ce que vous avez à faire est d'écrire une logique qui prend une chaîne JSON arbitraire et la rend sous forme JSON "canonique" - de sorte que deux chaînes JSON qui représentent des données équivalentes ont des formes "canoniques" qui sont identiques en tant que chaînes de texte - et ensuite vous pouvez utiliser le bon vieux "patch" pour calculer tous vos deltas pour vous.

Il semble que l'idée de JSON canonique n'est pas nouveau, mais le code requis pour générer une représentation canonique pour une chaîne JSON arbitraire n'est pas trivial, et il semble qu'il y ait place à l'amélioration dans tout ce que Google m'affiche pour "JSON canonique" à l'heure actuelle (y compris les réponses aux questions suivantes cette question bien qu'utilisant Bencode comme format de normalisation semble prometteur).

Ce qui est une excellente nouvelle, car cela signifie que vous pouvez écrire quelque chose de nouveau et d'utile ! Tenez-nous au courant lorsque vous aurez trouvé une solution viable (j'aimerais aussi pouvoir générer des deltas JSON).

EDIT : Après avoir réfléchi un peu plus, je me rends compte que l'idée de "canonisation" n'est pas vraiment utile du tout, puisque le même delta/patch ne peut pas s'appliquent généralement à deux morceaux JSON textuellement différents, même s'ils ont la même "forme canonique". Ce qui soulève la question suivante : si vous envoyez simplement des "deltas" pour un document JSON à travers un fil, alors pourquoi ne pas simplement les envoyer comme des différences littérales en texte clair (ou peut-être MIME documents de type text/x-diff) ? Pour se prémunir contre la corruption due à l'abandon de correctifs, vous pourriez ajouter un champ de numéro de séquence/révision quelque part (à la fois dans le fichier de données et dans les diffs), ou vous pourriez être ambitieux et utiliser le protocole Delta-V (développé pour WebDAV). Peut-être le faites-vous déjà ? J'essaierai de jeter un coup d'œil à votre code dans le courant de la semaine.

Answer 5

Checkout météore . Il dispose de quelques fonctionnalités intéressantes dans ce domaine, à savoir le contrôle du contexte et les fonctions d'invalidation/de mise à jour automatiques :)