--- a/services/sync/modules/engines.js
+++ b/services/sync/modules/engines.js
@@ -2,17 +2,18 @@
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 this.EXPORTED_SYMBOLS = [
   "EngineManager",
   "Engine",
   "SyncEngine",
   "Tracker",
-  "Store"
+  "Store",
+  "Changeset"
 ];
 
 var {classes: Cc, interfaces: Ci, results: Cr, utils: Cu} = Components;
 
 Cu.import("resource://services-common/async.js");
 Cu.import("resource://gre/modules/Log.jsm");
 Cu.import("resource://services-common/observers.js");
 Cu.import("resource://services-sync/constants.js");
@@ -126,48 +127,53 @@ Tracker.prototype = {
   },
 
   unignoreID: function (id) {
     let index = this._ignored.indexOf(id);
     if (index != -1)
       this._ignored.splice(index, 1);
   },
 
+  _saveChangedID(id, when) {
+    this._log.trace(`Adding changed ID: ${id}, ${JSON.stringify(when)}`);
+    this.changedIDs[id] = when;
+    this.saveChangedIDs(this.onSavedChangedIDs);
+  },
+
   addChangedID: function (id, when) {
     if (!id) {
       this._log.warn("Attempted to add undefined ID to tracker");
       return false;
     }
 
-    if (this.ignoreAll || (id in this._ignored)) {
+    if (this.ignoreAll || this._ignored.includes(id)) {
       return false;
     }
 
     // Default to the current time in seconds if no time is provided.
     if (when == null) {
-      when = Math.floor(Date.now() / 1000);
+      when = Date.now() / 1000;
     }
 
     // Add/update the entry if we have a newer time.
     if ((this.changedIDs[id] || -Infinity) < when) {
-      this._log.trace("Adding changed ID: " + id + ", " + when);
-      this.changedIDs[id] = when;
-      this.saveChangedIDs(this.onSavedChangedIDs);
+      this._saveChangedID(id, when);
     }
 
     return true;
   },
 
   removeChangedID: function (id) {
     if (!id) {
       this._log.warn("Attempted to remove undefined ID to tracker");
       return false;
     }
-    if (this.ignoreAll || (id in this._ignored))
+    if (this.ignoreAll || this._ignored.includes(id)) {
       return false;
+    }
     if (this.changedIDs[id] != null) {
       this._log.trace("Removing changed ID " + id);
       delete this.changedIDs[id];
       this.saveChangedIDs();
     }
     return true;
   },
 
@@ -857,19 +863,18 @@ SyncEngine.prototype = {
     return parseInt(Svc.Prefs.get(this.name + ".lastSyncLocal", "0"), 10);
   },
   set lastSyncLocal(value) {
     // Store as a string because pref can only store C longs as numbers.
     Svc.Prefs.set(this.name + ".lastSyncLocal", value.toString());
   },
 
   /*
-   * Returns a mapping of IDs -> changed timestamp. Engine implementations
-   * can override this method to bypass the tracker for certain or all
-   * changed items.
+   * Returns a changeset for this sync. Engine implementations can override this
+   * method to bypass the tracker for certain or all changed items.
    */
   getChangedIDs: function () {
     return this._tracker.changedIDs;
   },
 
   // Create a new record using the store and add in crypto fields.
   _createRecord: function (id) {
     let record = this._store.createRecord(id, this.name);
@@ -927,30 +932,26 @@ SyncEngine.prototype = {
     // Save objects that need to be uploaded in this._modified. We also save
     // the timestamp of this fetch in this.lastSyncLocal. As we successfully
     // upload objects we remove them from this._modified. If an error occurs
     // or any objects fail to upload, they will remain in this._modified. At
     // the end of a sync, or after an error, we add all objects remaining in
     // this._modified to the tracker.
     this.lastSyncLocal = Date.now();
     if (this.lastSync) {
-      this._modified = this.getChangedIDs();
+      this._modified = this.pullNewChanges();
     } else {
-      // Mark all items to be uploaded, but treat them as changed from long ago
       this._log.debug("First sync, uploading all items");
-      this._modified = {};
-      for (let id in this._store.getAllIDs()) {
-        this._modified[id] = 0;
-      }
+      this._modified = this.pullAllChanges();
     }
     // Clear the tracker now. If the sync fails we'll add the ones we failed
     // to upload back.
     this._tracker.clearChangedIDs();
 
-    this._log.info(Object.keys(this._modified).length +
+    this._log.info(this._modified.count() +
                    " outgoing items pre-reconciliation");
 
     // Keep track of what to delete at the end of sync
     this._delete = {};
   },
 
   /**
    * A tiny abstraction to make it easier to test incoming record
@@ -1288,22 +1289,22 @@ SyncEngine.prototype = {
     if (this._log.level <= Log.Level.Trace) {
       this._log.trace("Incoming: " + item);
     }
 
     // We start reconciling by collecting a bunch of state. We do this here
     // because some state may change during the course of this function and we
     // need to operate on the original values.
     let existsLocally   = this._store.itemExists(item.id);
-    let locallyModified = item.id in this._modified;
+    let locallyModified = this._modified.has(item.id);
 
     // TODO Handle clock drift better. Tracked in bug 721181.
     let remoteAge = AsyncResource.serverTime - item.modified;
     let localAge  = locallyModified ?
-      (Date.now() / 1000 - this._modified[item.id]) : null;
+      (Date.now() / 1000 - this._modified.getModifiedTimestamp(item.id)) : null;
     let remoteIsNewer = remoteAge < localAge;
 
     this._log.trace("Reconciling " + item.id + ". exists=" +
                     existsLocally + "; modified=" + locallyModified +
                     "; local age=" + localAge + "; incoming age=" +
                     remoteAge);
 
     // We handle deletions first so subsequent logic doesn't have to check
@@ -1364,23 +1365,23 @@ SyncEngine.prototype = {
         // an item but doesn't expose it through itemExists. If the API
         // contract were stronger, this could be changed.
         this._log.debug("Switching local ID to incoming: " + dupeID + " -> " +
                         item.id);
         this._store.changeItemID(dupeID, item.id);
 
         // If the local item was modified, we carry its metadata forward so
         // appropriate reconciling can be performed.
-        if (dupeID in this._modified) {
+        if (this._modified.has(dupeID)) {
           locallyModified = true;
-          localAge = Date.now() / 1000 - this._modified[dupeID];
+          localAge = Date.now() / 1000 -
+            this._modified.getModifiedTimestamp(dupeID);
           remoteIsNewer = remoteAge < localAge;
 
-          this._modified[item.id] = this._modified[dupeID];
-          delete this._modified[dupeID];
+          this._modified.swap(dupeID, item.id);
         } else {
           locallyModified = false;
           localAge = null;
         }
 
         this._log.debug("Local item after duplication: age=" + localAge +
                         "; modified=" + locallyModified + "; exists=" +
                         existsLocally);
@@ -1404,17 +1405,17 @@ SyncEngine.prototype = {
       }
 
       // If the item was modified locally but isn't present, it must have
       // been deleted. If the incoming record is younger, we restore from
       // that record.
       if (remoteIsNewer) {
         this._log.trace("Applying incoming because local item was deleted " +
                         "before the incoming item was changed.");
-        delete this._modified[item.id];
+        this._modified.delete(item.id);
         return true;
       }
 
       this._log.trace("Ignoring incoming item because the local item's " +
                       "deletion is newer.");
       return false;
     }
 
@@ -1430,17 +1431,17 @@ SyncEngine.prototype = {
 
     // If the records are the same, we don't need to do anything. This does
     // potentially throw away a local modification time. But, if the records
     // are the same, does it matter?
     if (recordsEqual) {
       this._log.trace("Ignoring incoming item because the local item is " +
                       "identical.");
 
-      delete this._modified[item.id];
+      this._modified.delete(item.id);
       return false;
     }
 
     // At this point the records are different.
 
     // If we have no local modifications, always take the server record.
     if (!locallyModified) {
       this._log.trace("Applying incoming record because no local conflicts.");
@@ -1455,17 +1456,17 @@ SyncEngine.prototype = {
                    item.id);
     return remoteIsNewer;
   },
 
   // Upload outgoing records.
   _uploadOutgoing: function () {
     this._log.trace("Uploading local changes to server.");
 
-    let modifiedIDs = Object.keys(this._modified);
+    let modifiedIDs = this._modified.ids();
     if (modifiedIDs.length) {
       this._log.trace("Preparing " + modifiedIDs.length +
                       " outgoing records");
 
       let counts = { sent: modifiedIDs.length, failed: 0 };
 
       // collection we'll upload
       let up = new Collection(this.engineURL, null, this.service);
@@ -1499,17 +1500,17 @@ SyncEngine.prototype = {
           this._log.debug("Records that will be uploaded again because "
                           + "the server couldn't store them: "
                           + failed.join(", "));
         }
 
         counts.failed += failed.length;
 
         for (let id of successful) {
-          delete this._modified[id];
+          this._modified.delete(id);
         }
 
         this._onRecordsWritten(successful, failed);
 
         // clear for next batch
         failed.length = 0;
         successful.length = 0;
       };
@@ -1583,20 +1584,18 @@ SyncEngine.prototype = {
   },
 
   _syncCleanup: function () {
     if (!this._modified) {
       return;
     }
 
     // Mark failed WBOs as changed again so they are reuploaded next time.
-    for (let [id, when] of Object.entries(this._modified)) {
-      this._tracker.addChangedID(id, when);
-    }
-    this._modified = {};
+    this.trackRemainingChanges();
+    this._modified.clear();
   },
 
   _sync: function () {
     try {
       this._syncStartup();
       Observers.notify("weave:engine:sync:status", "process-incoming");
       this._processIncoming();
       Observers.notify("weave:engine:sync:status", "upload-outgoing");
@@ -1672,10 +1671,113 @@ SyncEngine.prototype = {
    *
    * All return values will be part of the kRecoveryStrategy enumeration.
    */
   handleHMACMismatch: function (item, mayRetry) {
     // By default we either try again, or bail out noisily.
     return (this.service.handleHMACEvent() && mayRetry) ?
            SyncEngine.kRecoveryStrategy.retry :
            SyncEngine.kRecoveryStrategy.error;
+  },
+
+  /**
+   * Returns a changeset containing all items in the store. The default
+   * implementation returns a changeset with timestamps from long ago, to
+   * ensure we always use the remote version if one exists.
+   *
+   * This function is only called for the first sync. Subsequent syncs call
+   * `pullNewChanges`.
+   *
+   * @return A `Changeset` object.
+   */
+  pullAllChanges() {
+    let changeset = new Changeset();
+    for (let id in this._store.getAllIDs()) {
+      changeset.set(id, 0);
+    }
+    return changeset;
+  },
+
+  /*
+   * Returns a changeset containing entries for all currently tracked items.
+   * The default implementation returns a changeset with timestamps indicating
+   * when the item was added to the tracker.
+   *
+   * @return A `Changeset` object.
+   */
+  pullNewChanges() {
+    return new Changeset(this.getChangedIDs());
+  },
+
+  /**
+   * Adds all remaining changeset entries back to the tracker, typically for
+   * items that failed to upload. This method is called at the end of each sync.
+   *
+   */
+  trackRemainingChanges() {
+    for (let [id, change] of this._modified.entries()) {
+      this._tracker.addChangedID(id, change);
+    }
+  },
+};
+
+/**
+ * A changeset is created for each sync in `Engine::get{Changed, All}IDs`,
+ * and stores opaque change data for tracked IDs. The default implementation
+ * only records timestamps, though engines can extend this to store additional
+ * data for each entry.
+ */
+class Changeset {
+  // Creates a changeset with an initial set of tracked entries.
+  constructor(changes = {}) {
+    this.changes = changes;
   }
-};
+
+  // Returns the last modified time, in seconds, for an entry in the changeset.
+  // `id` is guaranteed to be in the set.
+  getModifiedTimestamp(id) {
+    return this.changes[id];
+  }
+
+  // Adds a change for a tracked ID to the changeset.
+  set(id, change) {
+    this.changes[id] = change;
+  }
+
+  // Indicates whether an entry is in the changeset.
+  has(id) {
+    return id in this.changes;
+  }
+
+  // Deletes an entry from the changeset. Used to clean up entries for
+  // reconciled and successfully uploaded records.
+  delete(id) {
+    delete this.changes[id];
+  }
+
+  // Swaps two entries in the changeset. Used when reconciling duplicates that
+  // have local changes.
+  swap(oldID, newID) {
+    this.changes[newID] = this.changes[oldID];
+    delete this.changes[oldID];
+  }
+
+  // Returns an array of all tracked IDs in this changeset.
+  ids() {
+    return Object.keys(this.changes);
+  }
+
+  // Returns an array of `[id, change]` tuples. Used to repopulate the tracker
+  // with entries for failed uploads at the end of a sync.
+  entries() {
+    return Object.entries(this.changes);
+  }
+
+  // Returns the number of entries in this changeset.
+  count() {
+    return this.ids().length;
+  }
+
+  // Clears the changeset.
+  clear() {
+    this.changes = {};
+  }
+}

--- a/services/sync/modules/engines/bookmarks.js
+++ b/services/sync/modules/engines/bookmarks.js
@@ -28,16 +28,18 @@ const ANNOS_TO_TRACK = [BookmarkAnnos.DE
 const SERVICE_NOT_SUPPORTED = "Service not supported on this platform";
 const FOLDER_SORTINDEX = 1000000;
 const {
   SOURCE_SYNC,
   SOURCE_IMPORT,
   SOURCE_IMPORT_REPLACE,
 } = Ci.nsINavBookmarksService;
 
+const SQLITE_MAX_VARIABLE_NUMBER = 999;
+
 // Maps Sync record property names to `PlacesSyncUtils` bookmark properties.
 const RECORD_PROPS_TO_BOOKMARK_PROPS = {
   title: "title",
   bmkUri: "url",
   tags: "tags",
   keyword: "keyword",
   description: "description",
   loadInSidebar: "loadInSidebar",
@@ -421,17 +423,103 @@ BookmarksEngine.prototype = {
       this._log.trace(item.id + " already a dupe: not finding one.");
       return;
     }
     let mapped = this._mapDupe(item);
     this._log.debug(item.id + " mapped to " + mapped);
     // We must return a string, not an object, and the entries in the GUIDMap
     // are created via "new String()" making them an object.
     return mapped ? mapped.toString() : mapped;
-  }
+  },
+
+  pullAllChanges() {
+    let changeset = new BookmarksChangeset();
+    for (let id in this._store.getAllIDs()) {
+      changeset.set(id, { modified: 0, deleted: false });
+    }
+    return changeset;
+  },
+
+  pullNewChanges() {
+    let modifiedGUIDs = this._getModifiedGUIDs();
+    if (!modifiedGUIDs.length) {
+      return new BookmarksChangeset(this._tracker.changedIDs);
+    }
+
+    // We don't use `PlacesUtils.promiseDBConnection` here because
+    // `getChangedIDs` might be called while we're in a batch, meaning we
+    // won't see any changes until the batch finishes and the transaction
+    // commits.
+    let db = PlacesUtils.history.QueryInterface(Ci.nsPIPlacesDatabase)
+                        .DBConnection;
+
+    // Filter out tags, organizer queries, and other descendants that we're
+    // not tracking. We chunk `modifiedGUIDs` because SQLite limits the number
+    // of bound parameters per query.
+    for (let startIndex = 0;
+         startIndex < modifiedGUIDs.length;
+         startIndex += SQLITE_MAX_VARIABLE_NUMBER) {
+
+      let chunkLength = Math.min(startIndex + SQLITE_MAX_VARIABLE_NUMBER,
+                                 modifiedGUIDs.length);
+
+      let query = `
+        WITH RECURSIVE
+        modifiedGuids(guid) AS (
+          VALUES ${new Array(chunkLength).fill("(?)").join(", ")}
+        ),
+        syncedItems(id) AS (
+          SELECT b.id
+          FROM moz_bookmarks b
+          WHERE b.id IN (${getChangeRootIds().join(", ")})
+          UNION ALL
+          SELECT b.id
+          FROM moz_bookmarks b
+          JOIN syncedItems s ON b.parent = s.id
+        )
+        SELECT b.guid, b.id
+        FROM modifiedGuids m
+        JOIN moz_bookmarks b ON b.guid = m.guid
+        LEFT JOIN syncedItems s ON b.id = s.id
+        WHERE s.id IS NULL
+      `;
+
+      let statement = db.createAsyncStatement(query);
+      try {
+        for (let i = 0; i < chunkLength; i++) {
+          statement.bindByIndex(i, modifiedGUIDs[startIndex + i]);
+        }
+        let results = Async.querySpinningly(statement, ["id", "guid"]);
+        for (let { id, guid } of results) {
+          let syncID = BookmarkSpecialIds.specialGUIDForId(id) || guid;
+          this._tracker.removeChangedID(syncID);
+        }
+      } finally {
+        statement.finalize();
+      }
+    }
+
+    return new BookmarksChangeset(this._tracker.changedIDs);
+  },
+
+  // Returns an array of Places GUIDs for all changed items. Ignores deletions,
+  // which won't exist in the DB and shouldn't be removed from the tracker.
+  _getModifiedGUIDs() {
+    let guids = [];
+    for (let syncID in this._tracker.changedIDs) {
+      if (this._tracker.changedIDs[syncID].deleted === true) {
+        // The `===` check also filters out old persisted timestamps,
+        // which won't have a `deleted` property.
+        continue;
+      }
+      let guid = BookmarkSpecialIds.syncIDToPlacesGUID(syncID);
+      guids.push(guid);
+    }
+    return guids;
+  },
 };
 
 function BookmarksStore(name, engine) {
   Store.call(this, name, engine);
 
   // Explicitly nullify our references to our cached services so we don't leak
   Svc.Obs.add("places-shutdown", function() {
     for (let query in this._stmts) {
@@ -959,107 +1047,130 @@ BookmarksTracker.prototype = {
   },
 
   QueryInterface: XPCOMUtils.generateQI([
     Ci.nsINavBookmarkObserver,
     Ci.nsINavBookmarkObserver_MOZILLA_1_9_1_ADDITIONS,
     Ci.nsISupportsWeakReference
   ]),
 
+  addChangedID(id, change) {
+    if (!id) {
+      this._log.warn("Attempted to add undefined ID to tracker");
+      return false;
+    }
+    if (this._ignored.includes(id)) {
+      return false;
+    }
+    let shouldSaveChange = false;
+    let currentChange = this.changedIDs[id];
+    if (currentChange) {
+      if (typeof currentChange == "number") {
+        // Allow raw timestamps for backward-compatibility with persisted
+        // changed IDs. The new format uses tuples to track deleted items.
+        shouldSaveChange = currentChange < change.modified;
+      } else {
+        shouldSaveChange = currentChange.modified < change.modified ||
+                           currentChange.deleted != change.deleted;
+      }
+    } else {
+      shouldSaveChange = true;
+    }
+    if (shouldSaveChange) {
+      this._saveChangedID(id, change);
+    }
+    return true;
+  },
+
   /**
    * Add a bookmark GUID to be uploaded and bump up the sync score.
    *
-   * @param itemGuid
-   *        GUID of the bookmark to upload.
+   * @param itemId
+   *        The Places item ID of the bookmark to upload.
+   * @param guid
+   *        The Places GUID of the bookmark to upload.
+   * @param isTombstone
+   *        Whether we're uploading a tombstone for a removed bookmark.
    */
-  _add: function BMT__add(itemId, guid) {
+  _add: function BMT__add(itemId, guid, isTombstone = false) {
     guid = BookmarkSpecialIds.specialGUIDForId(itemId) || guid;
-    if (this.addChangedID(guid))
+    let info = { modified: Date.now() / 1000, deleted: isTombstone };
+    if (this.addChangedID(guid, info)) {
       this._upScore();
+    }
   },
 
   /* Every add/remove/change will trigger a sync for MULTI_DEVICE (except in
      a batch operation, where we do it at the end of the batch) */
   _upScore: function BMT__upScore() {
     if (this._batchDepth == 0) {
       this.score += SCORE_INCREMENT_XLARGE;
     } else {
       this._batchSawScoreIncrement = true;
     }
   },
 
-  /**
-   * Determine if a change should be ignored.
-   *
-   * @param itemId
-   *        Item under consideration to ignore
-   * @param folder (optional)
-   *        Folder of the item being changed
-   * @param guid
-   *        Places GUID of the item being changed
-   * @param source
-   *        A change source constant from `nsINavBookmarksService::SOURCE_*`.
-   */
-  _ignore: function BMT__ignore(itemId, folder, guid, source) {
-    if (IGNORED_SOURCES.includes(source)) {
-      return true;
-    }
-
-    // Get the folder id if we weren't given one.
-    if (folder == null) {
-      try {
-        folder = PlacesUtils.bookmarks.getFolderIdForItem(itemId);
-      } catch (ex) {
-        this._log.debug("getFolderIdForItem(" + itemId +
-                        ") threw; calling _ensureMobileQuery.");
-        // I'm guessing that gFIFI can throw, and perhaps that's why
-        // _ensureMobileQuery is here at all. Try not to call it.
-        this._ensureMobileQuery();
-        folder = PlacesUtils.bookmarks.getFolderIdForItem(itemId);
-      }
-    }
-
-    // Ignore changes to tags (folders under the tags folder).
-    let tags = BookmarkSpecialIds.tags;
-    if (folder == tags)
-      return true;
-
-    // Ignore tag items (the actual instance of a tag for a bookmark).
-    if (PlacesUtils.bookmarks.getFolderIdForItem(folder) == tags)
-      return true;
-
-    // Make sure to remove items that have the exclude annotation.
-    if (PlacesUtils.annotations.itemHasAnnotation(itemId, BookmarkAnnos.EXCLUDEBACKUP_ANNO)) {
-      this.removeChangedID(guid);
-      return true;
-    }
-
-    return false;
-  },
-
   onItemAdded: function BMT_onItemAdded(itemId, folder, index,
                                         itemType, uri, title, dateAdded,
                                         guid, parentGuid, source) {
-    if (this._ignore(itemId, folder, guid, source)) {
+    if (IGNORED_SOURCES.includes(source)) {
       return;
     }
 
     this._log.trace("onItemAdded: " + itemId);
     this._add(itemId, guid);
     this._add(folder, parentGuid);
   },
 
   onItemRemoved: function (itemId, parentId, index, type, uri,
                            guid, parentGuid, source) {
-    if (this._ignore(itemId, parentId, guid, source)) {
+    if (IGNORED_SOURCES.includes(source)) {
+      return;
+    }
+
+    // Ignore changes to tags (folders under the tags folder).
+    if (parentId == PlacesUtils.tagsFolderId) {
+      return;
+    }
+
+    let grandParentId = -1;
+    try {
+      grandParentId = PlacesUtils.bookmarks.getFolderIdForItem(parentId);
+    } catch (ex) {
+      // `getFolderIdForItem` can throw if the item no longer exists, such as
+      // when we've removed a subtree using `removeFolderChildren`.
       return;
     }
 
+    // Ignore tag items (the actual instance of a tag for a bookmark).
+    if (grandParentId == PlacesUtils.tagsFolderId) {
+      return;
+    }
+
+    /**
+     * The above checks are incomplete: we can still write tombstones for
+     * items that we don't track, and upload extraneous roots.
+     *
+     * Consider the left pane root: it's a child of the Places root, and has
+     * children and grandchildren. `PlacesUIUtils` can create, delete, and
+     * recreate it as needed. We can't determine ancestors when the root or its
+     * children are deleted, because they've already been removed from the
+     * database when `onItemRemoved` is called. Likewise, we can't check their
+     * "exclude from backup" annos, because they've *also* been removed.
+     *
+     * So, we end up writing tombstones for the left pane queries and left
+     * pane root. For good measure, we'll also upload the Places root, because
+     * it's the parent of the left pane root.
+     *
+     * As a workaround, we can track the parent GUID and reconstruct the item's
+     * ancestry at sync time. This is complicated, and the previous behavior was
+     * already wrong, so we'll wait for bug 1258127 to fix this generally.
+     */
     this._log.trace("onItemRemoved: " + itemId);
-    this._add(itemId, guid);
+    this._add(itemId, guid, /* isTombstone */ true);
     this._add(parentId, parentGuid);
   },
 
   _ensureMobileQuery: function _ensureMobileQuery() {
     let find = val =>
       PlacesUtils.annotations.getItemsWithAnnotation(BookmarkAnnos.ORGANIZERQUERY_ANNO, {}).filter(
         id => PlacesUtils.annotations.getItemAnnotation(id, BookmarkAnnos.ORGANIZERQUERY_ANNO) == val
       );
@@ -1093,39 +1204,39 @@ BookmarksTracker.prototype = {
   },
 
   // This method is oddly structured, but the idea is to return as quickly as
   // possible -- this handler gets called *every time* a bookmark changes, for
   // *each change*.
   onItemChanged: function BMT_onItemChanged(itemId, property, isAnno, value,
                                             lastModified, itemType, parentId,
                                             guid, parentGuid, source) {
+    if (IGNORED_SOURCES.includes(source)) {
+      return;
+    }
+
     if (isAnno && (ANNOS_TO_TRACK.indexOf(property) == -1))
       // Ignore annotations except for the ones that we sync.
       return;
 
     // Ignore favicon changes to avoid unnecessary churn.
     if (property == "favicon")
       return;
 
-    if (this._ignore(itemId, parentId, guid, source)) {
-      return;
-    }
-
     this._log.trace("onItemChanged: " + itemId +
                     (", " + property + (isAnno? " (anno)" : "")) +
                     (value ? (" = \"" + value + "\"") : ""));
     this._add(itemId, guid);
   },
 
   onItemMoved: function BMT_onItemMoved(itemId, oldParent, oldIndex,
                                         newParent, newIndex, itemType,
                                         guid, oldParentGuid, newParentGuid,
                                         source) {
-    if (this._ignore(itemId, newParent, guid, source)) {
+    if (IGNORED_SOURCES.includes(source)) {
       return;
     }
 
     this._log.trace("onItemMoved: " + itemId);
     this._add(oldParent, oldParentGuid);
     if (oldParent != newParent) {
       this._add(itemId, guid);
       this._add(newParent, newParentGuid);
@@ -1141,8 +1252,31 @@ BookmarksTracker.prototype = {
   onEndUpdateBatch: function () {
     if (--this._batchDepth === 0 && this._batchSawScoreIncrement) {
       this.score += SCORE_INCREMENT_XLARGE;
       this._batchSawScoreIncrement = false;
     }
   },
   onItemVisited: function () {}
 };
+
+// Returns an array of root IDs to recursively query for synced bookmarks.
+// Items in other roots, including tags and organizer queries, will be
+// ignored.
+function getChangeRootIds() {
+  let rootIds = [
+    PlacesUtils.bookmarksMenuFolderId,
+    PlacesUtils.toolbarFolderId,
+    PlacesUtils.unfiledBookmarksFolderId,
+  ];
+  let mobileRootId = BookmarkSpecialIds.findMobileRoot(false);
+  if (mobileRootId) {
+    rootIds.push(mobileRootId);
+  }
+  return rootIds;
+}
+
+class BookmarksChangeset extends Changeset {
+  getModifiedTimestamp(id) {
+    let change = this.changes[id];
+    return change ? change.modified : Number.NaN;
+  }
+}

--- a/services/sync/modules/engines/clients.js
+++ b/services/sync/modules/engines/clients.js
@@ -306,17 +306,17 @@ ClientEngine.prototype = {
     }
   },
 
   _uploadOutgoing() {
     this._currentlySyncingCommands = this._prepareCommandsForUpload();
     const clientWithPendingCommands = Object.keys(this._currentlySyncingCommands);
     for (let clientId of clientWithPendingCommands) {
       if (this._store._remoteClients[clientId] || this.localID == clientId) {
-        this._modified[clientId] = 0;
+        this._modified.set(clientId, 0);
       }
     }
     SyncEngine.prototype._uploadOutgoing.call(this);
   },
 
   _onRecordsWritten(succeeded, failed) {
     // Reconcile the status of the local records with what we just wrote on the
     // server

--- a/services/sync/tests/unit/test_bookmark_tracker.js
+++ b/services/sync/tests/unit/test_bookmark_tracker.js
@@ -17,18 +17,19 @@ var tracker = engine._tracker;
 
 store.wipe();
 tracker.persistChangedIDs = false;
 
 const DAY_IN_MS = 24 * 60 * 60 * 1000;
 
 // Test helpers.
 function* verifyTrackerEmpty() {
-  do_check_empty(tracker.changedIDs);
-  do_check_eq(tracker.score, 0);
+  let changes = engine.pullNewChanges();
+  equal(changes.count(), 0);
+  equal(tracker.score, 0);
 }
 
 function* resetTracker() {
   tracker.clearChangedIDs();
   tracker.resetScore();
 }
 
 function* cleanup() {
@@ -43,27 +44,31 @@ function* startTracking() {
   Svc.Obs.notify("weave:engine:start-tracking");
 }
 
 function* stopTracking() {
   Svc.Obs.notify("weave:engine:stop-tracking");
 }
 
 function* verifyTrackedItems(tracked) {
-  let trackedIDs = new Set(Object.keys(tracker.changedIDs));
+  let changes = engine.pullNewChanges();
+  let trackedIDs = new Set(changes.ids());
   for (let guid of tracked) {
-    ok(tracker.changedIDs[guid] > 0, `${guid} should be tracked`);
+    ok(changes.has(guid), `${guid} should be tracked`);
+    ok(changes.getModifiedTimestamp(guid) > 0,
+      `${guid} should have a modified time`);
     trackedIDs.delete(guid);
   }
   equal(trackedIDs.size, 0, `Unhandled tracked IDs: ${
     JSON.stringify(Array.from(trackedIDs))}`);
 }
 
 function* verifyTrackedCount(expected) {
-  do_check_attribute_count(tracker.changedIDs, expected);
+  let changes = engine.pullNewChanges();
+  equal(changes.count(), expected);
 }
 
 add_task(function* test_tracking() {
   _("Test starting and stopping the tracker");
 
   let folder = PlacesUtils.bookmarks.createFolder(
     PlacesUtils.bookmarks.bookmarksMenuFolder,
     "Test Folder", PlacesUtils.bookmarks.DEFAULT_INDEX);
@@ -384,17 +389,17 @@ add_task(function* test_onItemTagged() {
 
     yield startTracking();
 
     _("Tag the item");
     PlacesUtils.tagging.tagURI(uri, ["foo"]);
 
     // bookmark should be tracked, folder should not be.
     yield verifyTrackedItems([bGUID]);
-    do_check_eq(tracker.score, SCORE_INCREMENT_XLARGE);
+    do_check_eq(tracker.score, SCORE_INCREMENT_XLARGE * 5);
   } finally {
     _("Clean up.");
     yield cleanup();
   }
 });
 
 add_task(function* test_onItemUntagged() {
   _("Items untagged using the synchronous API should be tracked");
@@ -517,17 +522,17 @@ add_task(function* test_async_onItemTagg
     _("Tag an item using the async bookmarks API");
     yield PlacesUtils.bookmarks.insert({
       type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
       parentGuid: tag.guid,
       url: "http://getfirefox.com",
     });
 
     yield verifyTrackedItems([fxBmk1.guid, fxBmk2.guid]);
-    do_check_eq(tracker.score, SCORE_INCREMENT_XLARGE * 2);
+    do_check_eq(tracker.score, SCORE_INCREMENT_XLARGE * 6);
   } finally {
     _("Clean up.");
     yield cleanup();
   }
 });
 
 add_task(function* test_onItemKeywordChanged() {
   _("Keyword changes via the synchronous API should be tracked");
@@ -695,41 +700,83 @@ add_task(function* test_onItemAnnoChange
     yield verifyTrackedItems([bGUID]);
     do_check_eq(tracker.score, SCORE_INCREMENT_XLARGE);
   } finally {
     _("Clean up.");
     yield cleanup();
   }
 });
 
-add_task(function* test_onItemExcluded() {
-  _("Items excluded from backups should not be tracked");
+add_task(function* test_onItemAdded_filtered_root() {
+  _("Items outside the change roots should not be tracked");
+
+  try {
+    yield startTracking();
+
+    _("Create a new root");
+    let rootID = PlacesUtils.bookmarks.createFolder(
+      PlacesUtils.bookmarks.placesRoot,
+      "New root",
+      PlacesUtils.bookmarks.DEFAULT_INDEX);
+    let rootGUID = engine._store.GUIDForId(rootID);
+    _(`New root GUID: ${rootGUID}`);
+
+    _("Insert a bookmark underneath the new root");
+    let untrackedBmkID = PlacesUtils.bookmarks.insertBookmark(
+      rootID,
+      Utils.makeURI("http://getthunderbird.com"),
+      PlacesUtils.bookmarks.DEFAULT_INDEX,
+      "Get Thunderbird!");
+    let untrackedBmkGUID = engine._store.GUIDForId(untrackedBmkID);
+    _(`New untracked bookmark GUID: ${untrackedBmkGUID}`);
+
+    _("Insert a bookmark underneath the Places root");
+    let rootBmkID = PlacesUtils.bookmarks.insertBookmark(
+      PlacesUtils.bookmarks.placesRoot,
+      Utils.makeURI("http://getfirefox.com"),
+      PlacesUtils.bookmarks.DEFAULT_INDEX, "Get Firefox!");
+    let rootBmkGUID = engine._store.GUIDForId(rootBmkID);
+    _(`New Places root bookmark GUID: ${rootBmkGUID}`);
+
+    _("New root and bookmark should be ignored");
+    yield verifyTrackedItems([]);
+    // ...But we'll still increment the score and filter out the changes at
+    // sync time.
+    do_check_eq(tracker.score, SCORE_INCREMENT_XLARGE * 6);
+  } finally {
+    _("Clean up.");
+    yield cleanup();
+  }
+});
+
+add_task(function* test_onItemDeleted_filtered_root() {
+  _("Deleted items outside the change roots should be tracked");
 
   try {
     yield stopTracking();
 
-    _("Create a bookmark");
-    let b = PlacesUtils.bookmarks.insertBookmark(
-      PlacesUtils.bookmarks.bookmarksMenuFolder,
+    _("Insert a bookmark underneath the Places root");
+    let rootBmkID = PlacesUtils.bookmarks.insertBookmark(
+      PlacesUtils.bookmarks.placesRoot,
       Utils.makeURI("http://getfirefox.com"),
       PlacesUtils.bookmarks.DEFAULT_INDEX, "Get Firefox!");
-    let bGUID = engine._store.GUIDForId(b);
+    let rootBmkGUID = engine._store.GUIDForId(rootBmkID);
+    _(`New Places root bookmark GUID: ${rootBmkGUID}`);
 
     yield startTracking();
 
-    _("Exclude the bookmark from backups");
-    PlacesUtils.annotations.setItemAnnotation(
-      b, BookmarkAnnos.EXCLUDEBACKUP_ANNO, "Don't back this up", 0,
-      PlacesUtils.annotations.EXPIRE_NEVER);
+    PlacesUtils.bookmarks.removeItem(rootBmkID);
 
-    _("Modify the bookmark");
-    PlacesUtils.bookmarks.setItemTitle(b, "Download Firefox");
-
-    _("Excluded items should be ignored");
-    yield verifyTrackerEmpty();
+    // We shouldn't upload tombstones for items in filtered roots, but the
+    // `onItemRemoved` observer doesn't have enough context to determine
+    // the root, so we'll end up uploading it.
+    yield verifyTrackedItems([rootBmkGUID]);
+    // We'll increment the counter twice (once for the removed item, and once
+    // for the Places root), then filter out the root.
+    do_check_eq(tracker.score, SCORE_INCREMENT_XLARGE * 2);
   } finally {
     _("Clean up.");
     yield cleanup();
   }
 });
 
 add_task(function* test_onPageAnnoChanged() {
   _("Page annotations should not be tracked");
@@ -1249,32 +1296,53 @@ add_task(function* test_async_onItemDele
     });
     _(`Mozilla GUID: ${mozBmk.guid}`);
     let mdnBmk = yield PlacesUtils.bookmarks.insert({
       type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
       parentGuid: PlacesUtils.bookmarks.menuGuid,
       url: "https://developer.mozilla.org",
       title: "MDN",
     });
+    _(`MDN GUID: ${mdnBmk.guid}`);
     let bugsFolder = yield PlacesUtils.bookmarks.insert({
       type: PlacesUtils.bookmarks.TYPE_FOLDER,
       parentGuid: PlacesUtils.bookmarks.toolbarGuid,
       title: "Bugs",
     });
+    _(`Bugs folder GUID: ${bugsFolder.guid}`);
     let bzBmk = yield PlacesUtils.bookmarks.insert({
       type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
       parentGuid: bugsFolder.guid,
       url: "https://bugzilla.mozilla.org",
       title: "Bugzilla",
     });
+    _(`Bugzilla GUID: ${bzBmk.guid}`);
+    let bugsChildFolder = yield PlacesUtils.bookmarks.insert({
+      type: PlacesUtils.bookmarks.TYPE_FOLDER,
+      parentGuid: bugsFolder.guid,
+      title: "Bugs child",
+    });
+    _(`Bugs child GUID: ${bugsChildFolder.guid}`);
+    let bugsGrandChildBmk = yield PlacesUtils.bookmarks.insert({
+      type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+      parentGuid: bugsChildFolder.guid,
+      url: "https://example.com",
+      title: "Bugs grandchild",
+    });
+    _(`Bugs grandchild GUID: ${bugsGrandChildBmk.guid}`);
 
     yield startTracking();
 
     yield PlacesUtils.bookmarks.eraseEverything();
 
+    // `eraseEverything` removes all items from the database before notifying
+    // observers. Because of this, grandchild lookup in the tracker's
+    // `onItemRemoved` observer will fail. That means we won't track
+    // (bzBmk.guid, bugsGrandChildBmk.guid, bugsChildFolder.guid), even
+    // though we should.
     yield verifyTrackedItems(["menu", mozBmk.guid, mdnBmk.guid, "toolbar",
                               bugsFolder.guid]);
     do_check_eq(tracker.score, SCORE_INCREMENT_XLARGE * 6);
   } finally {
     _("Clean up.");
     yield cleanup();
   }
 });