Syncing Bookmark Tombsones

Richard Newman rnewman at
Fri Jan 26 20:46:54 UTC 2018

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.

- 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'. You might find that your decision about
what to do with this bug is easier if you can describe the various cases —
restores, node reassignments, conflicting writes, sign out/sign in, old
clients — and their potential problems (undeletion or incorrect deletion)
in these terms.

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

On Thu, Jan 25, 2018 at 2:45 PM, Thom Chiovoloni <tchiovoloni at>

> Before break (before Austin, really), I put a patch up on bug 1343103
> <> that I'm only so-so about. It got f+, but I'm
> going to explain my concerns before finishing it.
> Currently we store tombstones locally until the next time we sync. Once we
> sync and upload the tombstones we have locally, we delete them from places.
> When we receive a remote tombstone to the server, if we don't have that
> item we do nothing, and if we do, we delete it (without creating a
> tombstone for it). The server will store tombstones roughly indefinitely,
> but not durably.
> Options:
>    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.
>    This approach fails in several cases. For example, if there is a node
>    reassignment, if the first client to sync didn't see all tombstones on the
>    server before the node reassignment, we will resurrect the deleted item.
>    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 is the approach I took with my patch.
>    This has issues around bookmark restoring, which aren't handled by my
>    patch (probably it's biggest TODO). We probably need to store tombstone
>    guids with the bookmark restore data. We also probably need to fix bugs
>    around missed bookmark restores that happen before sync is initialized. I
>    don't know for sure if this is enough or not.
>    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).
>    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).
>    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).
>    This is much more complexity, and is still imperfect (it fails if
>    there's a long enough time between when the bookmarks are modified and we
>    sync, since we won't be able to figure out the server timestamps).
>    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 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.
>    (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)
> Anyway, that's the writeup on this that I said I would do. Thoughts?
> - Thom Chiovoloni
> _______________________________________________
> Sync-dev mailing list
> Sync-dev at
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the Sync-dev mailing list