use std::sync::Arc;
use std::sync::atomic::{AtomicU64, Ordering};
use quick_cache::sync::Cache;
use quick_cache::{OptionsBuilder, Weighter};
const ASSUMED_BLOCK_LEN: u64 = 16 * 1024;
const MIN_ESTIMATED_ITEMS: usize = 16;
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub(crate) enum CacheItem {
Block(u32),
Meta {
kind: u32,
prefix_len: u16,
chunk: u32,
},
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub(crate) struct SegBlockKey {
pub segment_id: u64,
pub version: u32,
pub item: CacheItem,
}
#[derive(Clone)]
struct PayloadWeighter;
impl Weighter<SegBlockKey, Arc<[u8]>> for PayloadWeighter {
fn weight(&self, _key: &SegBlockKey, value: &Arc<[u8]>) -> u64 {
value.len() as u64
}
}
pub(crate) struct SegBlockCache {
inner: Option<Cache<SegBlockKey, Arc<[u8]>, PayloadWeighter>>,
hits: AtomicU64,
misses: AtomicU64,
meta_hits: AtomicU64,
meta_misses: AtomicU64,
}
impl SegBlockCache {
pub(crate) fn new(max_bytes: u64) -> Self {
let inner = (max_bytes > 0).then(|| {
let items = ((max_bytes / ASSUMED_BLOCK_LEN) as usize).max(MIN_ESTIMATED_ITEMS);
let options = OptionsBuilder::new()
.estimated_items_capacity(items)
.weight_capacity(max_bytes)
.shards(1)
.build()
.expect("valid block cache options");
Cache::with_options(
options,
PayloadWeighter,
Default::default(),
Default::default(),
)
});
Self {
inner,
hits: AtomicU64::new(0),
misses: AtomicU64::new(0),
meta_hits: AtomicU64::new(0),
meta_misses: AtomicU64::new(0),
}
}
pub(crate) fn get(&self, key: &SegBlockKey) -> Option<Arc<[u8]>> {
let found = self.inner.as_ref()?.get(key);
let counter = match (key.item, found.is_some()) {
(CacheItem::Block(_), true) => &self.hits,
(CacheItem::Block(_), false) => &self.misses,
(CacheItem::Meta { .. }, true) => &self.meta_hits,
(CacheItem::Meta { .. }, false) => &self.meta_misses,
};
counter.fetch_add(1, Ordering::Relaxed);
found
}
pub(crate) fn insert(&self, key: SegBlockKey, payload: Arc<[u8]>) {
if let Some(cache) = &self.inner {
cache.insert(key, payload);
}
}
pub(crate) fn weight(&self) -> u64 {
self.inner.as_ref().map_or(0, Cache::weight)
}
pub(crate) fn meta_hits(&self) -> u64 {
self.meta_hits.load(Ordering::Relaxed)
}
pub(crate) fn meta_misses(&self) -> u64 {
self.meta_misses.load(Ordering::Relaxed)
}
pub(crate) fn hits(&self) -> u64 {
self.hits.load(Ordering::Relaxed)
}
pub(crate) fn misses(&self) -> u64 {
self.misses.load(Ordering::Relaxed)
}
}
#[cfg(test)]
mod tests {
use super::*;
fn key(segment_id: u64, version: u32, block: u32) -> SegBlockKey {
SegBlockKey {
segment_id,
version,
item: CacheItem::Block(block),
}
}
fn payload(tag: u8, len: usize) -> Arc<[u8]> {
Arc::from(vec![tag; len])
}
#[test]
fn metadata_key_space_and_counters_are_independent_under_one_budget() {
let cache = SegBlockCache::new(1 << 20);
let block = key(1, 1, 0);
let mut meta = block;
meta.item = CacheItem::Meta {
kind: 2,
prefix_len: 0,
chunk: 0,
};
let mut prefix = meta;
prefix.item = CacheItem::Meta {
kind: 2,
prefix_len: 4,
chunk: 0,
};
let mut kind = meta;
kind.item = CacheItem::Meta {
kind: 3,
prefix_len: 0,
chunk: 0,
};
for k in [block, meta, prefix, kind] {
assert!(cache.get(&k).is_none());
}
for (i, k) in [block, meta, prefix, kind].into_iter().enumerate() {
cache.insert(k, payload(i as u8, 100));
}
for (i, k) in [block, meta, prefix, kind].into_iter().enumerate() {
assert_eq!(cache.get(&k).unwrap()[0], i as u8);
}
assert_eq!(
(
cache.hits(),
cache.misses(),
cache.meta_hits(),
cache.meta_misses()
),
(1, 1, 3, 3)
);
assert_eq!(cache.weight(), 400);
for n in 0..2_000 {
let mut k = meta;
k.item = CacheItem::Meta {
kind: 2,
prefix_len: 0,
chunk: n,
};
cache.insert(k, payload(1, 4096));
cache.insert(key(1, 1, n), payload(2, 4096));
}
assert!(cache.weight() <= 1 << 20);
}
#[test]
fn a_block_round_trips_and_counts_a_hit() {
let cache = SegBlockCache::new(1 << 20);
assert!(cache.get(&key(1, 1, 0)).is_none());
cache.insert(key(1, 1, 0), payload(7, 100));
assert_eq!(&*cache.get(&key(1, 1, 0)).unwrap(), &[7u8; 100][..]);
assert_eq!(cache.hits(), 1);
assert_eq!(cache.misses(), 1);
}
#[test]
fn every_part_of_the_key_matters() {
let cache = SegBlockCache::new(1 << 20);
cache.insert(key(1, 1, 0), payload(1, 10));
cache.insert(key(2, 1, 0), payload(2, 10));
cache.insert(key(1, 2, 0), payload(3, 10));
cache.insert(key(1, 1, 1), payload(4, 10));
assert_eq!(cache.get(&key(1, 1, 0)).unwrap()[0], 1);
assert_eq!(cache.get(&key(2, 1, 0)).unwrap()[0], 2);
assert_eq!(cache.get(&key(1, 2, 0)).unwrap()[0], 3);
assert_eq!(cache.get(&key(1, 1, 1)).unwrap()[0], 4);
}
#[test]
fn a_zero_budget_disables_the_cache() {
let cache = SegBlockCache::new(0);
cache.insert(key(1, 1, 0), payload(7, 100));
assert!(cache.get(&key(1, 1, 0)).is_none());
}
#[test]
fn the_budget_bounds_what_stays() {
let budget = 4u64 << 20;
let cache = SegBlockCache::new(budget);
for block in 0..64u32 {
cache.insert(key(1, 1, block), payload(block as u8, 1 << 20));
}
let kept: u64 = (0..64u32)
.filter_map(|block| cache.get(&key(1, 1, block)))
.map(|p| p.len() as u64)
.sum();
assert!(
kept <= budget,
"{kept} bytes kept under a budget of {budget}"
);
assert!(kept > 0, "the cache kept nothing");
}
#[test]
fn a_block_read_soon_after_insertion_outlives_blocks_never_read() {
const BLOCK: usize = 1024;
let cache = SegBlockCache::new(100 * BLOCK as u64);
for block in 0..200 {
cache.insert(key(1, 1, block), payload(0, BLOCK));
}
let x = key(2, 1, 0);
let y = key(2, 1, 1);
cache.insert(x, payload(1, BLOCK));
cache.insert(y, payload(2, BLOCK));
assert!(
cache.get(&x).is_some(),
"x was evicted by the next insertion"
);
for block in 0..200 {
cache.insert(key(3, 1, block), payload(3, BLOCK));
}
assert!(cache.get(&x).is_some(), "a block read again was evicted");
assert!(cache.get(&y).is_none(), "a block never read again stayed");
}
}