on_device_clustering_backend.cc 19 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458
  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/on_device_clustering_backend.h"
  5. #include <algorithm>
  6. #include <iterator>
  7. #include <set>
  8. #include "base/containers/flat_map.h"
  9. #include "base/i18n/case_conversion.h"
  10. #include "base/metrics/histogram_functions.h"
  11. #include "base/strings/string_util.h"
  12. #include "base/task/task_runner_util.h"
  13. #include "base/task/task_traits.h"
  14. #include "base/task/thread_pool.h"
  15. #include "base/threading/thread_task_runner_handle.h"
  16. #include "base/timer/elapsed_timer.h"
  17. #include "components/history/core/browser/history_types.h"
  18. #include "components/history_clusters/core/config.h"
  19. #include "components/history_clusters/core/content_annotations_cluster_processor.h"
  20. #include "components/history_clusters/core/content_visibility_cluster_finalizer.h"
  21. #include "components/history_clusters/core/features.h"
  22. #include "components/history_clusters/core/history_clusters_util.h"
  23. #include "components/history_clusters/core/keyword_cluster_finalizer.h"
  24. #include "components/history_clusters/core/label_cluster_finalizer.h"
  25. #include "components/history_clusters/core/metrics_cluster_finalizer.h"
  26. #include "components/history_clusters/core/noisy_cluster_finalizer.h"
  27. #include "components/history_clusters/core/on_device_clustering_features.h"
  28. #include "components/history_clusters/core/on_device_clustering_util.h"
  29. #include "components/history_clusters/core/ranking_cluster_finalizer.h"
  30. #include "components/history_clusters/core/similar_visit_deduper_cluster_finalizer.h"
  31. #include "components/history_clusters/core/single_domain_cluster_finalizer.h"
  32. #include "components/history_clusters/core/single_visit_cluster_finalizer.h"
  33. #include "components/optimization_guide/core/batch_entity_metadata_task.h"
  34. #include "components/optimization_guide/core/entity_metadata_provider.h"
  35. #include "components/optimization_guide/core/new_optimization_guide_decider.h"
  36. #include "components/site_engagement/core/site_engagement_score_provider.h"
  37. #include "components/url_formatter/url_formatter.h"
  38. namespace history_clusters {
  39. namespace {
  40. void RecordBatchUpdateProcessingTime(base::TimeDelta time_delta) {
  41. base::UmaHistogramTimes(
  42. "History.Clusters.Backend.ProcessBatchOfVisits.ThreadTime", time_delta);
  43. }
  44. } // namespace
  45. OnDeviceClusteringBackend::OnDeviceClusteringBackend(
  46. optimization_guide::EntityMetadataProvider* entity_metadata_provider,
  47. site_engagement::SiteEngagementScoreProvider* engagement_score_provider,
  48. optimization_guide::NewOptimizationGuideDecider* optimization_guide_decider,
  49. base::flat_set<std::string> mid_blocklist)
  50. : entity_metadata_provider_(entity_metadata_provider),
  51. engagement_score_provider_(engagement_score_provider),
  52. user_visible_task_traits_(
  53. {base::MayBlock(), base::TaskPriority::USER_VISIBLE}),
  54. continue_on_shutdown_user_visible_task_traits_(
  55. {base::MayBlock(), base::TaskPriority::USER_VISIBLE,
  56. base::TaskShutdownBehavior::CONTINUE_ON_SHUTDOWN}),
  57. user_visible_priority_background_task_runner_(
  58. base::ThreadPool::CreateSequencedTaskRunner(
  59. GetConfig().use_continue_on_shutdown
  60. ? continue_on_shutdown_user_visible_task_traits_
  61. : user_visible_task_traits_)),
  62. best_effort_task_traits_(
  63. {base::MayBlock(), base::TaskPriority::BEST_EFFORT}),
  64. continue_on_shutdown_best_effort_task_traits_(
  65. {base::MayBlock(), base::TaskPriority::BEST_EFFORT,
  66. base::TaskShutdownBehavior::CONTINUE_ON_SHUTDOWN}),
  67. best_effort_priority_background_task_runner_(
  68. base::ThreadPool::CreateSequencedTaskRunner(
  69. GetConfig().use_continue_on_shutdown
  70. ? continue_on_shutdown_best_effort_task_traits_
  71. : best_effort_task_traits_)),
  72. engagement_score_cache_last_refresh_timestamp_(base::TimeTicks::Now()),
  73. engagement_score_cache_(GetConfig().engagement_score_cache_size),
  74. mid_blocklist_(mid_blocklist) {
  75. if (GetConfig().should_check_hosts_to_skip_clustering_for &&
  76. optimization_guide_decider) {
  77. optimization_guide_decider_ = optimization_guide_decider;
  78. optimization_guide_decider_->RegisterOptimizationTypes(
  79. {optimization_guide::proto::HISTORY_CLUSTERS});
  80. }
  81. }
  82. OnDeviceClusteringBackend::~OnDeviceClusteringBackend() {
  83. DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
  84. }
  85. void OnDeviceClusteringBackend::GetClusters(
  86. ClusteringRequestSource clustering_request_source,
  87. ClustersCallback callback,
  88. std::vector<history::AnnotatedVisit> visits) {
  89. DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
  90. if (visits.empty()) {
  91. std::move(callback).Run({});
  92. return;
  93. }
  94. // Just start clustering without getting entity metadata if we don't have a
  95. // provider to translate the entities.
  96. if (!entity_metadata_provider_) {
  97. OnBatchEntityMetadataRetrieved(
  98. clustering_request_source, /*completed_task=*/nullptr, visits,
  99. /*entity_metadata_start=*/absl::nullopt, std::move(callback),
  100. /*entity_metadata_map=*/{});
  101. return;
  102. }
  103. base::ElapsedThreadTimer entity_id_gathering_timer;
  104. // Figure out what entity IDs we need to fetch metadata for.
  105. base::flat_set<std::string> entity_ids;
  106. for (const auto& visit : visits) {
  107. for (const auto& entity :
  108. visit.content_annotations.model_annotations.entities) {
  109. // Remove entities that are on the keyword blocklist.
  110. if (mid_blocklist_.find(entity.id) != mid_blocklist_.end()) {
  111. continue;
  112. }
  113. // Only put the entity IDs in if they exceed a certain threshold.
  114. if (entity.weight < GetConfig().entity_relevance_threshold) {
  115. continue;
  116. }
  117. entity_ids.insert(entity.id);
  118. }
  119. }
  120. base::UmaHistogramTimes(
  121. "History.Clusters.Backend.EntityIdGathering.ThreadTime",
  122. entity_id_gathering_timer.Elapsed());
  123. // Don't bother with getting entity metadata if there's nothing to get
  124. // metadata for.
  125. if (entity_ids.empty()) {
  126. OnBatchEntityMetadataRetrieved(
  127. clustering_request_source, /*completed_task=*/nullptr,
  128. std::move(visits),
  129. /*entity_metadata_start=*/absl::nullopt, std::move(callback),
  130. /*entity_metadata_map=*/{});
  131. return;
  132. }
  133. base::UmaHistogramCounts1000("History.Clusters.Backend.BatchEntityLookupSize",
  134. entity_ids.size());
  135. // Fetch the metadata for the entity ID present in |visits|.
  136. auto batch_entity_metadata_task =
  137. std::make_unique<optimization_guide::BatchEntityMetadataTask>(
  138. entity_metadata_provider_, entity_ids);
  139. auto* batch_entity_metadata_task_ptr = batch_entity_metadata_task.get();
  140. in_flight_batch_entity_metadata_tasks_.insert(
  141. std::move(batch_entity_metadata_task));
  142. batch_entity_metadata_task_ptr->Execute(
  143. base::BindOnce(&OnDeviceClusteringBackend::OnBatchEntityMetadataRetrieved,
  144. weak_ptr_factory_.GetWeakPtr(), clustering_request_source,
  145. batch_entity_metadata_task_ptr, std::move(visits),
  146. base::TimeTicks::Now(), std::move(callback)));
  147. }
  148. void OnDeviceClusteringBackend::OnBatchEntityMetadataRetrieved(
  149. ClusteringRequestSource clustering_request_source,
  150. optimization_guide::BatchEntityMetadataTask* completed_task,
  151. std::vector<history::AnnotatedVisit> annotated_visits,
  152. absl::optional<base::TimeTicks> entity_metadata_start,
  153. ClustersCallback callback,
  154. const base::flat_map<std::string, optimization_guide::EntityMetadata>&
  155. entity_metadata_map) {
  156. DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
  157. if (entity_metadata_start) {
  158. base::UmaHistogramTimes(
  159. "History.Clusters.Backend.BatchEntityLookupLatency2",
  160. base::TimeTicks::Now() - *entity_metadata_start);
  161. }
  162. if (base::TimeTicks::Now() >
  163. (engagement_score_cache_last_refresh_timestamp_ +
  164. GetConfig().engagement_score_cache_refresh_duration)) {
  165. engagement_score_cache_.Clear();
  166. engagement_score_cache_last_refresh_timestamp_ = base::TimeTicks::Now();
  167. }
  168. ProcessVisits(clustering_request_source, completed_task,
  169. std::move(annotated_visits), entity_metadata_start,
  170. std::move(callback), entity_metadata_map);
  171. }
  172. void OnDeviceClusteringBackend::ProcessVisits(
  173. ClusteringRequestSource clustering_request_source,
  174. optimization_guide::BatchEntityMetadataTask* completed_task,
  175. std::vector<history::AnnotatedVisit> annotated_visits,
  176. absl::optional<base::TimeTicks> entity_metadata_start,
  177. ClustersCallback callback,
  178. const base::flat_map<std::string, optimization_guide::EntityMetadata>&
  179. entity_metadata_map) {
  180. DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
  181. base::ElapsedThreadTimer process_batch_timer;
  182. std::vector<history::ClusterVisit> cluster_visits;
  183. base::flat_map<std::string, optimization_guide::EntityMetadata>
  184. human_readable_entity_name_to_metadata_map;
  185. for (const auto& visit : annotated_visits) {
  186. history::ClusterVisit cluster_visit;
  187. cluster_visit.annotated_visit = visit;
  188. const std::string& visit_host = visit.url_row.url().host();
  189. // Skip visits that should not be clustered.
  190. if (optimization_guide_decider_) {
  191. optimization_guide::OptimizationGuideDecision decision =
  192. optimization_guide_decider_->CanApplyOptimization(
  193. visit.url_row.url(), optimization_guide::proto::HISTORY_CLUSTERS,
  194. /*optimization_metadata=*/nullptr);
  195. if (decision != optimization_guide::OptimizationGuideDecision::kTrue) {
  196. continue;
  197. }
  198. }
  199. if (visit.content_annotations.search_normalized_url.is_empty()) {
  200. cluster_visit.normalized_url = visit.url_row.url();
  201. cluster_visit.url_for_deduping =
  202. ComputeURLForDeduping(cluster_visit.normalized_url);
  203. } else {
  204. cluster_visit.normalized_url =
  205. visit.content_annotations.search_normalized_url;
  206. // Search visits just use the `normalized_url` for deduping.
  207. cluster_visit.url_for_deduping = cluster_visit.normalized_url;
  208. }
  209. cluster_visit.url_for_display =
  210. ComputeURLForDisplay(cluster_visit.normalized_url);
  211. if (engagement_score_provider_) {
  212. auto it = engagement_score_cache_.Peek(visit_host);
  213. if (it != engagement_score_cache_.end()) {
  214. cluster_visit.engagement_score = it->second;
  215. } else {
  216. float score = engagement_score_provider_->GetScore(visit.url_row.url());
  217. engagement_score_cache_.Put(visit_host, score);
  218. cluster_visit.engagement_score = score;
  219. }
  220. }
  221. // Rewrite the entities for the visit, but only if it is possible that we
  222. // had additional metadata for it.
  223. if (entity_metadata_provider_) {
  224. cluster_visit.annotated_visit.content_annotations.model_annotations
  225. .entities.clear();
  226. cluster_visit.annotated_visit.content_annotations.model_annotations
  227. .categories.clear();
  228. base::flat_map<std::string, int> inserted_categories;
  229. for (const auto& entity :
  230. visit.content_annotations.model_annotations.entities) {
  231. auto entity_metadata_it = entity_metadata_map.find(entity.id);
  232. if (entity_metadata_it == entity_metadata_map.end() ||
  233. entity.weight < GetConfig().entity_relevance_threshold) {
  234. continue;
  235. }
  236. history::VisitContentModelAnnotations::Category rewritten_entity =
  237. entity;
  238. rewritten_entity.id = entity_metadata_it->second.human_readable_name;
  239. cluster_visit.annotated_visit.content_annotations.model_annotations
  240. .entities.push_back(rewritten_entity);
  241. human_readable_entity_name_to_metadata_map[rewritten_entity.id] =
  242. entity_metadata_it->second;
  243. for (const auto& category :
  244. entity_metadata_it->second.human_readable_categories) {
  245. auto category_it = inserted_categories.find(category.first);
  246. int category_score =
  247. static_cast<int>(category.second * entity.weight);
  248. // Just take the max category score (which is weighted by entity) as
  249. // the canonical score for the category.
  250. if (category_it == inserted_categories.end() ||
  251. category_it->second < category_score) {
  252. inserted_categories[category.first] = category_score;
  253. }
  254. }
  255. }
  256. // Only add the category to the visit if it exceeds the threshold.
  257. for (const auto& category : inserted_categories) {
  258. if (category.second > GetConfig().category_relevance_threshold) {
  259. cluster_visit.annotated_visit.content_annotations.model_annotations
  260. .categories.push_back({category.first, category.second});
  261. }
  262. }
  263. }
  264. cluster_visits.push_back(cluster_visit);
  265. }
  266. RecordBatchUpdateProcessingTime(process_batch_timer.Elapsed());
  267. OnAllVisitsFinishedProcessing(
  268. clustering_request_source, completed_task, std::move(cluster_visits),
  269. std::move(human_readable_entity_name_to_metadata_map),
  270. std::move(callback));
  271. }
  272. void OnDeviceClusteringBackend::OnAllVisitsFinishedProcessing(
  273. ClusteringRequestSource clustering_request_source,
  274. optimization_guide::BatchEntityMetadataTask* completed_task,
  275. std::vector<history::ClusterVisit> cluster_visits,
  276. base::flat_map<std::string, optimization_guide::EntityMetadata>
  277. human_readable_entity_name_to_entity_metadata_map,
  278. ClustersCallback callback) {
  279. DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
  280. // Mark the task as completed, as we are done with it and have moved
  281. // everything adequately at this point.
  282. if (completed_task) {
  283. auto it = in_flight_batch_entity_metadata_tasks_.find(completed_task);
  284. if (it != in_flight_batch_entity_metadata_tasks_.end()) {
  285. in_flight_batch_entity_metadata_tasks_.erase(it);
  286. }
  287. }
  288. // Post the actual clustering work onto the thread pool, then reply on the
  289. // calling sequence. This is to prevent UI jank.
  290. base::OnceCallback<std::vector<history::Cluster>()> clustering_callback =
  291. base::BindOnce(
  292. &OnDeviceClusteringBackend::ClusterVisitsOnBackgroundThread,
  293. clustering_request_source, engagement_score_provider_ != nullptr,
  294. std::move(cluster_visits),
  295. std::move(human_readable_entity_name_to_entity_metadata_map));
  296. switch (clustering_request_source) {
  297. case ClusteringRequestSource::kJourneysPage:
  298. user_visible_priority_background_task_runner_->PostTaskAndReplyWithResult(
  299. FROM_HERE, std::move(clustering_callback), std::move(callback));
  300. break;
  301. case ClusteringRequestSource::kKeywordCacheGeneration:
  302. best_effort_priority_background_task_runner_->PostTaskAndReplyWithResult(
  303. FROM_HERE, std::move(clustering_callback), std::move(callback));
  304. break;
  305. }
  306. }
  307. // static
  308. std::vector<history::Cluster>
  309. OnDeviceClusteringBackend::ClusterVisitsOnBackgroundThread(
  310. ClusteringRequestSource clustering_request_source,
  311. bool engagement_score_provider_is_valid,
  312. std::vector<history::ClusterVisit> visits,
  313. base::flat_map<std::string, optimization_guide::EntityMetadata>
  314. human_readable_entity_name_to_entity_metadata_map) {
  315. base::ElapsedThreadTimer cluster_visits_timer;
  316. // TODO(crbug.com/1260145): All of these objects are "stateless" between
  317. // requests for clusters. If there needs to be shared state, the entire
  318. // backend needs to be refactored to separate these objects from the UI and
  319. // background thread.
  320. std::unique_ptr<Clusterer> clusterer = std::make_unique<Clusterer>();
  321. // The cluster processors to be run.
  322. std::vector<std::unique_ptr<ClusterProcessor>> cluster_processors;
  323. // The cluster finalizers to be run.
  324. std::vector<std::unique_ptr<ClusterFinalizer>> cluster_finalizers;
  325. if (GetConfig().content_clustering_enabled) {
  326. cluster_processors.push_back(
  327. std::make_unique<ContentAnnotationsClusterProcessor>());
  328. }
  329. cluster_finalizers.push_back(
  330. std::make_unique<ContentVisibilityClusterFinalizer>());
  331. cluster_finalizers.push_back(
  332. std::make_unique<SimilarVisitDeduperClusterFinalizer>());
  333. cluster_finalizers.push_back(std::make_unique<RankingClusterFinalizer>());
  334. if (GetConfig().should_hide_single_visit_clusters_on_prominent_ui_surfaces) {
  335. cluster_finalizers.push_back(
  336. std::make_unique<SingleVisitClusterFinalizer>());
  337. }
  338. if (GetConfig().should_hide_single_domain_clusters_on_prominent_ui_surfaces) {
  339. cluster_finalizers.push_back(
  340. std::make_unique<SingleDomainClusterFinalizer>());
  341. }
  342. // Add feature to turn on/off site engagement score filter.
  343. if (engagement_score_provider_is_valid &&
  344. GetConfig().should_filter_noisy_clusters) {
  345. cluster_finalizers.push_back(std::make_unique<NoisyClusterFinalizer>());
  346. }
  347. cluster_finalizers.push_back(std::make_unique<KeywordClusterFinalizer>(
  348. human_readable_entity_name_to_entity_metadata_map));
  349. if (GetConfig().should_label_clusters) {
  350. cluster_finalizers.push_back(std::make_unique<LabelClusterFinalizer>());
  351. }
  352. if (clustering_request_source ==
  353. ClusteringRequestSource::kKeywordCacheGeneration) {
  354. // Only log metrics for whole clusters when it is a query-less state to get
  355. // a better lay of the land. We estimate this by using the request source.
  356. cluster_finalizers.push_back(std::make_unique<MetricsClusterFinalizer>());
  357. }
  358. // Group visits into clusters.
  359. std::vector<history::Cluster> clusters =
  360. clusterer->CreateInitialClustersFromVisits(&visits);
  361. // Process clusters.
  362. for (const auto& processor : cluster_processors) {
  363. clusters = processor->ProcessClusters(clusters);
  364. }
  365. // Run finalizers that dedupe and score visits within a cluster and
  366. // log several metrics about the result.
  367. std::vector<int> keyword_sizes;
  368. std::vector<int> visits_in_clusters;
  369. keyword_sizes.reserve(clusters.size());
  370. visits_in_clusters.reserve(clusters.size());
  371. for (auto& cluster : clusters) {
  372. for (const auto& finalizer : cluster_finalizers) {
  373. finalizer->FinalizeCluster(cluster);
  374. }
  375. visits_in_clusters.emplace_back(cluster.visits.size());
  376. keyword_sizes.emplace_back(cluster.keyword_to_data_map.size());
  377. }
  378. // It's a bit strange that this is essentially a `ClusterProcessor` but has
  379. // to operate after the finalizers.
  380. SortClusters(&clusters);
  381. if (!visits_in_clusters.empty()) {
  382. // We check for empty to ensure the below code doesn't crash, but
  383. // realistically this vector should never be empty.
  384. base::UmaHistogramCounts1000("History.Clusters.Backend.ClusterSize.Min",
  385. *std::min_element(visits_in_clusters.begin(),
  386. visits_in_clusters.end()));
  387. base::UmaHistogramCounts1000("History.Clusters.Backend.ClusterSize.Max",
  388. *std::max_element(visits_in_clusters.begin(),
  389. visits_in_clusters.end()));
  390. }
  391. if (!keyword_sizes.empty()) {
  392. // We check for empty to ensure the below code doesn't crash, but
  393. // realistically this vector should never be empty.
  394. base::UmaHistogramCounts100(
  395. "History.Clusters.Backend.NumKeywordsPerCluster.Min",
  396. *std::min_element(keyword_sizes.begin(), keyword_sizes.end()));
  397. base::UmaHistogramCounts100(
  398. "History.Clusters.Backend.NumKeywordsPerCluster.Max",
  399. *std::max_element(keyword_sizes.begin(), keyword_sizes.end()));
  400. }
  401. base::UmaHistogramTimes("History.Clusters.Backend.ComputeClusters.ThreadTime",
  402. cluster_visits_timer.Elapsed());
  403. return clusters;
  404. }
  405. } // namespace history_clusters