1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
//! Decoded value cache for the VarTyped collections (roadmap T4).
//!
//! Sibling of [`crate::value_cache`]: same physical key, but the value is a
//! decoded `Arc<T>` instead of raw bytes, so a hit skips both the byte copy and
//! the codec. `(file_id, offset)` is never reused for different bytes, so an
//! entry is implicitly invalidated by an update, a delete or a compaction — the
//! node simply stops pointing at it and it ages out.
//!
//! Spec: `docs/superpowers/specs/26-08-04-decoded-value-cache.md`.
use std::sync::Arc;
use quick_cache::Weighter;
use quick_cache::sync::Cache;
use crate::config::CacheConfig;
use crate::value_cache::ValueKey;
/// A decoded value plus the encoded length it came from.
///
/// The length rides in the value, not in [`ValueKey`], because the weighter only
/// sees `(&key, &val)` and `ValueKey` deliberately omits the length — length is
/// not part of version identity (see `VarTree::read_value_cached_result`).
pub(crate) struct DecodedEntry<T> {
pub(crate) value: Arc<T>,
pub(crate) encoded_len: u32,
}
// Manual, **not** `#[derive(Clone)]`: the derive emits `impl<T: Clone>`, and
// `T: Clone` is exactly the bound this cache exists to avoid. `quick_cache`
// requires `Val: Clone`, and cloning the entry must cost one `Arc` clone.
impl<T> Clone for DecodedEntry<T> {
fn clone(&self) -> Self {
Self {
value: Arc::clone(&self.value),
encoded_len: self.encoded_len,
}
}
}
#[derive(Clone)]
struct DecodedWeighter;
impl<T> Weighter<ValueKey, DecodedEntry<T>> for DecodedWeighter {
fn weight(&self, _key: &ValueKey, value: &DecodedEntry<T>) -> u64 {
// Strictly positive on purpose: `quick_cache` ignores zero-weight items
// when looking for eviction candidates, and this cache has no removal
// path, so a legal zero-byte encoding would otherwise accumulate past
// `max_size` forever.
u64::from(value.encoded_len).max(1)
}
}
/// Per-collection cache of decoded values, keyed by physical location.
///
/// The budget counts **encoded** bytes; the live heap behind a decoded `T` is
/// typically 1.5–3× that (`String`/`Vec` capacity, padding, `Arc` overhead).
pub(crate) struct DecodedCache<T> {
inner: Option<Cache<ValueKey, DecodedEntry<T>, DecodedWeighter>>,
}
impl<T> DecodedCache<T> {
/// Build a cache sized by `config`. `max_size == 0` disables it: [`get`](Self::get)
/// always returns `None` and [`insert`](Self::insert) is a no-op.
pub(crate) fn new(config: &CacheConfig) -> Self {
if config.max_size == 0 {
return Self { inner: None };
}
let cache = Cache::with_weighter(config.estimated_items, config.max_size, DecodedWeighter);
Self { inner: Some(cache) }
}
/// Whether this collection has a decoded cache at all. Callers use it to
/// keep `armdb.decoded_cache.miss` silent on a collection that never opted
/// in — otherwise every read of every non-caching collection would report a
/// miss and the hit *rate* of the ones that do would be unreadable.
pub(crate) fn is_enabled(&self) -> bool {
self.inner.is_some()
}
/// The cached value for `key`, or `None` on a miss (or when disabled).
/// A hit clones one `Arc`.
pub(crate) fn get(&self, key: &ValueKey) -> Option<Arc<T>> {
Some(self.inner.as_ref()?.get(key)?.value)
}
/// Insert (or overwrite) `key`. No-op when disabled. `encoded_len` is the
/// byte length the value was decoded from — the eviction weight.
pub(crate) fn insert(&self, key: ValueKey, value: Arc<T>, encoded_len: u32) {
if let Some(cache) = &self.inner {
cache.insert(key, DecodedEntry { value, encoded_len });
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::config::CacheConfig;
fn key(file_id: u32, offset: u32) -> ValueKey {
ValueKey {
shard_id: 0,
file_id,
offset,
}
}
fn cfg(max_size: u64, estimated_items: usize) -> CacheConfig {
CacheConfig {
max_size,
estimated_items,
}
}
#[test]
fn roundtrip_and_disambiguation() {
let cache: DecodedCache<String> = DecodedCache::new(&cfg(1 << 20, 16));
cache.insert(key(1, 0), Arc::new("alpha".to_owned()), 5);
cache.insert(key(1, 64), Arc::new("beta".to_owned()), 4);
cache.insert(key(2, 0), Arc::new("gamma".to_owned()), 5);
assert_eq!(cache.get(&key(1, 0)).as_deref(), Some(&"alpha".to_owned()));
assert_eq!(cache.get(&key(1, 64)).as_deref(), Some(&"beta".to_owned()));
assert_eq!(cache.get(&key(2, 0)).as_deref(), Some(&"gamma".to_owned()));
assert!(cache.get(&key(9, 9)).is_none());
}
#[test]
fn hit_returns_the_same_allocation() {
let cache: DecodedCache<String> = DecodedCache::new(&cfg(1 << 20, 16));
let stored = Arc::new("shared".to_owned());
cache.insert(key(1, 0), Arc::clone(&stored), 6);
let fetched = cache.get(&key(1, 0)).expect("hit");
assert!(Arc::ptr_eq(&stored, &fetched));
}
#[test]
fn disabled_when_max_size_zero() {
let cache: DecodedCache<String> = DecodedCache::new(&cfg(0, 16));
cache.insert(key(1, 0), Arc::new("x".to_owned()), 1);
assert!(cache.get(&key(1, 0)).is_none());
}
#[test]
fn capacity_pressure_evicts_something() {
// Budget 1 MiB; 64 entries weighing 64 KiB each cannot all be held.
let cache: DecodedCache<Vec<u8>> = DecodedCache::new(&cfg(1 << 20, 64));
for i in 0..64u32 {
cache.insert(
key(1, i * 64 * 1024),
Arc::new(vec![0u8; 64 * 1024]),
64 * 1024,
);
}
let present = (0..64u32)
.filter(|i| cache.get(&key(1, i * 64 * 1024)).is_some())
.count();
assert!(present < 64, "bounded cache must evict, got {present}/64");
}
#[test]
fn zero_length_encodings_are_still_evictable() {
// Regression for the weight floor. `quick_cache` never evicts
// zero-weight items and this cache has no removal path, so a
// zero-byte encoding without `.max(1)` would grow without bound.
let cache: DecodedCache<()> = DecodedCache::new(&cfg(8, 8));
for i in 0..64u32 {
cache.insert(key(1, i), Arc::new(()), 0);
}
let present = (0..64u32)
.filter(|i| cache.get(&key(1, *i)).is_some())
.count();
assert!(
present < 64,
"zero-length entries must still be evicted, got {present}/64"
);
}
#[test]
fn value_type_need_not_be_clone() {
// Compile-time guard for the manual `Clone for DecodedEntry<T>`:
// `#[derive(Clone)]` would demand `T: Clone` and break this.
struct NotClone {
body: Vec<u8>,
}
let cache: DecodedCache<NotClone> = DecodedCache::new(&cfg(1 << 20, 4));
cache.insert(key(1, 0), Arc::new(NotClone { body: vec![7; 3] }), 3);
assert_eq!(cache.get(&key(1, 0)).expect("hit").body, vec![7, 7, 7]);
}
}