Skip to content

web search done right

20.5 KB
Raw Blame
// Stract is an open source web search engine.
// Copyright (C) 2023 Stract ApS
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License as
// published by the Free Software Foundation, either version 3 of the
// License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Affero General Public License for more details.
//
// You should have received a copy of the GNU Affero General Public License
// along with this program.  If not, see <https://www.gnu.org/licenses/>.

use anyhow::{anyhow, Result};
use futures::stream::FuturesOrdered;
use futures::StreamExt;
use indicatif::ProgressIterator;
use itertools::Itertools;
use rayon::{prelude::*, ThreadPoolBuilder};
use std::cmp::Reverse;
use std::collections::{BTreeMap, HashMap, HashSet};
use std::hash::Hash;
use std::sync::Arc;
use std::{
    path::Path,
    sync::{atomic::AtomicUsize, Mutex},
};
use url::Url;

use crate::crawler::WeightedUrl;
use crate::distributed::cluster::Cluster;
use crate::external_sort::ExternalSorter;
use crate::log_group::HarmonicRankGroup;
use crate::webgraph::query::Id2NodeQuery;
use crate::webgraph::remote::RemoteWebgraph;
use crate::webgraph::Node;
use crate::webpage::url_ext::UrlExt;
use crate::SortableFloat;
use crate::{
    config::CrawlPlannerConfig,
    crawler::{file_queue::FileQueueWriter, Job},
    webgraph::NodeID,
};

use super::Domain;

const MAX_UNCOMMITTED_INSERTS_PER_GROUP: usize = 50_000;
const NUM_GROUPS: usize = 1024;
const CONCURRENCY_LIMIT: usize = 32;

#[derive(bincode::Encode, bincode::Decode, Clone, Debug, PartialEq, Eq, Hash)]
struct StoredUrl(#[bincode(with_serde)] Url);

impl StoredUrl {
    pub fn icann_domain(&self) -> Option<&str> {
        self.0.icann_domain()
    }
}

impl From<Url> for StoredUrl {
    fn from(url: Url) -> Self {
        Self(url)
    }
}

impl From<StoredUrl> for Url {
    fn from(url: StoredUrl) -> Self {
        url.0
    }
}

/// Store urls in groups on disk based on their harmonic rank.
struct UrlGrouper {
    groups: Vec<speedy_kv::Db<StoredUrl, ()>>,
    folder: std::path::PathBuf,
    harmonic_group: Arc<HarmonicRankGroup>,
    harmonic_rank: Arc<speedy_kv::Db<NodeID, u64>>,
}

impl UrlGrouper {
    pub fn new<P>(
        output_path: P,
        num_groups: usize,
        harmonic_group: Arc<HarmonicRankGroup>,
        harmonic_rank: Arc<speedy_kv::Db<NodeID, u64>>,
    ) -> Self
    where
        P: AsRef<std::path::Path>,
    {
        let folder = output_path.as_ref().join("groups").to_path_buf();

        Self {
            groups: (0..num_groups)
                .map(|g| {
                    speedy_kv::Db::open_or_create(folder.as_path().join(format!("{g}"))).unwrap()
                })
                .collect(),
            folder,
            harmonic_group,
            harmonic_rank,
        }
    }

    fn group(&mut self, url: &StoredUrl) -> usize {
        let domain = url.icann_domain().unwrap_or_default();

        let Ok(domain_url) = Url::parse(domain) else {
            return self.groups.len() - 1;
        };

        let id = Node::from(domain_url).id();

        match self.harmonic_rank.get(&id) {
            Ok(Some(rank)) => {
                let group = self.harmonic_group.group(rank) as usize;
                if group >= self.groups.len() {
                    self.groups.len() - 1
                } else {
                    group
                }
            }
            Ok(None) => self.groups.len() - 1,
            Err(_) => self.groups.len() - 1,
        }
    }

    pub fn insert(&mut self, url: Url) {
        let url = StoredUrl::from(url);
        let group = self.group(&url);
        let group = &mut self.groups[group];
        group.insert(url, ()).unwrap();

        if group.uncommitted_inserts() > MAX_UNCOMMITTED_INSERTS_PER_GROUP {
            group.commit().unwrap();
        }
    }

    pub fn into_groups(mut self) -> Vec<speedy_kv::Db<StoredUrl, ()>> {
        for group in &mut self.groups {
            group.commit().unwrap();
        }

        self.groups
    }
}

impl std::fmt::Debug for UrlGrouper {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("UrlGrouper")
            .field("num_groups", &self.groups.len())
            .field("folder", &self.folder)
            .finish()
    }
}

