TimelyDataflow / TimelyDataflow/differential-dataflow

reduce driver: late empty batches can transiently regress upper_limit (hardening follow-up from #801)

Open
#806 0 comments 0 reactions 0 assignees View on GitHub

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_limit explicitly monotone (only clone_from a received upper when it is at-or-beyond the current value, mirroring the join's guarded acknowledged update), and/or
  • assert! at retirement time that lower_limit ≤ upper_limit as 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

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.