Hacker News Reader

Comment by aidos | Hacker News Reader

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.

View on HN

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.

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.

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.

Google wave used OT, but Operational Transform can fail sometimes and seems to have been superseded by CRDTs (Commutative/Convergent Replicated Data Type) http://stackoverflow.com/questions/26694359/differences-betw...

Take a look at SwarmJs it uses CRDTs for multi user sync. http://swarmjs.github.io/articles/todomvc/

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.

(Please correct if I am wrong.)

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.

UPDATE: Found this in the CRDT paper [1]:

> CRDTs are not a universal solution, but, perhaps surprisingly, we were able to design highly useful CRDTs.

[1] CRDTs: Consistency without concurrency control.

Native (mutable) Maps and Weakmaps are coming up with ES6, and are already (mostly) polyfilled by things like core.js.

Immutable provides (immutable) implementations of Map, OrderedMap, Set, etc. See http://facebook.github.io/immutable-js/ :)

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.

Look up "Om/React", might just blow your mind.

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.

OT is notoriously hard to get right. That's probably why there's little work done around it.

It gets more difficult the more operation types you add. With just two ops it's actually very simple.

Reply on news.ycombinator.com