Closed Bug 720592 Opened 13 years ago Closed 3 years ago

Better handling of conflicting records


(Firefox :: Sync, defect, P4)






(Reporter: gps, Unassigned, Mentored)


(Blocks 1 open bug)


(Whiteboard: [sync:bookmarks][sync:history][sync:passwords][sync:prefs])

Sync currently drops record data under a specific scenario where there are local changes already made to an incoming record. See the comment in Engine._reconcile() (introduced in bug 710448). We should come up with some way to allow engines to resolve conflicts so we don't drop data in this situation.
I expect the most common case to be history. Visits can be fairly easily merged (modulo timestamp imprecision; Places uses microseconds!), and will conflict quite often -- no instant sync for history.
Whiteboard: [sync:bookmarks][sync:history]
This also suddenly becomes an issue when we're tracking usage and modification timestamps for passwords.
Blocks: 555755
Whiteboard: [sync:bookmarks][sync:history] → [sync:bookmarks][sync:history][sync:passwords]
Some thoughts on this.

The obvious approach is to extend both SyncEngine._reconcile and .update to say "yes" to remote records more often, and to handle merging the changes respectively.

The problem with that is illustrated by the following:

* Local change occurs to something we don't care about. Record it in the modified list.
* Remote change arrives that changes something material.
* How do we know the local change was to an immaterial field? We only know it was modified, but not how.
* Similarly, how do we know the remote change was to a material field?

We can perhaps assume that the remote change is significant, but without a Git-esque knowledge of previous state, we simply don't know for sure which fields are canonical, and which changed on each end.

(In short: we cannot do a three-way merge, because we don't know the shared parent.)

We have a few options.

* Record two separate sets of modifications locally: material and immaterial.
* Both kinds of changes are uploaded if there are no conflicts. (Which is somewhat unfortunate: because all remote changes are considered material, our upload of an immaterial change produces a materially-changed record for other clients.)
* Remote changes are applied ignoring immaterial changes, optionally with a smarter .update (e.g., only apply timestamps if they're newer). There will be some data loss -- if a password is used once in two places, one of those two uses will be lost.

* Record a delta of modifications locally.
* Use those notes about what changed when applying remote changes. This gives us the ability to ignore conflicts in immaterial fields. This is nearly isomorphic to splitting each record in two and syncing them separately.

* Ignore local immaterial changes altogether. We'll trade "minor" data loss (timestamps, etc.) in exchange for avoiding "major" data loss (passwords).

Greg, you have nearly as much record application guts on you as I do. Do you have thoughts on this?
Flags: needinfo?(gps)

Retaining enough state to enable a three-way merge is going to be a lot of effort. My gut reaction is to go with the easy approach of allowing engines to implement a custom reconcile algorithm, which will add an incrementally better level of conflict resolution until Sync can be rewritten to support the robust solution.

Also, let's get some data metrics on this problem so we can identify the impact on users.
Flags: needinfo?(gps)
My concern about pushing this down to the engine level is that in order to do something that doesn't suck, we still have to address three-way merges: how does, say, the passwords engine know that the local modification was only to a timestamp/count rather than to a material field? Well, it has to track a sequence of changes in memory (which is concerning if MP is enabled).

Furthermore, how does the engine know that a remote conflicting change is immaterial? (IOW: how do we transfer a sequence via the Sync record format?)

Perhaps it's fair to say that I'm not sure an incrementally better solution exists -- at least, one that's better than "don't track immaterial local changes at all".

I'm still chewing on this.
Further thoughts on this:

Option 2 isn't trivial, but might admit a general solution.

Something like the login manager gives its observers both the original and changed record when a modification occurs.

This gives us, over time, a sequence of changes.

If we assume that the shared parent of the server record is the first item in that sequence (a valid assumption, so long as we never lose changes), and we assume that server changes are either acceptable to coalesce, or only ever occur singly (fair, given that other clients should be reconciling, and the server is coalescing!), then we are able to do a three-way merge.

That is: we have the shared ancestor and both branches, in 'full'. The server branch is always a single step.

This generalizes the current approach, and the only per-engine part would be the specifics of the record merge.

One problem with this is that the sync engine would need to store password events in memory.

This perhaps is acceptable -- after all, it's not storing anything that wasn't just broadcast to the entire running browser chrome.

This is strictly the best solution that we can build without modifying the server and protocol.

I am leery of both option 1 and option 3. Option 3 is safer than 1 in that it will never result in a lost password, but in return it ensures that timestamp and count data will immediately diverge between clients and cease to be even remotely accurate, which means the work in Bug 555755 is futile.
Some time with a notepad gives me some confidence that I can build a TWM algorithm and integrate it with the current record application process and password tracker.

My bigger concern is that Android is unable to determine the shared ancestor, because it doesn't have a tracker.

That means a change to Sync on Android before we're able to roll this out.

I'll file a separate bug for that.
Assignee: nobody → rnewman
I can reliably reproduce the same issue for the prefs engine. I'm yet to understand the prefs engine, but, one example is that "remote" record has an entry |"privacy.clearOnShutdown.passwords":true| where the local record does not have that entry - even though about:config shows the exact same preference locally. But, that preference was actually deleted recently - ie, my local profile toggled the pref to a non-default value, then the default value for the preference was removed. I'm not sure how relevant that is yet.
Whiteboard: [sync:bookmarks][sync:history][sync:passwords] → [sync:bookmarks][sync:history][sync:passwords][sync:prefs]
Flags: firefox-backlog+
Priority: -- → P1
I won't have time to build this myself.
Assignee: rnewman → nobody
Mentor: rnewman
Priority: P1 → P2
Marking P4 for now because it's not immediately actionable.
Priority: P2 → P4
Component: Firefox Sync: Backend → Sync
Product: Cloud Services → Firefox

(In reply to Chris Karlof [:ckarlof] from comment #10)

Marking P4 for now because it's not immediately actionable.

I'm dropping this from the list of mentored bugs, based on this comment, and lack of details.

I don't think this is actionable as described.

Closed: 3 years ago
Resolution: --- → INCOMPLETE
You need to log in before you can comment on or make changes to this bug.