Skip to content

web search done right

21.1 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;
use hashbrown::HashSet;
use itertools::Itertools;
use rand::seq::SliceRandom;

use std::{
    collections::VecDeque,
    net::SocketAddr,
    sync::Arc,
    time::{Duration, Instant},
};

use url::Url;

use crate::{
    config::CrawlerConfig,
    crawler::MAX_URL_LEN_BYTES,
    dated_url::DatedUrl,
    distributed::{retry_strategy::ExponentialBackoff, sonic},
    entrypoint::crawler::router::{NewJob, RouterService},
    sitemap::{parse_sitemap, SitemapEntry},
    warc,
    webpage::{url_ext::UrlExt, Html},
};

use super::{
    encoded_body, robot_client::RobotClient, wander_prioritiser::WanderPrioritiser, CrawlDatum,
    DatumSink, Domain, Error, Result, RetrieableUrl, Site, WarcWriter, WeightedUrl, WorkerJob,
    MAX_CONTENT_LENGTH, MAX_OUTGOING_URLS_PER_PAGE,
};

const IGNORED_EXTENSIONS: [&str; 27] = [
    ".pdf", ".jpg", ".zip", ".png", ".css", ".js", ".json", ".jsonp", ".woff2", ".woff", ".ttf",
    ".svg", ".gif", ".jpeg", ".ico", ".mp4", ".mp3", ".avi", ".mov", ".mpeg", ".webm", ".wav",
    ".flac", ".aac", ".ogg", ".m4a", ".m4v",
];

const INITIAL_WANDER_STEPS: u64 = 4;

enum UrlVisit {
    Skip,
    CanCrawl,
}

struct ProcessedUrl {
    new_urls: Vec<Url>,
}

pub struct WorkerThread {
    writer: Arc<WarcWriter>,
    config: Arc<CrawlerConfig>,
    router_hosts: Vec<SocketAddr>,
    client: RobotClient,
}

impl WorkerThread {
    pub fn new(
        writer: Arc<WarcWriter>,
        client: RobotClient,
        config: CrawlerConfig,
        router_hosts: Vec<SocketAddr>,
    ) -> Result<Self> {
        Ok(Self {
            writer,
            client,
            config: Arc::new(config),
            router_hosts,
        })
    }

    async fn router_conn(&self) -> Result<sonic::service::Connection<RouterService>> {
        let retry = ExponentialBackoff::from_millis(1_000).with_limit(Duration::from_secs(10));

        let router = *self.router_hosts.choose(&mut rand::thread_rng()).unwrap();

        sonic::service::Connection::create_with_timeout_retry(
            router,
            Duration::from_secs(90),
            retry,
        )
        .await
        .map_err(|e| Error::from(anyhow!(e)))
    }

    pub async fn run(self) {
        loop {
            let mut conn = self.router_conn().await.unwrap();
            let res = conn
                .send_with_timeout(NewJob {}, Duration::from_secs(90))
                .await;

            match res {
                Ok(Some(job)) => {
                    let executor = JobExecutor::new(
                        job.into(),
                        self.config.clone(),
                        self.writer.clone(),
                        self.client.clone(),
                    );
                    executor.run().await;
                }
                Ok(None) => {
                    return;
                }
                _ => {
                    tokio::time::sleep(Duration::from_secs(60)).await;
                    continue;
                }
            }
        }
    }
}

/// JobExecutor receives a job from the coordinator and crawls the urls in the job.
pub struct JobExecutor<S: DatumSink> {
    writer: Arc<S>,
    client: RobotClient,
    has_gotten_429_response: bool,
    politeness_factor: u32,
    crawled_urls: HashSet<Url>,
    crawled_sitemaps: HashSet<Site>,
    sitemap_urls: HashSet<Url>,
    min_crawl_delay: Duration,
    max_crawl_delay: Duration,
    max_url_slowdown_retry: u8,
    min_politeness_factor: u32,
    max_politeness_factor: u32,
    wander_prioritiser: WanderPrioritiser,
    wandered_urls: u64,
    job: WorkerJob,
}

impl<S: DatumSink> JobExecutor<S> {
    pub fn new(
        job: WorkerJob,
        config: Arc<CrawlerConfig>,
        writer: Arc<S>,
        client: RobotClient,
    ) -> Self {
        Self {
            writer,
            politeness_factor: config.start_politeness_factor,
            min_politeness_factor: config.min_politeness_factor,
            client,
            crawled_urls: HashSet::new(),
            crawled_sitemaps: HashSet::new(),
            wandered_urls: 0,
            sitemap_urls: HashSet::new(),
            min_crawl_delay: Duration::from_millis(config.min_crawl_delay_ms),
            max_crawl_delay: Duration::from_millis(config.max_crawl_delay_ms),
            max_url_slowdown_retry: config.max_url_slowdown_retry,
            max_politeness_factor: config.max_politeness_factor,
            wander_prioritiser: WanderPrioritiser::new(),
            has_gotten_429_response: false,
            job,
        }
    }

    pub async fn run(mut self) {
        tracing::info!("Processing job: {:?}", self.job.domain);
        for site in self
            .job
            .urls
            .iter()
            .filter_map(|url| url.url().normalized_host())
        {
            if let Ok(url) = Url::parse(format!("https://{}", site).as_str()) {
                self.wander_prioritiser.inc(url, 1.0);
            }
        }

        let mut wander_steps = 0;
        while self.wandered_urls < self.job.wandering_urls
            && self.wander_prioritiser.known_urls() > 0
            && wander_steps < INITIAL_WANDER_STEPS
        {
            self.wander().await;
            wander_steps += 1;
        }

        self.scheduled_urls().await;

        if self.wandered_urls < self.job.wandering_urls {
            self.crawl_sitemaps().await;
        }

        while self.wandered_urls < self.job.wandering_urls
            && self.wander_prioritiser.known_urls() > 0
        {
            self.wander().await;
        }
    }

    async fn scheduled_urls(&mut self) {
        let urls = self.job.urls.drain(..).collect();
        self.process_urls(urls).await;
    }

    async fn wander(&mut self) {
        let mut urls: Vec<(Url, f64)> = self
            .wander_prioritiser
            .top_and_clear(self.job.wandering_urls.saturating_sub(self.wandered_urls) as usize)
            .into_iter()
            .chain(self.sitemap_urls.drain().map(|url| (url.clone(), 0.0)))
            .map(|(mut url, score)| {
                url.normalize_in_place();
                (url, score)
            })
            .filter(|(url, _)| !self.crawled_urls.contains(url))
            .filter(|(url, _)| self.job.domain == Domain::from(url))
            .filter(|(_, score)| score.is_finite())
            .unique_by(|(url, _)| url.clone())
            .collect();

        urls.sort_by(|(_, a), (_, b)| b.total_cmp(a));

        let urls: VecDeque<_> = urls
            .into_iter()
            .map(|(url, _)| url)
            .map(|mut url| {
                url.normalize_in_place();
                url
            })
            .filter(|url| !self.crawled_urls.contains(url))
            .take(self.job.wandering_urls.saturating_sub(self.wandered_urls) as usize)
            .map(|url| WeightedUrl { url, weight: 0.0 })
            .map(RetrieableUrl::from)
            .collect();

        self.wandered_urls += urls.len() as u64;

        self.process_urls(urls).await;
    }

