TimelyDataflow / TimelyDataflow/differential-dataflow
reduce driver: late empty batches can transiently regress upper_limit (hardening follow-up from #801)
Nobody has claimed this yet.
- Dominant language
- Rust
- Stars
- 3k
- Forks
- 211
- Avg merge
- 10h 42m
- Merged PRs (30d)
- 34
Description
A follow-up thread from the #801 investigation (see the closing comment there and #802): the reduce driver has a nearby, weaker hazard that we believe is content-safe but could transiently malform its retirement interval. Filing so the analysis doesn't get lost.
The pattern. reduce_with_tactic maintains its retirement upper as
input.for_each(|cap, batches| { ... upper_limit.clone_from(batch.upper()); ... });
source_trace.advance_upper(&mut upper_limit);
antichain_join_into(&upper_limit, &frontier.frontier(), &mut joined); // upper = join
Why it cannot lose content (unlike the join pre-#802): the input frontier participates in the joined upper, and any in-flight batch's message capability holds that frontier back, so the retirement interval can never advance past undelivered content. This is the structural reason the #801 bug lived in the join (whose acknowledged is pure batch bookkeeping) and not here.
The residual hazard: advance_upper can lift upper_limit through empty trace regions whose batch messages are still undelivered (empty batches are transmitted when capabilities permit). When such a late empty batch arrives, upper_limit.clone_from(batch.upper()) regresses it below lower_limit (the previous joined upper). Normally advance_upper immediately re-lifts through the same empty region — its precondition is an empty trace batch with lower() == upper_limit exactly — and the frontier join repairs the rest. But if trace merges have meanwhile absorbed that empty region into a neighbor below (physical compaction only pins boundaries at-or-above the previous upper), the exact-boundary match fails, and the joined upper can end up not-greater-or-equal to lower_limit on some coordinates: a malformed interval [lower, upper).
We have never observed this (the release-mode tiling assert at the end of the tactic's batch construction would fire loudly, and it never has across extensive contended and simulated runs, including the #801 repro workloads). Consequences if it ever occurred look like assert failures rather than silent corruption, which is the right failure mode — but the invariant is currently maintained by coincidence of timing rather than by construction.
Suggested hardening, in the spirit of the span asserts added to the join in #802:
- make
upper_limitexplicitly monotone (onlyclone_froma received upper when it is at-or-beyond the current value, mirroring the join's guardedacknowledgedupdate), and/or assert!at retirement time thatlower_limit ≤ upper_limitas frontiers, so a malformed interval is named at its source instead of surfacing as a downstream tiling failure.
count/threshold use advance_upper only to advance compaction and process every received batch; they have neither the join's skip guard nor this interval shape to maintain.
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start at the reduce_with_tactic implementation and read the closing comment from #801 and #802 for the related join hardening. Trace upper_limit, lower_limit, advance_upper, and the release-mode tiling assertion, then verify that retirement preserves a monotone upper and that malformed intervals are caught at their source during the contended and simulated workloads mentioned.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- distributed-systems
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 48/100