Assume we have 8 RPs with 1 resource, and we request 8 groups
with 1 resource each.
The full candidate matrix for a single provider tree (compute node)
by satisfying each group independently (G is request group, R is RP):
G0: [R0, R1,..., R7] # G0 can be fulfilled from R0, R1, ..., R7
G1: [R0, R1,..., R7]
...
G7: [R0, R1,..., R7]
Placement needs to satisfy every group in the request so it
creates all the possible combinations (a Cartesian product) of the
individual group fulfilments and checks if they are valid, i.e if
there are no two or more groups trying to use the same single piece
of resource.
The product looks like
(C is candidate, G0-R0 means G0 group satisfied from R0 RP):
C0: [G0-R0, G1-R0, ..., G7-R0] # invalid, R0 has 1 res but C0 needs 8
C1: [G0-R0, G2-R0, ..., G7-R1] # invalid, R0 has 1 res but C1 needs 7
...
Cx: [G0-R0, G1-R1, ..., G7-R7] # valid, each Rx has 1 res and
# Cx ask form 1 res each
From this picture it is clear that:
* There are a lot more invalid candidates than valid ones. Actually
in this specific scenario the total number of candidates are
8^8 ~ 16M. The valid candidates are 8! ~ 40K. Finding the valid ones
by blindly searching all possible ones are scaling very badly as
exponential grows faster than factorial. I.e. valid candidates will be
farther apart from each other in the search space.
* There is a structure within and across the candidates. E.g. If we
know that C0 is invalid already because of G0-R0 and G1-R0 tries
to consume the same singe resource from R0 then:
* We don't need to check how G2 is mapped in C0 as that mapping cannot
change the fact the whole candidate is invalid.
* We know that every candidate that starts with G0-R0, G1-R0 are
invalid for the same reason and we don't need to generate and
test them
The latter means that C1...Cy (y < x - 1) can be pruned out from the
search space after C0 is tested. This is a lot of candidates. In the
above natural ordering of the product generation algorithm it is
actually more than 40K candidates that we can skip after just testing
C0 alone. When we reach Cx, the first valid candidate, the algo already
pruned out more than 300k candidates.
After this patch the above pruning logic is not turned on automatically
but can be enabled via the config option:
[workarounds]
optimize_for_wide_provider_trees = true
The implementation consists of the following pieces:
A recursive product generator algorithm that calls a function on each
partial candidate and if that function signals that the partial
candidate is invalid then the algorithm does skips any candidate that
has the same partial candidate prefix.
The recursion does a tree traversal to find all partial prefixes.
With the above G0-G8, RP0, RP8 example the start of the traversal
looks like:
1. partial product G0-RP0, this does not exceed capacity so recurse
2. partial product G0-RP0, G1-RP0, this exceeds capacity so do not
recurse but try another RP on this level.
3. partial product G0-RP0, G1-RP1, this does not exceeds capacity so
recurse.
4. partial product G0-RP0, G1-RP1, G2-RP0, this exceeds capacity so
do not recurse but try another RP on this level
...
Without the optimization Placement uses the logic
areq = _consolidate_allocation_requests(areq_list, rw_ctx)
if rw_ctx.exceeds_capacity(areq)
continue
on all products after it was generated. The
_consolidate_allocation_requests folds the individual
AllocationRequestResource object in the product into a single
allocation. This has a side effect on some of the ARRs so the logic does
copy the affected ARRs. This is expensive especially if we want to call
it on every partial product as well. However if we only want to check
the capacity we don't need to fold the ARRs we just need to sum the
amount each ARR hold and the check that against the capacity. So
_exceeds_capacity() was added to do this optimized, side effect and copy
free, capacity check when the optimization is enabled.
When a valid product is generated _consolidate_allocation_requests still
needs to be called to get the folded AllocationRequest in any case as
the caller of _merge_candidates expects such structure. But the final
rw_ctx.exceeds_capacity can we skipped if the optimization is enabled.
The depth of the recursion is equal to the number of iterables passed to
the product call. It can be seen by the fact that each level of
recursion appends a new item to the partial product and when the length
of the partial product equals to the number of iterables then we have a
full product and the algo yields. The default python recursion limit is
1000 so we are not really limited by that as that means we could handle
~ 990 iterables, meaning an allocation candidate query with 990 request
groups. The limiting factor of this algorithm is not recursion depth but
execution time.
Gemini 2.5 pro was used to put together the generic Cartesian product
algorithm.
Co-Authored-by: Sean Mooney <work@seanmooney.info>
Assisted-By: gemini-2.5-pro
Closes-Bug: #2126751
Change-Id: I13ab83a165c229ae57876df4570e8af25221a45e
Signed-off-by: Balazs Gibizer <gibi@redhat.com>
5b73b980d0