Measurements

This page features measurements performed on Splinter to evaluate following approaches to work stealing:

Steal from right

This approach assigns the core at right as sibling. The first core is the sibling of last core. For example in a 4-core system, siblings are as follows:

Core 0's sibling is core 1

Core 1's sibling is core 2

Core 2's sibling is core 3

Core 3's sibling is core 0

This approach has the advantage that it doesn't have to make a selection decision at run time. Neither does it have to maintain stats like number of packets received, number of packets sent, and/or queue depth. It is labelled as "right" in the figures.

Power of 2 choices

Each core has all of other cores as siblings. When deciding where to steal work from, the core randomly picks two siblings from the list of siblings, and selects the one that has the most queue depth. Queue depth is maintained by each core. It is basically the difference between number of packets received and number of packets sent. It is stored as AtomicUsize so reads and writes are atomic i.e. we don't need locks when reading and writing queue depth. As an example, the sibling list of a 4-core system looks as follows:

Core 0's siblings: [1, 2, 3]

Core 1's siblings: [0, 2, 3]

Core 2's siblings: [0, 1, 3]

Core 3's siblings: [0, 1, 2]

This approach is labelled as "2choices" in the figures.

Last selected sibling

This is an enhancement of power-of-2-choices approach. The core remembers its last-selected sibling. When making a new sibling selection, it picks just one sibling randomly, compares the queue depth of last-selected with the newly-picked one, and selects the one with the most queue depth. This approach has an advantage of picking just one core randomly, hence the random number generation overhead is less than the power-of-2-choices. Intuition here is that under highly skewed workload, all idle cores will converge to selecting the core(s) with high load. It is labelled as "last" in the figures.

Methodology

Each of the above approaches is compared with every other approach for tenant skews 0.1, 0.5, 0.9, 0.99. The graphs below are listed in following order for each tenant skew: