# Binpacking & Set Theory: A Tutorial

One thing a good scheduler must do is “binpack”, which is the art of finding the right spot for your special program to run in a group of otherwise able computers. Computers have limited resources, and staying within those limits is key to having a good multi-tenant experience. Binpacking is named as such in relationship to the concept of several bins of pears at a pear farm in a line, collecting pears from the trees. You will fill the bins at different rates, so knowing both when the bins are full and how to divert the resources to available bins is a very important part of scheduling.

Binpacking is fundamentally a set theory problem, which I will demonstrate with basic binary operations. This is a simplification of the problem, but we’ll get into more advanced scenarios in a bit.

First off, the goal is to turn all these `0`

s into `1`

s:

1 | 0100000100001000 |

Until then, the number really isn’t saturated, now is it? So let’s do a binary “exclusive OR” operation with this other number! This will give us the result we want:

1 | 1011111011110111 |

Since “exclusive OR” gives us a `1`

if either is true, but not both, we get the result we want without colliding.

1 | 1111111111111111 |

And this number cannot be amended now without turning a `1`

back into a `0`

. This is the basis of how a scheduler works within a single node, but also amongst the whole cluster.

Think of each one of those `1`

s as a taken CPU, and every `0`

as a free one. Now, this is a single vector, which we can combine with other vectors such as memory usage or even much more subtle metrics like CPU pressure to determine a suitable host to stuff our container or VM onto.

A good way to express set theory with an arbitrary number of parameters is SQL, since it is more or less designed to handle this problem in all sorts of nefarious ways. Most of this tutorial will be based in the SQL language, so if you want to take it to your favorite general purpose language and use these ideas that way, great! It’s probably gonna handle SQL fine. Also keep in mind that none of these techniques are expressly limited to SQL, they’re just easier to model in a SQL language. A RDBMS generally has other drawbacks that many schedulers, especially big ones made by Google are not willing to tolerate. As with any large undertaking of importance, it’s critical to weigh your advantages and your disadvantages to the given situation.

All SQL is targeted at PostgreSQL idioms, but should be trivial to port to e.g. SQLite or MySQL.

Let’s start with a good schema for our database:

1 | -- list of the nodes. this is our physical (as far as we're concerned at least) |

To reiterate what the comments say, we keep one table, called `nodes`

, which is a representation of our physical limits for each instance we manage. We then store a metric for each unit in use.

To enter a new node, we simply insert it with its fixed stats:

1 | INSERT INTO nodes (ip, total_cpus, total_mem, total_disk) values ('127.0.0.1', 24, 64, 100) returning id; |

To enter a new usage, we simply insert into the `nodes_stats`

table:

1 | INSERT INTO nodes_stats (node_id, metric) values (1, 'cpu'); |

To query nodes that are available for use, we have to get a little more creative. What we do here is count the number of metrics for a given vector that are in use, then we subtract that number from the total available and see if it meets our requirement. This is very similar to what the exclusive OR does above semantically, but just with larger pieces of data.

Please note in this query that `target_cpu`

, `target_mem`

and `target_disk`

are all placeholders and depend on what kind of data you wish to require. It’s also expected that you would do this with a transaction that also inserted the used data, ensuring basic atomicity.

1 | SELECT nodes.id, cpu.metric, mem.metric, disk.metric |

This query will select a free node every time, provided you’re inserting your metrics once you find something suitable in an atomic way.

Anyway, there you have it! Hope you enjoyed this, it was fun to put it together.