1141850 - Implement synchronization for structured cross-device records (bookmarks)

Status: RESOLVED FIXED

(Firefox for iOS :: Sync, defect)

Description

[Richard Newman [:rnewman]]

Basically this means "bookmarks". These records are unique in that they normally cannot be independently added to, modified, or deleted; even deleting or reordering a leaf bookmark requires modifying its parent record and atomically applying that change. Moves require modifying three records. And so on.

This is a complication in two areas of iOS Sync:

1. Our judgment about when the server mirror can be applied -- that is, our assessment of whether it is *complete* (fully downloaded) and *consistent* (=> fully uploaded by another client) becomes important and non-trivial.

2. Record reconciling is a structural operation. Desktop uses a computed map for this; it would be unwise to follow the same approach.

The difficulty of correctly handling local changes here is enough motivation that we might use a replayable transaction log to limit the possibility of hard-to-resolve conflicts.

I intend to solve this problem last, and very likely in stages of limited scope (e.g., read-only server bookmarks, unsorted list of local bookmarks that are easy to reconcile).

Decisions elsewhere have made that kind of decomposition difficult -- e.g., desktop's "Unsorted bookmarks" aren't unsorted and can contain folders! -- but we'll do the best we can.

Comment 1

[Richard Newman [:rnewman]]

First gist:

https://gist.github.com/rnewman/f95720050df3d5515351

Comment 2

[Richard Newman [:rnewman]]

Here's the raw work stream. Careful, it's big. It works, and it has tests.

https://github.com/mozilla/firefox-ios/compare/rnewman/bm-merge-review?expand=1

I'm flattening this into a more manageable (hah!) set of commits in a separate branch; that's the PR I'll submit for review.

Comment 3

[Richard Newman [:rnewman]]

My existing to-do list:

* Make sure we set a parentName when inserting new bookmarks. This isn't ordinarily an issue, because we'll override the stored parentName when it's a special folder.
* Multi-part upload timestamps are utterly wrong: every uploaded record gets the timestamp of the last part. This is non-trivial.
* We batch uploads in chunks of 50. Often this is too small, and sometimes it's too large. We should use size-based upload.
* Outgoing invalid records -- that is, serialization failures into BookmarkBasePayload -- don't seem to abort the sync. Quietly dropping those records on the floor is wrong.
* Don't try a merge if the mirrorer aborts.
* Test multi-depth folder deletion.
* Test moving between roots.
* Implement true three-way merge for values, and see if there's anything more we can do for folders.
* In a value-based reconcile lookup, do we/should we limit the search to New local items?
* My logs tell me that we sometimes prefetch duplicates in the same request (A, A, B, B). Why?
* Make sure that prefetching never does redundant work.
* Make sure we prefetch as much as we might need.
* Check code for TODOs.
* Make sure we have all the indices we need.

Comment 4

[Richard Newman [:rnewman]]

Attachment: Pull req.

Believe it or not, this is the flattened one.

Comment 5

[Richard Newman [:rnewman]]

