Multi-value register instead of Last-write-wins semantics?

[gabrielgrant]

Loro's map docs explain that it uses LWW for conflict resolution. IIUC, though, the history is, in fact, stored internally, which makes me think it should be possible to identify conflicts, access the multiple conflicting states/operations, and potentially implement alternative conflict resolution strategies. Is that possible with Loro today? How would this be best achieved?

[zxch3n]

Yes, it's theoretically possible. But we have not provided an API for it yet. Do you have a concrete use case that needs this? We'd like to discuss how to design the API for use cases like this.

[msdrigg]

I would love to consider alternative strategies for conflict resolution for my use case as well. I just read this article here (https://www.moment.dev/blog/lies-i-was-told-pt-1) and it's associated hn discussion where loro came up a few times actually (https://news.ycombinator.com/item?id=42343953). I think the discussion there is relevant to this issue.

So my use case for Loro is to manage syncing an on-premise system (which might auto-discover devices, or have users edit the config locally) with a remote settings server+editor. The reason for a CRDT is to allow these offline edits on the local system even if the internet is out for several days

I am just getting started with Loro, so I am not sure how much would be possible, or how what API surface would work well, but I can imagine a few conflict features that would be interesting to me:

1. Preferential Treatment for certain Peers
So maybe the local admin makes an on-site change to edit a devices parameters (set the color to yellow), while at the same someone on the remote instance makes conflicting changes to the device parameters (set color to green). I would love to have a way to say so that the local admin's changes are preferred when the sync occurs (the color stays yellow after remote syncing).

This would be preferable because in the case of conflict, I would prefer the site to not magically change configuration after the internet comes back online.

2. General Conflict Detection
Another feature that would be interesting to me is to have some way to track when there has been a conflict (even though it has been resolved mathematically). For example if remote and local admins make changes to the same devices parameters, then the next time someone logs on I would love to be able to show them 'hey, there was a resolved conflict'. Then, they could ignore the problem, or they could look and manually make the change to fix it how they like.

3. Custom Conflict Resolution Rule
I can't actually think of a good example here, but I can imagine a scenario where given concurrent edits X and Y to a structure (e.g. X = remove the color field and Y = set the color field to yellow), a user would like to apply their own resolution to resolve to a final structure Z (for example, it should be yellow because it's better to have some color than none).

What do you think of these scenarios?

[zxch3n]

Do you think 1 and 2 can be solved by using multi-value registers? For example, when you use map.get(key), it returns a list of values instead of a single value.

For 3, it would require a central server to detect and resolve the conflicts by patching the document. In a P2P setting, this would be like requiring the users to invent their own CRDTs.

[msdrigg]

Yea I think that would work for 1 and 2. I would want it to be a separate API though instead of replacing the current API. I think for the CRD T’s, myself, and most people are gonna want the resolution done automatically.

I actually think this also solves 3. Because that central server can detect whenever there’s multiple values returned from a map and look through those values and present some UI to a user to fix.

I guess my only question with this is: would it be possible to ‘fix’ a conflict after the fact? Like if getting a value from a map returns two options, then would it be possible for a client to ‘fix’ the conflict by overwriting the maps key after it sees both conflicting oplogs?

Correct me if I have the wrong mental model for this, I’m pretty new to this space

[gabrielgrant]

Sorry for taking a bit to get back to this, and thanks for fleshing this out @msdrigg

My use cases are similar:

1. first class support for conflict detection so that this info can be surfaced to users. seeing changes ignored/overwritten can be surprising and should be called out
2. Custom merge/conflict resolution. Either allowing the user to do so manually, or automatic/algorithmic Yes, insofar as CRDTs are just conflict resolution rules, this would effectively be allowing support for custom CRDTs, however they need not be particularly complicated. @msdrigg 's two examples above seem like good ones:
   1. preferring a field be filled with some value, rather than a concurrent deletion
   2. Explicitly prioritizing edits from particular peers (this is effectively already the case today based on peer id iiuc, right?)

Pretty sure the needed info for these use cases is already in the oplog. And it seems likely this is all effectively possible somehow today by manually walking through history? But not immediately obvious from looking at the docs. And in particular, wondering if there's a better way to mark a particular version as the "resolved"/current version than just doing a new set operation with that final value

