Eventual Consistency in Real-time Web Apps
blog.johnryding.com
blog.johnryding.com
I don't see anything I recognize as eventual consistency in the traditional sense. It sounds like the client is just trying to receive a stream of updates, which could have been made by a single writer, and the only consistency issues are caused by the different overlapping mechanisms for getting updates.
I will say that our notifications come from a different service that is separate from the service the responds to HTTP requests, which leads to the process that is described in my post.
1) Local: In the view but before event dispatched to the model.
2) Local: In model but before it was synced to the server.
2a) Local: After model sync and in queue waiting to be sent to the server.
3) Remote: In transit to the server.
4) Remote: On the server (i.e. the one true state).
5) Remote: In transit to the clients.
6) Local: Received but before it was synced to the model.
7) Local: In model but before synced to the view.
8) In the initial state sync (e.g. when a new client joins)
So at any given point, every client state is inconsistent with every other client (maybe even significantly if the latency for one or more of the clients is bad) since pieces of the eventual state are spread across all these locations. If now every user stops changing state furiously, every client should eventually be consistent. It's not a hard problem but not completely trivial. For example, you will need conflict resolution rules on the server and in your client and traditional distributed issues like (temporary) network partitioning and latency need to be taken into account. Message ordering will probably matter.
>It sounds like the client is just trying to receive a stream of updates, which could have been made by a single writer
Not necessarily. You have the same synchronization issues whether the updates are coming from a single source, or from multiple sources.
The way I look at it, as long as the server has the final say over the "official" value at any given time -- which seems to be the case here, and is true in all real apps I've seen up to the backend datastore's ability to provide it -- you don't really have a consistency or convergence problem. You just have a UI problem. It's easy for the client to track both the latest official value and what the user is doing, and tell the server about the latter. The only question is what to show the user while their action is still outstanding, and the answer may be different for different kinds of UI. You may want to "fake it till you make it" (Meteor's default, aka latency compensation) or show some kind of loading indicator.
What about conflicts? Well, depending on your app, your options for how the server handles operations from the client include: they sometimes fail; they always succeed via "last writer wins" (good for a checkbox, say); they always succeed via operational transforms; or there is application-level conflict resolution that ropes in the user (implemented on top of the foregoing).
There's a trend at the moment to view everything as a distributed system, but if you treat a client as a tool for viewing information and calling APIs, it seems a lot simpler.
If two people make a change to the same documents at the same time, the changes are merged in a way that will never conflict. For example if we both simultaneously insert into a list embedded in some part of the data model, derby sends a "list insert at position X" operation, which is seamlessly transformed & merged into the document at all sites. The insertion position is updated automatically before merging using the same logic that makes collaborative text editing in etherpad work. Except you can do it over the JSON structures that power your web app.
Ok, I guess I must have misunderstood. If you're the guy whose building on-top some synchronization layer, then yeah, it's not really a problem. The sync layer is just another controller that manipulates your model or another consumer of your model changes.
If you're the guy implementing the synchronization layer, then you are thinking of distributed systems.
Merging the incoming deltas with fetched API state becomes a bit tricky, because you have to account for changes that might be happening while your GET is in transit. Alternatively, it may be that your notifications are slower than the GET request, depending on network conditions. An option that works in both of these cases (and doesn't involve version tagging all of your assets) is the approach described in the blog post.
Which CRDT things did you find, did you experiment with any, which are you using and why?
Aral Balkan gave a talk on a CRDT called WOOT for text editing[1] that I found really helpful to get the general idea of the concept. (Really only the last 8 or 9 minutes of his talk.)
If you want more of the nitty-gritty on some of the different types of CRDT, there's fairly readable paper on the topic[2].
From there, you can start using Google Scholar to find the other papers that have been written.
[1] https://www.youtube.com/watch?v=NSTZ4mIv_wk [2] http://hal.upmc.fr/docs/00/55/55/88/PDF/techreport.pdf
I like the Couch/Pouch idea, but it's really only handy when CouchDB fits your data. You can stream all CouchDB updates to a RDBMS using the changes stream, for example when you want to easily create management information, but I don't see how you can avoid making the CouchDB bunch-of-documents-per-db concept central to the app.
I haven't looked into Meteor, but my suspicion is that due to Mongo's comparably document-oriented setup, it can't be all that different.
Thus I started recording changes on the client, pushing them to the central server through functional endpoints and then pulling all changes from the server. To pull data from the server I found a paper[1] with an interesting way of encoding data so that the client can get a sense of the difference by getting a data structure of size proportional to the diff (no matter the whole dataset size). I developed a library for that, pretty limited for now [2].
[#2] http://conferences.sigcomm.org/sigcomm/2011/papers/sigcomm/p... [#1] https://github.com/3musket33rs/mathsync
OT but seems like a good time to ask, does anyone have any experience with Operational Transformations for dealing with syncing in web apps? I've started throwing the idea around for a web app I'm building and it seems like a really interesting pattern. The only real implementation I can find is in sharejs [1]. I work with python on the backend and I can't really find an implementation of it (though for my constrained use-case I can generate good enough code to do it myself).
It seems like a good approach but there's very little in the way of libraries implementing it, so I was wondering if it's somehow problematic.
Aral Balkan gave a talk on OT vs a CRDT called WOOT for text editing[1] that I found really helpful.
If you want more of the nitty-gritty on some of the different types of CRDT, there's fairly readable paper on the topic[2].
[1] https://www.youtube.com/watch?v=NSTZ4mIv_wk [2] http://hal.upmc.fr/docs/00/55/55/88/PDF/techreport.pdf
I'd also read that it's hard to get right (I think that was in a comment on HN by one of the people who worked on wave/sharejs). In my case I've limited myself to two different flavours of small object with a limited set of fields (instead of a totally generalised system). Most of the algorithms I've seen focus on the text element of the syncing but I'm much more interested in the object / list / field part for my use case.
Sharejs actually have a generic system of handling the OT on arbitrary json structures, but I'm not sure how well it works.
My use case is a little different, and one that OT seems to suit.
I have multiple users working on the same documents but they don't want/need to see each other's changes straight away. They perform a number of operations and then eventually save. When they save I'd like to propagate that that history to the other user(s) that haven't saved yet. It feels like OT works there - you have two threads of history and you need to rebase the uncommitted one on top of committed one.
Maybe I'm coming at the problem wrong, but it feels like something that could work quite well as a pattern in general.
Yes, you give up generality. But in exchange you get a more natural system with fewer strange edge cases that has good performance and won't lose data under pressure.
The biggest downsides of CRDTs are that your data ends up much bigger (although usually by a constant multiple), and nobody has figured out how to edit JSON documents using CRDTs yet.
Its not all that surprising that CRDTs will be larger - imagine a stream of operations happening to a document (think about them like tiny git commits, if that helps). You can end up with a lot of changes for a small document (tens of thousands of changes for a single page of text isn't unheard of). CRDTs in effect embed the history of operations into the document, while OT stores them separately. As such, with OT you can eventually migrate the operation log to secondary storage (or throw it away). You can never really do that with CRDTs.
The JSON problem is harder, and obviously very important for realtime web apps that do more than text editing. Decent CRDTs will be trivial to add to ShareJS when they're ready.
I believe I got this idea from Backbone's documentation [1] originally, but I've seen it mentioned in other places as well.