fn sorted_centralities(
    it: impl Iterator<Item = (NodeID, f64)>,
) -> impl Iterator<Item = (NodeID, f64)> {
    ExternalSorter::new()
        .with_chunk_size(100_000_000)
        .sort(it.map(|(node_id, centrality)| (Reverse(SortableFloat(centrality)), node_id)))
        .unwrap()
        .map(|(Reverse(SortableFloat(centrality)), node_id)| (node_id, centrality))
}

#[derive(Debug, Clone)]
struct Budget {
    remaining_schedulable: u64,
}

/// Create a crawl plan based on the harmonic rank of the hosts.
pub struct CrawlPlanner {
    host_centrality: Arc<speedy_kv::Db<NodeID, f64>>,
    host_centrality_rank: Arc<speedy_kv::Db<NodeID, u64>>,
    page_centrality: Arc<speedy_kv::Db<NodeID, f64>>,
    webgraph: RemoteWebgraph,
    config: CrawlPlannerConfig,

    harmonic_group: Arc<HarmonicRankGroup>,

    excluded_domains: HashSet<Domain>,

    domain_boosts: HashMap<Domain, f64>,
}

impl CrawlPlanner {
    pub async fn new(
        host_centrality: speedy_kv::Db<NodeID, f64>,
        host_centrality_rank: speedy_kv::Db<NodeID, u64>,
        page_centrality: speedy_kv::Db<NodeID, f64>,
        cluster: Arc<Cluster>,
        config: CrawlPlannerConfig,
    ) -> Result<Self> {
        Self::check_config(&config)?;

        let webgraph = RemoteWebgraph::new(cluster.clone()).await;
        webgraph.await_ready().await;

        let domain_boosts = config
            .domain_boosts
            .clone()
            .unwrap_or_default()
            .into_iter()
            .map(|domain_boost| (Domain(domain_boost.domain), domain_boost.boost))
            .collect();

        Ok(Self {
            host_centrality: Arc::new(host_centrality),
            page_centrality: Arc::new(page_centrality),
            webgraph,
            domain_boosts,
            excluded_domains: config
                .excluded_domains
                .clone()
                .unwrap_or_default()
                .into_iter()
                .map(Domain)
                .collect(),
            harmonic_group: Arc::new(HarmonicRankGroup::new(
                host_centrality_rank.len() as u64,
                NUM_GROUPS as u64,
            )),
            host_centrality_rank: Arc::new(host_centrality_rank),
            config,
        })
    }

    fn check_config(config: &CrawlPlannerConfig) -> Result<()> {
        if !(0.0..=1.0).contains(&config.wander_fraction) {
            return Err(anyhow::anyhow!(
                "top_host_fraction must be in range [0.0, 1.0]"
            ));
        }

        Ok(())
    }

