web search done right
// 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/>.
//! Simple in-memory key-value store with Raft consensus where keys
//! and values are arbitrary bytes.
//!
//! It is intended to be deployed across multiple nodes
//! with multiple shards. Each shard cluster
//! is a Raft cluster, and each key is then routed to the correct
//! cluster based on hash(key) % number_of_shards. The keys
//! are currently *not* re-balanced if the number of shards change, so
//! if an entire shard becomes unavailable or a new shard is added, all
//! keys in the entire DHT is essentially lost as the
//! keys might hash incorrectly.
//!
//! Heavily inspired by https://github.com/datafuselabs/openraft/blob/main/examples/raft-kv-memstore/
mod client;
pub mod key;
pub mod log_store;
pub mod network;
pub mod store;
pub mod upsert;
pub mod value;
use network::api::{
AllTables, BatchSet, BatchUpsert, CloneTable, CreateTable, DropTable, Set, Upsert,
};
use std::fmt::Debug;
use std::io::Cursor;
use openraft::TokioRuntime;
pub use key::{Key, KeyTrait};
pub use value::{Value, ValueTrait};
pub use self::network::Server;
pub use network::api::RemoteClient;
pub use network::raft::RemoteClient as RaftClient;
pub use crate::distributed::member::ShardId;
pub use client::{Client, Shard};
pub use store::Table;
pub use upsert::*;
pub type NodeId = u64;
#[derive(
serde::Serialize,
serde::Deserialize,
bincode::Encode,
bincode::Decode,
Debug,
Clone,
PartialEq,
Eq,
Default,
)]
pub struct BasicNode {
pub addr: String,
}
impl BasicNode {
/// Creates as [`BasicNode`].
pub fn new(addr: impl ToString) -> Self {
Self {
addr: addr.to_string(),
}
}
}
openraft::declare_raft_types!(
/// Declare the type configuration for example K/V store.
pub TypeConfig:
D = Request,
R = Response,
NodeId = NodeId,
Node = BasicNode,
Entry = openraft::Entry<TypeConfig>,
SnapshotData = Cursor<Vec<u8>>,
AsyncRuntime = TokioRuntime,
);
macro_rules! raft_sonic_request_response {
($service:ident, [$($req:ident),*$(,)?]) => {
#[derive(::serde::Serialize, ::serde::Deserialize, ::bincode::Decode, Clone, Debug)]
pub enum Request {
$(
$req($req),
)*
}
#[derive(::serde::Serialize, ::serde::Deserialize, ::bincode::Encode, Clone, Debug)]
pub enum Response {
$(
$req(<$req as $crate::distributed::sonic::service::Message<$service>>::Response),
)*
Empty,
}
$(
impl From<$req> for Request {
fn from(req: $req) -> Self {
Request::$req(req)
}
}
)*
}
}
raft_sonic_request_response!(
Server,
[
Set,
BatchSet,
Upsert,
BatchUpsert,
CreateTable,
DropTable,
AllTables,
CloneTable
]
);
#[cfg(test)]
pub mod tests {
use super::{key::Key, value::Value};
use std::{collections::BTreeMap, net::SocketAddr, sync::Arc};
use tokio::sync::Mutex;
use tracing_test::traced_test;
use crate::{ampc::dht, distributed::sonic, free_socket_addr};
use openraft::{error::InitializeError, Config};
use proptest::prelude::*;
use futures::{pin_mut, TryStreamExt};
use rand::seq::SliceRandom;
use super::*;
pub async fn server(
id: u64,
) -> anyhow::Result<(
openraft::Raft<TypeConfig>,
sonic::service::Server<Server>,
SocketAddr,
)> {
let config = Config {
heartbeat_interval: 500,
election_timeout_min: 1500,
election_timeout_max: 3000,
..Default::default()
};
let config = Arc::new(config.validate().unwrap());
let log_store = log_store::LogStore::<TypeConfig>::default();
let state_machine_store = Arc::new(store::StateMachineStore::default());
let network = network::Network;
let raft = openraft::Raft::new(id, config, network, log_store, state_machine_store.clone())
.await?;
let addr = free_socket_addr();
let server = Server::new(raft.clone(), state_machine_store)
.bind(addr)
.await?;
Ok((raft, server, addr))
}
#[tokio::test]
#[traced_test]
async fn test_simple_set_get() -> anyhow::Result<()> {
let (raft1, server1, addr1) = server(1).await?;
let (_, server2, addr2) = server(2).await?;
let servers = vec![server1, server2];
for server in servers {
tokio::spawn(async move {
loop {
server.accept().await.unwrap();
}
});
}
let members: BTreeMap<u64, _> = vec![(1, addr1), (2, addr2)]
.into_iter()
.map(|(id, addr)| (id, BasicNode::new(addr)))
.collect();
if let Err(e) = raft1.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),
}
};
let c1 = RemoteClient::new(addr1);
let c2 = RemoteClient::new(addr2);
let table = Table::from("test");
c1.set(
table.clone(),
"hello".to_string().into(),
"world".to_string().into(),
)
.await?;
let res = c1.get(table.clone(), "hello".to_string().into()).await?;
assert_eq!(res, Some("world".to_string().into()));
c2.set(
table.clone(),
"ensure-linearized-read".to_string().into(),
().into(),
)
.await?;
tokio::time::sleep(std::time::Duration::from_secs(1)).await;
let res = c2.get(table.clone(), "hello".to_string().into()).await?;
assert_eq!(res, Some("world".to_string().into()));
c2.set(
table.clone(),
"hello".to_string().into(),
"world2".to_string().into(),
)
.await?;
c1.set(
table.clone(),
"ensure-linearized-read".to_string().into(),
().into(),
)
.await?;
tokio::time::sleep(std::time::Duration::from_secs(1)).await;
let res = c1.get(table.clone(), "hello".to_string().into()).await?;
assert_eq!(res, Some("world2".to_string().into()));
let res = c1.batch_get(table.clone(), vec![]).await?;
assert!(res.is_empty());
let res = c1
.batch_get(table.clone(), vec!["hello".to_string().into()])
.await?;
assert!(res.len() == 1);
let res = c1
.batch_get(table.clone(), vec!["non-existent-key".to_string().into()])
.await?;
assert!(res.is_empty());
Ok(())
}
#[tokio::test]
#[traced_test]
async fn test_member_join() -> anyhow::Result<()> {
let (raft1, server1, addr1) = server(1).await?;
let (_, server2, addr2) = server(2).await?;
let (_, server3, addr3) = server(3).await?;
let servers = vec![server1, server2, server3];
for server in servers {
tokio::spawn(async move {
loop {
server.accept().await.unwrap();
}
});
}
let members: BTreeMap<u64, _> = vec![(1, addr1)]
.into_iter()
.map(|(id, addr)| (id, BasicNode::new(addr)))
.collect();
if let Err(e) = raft1.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),
}
};
let rc1 = network::raft::RemoteClient::new(addr1).await?;
rc1.join(2, addr2).await?;
let c1 = RemoteClient::new(addr1);
let c2 = RemoteClient::new(addr2);
let table = Table::from("test");
c1.set(
table.clone(),
"hello".to_string().into(),
"world".to_string().into(),
)
.await?;
c2.set(
table.clone(),
"ensure-linearized-read".to_string().into(),
().into(),
)
.await?;
tokio::time::sleep(std::time::Duration::from_secs(1)).await;
let res = c2.get(table.clone(), "hello".to_string().into()).await?;
assert_eq!(res, Some("world".to_string().into()));
rc1.join(3, addr3).await?;
tokio::time::sleep(std::time::Duration::from_secs(1)).await; // join is not blocking
let c3 = RemoteClient::new(addr3);
let res = c3.get(table.clone(), "hello".to_string().into()).await?;
assert_eq!(res, Some("world".to_string().into()));
Ok(())
}
#[tokio::test]
#[traced_test]
async fn test_stream() -> anyhow::Result<()> {
let (raft, server, addr) = server(1).await?;
let servers = vec![server];
for server in servers {
tokio::spawn(async move {
loop {
server.accept().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),
}
};
let client = dht::client::Node::new(addr);
let table = Table::from("test");
client
.set(
table.clone(),
"hello".to_string().into(),
"world".to_string().into(),
)
.await?;
client
.set(
table.clone(),
"hello2".to_string().into(),
"world2".to_string().into(),
)
.await?;
let stream = client.stream(table.clone());
pin_mut!(stream);
let mut res = Vec::new();
while let Some((k, v)) = stream.try_next().await? {
res.push((k, v));
}
res.sort_by_key(|(k, _)| k.clone());
assert_eq!(
res,
vec![
("hello".to_string().into(), "world".to_string().into()),
("hello2".to_string().into(), "world2".to_string().into()),
]
);
let table = Table::from("test2");
const N: u64 = 100_000;
client
.batch_set(
table.clone(),
(0..N)
.map(|i| (i.into(), i.into()))
.collect::<Vec<(Key, Value)>>(),
)
.await?;
let stream = client.stream(table.clone());
pin_mut!(stream);
let mut res = Vec::new();
while let Some((k, v)) = stream.try_next().await? {
res.push((k, v));
}
res.sort_by_key(|(k, _)| k.clone());
assert_eq!(res.len(), N as usize);
for (i, r) in res.into_iter().enumerate() {
let i = i as u64;
assert_eq!(r, (i.into(), i.into(),));
}
Ok(())
}
#[tokio::test]
#[traced_test]
#[ignore = "comitted logs must be stored in stable storage for raft to be able to recover from a node crash"]
// see: https://docs.rs/openraft/latest/openraft/docs/faq/index.html#what-will-happen-when-data-gets-lost
async fn test_node_crash() -> anyhow::Result<()> {
let (raft1, server1, addr1) = server(1).await?;
let (raft2, server2, addr2) = server(2).await?;
let servers = vec![server1, server2];
let mut handles = Vec::new();
for server in servers {
handles.push(tokio::spawn(async move {
loop {
server.accept().await.unwrap();
}
}));
}
let members: BTreeMap<u64, _> = vec![(1, addr1)]
.into_iter()
.map(|(id, addr)| (id, BasicNode::new(addr)))
.collect();
if let Err(e) = raft1.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),
}
};
let rc1 = network::raft::RemoteClient::new(addr1).await?;
rc1.join(2, addr2).await?;
let c1 = RemoteClient::new(addr1);
let table = Table::from("test");
c1.set(
table.clone(),
"hello".to_string().into(),
"world".to_string().into(),
)
.await?;
let res = c1.get(table.clone(), "hello".to_string().into()).await?;
assert_eq!(res, Some("world".to_string().into()));
// crash node 2
tracing::info!("crashing node 2");
handles[1].abort();
drop(raft2);
let (raft2, server2, addr2) = server(2).await?;
handles[1] = tokio::spawn(async move {
loop {
server2.accept().await.unwrap();
}
});
rc1.join(2, addr2).await?;
tokio::time::sleep(std::time::Duration::from_secs(1)).await;
let c2 = RemoteClient::new(addr2);
let res = c2.get(table.clone(), "hello".to_string().into()).await?;
assert_eq!(res, Some("world".to_string().into()));
// crash node 2 again
tracing::info!("crashing node 2 again");
handles[1].abort();
drop(raft2);
c1.set(
table.clone(),
"hello".to_string().into(),
"world2".to_string().into(),
)
.await?;
let (_raft2, server2, addr2) = server(2).await?;
handles[1] = tokio::spawn(async move {
loop {
server2.accept().await.unwrap();
}
});
rc1.join(2, addr2).await?;
tokio::time::sleep(std::time::Duration::from_secs(1)).await;
let c2 = RemoteClient::new(addr2);
let res = c2.get(table.clone(), "hello".to_string().into()).await?;
assert_eq!(res, Some("world2".to_string().into()));
Ok(())
}
#[derive(
Debug,
Clone,
serde::Serialize,
serde::Deserialize,
bincode::Encode,
bincode::Decode,
PartialEq,
)]
enum Action {
Set { key: String, value: String },
// get actions[prev_key % actions.len()]
// if actions[prev_key % actions.len()] is a get, then get a non-existent key
Get { prev_key: usize },
}
impl Arbitrary for Action {
type Parameters = ();
type Strategy = BoxedStrategy<Self>;
fn arbitrary_with(_args: ()) -> Self::Strategy {
prop_oneof![
(".{1,10}", ".{1,10}").prop_map(|(key, value)| Action::Set { key, value }),
(0..1000).prop_map(|prev_key| Action::Get {
prev_key: prev_key as usize
}),
]
.boxed()
}
}
proptest! {
#![proptest_config(ProptestConfig::with_cases(10))]
#[test]
#[traced_test]
fn proptest_chaos(actions: Vec<Action>) {
let ground_truth = Arc::new(Mutex::new(BTreeMap::<String, String>::new()));
tokio::runtime::Builder::new_multi_thread()
.enable_all()
.build()
.unwrap()
.block_on(async move {
let (raft1, server1, addr1) = server(1).await.unwrap();
let (raft2, server2, addr2) = server(2).await.unwrap();
let servers = vec![server1, server2];
let mut handles = Vec::new();
for server in servers {
handles.push(tokio::spawn(async move {
loop {
server.accept().await.unwrap();
}
}));
}
let members: BTreeMap<u64, _> = vec![(1, addr1), (2, addr2)]
.into_iter()
.map(|(id, addr)| (id, BasicNode::new(addr)))
.collect();
if let Err(e) = raft1.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),
}
};
if let Err(e) = raft2.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),
}
};
let c1 = RemoteClient::new(addr1);
let c2 = RemoteClient::new(addr2);
let clients = Arc::new(vec![c1, c2]);
let shared_actions = Arc::new(actions.clone());
let table = Table::from("test");
for (i, action) in actions.into_iter().enumerate() {
match action {
Action::Set { key, value } => {
let client = clients.choose(&mut rand::thread_rng()).unwrap();
client.set(table.clone(), key.clone().into(), value.clone().into()).await.unwrap();
ground_truth.lock().await.insert(key.clone(), value.clone());
}
Action::Get { prev_key } => {
let client = clients.choose(&mut rand::thread_rng()).unwrap();
client.set(table.clone(), "ensure-linearized-read".to_string().into(), ().into()).await.unwrap();
let key = if i == 0 {
"non-existent-key".to_string()
} else {
match shared_actions[prev_key % i] {
Action::Set { ref key, .. } => {
key.clone()
},
Action::Get { .. } => "non-existent-key".to_string(),
}
};
let res = client.get(table.clone(), key.clone().into()).await.unwrap();
let expected = ground_truth.lock().await.get(&key).cloned();
assert_eq!(res.map(|v| v.try_into().unwrap()), expected);
}
}
}
});
}
}
}