Repository navigation
Description
Found by a memory-accounting audit of 8b3c813. The tests are on branch audit/memory-tests and fail on main today; check out that branch to run them. File and line links point at that commit.
What goes wrong.
try_insertreads the slot's size withindex.get(src/core/src/cache/core.rs:634), moves the memory budget by the difference, and only then callsindex.insert(:650).- The slot that the insert actually displaced is never used for memory. The disk side does use it.
- Two tasks on one key that interleave between those two lines leave the budget permanently wrong, in either direction.
- Same-key inserts are routine, because
CachedColumn::insert(src/datafusion/src/cache/column.rs:229-241) is itself a separatecontainsfollowed by aninsert.
Evidence.
| Race | Result |
|---|---|
| Two inserts of one absent key | Budget 1,792 vs index 896: one entry charged twice. 4 of 4 runs |
| Evict (transcode) racing re-insert | Budget 856 below the index, the OOM direction. 6 of 6 runs |
Two reads hydrating one disk entry (default AlwaysHydrate) |
62 of 1,000 rounds drifted, by 13,888 bytes in total |
Eviction spill or flush_all_to_disk racing a re-insert |
An entry held in memory with nothing charged, on round 0 |
Scan path, through CachedColumn |
1,403 of 4,000 rounds accepted a duplicate insert; 2,817,024 bytes charged for nothing |
Tests. All are probabilistic. The first two tests run 5,000 rounds and take about 15–23 s when they fail; they are gated #[cfg(not(feature = "shuttle"))].
| Test | File | Command | Flags |
|---|---|---|---|
two_inserts_of_one_absent_key_keep_memory_budget |
src/core/src/cache/core.rs:1819 |
cargo +1.96.0 test -p liquid-cache --lib two_inserts_of_one_absent_key_keep_memory_budget |
P, Inline |
evict_racing_reinsert_keeps_memory_budget |
src/core/src/cache/core.rs:1835 |
cargo +1.96.0 test -p liquid-cache --lib evict_racing_reinsert_keeps_memory_budget |
P |
audit_two_reads_hydrating_one_disk_entry_charge_it_once |
src/core/src/cache/core.rs:3516 |
cargo +1.96.0 test -p liquid-cache --lib audit_two_reads_hydrating_one_disk_entry_charge_it_once -- --nocapture |
P |
audit_two_reads_hydrating_one_disk_entry_together_charge_it_once |
src/core/src/cache/core.rs:3524 |
cargo +1.96.0 test -p liquid-cache --lib audit_two_reads_hydrating_one_disk_entry_together_charge_it_once -- --nocapture |
P (test-only HydrateInPairs policy) |
audit_an_eviction_spill_racing_a_reinsert_leaves_the_budget_matching_the_index |
src/core/src/cache/core.rs:3593 |
cargo +1.96.0 test -p liquid-cache --lib audit_an_eviction_spill_racing_a_reinsert -- --nocapture |
P |
audit_a_flush_racing_a_reinsert_leaves_the_budget_matching_the_index |
src/core/src/cache/core.rs:3612 |
cargo +1.96.0 test -p liquid-cache --lib audit_a_flush_racing_a_reinsert -- --nocapture |
P |
audit_concurrent_inserts_keep_budget_equal_to_entries |
src/datafusion/src/cache/mod.rs:1211 |
cargo +1.96.0 test -p liquid-cache-datafusion --lib audit_concurrent_inserts_keep_budget_equal_to_entries -- --nocapture |
P |
Inline test (append inside mod tests in src/core/src/cache/core.rs; it uses the existing block_on, create_cache_store, create_test_array and assert_memory_budget_matches_index):
#[cfg(not(feature = "shuttle"))]
const RACE_ROUNDS: usize = 5_000;
/// A cache whose memory budget no round can fill.
#[cfg(not(feature = "shuttle"))]
fn roomy_cache() -> Arc<LiquidCache> {
block_on(create_cache_store(1 << 34, Box::new(LiquidPolicy::new())))
}
/// Run `first` and `second` at once, released together.
#[cfg(not(feature = "shuttle"))]
fn race(first: impl FnOnce() + Send, second: impl FnOnce() + Send) {
let barrier = std::sync::Barrier::new(2);
std::thread::scope(|scope| {
scope.spawn(|| {
barrier.wait();
first();
});
scope.spawn(|| {
barrier.wait();
second();
});
});
}
/// Two tasks insert the same absent key. Both read `None`, both
/// reserve the full size, one entry survives: the budget over-counts.
#[cfg(not(feature = "shuttle"))]
#[test]
fn two_inserts_of_one_absent_key_keep_memory_budget() {
let cache = roomy_cache();
for round in 0..RACE_ROUNDS {
let key = EntryID::from(round);
let insert = || block_on(cache.insert_inner(key, 0, create_test_array(100))).unwrap();
race(insert, insert);
assert_memory_budget_matches_index(&cache);
}
}Possible fix: settle the memory budget from the slot index.insert actually displaced, as the disk side already does. #30 proposes the matching invariant oracle.
Flags: P probabilistic (a pass after a fix only means the race wasn't hit), F interleaving forced by a test hook, L Linux only, D needs Docker, M measurement only, C control (passes by design).
Activity
Merge origin/main into fix/eviction-accounting