TimelyDataflow / timely-dataflow

A modular implementation of timely dataflow in Rust
MIT License
3.25k stars 272 forks source link

timely: unconstrained lifetime for `CapabilityRef` #491

Closed petrosagg closed 1 year ago

petrosagg commented 1 year ago

Since the merge of https://github.com/TimelyDataflow/timely-dataflow/pull/429, CapabilityRefs have been made safe to hold onto across operator invocations because that PR made sure that they only decremented their progress counts on Drop. While this allowed async/await based operators to freely hold on to them, it was still very difficult for synchronous based operators to do the same thing, due to the lifetime attached to the CapabilityRef.

We can observe that the lifetime no longer provides any benefits, which means it can be removed and turn CapabilityRefs into fully owned values. This allows any style of operator to easily hold on to them. The benefit of that isn't just performance (by avoiding the retain() dance), but also about deferring the decision of the output port a given input should flow to to a later time.

After making this change, the name CapabilityRef felt wrong, since there is no reference to anything anymore. Instead, the main distinction between CapabilityRefs and Capabilities are that the former is associated with an input port and the latter is associated with an output port.

As such, I have renamed CapabilityRef to InputCapability to signal to users that holding onto one of them represents holding onto a timestamp at the input for which we have not yet determined the output port that it should flow to. This nicely ties up the semantics of the InputCapability::retain_for_output and InputCapability::delayed_for_output methods, which make it clear by their name and signature that this is what "transfers" the capability from input ports to output ports.

frankmcsherry commented 1 year ago

For reference: this is blocked on a more thorough understanding of the implications for the progress tracking protocol. Async encroached on their correctness, and we need to re-establish whether holding input message capabilities indefinitely is safe, and under what conditions they can be transformed into output capabilities. This was verified for output capabilities a while ago, but the reasoning was delicate and relied on the inability to exchange output capabilities; as input capabilities correspond to messages, that inability no longer exists, and the progress tracking correctness may be more tenuous.

frankmcsherry commented 1 year ago

I think this is fine. The lifetime was not constraining the order of execution, rather attempting to remind folks not to stash these because it is a smell when you do (many early users of TD would do so, and stall out the computation). So, instead they have that footgun again but things are a bit simpler. Perhaps we'll add it back at some point.