There are several short-comings to the above approach though, specifically, you have to explicitly trade off performance vs. efficiency depending on the JSON you're dealing with.
JSON Patch is going to give you a consistent performance vs. efficiency curve which is desirable in a lot of circumstances.
This is about sending a diff over the network without having to either have the full json document on hand, or worrying about other concurrent changes that might wreck the diff-match-patch. It's also json-aware versus operating on pure text which might lead to invalid json documents.
1. Errr, to apply any delta, including these, you need the document on hand.
If your goal is to store deltas, this is no better than anything else.
2. This is in no way better at handling concurrent changes than anything other diff format. In fact, the extra operations it has do nothing to help you here (it is as good and bad as copy/add, or insert/delete diffs).
I'd love to know why you seem to think otherwise.
JSON awareness only helps when trying to apply partial patches. At that point, the only thing it can possibly buy you is syntactic correctness, which is worthless without semantic correctness (and in fact, sometimes worse)
> Errr, to apply any delta, including these, you need the document on hand. If your goal is to store deltas, this is no better than anything else.
Doesn't this allow the sender to send updates without knowledge of the existing values, though? With a string diff, the existing value would have to be known.
> This is in no way better at handling concurrent changes than anything other diff format. In fact, the extra operations it has do nothing to help you here (it is as good and bad as copy/add, or insert/delete diffs). I'd love to know why you seem to think otherwise.
If you're sending a regular diff, you would clobber changes to other parts of the object if they were updated between your initial retrieval and subsequent change. But yeah, it doesn't seem to help with applying concurrent changes to the same part of an object, though I don't know if the patch format should shoulder that responsibility.
You can know keys/paths but nothing else. Or you might have user-specific parts that won't be concurrently modified, but the base JSON doc might be modified by others. You'd have to have the latest version to do a text-based patch.
A text-based diff doesn't really gain much for what it loses in use cases.
A simple example: if the order of the keys is different, say because of a different json implementation, semantically the document is identical, but you can't apply the patch anymore.
The OP was talking about the current incumbent, and the solution proposed does not work for web applications, since the JSON.stringify in most browsers do not sort keys. Sure, you could implement your own javascript version, but it will be at least a couple of orders of magnitude slower.
So then it's a bad implementation of a textual tree diff algorithm .... which again, is a standard copy/add delta format (with a small amount of metadata).
Your proposed algorithm is a particularly poor solution in terms of correctness if nothing else. For text, DMP performs quite well- patches can typically be applied in arbitrary order with the same result. For complex data formats, you very quickly arrive at invalid (JSON).
But its Javascript Object Notation - Notation in this case implies text - if your storing it in something other than text it's not JSON.
From Wikipedia: JavaScript Object Notation, is an open standard format that uses human-readable text to transmit data objects consisting of attribute–value pairs.
Like you pointed out JSON is used to transmit data objects, but storage of data objects on the server or local file is entirely different story. I hope I don't have to explain further.
It is my understanding that the JSON encoding of objects is not specified canonically because the order of keys can be arbitrary. That is, JSON.stringify() is free to return different strings for the same JSON object.
Is my understanding correct? If it is, that would totally break your suggestion.
You are correct, but if you control the environment enough to be doing this at all, then you control the environment enough to get the serialization consistent: either by having ordered dictionaries in the language a la Python and PHP, or implementing your own, or by sorting the keys lexicographically a la bencode.
That is, `diff(sorted_json_stringify(json_parse(p)))` will be adequate if `diff(p)` is not.
The op missing is string diff. If a very long string value has changed, no matter how little the change is, you'll have to include the entire string in the patch.
If you have strings that long, maybe it would be wise to break it up semantically into some collection of resources (paragraphs, lines, etc.). It could be reassembled as needed for display but then stored and updated as its semantic parts.
Taken to an extreme (and isn't that what programming is all about), that could end up using a lot more memory and overhead, storing an array of many short strings, instead of storing one big flat string. And it would also require more work and pointless code complexity to deal with many short strings.
As opposed to the pointless complexity that comes from implementing support for string diffs?
Having implemented a json differ (which is similar, but with different representations of the paths due to having uniform access to nodes in the tree due to having id elements everywhere that matters), I would consider string diffs overengineering.
That is a really great point in favor of using string based diff. You've convinced me that's a better way to go than editing JSON structures. (Especially if you have big strings containing JavaScript code and other fluffy stuff.) Also of course it's better if the JSON you're patching is already represented as unparsed text, or if you have an un-parsed backing store you can apply the diffs to.
Let's say you want to update a typo in a lengthy document, I think it's worth the trouble. Good diff algorithm is hard, but there is open source solution.
We (Empirical) have implemented a similar couple years ago in our json-backed model. I see two big problems with this standard:
1. Why express paths as a string if you have the ability to encode it as an array in json? Otherwise you run up against the escaping problem for which they use ~0 and ~1 (of all things?!) which is only going to cause bugs.
2. Indexing into arrays is a problem in distributed computing because things can go out of sync super fast especially if these documents are concurrently shared across devices/users/caches. We solved this by making arrays into sets, whereby the sets are index by either a value (string, number) or in the case of containing more objects, having those objects specify a unique key (e.g. ["someArray", {"myUniqueKey": uniqueValue}, "propertyInsideTheObject"]. We maintain an ontology to know which keys are unique, but because we encode it in the patch itself the underlying platform doesn't need to know that hierarchy... it can simply look at each document's "myUniqueKey" to perform the update.
Thus our patches are always idempotent unlike the proposal.
If anyone is interested in any of this being open sourced (we have it production-quality in scala, java (android), objc, and javascript) let me know at aaron@empiric.al. It's a pretty powerful stack that we've considered open sourcing before... a bit like having your own version of Parse/Firebase but with a nicer/easier API.
Paths as array is a much better way than escape codes. That would save people a lot of time in explaining and understanding, especially if this is going to be standardized.
That's absolutely true about arrays but maintaining on ontology isn't a general-purpose solution for arbitrary JSON. Perhaps a simpler solution that applies patches to a known document in a specific order will still be useful in some cases?
I got stuck at indexing as well. I feel like there's a good solution involving using an array element within the path array to denote a selector query of sorts but I haven't hashed it out yet.
To me, it's more readable as a path since we all deal with those everyday in our address bar. The machine can make it an array if it wants, but I'd prefer to see it in one line.
I do wish they'd gone with backslash as an escape character. Don't know what possessed them to pull ~0 and ~1 out of their butts.
That kind of inflation is just a side effect of format encapsulation. You're representing a path format inside the JSON format, both of which need to escape their delimiters if they're to be taken literally. I still think a single consistent escape character is cleanest.
The same argument applies when I have any defined escape character or delimiter that I want to use as a literal.
I'll admit it's less human readable if you have a key `\/` but I can't think of many good reasons you'd want that as a key, which is what makes them good escape characters and delimiters.
We also faced this problem at work a while back, although, for XML.
My first iteration was similar in spirit to jsonpatch: a sequence of ops against the document. A XML patches grew things because mighty unwieldy and confusing. The maintainability of "diff operations" is incredibly low.
What I did in my second iteration was to have the patch document "look" like the document you are trying to create. Here's a document that will give you the general gist of how it worked (it's somewhat hard to describe in words): https://gist.github.com/jcdickinson/57e3a7e481a7e79f90b4
There are some operations (foreach, etc.) that I haven't included in the sample that are designed in an "operation" manner for scenarios where the structural approach won't work.
Either way it makes patches a lot more manageable and you may want to consider using it as inspiration. I included something rough in the gist to get the grey matter rolling.
I would love to know what the PostgreSQL developers thoughts are on this and whether this could be in the pipelines as an extension to their growing JSON support.
This is a great complement to the PATCH HTTP verb for RESTful APIs. It's much better to have a standard way to describe how a resource should be changed and not some ad hoc, implementation-specific syntax. Coincidentally, I just implemented support for this in one of my projects today (https://pypi.python.org/pypi/elita).
Seems like a good starting point, but it's a bit too simplistic for my taste.
"Add" seems like it's not idempotent as the existing value seems to change what it does.
Seems like a mistake to bundle array operations into "add" and "remove".
Array indexing is going to be useless for most applications because it makes assumptions about what's already there, and there is no way to specify fine-grained preconditions (or relativity such as "insert before the element 'b'").
No support for "increment", "decrement" or similar operations you'd want to make atomic.
No support for sets.
Unlike azinman2, I think paths as strings is fine. But why not support both? Let a path be either a string or an array.
As long as they don't try to call it RESTful I think it's a good idea.
On the other hand, if HTTP/2 can minimize the overhead of just making many consecutive HTTP calls, that feels a lot better to me than using what is essentially a constrained RPC interface.
I might misunderstand your comment but FWIW, buried in RFC 5789 the description of PATCH calls for a "description of changes" to be sent, so JSON Patch is trying to define a format for the set of changes to meet the requirement for using PATCH (and implementing REST) correctly. Still, JSON Patch is just too clunky compared to the elegant simplicity of JSON itself, IMHO.
I think it's arguable though that PATCH itself isn't quite RESTful as it doesn't describe the state of a resource at the identifier, but instead some subset of the state of that resource. Doing that kind of destroys the semantics of the resource identifier.
You'd probably still find me arguing for PATCH as it's obviously preferable not to resend an entire resource to reflect a small change in that resource.
Perhaps the more elegant solution is to forget PATCH and use more nested resource identifier semantics (never thought I'd say that) so that you can appropriately identify the entire subset of the resource being altered.
Hmm, I got the impression that REST purists insist on using PATCH. Rails 4 uses it for their REST implementation, for example. Also check out Will Durand's post [1]. I mused about the relative merits of PATCH vs POST in a blog post [2] - if you have any references you wouldn't mind leaving in the comments, I'd love to check them out.
PS. nesting resources is a pretty interesting issue in itself; there seem to be a few different schools of thought about that, ie. using the '/' in URLs like the '.' scoping operator on objects, versus a flat scheme where all the different collections live at the topmost level, versus a combination of both or even using one as an alias for the other.
I think it's arguable though that PATCH itself isn't quite RESTful as it doesn't describe the state of a resource at the identifier, but instead some subset of the state of that resource. Doing that kind of destroys the semantics of the resource identifier.
Can you expand on that point? I'm not clear on how would it affect the semantics of the resource identifier.
The resource identifier should uniquely identify the resource being described by the representation. PATCH literally means "Use the resource at this URI, but apply the enclosed state representation to some subset of that resource."
In that way, the state representation being sent only actually represents a subset of the resource being identified. I'd argue that this semantically makes the actual target of the new state a resource in itself and it should have its own identifier.
Still compressed its going to be bigger. The other thing is its going to be more efficient for the processor if we define where in the object we are going to be working rather than navigating through the object for every single change even if they are adjacent to each other.
This spec has come up a couple times; the first time I wondered whether a simpler approach might be acceptable:
* setting properties to be updated
* omitting properties to be unchanged
* explicitly setting 'undefined' properties to be deleted
I've used that approach and github seems to have done something similar. I like the idea of a patch spec for JSON - it's required by a strict implementation of REST with HTTP PATCH - but the proposals I've seen so far seem just beyond the ken of the forehead-slapping simplicity that everyone loves about the JSON format and the parse & stringify methods.
Oh, good - someone wrote an RFC for it - thanks for the link! It looks a lot like a post on partial updates in REST [1] where I recommended using null in the context of relational databases like mysql. Now I kinda feel undefined might be a better way to explicitly delete properties, especially if using a NoSQL database.
Thanks, you're right. "null" is what I do use - I forgot undefined won't work with JSON.parse. It would be nice to have a way to explicitly define a property as null, versus non-extant.
If you start with original.json, then client 1 applies add-middle-name.json, and then moments later client 2 applies change-name.json not knowing that the other patch had been applied, you'll end up with a possibly unintentional merging of the two. I'm assuming change-name here wanted to clobber the whole name object, and did not intend to merge and keep the middle name.
There's a couple ways around this. One is to code defensively and always pass the middle:null when clobbering the name, since you know other clients could set a middle name. The other is to do some sort of versioning check to ensure no one else has changed the document since you last fetched it. That could be implemented outside the json patch, using if-not-modified headers or something, though it is tempting to do it with the "test" actions provided in the main spec discussed here.
Most serializers will omit undefined (I don't believe it's allowed as a JSON value. That said, I think null should be sufficient. Though, MongoDB already defines update syntax pretty well, and would just assume follow that syntax.
This is what people often do apart from the last point (no undefined in JSON, and by definition anything you could choose here would conflict with valid values). This works well for a lot of use cases but can't express everything you might want to do with something like JSON-Patch.
This is what people often do apart from the last point (no undefined in JSON, and by definition anything you could choose here would conflict with valid values). This works well for a lot of use cases but can't express everything you might want to do with something like JSON-Patch.
YES! I couldn't agree more. Thank you for making this comment, specifically this part, "...the proposals I've seen so far seem just beyond the ken of the forehead-slapping simplicity...". To me the existing proposals are a complete aberration when viewed along with the rest of the JSON spec and standard REST implementations. I'm really happy to see that GitHub took the simpler more intuitive implementation as well.
I think that this idea is missing one key point of patching: the patch should be smaller than the size of the new document, or at the least the sum of both the new and old documents (in case you want the patch for record keeping).
In the example given the original text is 34 bytes long, the patch is 151 bytes, and the result is 42 bytes. Storing both the new text and the old text is 76 bytes which is about half of the size of the patch. If this were a corner case that rarely happened, then I wouldnt bring it up. However, it is actually a common case (and is even given as the example!) and has such terrible characteristics, there is no reason to use it.
I use this patch system in production and I agree. For small JSON documents, this system actually can result in larger patch files than the original document.
Instead of using this everywhere we output JSON however, we only use this patch system on large documents. It cuts our average transfer size from ~60KB (full JSON data) to ~2KB (patch data) per API request after the initial load since only a handful of values change over the polling interval.
Google Wave did something like this. What protocol did they use to update JSON, and is it modular and can stand on its own, without all the other Wave stuff? Does anyone know what its features and drawbacks were?
I'll help you, but you should know that what they do is nothing like that. They used Operational Transformation. They have convergent properties which guarantee that you won't ever have merge conflicts. They also have, depending on the implementation, certain causality guarantees that ensure that what you edited stays the way you intended.
The basic idea is that you receive operations that modify your local operations. The challenge is in writing the function that takes each two operations and mutates them. Therefore, the protocol is of no practical interest, it simply serves that function's purpose.
This is cool! My only substantive comment is criticism, but this is cool.
I think it's a problem that remove and replace don't indicate what they're removing or replacing, the same way .patch files indicate what lines they're removing. This makes patch files reversible, which JSON patches appear not to be. It also provides some redundancy/error correction, which is handy.
I've just used this to get a solid undo/redo in our WebGL editor. It works amazingly well, and is very performant. However, our backend is not in Javascript, so if I'd want to use it for data transport I'd have to make a compatible python implementation. So I get the point of a standard, so long as it's up to par.
Relatedly, Mattt Thompson of Gowalla/Heroku/Panic/AFNetworking fame proposed Rocket, a technique that pairs JSON Patch and Server-Sent Events to aid in the construction of realtime apps via REST services. The proposal has seemingly been abandon, which is unfortunate as the formalization of handling was interesting, even if one implemented it on top of a different transport layer like Web Sockets or a push notification service.
111 comments
[ 2.5 ms ] story [ 184 ms ] thread1. JSON.stringify()
2. Diff-match-patch: https://code.google.com/p/google-diff-match-patch/
3. JSON.parse()
There are several short-comings to the above approach though, specifically, you have to explicitly trade off performance vs. efficiency depending on the JSON you're dealing with.
JSON Patch is going to give you a consistent performance vs. efficiency curve which is desirable in a lot of circumstances.
2. This is in no way better at handling concurrent changes than anything other diff format. In fact, the extra operations it has do nothing to help you here (it is as good and bad as copy/add, or insert/delete diffs). I'd love to know why you seem to think otherwise.
JSON awareness only helps when trying to apply partial patches. At that point, the only thing it can possibly buy you is syntactic correctness, which is worthless without semantic correctness (and in fact, sometimes worse)
Doesn't this allow the sender to send updates without knowledge of the existing values, though? With a string diff, the existing value would have to be known.
> This is in no way better at handling concurrent changes than anything other diff format. In fact, the extra operations it has do nothing to help you here (it is as good and bad as copy/add, or insert/delete diffs). I'd love to know why you seem to think otherwise.
If you're sending a regular diff, you would clobber changes to other parts of the object if they were updated between your initial retrieval and subsequent change. But yeah, it doesn't seem to help with applying concurrent changes to the same part of an object, though I don't know if the patch format should shoulder that responsibility.
This system requires knowledge of existing values/nodes to create the diff/patch document.
However for JSON data, it does have the advantage of not clobbering data unlike a string diff as you mentioned.
A text-based diff doesn't really gain much for what it loses in use cases.
This seems like a trivial application of any copy/add delta format, which are easily expressed in text diff format.
Or are you simply talking about javascript style object literals?
From Wikipedia: JavaScript Object Notation, is an open standard format that uses human-readable text to transmit data objects consisting of attribute–value pairs.
Is my understanding correct? If it is, that would totally break your suggestion.
That is, `diff(sorted_json_stringify(json_parse(p)))` will be adequate if `diff(p)` is not.
https://tools.ietf.org/html/draft-ietf-scim-api-12#section-3...
(SCIM is a set of specs describing a schema and a REST API for data exchange between identity providers, more or less.)
Having implemented a json differ (which is similar, but with different representations of the paths due to having uniform access to nodes in the tree due to having id elements everywhere that matters), I would consider string diffs overengineering.
http://code.google.com/p/google-diff-match-patch
1. Why express paths as a string if you have the ability to encode it as an array in json? Otherwise you run up against the escaping problem for which they use ~0 and ~1 (of all things?!) which is only going to cause bugs.
2. Indexing into arrays is a problem in distributed computing because things can go out of sync super fast especially if these documents are concurrently shared across devices/users/caches. We solved this by making arrays into sets, whereby the sets are index by either a value (string, number) or in the case of containing more objects, having those objects specify a unique key (e.g. ["someArray", {"myUniqueKey": uniqueValue}, "propertyInsideTheObject"]. We maintain an ontology to know which keys are unique, but because we encode it in the patch itself the underlying platform doesn't need to know that hierarchy... it can simply look at each document's "myUniqueKey" to perform the update.
Thus our patches are always idempotent unlike the proposal.
If anyone is interested in any of this being open sourced (we have it production-quality in scala, java (android), objc, and javascript) let me know at aaron@empiric.al. It's a pretty powerful stack that we've considered open sourcing before... a bit like having your own version of Parse/Firebase but with a nicer/easier API.
Paths as array is a much better way than escape codes. That would save people a lot of time in explaining and understanding, especially if this is going to be standardized.
http://en.wikipedia.org/wiki/Trie
Also, Clojure has a nice functions called get-in and friends:
To me, it's more readable as a path since we all deal with those everyday in our address bar. The machine can make it an array if it wants, but I'd prefer to see it in one line.
I do wish they'd gone with backslash as an escape character. Don't know what possessed them to pull ~0 and ~1 out of their butts.
The same argument applies when I have any defined escape character or delimiter that I want to use as a literal.
I'll admit it's less human readable if you have a key `\/` but I can't think of many good reasons you'd want that as a key, which is what makes them good escape characters and delimiters.
Probably because it's mimicking XPath, which was the analogous string but for XML. Think regex as well, which is a string.
My first iteration was similar in spirit to jsonpatch: a sequence of ops against the document. A XML patches grew things because mighty unwieldy and confusing. The maintainability of "diff operations" is incredibly low.
What I did in my second iteration was to have the patch document "look" like the document you are trying to create. Here's a document that will give you the general gist of how it worked (it's somewhat hard to describe in words): https://gist.github.com/jcdickinson/57e3a7e481a7e79f90b4
There are some operations (foreach, etc.) that I haven't included in the sample that are designed in an "operation" manner for scenarios where the structural approach won't work.
Either way it makes patches a lot more manageable and you may want to consider using it as inspiration. I included something rough in the gist to get the grey matter rolling.
http://www.postgresql.org/message-id/CACu89FSYikxdUj+J01BoAv...
Here's a link to the original RFC from 2013: https://tools.ietf.org/html/rfc6902
A cool thing is the "test" operation. JSON patches are atomic, so you can put in something like:
...and if { foo: { bar: 75 }}, none of the patch will be applied."Add" seems like it's not idempotent as the existing value seems to change what it does.
Seems like a mistake to bundle array operations into "add" and "remove".
Array indexing is going to be useless for most applications because it makes assumptions about what's already there, and there is no way to specify fine-grained preconditions (or relativity such as "insert before the element 'b'").
No support for "increment", "decrement" or similar operations you'd want to make atomic.
No support for sets.
Unlike azinman2, I think paths as strings is fine. But why not support both? Let a path be either a string or an array.
On the other hand, if HTTP/2 can minimize the overhead of just making many consecutive HTTP calls, that feels a lot better to me than using what is essentially a constrained RPC interface.
I think it's arguable though that PATCH itself isn't quite RESTful as it doesn't describe the state of a resource at the identifier, but instead some subset of the state of that resource. Doing that kind of destroys the semantics of the resource identifier.
You'd probably still find me arguing for PATCH as it's obviously preferable not to resend an entire resource to reflect a small change in that resource.
Perhaps the more elegant solution is to forget PATCH and use more nested resource identifier semantics (never thought I'd say that) so that you can appropriately identify the entire subset of the resource being altered.
PS. nesting resources is a pretty interesting issue in itself; there seem to be a few different schools of thought about that, ie. using the '/' in URLs like the '.' scoping operator on objects, versus a flat scheme where all the different collections live at the topmost level, versus a combination of both or even using one as an alias for the other.
1. http://williamdurand.fr/2014/02/14/please-do-not-patch-like-...
2. http://51elliot.blogspot.ca/2014/05/rest-api-best-practices-...
Can you expand on that point? I'm not clear on how would it affect the semantics of the resource identifier.
In that way, the state representation being sent only actually represents a subset of the resource being identified. I'd argue that this semantically makes the actual target of the new state a resource in itself and it should have its own identifier.
I prefer it, and think it's much easier to understand.
1.http://51elliot.blogspot.ca/2014/05/rest-api-best-practices-...
If you start with original.json, then client 1 applies add-middle-name.json, and then moments later client 2 applies change-name.json not knowing that the other patch had been applied, you'll end up with a possibly unintentional merging of the two. I'm assuming change-name here wanted to clobber the whole name object, and did not intend to merge and keep the middle name.
There's a couple ways around this. One is to code defensively and always pass the middle:null when clobbering the name, since you know other clients could set a middle name. The other is to do some sort of versioning check to ensure no one else has changed the document since you last fetched it. That could be implemented outside the json patch, using if-not-modified headers or something, though it is tempting to do it with the "test" actions provided in the main spec discussed here.
http://docs.mongodb.org/manual/tutorial/modify-documents/
It's not perfect, but it is pretty widely used, and well thought out enough for this purpose.
jQuery basically already has support for this exact thing, and it's only a few lines of pure JS.
$.extend({a:'b', b:2, c: [1,2]}, { a: null, b: 0})
that wouldn't foretell an optimistic future for this.
In the example given the original text is 34 bytes long, the patch is 151 bytes, and the result is 42 bytes. Storing both the new text and the old text is 76 bytes which is about half of the size of the patch. If this were a corner case that rarely happened, then I wouldnt bring it up. However, it is actually a common case (and is even given as the example!) and has such terrible characteristics, there is no reason to use it.
Instead of using this everywhere we output JSON however, we only use this patch system on large documents. It cuts our average transfer size from ~60KB (full JSON data) to ~2KB (patch data) per API request after the initial load since only a handful of values change over the polling interval.
The basic idea is that you receive operations that modify your local operations. The challenge is in writing the function that takes each two operations and mutates them. Therefore, the protocol is of no practical interest, it simply serves that function's purpose.
Here's a set of libraries that implement this for strings: https://github.com/Operational-Transformation
Implementing this for JSON is certainly possible, and has been done. See this for instance: https://github.com/share/ShareJS
I think it's a problem that remove and replace don't indicate what they're removing or replacing, the same way .patch files indicate what lines they're removing. This makes patch files reversible, which JSON patches appear not to be. It also provides some redundancy/error correction, which is handy.
I'm also not entirely sure about adjustments to arrays with this syntax.
Then I kind of stopped because I didn't see the point
I can understand not using a raw text patch, however.
http://rocket.github.io/
There's been some discussion recently on the wave-dev list: http://mail-archives.apache.org/mod_mbox/incubator-wave-dev/...