use std::collections::BTreeMap;
use crate::backend::api::{Backend, KeyRange, Op, ScanRequest, Table};
use crate::error::{Error, Result};
use crate::key::LockerId;
const LRU_PREFIX: &[u8] = b"lru::";
const META_NEXT_TICK: &[u8] = b"next_tick";
const RECORD_LEN: usize = 12;
pub(crate) fn locker_prefix(id: LockerId) -> Vec<u8> {
let mut out = Vec::with_capacity(LRU_PREFIX.len() + 6);
out.extend_from_slice(LRU_PREFIX);
out.extend_from_slice(&id.to_be_bytes());
out.extend_from_slice(b"::");
out
}
pub(crate) fn entry_key(id: LockerId, key: &[u8]) -> Vec<u8> {
let mut out = locker_prefix(id);
out.extend_from_slice(key);
out
}
fn user_key<'a>(prefix: &[u8], meta_key: &'a [u8]) -> Option<&'a [u8]> {
meta_key.strip_prefix(prefix)
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) struct Entry {
pub tick: u64,
pub bytes: u64,
}
fn encode_entry(entry: Entry) -> Vec<u8> {
let mut out = Vec::with_capacity(RECORD_LEN);
out.extend_from_slice(&entry.tick.to_be_bytes());
out.extend_from_slice(&(entry.bytes.min(u32::MAX as u64) as u32).to_be_bytes());
out
}
fn parse_entry(raw: &[u8]) -> Option<Entry> {
if raw.len() != RECORD_LEN {
return None;
}
let tick = u64::from_be_bytes(raw[0..8].try_into().ok()?);
let bytes = u32::from_be_bytes(raw[8..12].try_into().ok()?) as u64;
Some(Entry { tick, bytes })
}
pub(crate) fn put_op(id: LockerId, key: &[u8], entry: Entry) -> Op {
Op::Put {
table: Table::Meta,
key: entry_key(id, key),
value: encode_entry(entry),
}
}
pub(crate) fn delete_op(id: LockerId, key: &[u8]) -> Op {
Op::Delete {
table: Table::Meta,
key: entry_key(id, key),
}
}
pub(crate) fn clear_op(id: LockerId) -> Op {
Op::DeleteRange {
table: Table::Meta,
range: KeyRange::prefix(&locker_prefix(id)),
}
}
#[derive(Debug, Default)]
pub struct Ticks {
state: std::sync::Mutex<TickState>,
}
#[derive(Debug, Default)]
struct TickState {
next: Option<u64>,
floor: u64,
}
impl TickState {
fn cursor(&self, stored: Option<u64>) -> Option<u64> {
let next = match (self.next, stored) {
(Some(current), Some(stored)) => current.max(stored),
(Some(current), None) => current,
(None, Some(stored)) => stored,
(None, None) => return None,
};
Some(next.max(self.floor))
}
}
impl Ticks {
fn lock(&self) -> Result<std::sync::MutexGuard<'_, TickState>> {
self.state
.lock()
.map_err(|_| Error::backend("tick cursor was poisoned"))
}
fn take(&self) -> Result<Option<u64>> {
let mut guard = self.lock()?;
match guard.cursor(None) {
None => Ok(None),
Some(tick) => {
guard.next = Some(advance(tick)?);
Ok(Some(tick))
}
}
}
fn seed_and_take(&self, stored: u64) -> Result<u64> {
let mut guard = self.lock()?;
let tick = guard.cursor(Some(stored)).unwrap_or(stored);
guard.next = Some(advance(tick)?);
Ok(tick)
}
pub(crate) fn observe_recorded(&self, max_seen: u64) -> Result<()> {
let at_least = advance(max_seen)?;
let mut guard = self.lock()?;
guard.floor = guard.floor.max(at_least);
if let Some(current) = guard.next {
guard.next = Some(current.max(guard.floor));
}
Ok(())
}
pub(crate) async fn allocate(&self, backend: &dyn Backend) -> Result<u64> {
if let Some(tick) = self.take()? {
return Ok(tick);
}
let raw = backend.get(Table::Meta, META_NEXT_TICK).await?;
let stored = match raw {
None => 0,
Some(bytes) => <[u8; 8]>::try_from(bytes.as_slice())
.map(u64::from_be_bytes)
.map_err(|_| Error::Corrupt("next_tick is not an 8-byte integer".into()))?,
};
self.seed_and_take(stored)
}
pub(crate) fn counter_op(&self) -> Result<Op> {
let guard = self.lock()?;
let next = guard.cursor(None).unwrap_or(guard.floor);
Ok(Op::Put {
table: Table::Meta,
key: META_NEXT_TICK.to_vec(),
value: next.to_be_bytes().to_vec(),
})
}
}
fn advance(tick: u64) -> Result<u64> {
tick.checked_add(1)
.ok_or_else(|| Error::backend("tick space is exhausted"))
}
pub(crate) const PENDING_PER_COMMIT: usize = 64;
#[derive(Debug, Default)]
pub(crate) struct Plan {
pub victims: Vec<Vec<u8>>,
pub total: u64,
}
#[derive(Debug)]
pub(crate) struct LruState {
pub max_bytes: u64,
entries: BTreeMap<Vec<u8>, Entry>,
total: u64,
pending: BTreeMap<Vec<u8>, u64>,
dirty: bool,
}
impl LruState {
pub fn new(max_bytes: u64) -> Self {
Self {
max_bytes,
entries: BTreeMap::new(),
total: 0,
pending: BTreeMap::new(),
dirty: false,
}
}
pub fn total(&self) -> u64 {
self.total
}
pub fn is_dirty(&self) -> bool {
self.dirty
}
pub fn mark_dirty(&mut self) {
self.dirty = true;
}
pub fn adopt_loaded(&mut self, loaded: LruState) {
self.entries = loaded.entries;
self.total = loaded.total;
self.pending.retain(|k, _| self.entries.contains_key(k));
self.dirty = false;
}
pub fn next_local_tick(&self) -> u64 {
self.entries
.values()
.map(|e| e.tick)
.max()
.unwrap_or(0)
.saturating_add(1)
}
pub fn remote_put(&mut self, key: &[u8], bytes: Option<u64>) {
let tick = self.next_local_tick();
match bytes {
Some(bytes) => {
if let Some(old) = self.entries.insert(key.to_vec(), Entry { tick, bytes }) {
self.total = self.total.saturating_sub(old.bytes);
}
self.total = self.total.saturating_add(bytes);
}
None => {
self.entries
.entry(key.to_vec())
.or_insert(Entry { tick, bytes: 0 });
self.mark_dirty();
}
}
}
pub fn remote_delete(&mut self, key: &[u8]) {
if let Some(old) = self.entries.remove(key) {
self.total = self.total.saturating_sub(old.bytes);
}
self.pending.remove(key);
}
pub fn remote_clear(&mut self) {
self.entries.clear();
self.pending.clear();
self.total = 0;
self.dirty = false;
}
pub fn touch(&mut self, key: &[u8], tick: u64) {
if let Some(entry) = self.entries.get_mut(key) {
entry.tick = tick;
self.pending.insert(key.to_vec(), tick);
}
}
pub fn pending_ops(&self, id: LockerId, skip: &[Vec<u8>]) -> (Vec<Vec<u8>>, Vec<Op>) {
let mut keys = Vec::new();
let mut ops = Vec::new();
for (key, tick) in self.pending.iter().take(PENDING_PER_COMMIT) {
if skip.iter().any(|s| s == key) {
keys.push(key.clone());
continue;
}
let Some(entry) = self.entries.get(key) else {
continue;
};
keys.push(key.clone());
ops.push(put_op(
id,
key,
Entry {
tick: *tick,
bytes: entry.bytes,
},
));
}
(keys, ops)
}
#[cfg(test)]
pub fn pending_len(&self) -> usize {
self.pending.len()
}
pub fn clear_pending(&mut self, keys: &[Vec<u8>]) {
for key in keys {
self.pending.remove(key);
}
}
pub fn plan(
&self,
updates: &[(Vec<u8>, Entry)],
removals: &[Vec<u8>],
cleared: bool,
budget: u64,
keep: &[Vec<u8>],
) -> Plan {
let mut total = if cleared { 0 } else { self.total };
if !cleared {
for key in removals {
if let Some(entry) = self.entries.get(key.as_slice()) {
total = total.saturating_sub(entry.bytes);
}
}
}
for (key, entry) in updates {
if !cleared {
if let Some(old) = self.entries.get(key.as_slice()) {
total = total.saturating_sub(old.bytes);
}
}
total = total.saturating_add(entry.bytes);
}
if total <= budget {
return Plan {
victims: Vec::new(),
total,
};
}
let mut candidates: Vec<(u64, &[u8], u64)> = Vec::new();
if !cleared {
for (key, entry) in &self.entries {
if removals.iter().any(|r| r == key)
|| updates.iter().any(|(k, _)| k == key)
|| keep.iter().any(|k| k.as_slice() == key.as_slice())
{
continue;
}
candidates.push((entry.tick, key.as_slice(), entry.bytes));
}
}
for (key, entry) in updates {
if keep.iter().any(|k| k == key) {
continue;
}
candidates.push((entry.tick, key.as_slice(), entry.bytes));
}
candidates.sort_by(|a, b| a.0.cmp(&b.0).then_with(|| a.1.cmp(b.1)));
let mut victims = Vec::new();
for (_, key, bytes) in candidates {
if total <= budget {
break;
}
total = total.saturating_sub(bytes);
victims.push(key.to_vec());
}
Plan { victims, total }
}
pub fn apply(
&mut self,
updates: &[(Vec<u8>, Entry)],
removals: &[Vec<u8>],
cleared: bool,
plan: &Plan,
) {
if cleared {
self.entries.clear();
self.pending.clear();
}
for key in removals {
self.entries.remove(key.as_slice());
self.pending.remove(key.as_slice());
}
for (key, entry) in updates {
self.entries.insert(key.clone(), *entry);
}
for key in &plan.victims {
self.entries.remove(key.as_slice());
self.pending.remove(key.as_slice());
}
self.total = plan.total;
}
pub fn adopt(&mut self, key: Vec<u8>) {
self.entries
.entry(key)
.or_insert(Entry { tick: 0, bytes: 0 });
}
pub fn retain_keys(&mut self, live: impl Fn(&[u8]) -> bool) {
self.entries.retain(|k, _| live(k));
self.pending.retain(|k, _| live(k));
self.total = self.entries.values().map(|e| e.bytes).sum();
}
}
pub(crate) async fn load(
backend: &dyn Backend,
id: LockerId,
max_bytes: u64,
ticks: &Ticks,
) -> Result<LruState> {
let mut state = LruState::new(max_bytes);
let prefix = locker_prefix(id);
let mut range = KeyRange::prefix(&prefix);
let mut max_tick: Option<u64> = None;
loop {
let page = backend
.scan(ScanRequest {
table: Table::Meta,
range: range.clone(),
reverse: false,
limit: super::inner::SCAN_PAGE,
want_values: true,
})
.await?;
for (meta_key, value) in &page.items {
let Some(key) = user_key(&prefix, meta_key) else {
continue;
};
if let Some(entry) = value.as_deref().and_then(parse_entry) {
state.total = state.total.saturating_add(entry.bytes);
max_tick = Some(max_tick.map_or(entry.tick, |m: u64| m.max(entry.tick)));
state.entries.insert(key.to_vec(), entry);
}
}
match page.resume {
Some(last) => range.start = std::ops::Bound::Excluded(last),
None => break,
}
}
if let Some(max_tick) = max_tick {
ticks.observe_recorded(max_tick)?;
}
Ok(state)
}
#[cfg(test)]
mod tests {
use super::*;
fn state() -> LruState {
let mut s = LruState::new(100);
for (key, tick, bytes) in [(b"a", 1u64, 40u64), (b"b", 2, 40), (b"c", 3, 20)] {
s.entries.insert(key.to_vec(), Entry { tick, bytes });
s.total += bytes;
}
s
}
#[test]
fn entry_records_round_trip() {
let e = Entry {
tick: 9_000_000_000,
bytes: 4096,
};
assert_eq!(parse_entry(&encode_entry(e)), Some(e));
assert_eq!(parse_entry(b"short"), None);
}
#[test]
fn an_oversized_value_saturates_rather_than_wrapping() {
let e = Entry {
tick: 1,
bytes: u64::from(u32::MAX) + 10_000,
};
let back = parse_entry(&encode_entry(e)).expect("fixed width");
assert_eq!(back.bytes, u64::from(u32::MAX));
}
#[test]
fn a_put_inside_the_budget_evicts_nothing() {
let s = state();
let plan = s.plan(
&[(b"c".to_vec(), Entry { tick: 4, bytes: 20 })],
&[],
false,
s.max_bytes,
&[b"c".to_vec()],
);
assert!(plan.victims.is_empty());
assert_eq!(plan.total, 100);
}
#[test]
fn going_over_sheds_the_lowest_tick_first() {
let s = state();
let plan = s.plan(
&[(b"d".to_vec(), Entry { tick: 4, bytes: 30 })],
&[],
false,
s.max_bytes,
&[b"d".to_vec()],
);
assert_eq!(plan.victims, vec![b"a".to_vec()]);
assert_eq!(plan.total, 90);
}
#[test]
fn the_key_being_written_is_never_its_own_victim() {
let s = state();
let plan = s.plan(
&[(
b"big".to_vec(),
Entry {
tick: 9,
bytes: 500,
},
)],
&[],
false,
s.max_bytes,
&[b"big".to_vec()],
);
assert_eq!(plan.victims.len(), 3);
assert_eq!(plan.total, 500);
}
#[test]
fn a_read_bumps_the_tick_and_defers_the_write() {
let mut s = state();
s.touch(b"a", 99);
assert_eq!(s.pending_len(), 1);
let (keys, ops) = s.pending_ops(7, &[]);
assert_eq!(keys, vec![b"a".to_vec()]);
assert_eq!(ops.len(), 1);
assert!(s.pending_ops(7, &[b"a".to_vec()]).1.is_empty());
let plan = s.plan(
&[(
b"d".to_vec(),
Entry {
tick: 100,
bytes: 30,
},
)],
&[],
false,
s.max_bytes,
&[b"d".to_vec()],
);
assert_eq!(plan.victims, vec![b"b".to_vec()]);
}
#[cfg(not(target_arch = "wasm32"))]
#[test]
fn the_clock_opens_above_every_tick_the_records_hold() {
let backend = crate::backend::MemoryBackend::new();
futures::executor::block_on(async {
backend
.commit(vec![
put_op(
7,
b"a",
Entry {
tick: 41,
bytes: 10,
},
),
put_op(
7,
b"b",
Entry {
tick: 900,
bytes: 10,
},
),
])
.await
.expect("plant records");
let ticks = Ticks::default();
let state = load(&backend, 7, 1_000, &ticks).await.expect("load");
assert_eq!(state.total(), 20);
let first = ticks.allocate(&backend).await.expect("allocate");
assert!(
first > 900,
"opened on tick {first}, at or below the 900 already recorded"
);
});
}
#[cfg(not(target_arch = "wasm32"))]
#[test]
fn a_higher_stored_counter_is_not_dragged_back_down() {
let backend = crate::backend::MemoryBackend::new();
futures::executor::block_on(async {
backend
.commit(vec![
put_op(7, b"a", Entry { tick: 3, bytes: 10 }),
Op::Put {
table: Table::Meta,
key: META_NEXT_TICK.to_vec(),
value: 5_000u64.to_be_bytes().to_vec(),
},
])
.await
.expect("plant records");
let ticks = Ticks::default();
load(&backend, 7, 1_000, &ticks).await.expect("load");
assert_eq!(ticks.allocate(&backend).await.expect("allocate"), 5_000);
});
}
#[test]
fn touching_a_key_we_do_not_hold_records_nothing() {
let mut s = state();
s.touch(b"absent", 42);
assert_eq!(s.pending_len(), 0);
}
}