    async fn verify_url(&mut self, retryable_url: &RetrieableUrl) -> UrlVisit {
        if Domain::from(retryable_url.url()) != self.job.domain {
            return UrlVisit::Skip;
        }

        if self.crawled_urls.contains(retryable_url.url()) {
            return UrlVisit::Skip;
        }

        if retryable_url.retries > self.max_url_slowdown_retry {
            return UrlVisit::Skip;
        }

        if retryable_url.url().host_str().is_none()
            || !matches!(retryable_url.url().scheme(), "http" | "https")
        {
            return UrlVisit::Skip;
        }

        if !self
            .client
            .robots_txt_manager()
            .is_allowed(retryable_url.url())
            .await
        {
            return UrlVisit::Skip;
        }

        if let Some(port) = retryable_url.url().port() {
            if port != 80 && port != 443 {
                return UrlVisit::Skip;
            }
        }

        UrlVisit::CanCrawl
    }

    async fn crawl_sitemaps(&mut self) {
        let urls: Vec<_> = self.job.urls.iter().map(|url| url.url()).cloned().collect();

        for url in urls {
            let site = Site(url.host_str().unwrap_or_default().to_string());
            if !self.crawled_sitemaps.contains(&site) {
                self.crawled_sitemaps.insert(site.clone());

                let sitemaps = self.client.robots_txt_manager().sitemaps(&url).await;

                for sitemap in sitemaps {
                    let res = self.urls_from_sitemap(sitemap, 5).await;
                    self.sitemap_urls
                        .extend(res.into_iter().map(|dated_url| dated_url.url));
                }
            }
        }
    }

    pub async fn process_urls(&mut self, mut urls: VecDeque<RetrieableUrl>) {
        tracing::debug!("processing {} urls", urls.len());
        while let Some(mut retryable_url) = urls.pop_front() {
            retryable_url.weighted_url.url.normalize_in_place();

            if let UrlVisit::Skip = self.verify_url(&retryable_url).await {
                tracing::debug!("skipping url: {}", retryable_url.url());
                continue;
            }

            if let Some(delay) = self
                .client
                .robots_txt_manager()
                .crawl_delay(retryable_url.url())
                .await
            {
                if delay > self.min_crawl_delay {
                    self.min_crawl_delay = delay.min(self.max_crawl_delay);
                }
            }

            let res = self.process_url(retryable_url.url().clone()).await;

            match res {
                Ok(res) => {
                    if !self.has_gotten_429_response {
                        self.decrease_politeness();
                    }

                    let weight = retryable_url.weighted_url.weight;

                    for new_url in res.new_urls {
                        if new_url.host_str().is_none() {
                            continue;
                        }

                        if new_url.root_domain() != retryable_url.url().root_domain() {
                            continue;
                        }

                        self.wander_prioritiser.inc(new_url, weight);
                    }
                }
                Err(Error::FetchFailed {
                    status_code,
                    headers,
                }) if status_code == 429 => {
                    self.has_gotten_429_response = true;

                    if headers.contains_key("retry-after") {
                        let retry_after = headers["retry-after"]
                            .to_str()
                            .ok()
                            .and_then(|s| s.parse::<u64>().ok())
                            .map(Duration::from_secs);

                        if let Some(retry_after) = retry_after {
                            if retry_after > self.max_crawl_delay {
                                return; // don't crawl anymore from this site
                            }

                            tokio::time::sleep(retry_after).await;
                        }
                    }

                    self.increase_politeness();
                    let mut retryable_url = retryable_url;
                    retryable_url.retries += 1;
                    urls.push_back(retryable_url);
                }
                Err(Error::FetchFailed {
                    status_code,
                    headers,
                }) if status_code == 301 || status_code == 302 => {
                    if let Some(new_url) = headers
                        .get("location")
                        .and_then(|location| std::str::from_utf8(location.as_bytes()).ok())
                        .and_then(|location| {
                            Url::parse_with_base_url(&retryable_url.weighted_url.url, location).ok()
                        })
                    {
                        let mut retryable_url = retryable_url;
                        retryable_url.weighted_url.url = new_url;
                        retryable_url.retries += 1;
                        urls.push_back(retryable_url);
                    }
                }
                Err(_) => {}
            }
        }
    }

