Syncing Bookmark Tombsones

Thom Chiovoloni tchiovoloni at
Mon Jan 29 20:44:41 UTC 2018

On Mon, Jan 29, 2018 at 3:53 AM, Mark Hammond <mhammond at> wrote:

> Thanks for writing this up Thom (and thanks for replying already Richard -
> I briefly respond to you near the end of this mail)
> First, for my own benefit, let me try and restate the issue we have here:
> * 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.
> * 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)
> * For bookmarks in particular, bookmark restoring may introduce other
> issues that will require thought.
> And that's pretty-much the full extent of our resurrection issue, right?
> 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.
> The edge-case here is that:
> * client-1 syncs.
> * client-2 deletes a bookmark, creates a persistent local tombstone and
> uploads it to the server.
> * server data is lost
> * client-1 does the next initial sync and uploads the item (as it has no
> tombstone)
> * client-2 does the next sync - sees the item it knows for sure was
> previously deleted *somewhere* and must decide what to do.
> 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.
> The possible solutions to *this* are:
> * 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.
> * Always delete the item. This is (2) below.
> * Track more state so we can try and be confident we made the correct
> choice between resurrection and deletion. This is (3)
> * Give up in disgust, deciding that this is "edge-cases all the way down",
> which is (4).
> * 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.
> Am I missing something here? Are there other edge-cases not related to
> bookmark restore that I've omitted?
> 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.
> More comments inline:
> On Thu, Jan 25, 2018 at 2:45 PM, Thom Chiovoloni      1. Treat tombstones
>> more-or-less like we treat bookmarks now, that
>>         is, keep them around locally, store remote ones locally when
>>         they come in, and resolve conflicts based on the modified
>>         timestamp on the item.
> To make sure I'm not missing some subtlety, is this "more-or-less like we
> treat bookmarks" or "exactly like we treat bookmarks"?

Exactly like we treat bookmarks.

>      2. Store tombstones from the server locally in places (as in #1),
>>         but always reconcile in favor of deleted items over new items.
>>         Once an item is deleted it's gone. (There are some nuances, e.g.
>>         If an incoming item has a local tombstone, we reupload that
>>         tombstone to the server (to delete it), etc.)
>>         This has issues around bookmark restoring, which aren't handled
>>         by my patch (probably it's biggest TODO).
> 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.

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.

> 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)

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).

>         It also seems dangerous to never allow items to be undeleted --
>>         once a guid is discarded, it's effectively gone forever (except
>>         for cases where all clients with the guid wipeClient).
> 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"?

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.

>      3. The "most correct" approach is probably to store the (best guess
>>         for) the server timestamp when the bookmark was deleted in the
>>         places database, which would then be used for reconciliation
>>         (Possibly using a scheme similar to dateAdded for ratcheting
>>         time backwards).
> IIUC we already do that

We store a local timestamp currently, and don't do any dateAdded style
ratcheting for it for tombstones.

>         We'd also need to add the 'real' modification date to each
>>         bookmark record, e.g. the server timestamp upon editing the
>>         record. This would allow us to continue working as we do now
>>         (sometimes undeleting bookmarks).
> 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.

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

> 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? :)
>      4. I guess we could also do nothing. It's an edge case, there
>>         doesn't seem to be a perfect solution (after writing this up I
>>         still think #2 is probably the best). I also suspect that most
>>         people who have seen resurrected items, it was really bug
>>         1177516 <>, which this won't fix at all.
> 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.

Yeah, you're probably right.

> 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.

>         I don't think #4 is the right choice, but I'm including it since
>>         Mark mentioned it in our one-on-one. I think we should still do
>>         this, since the code complexity isn't *that* bad (well, for #3
>>         it's a good amount worse), and it does solve a known issue -- we
>>         also knew it wouldn't be trivial when we decided to do it
>>         initially, and I don't think much has changed around this since
>>         then.
> 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.)

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).

> (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)
> Yeah, that would suck, but I'm sure you agree that alone isn't a good
> enough reason to do something here :)
> 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.
> On 27/01/2018 7:46 am, Richard Newman wrote:
> > A quick reply to this:
> >
> > - First, to get it out of the way, I don't think we need to be
> > concerned about cost of keeping tombstones. However, the more
> > we store — timestamps, states, etc. — the more we have to
> > worry about this. Imagine
> > that poor user with multi-duplicated bookmarks thanks to old bugs,
> > creating thousands of tombstones as they clean up.
> 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.
> 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) :)

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).

> > - Secondly, I think it's worth taking one further analytical step beyond
> > timestamps. Your node reassignment concern in #1 is an ordering concern,
> > and your approach of keeping and ratcheting server timestamps is a
> > heuristic for specifying happened-before relationships that aren't
> > currently modeled in Sync. Reconciling conflicts and handling empty
> > servers is, in part, a question of deciding which changes to discard
> > because they happened in a previous 'epoch'.
> I don't understand what specifically you are getting at here? Is my
> "holistic" note above roughly what you mean?
> TBH though, IMO the further analytical step should really be around
> bookmark restore - there will certainly be additional trade-offs here.
> > - When considering whether it's worth doing this work: how often do we
> > have users who: (a) have a device that's out of sync, (b) have
> > tombstones on the server, and (c) are node reassigned? That is, how
> > often do users' devices drift out of sync and undelete items because
> > of  a failure to propagate deletions? And what else would this work
> > solve? I'm in favor of systems that behave predictably, but I'm not
> > usually in  favor of trying to achieve predictability by piling on
> > layers of additional behavior onto a system that simply isn't
> > expressive enough.
> 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.
> 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.

In practice it gets a bit more complicated than that, but yes, conceptually
that's all there is.

> 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.
> But all of this has a cost - there's still space for someone to advocate
> for accepting (4) - the status-quo and doing nothing :)
> Thanks!
> Mark
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the Sync-dev mailing list