Skip to content

Commit 09a2aff

Browse files
adriangbclaude
andauthored
fix: RepartitionExec deadlock when its spill pool holds two open files (apache#24891)
## Which issue does this PR close? - Closes apache#24883 ## Rationale for this change Under a memory limit, a grouped aggregation on two or more partitions can stop and never complete. The query does not return and does not give an error. All worker threads wait. The issue has the full analysis. In short: when `RepartitionExec` cannot reserve memory for a batch, it writes the batch to a spill pool and sends a marker. The reader then blocks on the pool until it gets a batch. When two input tasks spill at the same time, the pool has two open files. The reader reads only the oldest file. When that file has no unread batch, the reader waits for it. But the batch that the reader needs is in the newer file. When each channel has data, the gate closes and the writers wait too. Nothing can wake the reader. ## What changes are included in this PR? The PR has three commits, in test-first order. 1. `test: reproduce the RepartitionExec spill pool deadlock with a SQL query`. This is the query from the issue as a test in `datafusion/core/tests/memory_limit/repartition_mem_limit.rs`. It makes 12 attempts and stops each one after 20 seconds. On `main`, attempt 0 does not complete and the test fails with a message. 2. `test: add a scenario fuzzer for the spill pool contract`. This adds a test double that can hold a writer inside its first disk write, delay the reads of a file, or fail them. It adds a test that holds writer 1 while writer 2 pushes a batch, a test that a failed read gives an error to the reader, and `spill_pool_scenario_fuzz`, which runs random scenarios from a seed and checks the pool contract: after overlapping pushes the reader can read each pushed batch without more writer activity, it does not signal EOF while a writer is alive, it gives exactly the pushed batches (in order for one writer), and it releases the files. The first two tests are red on this commit. The extended CI job runs 1000 seeds. 3. `fix: RepartitionExec deadlock when its spill pool holds two open files`. `SpillPoolReader` now keeps all the files that it received, oldest first, and gives the first available batch. It skips a file that has no unread batch. It waits for the oldest file that has an unread batch when the read of that file is not complete, so one writer keeps FIFO order. The writer side does not change. The tests of the two commits before it become green. The fuzzer finds each known fault of this pool that a test can reach: | Pool version | Unit tests of that version | Fuzzer | |---|---|---| | Before apache#23522 (has apache#23447) | 16 of 16 pass | Seeds 0 and 1: stall with unread batches. Seed 4: stall after the drop of all writers (the apache#23447 signature). | | `main` (has apache#24883) | pass | Seed 0: stall with 5 of 13 batches unread. | | A draft of this fix that skips a file with a read in progress | 1 failure | Seed 2: FIFO violation with one writer, `[1, 3, 4, 2, ...]`. | | This fix | pass | 500 seeds pass. | ## What is the testing strategy for this PR? - The reproducer makes 12 attempts, each with a 20-second limit. With the fix, 156 runs and 3000 instrumented attempts gave 0 stalls. - The memory limit must be small enough that `RepartitionExec` spills, and that window is narrow: at 4 MB the inner repartition spills in 10 of 10 runs, and at 6 MB and more it never spills. Thus the test also sums the `spill_count` metric of the `RepartitionExec` nodes and fails if no attempt spilled. A later change that stops the query from spilling makes the test say so, instead of passing while it covers nothing. - At 4 MB the greedy pool sometimes refuses an allocation of the final aggregate. That is a correct result of the limit and not a fault, so the test accepts a resources-exhausted error. One attempt in 3000 failed in this way. - The fuzzer runs 50 seeds by default, in approximately three seconds. `DATAFUSION_SPILL_POOL_FUZZ_ITERATIONS` sets the count, and `DATAFUSION_SPILL_POOL_FUZZ_SEED` replays one seed. - `test_read_error_is_reported_to_the_reader` covers the error paths of `SpillPoolFile::poll_file`, which had no test before. - The 33 memory-limit tests, the 111 spill and repartition unit tests, and the spill pool doctests pass. `cargo fmt` and `cargo clippy --all-targets --all-features -- -D warnings` pass on the two changed crates. I also wrote this reproducer as a sqllogictest file and then removed it. sqllogictest has no time limit, so a return of the deadlock stops the file until the CI job reaches its time limit, instead of a quick failure with a message. It also cannot say "these rows, or this resource error", so the file failed 1 run in 400 (3200 queries) on the legitimate resources-exhausted error. The limit cannot be relaxed to avoid this, because at 6 MB and more nothing spills, and a smaller count of distinct values also stops the spill (with 97 distinct values 7 of 10 runs do not spill, and with 53 none do). I also evaluated a second fix that keeps one open write file for each pool. It passes the same tests. It serializes writers that spill at the same time on the file lock, which apache#23522 avoided on purpose. It is not part of this PR. ## Are there any user-facing changes? No. The `branch-54` line has the same fault, because apache#23654 backported the same file model. A backport of this fix is necessary. 🤖 Generated with [Claude Code](https://claude.com/claude-code) https://claude.ai/code/session_01RauD5PqPCp4y92RUZUD6C9 --------- Co-authored-by: Claude <[email protected]>
1 parent eaf7fff commit 09a2aff

3 files changed

Lines changed: 874 additions & 93 deletions

File tree

‎.github/workflows/extended.yml‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -88,6 +88,9 @@ jobs:
8888
- name: Run tests (excluding doctests)
8989
env:
9090
RUST_BACKTRACE: 1
91+
# Run more random scenarios of the spill pool fuzzer than the
92+
# default suite does (about a minute).
93+
DATAFUSION_SPILL_POOL_FUZZ_ITERATIONS: 1000
9194
run: |
9295
cargo test \
9396
--profile ci \

‎datafusion/core/tests/memory_limit/repartition_mem_limit.rs‎

Lines changed: 154 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -117,3 +117,157 @@ async fn test_repartition_memory_limit() {
117117
];
118118
assert_batches_sorted_eq!(expected, &all_batches);
119119
}
120+
121+
/// Regression test for <https://github.com/apache/datafusion/issues/24883>.
122+
///
123+
/// In non-preserve-order mode every input task of a `RepartitionExec` shares one
124+
/// spill pool per output partition. When two input tasks spilled concurrently the
125+
/// pool could end up with two open spill files while the reader only ever drained
126+
/// the head file: it parked on a drained-but-unfinished head file even though the
127+
/// batch it was waiting for had been written to the second file. Once every
128+
/// distributor channel was non-empty the gate closed, both input tasks parked in
129+
/// `send`, no sink was dropped, and nothing could wake anybody.
130+
///
131+
/// This module is not compiled with `force_hash_collisions`. That feature makes
132+
/// every hash 0, so the hash `RepartitionExec` sends all rows to one output
133+
/// partition. The gate closes only when every channel holds data, so the
134+
/// deadlock cannot occur and the test cannot test anything. The feature also
135+
/// makes the group-by hash table degenerate, which made one attempt of this
136+
/// query approximately 36 times slower and thus longer than the limit below.
137+
#[cfg(not(feature = "force_hash_collisions"))]
138+
mod spill_pool_deadlock {
139+
use super::*;
140+
141+
use std::time::Duration;
142+
143+
use datafusion::execution::session_state::SessionStateBuilder;
144+
use datafusion_execution::disk_manager::{DiskManagerBuilder, DiskManagerMode};
145+
use datafusion_execution::memory_pool::{GreedyMemoryPool, MemoryPool};
146+
use datafusion_physical_plan::collect;
147+
148+
/// Memory limit that puts `RepartitionExec` into its spilling path for this
149+
/// query without failing the aggregation outright.
150+
const MEMORY_LIMIT: usize = 4 * 1024 * 1024;
151+
152+
/// Number of attempts. On an unfixed tree the first attempt deadlocks; the
153+
/// budget is only there so a fix cannot pass by luck.
154+
const ATTEMPTS: usize = 12;
155+
156+
/// Generous per-attempt budget: a healthy run of this query takes well under
157+
/// a second.
158+
const PER_ATTEMPT_TIMEOUT: Duration = Duration::from_secs(20);
159+
160+
/// Runs the query once. Returns the number of output rows and the number
161+
/// of spills the `RepartitionExec`s did.
162+
async fn run_once() -> datafusion::error::Result<(usize, usize)> {
163+
let pool: Arc<dyn MemoryPool> = Arc::new(GreedyMemoryPool::new(MEMORY_LIMIT));
164+
let runtime = RuntimeEnvBuilder::new()
165+
// Spilling must be possible: with the disk manager disabled the query
166+
// fails with a resource error instead of deadlocking.
167+
.with_disk_manager_builder(
168+
DiskManagerBuilder::default().with_mode(DiskManagerMode::OsTmpDirectory),
169+
)
170+
.with_memory_pool(pool)
171+
.build_arc()?;
172+
173+
let config = SessionConfig::new()
174+
// Two input partitions feeding one hash RepartitionExec is the
175+
// smallest configuration with two concurrent writers per spill pool.
176+
.with_target_partitions(2)
177+
// Small batches so many small batches reach the repartition spill
178+
// path while the spill file stays far below
179+
// `max_spill_file_size_bytes` and so never rotates.
180+
.with_batch_size(64);
181+
182+
let state = SessionStateBuilder::new()
183+
.with_config(config)
184+
.with_runtime_env(runtime)
185+
.with_default_features()
186+
.build();
187+
let ctx = SessionContext::new_with_state(state);
188+
189+
ctx.sql(
190+
"create table trace_events as
191+
select v % 13 as g,
192+
case when v % 29 = 0 then null
193+
else md5(cast(v % 337 as varchar)) end as trace_id
194+
from generate_series(1, 40000) as t(v)",
195+
)
196+
.await?
197+
.collect()
198+
.await?;
199+
200+
ctx.sql(
201+
"create view tv as
202+
select g, arrow_cast(trace_id, 'Utf8View') as trace_id from trace_events",
203+
)
204+
.await?
205+
.collect()
206+
.await?;
207+
208+
let logical = ctx
209+
.state()
210+
.create_logical_plan(
211+
"select g, count(distinct trace_id) as n from tv group by g",
212+
)
213+
.await?;
214+
let plan = ctx.state().create_physical_plan(&logical).await?;
215+
let batches = collect(Arc::clone(&plan), ctx.task_ctx()).await?;
216+
217+
// Count the spills of the `RepartitionExec`s. The caller uses this to
218+
// make sure the query still goes through the spill path: if a change
219+
// stops it spilling, this test keeps passing but no longer covers the
220+
// deadlock, and that must fail loudly instead.
221+
let mut spills = 0;
222+
plan.transform_down(|node| {
223+
if node.is::<RepartitionExec>() {
224+
spills += node.metrics().and_then(|m| m.spill_count()).unwrap_or(0);
225+
}
226+
Ok(Transformed::no(node))
227+
})?;
228+
229+
Ok((batches.iter().map(|b| b.num_rows()).sum(), spills))
230+
}
231+
232+
#[tokio::test(flavor = "multi_thread", worker_threads = 8)]
233+
async fn repartition_spill_pool_does_not_deadlock() {
234+
let mut attempts_that_spilled = 0;
235+
for attempt in 0..ATTEMPTS {
236+
match tokio::time::timeout(PER_ATTEMPT_TIMEOUT, run_once()).await {
237+
Err(elapsed) => panic!(
238+
"attempt {attempt}: grouped COUNT(DISTINCT Utf8View) never completed \
239+
within {PER_ATTEMPT_TIMEOUT:?} ({elapsed}); RepartitionExec spill \
240+
pool deadlock"
241+
),
242+
Ok(Ok((rows, spills))) => {
243+
assert_eq!(rows, 13, "attempt {attempt}: wrong row count");
244+
if spills > 0 {
245+
attempts_that_spilled += 1;
246+
}
247+
}
248+
// The budget is deliberately far too small for the query, and the
249+
// greedy pool hands memory out first come first served, so once in
250+
// a few thousand attempts an aggregate's allocation is refused
251+
// while the repartition reservations hold the pool. That is a
252+
// legitimate outcome of the limit, not the hang this test guards
253+
// against.
254+
Ok(Err(e))
255+
if matches!(
256+
e.find_root(),
257+
datafusion::error::DataFusionError::ResourcesExhausted(_)
258+
) => {}
259+
Ok(Err(e)) => panic!("attempt {attempt}: query failed: {e}"),
260+
}
261+
}
262+
263+
// The memory limit must be tight enough that `RepartitionExec` spills,
264+
// because the deadlock is in its spill pool. Timing decides how many
265+
// attempts spill, but if none of them do, the limit no longer forces
266+
// the spill path and this test has stopped testing anything.
267+
assert!(
268+
attempts_that_spilled > 0,
269+
"no attempt reached the RepartitionExec spill path in {ATTEMPTS} \
270+
attempts; the memory limit no longer forces a spill"
271+
);
272+
}
273+
}

0 commit comments

Comments
 (0)