Xen 4.2 Automatic NUMA Placement

Automatic NUMA Placement

With NUMA placement, we refer to the decision on out of which NUMA nodes in an host the memory for a newly created VM should be allocated. Unfortunately, fitting VMs on a NUMA host is an incarnation of the Bin Packing Problem, which means it is NP-hard, so heuristics is the only reasonable way to go.

Preliminary/Exploration Work

The first attempt of moving NUMA placement away of XEND's python code (to, in that case, libxc) dates back to 2010 (can't find the link anymore).

More recently, this patch series was released as an RFC on April 2012. In patches 8/10 and 9/10, it implemented three possible placement policies:

• greedy, which scans the host’s node and put the new VM on the first one that is found to have enough free memory;
• packed, which puts the new 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 new 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.

Some benchmarks, of all the three policies, were performed (as explained in details here). One of the obtained graphs is reported below. This shows the aggregate result of the SpecJBB2005 benchmark, concurrently run inside multiple VMs

That served as a quite effective confirmation that the spread (i.e., the one based on the worst fit algorithm) policy was the absolute best, and thus, in the continuation of the work on automatic placement, the othe twos could be neglected.

There was also a blog post about this, and it is still available here.

The Actual Solution

The Automatic NUMA placement Xen_NUMA_Roadmap#Automatic_VM_placement entry in the roadmap page may contain more information.

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!