Skip to content

cache: try_insert settles memory from a stale index read #67

Closed

Description

@zfarrell

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_insert reads the slot's size with index.get (src/core/src/cache/core.rs:634), moves the memory budget by the difference, and only then calls index.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 separate contains followed by an insert.

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).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't workingmemoryMemory accounting or memory usage

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions