use std::collections::HashMap;
use std::hash::Hash;
use std::io::Read;
use std::path::PathBuf;
use std::sync::{Arc, Mutex, MutexGuard};
use durability::{Directory, PersistenceError, PersistenceResult};
use serde::de::DeserializeOwned;
use crate::{try_index_name, SegmentCatalog, SegmentedStore, SidecarEnvelope, Store, View};
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct LiveIds<Id> {
ids: Vec<Id>,
}
impl<Id: Ord> LiveIds<Id> {
pub fn new(ids: impl IntoIterator<Item = Id>) -> Self {
let mut ids: Vec<Id> = ids.into_iter().collect();
ids.sort_unstable();
ids.dedup();
Self { ids }
}
pub fn as_slice(&self) -> &[Id] {
&self.ids
}
pub fn len(&self) -> usize {
self.ids.len()
}
pub fn is_empty(&self) -> bool {
self.ids.is_empty()
}
pub fn contains(&self, id: &Id) -> bool {
self.ids.binary_search(id).is_ok()
}
pub fn iter(&self) -> std::slice::Iter<'_, Id> {
self.ids.iter()
}
}
impl<Id: Ord> FromIterator<Id> for LiveIds<Id> {
fn from_iter<I: IntoIterator<Item = Id>>(iter: I) -> Self {
Self::new(iter)
}
}
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct SidecarKey<Id> {
segment_id: u64,
live_ids: LiveIds<Id>,
}
impl<Id> SidecarKey<Id> {
pub fn new(segment_id: u64, live_ids: LiveIds<Id>) -> Self {
Self {
segment_id,
live_ids,
}
}
pub fn segment_id(&self) -> u64 {
self.segment_id
}
pub fn live_ids(&self) -> &LiveIds<Id> {
&self.live_ids
}
}
pub trait SidecarCodec {
type Id: Clone + Ord + Hash;
type Index;
fn magic(&self) -> &[u8; 8];
fn version(&self) -> u32;
fn kind(&self) -> &str;
fn recipe(&self) -> &str;
fn encode(&self, index: &Self::Index) -> Option<Vec<u8>>;
fn decode(&self, payload: &[u8]) -> Option<Self::Index>;
fn accepts(&self, index: &Self::Index, live: &LiveIds<Self::Id>) -> bool;
}
pub trait SidecarHost {
fn sidecar_dir(&self) -> &Arc<dyn Directory>;
fn try_sidecar_name(&self, segment_id: u64, kind: &str) -> PersistenceResult<String>;
fn sidecar_name(&self, segment_id: u64, kind: &str) -> String {
self.try_sidecar_name(segment_id, kind)
.unwrap_or_else(|e| panic!("invalid segstore sidecar name: {e}"))
}
fn sidecar_file_path(&self, segment_id: u64, kind: &str) -> PersistenceResult<Option<PathBuf>> {
let name = self.try_sidecar_name(segment_id, kind)?;
Ok(self.sidecar_dir().file_path(&name))
}
fn sidecar_exists(&self, name: &str) -> bool {
self.sidecar_dir().exists(name)
}
fn read_sidecar(&self, name: &str) -> PersistenceResult<Option<Vec<u8>>> {
let dir = self.sidecar_dir();
if !dir.exists(name) {
return Ok(None);
}
let mut file = dir.open_file(name)?;
let mut bytes = Vec::new();
file.read_to_end(&mut bytes)?;
Ok(Some(bytes))
}
fn write_sidecar(&self, name: &str, bytes: &[u8]) -> PersistenceResult<()> {
self.sidecar_dir().atomic_write(name, bytes)
}
fn delete_sidecar(&self, name: &str) -> PersistenceResult<()> {
let dir = self.sidecar_dir();
if dir.exists(name) {
dir.delete(name)?;
}
Ok(())
}
}
impl<S: Store> SidecarHost for SegmentedStore<S> {
fn sidecar_dir(&self) -> &Arc<dyn Directory> {
self.dir()
}
fn try_sidecar_name(&self, segment_id: u64, kind: &str) -> PersistenceResult<String> {
self.try_index_name(segment_id, kind)
}
}
impl<Id> SidecarHost for SegmentCatalog<Id>
where
Id: Eq + Hash + DeserializeOwned,
{
fn sidecar_dir(&self) -> &Arc<dyn Directory> {
self.dir()
}
fn try_sidecar_name(&self, segment_id: u64, kind: &str) -> PersistenceResult<String> {
self.try_index_name(segment_id, kind)
}
}
impl<S: Store> SidecarHost for View<S> {
fn sidecar_dir(&self) -> &Arc<dyn Directory> {
self.dir()
}
fn try_sidecar_name(&self, segment_id: u64, kind: &str) -> PersistenceResult<String> {
if self.segment_ids().binary_search(&segment_id).is_err() {
return Err(PersistenceError::NotFound(format!(
"segment id {segment_id} is not in this view"
)));
}
try_index_name(segment_id, kind)
}
}
pub struct SidecarCache<C: SidecarCodec> {
codec: C,
entries: Mutex<EntryMap<C::Id, C::Index>>,
}
type EntryMap<Id, Index> = HashMap<SidecarKey<Id>, Arc<Index>>;
type Entry<Id, Index> = (SidecarKey<Id>, Arc<Index>);
impl<C: SidecarCodec> SidecarCache<C> {
pub fn new(codec: C) -> Self {
Self {
codec,
entries: Mutex::new(HashMap::new()),
}
}
pub fn codec(&self) -> &C {
&self.codec
}
pub fn len(&self) -> usize {
self.entries().len()
}
pub fn is_empty(&self) -> bool {
self.entries().is_empty()
}
pub fn contains(&self, key: &SidecarKey<C::Id>) -> bool {
self.entries().contains_key(key)
}
pub fn get_or_build<H, F>(
&self,
host: &H,
key: SidecarKey<C::Id>,
build: F,
) -> Option<Arc<C::Index>>
where
H: SidecarHost,
F: FnOnce() -> Option<C::Index>,
{
let mut entries = self.entries();
if let Some(hit) = entries.get(&key) {
return Some(hit.clone());
}
if let Some(index) = self.load(host, &key) {
let index = Arc::new(index);
Self::insert(&mut entries, key, index.clone());
return Some(index);
}
let index = Arc::new(build()?);
Self::insert(&mut entries, key, index.clone());
Some(index)
}
pub fn invalidate<H: SidecarHost>(&self, host: &H, segment_id: u64) -> PersistenceResult<()> {
self.entries()
.retain(|key, _| key.segment_id() != segment_id);
let name = host.try_sidecar_name(segment_id, self.codec.kind())?;
host.delete_sidecar(&name)
}
pub fn retain(&self, segment_ids: &[u64]) {
self.entries()
.retain(|key, _| segment_ids.contains(&key.segment_id()));
}
pub fn persist<H: SidecarHost>(
&self,
host: &H,
key: &SidecarKey<C::Id>,
) -> PersistenceResult<bool> {
let Some(index) = self.entries().get(key).cloned() else {
return Ok(false);
};
let bytes = self.encode_envelope(key, &index)?;
let name = host.try_sidecar_name(key.segment_id(), self.codec.kind())?;
host.write_sidecar(&name, &bytes)?;
Ok(true)
}
pub fn persist_missing<H: SidecarHost>(
&self,
host: &H,
segment_ids: &[u64],
) -> PersistenceResult<usize> {
let pending: Vec<Entry<C::Id, C::Index>> = {
let entries = self.entries();
entries
.iter()
.filter(|(key, _)| segment_ids.contains(&key.segment_id()))
.map(|(key, index)| (key.clone(), index.clone()))
.collect()
};
let mut written = 0;
for (key, index) in pending {
let name = host.try_sidecar_name(key.segment_id(), self.codec.kind())?;
if host.sidecar_exists(&name) {
continue;
}
let bytes = self.encode_envelope(&key, &index)?;
host.write_sidecar(&name, &bytes)?;
written += 1;
}
Ok(written)
}
fn load<H: SidecarHost>(&self, host: &H, key: &SidecarKey<C::Id>) -> Option<C::Index> {
let name = host
.try_sidecar_name(key.segment_id(), self.codec.kind())
.ok()?;
let bytes = host.read_sidecar(&name).ok()??;
let payload = SidecarEnvelope::decode(
self.codec.magic(),
self.codec.version(),
key.segment_id(),
self.codec.recipe().as_bytes(),
&bytes,
)
.ok()?;
let index = self.codec.decode(payload)?;
self.codec.accepts(&index, key.live_ids()).then_some(index)
}
fn encode_envelope(
&self,
key: &SidecarKey<C::Id>,
index: &C::Index,
) -> PersistenceResult<Vec<u8>> {
let payload = self.codec.encode(index).ok_or_else(|| {
PersistenceError::InvalidConfig(format!(
"sidecar codec {:?} could not encode segment {}",
self.codec.kind(),
key.segment_id()
))
})?;
SidecarEnvelope::encode(
self.codec.magic(),
self.codec.version(),
key.segment_id(),
self.codec.recipe().as_bytes(),
&payload,
)
}
fn insert(
entries: &mut EntryMap<C::Id, C::Index>,
key: SidecarKey<C::Id>,
index: Arc<C::Index>,
) {
let segment_id = key.segment_id();
entries.retain(|existing, _| existing.segment_id() != segment_id);
entries.insert(key, index);
}
fn entries(&self) -> MutexGuard<'_, EntryMap<C::Id, C::Index>> {
self.entries.lock().unwrap_or_else(|e| e.into_inner())
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::sync::atomic::{AtomicUsize, Ordering};
use std::sync::Barrier;
use durability::MemoryDirectory;
use crate::DefaultStore;
struct IdListCodec;
impl SidecarCodec for IdListCodec {
type Id = u32;
type Index = Vec<u32>;
fn magic(&self) -> &[u8; 8] {
b"TOYIDX01"
}
fn version(&self) -> u32 {
1
}
fn kind(&self) -> &str {
"toy"
}
fn recipe(&self) -> &str {
"u32-id-list-v1"
}
fn encode(&self, index: &Self::Index) -> Option<Vec<u8>> {
Some(index.iter().flat_map(|id| id.to_le_bytes()).collect())
}
fn decode(&self, payload: &[u8]) -> Option<Self::Index> {
if payload.len() % 4 != 0 {
return None;
}
Some(
payload
.chunks_exact(4)
.map(|c| u32::from_le_bytes([c[0], c[1], c[2], c[3]]))
.collect(),
)
}
fn accepts(&self, index: &Self::Index, live: &LiveIds<u32>) -> bool {
index.as_slice() == live.as_slice()
}
}
fn sealed_store() -> (
Arc<dyn Directory>,
SegmentedStore<DefaultStore<u32, String>>,
) {
let dir = MemoryDirectory::arc();
let mut store =
SegmentedStore::open(dir.clone(), DefaultStore::<u32, String>::new(), 2).unwrap();
store.add(1, "a".into()).unwrap();
store.add(2, "b".into()).unwrap();
store.checkpoint().unwrap();
(dir, store)
}
fn key(segment_id: u64, ids: &[u32]) -> SidecarKey<u32> {
SidecarKey::new(segment_id, LiveIds::new(ids.iter().copied()))
}
struct DirHost {
dir: Arc<dyn Directory>,
}
impl SidecarHost for DirHost {
fn sidecar_dir(&self) -> &Arc<dyn Directory> {
&self.dir
}
fn try_sidecar_name(&self, segment_id: u64, kind: &str) -> PersistenceResult<String> {
try_index_name(segment_id, kind)
}
}
#[test]
fn toy_codec_round_trips_through_a_store_host() {
let (_dir, store) = sealed_store();
let seg = store.segment_ids()[0];
let live = store.live_ids(seg).expect("default store lists ids");
assert_eq!(live.as_slice(), &[1, 2]);
let cache = SidecarCache::new(IdListCodec);
let mut builds = 0;
let built = cache
.get_or_build(&store, key(seg, &[1, 2]), || {
builds += 1;
Some(live.as_slice().to_vec())
})
.expect("built");
assert_eq!(built.as_slice(), &[1, 2]);
assert_eq!(cache.persist_missing(&store, &[seg]).unwrap(), 1);
let reopened = SidecarCache::new(IdListCodec);
let loaded = reopened
.get_or_build(&store, key(seg, &[1, 2]), || {
builds += 1;
None
})
.expect("loaded from the persisted sidecar");
assert_eq!(loaded.as_slice(), &[1, 2]);
assert_eq!(builds, 1, "the persisted sidecar was loaded, not rebuilt");
}
#[test]
fn stale_live_ids_invalidate_and_rebuild_once() {
let (_dir, store) = sealed_store();
let seg = store.segment_ids()[0];
let cache = SidecarCache::new(IdListCodec);
let mut builds = 0;
cache
.get_or_build(&store, key(seg, &[1, 2]), || {
builds += 1;
Some(vec![1, 2])
})
.unwrap();
assert_eq!(cache.persist_missing(&store, &[seg]).unwrap(), 1);
let rebuilt = cache
.get_or_build(&store, key(seg, &[1]), || {
builds += 1;
Some(vec![1])
})
.unwrap();
assert_eq!(builds, 2, "the stale sidecar was rejected and rebuilt once");
assert_eq!(rebuilt.as_slice(), &[1]);
assert_eq!(cache.len(), 1, "the stale entry is replaced, not kept");
assert!(!cache.contains(&key(seg, &[1, 2])));
let hit = cache
.get_or_build(&store, key(seg, &[1]), || {
builds += 1;
None
})
.unwrap();
assert_eq!(hit.as_slice(), &[1]);
assert_eq!(builds, 2, "the rebuilt entry is served from memory");
}
#[test]
fn retain_evicts_entries_for_deleted_segments() {
let (_dir, store) = sealed_store();
let cache = SidecarCache::new(IdListCodec);
for seg in [0, 1, 2] {
cache
.get_or_build(&store, key(seg, &[1]), || Some(vec![1]))
.unwrap();
}
assert_eq!(cache.len(), 3);
cache.retain(&[0, 2]);
assert_eq!(cache.len(), 2);
assert!(cache.contains(&key(0, &[1])));
assert!(!cache.contains(&key(1, &[1])));
assert!(cache.contains(&key(2, &[1])));
}
#[test]
fn persist_missing_writes_only_absent_entries() {
let (_dir, store) = sealed_store();
let seg = store.segment_ids()[0];
let cache = SidecarCache::new(IdListCodec);
cache
.get_or_build(&store, key(seg, &[1, 2]), || Some(vec![1, 2]))
.unwrap();
let name = store.sidecar_name(seg, "toy");
store.write_sidecar(&name, b"present").unwrap();
assert_eq!(
cache.persist_missing(&store, &[seg, seg + 1]).unwrap(),
0,
"a present sidecar is never overwritten"
);
assert_eq!(store.read_sidecar(&name).unwrap().unwrap(), b"present");
store.delete_sidecar(&name).unwrap();
assert_eq!(
cache.persist_missing(&store, &[seg, seg + 1]).unwrap(),
1,
"only the cached entry for a listed segment is written"
);
let written = store.read_sidecar(&name).unwrap().expect("sidecar");
let payload = SidecarEnvelope::decode(b"TOYIDX01", 1, seg, b"u32-id-list-v1", &written)
.expect("valid envelope");
assert_eq!(payload, &[1, 0, 0, 0, 2, 0, 0, 0]);
}
#[test]
fn invalidate_drops_the_entry_and_the_persisted_file() {
let (_dir, store) = sealed_store();
let seg = store.segment_ids()[0];
let cache = SidecarCache::new(IdListCodec);
cache
.get_or_build(&store, key(seg, &[1, 2]), || Some(vec![1, 2]))
.unwrap();
assert_eq!(cache.persist_missing(&store, &[seg]).unwrap(), 1);
cache.invalidate(&store, seg).unwrap();
assert!(cache.is_empty());
assert!(!store.sidecar_exists(&store.sidecar_name(seg, "toy")));
let mut rebuilt = 0;
cache
.get_or_build(&store, key(seg, &[1, 2]), || {
rebuilt += 1;
Some(vec![1, 2])
})
.unwrap();
assert_eq!(rebuilt, 1, "an invalidated key rebuilds exactly once");
}
#[test]
fn concurrent_get_or_build_on_one_key_builds_once() {
let host = DirHost {
dir: MemoryDirectory::arc(),
};
let cache = SidecarCache::new(IdListCodec);
let builds = AtomicUsize::new(0);
let barrier = Barrier::new(8);
let handles: Vec<Arc<Vec<u32>>> = std::thread::scope(|scope| {
let spawned: Vec<_> = (0..8)
.map(|_| {
let cache = &cache;
let host = &host;
let builds = &builds;
let barrier = &barrier;
scope.spawn(move || {
barrier.wait();
cache
.get_or_build(host, key(0, &[1, 2]), || {
builds.fetch_add(1, Ordering::SeqCst);
Some(vec![1, 2])
})
.expect("built once")
})
})
.collect();
spawned
.into_iter()
.map(|handle| handle.join().unwrap())
.collect()
});
assert_eq!(builds.load(Ordering::SeqCst), 1);
assert!(
handles
.iter()
.all(|handle| Arc::ptr_eq(handle, &handles[0])),
"every caller receives the same cached index"
);
assert_eq!(cache.len(), 1);
}
#[test]
fn catalog_and_view_hosts_name_the_same_sidecar() {
let (dir, store) = sealed_store();
let seg = store.segment_ids()[0];
let expected = store.sidecar_name(seg, "toy");
let catalog = SegmentCatalog::<u32>::open(dir).unwrap();
assert_eq!(catalog.sidecar_name(seg, "toy"), expected);
let view = store.reader().view();
assert_eq!(view.sidecar_name(seg, "toy"), expected);
assert_eq!(view.live_ids(seg, [2, 1, 2]).as_slice(), &[1, 2]);
let missing = view.try_sidecar_name(seg + 99, "toy").unwrap_err();
assert!(missing.to_string().contains("not in this view"));
}
}