[zxch3n]

@gabrielgrant

Regarding the first point: We can provide interfaces to detect concurrent overwrites in newly imported operations. This mainly affects:

• Set operations on LoroMap
• Set operations on LoroMoveableList

Other scenarios (text insertion/deletion, style overwrites, tree movements) are either rare or have limited user control options.

For the final events, we could include hints when concurrent set operations cause conflicts, possibly wrapping our write records in the event. Would this solve your needs?

Custom Merge/Conflict Resolution challenges:

• Very problematic because we must maintain CRDT document state
• User-provided custom logic might break CRDT validity, causing cross-endpoint inconsistencies
• Ensuring CRDT validity is extremely complex
• Internal operations (undo/redo, version rollback, serialization) are too complex for user definition
• We initially considered user-registered CRDT types but abandoned it due to excessive complexity

Alternative approach:
We can provide interfaces to walk the underlying OpLog, letting users implement custom logic on top. However:

• Walking OpLog is slow
• OpLog is sometimes incomplete (e.g., shallow snapshots only contain partial logs)
• With shallow snapshots, you start from a potentially unwanted document state (doesn't match the state you want), which is tricky

Would this OpLog walking approach work for your use case?

[gabrielgrant]

@zxch3n thanks for the follow-up

Yes, those two set operations seem like the most important. In general, it seems this is mostly relevant for operations where conflict resolution has fallen back to depend only on peer ID. And particularly ops that set a value that is resolved to exactly what was set by one peer based on peer ID, and where the operation performed by other peers is completely ignored (unlike, say, text manipulation, or tree movements, where, in general, the resolved final value is some more sophisticated combination of the peers' changes)

Having these types of conflicts flagged in the event that reports updates back to user code seems like a good approach (though I'm not 100% sure I understand what you mean by "wrapping our write records in the event")

Re: custom merge

I understand there are almost certainly complexities I'm overlooking in fully-user-defined CRDTs. Requiring that the core CRDT types be defined by within the loro codebase seems like a reasonable design decision. Instead of fully-custom CRDTs, perhaps certain specific CRDTs could have user-defined hooks to customize behavior in ways that would address the use-cases @msdrigg and I provided? (eg, by default peers are prioritized by peer id, but this prioritization could be optionally overridden by a user-defined ordering function)

Re: oplog walking

This seems like it would potentially be very useful. By OpLog walking, I'm assuming you mean something more granular than doc.getAllChanges()? Being able to incrementally walk (backwards?) through the OpLog without having to materialize the whole thing (a la git log), for example?

Edit: It appears there's a doc.travelChangeAncestors() method used by the inspector. Not finding any docs on it, but from a brief glance at the code seems it may do this?

[zxch3n]

@gabrielgrant

Edit: It appears there's a doc.travelChangeAncestors() method used by the inspector. Not finding any docs on it, but from a brief glance at the code seems it may do this?

Yeah, you can give it a try. We may be able to create an API for travel that targets a container only to make this faster.

by default peers are prioritized by peer id, but this prioritization could be optionally overridden by a user-defined ordering function

How should this user-defined ordering function look?

You can simulate an MVR by combining LoroMap and LoroList, though.

map.set("name", "David") =>

const list = map.get("name");
list.clear();
list.push("David");

map.get("name") =>

const list = map.get("name");
// If there are multiple values in the list, they are inserted concurrently. 

[gabrielgrant]

@zxch3n thanks for the follow-up!

Honestly haven't thought through the example of peer id ordering alternatives, so that may not be a good idea. Was thinking something along the lines of how you can pass a custom compare function to JS' Array.sort() method (though perhaps should allow return values to be async?), but certainly see how that could break (or at least add a lot of complexity) if different peers' compare functions could prioritize peers differently at different times

MVR with map of lists is interesting. I'm understanding correctly that list.clear() calls only removed items present in the list locally at the time of the call, so don't interfere when other peers are also clearing and pushing items concurrently? (that does seem like the sensible alternative to LWW/max-peer-ID resolution, but not finding it explicitly in the docs)