             return succeed()
         }
 
+        func loadCache() -> Success {
+            return history.invalidateTopSitesIfNeeded().bind { result in
+                XCTAssertTrue(result, "Invalidate should be successful")
+                return succeed()
+            }
+        }
+
         func checkTopSitesReturnsResults() -> Success {
             return history.getTopSitesWithLimit(20) >>== { topSites in
                 XCTAssertEqual(topSites.count, 20)
-                XCTAssertNotNil(prefs.timestampForKey(PrefsKeys.KeyLastFrecencyCacheTime))
-                XCTAssertEqual(topSites[0]!.guid, "abc\(500)def")
-                return succeed()
-            }
-        }
-
-        func addAdditionalVisits() -> Success {
-            let site = Site(url: "http://s\(19)ite\(19)/foo", title: "A \(19)")
-            site.guid = "abc\(19)def"
-
+                XCTAssertEqual(topSites[0]!.guid, "abc\(5)def")
+                return succeed()
+            }
+        }
+
+        func invalidateIfNeededDoesntChangeResults() -> Success {
+            return history.invalidateTopSitesIfNeeded().bind { result in
+                return history.getTopSitesWithLimit(20) >>== { topSites in
+                    XCTAssertEqual(topSites.count, 20)
+                    XCTAssertEqual(topSites[0]!.guid, "abc\(5)def")
+                    return succeed()
+                }
+            }
+        }
+
+        func addVisitsToZerothSite() -> Success {
+            let site = Site(url: "http://s\(0)ite\(0)/foo", title: "A \(0)")
+            site.guid = "abc\(0)def"
             for i in 0...20 {
-                let local = SiteVisit(site: site, date: Timestamp(1000 * (1437088398461 + (1000 * i))), type: VisitType.Link)
-                XCTAssertTrue(history.addLocalVisit(local).value.isSuccess)
-            }
-
-            // Set timestamp to something really old to force invalidation
-            prefs.setTimestamp(0, forKey: PrefsKeys.KeyLastFrecencyCacheTime)
+                addVisitForSite(site, intoHistory: history, from: .Local, atTime: Timestamp(1439088398461 + (1000 * i)))
+            }
             return succeed()
         }
 
-        func checkTopOfTopSitesChanged() -> Success {
+        func markInvalidation() -> Success {
+            history.setTopSitesNeedsInvalidation()
+            return succeed()
+        }
+
+        func checkSitesInvalidate() -> Success {
+            history.invalidateTopSitesIfNeeded().value
+
             return history.getTopSitesWithLimit(20) >>== { topSites in
                 XCTAssertEqual(topSites.count, 20)
-                XCTAssertEqual(topSites[0]!.guid, "abc\(19)def")
-                return succeed()
-            }
-        }
-
-        checkTopSitesReturnsResults()
-            >>> addAdditionalVisits
-            >>> checkTopOfTopSitesChanged
+                XCTAssertEqual(topSites[0]!.guid, "abc\(0)def")
+                return succeed()
+            }
+        }
+
+        loadCache()
+            >>> checkTopSitesReturnsResults
+            >>> invalidateIfNeededDoesntChangeResults
+            >>> markInvalidation
+            >>> addVisitsToZerothSite
+            >>> checkSitesInvalidate
             >>> done
 
         waitForExpectationsWithTimeout(10.0) { error in

        let prefs = MockProfilePrefs()
        let history = SQLiteHistory(db: db, prefs: prefs)!

        // Make sure that we get back the top sites
        XCTAssertNil(prefs.timestampForKey(PrefsKeys.KeyLastFrecencyCacheTime))
        populateHistoryForFrecencyCalcuations(history, siteCount: 100)

        let expectation = self.expectationWithDescription("First.")
        func done() -> Success {

        history.clearHistory().value
        populateHistoryForFrecencyCalcuations(history, siteCount: count)

        history.setTopSitesNeedsInvalidation()
        self.measureMetrics([XCTPerformanceMetric_WallClockTime], automaticallyStartMeasuring: true) {
            history.invalidateTopSitesIfNeeded().value
            self.stopMeasuring()
        }
    }
}

// MARK - Private Test Helper Methods

private enum VisitOrigin {
    case Local
    case Remote
}

private func populateHistoryForFrecencyCalcuations(history: SQLiteHistory, siteCount count: Int) {
