history_clusters_service.cc 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427
  1. // Copyright 2021 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #include "components/history_clusters/core/history_clusters_service.h"
  5. #include <algorithm>
  6. #include <memory>
  7. #include <string>
  8. #include <utility>
  9. #include "base/bind.h"
  10. #include "base/containers/flat_map.h"
  11. #include "base/i18n/case_conversion.h"
  12. #include "base/metrics/histogram_functions.h"
  13. #include "base/strings/utf_string_conversions.h"
  14. #include "base/system/sys_info.h"
  15. #include "base/time/time.h"
  16. #include "base/time/time_to_iso8601.h"
  17. #include "base/timer/elapsed_timer.h"
  18. #include "base/timer/timer.h"
  19. #include "components/history/core/browser/history_backend.h"
  20. #include "components/history/core/browser/history_database.h"
  21. #include "components/history/core/browser/history_db_task.h"
  22. #include "components/history/core/browser/history_types.h"
  23. #include "components/history_clusters/core/config.h"
  24. #include "components/history_clusters/core/history_clusters_debug_jsons.h"
  25. #include "components/history_clusters/core/history_clusters_types.h"
  26. #include "components/history_clusters/core/history_clusters_util.h"
  27. #include "components/history_clusters/core/on_device_clustering_backend.h"
  28. #include "components/optimization_guide/core/entity_metadata_provider.h"
  29. #include "components/optimization_guide/core/new_optimization_guide_decider.h"
  30. #include "components/site_engagement/core/site_engagement_score_provider.h"
  31. namespace history_clusters {
  32. VisitDeletionObserver::VisitDeletionObserver(
  33. HistoryClustersService* history_clusters_service)
  34. : history_clusters_service_(history_clusters_service) {}
  35. VisitDeletionObserver::~VisitDeletionObserver() = default;
  36. void VisitDeletionObserver::AttachToHistoryService(
  37. history::HistoryService* history_service) {
  38. DCHECK(history_service);
  39. history_service_observation_.Observe(history_service);
  40. }
  41. void VisitDeletionObserver::OnURLsDeleted(
  42. history::HistoryService* history_service,
  43. const history::DeletionInfo& deletion_info) {
  44. history_clusters_service_->ClearKeywordCache();
  45. }
  46. HistoryClustersService::HistoryClustersService(
  47. const std::string& application_locale,
  48. history::HistoryService* history_service,
  49. optimization_guide::EntityMetadataProvider* entity_metadata_provider,
  50. scoped_refptr<network::SharedURLLoaderFactory> url_loader_factory,
  51. site_engagement::SiteEngagementScoreProvider* engagement_score_provider,
  52. optimization_guide::NewOptimizationGuideDecider* optimization_guide_decider)
  53. : is_journeys_enabled_(
  54. GetConfig().is_journeys_enabled_no_locale_check &&
  55. IsApplicationLocaleSupportedByJourneys(application_locale)),
  56. history_service_(history_service),
  57. visit_deletion_observer_(this) {
  58. DCHECK(history_service_);
  59. visit_deletion_observer_.AttachToHistoryService(history_service);
  60. backend_ = std::make_unique<OnDeviceClusteringBackend>(
  61. entity_metadata_provider, engagement_score_provider,
  62. optimization_guide_decider, JourneysMidBlocklist());
  63. RepeatedlyUpdateClusters();
  64. }
  65. HistoryClustersService::~HistoryClustersService() = default;
  66. base::WeakPtr<HistoryClustersService> HistoryClustersService::GetWeakPtr() {
  67. return weak_ptr_factory_.GetWeakPtr();
  68. }
  69. void HistoryClustersService::Shutdown() {}
  70. bool HistoryClustersService::IsJourneysEnabled() const {
  71. return is_journeys_enabled_;
  72. }
  73. void HistoryClustersService::AddObserver(Observer* obs) {
  74. observers_.AddObserver(obs);
  75. }
  76. void HistoryClustersService::RemoveObserver(Observer* obs) {
  77. observers_.RemoveObserver(obs);
  78. }
  79. bool HistoryClustersService::ShouldNotifyDebugMessage() const {
  80. return !observers_.empty();
  81. }
  82. void HistoryClustersService::NotifyDebugMessage(
  83. const std::string& message) const {
  84. for (Observer& obs : observers_) {
  85. obs.OnDebugMessage(message);
  86. }
  87. }
  88. IncompleteVisitContextAnnotations&
  89. HistoryClustersService::GetIncompleteVisitContextAnnotations(int64_t nav_id) {
  90. DCHECK(HasIncompleteVisitContextAnnotations(nav_id));
  91. return GetOrCreateIncompleteVisitContextAnnotations(nav_id);
  92. }
  93. IncompleteVisitContextAnnotations&
  94. HistoryClustersService::GetOrCreateIncompleteVisitContextAnnotations(
  95. int64_t nav_id) {
  96. return incomplete_visit_context_annotations_[nav_id];
  97. }
  98. bool HistoryClustersService::HasIncompleteVisitContextAnnotations(
  99. int64_t nav_id) {
  100. return incomplete_visit_context_annotations_.count(nav_id);
  101. }
  102. void HistoryClustersService::CompleteVisitContextAnnotationsIfReady(
  103. int64_t nav_id) {
  104. auto& visit_context_annotations =
  105. GetIncompleteVisitContextAnnotations(nav_id);
  106. DCHECK((visit_context_annotations.status.history_rows &&
  107. visit_context_annotations.status.navigation_ended) ||
  108. !visit_context_annotations.status.navigation_end_signals);
  109. DCHECK(visit_context_annotations.status.expect_ukm_page_end_signals ||
  110. !visit_context_annotations.status.ukm_page_end_signals);
  111. if (visit_context_annotations.status.history_rows &&
  112. visit_context_annotations.status.navigation_end_signals &&
  113. (visit_context_annotations.status.ukm_page_end_signals ||
  114. !visit_context_annotations.status.expect_ukm_page_end_signals)) {
  115. // If the main Journeys feature is enabled, we want to persist visits.
  116. // And if the persist-only switch is enabled, we also want to persist them.
  117. if (IsJourneysEnabled() ||
  118. GetConfig().persist_context_annotations_in_history_db) {
  119. history_service_->SetOnCloseContextAnnotationsForVisit(
  120. visit_context_annotations.visit_row.visit_id,
  121. visit_context_annotations.context_annotations);
  122. }
  123. incomplete_visit_context_annotations_.erase(nav_id);
  124. }
  125. }
  126. std::unique_ptr<HistoryClustersServiceTaskGetMostRecentClusters>
  127. HistoryClustersService::QueryClusters(
  128. ClusteringRequestSource clustering_request_source,
  129. base::Time begin_time,
  130. QueryClustersContinuationParams continuation_params,
  131. bool recluster,
  132. QueryClustersCallback callback) {
  133. if (ShouldNotifyDebugMessage()) {
  134. NotifyDebugMessage("HistoryClustersService::QueryClusters()");
  135. NotifyDebugMessage(
  136. " begin_time = " +
  137. (begin_time.is_null() ? "null" : base::TimeToISO8601(begin_time)));
  138. NotifyDebugMessage(
  139. " end_time = " +
  140. (continuation_params.continuation_time.is_null()
  141. ? "null"
  142. : base::TimeToISO8601(continuation_params.continuation_time)));
  143. }
  144. DCHECK(history_service_);
  145. return std::make_unique<HistoryClustersServiceTaskGetMostRecentClusters>(
  146. weak_ptr_factory_.GetWeakPtr(), incomplete_visit_context_annotations_,
  147. backend_.get(), history_service_, clustering_request_source, begin_time,
  148. continuation_params, recluster, std::move(callback));
  149. }
  150. void HistoryClustersService::RepeatedlyUpdateClusters() {
  151. if (!GetConfig().persist_clusters_in_history_db)
  152. return;
  153. // Update clusters, both periodically and once after startup because:
  154. // 1) To avoid having very stale (up to 90 days) clusters for the initial
  155. // period after startup.
  156. // 2) Likewise, to avoid having very stale keywords.
  157. // 3) Some users might not keep chrome running for the period.
  158. update_clusters_after_startup_delay_timer_.Start(
  159. FROM_HERE,
  160. base::Minutes(
  161. GetConfig()
  162. .persist_clusters_in_history_db_after_startup_delay_minutes),
  163. this, &HistoryClustersService::UpdateClusters);
  164. update_clusters_period_timer_.Start(
  165. FROM_HERE,
  166. base::Minutes(GetConfig().persist_clusters_in_history_db_period_minutes),
  167. this, &HistoryClustersService::UpdateClusters);
  168. }
  169. void HistoryClustersService::UpdateClusters() {
  170. DCHECK(history_service_);
  171. if (update_clusters_task_ && !update_clusters_task_->Done())
  172. return;
  173. update_clusters_task_ =
  174. std::make_unique<HistoryClustersServiceTaskUpdateClusters>(
  175. incomplete_visit_context_annotations_, backend_.get(),
  176. history_service_, base::DoNothing());
  177. }
  178. absl::optional<history::ClusterKeywordData>
  179. HistoryClustersService::DoesQueryMatchAnyCluster(const std::string& query) {
  180. if (!IsJourneysEnabled())
  181. return absl::nullopt;
  182. // We don't want any omnibox jank for low-end devices.
  183. if (base::SysInfo::IsLowEndDevice())
  184. return absl::nullopt;
  185. StartKeywordCacheRefresh();
  186. // Early exit for single-character queries, even if it's an exact match.
  187. // We still want to allow for two-character exact matches like "uk".
  188. if (query.length() <= 1)
  189. return absl::nullopt;
  190. auto query_lower = base::i18n::ToLower(base::UTF8ToUTF16(query));
  191. auto short_it = short_keyword_cache_.find(query_lower);
  192. if (short_it != short_keyword_cache_.end()) {
  193. return short_it->second;
  194. }
  195. auto it = all_keywords_cache_.find(query_lower);
  196. if (it != all_keywords_cache_.end()) {
  197. return it->second;
  198. }
  199. return absl::nullopt;
  200. }
  201. bool HistoryClustersService::DoesURLMatchAnyCluster(
  202. const std::string& url_keyword) {
  203. if (!IsJourneysEnabled())
  204. return false;
  205. // We don't want any omnibox jank for low-end devices.
  206. if (base::SysInfo::IsLowEndDevice())
  207. return false;
  208. StartKeywordCacheRefresh();
  209. return short_url_keywords_cache_.find(url_keyword) !=
  210. short_url_keywords_cache_.end() ||
  211. all_url_keywords_cache_.find(url_keyword) !=
  212. all_url_keywords_cache_.end();
  213. }
  214. void HistoryClustersService::ClearKeywordCache() {
  215. all_keywords_cache_timestamp_ = base::Time();
  216. short_keyword_cache_timestamp_ = base::Time();
  217. all_keywords_cache_.clear();
  218. all_url_keywords_cache_.clear();
  219. short_keyword_cache_.clear();
  220. short_keyword_cache_.clear();
  221. cache_keyword_query_task_.reset();
  222. }
  223. void HistoryClustersService::StartKeywordCacheRefresh() {
  224. // If `all_keywords_cache_` is older than 2 hours, update it with the keywords
  225. // of all clusters. Otherwise, update `short_keyword_cache_` with the
  226. // keywords of only the clusters not represented in all_keywords_cache_.
  227. // Don't make new queries if there's a pending query.
  228. if (cache_keyword_query_task_ && !cache_keyword_query_task_->Done())
  229. return;
  230. // 2 hour threshold chosen arbitrarily for cache refresh time.
  231. if ((base::Time::Now() - all_keywords_cache_timestamp_) > base::Hours(2)) {
  232. // Update the timestamp right away, to prevent this from running again.
  233. // (The cache_query_task_tracker_ should also do this.)
  234. all_keywords_cache_timestamp_ = base::Time::Now();
  235. NotifyDebugMessage("Starting all_keywords_cache_ generation.");
  236. cache_keyword_query_task_ = QueryClusters(
  237. ClusteringRequestSource::kKeywordCacheGeneration,
  238. /*begin_time=*/base::Time(),
  239. /*continuation_params=*/{}, false,
  240. base::BindOnce(&HistoryClustersService::PopulateClusterKeywordCache,
  241. weak_ptr_factory_.GetWeakPtr(), base::ElapsedTimer(),
  242. /*begin_time=*/base::Time(),
  243. std::make_unique<KeywordMap>(),
  244. std::make_unique<URLKeywordSet>(), &all_keywords_cache_,
  245. &all_url_keywords_cache_));
  246. } else if ((base::Time::Now() - all_keywords_cache_timestamp_).InSeconds() >
  247. 10 &&
  248. (base::Time::Now() - short_keyword_cache_timestamp_).InSeconds() >
  249. 10) {
  250. // Update the timestamp right away, to prevent this from running again.
  251. short_keyword_cache_timestamp_ = base::Time::Now();
  252. NotifyDebugMessage("Starting short_keywords_cache_ generation.");
  253. cache_keyword_query_task_ = QueryClusters(
  254. ClusteringRequestSource::kKeywordCacheGeneration,
  255. /*begin_time=*/all_keywords_cache_timestamp_,
  256. /*continuation_params=*/{}, false,
  257. base::BindOnce(&HistoryClustersService::PopulateClusterKeywordCache,
  258. weak_ptr_factory_.GetWeakPtr(), base::ElapsedTimer(),
  259. all_keywords_cache_timestamp_,
  260. std::make_unique<KeywordMap>(),
  261. std::make_unique<URLKeywordSet>(), &short_keyword_cache_,
  262. &short_url_keywords_cache_));
  263. }
  264. }
  265. void HistoryClustersService::PopulateClusterKeywordCache(
  266. base::ElapsedTimer total_latency_timer,
  267. base::Time begin_time,
  268. std::unique_ptr<KeywordMap> keyword_accumulator,
  269. std::unique_ptr<URLKeywordSet> url_keyword_accumulator,
  270. KeywordMap* cache,
  271. URLKeywordSet* url_cache,
  272. std::vector<history::Cluster> clusters,
  273. QueryClustersContinuationParams continuation_params) {
  274. base::ElapsedThreadTimer populate_keywords_thread_timer;
  275. const size_t max_keyword_phrases = GetConfig().max_keyword_phrases;
  276. // Copy keywords from every cluster into the accumulator set.
  277. for (auto& cluster : clusters) {
  278. if (!cluster.should_show_on_prominent_ui_surfaces) {
  279. // `clusters` doesn't have any post-processing, so we need to skip
  280. // sensitive clusters here.
  281. continue;
  282. }
  283. if (cluster.visits.size() < 2) {
  284. // Only accept keywords from clusters with at least two visits. This is a
  285. // simple first-pass technique to avoid overtriggering the omnibox action.
  286. continue;
  287. }
  288. // Lowercase the keywords for case insensitive matching while adding to the
  289. // accumulator.
  290. // Keep the keyword data with the highest score if found in multiple
  291. // clusters.
  292. if (keyword_accumulator->size() < max_keyword_phrases) {
  293. for (const auto& keyword_data_p : cluster.keyword_to_data_map) {
  294. auto keyword = base::i18n::ToLower(keyword_data_p.first);
  295. auto it = keyword_accumulator->find(keyword);
  296. if (it == keyword_accumulator->end()) {
  297. keyword_accumulator->insert(
  298. std::make_pair(keyword, keyword_data_p.second));
  299. } else if (it->second.score < keyword_data_p.second.score) {
  300. // Update keyword data to the one with a higher score.
  301. it->second = keyword_data_p.second;
  302. }
  303. }
  304. }
  305. // Push a simplified form of the URL for each visit into the cache.
  306. if (url_keyword_accumulator->size() < max_keyword_phrases) {
  307. for (const auto& visit : cluster.visits) {
  308. if (visit.engagement_score >
  309. GetConfig().noisy_cluster_visits_engagement_threshold &&
  310. !GetConfig().omnibox_action_on_noisy_urls) {
  311. // Do not add a noisy visit to the URL keyword accumulator if not
  312. // enabled via flag. Note that this is at the visit-level rather than
  313. // at the cluster-level, which is handled by the NoisyClusterFinalizer
  314. // in the ClusteringBackend.
  315. continue;
  316. }
  317. url_keyword_accumulator->insert(
  318. (!visit.annotated_visit.content_annotations.search_normalized_url
  319. .is_empty())
  320. ? visit.normalized_url.spec()
  321. : ComputeURLKeywordForLookup(visit.normalized_url));
  322. }
  323. }
  324. }
  325. // Make a continuation request to get the next page of clusters and their
  326. // keywords only if both 1) there is more clusters remaining, and 2) we
  327. // haven't reached the soft cap `max_keyword_phrases` (or there is no cap).
  328. constexpr char kKeywordCacheThreadTimeUmaName[] =
  329. "History.Clusters.KeywordCache.ThreadTime";
  330. if (!continuation_params.exhausted_all_visits &&
  331. (keyword_accumulator->size() < max_keyword_phrases ||
  332. url_keyword_accumulator->size() < max_keyword_phrases)) {
  333. cache_keyword_query_task_ = QueryClusters(
  334. ClusteringRequestSource::kKeywordCacheGeneration, begin_time,
  335. continuation_params, /*recluster=*/false,
  336. base::BindOnce(&HistoryClustersService::PopulateClusterKeywordCache,
  337. weak_ptr_factory_.GetWeakPtr(),
  338. std::move(total_latency_timer), begin_time,
  339. // Pass on the accumulator sets to the next callback.
  340. std::move(keyword_accumulator),
  341. std::move(url_keyword_accumulator), cache, url_cache));
  342. // Log this even if we go back for more clusters.
  343. base::UmaHistogramTimes(kKeywordCacheThreadTimeUmaName,
  344. populate_keywords_thread_timer.Elapsed());
  345. return;
  346. }
  347. // We've got all the keywords now. Move them all into the flat_set at once
  348. // via the constructor for efficiency (as recommended by the flat_set docs).
  349. // De-duplication is handled by the flat_set itself.
  350. *cache = std::move(*keyword_accumulator);
  351. *url_cache = std::move(*url_keyword_accumulator);
  352. if (ShouldNotifyDebugMessage()) {
  353. NotifyDebugMessage("Cache construction complete; keyword cache:");
  354. NotifyDebugMessage(GetDebugJSONForKeywordMap(*cache));
  355. NotifyDebugMessage("Url cache:");
  356. NotifyDebugMessage(GetDebugJSONForUrlKeywordSet(*url_cache));
  357. }
  358. // Record keyword phrase & keyword counts for the appropriate cache.
  359. if (cache == &all_keywords_cache_) {
  360. base::UmaHistogramCounts100000(
  361. "History.Clusters.Backend.KeywordCache.AllKeywordsCount",
  362. static_cast<int>(cache->size()));
  363. } else {
  364. base::UmaHistogramCounts100000(
  365. "History.Clusters.Backend.KeywordCache.ShortKeywordsCount",
  366. static_cast<int>(cache->size()));
  367. }
  368. base::UmaHistogramTimes(kKeywordCacheThreadTimeUmaName,
  369. populate_keywords_thread_timer.Elapsed());
  370. base::UmaHistogramMediumTimes("History.Clusters.KeywordCache.Latency",
  371. total_latency_timer.Elapsed());
  372. }
  373. } // namespace history_clusters