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 crate::block_on;
use std::{collections::BTreeMap, net::SocketAddr, pin::Pin};

use super::dht::{self, upsert::UpsertEnum, KeyTrait, UpsertAction, ValueTrait};

use crate::Result;

pub trait DhtTables
where
    Self: Clone + bincode::Encode + bincode::Decode + Send + Sync,
{
    fn drop_tables(&self);
    fn next(&self) -> Self;
    fn cleanup_prev_tables(&self);
}

// TODO: this could be a derive proc macro instead
macro_rules! impl_dht_tables {
    ($struct:ty, [$($field:ident),*$(,)?]) => {
        #[allow(unused_imports)]
        use $crate::ampc::dht_conn::DhtTable as _;

        impl $crate::ampc::dht_conn::DhtTables for $struct {
            fn drop_tables(&self) {
                $(self.$field.drop_table();)*
            }

            fn next(&self) -> Self {
                Self {
                    $($field: self.$field.next(),)*
                }
            }

            fn cleanup_prev_tables(&self) {
                $(
                    let tables = $crate::block_on(self.$field.client().all_tables()).unwrap();

                    for table in tables {
                        if table.as_str().starts_with(&self.$field.table().prefix()) {
                            $crate::block_on(self.$field.client().drop_table(table)).unwrap();
                        }
                    }
                )*
            }
        }
    };
}

use anyhow::anyhow;
use futures::{Stream, StreamExt};
pub(crate) use impl_dht_tables;

#[derive(serde::Serialize, serde::Deserialize, bincode::Encode, bincode::Decode, Clone, Debug)]
pub struct Table {
    prefix: String,
    round: u64,
}

impl Table {
    pub fn new<S: AsRef<str>>(prefix: S) -> Self {
        Self {
            prefix: prefix.as_ref().to_string(),
            round: 0,
        }
    }

    pub fn prefix(&self) -> &str {
        &self.prefix
    }

    fn dht(&self) -> dht::Table {
        format!("{}-{}", self.prefix, self.round).into()
    }

    fn next(&self) -> Self {
        Self {
            prefix: self.prefix.clone(),
            round: self.round + 1,
        }
    }
}

#[derive(Debug)]
pub struct DefaultDhtTable<K, V> {
    table: Table,
    client: dht::Client,
    _maker: std::marker::PhantomData<(K, V)>,
}

impl<K, V> bincode::Encode for DefaultDhtTable<K, V> {
    fn encode<E: bincode::enc::Encoder>(
        &self,
        encoder: &mut E,
    ) -> std::prelude::v1::Result<(), bincode::error::EncodeError> {
        self.table.encode(encoder)?;
        self.client.encode(encoder)
    }
}

impl<K, V> bincode::Decode for DefaultDhtTable<K, V> {
    fn decode<D: bincode::de::Decoder>(
        decoder: &mut D,
    ) -> std::prelude::v1::Result<Self, bincode::error::DecodeError> {
        let table = Table::decode(decoder)?;
        let client = dht::Client::decode(decoder)?;

        Ok(Self {
            table,
            client,
            _maker: std::marker::PhantomData,
        })
    }
}

impl<'de, K, V> bincode::BorrowDecode<'de> for DefaultDhtTable<K, V> {
    fn borrow_decode<D: bincode::de::BorrowDecoder<'de>>(
        decoder: &mut D,
    ) -> std::prelude::v1::Result<Self, bincode::error::DecodeError> {
        let table = Table::borrow_decode(decoder)?;
        let client = dht::Client::borrow_decode(decoder)?;

        Ok(Self {
            table,
            client,
            _maker: std::marker::PhantomData,
        })
    }
}

impl<K, V> Clone for DefaultDhtTable<K, V> {
    fn clone(&self) -> Self {
        Self {
            table: self.table.clone(),
            client: self.client.clone(),
            _maker: std::marker::PhantomData,
        }
    }
}
impl<K, V> DefaultDhtTable<K, V>
where
    K: KeyTrait,
    V: ValueTrait,
{
    pub fn new<S: AsRef<str>>(members: &[(dht::ShardId, SocketAddr)], prefix: S) -> Self {
        Self {
            table: Table::new(prefix),
            client: dht::Client::new(members),
            _maker: std::marker::PhantomData,
        }
    }

    pub fn shards(&self) -> &BTreeMap<dht::ShardId, dht::Shard> {
        self.client.shards()
    }
}

pub trait DhtTable: Clone + bincode::Encode + bincode::Decode {
    type Key: KeyTrait;
    type Value: ValueTrait;

    fn client(&self) -> &dht::Client;
    fn table(&self) -> &Table;
    fn next(&self) -> Self;

    fn get(&self, key: Self::Key) -> Option<Self::Value> {
        block_on(self.client().get(self.table().dht(), key.into()))
            .unwrap()
            .map(|v| {
                Self::Value::try_from(v)
                    .map_err(|_| anyhow!("unexpected value type in DHT table get"))
                    .unwrap()
            })
    }

    fn batch_get(&self, keys: Vec<Self::Key>) -> Vec<(Self::Key, Self::Value)> {
        let keys: Vec<dht::Key> = keys.into_iter().map(|k| k.into()).collect::<Vec<_>>();
        let values = block_on(self.client().batch_get(self.table().dht(), keys)).unwrap();

        values
            .into_iter()
            .map(|(k, v)| {
                let k = Self::Key::try_from(k)
                    .map_err(|_| anyhow!("unexpected key type in DHT table batch-get"))
                    .unwrap();

                let v = Self::Value::try_from(v)
                    .map_err(|_| anyhow!("unexpected value type in DHT table batch-get"))
                    .unwrap();

                (k, v)
            })
            .collect()
    }

    fn set(&self, key: Self::Key, value: Self::Value) {
        block_on(
            self.client()
                .set(self.table().dht(), key.into(), value.into()),
        )
        .unwrap();
    }

    fn batch_set(&self, pairs: Vec<(Self::Key, Self::Value)>) {
        let pairs: Vec<(dht::Key, dht::Value)> = pairs
            .into_iter()
            .map(|(k, v)| (k.into(), v.into()))
            .collect();

        block_on(self.client().batch_set(self.table().dht(), pairs)).unwrap();
    }

    fn num_keys(&self) -> u64 {
        block_on(self.client().num_keys(self.table().dht())).unwrap()
    }

    fn upsert<F: Into<UpsertEnum>>(
        &self,
        upsert: F,
        key: Self::Key,
        value: Self::Value,
    ) -> UpsertAction {
        block_on(
            self.client()
                .upsert(self.table().dht(), upsert, key.into(), value.into()),
        )
        .unwrap()
    }

    fn batch_upsert<F: Into<UpsertEnum> + Clone>(
        &self,
        upsert: F,
        pairs: Vec<(Self::Key, Self::Value)>,
    ) -> Vec<(Self::Key, UpsertAction)> {
        let pairs: Vec<(dht::Key, dht::Value)> = pairs
            .into_iter()
            .map(|(k, v)| (k.into(), v.into()))
            .collect();

        block_on(
            self.client()
                .batch_upsert(self.table().dht(), upsert, pairs),
        )
        .unwrap()
        .into_iter()
        .map(|(k, did_upsert)| {
            let k = k
                .try_into()
                .map_err(|_| anyhow!("unexpected key type in DHT table batch-upsert"))
                .unwrap();
            (k, did_upsert)
        })
        .collect()
    }

    fn init_from(&self, prev: &DefaultDhtTable<Self::Key, Self::Value>) {
        block_on(
            self.client()
                .clone_table(prev.table().dht(), self.table().dht()),
        )
        .unwrap();
    }

    fn drop_table(&self) {
        block_on(self.client().drop_table(self.table().dht())).unwrap();
    }

    fn raw_iter(&self) -> impl Iterator<Item = (dht::Key, dht::Value)> + '_ {
        let s = self.client().stream(self.table().dht());
        DhtTableIterator::new(s)
    }

    fn iter(&self) -> impl Iterator<Item = (Self::Key, Self::Value)> + '_ {
        self.raw_iter().map(|(key, value)| {
            let key = Self::Key::try_from(key)
                .map_err(|_| anyhow!("unexpected key type in DHT table iter"))
                .unwrap();

            let value = Self::Value::try_from(value)
                .map_err(|_| anyhow!("unexpected value type in DHT table iter"))
                .unwrap();

            (key, value)
        })
    }
}

struct DhtTableIterator<S> {
    stream: Pin<Box<S>>,
    batch: Vec<(dht::Key, dht::Value)>,
}

impl<S> DhtTableIterator<S> {
    fn new(stream: S) -> Self {
        Self {
            stream: Box::pin(stream),
            batch: Vec::new(),
        }
    }
}

impl<S> Iterator for DhtTableIterator<S>
where
    S: Stream<Item = Result<(dht::Key, dht::Value)>>,
{
    type Item = (dht::Key, dht::Value);

    fn next(&mut self) -> Option<Self::Item> {
        if self.batch.is_empty() {
            self.batch = block_on(iter_batch(&mut self.stream));
        }

        self.batch.pop()
    }
}

