Skip to content

web search done right

23.6 KB
Raw Blame
// Stract is an open source web search engine.
// Copyright (C) 2024 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 crate::{
    distributed::{
        cluster::Cluster,
        member::{LiveIndexState, Service},
        sonic::{
            self,
            replication::{
                AllShardsSelector, RandomReplicaSelector, RemoteClient, ReplicatedClient,
                ReusableClientManager, ReusableShardedClient, Shard, ShardIdentifier,
                ShardedClient, SpecificShardSelector,
            },
        },
    },
    entrypoint::{
        entity_search_server, live_index::LiveIndexService, search_server::{self, RetrieveReq, SearchService}
    },
    generic_query::{self, Collector},
    inverted_index::{RetrievedWebpage, ShardId, WebpagePointer},
    ranking::pipeline::{PrecisionRankingWebpage, RecallRankingWebpage},
    Result,
};

use std::{collections::HashMap, sync::Arc};

use fnv::FnvHashMap;
use futures::{future::join_all, stream::FuturesUnordered, StreamExt};
use itertools::Itertools;
use std::future::Future;
use thiserror::Error;
use tokio::sync::Mutex;

use super::{InitialWebsiteResult, LocalSearcher, SearchQuery};

const CLIENT_REFRESH_INTERVAL: std::time::Duration = std::time::Duration::from_secs(60);

#[derive(Error, Debug)]
pub enum Error {
    #[error("Failed to get search result")]
    SearchFailed,

    #[error("Query cannot be empty")]
    EmptyQuery,

    #[error("Webpage not found")]
    WebpageNotFound,
}

pub trait SearchClient {
    fn search_initial(
        &self,
        query: &SearchQuery,
    ) -> impl Future<Output = Vec<InitialSearchResultShard>> + Send;

    fn retrieve_webpages(
        &self,
        top_websites: &[ScoredWebpagePointer],
        query: &str,
    ) -> impl Future<Output = Vec<PrecisionRankingWebpage>> + Send;

    fn search_initial_generic<Q>(
        &self,
        query: Q,
    ) -> impl Future<Output = Result<<Q::Collector as generic_query::Collector>::Fruit>> + Send
    where
        Q: search_server::Query,
        
        Result<
            <Q::Collector as generic_query::Collector>::Fruit,
            search_server::EncodedError,
        >: From<<Q as sonic::service::Message<SearchService>>::Response>,
        <<Q::Collector as generic_query::Collector>::Child as tantivy::collector::SegmentCollector>::Fruit:
            From<<Q::Collector as generic_query::Collector>::Fruit>;

    fn retrieve_generic<Q>(
        &self,
        query: Q,
        fruit: <Q::Collector as generic_query::Collector>::Fruit,
    ) -> impl Future<Output = Result<Vec<Q::IntermediateOutput>>> + Send
    where
        Q: search_server::Query,
        <Q::Collector as generic_query::Collector>::Fruit: Clone,
        Result<Q::IntermediateOutput, search_server::EncodedError>:
            From<
                <<Q as search_server::Query>::RetrieveReq as sonic::service::Message<
                    SearchService,
                >>::Response,
            >;

    fn search_generic<Q>(&self, query: Q) -> impl Future<Output = Result<Q::Output>> + Send
    where
        Self: Send + Sync,
        Q: search_server::Query,
        Result<
        <Q::Collector as generic_query::Collector>::Fruit,
        search_server::EncodedError,
    >: From<<Q as sonic::service::Message<SearchService>>::Response>,
    <<Q::Collector as generic_query::Collector>::Child as tantivy::collector::SegmentCollector>::Fruit:
        From<<Q::Collector as generic_query::Collector>::Fruit>,
        <Q::Collector as generic_query::Collector>::Fruit: Clone,
        Result<Q::IntermediateOutput, search_server::EncodedError>:
            From<
                <<Q as search_server::Query>::RetrieveReq as sonic::service::Message<
                    SearchService,
                >>::Response,
    >
    {
        async {
            let fruit = self.search_initial_generic(query.clone()).await?;
            let res = self.retrieve_generic(query, fruit).await?;
            let output = Q::merge_results(res);
            Ok(output)
        }
    }

    fn batch_search_initial_generic<Q>(
        &self,
        queries: Vec<Q>,
    ) -> impl Future<Output = Result<Vec<<Q::Collector as generic_query::Collector>::Fruit>>> + Send
    where
        Q: search_server::Query,
        
        Result<<<Q::Collector as generic_query::Collector>::Child as tantivy::collector::SegmentCollector>::Fruit, search_server::EncodedError>:
            From<<Q as sonic::service::Message<SearchService>>::Response>;

    fn batch_retrieve_generic<Q>(
        &self,
        queries: Vec<(Q, <Q::Collector as generic_query::Collector>::Fruit)>,
    ) -> impl Future<Output = Result<Vec<Vec<Q::IntermediateOutput>>>> + Send
    where
        Q: search_server::Query,
        Result<Q::IntermediateOutput, search_server::EncodedError>: From<
            <<Q as search_server::Query>::RetrieveReq as sonic::service::Message<
                SearchService,
            >>::Response,
        >,
        <Q::Collector as generic_query::Collector>::Fruit: Clone;

    fn batch_search_generic<Q>(&self, queries: Vec<Q>) -> impl Future<Output = Result<Vec<Q::Output>>> + Send
        where
            Q: search_server::Query,
            Self: Send + Sync,
            Result<<<Q::Collector as generic_query::Collector>::Child as tantivy::collector::SegmentCollector>::Fruit, search_server::EncodedError>:
                From<<Q as sonic::service::Message<SearchService>>::Response>,
            Result<Q::IntermediateOutput, search_server::EncodedError>: From<
                <<Q as search_server::Query>::RetrieveReq as sonic::service::Message<
                    SearchService,
                >>::Response,
            >,
            <Q::Collector as generic_query::Collector>::Fruit: Clone
        {
            async {
                let res = self.batch_search_initial_generic(queries.clone()).await?;
                let res = self
                    .batch_retrieve_generic(queries.into_iter().zip(res).collect())
                    .await?;
                Ok(res.into_iter().map(|v| Q::merge_results(v)).collect())
            }
        }
}

#[derive(Clone, Debug)]
pub struct ScoredWebpagePointer {
    pub website: RecallRankingWebpage,
    pub shard: ShardId,
}

impl ScoredWebpagePointer {
    pub fn as_ranking(&self) -> &RecallRankingWebpage {
        &self.website
    }

    pub fn as_ranking_mut(&mut self) -> &mut RecallRankingWebpage {
        &mut self.website
    }
}

impl ShardIdentifier for ShardId {}

#[derive(Debug)]
pub struct InitialSearchResultShard {
    pub local_result: InitialWebsiteResult,
    pub shard: ShardId,
}

impl ReusableClientManager for SearchService {
    const CLIENT_REFRESH_INTERVAL: std::time::Duration = CLIENT_REFRESH_INTERVAL;

    type Service = SearchService;
    type ShardId = ShardId;

    async fn new_client(cluster: &Cluster) -> ShardedClient<Self::Service, Self::ShardId> {
        let mut shards = HashMap::new();
        for member in cluster.members().await {
            if let Service::Searcher { host, shard } = member.service {
                shards.entry(shard).or_insert_with(Vec::new).push(host);
            } else if let Service::LiveIndex { search_host, shard, state, .. } = member.service {
                if state == LiveIndexState::Ready {
                    shards.entry(shard).or_insert_with(Vec::new).push(search_host);
                }
            }
        }

        let mut shard_clients = Vec::new();

        for (id, replicas) in shards {
            let replicated =
                ReplicatedClient::new(replicas.into_iter().map(RemoteClient::new).collect());
            let shard = Shard::new(id, replicated);
            shard_clients.push(shard);
        }

        ShardedClient::new(shard_clients)
    }
}

impl ReusableClientManager for entity_search_server::SearchService {
    const CLIENT_REFRESH_INTERVAL: std::time::Duration = CLIENT_REFRESH_INTERVAL;

    type Service = entity_search_server::SearchService;
    type ShardId = ();

    async fn new_client(cluster: &Cluster) -> ShardedClient<Self::Service, Self::ShardId> {
        let mut replicas = Vec::new();
        for member in cluster.members().await {
            if let Service::EntitySearcher { host } = member.service {
                replicas.push(RemoteClient::new(host));
            }
        }

        let rep = ReplicatedClient::new(replicas);

        if !rep.is_empty() {
            ShardedClient::new(vec![Shard::new((), rep)])
        } else {
            ShardedClient::new(vec![])
        }
    }
}

impl ReusableClientManager for LiveIndexService {
    const CLIENT_REFRESH_INTERVAL: std::time::Duration = CLIENT_REFRESH_INTERVAL;

    type Service = LiveIndexService;

    type ShardId = ShardId;

    async fn new_client(cluster: &Cluster) -> ShardedClient<Self::Service, Self::ShardId> {
        let mut shards = HashMap::new();
        for member in cluster.members().await {
            if let Service::LiveIndex { host, shard, state, .. } = member.service {
                if state == LiveIndexState::Ready {
                    shards.entry(shard).or_insert_with(Vec::new).push(host);
                }
            }
        }

        let mut shard_clients = Vec::new();

        for (id, replicas) in shards {
            let replicated =
                ReplicatedClient::new(replicas.into_iter().map(RemoteClient::new).collect());
            let shard = Shard::new(id, replicated);
            shard_clients.push(shard);
        }

        ShardedClient::new(shard_clients)
    }
}

/// A searcher that runs the search on a remote cluster.
pub struct DistributedSearcher {
    client: Mutex<ReusableShardedClient<SearchService>>,
}

impl DistributedSearcher {
    pub async fn new(cluster: Arc<Cluster>) -> Self {
        Self::from_client(ReusableShardedClient::new(cluster.clone()).await)
    }

    pub fn from_client(client: ReusableShardedClient<SearchService>) -> Self {
        Self {
            client: Mutex::new(client),
        }
    }

    async fn conn(&self) -> Arc<ShardedClient<SearchService, ShardId>> {
        self.client.lock().await.conn().await
    }

    async fn retrieve_webpages_from_shard(
        &self,
        shard: ShardId,
        client: &ShardedClient<SearchService, ShardId>,
        query: &str,
        pointers: Vec<(usize, WebpagePointer)>,
    ) -> Vec<(usize, RetrievedWebpage)> {
        let (idxs, pointers): (Vec<usize>, Vec<WebpagePointer>) = pointers.into_iter().unzip();

        match client
            .send(
                search_server::RetrieveWebsites {
                    websites: pointers,
                    query: query.to_string(),
                },
                &SpecificShardSelector(shard),
                &RandomReplicaSelector,
            )
            .await
        {
            Ok(v) => v
                .into_iter()
                .flatten()
                .flat_map(|(_, v)| v.into_iter().map(|(_, v)| v))
                .flatten()
                .flatten()
                .zip_eq(idxs)
                .map(|(v, i)| (i, v))
                .collect(),
            _ => vec![],
        }
    }
}

impl SearchClient for DistributedSearcher {
    async fn search_initial(&self, query: &SearchQuery) -> Vec<InitialSearchResultShard> {
        let client = self.conn().await;
        let mut results = Vec::new();

        if let Ok(res) = client
            .send(
                search_server::Search {
                    query: query.clone(),
                },
                &AllShardsSelector,
                &RandomReplicaSelector,
            )
            .await
        {
            for (shard_id, mut res) in res.into_iter().flatten() {
                if let Some((_, Some(res))) = res.pop() {
                    results.push(InitialSearchResultShard {
                        local_result: res,
                        shard: shard_id,
                    });
                }
            }
        }

        results
    }

    async fn retrieve_webpages(
        &self,
        top_websites: &[ScoredWebpagePointer],
        query: &str,
    ) -> Vec<PrecisionRankingWebpage> {
        let mut rankings = FnvHashMap::default();
        let mut pointers: HashMap<_, Vec<_>> = HashMap::new();

        for (i, pointer) in top_websites.iter().enumerate() {
            pointers
                .entry(pointer.shard)
                .or_default()
                .push((i, pointer.website.pointer().clone()));

            rankings.insert(i, pointer.website.clone());
        }

        let client = self.conn().await;
        let mut futures = Vec::new();
        for (shard, pointers) in pointers {
            futures.push(self.retrieve_webpages_from_shard(shard, &client, query, pointers));
        }

        let mut retrieved_webpages = Vec::new();
        for pages in join_all(futures).await {
            for (i, page) in pages {
                retrieved_webpages
                    .push((i, PrecisionRankingWebpage::new(page, rankings[&i].clone())));
            }
        }

        debug_assert_eq!(retrieved_webpages.len(), top_websites.len());

        retrieved_webpages.sort_by(|(a, _), (b, _)| a.cmp(b));
        retrieved_webpages.into_iter().map(|(_, v)| v).collect()
    }

    async fn search_initial_generic<Q>(
        &self,
        query: Q,
    ) -> Result<<Q::Collector as generic_query::Collector>::Fruit>
    where
        Q: search_server::Query,
        Result<
            <Q::Collector as generic_query::Collector>::Fruit,
            search_server::EncodedError,
        >: From<<Q as sonic::service::Message<SearchService>>::Response>,
        <<Q::Collector as generic_query::Collector>::Child as tantivy::collector::SegmentCollector>::Fruit:
            From<<Q::Collector as generic_query::Collector>::Fruit> {
        let collector = query.coordinator_collector();

        let res = self.conn().await
            .send(query, &AllShardsSelector, &RandomReplicaSelector)
            .await?;

        let fruits: Vec<<<Q::Collector as generic_query::Collector>::Child as tantivy::collector::SegmentCollector>::Fruit> = res
            .into_iter()
            .flatten()
            .flat_map(|(_, reps)| reps)
            .filter_map(|(_, rep)| {
                Result::<
                    <Q::Collector as generic_query::Collector>::Fruit,
                    search_server::EncodedError,
                >::from(rep)
                .ok()
            })
            .map(|fruit| {
                <<Q::Collector as generic_query::Collector>::Child as tantivy::collector::SegmentCollector>::Fruit::from(fruit)
            })
            .collect();

        collector
            .merge_fruits(fruits)
            .map_err(|_| anyhow::anyhow!("failed to merge fruits"))
    }
    
    async fn retrieve_generic<Q>(
        &self,
        query: Q,
        fruit: <Q::Collector as generic_query::Collector>::Fruit,
    ) -> Result<Vec<Q::IntermediateOutput>>
    where
        Q: search_server::Query,
        <Q::Collector as generic_query::Collector>::Fruit: Clone,
        Result<Q::IntermediateOutput, search_server::EncodedError>:
            From<
                <<Q as search_server::Query>::RetrieveReq as sonic::service::Message<
                    SearchService,
                >>::Response,
            >
    {
        let conn = self.conn().await;
        let mut results = FuturesUnordered::new();
        for shard in conn.shards() {
            let fruit = query.filter_fruit_shards(*shard.id(), fruit.clone());
            let req = Q::RetrieveReq::new(query.clone(), fruit);
            results.push(shard.replicas().send(req, &RandomReplicaSelector));
        }
        let mut res = Vec::new();

        while let Some(shard_res) = results.next().await {
            if let Ok(shard_res) = shard_res {
                res.push(shard_res);
            }
        }

        Ok(res
            .into_iter()
            .flatten()
            .filter_map(|(_, res)| {
                Result::<Q::IntermediateOutput, search_server::EncodedError>::from(res).ok()
            })
            .collect())
    }
    
    async fn batch_search_initial_generic<Q>(
        &self,
        queries: Vec<Q>,
    ) -> Result<Vec<<Q::Collector as generic_query::Collector>::Fruit>>
    where
        Q: search_server::Query,
        Result<<<Q::Collector as generic_query::Collector>::Child as tantivy::collector::SegmentCollector>::Fruit, search_server::EncodedError>:
            From<<Q as sonic::service::Message<SearchService>>::Response>,
        {
            let res = self
                .conn()
                .await
                .batch_send(&queries, &AllShardsSelector, &RandomReplicaSelector)
                .await?;
    
            let mut fruits = Vec::with_capacity(queries.len());
    
            for _ in 0..queries.len() {
                fruits.push(Vec::new());
            }
    
            for (_, replica_results) in res.into_iter() {
                debug_assert_eq!(replica_results.len(), 1);
    
                for (_, shard_results) in replica_results.into_iter() {
                    for (i, shard_result) in shard_results.into_iter().enumerate() {
                        if let Ok(shard_result) =
                            Result::<_, search_server::EncodedError>::from(shard_result)
                        {
                            fruits[i].push(shard_result);
                        }
                    }
                }
            }
    
            queries
                .iter()
                .zip_eq(fruits.into_iter())
                .map(|(query, shard_fruits)| query.coordinator_collector().merge_fruits(shard_fruits))
                .collect::<Result<Vec<_>, _>>()
    }
    
    async fn batch_retrieve_generic<Q>(
        &self,
        queries: Vec<(Q, <Q::Collector as generic_query::Collector>::Fruit)>,
    ) -> Result<Vec<Vec<Q::IntermediateOutput>>>
    where
        Q: search_server::Query,
        Result<Q::IntermediateOutput, search_server::EncodedError>: From<
            <<Q as search_server::Query>::RetrieveReq as sonic::service::Message<
                SearchService,
            >>::Response,
        >,
        <Q::Collector as generic_query::Collector>::Fruit: Clone,
    {
        let conn = self.conn().await;
        let mut results = FuturesUnordered::new();

        for shard in conn.shards() {
            let retrieve_requests: Vec<_> = queries
                .iter()
                .map(|(query, fruit)| {
                    let fruit = query.filter_fruit_shards(*shard.id(), fruit.clone());
                    Q::RetrieveReq::new(query.clone(), fruit)
                })
                .collect();

            results.push(async move {
                let retrieve_requests = retrieve_requests; // move lifetime
                shard
                    .replicas()
                    .batch_send(&retrieve_requests, &RandomReplicaSelector)
                    .await
            });
        }

        let mut res = Vec::new();

        for _ in 0..queries.len() {
            res.push(Vec::new());
        }

        while let Some(shard_res) = results.next().await {
            for (_, shard_res) in shard_res? {
                assert_eq!(shard_res.len(), queries.len());

                for (i, query_res) in shard_res.into_iter().enumerate() {
                    res[i].push(
                        <Result<Q::IntermediateOutput, search_server::EncodedError>>::from(
                            query_res,
                        )
                        .map_err(|e| anyhow::anyhow!("{e}"))?,
                    );
                }
            }
        }

        Ok(res)
    }

    
}

/// This should only be used for testing and benchmarks.
pub struct LocalSearchClient(LocalSearcher);
impl From<LocalSearcher> for LocalSearchClient {
    fn from(searcher: LocalSearcher) -> Self {
        Self(searcher)
    }
}

impl SearchClient for LocalSearchClient {
    async fn search_initial(&self, query: &SearchQuery) -> Vec<InitialSearchResultShard> {
        let res = self.0.search_initial(query, true).await.unwrap();

        vec![InitialSearchResultShard {
            local_result: res,
            shard: ShardId::Backbone(0),
        }]
    }

    async fn retrieve_webpages(
        &self,
        top_websites: &[ScoredWebpagePointer],
        query: &str,
    ) -> Vec<PrecisionRankingWebpage> {
        let pointers = top_websites
            .iter()
            .map(|p| p.website.pointer().clone())
            .collect::<Vec<_>>();

        let res = self
            .0
            .retrieve_websites(&pointers, query)
            .await
            .unwrap()
            .into_iter()
            .zip(top_websites.iter().map(|p| p.website.clone()))
            .map(|(ret, ran)| PrecisionRankingWebpage::new(ret, ran))
            .collect::<Vec<_>>();

        res
    }

    async fn search_initial_generic<Q>(
        &self,
        query: Q,
    ) -> Result<<Q::Collector as generic_query::Collector>::Fruit>
    where
        Q: search_server::Query + 'static,
        Result<
            <Q::Collector as generic_query::Collector>::Fruit,
            search_server::EncodedError,
        >: From<<Q as sonic::service::Message<SearchService>>::Response>,
        <<Q::Collector as generic_query::Collector>::Child as tantivy::collector::SegmentCollector>::Fruit:
            From<<Q::Collector as generic_query::Collector>::Fruit> {
        self.0.search_initial_generic(query).await
    }
    
    async fn retrieve_generic<Q>(
        &self,
        query: Q,
        fruit: <Q::Collector as generic_query::Collector>::Fruit,
    ) -> Result<Vec<Q::IntermediateOutput>>
    where
        Q: search_server::Query,
        <Q::Collector as generic_query::Collector>::Fruit: Clone,
        Result<Q::IntermediateOutput, search_server::EncodedError>:
            From<
                <<Q as search_server::Query>::RetrieveReq as sonic::service::Message<
                    SearchService,
                >>::Response,
            > {
        Ok(vec![self.0.retrieve_generic(query, fruit).await?])
    }
    
    async fn batch_search_initial_generic<Q>(
        &self,
        queries: Vec<Q>,
    ) -> Result<Vec<<Q::Collector as generic_query::Collector>::Fruit>>
    where
        Q: search_server::Query,
        Result<<<Q::Collector as generic_query::Collector>::Child as tantivy::collector::SegmentCollector>::Fruit, search_server::EncodedError>:
            From<<Q as sonic::service::Message<SearchService>>::Response> {
        let mut res = Vec::new();

        for query in queries {
            res.push(self.0.search_initial_generic(query).await?);
        }

        Ok(res)
    }
    
    async fn batch_retrieve_generic<Q>(
        &self,
        queries: Vec<(Q, <Q::Collector as generic_query::Collector>::Fruit)>,
    ) -> Result<Vec<Vec<Q::IntermediateOutput>>>
    where
        Q: search_server::Query,
        Result<Q::IntermediateOutput, search_server::EncodedError>: From<
            <<Q as search_server::Query>::RetrieveReq as sonic::service::Message<
                SearchService,
            >>::Response,
        >,
        <Q::Collector as generic_query::Collector>::Fruit: Clone,
       {
        let mut res = Vec::new();

        for (query, fruit) in queries {
            res.push(vec![self.0.retrieve_generic(query, fruit).await?]);
        }

        Ok(res)
    }
}