    fn increase_politeness(&mut self) {
        self.politeness_factor += 1;

        if self.politeness_factor > self.max_politeness_factor {
            self.politeness_factor = self.max_politeness_factor;
        }

        tracing::warn!(
            "politeness factor increased to {} for {}",
            self.politeness_factor,
            self.job.domain.as_str()
        );
    }

    fn decrease_politeness(&mut self) {
        if self.min_politeness_factor >= self.politeness_factor {
            self.politeness_factor = self.min_politeness_factor;
            return;
        }

        self.politeness_factor = self.politeness_factor.saturating_sub(1);
    }

    fn new_urls(&self, html: &Html) -> Vec<Url> {
        html.anchor_links()
            .into_iter()
            .map(|link| link.destination)
            .filter(|url| matches!(url.scheme(), "http" | "https"))
            .map(|mut url| {
                url.normalize_in_place();
                url
            })
            .filter(|url| url.as_str().len() <= MAX_URL_LEN_BYTES)
            .filter(|url| {
                IGNORED_EXTENSIONS
                    .iter()
                    .all(|ext| !url.as_str().ends_with(ext))
            })
            .filter(|url| !self.crawled_urls.contains(url))
            .unique()
            .collect()
    }

    async fn process_url(&mut self, url: Url) -> Result<ProcessedUrl> {
        let datum = self.polite_crawl_url(url.clone()).await?;
        self.save_datum(datum.clone()).await;

        match Html::parse(&datum.body, datum.url.as_str()) {
            Ok(html) => {
                let root_domain = datum.url.root_domain();
                let new_urls = self
                    .new_urls(&html)
                    .into_iter()
                    .filter(|new_url| new_url.root_domain() == root_domain)
                    .take(MAX_OUTGOING_URLS_PER_PAGE)
                    .collect();
                Ok(ProcessedUrl { new_urls })
            }
            Err(_) => Err(Error::InvalidHtml),
        }
    }

    async fn save_datum(&self, datum: CrawlDatum) {
        self.writer.write(datum).await.ok();
    }

    async fn fetch(&self, url: Url) -> Result<reqwest::Response> {
        self.client
            .get(url)
            .await?
            .send()
            .await
            .map_err(|e| Error::from(anyhow!(e)))
    }

    async fn fetch_with_https_priority(&self, url: Url) -> Result<reqwest::Response> {
        if url.scheme() == "http" {
            let mut https = url.clone();
            https
                .set_scheme("https")
                .map_err(|_| anyhow!("set scheme on url failed"))?;

            match self.fetch(https).await {
                Ok(res) => Ok(res),
                Err(_) => {
                    tokio::time::sleep(self.delay_duration()).await;
                    self.fetch(url.clone()).await
                }
            }
        } else {
            self.fetch(url.clone()).await
        }
    }

    fn delay_duration(&self) -> Duration {
        let mut delay = self.min_crawl_delay;
        delay = delay.mul_f64(2.0_f64.powi(self.politeness_factor as i32));

        if delay > self.max_crawl_delay {
            delay = self.max_crawl_delay;
        }

        delay
    }

    async fn politeness_delay(&self, fetch_time: Duration) {
        let mut delay = fetch_time;

        if delay < self.min_crawl_delay {
            delay = self.min_crawl_delay;
        }

        delay = delay.mul_f64(2.0_f64.powi(self.politeness_factor as i32));

        if delay > self.max_crawl_delay {
            delay = self.max_crawl_delay;
        }

        tokio::time::sleep(delay).await;
    }

    fn check_headers(&self, res: &reqwest::Response) -> Result<warc::PayloadType> {
        // check if content length is too large
        if let Some(content_length) = res
            .headers()
            .get(reqwest::header::CONTENT_LENGTH)
            .and_then(|value| value.to_str().ok())
            .and_then(|value| value.parse::<usize>().ok())
        {
            if content_length > MAX_CONTENT_LENGTH {
                return Err(Error::ContentTooLarge);
            }
        }

        // check if content type is html
        match res
            .headers()
            .get(reqwest::header::CONTENT_TYPE)
            .and_then(|val| val.to_str().ok())
        {
            Some(ct) if ct.contains("text/html") => Ok(warc::PayloadType::Html),
            Some(ct) if ct.contains("application/rss") => Ok(warc::PayloadType::Rss),
            Some(ct) if ct.contains("application/atom") => Ok(warc::PayloadType::Atom),
            ct => Err(Error::InvalidContentType(format!("{ct:?}"))),
        }
    }