async fn iter_batch<S>(stream: &mut Pin<Box<S>>) -> Vec<(dht::Key, dht::Value)>
where
    S: Stream<Item = Result<(dht::Key, dht::Value)>>,
{
    let mut res = Vec::new();
    let mut count = 0;

    while let Some(item) = stream.next().await {
        match item {
            Ok((k, v)) => {
                res.push((k, v));
                count += 1;
            }
            Err(_) => break,
        }

        if count >= 1024 {
            break;
        }
    }

    res
}

impl<K, V> DhtTable for DefaultDhtTable<K, V>
where
    K: KeyTrait,

    V: ValueTrait,
{
    type Key = K;
    type Value = V;

    fn client(&self) -> &dht::Client {
        &self.client
    }

    fn table(&self) -> &Table {
        &self.table
    }

    fn next(&self) -> DefaultDhtTable<Self::Key, Self::Value> {
        let new = Self {
            table: self.table().next(),
            client: self.client().clone(),
            _maker: std::marker::PhantomData,
        };

        new.init_from(self);

        new
    }
}

#[derive(serde::Serialize, serde::Deserialize, bincode::Encode, bincode::Decode, Clone)]
pub struct DhtConn<T> {
    prev: T,
    next: T,
}

impl<T> DhtConn<T>
where
    T: DhtTables,
{
    pub fn new(initial: T) -> Self {
        let next = initial.next();

        Self {
            prev: initial,
            next,
        }
    }

    pub(super) fn cleanup_prev_tables(&self) {
        self.prev.cleanup_prev_tables();
    }

    pub(super) fn next_round(&mut self) {
        self.prev.drop_tables();
        self.prev = self.next.clone();

        self.next = self.prev.next();
    }

    pub fn prev(&self) -> &T {
        &self.prev
    }

    pub fn next(&self) -> &T {
        &self.next
    }

    pub fn take_prev(self) -> T {
        self.prev
    }
}

#[cfg(test)]
mod tests {
    use openraft::error::InitializeError;
    use tracing_test::traced_test;

    use self::dht::{upsert, BasicNode};

    use super::*;

    type Id = u64;
    type Counter = u64;

    #[derive(Clone, bincode::Encode, bincode::Decode)]
    struct Tables {
        id: DefaultDhtTable<Id, Counter>,
    }

    impl_dht_tables!(Tables, [id]);

    pub fn start_dht_background() -> SocketAddr {
        let (tx, rx) = crossbeam_channel::unbounded();
        std::thread::spawn(move || {
            let rt = tokio::runtime::Runtime::new().unwrap();
            rt.block_on(async {
                let (raft, server, addr) = dht::tests::server(1).await.unwrap();

                let members: BTreeMap<u64, _> = vec![(1, addr)]
                    .into_iter()
                    .map(|(id, addr)| (id, BasicNode::new(addr)))
                    .collect();

                if let Err(e) = raft.initialize(members.clone()).await {
                    match e {
                        openraft::error::RaftError::APIError(e) => match e {
                            InitializeError::NotAllowed(_) => {}
                            InitializeError::NotInMembers(_) => panic!("{:?}", e),
                        },
                        openraft::error::RaftError::Fatal(_) => panic!("{:?}", e),
                    }
                };

                tx.send(addr).unwrap();

                loop {
                    server.accept().await.unwrap();
                }
            })
        });

        rx.recv().unwrap()
    }

    #[test]
    #[traced_test]
    fn test_dht_conn() -> anyhow::Result<()> {
        let addr = start_dht_background();

        let tables = Tables {
            id: DefaultDhtTable::new(&[(1.into(), addr)], "id"),
        };

        tables.id.set(0, 0);

        assert_eq!(tables.id.get(0), Some(0));

        tables.id.batch_set(vec![(1, 0), (2, 0)]);

        let mut res = tables.id.batch_get(vec![1, 2]);
        res.sort_by(|(a, _), (b, _)| a.cmp(b));

        assert_eq!(res, vec![(1, 0), (2, 0)]);

        tables.id.upsert(upsert::U64Add, 0, 1);
        assert_eq!(tables.id.get(0), Some(1));

        tables.id.batch_upsert(upsert::U64Add, vec![(1, 1), (2, 1)]);

        let mut res = tables.id.batch_get(vec![0, 1, 2]);
        res.sort_by(|(a, _), (b, _)| a.cmp(b));

        assert_eq!(res, vec![(0, 1), (1, 1), (2, 1)]);

        Ok(())
    }
}