pub(crate) const BATCH_MAX_ENTRIES: usize = 65_536;
pub(crate) const BATCH_MAX_BYTES: usize = 16 << 20;
const ENTRY_OVERHEAD: usize = 64;
const OP_OVERHEAD: usize = 48;
pub(crate) enum SourceAction {
Put(Vec<u8>),
Delete,
}
pub(crate) struct DerivedOp {
pub(crate) target: &'static str,
pub(crate) key: Vec<u8>,
pub(crate) value: Option<Vec<u8>>,
}
pub(crate) struct BatchEntry {
pub(crate) key: Vec<u8>,
pub(crate) action: SourceAction,
pub(crate) ops: Vec<DerivedOp>,
}
impl BatchEntry {
fn charge(&self) -> usize {
let action = match &self.action {
SourceAction::Put(v) => v.capacity(),
SourceAction::Delete => 0,
};
ENTRY_OVERHEAD
+ self.key.capacity()
+ action
+ self.ops.capacity() * OP_OVERHEAD.max(std::mem::size_of::<DerivedOp>())
+ self
.ops
.iter()
.map(|o| o.key.capacity() + o.value.as_ref().map_or(0, Vec::capacity))
.sum::<usize>()
}
}
pub(crate) struct MigrationBatch {
entries: Vec<BatchEntry>,
charged: usize,
max_entries: usize,
max_bytes: usize,
}
impl MigrationBatch {
pub(crate) fn new(max_entries: usize, max_bytes: usize) -> Self {
Self {
entries: Vec::new(),
charged: 0,
max_entries,
max_bytes,
}
}
fn next_capacity(&self) -> usize {
if self.entries.len() == self.entries.capacity() {
self.entries.capacity().saturating_mul(2).max(4)
} else {
self.entries.capacity()
}
}
pub(crate) fn must_drain_before(&self, entry: &BatchEntry) -> bool {
!self.is_empty()
&& (self.entries.len() >= self.max_entries
|| self.charged.saturating_add(entry.charge()).saturating_add(
self.next_capacity()
.saturating_mul(std::mem::size_of::<BatchEntry>()),
) > self.max_bytes)
}
pub(crate) fn push(&mut self, entry: BatchEntry) -> bool {
assert!(
!self.must_drain_before(&entry),
"drain before retaining an over-budget entry"
);
let capacity = self.next_capacity();
self.entries.reserve_exact(capacity - self.entries.len());
self.charged += entry.charge();
self.entries.push(entry);
self.entries.len() >= self.max_entries || self.charged() >= self.max_bytes
}
pub(crate) fn is_empty(&self) -> bool {
self.entries.is_empty()
}
pub(crate) fn charged(&self) -> usize {
self.charged + self.entries.capacity() * std::mem::size_of::<BatchEntry>()
}
pub(crate) fn drain(&mut self) -> Vec<BatchEntry> {
self.charged = 0;
std::mem::take(&mut self.entries)
}
}
pub(crate) fn batch_max_entries() -> usize {
#[cfg(feature = "test-faults")]
if let Some(limit) = std::env::var("ARMDB_SEG_INDEX_BATCH_ENTRIES")
.ok()
.and_then(|value| value.parse::<usize>().ok())
.filter(|&n| n > 0)
{
return limit.min(BATCH_MAX_ENTRIES);
}
BATCH_MAX_ENTRIES
}
#[cfg(test)]
mod tests {
use super::*;
fn entry(key: u8, value: usize, ops: usize) -> BatchEntry {
BatchEntry {
key: vec![key; 8],
action: SourceAction::Put(vec![0; value]),
ops: (0..ops)
.map(|i| DerivedOp {
target: "t",
key: vec![i as u8; 24],
value: Some(Vec::new()),
})
.collect(),
}
}
#[test]
fn the_budget_charges_keys_values_ops_and_capacity() {
let mut b = MigrationBatch::new(10, 1 << 20);
b.push(entry(1, 100, 3));
assert!(b.charged() >= 8 + 100 + 3 * 24);
}
#[test]
fn a_full_batch_asks_to_be_applied() {
let mut b = MigrationBatch::new(2, 1 << 20);
assert!(!b.push(entry(1, 1, 1)));
assert!(b.push(entry(2, 1, 1)));
}
#[test]
fn an_oversized_entry_forms_its_own_batch() {
let mut b = MigrationBatch::new(10, 64);
assert!(
b.push(entry(1, 1000, 1)),
"one entry over budget is accepted alone and flushes"
);
assert_eq!(b.drain().len(), 1);
assert!(b.is_empty());
}
#[test]
fn an_oversized_entry_cannot_join_a_nonempty_batch() {
let mut b = MigrationBatch::new(100, 2048);
assert!(!b.push(entry(1, 1, 1)));
let oversized = entry(2, 4096, 1);
assert!(b.must_drain_before(&oversized));
assert_eq!(b.drain().len(), 1);
assert!(b.push(oversized));
assert_eq!(b.drain().len(), 1);
}
#[test]
fn capacity_growth_is_preflighted_and_charged() {
let first = entry(1, 1, 0);
let row_charge = first.charge();
let size = std::mem::size_of::<BatchEntry>();
let mut b = MigrationBatch::new(100, row_charge * 5 + size * 4);
for key in 0..4 {
assert!(!b.push(entry(key, 1, 0)));
}
assert_eq!(b.charged(), row_charge * 4 + size * 4);
assert!(
b.must_drain_before(&entry(5, 1, 0)),
"the fifth row grows capacity to eight"
);
}
#[test]
fn delete_fanout_covering_values_and_multiple_targets_are_charged() {
let mut e = entry(1, 8192, 100);
e.key.reserve_exact(128);
e.ops.reserve_exact(50);
for (i, op) in e.ops.iter_mut().enumerate() {
op.target = if i % 2 == 0 { "a" } else { "b" };
op.value = Some(Vec::with_capacity(256));
}
let expected = ENTRY_OVERHEAD
+ e.key.capacity()
+ 8192
+ e.ops.capacity() * std::mem::size_of::<DerivedOp>().max(OP_OVERHEAD)
+ 100 * (24 + 256);
assert_eq!(e.charge(), expected);
e.action = SourceAction::Delete;
for op in &mut e.ops {
op.value = None;
}
let expected = expected - 8192 - 100 * 256;
assert_eq!(e.charge(), expected);
let mut b = MigrationBatch::new(100, expected * 2);
b.push(e);
assert!(b.charged() >= expected);
}
#[test]
fn an_index_targets_shared_migration_accepts_keep_and_refuses_update_and_delete() {
use crate::seg::testkit::{TextCodec, key_of, meta};
let dir = tempfile::tempdir().unwrap();
let tree = crate::seg::SegTree::open_deferred(
dir.path(),
meta(),
&[],
true,
crate::seg::SegConfig::test(),
TextCodec,
crate::NoHook,
)
.unwrap();
let key = key_of(7);
tree.core().put(&key, b"old").unwrap();
assert_eq!(
tree.migrate_rows(|_, _| crate::MigrateAction::Keep)
.unwrap(),
0
);
for update in [true, false] {
let err = tree
.migrate_rows(|_, _| {
if update {
crate::MigrateAction::Update(String::from("new"))
} else {
crate::MigrateAction::Delete
}
})
.unwrap_err();
assert!(matches!(err, crate::DbError::Config(message) if message.contains("Keep")));
assert_eq!(tree.try_get(&key).unwrap(), Some(String::from("old")));
}
}
}