Skip to content

web search done right

13.3 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 std::sync::Arc;

use futures::{stream::FuturesUnordered, StreamExt};
use itertools::Itertools;
use tokio::sync::Mutex;
use url::Url;

use crate::{
    ampc::dht::ShardId,
    distributed::{
        cluster::Cluster,
        member::Service,
        sonic::{
            self,
            replication::{
                AllShardsSelector, RandomReplicaSelector, RemoteClient, ReplicatedClient,
            },
        },
        streaming_response::StreamingResponse,
    },
    entrypoint::webgraph_server::{self, GetPageNodeIDs, Query, RetrieveReq, WebGraphService},
    webgraph::Collector,
    Result,
};

use super::{query::BacklinksQuery, EdgeLimit, Node, NodeID};
use crate::webgraph;

impl sonic::replication::ShardIdentifier for ShardId {}

struct WebgraphClientManager;

impl sonic::replication::ReusableClientManager for WebgraphClientManager {
    const CLIENT_REFRESH_INTERVAL: std::time::Duration = std::time::Duration::from_secs(60);

    type Service = WebGraphService;
    type ShardId = ShardId;

    async fn new_client(
        cluster: &Cluster,
    ) -> sonic::replication::ShardedClient<Self::Service, Self::ShardId> {
        let shards = cluster
            .members()
            .await
            .into_iter()
            .filter_map(|member| {
                if let Service::Webgraph { host, shard } = member.service {
                    Some((shard, RemoteClient::<WebGraphService>::new(host)))
                } else {
                    None
                }
            })
            .into_group_map();

        let shards: Vec<_> = shards
            .into_iter()
            .map(|(shard, clients)| {
                let replica = ReplicatedClient::new(clients);
                sonic::replication::Shard::new(shard, replica)
            })
            .collect();

        sonic::replication::ShardedClient::new(shards)
    }
}

#[derive(Clone)]
pub struct RemoteWebgraph {
    client: Arc<Mutex<sonic::replication::ReusableShardedClient<WebgraphClientManager>>>,
    cluster: Arc<Cluster>,
}

impl RemoteWebgraph {
    pub async fn new(cluster: Arc<Cluster>) -> Self {
        Self {
            client: Arc::new(Mutex::new(
                sonic::replication::ReusableShardedClient::new(cluster.clone()).await,
            )),
            cluster,
        }
    }

    pub async fn await_ready(&self) {
        tracing::info!("waiting for webgraph to come online...");
        self.cluster
            .await_member(|member| matches!(member.service, Service::Webgraph { .. }))
            .await;
    }

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

    pub async fn search_initial<Q>(
        &self,
        query: &Q,
    ) -> Result<<Q::Collector as webgraph::Collector>::Fruit>
    where
        Q: Query,
        Result<
            <Q::Collector as webgraph::Collector>::Fruit,
            webgraph_server::EncodedError,
        >: From<<Q as sonic::service::Message<WebGraphService>>::Response>,
        <<Q::Collector as webgraph::Collector>::Child as tantivy::collector::SegmentCollector>::Fruit:
            From<<Q::Collector as webgraph::Collector>::Fruit>,
    {
        let collector = query.coordinator_collector();

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

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

        collector
            .merge_fruits(fruits)
            .map_err(|_| anyhow::anyhow!("failed to merge fruits"))
    }