(In reply to Richard Newman [:rnewman] from comment #3)

> * Multi-part upload timestamps are utterly wrong: every uploaded record gets
> the timestamp of the last part. This is non-trivial.

Consequence: should be none of note, but it makes me uneasy, so we should fix it.


> * We batch uploads in chunks of 50. Often this is too small, and sometimes
> it's too large. We should use size-based upload.

Consequence: uploading a very large record, or a certain combination of large records, will cause the upload to fail and your bookmarks to never sync. That's not good.


> * Outgoing invalid records -- that is, serialization failures into
> BookmarkBasePayload -- don't seem to abort the sync. Quietly dropping those
> records on the floor is wrong.

Consequence: potential missing records on the server, propagating inconsistency. Not good.


Most of the others are improvements or perf. These I'd want to fix before shipping.

Comment 6

[Richard Newman [:rnewman]]

(In reply to Richard Newman [:rnewman] from comment #3)
> My existing to-do list:

One more:

* Handling detected wipes and storage format changes in BookmarksDownloader.

Comment 7

[Richard Newman [:rnewman]]

> * Multi-part upload timestamps are utterly wrong: every uploaded record gets
> the timestamp of the last part. This is non-trivial.

Done (but not tested; I'm on a plane) in Part 7. We accrue timestamps directly into the local completion op, and can replay them into the mirror once the uploads are done.

Comment 8

[Richard Newman [:rnewman]]

Performance: download + merge + upload on ~1600 bookmarks takes 9 seconds on my 6S.

Download alone takes 5 seconds. In this case about 300msec went on upload. I'm happy with that.

I expect a fair amount of the time goes to logging, which we can ramp down over time.

Comment 9

[Emily Toop (:fluffyemily)]

Attachment: Logs.zip

I'm sorry, but this doesn't seem to work for me.

First I just deployed this version overriding my existing dev version that had no account attached at that time. added my account and waited for sync (which took a really tiny amount of time). I did not see either my dekstop bookmarks or see my mobile bookmarks on desktop. I also did not see my history synced over.

I then deleted my app and tried from a fresh install. This is the log I'm attaching here. I added 3 sites to my bookmarks (bbc.co.uk, slashdot.org & theguardian.co.uk), then connected my FxA. Again, after a super quick sync time, I see my synced tabs, but no desktop history or bookmarks synced over.

Comment 10

[Nick Alexander :nalexander [he/him]]

Comment on attachment 8721110 [details] [review]
Pull req.

As a reviewer I tend to review such that I can address issues that may arise.  In this case, I don't think that's possible -- it's rnewman in the next two months, and after that nobody.

Comment 11

[Richard Newman [:rnewman]]

(In reply to Emily Toop (:fluffyemily) from comment #9)

> I then deleted my app and tried from a fresh install. This is the log I'm
> attaching here. I added 3 sites to my bookmarks (bbc.co.uk, slashdot.org &
> theguardian.co.uk), then connected my FxA. Again, after a super quick sync
> time, I see my synced tabs, but no desktop history or bookmarks synced over.

It synced (in 600msec!), but your bookmarks weren't consistent.

13:39:19.141 [BookmarksDownloader.swift:93] go(_:greenLight:) > Downloading up to 100 records.
13:39:19.142 [Downloader.swift:127] go(_:limit:) > Modified: 1455796035270; last 0.
13:39:19.143 [Downloader.swift:152] downloadNextBatchWithLimit(_:infoModified:) > Fetching newer=0, offset=nil.
13:39:19.145 [StorageClient.swift:699] getSince(_:sort:limit:offset:) > Issuing GET with newer = 0.
13:39:19.497 [StorageClient.swift:330] failFromResponse > Status code: 200.
13:39:19.670 [Downloader.swift:170] handleSuccess > Handling success.
13:39:19.673 [Downloader.swift:204] handleSuccess > Got success response with Optional(83) records.
13:39:19.674 [BookmarksDownloader.swift:102] go(_:greenLight:) > Done with batched mirroring.
13:39:19.701 [BookmarksDownloader.swift:83] applyRecordsFromBatcher() > Applying 83 downloaded bookmarks.
13:39:19.740 [SQLiteBookmarksSyncing.swift:469] applyRecords(_:withMaxVars:) > 9 folders and 15 deleted maybe-folders to drop from buffer structure table.
13:39:19.740 [SQLiteBookmarksSyncing.swift:344] deleteStructureForGUIDs(_:fromTable:connection:withMaxVars:) > Deleting 24 parents from bookmarksBufferStructure.
13:39:19.741 [SQLiteBookmarksSyncing.swift:477] applyRecords(_:withMaxVars:) > Inserting 62 children.
13:39:19.742 [SQLiteBookmarksSyncing.swift:372] insertStructureIntoTable(_:connection:children:maxVars:) > Inserting 62 records (out of 62).
13:39:19.753 [Downloader.swift:187] handleSuccess > Advancing baseTimestamp to 1455796035270 - 1
13:39:19.755 [Downloader.swift:199] handleSuccess > Advancing lastModified to Optional(1455796035270) ?? 1455796035270.
13:39:19.757 [BrowserDB.swift:287] checkpoint() > Checkpointing a BrowserDB.
13:39:19.757 [SwiftData.swift:531] checkpoint > Running WAL checkpoint on /private/var/mobile/Containers/Shared/AppGroup/AFDA9BA5-C0A9-4EFA-8A3E-DE82F9B7FBEA/profile.profile/browser.db on thread <NSThread: 0x14865e5a0>{number = 10, name = (null)}.
13:39:19.758 [SwiftData.swift:533] checkpoint > WAL checkpoint done on /private/var/mobile/Containers/Shared/AppGroup/AFDA9BA5-C0A9-4EFA-8A3E-DE82F9B7FBEA/profile.profile/browser.db.
13:39:19.781 [ThreeWayTreeMerger.swift:994] produceMergedTree() > Remote bookmarks not fully rooted when overlayed on mirror. Partial read or write in buffer?
13:39:19.782 [BookmarksSynchronizer.swift:124] synchronizeBookmarksToStorage(_:usingBuffer:withServer:info:greenLight:) > Bookmark sync took 644118µs.



But fallback mode behaves correctly:

<fluffyemily> rnewman: you'll be happy to know that once that crasher is removed, my bookmarks behave as expected (in fallback readonly mode)

Comment 12

[Richard Newman [:rnewman]]

09b923a

Comment 13

[Brian Nicholson (:bnicholson)]

Comment on attachment 8721110 [details] [review]
Pull req.

Only reviewed (or more accurately, skimmed) 1/3rd of the PR, but finally tried syncing my account and it works flawlessly. Excellent job!