1303825 - Track whether bookmarks are syncable in Places

Status: RESOLVED WONTFIX

(Toolkit :: Places, defect)

Description

[Lina Butler [:lina]]

This is mainly useful for Sync, but it has implications for other Places methods, too.

Sync currently filters out bookmarks based on the root. We only consider bookmarks under "menu________", "toolbar_____", "unfiled_____", and mobile; others ("tags________", left pane queries, and the Places root itself) are ignored.

I think it makes sense to store the root alongside the item for two reasons:

* Bug 1258127 adds a `moz_bookmarks_deleted` table to track tombstones for deleted synced bookmarks. Right now, we have to use a recursive query to find the root, then check if we need to write a tombstone. Storing the root means we could get rid of the query and simplify the check to `deletedBookmark.syncStatus != SYNC_STATUS_NEW && IsRootSyncable(deletedBookmark.rootGuid)`. Insertions should also be easy: since we fetch the parent before inserting, we just use the parent's root.

* In bug 1303679, we're discussing what happens if a bookmark or folder is moved from a synced root to an unsynced root. (Say, from the left pane root to unfiled, or from tags to toolbar). In theory, this is impossible in the UI, and doesn't even make sense...but it is allowed. In bug 1303679, comment 3, Richard points out that the only way to keep this sound is to disallow moves between synced and unsynced roots. If we stored the root for each item, the check would be a cheap `aOldRootGuid.Equals(aNewRootGuid) || (IsRootSyncable(aOldRootGuid) && IsRootSyncable(aNewRootGuid))`.

Comment 1

[Marco Bonardo [:mak]]

Off-hand, I don't like the idea.
You are moving the burden from reads (fast) to writes (slow). Any bookmarks move will have to ensure to set the root correctly or bad things may happen.
The other problem is that it will add more textual data to each entry, increasing the db size, text is unefficiently stored, integers is better.
The final problem is that one day you may need to know the 2 or 3 levels up ancestor, and stop before the root. And then you must again revert to recursive. So this is only partially workarounding the problem that is: "I need all the ancestors of a node".

These costs must balance the benefit, that is to avoid a recursive query. Since very often the users don't go further than 2 levels, so it should not be that bad, and it's a read. So it doesn't sound well balanced.

There are other ways to achieve even better results, see bug 408991. With a nested tree we could very easily get all ancestors and descendants of a node. The links there are broken, but you can find some interesting insight (and a third method) here:
http://stackoverflow.com/questions/192220/what-is-the-most-efficient-elegant-way-to-parse-a-flat-table-into-a-tree/192462#192462
This would generally be useful to a bunch of Places code, not just Sync. On the other side, disaster recovery is more complex than with an adjacency tree representation, so it needs good testing and some time to implement properly.
Personally, rather than spending resources on adding a string column to bookmarks, I'd prefer spending them on a new related table containing either a nested tree or a closure representation of bookmarks. Then you can get very easily any ancestor or descendant. And we can reuse it.

(In reply to Kit Cambridge [:kitcambridge] from comment #0)
> * In bug 1303679, we're discussing what happens if a bookmark or folder is
> moved from a synced root to an unsynced root. (Say, from the left pane root
> to unfiled, or from tags to toolbar).

What's the "real" use-case? The example doesn't fit, nothing can move from the left pane root to something else and nothing should.

In theory, this is impossible in the
> UI, and doesn't even make sense...but it is allowed.

And I'd not object to completely throw away the db and rebuild it, if the user does that on purpose through other ways. Can we just throw away those moved bookmarks and forget about them?

Comment 2

[Lina Butler [:lina]]

Thanks, Mak, this is useful feedback!

(In reply to Marco Bonardo [::mak] from comment #1)
> Off-hand, I don't like the idea.
> You are moving the burden from reads (fast) to writes (slow). Any bookmarks
> move will have to ensure to set the root correctly or bad things may happen.

I suspect we're going to need to do this anyway for Sync, so that we don't end up creating divergent trees (see bug 1303679, comment 3). Some other alternatives:

* We implement your suggestion and rebuild the DB if the user moves an item between the syncable and non-syncable parts of a tree. When would be a good time to do that? I don't think it's something PlacesDBUtils could do, because we don't want to sync bad changes to other devices until the next time it runs. Would we rebuild right at Sync time? Stop syncing and rebuild on the next startup?

* We add another sync status flag (SYNC_STATUS_IGNORED), then use a recursive query for each move to check if we're moving between synced and non-synced subtrees. Alternatively, we could special-case SYNC_STATUS_IGNORED so that it's inherited from parent to child, and maybe avoid the query then. That seems like a lot of effort for a case that the UI doesn't (again, AFAIK) even allow you to do.

> The other problem is that it will add more textual data to each entry,
> increasing the db size, text is unefficiently stored, integers is better.

Good to know! I think an integer ID would work just as well.

> The final problem is that one day you may need to know the 2 or 3 levels up
> ancestor, and stop before the root. And then you must again revert to
> recursive. So this is only partially workarounding the problem that is: "I
> need all the ancestors of a node".

Makes sense, but I'm not interested in all the ancestors; just the root.

> These costs must balance the benefit, that is to avoid a recursive query.
> Since very often the users don't go further than 2 levels, so it should not
> be that bad, and it's a read. So it doesn't sound well balanced.

OK, that makes sense. This would be a recursive query executed for every move and delete, which seems like it could get expensive. I can measure and see, but didn't want to do too much implementation work before discussing.

> There are other ways to achieve even better results, see bug 408991. With a
> nested tree we could very easily get all ancestors and descendants of a
> node. The links there are broken, but you can find some interesting insight
> (and a third method) here:
> http://stackoverflow.com/questions/192220/what-is-the-most-efficient-elegant-
> way-to-parse-a-flat-table-into-a-tree/192462#192462
> This would generally be useful to a bunch of Places code, not just Sync. On
> the other side, disaster recovery is more complex than with an adjacency
> tree representation, so it needs good testing and some time to implement
> properly.
> Personally, rather than spending resources on adding a string column to
> bookmarks, I'd prefer spending them on a new related table containing either
> a nested tree or a closure representation of bookmarks. Then you can get
> very easily any ancestor or descendant. And we can reuse it.

That's very interesting reading. Thank you for the pointers!

> (In reply to Kit Cambridge [:kitcambridge] from comment #0)
> > * In bug 1303679, we're discussing what happens if a bookmark or folder is
> > moved from a synced root to an unsynced root. (Say, from the left pane root
> > to unfiled, or from tags to toolbar).
> 
> What's the "real" use-case? The example doesn't fit, nothing can move from
> the left pane root to something else and nothing should.

I think our concerns (bug 1303679, comment 3) are mostly theoretical at this point. The general problem we're trying to solve is, "Sync should only upload records that belong to one of those four roots." But we also don't want to upload partial trees, because its conflict resolution will do the wrong thing.

Comment 3

[Marco Bonardo [:mak]]

(In reply to Kit Cambridge [:kitcambridge] from comment #2)
> I think our concerns (bug 1303679, comment 3) are mostly theoretical at this
> point. The general problem we're trying to solve is, "Sync should only
> upload records that belong to one of those four roots." But we also don't
> want to upload partial trees, because its conflict resolution will do the
> wrong thing.

My question is, if you walk the tree hierarchically, starting from the 4 roots, how do you end up looking into things that are in the other roots? shouldn't those just be nonexistant for your walking code? if something suddenly appears that you don't know, shouldn't you just consider it a newly added bookmark?

Comment 4

[Lina Butler [:lina]]

(In reply to Marco Bonardo [::mak] from comment #3)
> (In reply to Kit Cambridge [:kitcambridge] from comment #2)
> > I think our concerns (bug 1303679, comment 3) are mostly theoretical at this
> > point. The general problem we're trying to solve is, "Sync should only
> > upload records that belong to one of those four roots." But we also don't
> > want to upload partial trees, because its conflict resolution will do the
> > wrong thing.
> 
> My question is, if you walk the tree hierarchically, starting from the 4
> roots, how do you end up looking into things that are in the other roots?
> shouldn't those just be nonexistant for your walking code?

They should, yes. But consider this tree:

    let trackedFolder = yield PlacesUtils.bookmarks.insert({
      type: PlacesUtils.bookmarks.TYPE_FOLDER,
      parentGuid: PlacesUtils.bookmarks.toolbarGuid,
      title: "Folder created by user; should be synced",
    });
    let trackedBookmark = yield PlacesUtils.bookmarks.insert({
      type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
      parentGuid: trackedFolder.guid,
      title: "Bookmark created by user; should also be synced",
      url: "https://example.com",
    });
    let untrackedRoot = yield PlacesUtils.bookmarks.insert({
      type: PlacesUtils.bookmarks.TYPE_FOLDER,
      parentGuid: PlacesUtils.bookmarks.rootGuid,
      title: "Some root created by an add-on; should be ignored by sync",
    });
    let untrackedFolder = yield PlacesUtils.bookmarks.insert({
      type: PlacesUtils.bookmarks.TYPE_FOLDER,
      parentGuid: untrackedRoot.guid,
      title: "A folder not tracked by Sync because its root is ignored",
    });
    let untrackedBookmark = yield PlacesUtils.bookmarks.insert({
      type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
      parentGuid: untrackedFolder.guid,
      title: "Another bookmark; should be ignored because its root is ignored",
      url: "https://mozilla.com",
    })

Let's say I have a Sync account with two devices.

Now, what happens if I move trackedFolder into untrackedRoot on my desktop?

* Toolbar gets a sync change, because we moved one of its children to another folder.
* But trackedFolder is now in an untracked root, so it's not uploaded to the server and becomes an orphan.
* My second device still has trackedFolder as a child of toolbar...because it didn't see my desktop's move to an untracked folder.
* If I add more bookmarks to trackedFolder on my desktop, they won't make it to my laptop. But, if I add them on my laptop (which still thinks it's in the toolbar), then Sync will upload an incomplete record for that folder.

Let's go the other way. What happens if I move untrackedFolder into the toolbar on my desktop?

* Toolbar gets a sync change, because we added a child.
* untrackedFolder also gets a sync change, because we moved it to the toolbar.
* untrackedBookmark *doesn't* get a change, because we don't bump the change counter for children of moved folders. (Since we'd then need to reupload all descendants, recursively, for every move). Now untrackedBookmark is orphaned on my desktop.

One possibility is to say, "don't do that." It's definitely an edge case, but one that can easily cause divergence and data loss.  Richard's suggestion to keep this sane is to prevent moves between synced and unsynced subtrees, so trying to move trackedFolder into untrackedRoot (or untrackedFolder to the toolbar) would throw. Nothing in Places today guarantees or enforces this, because Places doesn't know about Sync.

Comment 5

[Lina Butler [:lina]]

Another idea: instead of overloading "syncStatus" to be sometimes inherited, and sometimes not, we add a boolean (integer, really) "syncable" column. Unlike "syncStatus", this one would always be inherited, from parent to child.

Exception: the Places root would be syncable = 0, since we don't want to sync other roots...but toolbar, menu, unfiled, and mobile would be syncable = 1, and so would their children.

* It's a more direct answer to the question, "should this item be synced?" (instead of "what's the root of this item?", where we only care about the root for sync eligibility). Conceptually, it's simpler.
* It would let us get rid of the recursive query and filtering based on the root: `SELECT guid FROM moz_bookmarks WHERE syncable = 1` would return all synced bookmarks. `SELECT guid FROM moz_bookmarks WHERE syncable = 1 AND syncChangeCounter > 0` would return everything that's changed since the last sync.
* It makes for a cheap tombstone check: if `deletedBookmark.syncable` is true, write one; if not, don't. (We can also ditch the `rootGuid` column for the tombstones table in bug 1258127).
* It makes it easy to enforce keeping syncable and non-syncable subtrees separate: if `oldParent.syncable != newParent.syncable`, throw.

Comment 6

[Lina Butler [:lina]]

Attachment: Bug 1303825 - Track whether bookmarks are syncable in Places. f?mak

Review commit: https://reviewboard.mozilla.org/r/79876/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/79876/

Comment 7

[Lina Butler [:lina]]

Comment on attachment 8793093 [details]
Bug 1303825 - Track whether bookmarks are syncable in Places. f?mak

This is how an inherited syncable flag looks. WDYT?

Comment 8

[Lina Butler [:lina]]

Comment on attachment 8793093 [details]
Bug 1303825 - Track whether bookmarks are syncable in Places. f?mak

Mark and I talked a bit about this, and this patch doesn't really do anything useful.

It does prevent us from moving between synced and unsynced roots, but that's already impossible in the Desktop UI. An add-on could do this, but it can also just write custom queries. At that point, all bets are off.

It also doesn't really help with filtering out *incoming* items that shouldn't be applied. Either we know its root already, or we reparent to unfiled and figure out the root later.

Clearing f? for now.

Comment 9

[Lina Butler [:lina]]

This is handled in the tracker rewrite; doesn't make sense to split this out per comment 8.