I see that Remutable uses 'patches'. How does it compare with ShareJS? Does it allow collaborative editing (ie multiple people changing the same data structure concurrently, is patch application commutative)?
The idea behind ShareJS (or OT for that matter) is awesome. You never have to think about what to do if two people edit the same document concurrently. It just works. You get undo for free. And you can write the code that it saves automatically in the background. Never again do users have to press a 'save' button.
A while ago I wrote a library which builds on top of the same ideas as ShareJS (ie. OT) but with slightly different focus. You define object types and their properties. This allows the library to automatically parse JSON into JavaScript class instances. It also tracks changes to these objects in a very similar way as ShareJS: each change has a 'path' (where something was changed) and then the actual chang record (currently set and splice).
I use Avers in an SPA which is an editor of fairly complex data structures (90 different object types, nested ~5 levels deep). For rendering I use React. The integration is really simple: Attach a change listener to the root and re-render when anything changes.
I didn't now about ShareJS, but I'll definitely check it out. At its core, the patch abstraction is commutative (and more importantly, reversible), so I should be able to implement the 'rebase'-like operation. My feeling is that it would be more efficient to perform this at a higher level though, by replaying Actions in the right order in every client to get eventual consistency.
Remutable.Patch objects represent a collection of map edits, ie. a set of { key, value } pairs indicating that 'key' should be replaced by 'value' (and value can be void 0 to indicate deletion). They also embed a version and a hash for faster matching, but they can already be reverted/combined (for undo/redo stack or batching). I will read more about OTs!
OTs are the same idea along with a sort of rebase step for replaying changes that come in to get the head to the same point (regardless of the order in which the operations were received).
It seems like a great model, but as I mentioned above, there's surprisingly little code around for you to draw on. I seem to recall reading a conversation from the ShareJS guys (though maybe it was someone else) about how hairy the edge cases can get when you're trying to do it for general data-structures (which was disappointing, because conceptually it seems simple).
Interesting. I'm surprised at how little work seems to have been done around OT (operational transformation, for those who haven't heard of it before).
I have an application where I hold a lot of synced data in the client and the server but I've struggled to find good libraries to help manage that. Generally the work seemed to be around text, rather than arbitrary objects. Sharejs was the best I could find, but my BE system is python (and the object support in ShareJS was a bit sketchy when I looked at it).
Unrelated but looking at your project I saw you were using Sets and Maps. I didn't even know JS had those yet (and they're something I really miss coming from python). Will be switching immediately.
I'm going to have a deeper dig through your code today too. These ideas are definitely along the lines of what I've had formulating in my mind recently so I'd like to see how you've gone about implementing it.
Since it seems like you know a bit about this - do you have any experience with dealing with immutable structures in larger scale applications?
I used a react for a sub project to my core app and one of the issues I ran into straight away was that you can't really keep any state within components because of the way they're destroyed and created (something as simple as a file tree with an open/closed flag on folders falls down). So you need to have all of your state in stores.
What's the best way of managing that? I've been envisaging a world in which my application is one single large immutable data-structure containing everything about the current state of the application. The actions and then carried out (maybe via a backend over a websocket as you've described) to make changes to the tree. React then looks after the rendering.
> What's the best way of managing that? I've been envisaging a world in which my application is one single large immutable data-structure containing everything about the current state of the application. The actions and then carried out (maybe via a backend over a websocket as you've described) to make changes to the tree. React then looks after the rendering.
I've looked at Om before. It looks great and I guess probably implements some of the ideas I'm talking about but it's just too far away from what I'm doing. I have some really complex optimised code already and I'm pretty adverse to trying to bend it into a whole new language. Will take another look though to see if there are ideas I can borrow.
Avers supports only two operations, set and splice. It is very simple to implement in any language. My backend is written in Haskell. The code dealing with applying the patches is about 200 lines.
With these two operations you can edit arbitrary data structures. The user experience may not be the best, for example if two people edit the same text, because if you only have set then latest change wins. But maybe your data structures are not text heavy. Or they have many small text fields where the 'latest change wins' semantic is actually desireable.
At my previous company we also used and OT based patch system. And we didn't have text-editing support, we only had an equivalent to set in Avers. And it worked alright. Which operations you need depends on the application, ShareJS is good for one particular type, but too complex (or maybe even lacking) for others.
I'd be happy with set and splice. Text isn't really a big deal for my use case. Will have more of a read through your code later today too. Thanks for posting.
Great support list! Thanks for that. My customers all use the latest Chrome, so I'm ok with fairly bleeding edge features.
From the looks of it, CRDT is performing a "merge" on incoming states. This is (imho) in general not a good way of converging, because for some operations, the process for merging may not even be properly defined. Also, in order to perform security checks, it may be required to know the actual operations being performed. So I would not say that the technique is a "successor" of OT.
It seems to be a bit like using "git" to 3-way merge updates. In most cases (>99%), the merges are fine. But in some cases, a non-conflicting merge can have disastrous results.
OT and CRDT are conflict-free (from the applications point of view). If there is a conflict, it is automatically resolved by the underlying OT / CRDT algorithm and the application always gets a clean data structure to work with.
You can build your data structures so that if there is a conflict (in your domain model) it'll be handled by your application. But that happens logically at a level above OT / CRDT.
Indeed, Share.js is awesome. I've worked extensively with it, and recently hooked up Share.js to immutable React using a modified React-Cursor. It takes local mutations and converts them into JSON-OT. Remote OTs are merged back in, the server is always ground truth.
You get local reactive UI with immutable state. On the server-side, you can validate the ops as they come in using e.g. the entire infrastructure of passport in node. OAuth2-validated Share.js with strict per-property write access, no problem.
I also extended the couchDB driver to merge in server-side changes, thus allowing daemons to make live changes to the DB without having to care about any of the OT stuff. If share.js changes were made in the meantime, it will save a merged snapshot.
Basically, Share.js can be your insurance policy against pesky humans messing up your data structures, in a world of atomic data-driven robots and asynchronous feeds.
Hmm, I don't really get it yet, but "single source of truth" sounds to me like it needs extra round-trips to this "source of truth" in order to update the display (even if the updates come from the client itself). Is that correct?
You're right, although its fairly easy to implement optimistic updates on top of this. Since patch objects are reversible, you can use a simple logical clock and an undo/redo stack to perform optimistic updates locally, and undo them/redo them when the remote SSoT sends updates.
Absolutely. I plan to include it in the framework ultimately, although it requires implementing an optimistic client-side dispatcher in JS which mocks the optimistic behaviour of the actual, eventually true server-side dispatcher (which may not always be implemented in full JS, eg. if it needs to sync with a db).
Conflicts are handled by the server-side dispatcher logic. Many applications can handle conflicts easily (eg. chat rooms which only append new messages), others can be more complex (eg. document editing). As mentionned in another comment, Remutable.Patch leaves room for rebase-like algorithms. Its definitely a very promising further work! :)
Alas, I've been working on something like this for the last few weeks on and off, especially the "patching" of immutable data, my solution was to use jiff[1], which generates JSON Patch operations[2], which is then applied to the Immutable object using immpatch[3] (a lib I wrote).
A cursory look at Remutable seems it to be the better and faster option :)
However I realized actual diffing was really slow, especially for large collections, as it involves scanning the entire structure for changes, when in fact all changes could simply be flagged upon mutation. Conceptually, it performs diffing (ie. it gives you a diff object), its just much, much faster!
Its shouldJS. An assertion lib with a fun chainable DSL. Basically whatever.should.predicate desugars to assert(predicate(whatever)). See https://github.com/shouldjs/should.js :)
Synchronising state over the wire?
Surely this is a solved problem in games development already - serialise your state into a consistent binary form, send over the binary diff of the previous state (AKA delta compression), deserialise on client side.
Remutable looks really impressive. I'm a little leery of the rest of it, though, as it means my backend is no longer a simple REST API. I'm also rather nonplussed that the full-stack Flux doesn't include optimistic display with loading icon, error state, and rollback handling out of the box. It doesn't even seem like an easy thing to do manually with this setup, though I haven't played with it enough to know.
Few minor questions: it looks like a base Remutable must be an Immutable.Map(). Can child items be any of the Immutable datatypes? Do we get updateIn() and similar?
Thanks for your feedback. Several other comments point in the same direction: automatic (or assisted) handling of optimistic updates. I think this is actually relatively easy, since there are clear hooks in the Nexus Flux API to implement dispatch-time and update-time behaviour, but I will definitely provide an example, or even better, an implementation of this that just works out of the box.
This is a really cool implementation! I'm wondering if it wouldn't be possible to handle optimistic updates by submitting a request to the server and then submitting an optimistic response from the client to itself. Then, when the server comes back, you hook into the already present optimistic response and just confirm or deny it based on the response from the server. That way you keep as little state on the client as possible.
The best example of single source of truth may be chat, but I believe chat is the best example of a replicated log. This throw me off a bit while reading the article :| Left it, came back to the comments later to see people talking about OT and realized I missed something. Just an obesevation.
> We will rather record the mutations (or more accurately, the transitions between immutable states), and just replay them on the client.
Few questions -
How can we replay all the mutations?
How about instead of replaying, if we just show the last mutation? Will it not be the same thing?
I think this flux architecture will work best only in chatting applications. This approach is also making the app itself very chatter so performance concerns in case you do not have strong machines.
I think on form pages this flux approach may not be required.
Take a look at swarm.js for a fantastic way to keep stores in sync - even works in offline. Matrix.io could also be an interesting option for this, but focuses more on communication than shared data.
42 comments
[ 4.6 ms ] story [ 101 ms ] threadThe idea behind ShareJS (or OT for that matter) is awesome. You never have to think about what to do if two people edit the same document concurrently. It just works. You get undo for free. And you can write the code that it saves automatically in the background. Never again do users have to press a 'save' button.
A while ago I wrote a library which builds on top of the same ideas as ShareJS (ie. OT) but with slightly different focus. You define object types and their properties. This allows the library to automatically parse JSON into JavaScript class instances. It also tracks changes to these objects in a very similar way as ShareJS: each change has a 'path' (where something was changed) and then the actual chang record (currently set and splice).
I use Avers in an SPA which is an editor of fairly complex data structures (90 different object types, nested ~5 levels deep). For rendering I use React. The integration is really simple: Attach a change listener to the root and re-render when anything changes.
https://github.com/wereHamster/avers https://caurea.org/2015/02/08/the-future-of-avers.html
Remutable.Patch objects represent a collection of map edits, ie. a set of { key, value } pairs indicating that 'key' should be replaced by 'value' (and value can be void 0 to indicate deletion). They also embed a version and a hash for faster matching, but they can already be reverted/combined (for undo/redo stack or batching). I will read more about OTs!
It seems like a great model, but as I mentioned above, there's surprisingly little code around for you to draw on. I seem to recall reading a conversation from the ShareJS guys (though maybe it was someone else) about how hairy the edge cases can get when you're trying to do it for general data-structures (which was disappointing, because conceptually it seems simple).
https://github.com/Operational-Transformation/ot.js/
They have a nice visualization of OT here:
http://operational-transformation.github.io/visualization.ht...
I have an application where I hold a lot of synced data in the client and the server but I've struggled to find good libraries to help manage that. Generally the work seemed to be around text, rather than arbitrary objects. Sharejs was the best I could find, but my BE system is python (and the object support in ShareJS was a bit sketchy when I looked at it).
Unrelated but looking at your project I saw you were using Sets and Maps. I didn't even know JS had those yet (and they're something I really miss coming from python). Will be switching immediately.
Immutable provides (immutable) implementations of Map, OrderedMap, Set, etc. See http://facebook.github.io/immutable-js/ :)
Since it seems like you know a bit about this - do you have any experience with dealing with immutable structures in larger scale applications?
I used a react for a sub project to my core app and one of the issues I ran into straight away was that you can't really keep any state within components because of the way they're destroyed and created (something as simple as a file tree with an open/closed flag on folders falls down). So you need to have all of your state in stores.
What's the best way of managing that? I've been envisaging a world in which my application is one single large immutable data-structure containing everything about the current state of the application. The actions and then carried out (maybe via a backend over a websocket as you've described) to make changes to the tree. React then looks after the rendering.
Look up "Om/React", might just blow your mind.
With these two operations you can edit arbitrary data structures. The user experience may not be the best, for example if two people edit the same text, because if you only have set then latest change wins. But maybe your data structures are not text heavy. Or they have many small text fields where the 'latest change wins' semantic is actually desireable.
At my previous company we also used and OT based patch system. And we didn't have text-editing support, we only had an equivalent to set in Avers. And it worked alright. Which operations you need depends on the application, ShareJS is good for one particular type, but too complex (or maybe even lacking) for others.
As for maps and sets, see http://kangax.github.io/compat-table/es6/ how good the support is. There are polyfills though if you need to support older browsers.
Great support list! Thanks for that. My customers all use the latest Chrome, so I'm ok with fairly bleeding edge features.
Take a look at SwarmJs it uses CRDTs for multi user sync. http://swarmjs.github.io/articles/todomvc/
It seems to be a bit like using "git" to 3-way merge updates. In most cases (>99%), the merges are fine. But in some cases, a non-conflicting merge can have disastrous results.
(Please correct if I am wrong.)
You can build your data structures so that if there is a conflict (in your domain model) it'll be handled by your application. But that happens logically at a level above OT / CRDT.
> CRDTs are not a universal solution, but, perhaps surprisingly, we were able to design highly useful CRDTs.
[1] CRDTs: Consistency without concurrency control.
You get local reactive UI with immutable state. On the server-side, you can validate the ops as they come in using e.g. the entire infrastructure of passport in node. OAuth2-validated Share.js with strict per-property write access, no problem.
I also extended the couchDB driver to merge in server-side changes, thus allowing daemons to make live changes to the DB without having to care about any of the OT stuff. If share.js changes were made in the meantime, it will save a merged snapshot.
Basically, Share.js can be your insurance policy against pesky humans messing up your data structures, in a world of atomic data-driven robots and asynchronous feeds.
Also, what happens when simultaneously transmitted actions/patches are in conflict?
Conflicts are handled by the server-side dispatcher logic. Many applications can handle conflicts easily (eg. chat rooms which only append new messages), others can be more complex (eg. document editing). As mentionned in another comment, Remutable.Patch leaves room for rebase-like algorithms. Its definitely a very promising further work! :)
A cursory look at Remutable seems it to be the better and faster option :)
[1] https://github.com/cujojs/jiff
[2] https://tools.ietf.org/html/rfc6902
[3] https://github.com/zaim/immpatch
(edited formatting)
However I realized actual diffing was really slow, especially for large collections, as it involves scanning the entire structure for changes, when in fact all changes could simply be flagged upon mutation. Conceptually, it performs diffing (ie. it gives you a diff object), its just much, much faster!
Few minor questions: it looks like a base Remutable must be an Immutable.Map(). Can child items be any of the Immutable datatypes? Do we get updateIn() and similar?
Few questions -
How can we replay all the mutations?
How about instead of replaying, if we just show the last mutation? Will it not be the same thing?
I think this flux architecture will work best only in chatting applications. This approach is also making the app itself very chatter so performance concerns in case you do not have strong machines.
I think on form pages this flux approach may not be required.