Xen 4.2 Automatic NUMA Placement

NUMA Placement

First of all, just notice that optimally fitting VMs on a NUMA host is an incarnation of the Bin Packing Problem, which means it is NP-hard, so an heuristic approach must be undertaken.

Concentrating on memory, what if we have a bunch of nodes, each with its own amount of free memory, and we need to decide where a new VM should be placed? This RFC patch series includes two patches (8/10 and 9/10) implementing three possible NUMA placement policies:

• greedy, which scans the host’s node and put the VM on the first one that is found to have enough free memory;
• packed, which puts the VM on the node that has the smallest amount of free memory (although still enough for the VM to fit there);
• spread, which puts the VM on the node that has the biggest amount of free memory.

The names comes from the intrinsic characteristics of the three algorithms. In fact, greedy just grabs the first suitable node, packed tends to keep nodes as full as possible while spread tries to keep them as free/empty as possible. Notice that keeping the nodes full or empty should be intended memory-wise here, but that it also imply the following:

• greedy and packed policies are both incline to put as much VMs as possible on one node before moving on to try others (which one does that most, depends on the VMs' characteristics and creation order);
• spread is incline to distribute the VMs across the various nodes (although again, it will depend somehow on VMs' characteristics).

"Scientifically" speaking, greedy is based on the First Fit algorithm, packed is based on Best Fit and spread on Worst Fit.

For benchmarking the placement heuristics (full results available here), on the other hand, all the VMs have been created asking xl to use either the greedy, packed or spread policy. The aggregate throughput is then computed by summing the throughput achieved in all the VMs (and averaging the result).

It is easy to see that (in this case) both spread and packed placement works better than unpinned. That should have been expected, especially for spread, as it manages in distributing the load a bit better. Given the specific characteristics of this experiment, it should also have also been expected for greedy to behave very bad when load is small. In fact, with less than 5 VMs, all of them fit on the first NUMA node. This means memory accesses are local, but the load distribution is clearly sub-optimal. Also, the benefit we get from NUMA affinity seems to get smaller with the increase of the VM count. This probably have some relationship with the CPU overcommitment (starting at 5 VM).

NUMA Scheduling

Suppose we have a VM with all its memory allocated on NODE#0 and NODE#2 of our NUMA host. Of course, the best thing to do would be to pin the VM’s vCPUs on the pCPUs related to the two nodes. However, pinning is quite unflexible: what if those pCPUs get very busy while there are completely idle pCPUs on other nodes? It will depend on the workload, but it is not hard to imagine that having some chance to run –even if on a remote node– would be better than not running at all. It would therefore be preferable to give the scheduler some hints about where a VM’s vCPUs should be executed. It then can try at its best to honor these requests of ours, but not at the cost of subverting its own algorithm. From now on, we’ll call this hinting mechanism node affinity (don’t confuse it with CPU affinity, which is about to static CPU pinning).

As said, the experimental patchset introduces also the support for node affinity aware scheduling by means of this changeset: [sched_credit: Let the scheduler know about `node affinity`. As of now, it is all very simple, and it only happens for the credit1 scheduling plugin of the Xen hypervisor. However, looking at some early performance measurements seems promising.

Looking at the results, attempts to suggest the scheduler the preferred node for a VM seem to be the righ direction to go (For the interested, complete results set is here). The various curves in the graph below represents the throughput achieved on one of the VMs, more specifically the one that is being, respectively:

• scheduled without any pinning or affinity, i.e., (cpus="all" in the VM config file, red line, also called default in this article),
• created and pinned on NODE#0, so that all its memory accesses are local (green line),
• scheduled with node affinity only to NODE#0 (no pinning) as per what is introduced by the patch (blue line).

What the plot actually shows is the percent increase of each configuration with respect to the worst possible case (i.e., when all memory access are remote). This means tweaking node affinity increases performance by ~12% to ~18% from the worst case. Also, it lets us gain up to ~8% performance as compared to unpinned behavior, doing particularly well as load increases. However, although it gets quite close to the green line (which is the best case), there is still probably some performance bits to squeeze from it.

Combining Placement and Scheduling

So, if we do both things, i.e.:

• we introduce some form of automatic placement logic in xl. This means assigning a "node affinity" to a domain at creation time and asking Xen to stick to it;
• we tweak the scheduler so that it will strongly prefer running a domain on the node(s) it has affinity with, but not in a strict manner as it is for pinning.

The various lines have the same meaning described in the Xen NUMA Introduction article.

Here it is what the benchmarks tells. In all the graphs here, the light blue line is the interesting one, as it is representative of the case when VM#1 has its affinity set to NODE#0. The most interesting among the various plots is probably this one below:

We can see the "node affinity" curve managing in getting quite closer to the best case, especially under high system load (4 to 8 VMs). It can't be called as perfect yet, as some more consideration needs to be given to the not-so-loaded cases, but it is a start. If you feel like wanting to help with testing, benchmarking, fixing or whatever... Please, jump in!