    pub async fn retrieve<Q>(
        &self,
        query: Q,
        fruit: <Q::Collector as webgraph::Collector>::Fruit,
    ) -> Result<Vec<Q::IntermediateOutput>>
    where
        Q: Query,
        <Q::Collector as webgraph::Collector>::Fruit: Clone,
        <Q as webgraph_server::Query>::RetrieveReq: sonic::service::Wrapper<WebGraphService>,
        Result<Q::IntermediateOutput, webgraph_server::EncodedError>: From<
            <<Q as webgraph_server::Query>::RetrieveReq as sonic::service::Message<
                WebGraphService,
            >>::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, webgraph_server::EncodedError>::from(res).ok()
            })
            .collect())
    }

    pub async fn search<Q>(&self, query: Q) -> Result<Q::Output>
    where
        Q: Query,
        <Q::Collector as webgraph::Collector>::Fruit: Clone,
        Result<
            <Q::Collector as webgraph::Collector>::Fruit,
            webgraph_server::EncodedError,
        >: From<<Q as sonic::service::Message<WebGraphService>>::Response>,
        <<Q::Collector as webgraph::Collector>::Child as tantivy::collector::SegmentCollector>::Fruit:
            From<<Q::Collector as webgraph::Collector>::Fruit>,
        <Q as webgraph_server::Query>::RetrieveReq: sonic::service::Wrapper<WebGraphService>,
        Result<Q::IntermediateOutput, webgraph_server::EncodedError>: From<
            <<Q as webgraph_server::Query>::RetrieveReq as sonic::service::Message<
                WebGraphService,
            >>::Response,
        >,
    {
        let fruit = self.search_initial(&query).await?;
        let res = self.retrieve(query, fruit).await?;
        let output = Q::merge_results(res);
        Ok(output)
    }

    pub async fn batch_search_initial<Q>(
        &self,
        queries: &[Q],
    ) -> Result<Vec<<Q::Collector as webgraph::Collector>::Fruit>>
    where
        Q: Query,
        <Q::Collector as webgraph::Collector>::Fruit: Clone,
        Result<<<Q::Collector as webgraph::Collector>::Child as tantivy::collector::SegmentCollector>::Fruit, webgraph_server::EncodedError>:
            From<<Q as sonic::service::Message<WebGraphService>>::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::<_, webgraph_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<_>, _>>()
    }

    pub async fn batch_retrieve<Q>(
        &self,
        queries: Vec<(Q, <Q::Collector as webgraph::Collector>::Fruit)>,
    ) -> Result<Vec<Vec<Q::IntermediateOutput>>>
    where
        Q: Query,
        <Q as webgraph_server::Query>::RetrieveReq: sonic::service::Wrapper<WebGraphService>,
        Result<Q::IntermediateOutput, webgraph_server::EncodedError>: From<
            <<Q as webgraph_server::Query>::RetrieveReq as sonic::service::Message<
                WebGraphService,
            >>::Response,
        >,
        <Q::Collector as webgraph::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, webgraph_server::EncodedError>>::from(
                            query_res,
                        )
                        .map_err(|e| anyhow::anyhow!("{e}"))?,
                    );
                }
            }
        }

        Ok(res)
    }

    pub async fn batch_search<Q>(&self, queries: Vec<Q>) -> Result<Vec<Q::Output>>
    where
        Q: Query,
        <Q::Collector as webgraph::Collector>::Fruit: Clone,
        Result<<<Q::Collector as webgraph::Collector>::Child as tantivy::collector::SegmentCollector>::Fruit, webgraph_server::EncodedError>:
            From<<Q as sonic::service::Message<WebGraphService>>::Response>,
            <Q as webgraph_server::Query>::RetrieveReq: sonic::service::Wrapper<WebGraphService>,
        Result<Q::IntermediateOutput, webgraph_server::EncodedError>: From<
            <<Q as webgraph_server::Query>::RetrieveReq as sonic::service::Message<
                WebGraphService,
            >>::Response,
        >,
    {
        let res = self.batch_search_initial(&queries).await?;
        let res = self
            .batch_retrieve(queries.into_iter().zip(res).collect())
            .await?;
        Ok(res.into_iter().map(|v| Q::merge_results(v)).collect())
    }

    pub async fn knows(&self, mut host: String) -> Result<Option<Node>> {
        if let Some(suf) = host.strip_prefix("http://") {
            host = suf.to_string();
        }
        if let Some(suf) = host.strip_prefix("https://") {
            host = suf.to_string();
        }

        let url = Url::parse(&("http://".to_string() + host.as_str()))?;
        let node = Node::from(url).into_host();
        let id = node.id();
        let edges = self
            .search(BacklinksQuery::new(id).with_limit(EdgeLimit::Limit(1)))
            .await?;

        if !edges.is_empty() {
            Ok(Some(node))
        } else {
            Ok(None)
        }
    }

    pub async fn stream_page_node_ids(&self) -> impl futures::Stream<Item = NodeID> {
        StreamNodeIDs::new(self.conn().await).stream()
    }
}

pub struct StreamNodeIDs {
    offset: u64,
    limit: u64,
    conn: Arc<sonic::replication::ShardedClient<WebGraphService, ShardId>>,
}

impl StreamNodeIDs {
    pub fn new(conn: Arc<sonic::replication::ShardedClient<WebGraphService, ShardId>>) -> Self {
        Self {
            offset: 0,
            limit: 2048,
            conn,
        }
    }
}

impl StreamingResponse for StreamNodeIDs {
    type Item = NodeID;

    async fn next_batch(&mut self) -> Result<Vec<Self::Item>> {
        let req = GetPageNodeIDs {
            offset: self.offset,
            limit: self.limit,
        };

        let res = self
            .conn
            .send(req, &AllShardsSelector, &RandomReplicaSelector)
            .await?;
        self.offset += self.limit;

        Ok(res
            .into_iter()
            .flatten()
            .flat_map(|(_, v)| v.into_iter().flat_map(|(_, v)| v))
            .collect())
    }
}