    fn prepare_job(
        &self,
        domain: Domain,
        pages: Vec<Url>,
        wander_budget: f64,
        total_host_centralities: f64,
    ) -> (Job, DomainStats) {
        let hosts = pages
            .iter()
            .map(|url| Node::from(url).into_host())
            .unique()
            .collect::<Vec<_>>();

        let host_centrality: f64 = hosts
            .iter()
            .map(|host| host.id())
            .map(|id| self.host_centrality.get(&id).unwrap().unwrap_or_default())
            .sum();

        let wander_budget = ((wander_budget * host_centrality) / total_host_centralities).max(1.0);

        let boost = *self.domain_boosts.get(&domain).unwrap_or(&1.0);
        let wander_budget = boost * wander_budget;
        let wander_budget = wander_budget.round() as u64;

        let mut urls: Vec<_> = pages
            .into_iter()
            .chain(
                hosts
                    .into_iter()
                    .filter_map(|host| Url::parse(&format!("https://{}", host.as_str())).ok()),
            )
            .unique()
            .map(|url| WeightedUrl {
                url: url.clone(),
                weight: self
                    .page_centrality
                    .get(&Node::from(url).id())
                    .unwrap()
                    .unwrap_or_default(),
            })
            .collect();

        urls.sort_by(|a, b| a.weight.total_cmp(&b.weight));
        urls.reverse();

        let job = Job {
            domain: domain.clone(),
            urls: urls.into_iter().collect(),
            wandering_urls: wander_budget,
        };

        let domain_stats = DomainStats {
            domain,
            num_hosts: job
                .urls
                .iter()
                .map(|url| url.url.host_str())
                .unique()
                .count(),
            scheduled_urls: job.urls.len() as u64,
            wander_budget,
        };

        (job, domain_stats)
    }

    fn assign_budgets(&self) -> BTreeMap<NodeID, Budget> {
        let total_crawl_budget = self.config.crawl_budget as f64;
        let num_hosts = self.host_centrality.len();
        let num_hosts = ((num_hosts as f64) * self.config.top_host_fraction).ceil() as usize;

        let crawl_budget_top_hosts_boost = total_crawl_budget
            * self
                .config
                .top_hosts_budget_boost
                .as_ref()
                .map(|top_hosts_budget_boost| top_hosts_budget_boost.reserved_budget_fraction)
                .unwrap_or_default();
        let total_crawl_budget = total_crawl_budget - crawl_budget_top_hosts_boost;

        let mut prev_sum = 0.0;
        let total_host_centrality = sorted_centralities(self.host_centrality.iter())
            .map(|(_, centrality)| centrality)
            .take_while(|centrality| {
                let sum = prev_sum + centrality;
                prev_sum = sum;
                // take as long as budget * c_i / S(c_i) > 0.5
                // as this will include exactly the hosts where
                // we crawl at least one page.
                // S(c_i) denotes the sum of all centralities
                // up to and including c_i
                2.0 * total_crawl_budget * centrality > sum
            })
            .take(num_hosts)
            .sum::<f64>();

        let top_hosts_total_centrality = self
            .config
            .top_hosts_budget_boost
            .as_ref()
            .map(|top_hosts_budget_boost| {
                sorted_centralities(self.host_centrality.iter())
                    .take(top_hosts_budget_boost.top_hosts)
                    .map(|(_, centrality)| centrality)
                    .sum::<f64>()
            })
            .unwrap_or_default();

        sorted_centralities(self.host_centrality.iter())
            .take(num_hosts)
            .enumerate()
            .filter_map(|(rank, (id, centrality))| {
                let mut total =
                    ((total_crawl_budget * centrality) / total_host_centrality).ceil() as u64;

                if let Some(top_hosts_budget_boost) = &self.config.top_hosts_budget_boost {
                    if rank < top_hosts_budget_boost.top_hosts {
                        total += ((crawl_budget_top_hosts_boost * centrality)
                            / top_hosts_total_centrality)
                            .round() as u64;
                    }
                }

                let budget = Budget {
                    remaining_schedulable: (total as f64 * (1.0 - self.config.wander_fraction))
                        .ceil() as u64,
                };

                if budget.remaining_schedulable > 0 {
                    Some((id, budget))
                } else {
                    None
                }
            })
            .collect()
    }

    async fn pages_to_crawl(&self) -> (Vec<speedy_kv::Db<StoredUrl, ()>>, u64) {
        let mut budgets = self.assign_budgets();

        let mut grouper = UrlGrouper::new(
            &self.config.output_path,
            NUM_GROUPS,
            self.harmonic_group.clone(),
            self.host_centrality_rank.clone(),
        );
        let mut futures = FuturesOrdered::new();

        let num_pages = self.page_centrality.len();
        for chunk in sorted_centralities(self.page_centrality.iter())
            .map(|(id, _)| id)
            .progress_count(num_pages as u64)
            .chunks(128)
            .into_iter()
        {
            while futures.len() >= CONCURRENCY_LIMIT {
                let nodes: Vec<Option<Node>> = futures.next().await.unwrap();
                add_nodes_to_grouper(nodes.into_iter().flatten(), &mut grouper, &mut budgets);
            }

            if budgets.is_empty() {
                break;
            }

            let nodes = chunk.collect::<Vec<_>>();
            let webgraph = self.webgraph.clone();

            futures.push_back(async move {
                webgraph
                    .batch_search(nodes.into_iter().map(Id2NodeQuery::Page).collect())
                    .await
                    .unwrap()
            });
        }

        while let Some(nodes) = futures.next().await {
            add_nodes_to_grouper(nodes.into_iter().flatten(), &mut grouper, &mut budgets);
        }

        // make sure frontpage is added for all hosts with a budget.
        // this is necessary to ensure that we crawl at least one page
        // for each host.
        let mut futures = FuturesOrdered::new();
        let num_missing_budgets = budgets.len();
        let missing_budgets = budgets.clone();
        for chunk in missing_budgets
            .keys()
            .copied()
            .progress_count(num_missing_budgets as u64)
            .chunks(128)
            .into_iter()
        {
            while futures.len() >= CONCURRENCY_LIMIT {
                let nodes: Vec<Option<Node>> = futures.next().await.unwrap();

                let nodes = nodes.into_iter().flatten().filter_map(|node| {
                    if let Ok(url) = Url::parse(&format!("https://{}", node.as_str())) {
                        Some(Node::from(url))
                    } else {
                        None
                    }
                });

                add_nodes_to_grouper(nodes, &mut grouper, &mut budgets);
            }

            let nodes = chunk.collect::<Vec<_>>();
            let webgraph = self.webgraph.clone();

            futures.push_back(async move {
                webgraph
                    .batch_search(nodes.into_iter().map(Id2NodeQuery::Host).collect())
                    .await
                    .unwrap()
            });
        }

        while let Some(nodes) = futures.next().await {
            add_nodes_to_grouper(nodes.into_iter().flatten(), &mut grouper, &mut budgets);
        }

        let missing_budgets = budgets
            .values()
            .map(|budget| budget.remaining_schedulable)
            .sum::<u64>();

        (grouper.into_groups(), missing_budgets)
    }