    fn redirect_datum(
        &self,
        res: &reqwest::Response,
        url: &Url,
        payload_type: warc::PayloadType,
    ) -> Result<Option<CrawlDatum>> {
        let status_code = res.status().as_u16();

        if status_code == 301 || status_code == 302 {
            let location = res
                .headers()
                .get("location")
                .ok_or(Error::InvalidRedirect)?;

            let location = location.to_str().map_err(|_| Error::InvalidRedirect)?;

            let url = Url::parse(location)
                .or_else(|_| url.join(location))
                .map_err(|_| Error::InvalidRedirect)?;

            Ok(Some(CrawlDatum {
                url,
                payload_type,
                body: String::new(),
                fetch_time_ms: 0,
                date: chrono::Utc::now(),
            }))
        } else {
            Ok(None)
        }
    }

    async fn unpolite_crawl_url(&mut self, url: Url) -> Result<CrawlDatum> {
        tracing::debug!("crawling url: {}", url);

        let res = self.fetch_with_https_priority(url.clone()).await?;

        let payload_type = self.check_headers(&res);
        let status_code = res.status();
        let mut res_url = res.url().clone();

        if let Ok(payload_type) = payload_type {
            if let Ok(Some(datum)) = self.redirect_datum(&res, &url, payload_type) {
                return Ok(datum);
            }
        }
        if status_code != reqwest::StatusCode::OK {
            return Err(Error::FetchFailed {
                status_code,
                headers: res.headers().clone(),
            });
        }

        let body = encoded_body(res).await;

        self.crawled_urls.insert(url.clone());

        res_url.normalize_in_place();

        self.crawled_urls.insert(res_url.clone());

        Ok(CrawlDatum {
            url: res_url,
            body: body?,
            payload_type: payload_type?,
            fetch_time_ms: 0,
            date: chrono::Utc::now(),
        })
    }

    async fn polite_crawl_url(&mut self, url: Url) -> Result<CrawlDatum> {
        let mut url = url;
        url.normalize_in_place();

        if self.crawled_urls.contains(&url) {
            return Err(Error::from(anyhow!("url already crawled: {}", url)));
        }

        let start = Instant::now();
        let res = self.unpolite_crawl_url(url).await;
        let fetch_time = start.elapsed();
        self.politeness_delay(fetch_time).await;
        let mut datum = res?;
        datum.fetch_time_ms = fetch_time.as_millis() as u64;
        Ok(datum)
    }

    async fn urls_from_sitemap(&mut self, sitemap: Url, max_depth: usize) -> Vec<DatedUrl> {
        let mut stack = vec![(sitemap, 0)];
        let mut urls = vec![];

        while let Some((url, depth)) = stack.pop() {
            if depth >= max_depth {
                continue;
            }

            let res = self.fetch_with_https_priority(url).await;
            tokio::time::sleep(self.delay_duration()).await;

            if res.is_err() {
                continue;
            }

            let res = res.unwrap();

            if res.status() != reqwest::StatusCode::OK {
                continue;
            }

            let body = res.text().await;

            if body.is_err() {
                continue;
            }

            let body = body.unwrap();

            let entries = parse_sitemap(&body);

            for entry in entries {
                match entry {
                    SitemapEntry::Url(url) => {
                        urls.push(url);
                    }
                    SitemapEntry::Sitemap(url) => {
                        stack.push((url, depth + 1));
                    }
                }
            }
        }

        urls
    }
}