diff options
| author | Balazs Gibizer <gibi@redhat.com> | 2022-06-15 09:28:27 +0200 |
|---|---|---|
| committer | Balazs Gibizer <gibi@redhat.com> | 2022-06-15 12:40:48 +0200 |
| commit | 099a6f63af7805440d91976ba0ea03bc6c278280 (patch) | |
| tree | 90dcb82486bffebd55ab100b9329d55a7272b7e9 /releasenotes | |
| parent | d86916360858daa06164ebc0d012b78d19ae6497 (diff) | |
| download | nova-099a6f63af7805440d91976ba0ea03bc6c278280.tar.gz | |
Optimize numa_fit_instance_to_host
The numa_fit_instance_to_host algorithm tries all the possible
host cell permutations to fit the instance cells. So in worst case
scenario it does n! / (n-k)! _numa_fit_instance_cell calls
(n=len(host_cells) k=len(instance_cells)) to find if the instance can be
fit to the host. With 16 NUMA nodes host and 8 NUMA node guests this
means 500 million calls to _numa_fit_instance_cell. This takes excessive
time.
However going through these permutations there are many repetitive
host_cell, instance_cell pairs to try to fit.
E.g.
host_cells=[H1, H2, H2]
instance_cells=[G1, G2]
Produces pairings:
* H1 <- G1 and H2 <- G2
* H1 <- G1 and H3 <- G2
...
Here G1 is checked to fit H1 twice. But if it does not fit in the first
time then we know that it will not fit in the second time either. So we
can cache the result of the first check and use that cache for the later
permutations.
This patch adds two caches to the algo. A fit_cache to hold
host_cell.id, instance_cell.id pairs that we know fit, and a
no_fit_cache for those pairs that we already know that doesn't fit.
This change significantly boost the performance of the algorithm. The
reproduction provided in the bug 1978372 took 6 minutes on my local
machine to run without the optimization. With the optimization it run in
3 seconds.
This change increase the memory usage of the algorithm with the two
caches. Those caches are sets of integer two tuples. And the total size
of the cache is the total number of possible host_cell, instance_cell
pairs which is len(host_cell) * len(instance_cells). So form the above
example (16 host, 8 instance NUMA) it is 128 pairs of integers in the
cache. That will not cause a significant memory increase.
Closes-Bug: #1978372
Change-Id: Ibcf27d741429a239d13f0404348c61e2668b4ce4
Diffstat (limited to 'releasenotes')
| -rw-r--r-- | releasenotes/notes/bug-1978372-optimized-numa-fitting-algorithm-5d5b922b0bdbf818.yaml | 9 |
1 files changed, 9 insertions, 0 deletions
diff --git a/releasenotes/notes/bug-1978372-optimized-numa-fitting-algorithm-5d5b922b0bdbf818.yaml b/releasenotes/notes/bug-1978372-optimized-numa-fitting-algorithm-5d5b922b0bdbf818.yaml new file mode 100644 index 0000000000..3f42f70908 --- /dev/null +++ b/releasenotes/notes/bug-1978372-optimized-numa-fitting-algorithm-5d5b922b0bdbf818.yaml @@ -0,0 +1,9 @@ +--- +fixes: + - | + The algorithm that is used to see if a multi NUMA guest fits to + a multi NUMA host has been optimized to speed up the decision + on hosts with high number of NUMA nodes ( > 8). For details see + `bug 1978372`_ + + .. _bug 1978372: https://bugs.launchpad.net/nova/+bug/1978372 |