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)
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 aPendingafter every 64Ready(RecordBatch). With the task budget you will only actually inject thePendingwhen it’s actually necessary. The system automatically does the right thing.Finally it aligns the cooperative yielding strategy across the library.
RecordBatchReceiverStreamis 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.
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).
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:
poll_proceedwith a combination of ‘has budget’ and ‘consume budget’ in the meantime.ExecutionPlanthat communicates if an operator consumes the task budget (not sure what the best description of this would be) instead ofwith_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.
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.
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, nottokio::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.
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”)
Indeed – it is my perspective that
Streamimplementation may not yield directly.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
ReceiverStreamBuildermakes use oftokio::sync::mpsc::Receiver. WheneverReceiver::recvis 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:
The downsides remain: