datafusion: [Epic] Pipeline breaking cancellation support and improvement

Is your feature request related to a problem or challenge?

We have done the first step in https://github.com/apache/datafusion/pull/16196 for pipeline breaking cancellation support, this epic trace the remaining sub-task for the remaining improvement. cc @ozankabak @alamb @pepijnve

  • Adding a few tests (maybe SLT?) that show YieldStreamExec being inserted. Also add logs related to built-in YiedStream.

  • Improving the documentation to make it clear that any leaf (source) that already yields just has to implement

fn with_cooperative_yields(self: Arc<Self>) -> Option<Arc<dyn ExecutionPlan>> {
    Some(self)
}

to signal the planner that no YieldStream combinator is necessary.

  • Improving InsertYieldExec rule by means of an API that exposes input and output pipelining behaviors of operators effectively

  • Investigating whether any already-existing manual yielding (for example, like the one in RepartitionExec) can now be removed

  • We will think about supporting cases involving non-volcano (e.g. spill) data flow.

  • Fix the corner case provided in this link: https://gist.github.com/pepijnve/0e1a66f98033c6c44c62a51fb9dbae5a

Feel free to add more tasks, thanks!

Describe the solution you’d like

No response

Describe alternatives you’ve considered

No response

Additional context

No response

About this issue

  • Original URL
  • State: closed
  • Created a year ago
  • Reactions: 2
  • Comments: 30 (30 by maintainers)

Most upvoted comments

fixes any bugs / adds features over the current one, Is “just” cleaner way to implement the same thing (this is also a fine thing to contribute as well).

There are a couple of benefits.

It removes the edge case seen in the interleave operator (or any select! style code in general). With the current per stream counter, one stream might want to yield, but the parent stream may decide to poll another stream in response which happens to be ready. The end result is that two cooperating streams may turn into a non-cooperating when they are merged. To fix this, you would need to adjust the merging operator as well and we’re basically back where we started. If all cooperating streams use the same budget, then this problem goes away. Once the yield point has been hit, all cooperating streams will yield.

Using the task budget also avoids the ‘redundant yield’ problem in the current version. If you now do a simple SELECT * FROM ... query, by default you’ll get a Pending after every 64 Ready(RecordBatch). With the task budget you will only actually inject the Pending when it’s actually necessary. The system automatically does the right thing.

Finally it aligns the cooperative yielding strategy across the library. RecordBatchReceiverStream is implicitly already using this strategy in a way you cannot opt out of. It’s better to have one consist way of solving this cancellation problem once and for all.

I have a patch almost ready. I’ll make a draft PR already so this all becomes a bit more tangible.

pipeline mode and pipeline breaking

I’m starting to realize we might have been placing too much emphasis on this aspect. I’ve been doing my homework by reading the Volcano paper. I had never read that paper in depth (never has a need to), I just knew that people used the term to kind of refer to ‘the iterator approach’. The more I read the more I can see DataFusion is basically a modern day Volcano.

One thing DataFusion does not have explicitly, as far as I know, is an exchange operator. I say not explicitly, because the essential demand/data-driven switch part of exchange is present in a couple of operators like Repartition and Coalesce. Perhaps these dataflow change points are a better way of looking at the problem.

I really miss having a white board, but here’s an approximation :smiling: This is from the Volcano paper (with annotations by me of course).

Image

Each of the colored blocks is an independently executing sub portion of the query. Translated to Tokio each of these colored blocks is a separate concurrent task. Each of those tasks needs to be cooperatively scheduled to guarantee all of them get a fair share of time to run.

As we’ve concluded earlier the output side of the exchange-like operators is already handling this for us implicitly because they consume tokio task budget. The table sources (Scan in the image) do not.

Perhaps this reframing of the problem is the path to a general purpose solution. To verify correct scheduling behavior, you can first subdivide the plan into subplans using the exchange-like operators as cut points. Per sub plan you can then look at all the leave nodes. Each leave node that ‘inserts’ work into the task needs to consume from the same task-wide tokio budget, not a per operator budget as we’re doing today.

So what does all this mean in terms of implementation:

  • Replace the per operator counters with consuming the Tokio task budget. DataFusion is already doing this today so there’s precedent for it, and it resolves a bunch of side effects. I’ve opened a PR in tokio to allow us to use the necessary API for this https://github.com/tokio-rs/tokio/pull/7405. I think we can approximate poll_proceed with a combination of ‘has budget’ and ‘consume budget’ in the meantime.
  • Remove the configuration option
  • Consider renaming YieldStream to CooperativeStream.
  • I think I would prefer a declarative property on ExecutionPlan that communicates if an operator consumes the task budget (not sure what the best description of this would be) instead of with_cooperative_yielding. It’s not really something you want to opt-in to after all and the exchange-like operators have no way of opting out.

The one thing that we still cannot solve automatically then is dynamic query planning. Operators that create streams dynamically still have to make sure they set things up correctly themselves.

One possible downside to this approach is that the cooperative scheduling budget is implementation specific to the Tokio runtime. DataFusion becomes more tied to Tokio rather than less. Not sure if that’s an issue or not.

@alamb @ozankabak wdyt? Maybe this is what you were going for all along and I’m just slowly catching up :smiling:

The change of heart comes from the realization that Tokio itself also takes a ‘consume at the leaves’ strategy and having a task wide budget ensures that tasks cannot silently ignore the yield request. Once one resource depletes the budget, it’s no longer possible to make progress anywhere else provided all resource participate in the budgeting system.

@alamb @ozankabak wdyt? Maybe this is what you were going for all along and I’m just slowly catching up :smiling:

The change of heart comes from the realization that Tokio itself also takes a ‘consume at the leaves’ strategy and having a task wide budget ensures that tasks cannot silently ignore the yield request. Once one resource depletes the budget, it’s no longer possible to make progress anywhere else provided all resource participate in the budgeting system.

A draft PR would be good to have, I think I can make better comments then. However, solving this at the stream level in a way transparent to the operator builder would be great in general. That was my original intention, but we weren’t able to materialize that solution in a reasonable amount of time. Hence the current solution, which is basically a fallback that has some characteristics of the ideal solution (e.g. “transparency”, focusing on leaves etc.), but requires support from the planner via to-be-designed APIs. The current approach can evolve into a decent one with such APIs, but it would always be worse than a proper lower-level solution. It would be good if we can build that, but in the meantime, I am glad that we have some solution that works for many cases.

If it turns out that we can arrive at a proper stream-based solution quickly, we can retire this one quickly. Otherwise, we can incrementally improve what we have today as alternatives go through design/experimentation etc.

This is true in theory – but I think we also take pains to try and avoid “over scheduling” tasks in tokio – for example, we purposely only have N input partitions (and hence N streams) per scan, even if there are 100+ files – the goal is to keep all the cores busy, but not oversubscribed.

What I was trying to say is that from a scheduling/yielding pov you can reason about each box in isolation. Whether you actually try to make 100s of concurrent (not parallel) tasks or not is a rabbit hole for another thread 😄

@zhuqi-lucas with all the various sprawling discussion threads I think we may have gotten to a point where it’s no longer easy to have an overview of what the problems are and what the final goal may look like. To make matters worse there are multiple options. I was thinking it might be useful to try and put together some kind of design document / overview that clearly describes the cancellation/abort problem, its root cause(s), the existing mitigations and possible future mitigations. Having a bit of a mea culpa moment, so I would like to take a shot at making a first draft. Is that ok for you? Any preference wrt tooling? I usually write my technical docs in asciidoc+plantuml for ease of version control and diffing, but willing to use whatever people prefer.

Figured it out. File access is done via object store and object store uses std::fs::File, not tokio::fs::File. Even if it would, from browsing the code it doesn’t look to me like Tokio’s file stuff consumes budget.

I tried reworking YieldStream to use the Tokio budget, but I don’t see a way to. I rephrased the issue I opened at https://github.com/tokio-rs/tokio/issues/7403.

Sorry, I usually do this around a white board.

Yeah I agree doing this kind of thing with a whiteboard is easier. I am happy to set up a video call with the relevant parties if that might be more efficient (and it would be nice to meet you all “face to face”)

First and foremost I’m trying to communicate what I see as intrinsic problems with the external optimizer rule approach. This was countered with a belief that it can be solved, but I don’t see it yet myself.

Indeed – it is my perspective that

  1. https://github.com/apache/datafusion/pull/16196 handles most, but not all, cases where an Stream implementation may not yield directly.
  2. For some of the more advanced cases you describe (like switching a stream mid-execution) the general optimizer approach will not permit cancelling and thus the individual stream implementations need to be made yield aware.

stream in a YieldStream". #16301 does not make use of Tokio’s coop budget yet however. Instead it’s the per-operator counter variant. The diff per operator does illustrate the scope and nature of the change Stream implementers would need to make.

This makes sense (and I am sure we could encapsulate the changes from 16301 more too if we go with that approach)

I wonder if your main concern is that the optimizer approach we merged does not handle all of the cases, so it potentially leaves a trap for future Stream implementors (who do more avanced streams)?

Tokio’s cooperative budget is essentially a counter per task that can be decremented at any point in the task. When the counter hits zero you’ll return Pending from the function trying to consume the budget. That’s basically what YieldStream is doing but with a local counter rather than a task wide one.

DataFusion’s ReceiverStreamBuilder makes use of tokio::sync::mpsc::Receiver. Whenever Receiver::recv is being called, that counter is being decremented, and you’ll get a Pending result when the budget is depleted. This is the same thing as what YieldStream is trying to do.

The benefits I see of trying to leverage the same mechanism elsewhere in DataFusion are:

  • There is only one cooperative yielding mechanism at play. This is easier to reason about than multiple interacting ones.
  • There is no need for additional API. DataFusion is already using this in the current released version.
  • There are fewer corner cases. Once the budget is depleted, any point in the code checking the budget will yield since all those points are checking the same shared counter.

The downsides remain:

  • Code that loops may still need to have yield points added to it in order to not yield unnecessarily.
  • It’s not yet 100% clear to me how you can use this in manually written Futures and Streams. The required bits for that seem to only be crate visible in the current Tokio release. I’ve raised the question here https://github.com/tokio-rs/tokio/issues/7403
  • I have not made a performance analysis of this yet, but since it’s used quite extensively already it’s likely to be ok. Needs to be evaluated.