TimelyDataflow / TimelyDataflow/timely-dataflow
Optimize progress traffic for some operators
Nobody has claimed this yet.
- Dominant language
- Rust
- Stars
- 3.6k
- Forks
- 293
- Avg merge
- 14h 46m
- Merged PRs (30d)
- 4
Description
Several operators do not require progress traffic.
Operators like map, concat, partition all produce exactly as many output records as they take as input. There should be no harm in immediately advancing all counts of records declared on their input as counts of records on their outputs. Although we don't know where the records are, or exactly when they will be consumed, the operators themselves are agnostic to this information and the only information downstream operators require is whether more records might arrive, not where they are at the moment.
Similarly, the feedback operator produces output or not based on the timestamp in question. If it is less than its upper bound, it produces the same output as input, and if not it does not produce the output. This also seems to require no advanced thinking, and could just be compiled down (although the rule is more complicated: "apply this logic" rather than "forward").
Hypothetically, the queue operator, which batches records by timestamp and releases them not-out-of-order, is an example of an operator that produces its input as output by requires notifications, so not all of these "simple" operators need to be progress-oblivious.
I think in the cases mentioned above the summary returned from get_internal_summary is actually a guarantee, not just a lower bound. It would be interesting if this could be communicated, as our current progress tracking mechanisms could just fold this into the path summaries.
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 by tracing get_internal_summary and how progress traffic and path summaries are handled. Compare the proposed treatment of map, concat, partition, feedback, and queue, especially which operators provide guarantees versus requiring notifications. Done means the guarantee is communicated and safely folded into path summaries without changing queue semantics.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- distributed-systems, performance, stream-processing
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100