    pub async fn build(self) -> Result<()> {
        let output = Path::new(&self.config.output_path);

        if output.exists() {
            return Err(anyhow!("output path already exists"));
        }

        let queue_path = output.join("job_queue");
        std::fs::create_dir_all(&queue_path)?;

        tracing::info!("getting pages to crawl");

        let job_queues: Vec<Mutex<FileQueueWriter<Job>>> = (0..self.config.num_job_queues)
            .map(|i| {
                let path = queue_path.join(format!("{}.queue", i));
                FileQueueWriter::new(path)
            })
            .collect::<Result<Vec<_>>>()?
            .into_iter()
            .map(Mutex::new)
            .collect();

        let stats = Mutex::new(Vec::new());

        let pool = ThreadPoolBuilder::new()
            .num_threads(usize::from(std::thread::available_parallelism().unwrap()))
            .stack_size(80_000_000)
            .thread_name(move |num| format!("crawl-planner-{num}"))
            .build()?;

        let (groups, missing_budgets) = self.pages_to_crawl().await;

        tracing::info!("grouping pages by domain");

        for group in groups.into_iter().progress() {
            let mut grouped_pages = BTreeMap::new();

            for page in group.iter().map(|(url, _)| url).map(Url::from) {
                if let Some(domain) = page.icann_domain() {
                    grouped_pages
                        .entry(Domain::from(domain.to_string()))
                        .or_insert_with(Vec::new)
                        .push(page);
                }
            }

            pool.install(|| {
                let total_host_centralities: f64 = grouped_pages
                    .par_iter()
                    .map(|(_, pages)| {
                        pages
                            .iter()
                            .map(|url| Node::from(url).into_host().id())
                            .unique()
                            .map(|id| self.host_centrality.get(&id).unwrap().unwrap_or_default())
                            .sum::<f64>()
                    })
                    .sum();

                let total_host_centralities = total_host_centralities * NUM_GROUPS as f64;

                let wander_budget = self.config.crawl_budget as f64 * self.config.wander_fraction
                    + missing_budgets as f64;

                let next_queue = AtomicUsize::new(0);

                grouped_pages.into_par_iter().for_each(|(domain, pages)| {
                    if domain.as_str().is_empty() || self.excluded_domains.contains(&domain) {
                        return;
                    }

                    let (job, domain_stats) =
                        self.prepare_job(domain, pages, wander_budget, total_host_centralities);

                    stats
                        .lock()
                        .unwrap_or_else(|e| e.into_inner())
                        .push(domain_stats);

                    // `fetch_add` wraps around on overflow
                    let queue_index = next_queue.fetch_add(1, std::sync::atomic::Ordering::SeqCst);
                    job_queues[queue_index % job_queues.len()]
                        .lock()
                        .unwrap_or_else(|e| e.into_inner())
                        .push(job)
                        .unwrap();
                })
            });
        }

        for queue in job_queues {
            queue
                .into_inner()
                .unwrap_or_else(|e| e.into_inner())
                .finalize()?;
        }

        let mut stats = stats.into_inner().unwrap_or_else(|e| e.into_inner());
        stats.sort_by_key(|b| std::cmp::Reverse(b.schedule_budget()));

        let total_scheduled_urls: u64 = stats.iter().map(|d| d.scheduled_urls).sum();
        let total_wander_budget: u64 = stats.iter().map(|d| d.wander_budget).sum();
        let total_num_hosts: u64 = stats.iter().map(|d| d.num_hosts as u64).sum();
        let total_num_domains: u64 = stats.len() as u64;

        let metadata = Metadata {
            stats,
            total_scheduled_urls,
            total_wander_budget,
            total_num_hosts,
            total_num_domains,
        };

        tracing::info!("total scheduled urls: {}", metadata.total_scheduled_urls);

        tracing::info!("total wander budget: {}", metadata.total_wander_budget);

        let metadata_path = output.join("metadata.json");

        let metadata_file = std::fs::File::create(metadata_path)?;
        serde_json::to_writer_pretty(metadata_file, &metadata)?;

        std::fs::remove_dir_all(output.join("groups"))?;

        Ok(())
    }
}

fn add_nodes_to_grouper(
    nodes: impl Iterator<Item = Node>,
    grouper: &mut UrlGrouper,
    budgets: &mut BTreeMap<NodeID, Budget>,
) {
    for node in nodes {
        let url = Url::parse(&format!("https://{}", node.as_str()));
        let host = node.into_host();

        if let Some(budget) = budgets.get_mut(&host.id()) {
            if budget.remaining_schedulable == 0 {
                continue;
            }

            if let Ok(url) = url {
                budget.remaining_schedulable -= 1;
                grouper.insert(url);

                if budget.remaining_schedulable == 0 {
                    budgets.remove(&host.id());
                }
            }
        }
    }
}

#[derive(serde::Serialize)]
struct DomainStats {
    domain: Domain,
    num_hosts: usize,
    scheduled_urls: u64,
    wander_budget: u64,
}

impl DomainStats {
    pub fn schedule_budget(&self) -> u64 {
        self.scheduled_urls + self.wander_budget
    }
}

#[derive(serde::Serialize)]
struct Metadata {
    total_scheduled_urls: u64,
    total_wander_budget: u64,
    total_num_hosts: u64,
    total_num_domains: u64,
    stats: Vec<DomainStats>,
}