Hacker News Reader

Comment by amelius | Hacker News Reader

Another problem is this. Let's say there is a counter that is at value 100. I increment the counter. Simultaneously another user increments the counter, so the stable value should be 102. However, a operation-agnostic "merging" approach like described here can never catch that, and sets the final value to 101.

View on HN

CRDTs generally benefit from "intent preservation" in their design. In automerge's case, this would mean that instead of storing a "set" value, you'd store either an "increment" value or a "set" value to support cases like the one you describe.

Automerge has fairly robust support for these kinds of use-cases around lists, which we use quite a lot, but we haven't actually needed them for numbers (though I expect we may want them eventually.)

My experience is with OT, so I can't speak for CRDT, but I can imagine it's similar.

With OT, you send a na[1] (number add) operation, so this would work fine. Indeed, if you treat the number as a string, then you have a problem.

[1]: https://github.com/ottypes/json0#summary-of-operations

This doesn't compose with all operations. One users adds and another user multiplies, for example. That is to say, not all operations are associative.

I bet you can run really far with this general idea. But there is no panacea.

You're absolutely right, but I'd also never suggest a collaborative system for anything critical. As I've said earlier in this thread: If you're in a Google Docs document with a buddy and you write "A" and he writes "B" at the same time, you also don't know whether that'll show up as "AB" or "BA". In practice, this isn't an issue.

To underscore our point, concatenation on strings is not associative, either.

To that end, the basics of math in associative, cumulative, distributive, etc., go together to create an algebra of what you can automate rather easily. I think most of us stopped thinking in terms of those laws years ago. To the point that it is probably odd to folks that stayed close to them.

> To underscore our point, concatenation on strings is not associative, either.

I think you mean commutative. It certainly is associative.

Ha! Yes. I meant to draw attention to all of the fundamental laws people are used to. Messed up in some edit.

Thanks!

As I understand it, CRDTs don’t work on atomic types you might use in normal code - they work on larger structures where the problem has been solved.

Wikipedia has some examples: https://en.m.wikipedia.org/wiki/Conflict-free_replicated_dat...

If you model all state changes as a serializable list of actions, like with Redux or Vuex, this is a non issue. You'd simply get the same two commands and your reducers would compute the same state for all clients, thanks to immutable data structures we don't need to mutate the state & do not have the issue you described.

The challenge is when there are multiple observers that have a different opinion on what order the commands happened in. Redux and Vuex don't have that problem, that's why it's a nonissue there.

Using lamport/logical timestamps you can ensure a distributed and totally consistent ordering of actions.

I wrote a middleware for Redux which propagates actions peer-to-peer in a consistent order using these timestamps and the scuttlebutt gossip protocol, you might find it interesting. https://github.com/grrowl/redux-scuttlebutt

That sounds like expected behavior. Both users are incrementing a value of 100, which would be 101 in both cases. It's not atomic.

If User A incremented 100, and saved it down; then User B loaded this saved state and incremented 101, it'd be 102.

But the point was: what if you wanted the behavior to be different than what you described. What if the intent was really "increment"?

For example, say you have a list AND a counter. Everytime you add an item to the list, you need to increment the counter, as an invariant of your system.

Of course, it's a contrived example, but you get the point: things can get more complicated and the system may break as a result, unless you're very careful.

We had this problem in our iOS app, solved it by using an array of ints wich are the increment-operations (well, we had uuids on them as well so we could determine what was new and do a proper merge).

But we merge by using differential synchronization (kinda) to resolve local changes and remote changes (to construct a "patch") by keeping an unchanged copy of the upstreams latest version (from the clients perspective).

Good point! I think you'd have to implement a lock of some sort, and check for it in application logic-- that way both can be updated simultaneously... not ideal!

Reply on news.ycombinator.com