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/>.
//! On-disk key-value store designed for very read-heavy workloads without many small writes.
//! Lookups are O(k) where k is the size of the largest key.
//!
//! The design is loosely inspired by tantivy column store.
// TODO: When V is !Sized, there is no need to store the value in the blob store
// and therefore also not in the `BlobIndex`. This would save space.
// TODO: Handle the case when K is !Sized. I think this would currently crash fst mmap
// as one cannot mmap an empty file. All lookups should probably just return Ok(None) in this case.
use std::{
collections::BTreeMap,
ops::{Range, RangeBounds},
path::{Path, PathBuf},
};
use self::{
blob_id_index::{BlobIdIndex, BlobIdIndexWriter},
blob_index::{BlobIndex, BlobIndexWriter},
blob_store::{BlobStore, BlobStoreWriter},
segment::{Segment, SegmentWriter},
};
type Result<T, E = anyhow::Error> = std::result::Result<T, E>;
pub mod automaton;
mod blob_id_index;
mod blob_index;
mod blob_store;
mod segment;
mod serialized;
use file_store::{ConstSerializable, Peekable};
use segment::SortedSegments;
pub use serialized::{Serialized, SerializedRef};
struct BlobPointer {
key: Range<u64>,
value: Range<u64>,
}
impl BlobPointer {
const fn size() -> usize {
std::mem::size_of::<BlobPointer>()
}
fn as_bytes(&self) -> [u8; BlobPointer::size()] {
let mut res = [0; BlobPointer::size()];
let mut offset = 0;
for b in [
self.key.start,
self.key.end,
self.value.start,
self.value.end,
] {
let bytes = b.to_le_bytes();
res[offset..(bytes.len() + offset)].copy_from_slice(&bytes[..]);
offset += bytes.len();
}
res
}
fn from_bytes(bytes: [u8; BlobPointer::size()]) -> Self {
Self {
key: Range {
start: u64::from_le_bytes(bytes[0..8].try_into().unwrap()),
end: u64::from_le_bytes(bytes[8..16].try_into().unwrap()),
},
value: Range {
start: u64::from_le_bytes(bytes[16..24].try_into().unwrap()),
end: u64::from_le_bytes(bytes[24..32].try_into().unwrap()),
},
}
}
}
impl ConstSerializable for BlobPointer {
const BYTES: usize = Self::size();
fn serialize(&self, buf: &mut [u8]) {
buf.copy_from_slice(&self.as_bytes());
}
fn deserialize(buf: &[u8]) -> Self {
Self::from_bytes(buf.try_into().unwrap())
}
}
#[derive(Clone, Copy)]
struct BlobId(file_store::random_lookup::ItemId);
#[derive(Debug)]
struct LiveSegment<K, V> {
db: BTreeMap<Vec<u8>, Vec<u8>>,
_marker: std::marker::PhantomData<(K, V)>,
}
impl<K, V> Default for LiveSegment<K, V> {
fn default() -> Self {
Self::new()
}
}
impl<K, V> LiveSegment<K, V> {
fn new() -> Self {
Self {
db: BTreeMap::new(),
_marker: std::marker::PhantomData,
}
}
fn len(&self) -> usize {
self.db.len()
}
fn insert_raw<SerializedKey, SerializedVal>(&mut self, key: SerializedKey, value: SerializedVal)
where
SerializedKey: Into<Serialized<K>>,
SerializedVal: Into<Serialized<V>>,
{
let key: Serialized<K> = key.into();
let value: Serialized<V> = value.into();
self.db.insert(key.into(), value.into());
}
fn get_raw<'a, SerializedKey>(&'a self, key: SerializedKey) -> Option<SerializedRef<'a, V>>
where
SerializedKey: Into<SerializedRef<'a, K>>,
{
let key: SerializedRef<'a, K> = key.into();
self.db
.get(key.as_bytes())
.map(|v| SerializedRef::from(v.as_slice()))
}
fn iter(&self) -> impl Iterator<Item = (SerializedRef<'_, K>, SerializedRef<'_, V>)> {
self.db.iter().map(|(k, v)| {
(
SerializedRef::from(k.as_slice()),
SerializedRef::from(v.as_slice()),
)
})
}
fn store<P: AsRef<Path>>(self, uuid: uuid::Uuid, folder: P) -> Result<Segment<K, V>> {
if !folder.as_ref().exists() {
std::fs::create_dir_all(&folder)?;
}
let id_index = std::fs::OpenOptions::new()
.write(true)
.create(true)
.truncate(true)
.open(folder.as_ref().join(BlobIdIndex::<K>::file_name(uuid)))?;
let blob_index = std::fs::OpenOptions::new()
.write(true)
.create(true)
.truncate(true)
.open(folder.as_ref().join(BlobIndex::file_name(uuid)))?;
let store = std::fs::OpenOptions::new()
.write(true)
.create(true)
.truncate(true)
.open(folder.as_ref().join(BlobStore::<K, V>::file_name(uuid)))?;
let bloom = std::fs::OpenOptions::new()
.write(true)
.create(true)
.truncate(true)
.open(folder.as_ref().join(Segment::<K, V>::bloom_file_name(uuid)))?;
let writers = segment::Writers {
id_index: BlobIdIndexWriter::new(id_index)?,
blob_index: BlobIndexWriter::new(blob_index),
store: BlobStoreWriter::new(store),
bloom,
};
SegmentWriter::new(self.db.len(), writers).write_sorted_it(self.iter())?;
let res = Segment::open(uuid, folder)?;
Ok(res)
}
}
impl<K, V> LiveSegment<K, V>
where
K: bincode::Encode,
V: bincode::Encode,
{
fn insert(&mut self, key: K, value: V) -> Result<()> {
let key = Serialized::new(&key)?;
let value = Serialized::new(&value)?;
self.insert_raw(key, value);
Ok(())
}
}
#[derive(Debug, Clone, Default, serde::Serialize, serde::Deserialize)]
struct Meta {
segments: Vec<uuid::Uuid>,
}
pub struct Db<K, V> {
folder: PathBuf,
meta: Meta,
live_segment: LiveSegment<K, V>,
segments: Vec<Segment<K, V>>,
}
impl<K, V> Db<K, V> {
pub fn open_or_create<P: AsRef<Path>>(folder: P) -> Result<Self> {
let folder = folder.as_ref().to_path_buf();
if !folder.exists() {
std::fs::create_dir_all(&folder)?;
}
if !folder.is_dir() {
anyhow::bail!("Path is not a directory");
}
let meta_path = folder.join("meta.json");
let meta = if meta_path.exists() {
let meta = std::fs::read_to_string(&meta_path)?;
serde_json::from_str(&meta)?
} else {
Meta::default()
};
let segments = meta
.segments
.iter()
.map(|uuid| Segment::open(*uuid, &folder))
.collect::<Result<Vec<_>>>()?;
let s = Self {
folder,
meta,
live_segment: LiveSegment::default(),
segments,
};
s.save_meta()?;
Ok(s)
}
pub fn folder(&self) -> &Path {
&self.folder
}
pub fn uncommitted_inserts(&self) -> usize {
self.live_segment.len()
}
fn save_meta(&self) -> Result<()> {
let meta_path = self.folder.join("meta.json");
let meta = serde_json::to_string_pretty(&self.meta)?;
std::fs::write(meta_path, meta)?;
Ok(())
}
pub fn merge_all_segments(&mut self) -> Result<()> {
let segments = std::mem::take(&mut self.segments);
if let Some(new) = Segment::merge(segments, &self.folder)? {
self.meta.segments.clear();
self.meta.segments.push(new.uuid());
self.segments.push(new);
self.save_meta()?;
}
Ok(())
}
pub fn insert_raw<SerializedKey, SerializedVal>(
&mut self,
key: SerializedKey,
value: SerializedVal,
) where
SerializedKey: Into<Serialized<K>>,
SerializedVal: Into<Serialized<V>>,
{
self.live_segment.insert_raw(key, value);
}
pub fn get_raw_with_live<'a, SerializedKey>(
&'a self,
key: SerializedKey,
) -> Option<SerializedRef<'a, V>>
where
SerializedKey: Into<SerializedRef<'a, K>>,
{
let key: SerializedRef<'a, K> = key.into();
if let Some(value) = self.live_segment.get_raw(key) {
return Some(value);
}
self.segments
.iter()
.rev()
.find_map(|segment| segment.get_raw(key.as_bytes()).ok().flatten())
}
pub fn get_raw<'a, SerializedKey>(&'a self, key: SerializedKey) -> Option<SerializedRef<'a, V>>
where
SerializedKey: Into<SerializedRef<'a, K>>,
{
let key: SerializedRef<'a, K> = key.into();
self.segments
.iter()
.rev()
.find_map(|segment| segment.get_raw(key.as_bytes()).ok().flatten())
}
pub fn search_raw<'a, A>(
&'a self,
query: A,
) -> impl Iterator<Item = (SerializedRef<'a, K>, SerializedRef<'a, V>)> + 'a
where
A: fst::Automaton + Clone + 'a,
{
self.segments
.iter()
.rev()
.flat_map(move |segment| segment.search_raw(query.clone()))
}
pub fn range_raw<'a, R>(
&'a self,
range: R,
) -> impl Iterator<Item = (SerializedRef<'a, K>, SerializedRef<'a, V>)> + 'a
where
R: RangeBounds<SerializedRef<'a, K>> + Clone + 'a,
{
self.segments
.iter()
.rev()
.flat_map(move |segment| segment.range_raw(range.clone()))
}
pub fn commit(&mut self) -> Result<()> {
if self.live_segment.db.is_empty() {
return Ok(());
}
let uuid = uuid::Uuid::new_v4();
let live_segment = std::mem::take(&mut self.live_segment);
let segment = live_segment.store(uuid, &self.folder)?;
self.segments.push(segment);
self.meta.segments.push(uuid);
self.save_meta()?;
Ok(())
}
pub fn merge(&mut self, other: Self) -> Result<()> {
let other_folder = other.folder().to_path_buf();
for mut segment in other.segments {
segment.move_to(self.folder())?;
self.segments.push(segment);
}
self.meta.segments = self.segments.iter().map(|s| s.uuid()).collect();
self.save_meta()?;
std::fs::remove_dir_all(other_folder)?;
Ok(())
}
}
impl<K, V> Db<K, V>
where
K: Send + Sync,
V: Send + Sync,
{
pub fn iter_raw(
&self,
) -> impl Iterator<Item = (SerializedRef<'_, K>, SerializedRef<'_, V>)> + '_ {
self.segments.iter().flat_map(|segment| segment.iter_raw())
}
pub fn iter_raw_with_offset(
&self,
offset: u64,
) -> impl Iterator<Item = (SerializedRef<'_, K>, SerializedRef<'_, V>)> + '_ {
let mut remaining_offset = offset;
let mut segment_idx = 0;
let mut found_segment = false;
for (idx, segment) in self.segments.iter().enumerate() {
let segment_len = segment.len() as u64;
segment_idx = idx;
if remaining_offset < segment_len {
found_segment = true;
break;
}
remaining_offset -= segment_len;
}
if !found_segment {
segment_idx = self.segments.len();
}
self.segments
.iter()
.skip(segment_idx)
.flat_map(move |segment| {
let iter = segment.iter_raw_with_offset(remaining_offset);
remaining_offset = 0; // only offset into first segment
iter
})
}
pub fn sorted_iter_raw(
&self,
) -> impl Iterator<Item = (SerializedRef<'_, K>, SerializedRef<'_, V>)> + '_ {
SortedSegments::new(
self.segments
.iter()
.map(|s| Peekable::new(s.iter_raw()))
.collect(),
)
}
}
impl<K, V> Db<K, V>
where
K: bincode::Encode,
V: bincode::Encode,
{
pub fn insert(&mut self, key: K, value: V) -> Result<()> {
self.live_segment.insert(key, value)?;
Ok(())
}
}
impl<K, V> Db<K, V>
where
K: bincode::Encode,
V: bincode::Decode,
{
pub fn get(&self, key: &K) -> Result<Option<V>> {
let key = bincode::encode_to_vec(key, common::bincode_config())?;
match self.get_raw(key.as_slice()) {
Some(v) => {
let (v, _) = bincode::decode_from_slice(v.as_bytes(), common::bincode_config())?;
Ok(Some(v))
}
None => Ok(None),
}
}
}
impl<K, V> Db<K, V>
where
K: bincode::Decode,
V: bincode::Decode,
{
pub fn search<'a, A>(&'a self, query: A) -> impl Iterator<Item = (K, V)> + 'a
where
A: fst::Automaton + Clone + 'a,
{
self.search_raw(query).filter_map(|(k, v)| {
let (k, _) = bincode::decode_from_slice(k.as_bytes(), common::bincode_config()).ok()?;
let (v, _) = bincode::decode_from_slice(v.as_bytes(), common::bincode_config()).ok()?;
Some((k, v))
})
}
pub fn len(&self) -> usize {
self.segments.iter().map(|s| s.len()).sum()
}
pub fn is_empty(&self) -> bool {
self.segments.iter().all(|s| s.is_empty())
}
}
impl<K, V> Db<K, V>
where
K: bincode::Decode + Send + Sync,
V: bincode::Decode + Send + Sync,
{
pub fn iter(&self) -> impl Iterator<Item = (K, V)> + '_ {
self.iter_raw().filter_map(|(k, v)| {
let (k, _) = bincode::decode_from_slice(k.as_bytes(), common::bincode_config()).ok()?;
let (v, _) = bincode::decode_from_slice(v.as_bytes(), common::bincode_config()).ok()?;
Some((k, v))
})
}
pub fn iter_with_offset(&self, offset: u64) -> impl Iterator<Item = (K, V)> + '_ {
self.iter_raw_with_offset(offset).filter_map(|(k, v)| {
let (k, _) = bincode::decode_from_slice(k.as_bytes(), common::bincode_config()).ok()?;
let (v, _) = bincode::decode_from_slice(v.as_bytes(), common::bincode_config()).ok()?;
Some((k, v))
})
}
pub fn sorted_iter(&self) -> impl Iterator<Item = (K, V)> + '_ {
self.sorted_iter_raw().filter_map(|(k, v)| {
let (k, _) = bincode::decode_from_slice(k.as_bytes(), common::bincode_config()).ok()?;
let (v, _) = bincode::decode_from_slice(v.as_bytes(), common::bincode_config()).ok()?;
Some((k, v))
})
}
}
#[cfg(test)]
mod tests {
use super::*;
use file_store::gen_temp_dir;
#[test]
fn test_simple() {
let temp_dir = gen_temp_dir().unwrap();
let mut db = Db::open_or_create(&temp_dir).unwrap();
db.insert(1, 2).unwrap();
db.insert(2, 3).unwrap();
db.commit().unwrap();
assert_eq!(db.get(&1).unwrap(), Some(2));
assert_eq!(db.get(&2).unwrap(), Some(3));
}
#[test]
fn test_multiple_segments() {
let temp_dir = gen_temp_dir().unwrap();
let mut db = Db::open_or_create(&temp_dir).unwrap();
db.insert(1, 2).unwrap();
db.insert(2, 3).unwrap();
db.commit().unwrap();
db.insert(3, 4).unwrap();
db.insert(4, 5).unwrap();
db.commit().unwrap();
assert_eq!(db.get(&1).unwrap(), Some(2));
assert_eq!(db.get(&2).unwrap(), Some(3));
assert_eq!(db.get(&3).unwrap(), Some(4));
assert_eq!(db.get(&4).unwrap(), Some(5));
}
#[test]
fn test_segment_merge() {
let temp_dir = gen_temp_dir().unwrap();
let mut db = Db::open_or_create(&temp_dir).unwrap();
db.insert(1, 2).unwrap();
db.insert(2, 3).unwrap();
db.commit().unwrap();
db.insert(3, 4).unwrap();
db.insert(4, 5).unwrap();
db.commit().unwrap();
db.insert(5, 6).unwrap();
db.insert(6, 7).unwrap();
db.commit().unwrap();
db.merge_all_segments().unwrap();
assert_eq!(db.get(&1).unwrap(), Some(2));
assert_eq!(db.get(&2).unwrap(), Some(3));
assert_eq!(db.get(&3).unwrap(), Some(4));
assert_eq!(db.get(&4).unwrap(), Some(5));
assert_eq!(db.get(&5).unwrap(), Some(6));
assert_eq!(db.get(&6).unwrap(), Some(7));
}
#[test]
fn test_overwrite_key() {
let temp_dir = gen_temp_dir().unwrap();
let mut db = Db::open_or_create(&temp_dir).unwrap();
db.insert(1, 2).unwrap();
db.insert(1, 3).unwrap();
db.commit().unwrap();
assert_eq!(db.get(&1).unwrap(), Some(3));
db.insert(1, 4).unwrap();
db.commit().unwrap();
assert_eq!(db.get(&1).unwrap(), Some(4));
db.merge_all_segments().unwrap();
assert_eq!(db.get(&1).unwrap(), Some(4));
}
#[test]
fn test_len() {
let temp_dir = gen_temp_dir().unwrap();
let mut db = Db::open_or_create(&temp_dir).unwrap();
assert_eq!(db.len(), 0);
db.insert(1, 2).unwrap();
db.insert(2, 3).unwrap();
assert_eq!(db.len(), 0);
db.commit().unwrap();
assert_eq!(db.len(), 2);
}
#[test]
fn test_merge_db() {
let temp_dir = gen_temp_dir().unwrap();
let mut db1 = Db::open_or_create(&temp_dir.as_ref().join("db1")).unwrap();
let mut db2 = Db::open_or_create(&temp_dir.as_ref().join("db2")).unwrap();
db1.insert(1, 2).unwrap();
db1.insert(2, 3).unwrap();
db1.commit().unwrap();
db2.insert(3, 4).unwrap();
db2.insert(4, 5).unwrap();
db2.commit().unwrap();
db1.merge(db2).unwrap();
assert_eq!(db1.get(&1).unwrap(), Some(2));
assert_eq!(db1.get(&2).unwrap(), Some(3));
assert_eq!(db1.get(&3).unwrap(), Some(4));
assert_eq!(db1.get(&4).unwrap(), Some(5));
let path = db1.folder().to_path_buf();
drop(db1);
let db = Db::open_or_create(path).unwrap();
assert_eq!(db.get(&1).unwrap(), Some(2));
assert_eq!(db.get(&2).unwrap(), Some(3));
assert_eq!(db.get(&3).unwrap(), Some(4));
assert_eq!(db.get(&4).unwrap(), Some(5));
}
#[test]
fn test_iter_with_offset() {
let temp_dir = gen_temp_dir().unwrap();
let mut db = Db::open_or_create(&temp_dir).unwrap();
db.insert(1, 2).unwrap();
db.insert(2, 3).unwrap();
db.commit().unwrap();
db.insert(3, 4).unwrap();
db.insert(4, 5).unwrap();
db.insert(5, 6).unwrap();
db.commit().unwrap();
let res: Vec<_> = db.iter_with_offset(0).take(2).collect();
assert_eq!(res, vec![(1, 2), (2, 3)]);
let res: Vec<_> = db.iter_with_offset(1).take(2).collect();
assert_eq!(res, vec![(2, 3), (3, 4)]);
let res: Vec<_> = db.iter_with_offset(2).take(2).collect();
assert_eq!(res, vec![(3, 4), (4, 5)]);
let res: Vec<_> = db.iter_with_offset(3).take(2).collect();
assert_eq!(res, vec![(4, 5), (5, 6)]);
let res: Vec<_> = db.iter_with_offset(4).take(2).collect();
assert_eq!(res, vec![(5, 6)]);
let res: Vec<_> = db.iter_with_offset(5).take(2).collect();
assert_eq!(res, vec![]);
let res: Vec<_> = db.iter_with_offset(6).take(2).collect();
assert_eq!(res, vec![]);
}
}