Re: [BuildStream] Scheduler optimization

[Tristan Van Berkom <tristan vanberkom codethink co uk>]

On Thu, 2019-03-28 at 09:30 +0000, Benjamin Schubert via buildstream-list wrote:
> Hey everyone,
>
> TLDR: I want to refactor the queues and scheduler from their current
> model to a push based model.
> I would need feeback on the approach to see if I'm not missing something.
> I would also need to know if there is any objections to my plan since
> this would be a
> significant refactoring effort.

This looks like a significantly large change. I think the direction is
the right one and don't object - I do have some strong opinions about
how it happens (currently your proposal is very high level and general,
so it's hard to imagine what exactly you intend as actual code
changes).

For instance, one of the purposes of `Queue.status()` is to skip
elements without every having launched a job, as Jonathan points out in
the sibling post - I think that is a valuable filter to have as
elements pass through queues - however it probably only has to happen
once per element which enters a queue right ?

[...]
> I therefore think we should be pushing items in the queue as soon as they are
> needed.

My greatest fear when I read the above is that an implementation might
end up having Element codepaths accessing the Scheduler.

Please be careful to ensure that doesn't happen - the Element is not
allowed to know what the scheduler is and should not even have any
abstract knowledge of what the queues are.

To maintain clean separation of logic; the elements should be able to
notify their owner (the Stream which ultimately creates them) that some
element related state change has occurred (like that an element has
been "fetched" or "assembled", or maybe also that assemble or fetch has
been scheduled, like _schedule_assemble(), if that turns out to be
important).

Once the Stream has received a notification of an element related state
change, it can then delegate the decision of whether to promote the
element into a new queue to the Scheduler or it's queues - but this
business logic of course belongs to the Scheduler, while only element
related state changes are known by the Element.

Further than this, I think we should probably have symmetry of
schedule/done (like _schedule_assemble() / _assemble_done()) related
events and have a single callback to marshal these events through the
appropriate codepaths.

> This is in details what I think should be done:
>
> 1) Don't store a list of all elements in each queue.
>     - Currently, every queue contains everything, and we need to go over it
>       everytime.

We will still want the status 3 lists for the UI - and I also think you
probably still need a ready list in order to throttle what jobs can be
launched using the _scheduler/resources.py logic.

Of course, once an element ends up in a queue's ready list, one needs
only to consult the resources to know if a job is allowed to run yet,
and one need not traverse the entire list but can just take the next
ready job.

> 2) Remove Queue.status() method, allowing to check if an element is ready
>     - Currently, this method is called on every element of the queue,
> in sequence,
>       until the queue has enough elements to use all the resources.

My suspicion is that this will again exist in some shape or form but
will not be called in the same way - for instance it might be that when
the Stream receives a notification that foo.bst has been "pulled", the
Scheduler will know that the next queue is the fetch queue, and will be
able to push the element into the fetch queue, it will probably still
ask the fetch queue whether it can be skipped at that time.

This is pure speculation and it might look different, but I think that
there is still some decision making that is in the domain of a specific
Queue which should still remain that way, and not jumbled into a big
master function which has too much knowledge of how all the individual
queues should work.

> 3) When setting an element for tracking, put it in the `track` queue.
>
> 4) When calling "set_required" on element, put the element in the fetch_queue.
>     - Currently, what happens is that the element is already in the
> queue, and when
>       "set_required" is called, a boolean is toggled, making the
> status of the element
>       go from WAITING to READY, and allows the queue to pick it.

Yes, but again I expect this to change significantly - probably we want
to reconsider whether there is really a need for `_schedule_assemble()`
and `_set_required()` to be separate things - instead we probably want
symmetry in events and have a schedule/done event triggered for each
kind of state transforming event.

> 5) When an element is put in the build queue, if all its dependencies
> are not ready,
> add the element to a list in every dependency that is not ready.

I follow what you are shooting for, they appear to be pretty big lists
and I wonder if there are other ways to determine this efficiently
without having lists this big.

More importantly, when you say: "Add the element to a list in every
dependency that is not ready", I agree with the concept, but I think
that these lists should not necessarily be stored on the elements
proper.

These lists are strictly scheduling related logic and the Element
should not have to know that they exist.

>  Whenever an
> element becomes done in this queue, go over this list and for every ready
> element put it in the queue.
>     - Currently, what happens is that the element is already in the
> queue, and whenever
>       it's status is checked, it will check if all its dependencies
> are available before
>       saying that it is ready.
>
>
> All other queues should just get the elements from the previous queue pushed
> to them when ready, as they don't have dependencies on other elements.
>
> One concern that was raised in the past was that we would lose the ordering
> of the build and that would decrease performance.
>
> We could prevent this by using a priority queue and sort elements when adding
> them. We would therefore still keep the stable ordering we have now.

Right now the queues are FIFO, only the initial addition of elements
into the queues are depth sorted, the other aspect is that later queues
have priority over early queues.

For the second aspect, of course later queues should have priority over
previous queues and that shouldnt change (this way we start building
things right away instead of waiting for everything to pass through the
pull queue before starting our first build).

For the first aspect of queues being FIFO, it is hard to say whether or
not this should remain the same - there is certainly room for improving
this in the future (for instance, we might one day need to allow
elements to declare token values for how resource intensive they are,
and we might want to prioritize more resource intensive elements when
they unblock other elements from processing).

> Does this plan seem sensible? Am I missing something? Any feedback is welcome!
> I plan to start working on this next week unless anyone has any
> objections to the
> plan.

The theory is very sensible and I am happy to see us go in this
direction, as I mentioned at the top; most of my concerns are only
about ensuring sane encapsulation of logic separated into sensibly
isolated modules.

I think that another bonus of this refactor will be that the functions
in Stream which launch sessions should probably have an easier time
constructing the scheduler and it's queues (I hope).

Cheers,
    -Tristan