<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Jan 29, 2018 at 3:53 AM, Mark Hammond <span dir="ltr"><<a href="mailto:mhammond@mozilla.com" target="_blank">mhammond@mozilla.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Thanks for writing this up Thom (and thanks for replying already Richard - I briefly respond to you near the end of this mail)<br>
<br>
First, for my own benefit, let me try and restate the issue we have here:<br>
<br>
* Currently no devices persist tombstones - they exist only on the server. If the server data is lost, any clients which have not synced between an item being deleted and the server wipe will resurrect deleted items - because no tombstone exists on any client nor on the server.<br>
<br>
* While we talk more about bookmarks, this is true for all collections with tombstones. This is also true no matter how we might lose the server data (of which there are many)<br>
<br>
* For bookmarks in particular, bookmark restoring may introduce other issues that will require thought.<br>
<br>
And that's pretty-much the full extent of our resurrection issue, right?<br>
<br>
The solution to this is, roughly, "have all clients remember all tombstones". The for sake of this discussion, we assume the cost of locally persisting tombstones is reasonable.<br>
<br>
The edge-case here is that:<br>
<br>
* client-1 syncs.<br>
<br>
* client-2 deletes a bookmark, creates a persistent local tombstone and uploads it to the server.<br>
<br>
* server data is lost<br>
<br>
* client-1 does the next initial sync and uploads the item (as it has no tombstone)<br>
<br>
* client-2 does the next sync - sees the item it knows for sure was previously deleted *somewhere* and must decide what to do.<br>
<br>
The only reason to not honor the deletion (ie, resurrect it) is the possibility that the bookmark might have been edited on one device but deleted on the other, so deleting it would be data-loss.<br>
<br>
The possible solutions to *this* are:<br>
<br>
* Always resurrect the item. This is what our current reconcillation logic will do as the last-modified timestamp on the server will be later than the time we recorded the deletion. IIUC, this is (1) below.<br>
<br>
* Always delete the item. This is (2) below.<br>
<br>
* Track more state so we can try and be confident we made the correct choice between resurrection and deletion. This is (3)<br>
<br>
* Give up in disgust, deciding that this is "edge-cases all the way down", which is (4).<br>
<br>
* Make each client aware of the fact that the server was wiped and that some other device has uploaded *its* view of the world and attempt to make decisions in a more holistic manner. I think this is what Richard was implying in part of his response.<br>
<br>
Am I missing something here? Are there other edge-cases not related to bookmark restore that I've omitted?<br>
<br>
If not, then I believe Thom is correct in that (2) below is the right thing to do. Closely followed by (4). (1) is clearly wrong, (3) is not worth the cost, and (holistic) is for some distant/alternate future.<br>
<br>
More comments inline:<br>
<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
On Thu, Jan 25, 2018 at 2:45 PM, Thom Chiovoloni 1. Treat tombstones more-or-less like we treat bookmarks now, that<span class="gmail-"><br>
is, keep them around locally, store remote ones locally when<br>
they come in, and resolve conflicts based on the modified<br>
timestamp on the item.<br>
</span></blockquote>
<br>
To make sure I'm not missing some subtlety, is this "more-or-less like we treat bookmarks" or "exactly like we treat bookmarks"?<br></blockquote><div><br></div><div>Exactly like we treat bookmarks. <br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
2. Store tombstones from the server locally in places (as in #1),<span class="gmail-"><br>
but always reconcile in favor of deleted items over new items.<br>
Once an item is deleted it's gone. (There are some nuances, e.g.<br>
If an incoming item has a local tombstone, we reupload that<br>
tombstone to the server (to delete it), etc.)<br></span><span class="gmail-">
This has issues around bookmark restoring, which aren't handled<br>
by my patch (probably it's biggest TODO).<br>
</span></blockquote>
<br>
Restoring is a problem, particularly in edge-cases such as the restore is from a completely different set of bookmarks (where the normal case is typically a restore from an older version of the same bookmarks). Further, it's not clear to me that we should honor tombstones that exist on the server on restore - the user may be restoring precisely to get back bookmarks they accidentally deleted - so it may be that storing tombstones doesn't make much sense.<br></blockquote><div><br></div><div>Storing tombstones with the restore would bring the state of our local tombstones back to the state they were at when the restorepoint was created.<br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
We certainly should do a better job on restore (and particularly automatic restore that happens before we are loaded, and better handle transient failures wiping the server), but otherwise I'm not sure we should conflate the 2 issues too much (which isn't to say we shouldn't consider how they interact)<span class="gmail-"><br></span></blockquote><div><br></div><div>Yeah, the concern is mostly with how they interact. Note that with solution #2 as implemented (e.g. ignoring restore), when a bookmark is resurected via a restore to bring it back after an accidental deletion (as you suggested), a remote client that happens to have seen the tombstone for the record will re-delete it, unless it gets a wipe command (which it will, unless we failed to notice the restore).<br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span class="gmail-">
<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
It also seems dangerous to never allow items to be undeleted --<br>
once a guid is discarded, it's effectively gone forever (except<br>
for cases where all clients with the guid wipeClient).<br>
</blockquote>
<br></span>
In what way is it dangerous? Is there any risk other than the "user deletes on device-1, edits on device-2, and gets upset we took the delete"?<br></blockquote><div><br></div><div>The main other risk I can think of is around restores, but in general it prevents us from ever adding other cases where we decide an undeletion is the correct approach -- other clients simply won't respect it.<br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
3. The "most correct" approach is probably to store the (best guess<span class="gmail-"><br>
for) the server timestamp when the bookmark was deleted in the<br>
places database, which would then be used for reconciliation<br>
(Possibly using a scheme similar to dateAdded for ratcheting<br>
time backwards).<br>
</span></blockquote>
<br>
IIUC we already do that</blockquote><div><br></div><div>We store a local timestamp currently, and don't do any dateAdded style ratcheting for it for tombstones.<br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span class="gmail-"><br>
<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
We'd also need to add the 'real' modification date to each<br>
bookmark record, e.g. the server timestamp upon editing the<br>
record. This would allow us to continue working as we do now<br>
(sometimes undeleting bookmarks).<br>
</blockquote>
<br></span>
Server timestamps have their own set of problems too - all we know is the time of the last or next sync - we clearly can't always know the server timestamp for a local deletion or modification - which itself leads to edge-cases.<br></blockquote><div><br></div><div>I think we'd we'd want to store the local timestamp until upload, and on upload, convert it to a remote timestamp, using how far in the past it is according to the local clock (since this is roughly the logic we use for reconciliation). Then, when you update the sync state to NORMAL, we'd change the timestamp from a local timestamp to the remote timestamp you just uploaded too. Yes, this is complicated, which is why I abandoned this option.<br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
A local timestamp would work (poorly) too - but yeah, this seems tricky and more complex than is worthwhile given it's an edge-case^2 (or are we up to ^3? :)<br>
<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
4. I guess we could also do nothing. It's an edge case, there<span class="gmail-"><br>
doesn't seem to be a perfect solution (after writing this up I<br>
still think #2 is probably the best). I also suspect that most<br>
people who have seen resurrected items, it was really bug<br></span>
1177516 <<a href="https://bugzil.la/1177516" rel="noreferrer" target="_blank">https://bugzil.la/1177516</a>>, which this won't fix at all.<br>
</blockquote>
<br>
I'm skeptical that users who reported resurrected items were talking only about default bookmarks - these defaults will not be resurrected by a node reassignment and users reporting issues explicitly mentioned they did indeed sync an "old" device.<br></blockquote><div><br></div><div>Yeah, you're probably right.<br></div><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
IOW, I believe bug 1177516 is "a very limited set of bookmarks may get 'resurrected' when a new device is added", whereas we are talking about "potentially unlimited set of bookmarks may get resurrected on node reassignment" - so 2 quite different things.<span class="gmail-"><br></span></blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span class="gmail-">
<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
I don't think #4 is the right choice, but I'm including it since<br>
Mark mentioned it in our one-on-one. I think we should still do<br>
this, since the code complexity isn't *that* bad (well, for #3<br>
it's a good amount worse), and it does solve a known issue -- we<br>
also knew it wouldn't be trivial when we decided to do it<br>
initially, and I don't think much has changed around this since<br>
then.<br>
</blockquote>
<br></span>
Another thing I mentioned was the possibility of "solving" this via UX - eg, when we notice an old device is about to Sync, we could check what they want to do (there's a bug on file for this, but can't find it) - there will be devil in the detail there too though (and even then, if the user selects "merge them", we are stuck in the same position we are now.)<span class="gmail-"><br></span></blockquote><div><br></div><div>I'm not convinced there's a solution that would work well enough just via UX. Some of the cases probably would hit it, but not all of these involve disconnected accounts or substantial amounts of time between syncs (these make it more likely, but only as far as it's more likely that you've deleted items in this timeframe).<br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span class="gmail-">
<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
(Admittedly, I'm biased though, I'd rather not have another OKR I'm assigned to where we end up doing nothing; as with the sync-repair system addon)<br>
</blockquote>
<br></span>
Yeah, that would suck, but I'm sure you agree that alone isn't a good enough reason to do something here :)<br>
<br>
But all in all, and as mentioned above, I'm leaning towards (2) too, simply because I feel that a user deleting on one device and editing on another is (a) unlikely, (b) may do the wrong thing today even when we don't lose server data, and (c) having these items be deleted when we guess wrong seems less surprising to the user than having then resurrected when they didn't actually edit the item.<span class="gmail-"><br>
<br>
On 27/01/2018 7:46 am, Richard Newman wrote:<br>
<br>
> A quick reply to this:<br>
><br>
> - First, to get it out of the way, I don't think we need to be<br>
> concerned about cost of keeping tombstones. However, the more<br>
> we store — timestamps, states, etc. — the more we have to<br>
> worry about this. Imagine<br>
> that poor user with multi-duplicated bookmarks thanks to old bugs,<br>
> creating thousands of tombstones as they clean up.<br>
<br></span>
I agree in general, although I think the cost of a tombstone without an extra timestamp vs one with an extra timestamp is noise. We could also use telemetry to help us understand how many tombstones we have and expire them if necessary - I'm really not too bothered by a device coming back after 2 years having somewhat strange things happen.<br>
<br>
IOW, local tombstones *do* have a cost that we will need to manage forever, both in places and sync. This is another argument for (4) :)<span class="gmail-"><br></span></blockquote><div><br></div><div>I suspect the cost for local tombstones is rather small. Certainly the `moz_bookmarks_deleted` table is much more lightweight than the `moz_bookmarks` table, even with my changes (which add a single INTEGER column, which will only ever be 0, 1, or 2 -- my understanding is that SQLite will optimize this under the hood in some manner, but even if it doesn't its a small amount of data).<br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span class="gmail-">
<br>
> - Secondly, I think it's worth taking one further analytical step beyond<br>
> timestamps. Your node reassignment concern in #1 is an ordering concern,<br>
> and your approach of keeping and ratcheting server timestamps is a<br>
> heuristic for specifying happened-before relationships that aren't<br>
> currently modeled in Sync. Reconciling conflicts and handling empty<br>
> servers is, in part, a question of deciding which changes to discard<br>
> because they happened in a previous 'epoch'.<br>
<br></span>
I don't understand what specifically you are getting at here? Is my "holistic" note above roughly what you mean?<br>
<br>
TBH though, IMO the further analytical step should really be around bookmark restore - there will certainly be additional trade-offs here.<span class="gmail-"><br>
<br>
> - When considering whether it's worth doing this work: how often do we<br>
> have users who: (a) have a device that's out of sync, (b) have<br>
> tombstones on the server, and (c) are node reassigned? That is, how<br>
> often do users' devices drift out of sync and undelete items because<br>
> of a failure to propagate deletions? And what else would this work<br>
> solve? I'm in favor of systems that behave predictably, but I'm not<br>
> usually in favor of trying to achieve predictability by piling on<br>
> layers of additional behavior onto a system that simply isn't<br>
> expressive enough.<br>
<br></span>
I agree with this in general, but it's tricky because node reassignments aren't a regular occurrence (let alone reassigning *every* user like we did last year) - but they are expected.<br>
<br>
IIU Thom's (2) correctly, there's not a whole lot of extra work or state to carry around here - it really is just "reconcile always prefers deletions" - that doesn't seem like it's adding much extra complexity, the cases in which it fails don't seem worth worrying about, so is arguably justifiable. Without a more compelling reason, I'm against (3) for exactly the reason you imply above - the bang isn't worth the buck.<br></blockquote><div><br></div><div>In practice it gets a bit more complicated than that, but yes, conceptually that's all there is. <br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
I do agree that we should be careful to understand what tradeoffs we are proposing here and make sure we understand and accept when (2) would do worse than the status quo in the face of these strange events, particularly with bookmark restore.<br>
<br>
But all of this has a cost - there's still space for someone to advocate for accepting (4) - the status-quo and doing nothing :)<br>
<br>
Thanks!<span class="gmail-HOEnZb"><font color="#888888"><br>
<br>
Mark<br>
</font></span></blockquote></div><br></div></div>