Clarification around latest version of RON

[Erudition]

Hi, I love the updates I'm seeing at http://doc.replicated.cc. The RONt format looks cleaner (I'm trying to wrap my head around it and implement it at the same time) and the explanations look more concise and complete. Since the old stuff at replicated.cc is not as old as the stuff in this repo, the inconsistencies between them has left me trying to walk through your history and understand how and why the format has changed over time, despite so many holes in documentation (e.g. the new "docs" site has many blank pages) where I have to fall back to older versions.

Is there going to be any point at which the "docs" site version (3?) is made official? I have some questions about the changes - such as, should I rename my "LWW" objects to "struct" (a much nicer name) or "trie" or "dict" or does the old LWW have no match in the new system?

[cblp]

@Erudition please help me implement it in https://hackage.haskell.org/package/ron

[cblp]

By the way, I find LWW dangerous to use for structures, I use OR-set.

[Erudition]

Hi cblp, thanks for your contributions! I loved learning Haskell but I found it hard to work with in everyday code given the error messages and short syntax, but lately I've fallen in love with Elm, which has Haskell roots but solves all the roadblocks for me. That said, while I can't help much with the haskell code, I've been implementing RON myself in Elm! It's been a long project over many weeks and it took crossreferencing all three RON docs to grok most of the rules, but you can get a glimpse of my work over here: https://github.com/Erudition/Minder/tree/master/elm/Replicated

Anyway, while this is an entry-level experiment and not suitable as a standard library like I'm sure yours will be, I am making great progress in having a working RON serialization scheme. It is clean-room implemented in a very different way from yours I'm sure.

I've only managed to implement LWW so far. What is it that you think is dangerous? I'm basically using them to serialize Records. How might one use an OR-set for that?

[cblp]

@Erudition I described the LWW-struct problem in a blog post https://cblp.github.io/2021/10/07/CRDT_structure_encoding.html

[Erudition]

@cblp Fascinating!

Thank you for making me aware of the schema-change and concurrent-initialization possibility. Right now I'm focusing on a user-friendly type Register that will expose an interface as a LWW-Register by default for simplicity but allow the user to provided a custom "conflict resolution" function when desired - thus it is effectively a multi-valued register.

That still works for flat values with no UUID references. Reading your post, I think that when a nested field (pointer) is detected, the default resolution algorithm should instead simply fetch the objects at all specified pointers and provide the application with a merged one. That should do the trick!

[cblp]

@Erudition How do you detect "conflicts" with LWW?

[Erudition]

Re-reading my post, but still not sure what you mean by "detect conflicts with LWW".

LWW is one particular conflict resolution algorithm. A Register that uses only this algorithm could be called a LWW Register, as described in RON.

Instead, I intend to provide simply a Register, where LWW is the default resolution algorithm but a more domain-specific chooser can be specified. That's the point of a multi-valued register, after all. In the end we still typically want one value to "win".

By "conflicts" I just mean concurrent updates, of course.

[cblp]

LWW is a conflict resolution policy of ignoring any conflict. What if I don't want to ignore? If I add a tag to an item on one replica, and another tag on another replica, I don't want to ignore one of them, I want to keep both.

How do you specify a more domain-specific chooser?

[Erudition]

Eh, to me "ignoring a conflict" would be to keep an older value and not use either of the new conflicting values. As in git with conflicts that must be merged manually, and until then nothing changes.

Whereas, picking one of the values to "win" is one way of resolving a conflict. And it's extremely common - for many use cases it's the only method that makes sense (e.g. if a task's progressComplete variable gets set to 60% on my phone, then 90% on my laptop, the new truth should reconcile to the more recent 90%). I know it feels scary to "throw away data", but that's exactly what's desired here. Actually, it's not thrown away, because it's history. I could always hit "undo" and go back to 60%.

Anyway, I get what you're saying, there are cases where it feels wrong to not incorporate both changes in some way. Perhaps you want to incorporate a concurrent edit of the task's title, when resolving with a newer edit of the title. I'd argue that the user might be fine with (and even expect!) that the newer title overwrites the old one completely, but text fields are always eligible to become a "collaborative text editor" type as described in RON, so not applicable here.

Your tag example is not valid, because while the "item" you describe may, at the top level, be represented as a Register, the tags: field of that register is simply a pointer to a Set object elsewhere, not some flat list of tags that gets overwritten. From my understanding of reading the entire RON site, this is how it is meant to be used. Thus, when adding a tag to the Set object, concurrently with a different tag to the same set, there is no conflict to resolve - both tags are kept because that's how a set CRDT works.

So to find a valid example we'd have to come up with something that:

1. Would be found as a field (a single value - hence the whole idea of a "winner") in a Register object (representing some item in an application)
2. Would NOT be best represented as a nested object (like sets, lists, maps, dictionaries, counters.... stuff other CRDTs are meant for) but only as a flat value.

I can't think of any examples like that at the moment, but I'm sure there are some. In that case, like I said, falling back to a Multi Valued Register works fine. You can either expose the conflicting values to the application (forcing the application to expect not a single value but a nonempty list) or you can program a custom resolver function into the register itself. So for my Register type, I'll probably put it in the initialization function, an optional argument that takes a function from Nonempty Thing -> Thing (Elm types). Or better yet Nonempty (Thing, RonUUID) -> Thing so the custom function can take the timestamp, replica, etc into consideration when choosing the winner.

[cblp]

The biggest problem arises when you have no Set object yet but want to add a tag. What do you do in that case?

[Erudition]

I would 1. initialize the Set object 2. Set the corresponding Register field's value to the new set's UUID 3. Add the tag to the Set as usual.

I don't see any problems there, but if you meant to refer to the problem of "what if two replicas concurrently initialize the Set without knowing about each other" which you described well in your blog post - then I agree that's a problem, but I think the solution I proposed should work.

[cblp]

Ok, suppose you initialized two Set objects concurrently. How would you merge Register{tags=set1} and Register{tags=set2}? What your solution does in this case?

[Erudition]

See previous,

In that case, like I said, falling back to a Multi Valued Register works fine.

The accessor for Register.tags would do a Set.union of all the sets it finds.

Even if there's a third concurrently-initialized-set that takes a year to show up, Register.tags will still get every known tag, forever.

[cblp]

Yes, that's my point, that you have to use MV. But if your register resolves "conflicts" as MV, why do you call it LWW?

Maybe it's rather MV with fallback to LWW as a default merge operation?

[Erudition]

that you have to use MV

The Multi-value-ness is only used to resolve the conflict - in the same way that two simultaneous RON Ops get resolved by the preferring the replica with a higher replica ID - that is to say, it's not necessarily ever exposed to the end user of the Register, or even in the API for it. If we don't expose any functions for accessing multiple values, it cannot really be called a Multi-Value Register. Despite the fact that the single value given can be sourced from separate RON Ops.

Here's another example: Undos. When you get the latest value(s) from a Register, the Undo Ops are already taken into account - so the latest op may not be the one you get (it may have been undone). So the Register is still providing an accessor that returns a single value, despite the fact that multiple Ops are consulted in the process of constructing that value. Yet we woudn't consider an LWW Register to be "multi-valued" simply because it supports Undo.

When returning a single Set, like your tags example, we consult multiple ops as well. By consulting all the concurrently-initialized sets, we're really just considering a few more ops in the same function that gives the end user a single cohesive Set.

Maybe it's rather MV with fallback to LWW as a default merge operation

I would phrase it conversely - it's LWW for nearly everything, except nested Sets where it falls back to an MV-based algorithm. Though I don't see anything wrong with saying it's both LWW and MV.

But I'm not sure you need to call it MV if it doesn't ever give the user multiple values when querying a single field.