TimelyDataflow / TimelyDataflow/differential-dataflow

The `group` operator is insane

Open
#28 1 comment 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

The group operator does several clever things, each of which are meant to make sense, but collectively it does some things that are hard to rationalize.

Specifically, I have recently seen (but can no longer reproduce, since #27) panics in group where it determines an interesting time t for which it does not hold a capability, and panics when it tries to warn itself about the time (as it cannot acquire a capability). In each round group downgrades its capabilities to the frontier of times it has been warned about, and collects new capabilities from its inputs. For the panic to happen, it would seem to mean that the new warning was in potentially dead space, where the operator has previously committed to no output.

This isn't fundamentally wrong. The warnings are conservative, and would could take the fact that the warning is not in the future of a capability as evidence that we could not possibly produce data at its time. That may be true, but it makes it much harder to sanely understand the properties of the group operator.

I would have much higher confidence about the implementation of group if there were more invariants, and corresponding debug_assert! statements, sprinkled throughout the code. Correspondingly, it would help if the structure of the implementation lent itself to having more invariants, which I think is possible (and has been its recent direction).

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 by locating the group operator and reviewing how each round downgrades capabilities, collects capabilities from inputs, and handles warnings. Define the relevant invariants and add corresponding debug_assert! statements, while restructuring the implementation where needed so those invariants are easier to establish.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
distributed-systems, stream-processing
Issue type
Refactor
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
20/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.