4 ms·

Ask HN: help needed on VM placement algorithm

8 points by kuvkir 17y ago

Hello! I'm working on a "cloud computing" management system and need help on a VM placement/provision algorithm. Let us assume we have a cluster of N physical servers. Each server has a single type of resource - slots (Note that in real world servers have more resources CPU/memory/disk/etc...). Let a server have M slots. Servers can run virtual machines, every VM occupies from 1 to M slots. Once the VM (with k slots) starts on a server, the number of free server slots is reduced accordingly. When the VM stops, the occupied slots are freed. VMs can live-migrate across servers. For example, when there is no server with M free slots (every server runs at least one VM), and we need to start an M-slot VM - there we need to rearrange VMs across a cluster. The goal is implement a VM placement policy to satisfy the following requirements: * utilize server resources in a uniform way, e.g. if we have 3 servers and 3 single-slot VMs we should place them on different servers. * minimize number of VM migrations as it is a costly operation. It looks like the problem in question has something to do with multiple knapsack problem, so I'm looking for some kind of heuristic algorithm. Any advise / papers / working solutions ? Thanks in advance, Kirill

eru 17y ago
I will look into your problem. Perhaps I can work out an integer linear formulation that you can feed into a standard solver for linear optimization problems. If you want to read papers on the subject, look for 'scheduling' or 'production planning'. 'Bin packing' and 'cutting stock' might also be related. Do you need an online solution or do you know all demands in advance? Also what do you do when not enough slots are available for all VMs? That could happen either because the number of slots in demand is higher than the supply --- or a bit more subtle: Say you have n servers, and n+1 VMs each taking M/2+1 slots. The total number of slots suffices, but still your VMs do not fit the machines.
- kuvkir 17y ago
  Thanks for your reply, eru! > Do you need an online solution or do you know all demands in advance? The online solution, as we don't know the type of load in advance. It resembles tetris in some way, meaning that we don't know which piece you'll get next. > Also what do you do when not enough slots are available for all VMs? If it's not theoretically possible to host all VMs like in examples you provided, nothing can be done. But it's not an algorithmic problem, in real world new servers should be bought in that case.
  - rjprins 17y ago
    Wait, this is very simple: Always pick the server with the most slots open. Only when no server has enough space to accomodate the next machine, but together they have enough space, should you apply a packing algorithm.
    - eru 17y ago
      If this is so simple, please prove the optimality of your solution. I can imagine that, when you have a perfect fit i.e. a machine that has l slots open and a VM that takes l slots, putting the VM on that machine might prove a good idea. At least when moving VMs is not too cheap compared to the advantages of a homogeneous load.
      - rjprins 17y ago
        Okay, you have two conflicting criteria: Spreading load and minimizing VM movements: Algorithm A: Always choose the server with the most slots free spreads the load most equally without moving VM's. (Assuming servers are equal in capacity. Minimizing load-balance is defined as minimizing the difference between highest loaded server and lowest loaded server.) Proof: Given a VM to be placed, v, and a set of servers S of which server s' is has most slots free. Say picking s' to place v does not give the most optimal load-balance. Then there must be server with with more slots free then s', contradiction. Algorithm B: Let S be a series of servers ordered by load (lowest number of free slots first). Put a new VM v on the first server s, on which v fits. This maximizes the initial number of VM's you can place without moving VM's, without prior knowledge. Proof: Because we always try to fit each VM in the first server possible, we maximize the amount of consecutive space on the last server. Thus, without prior knowledge, this maximizes the number of VM's we can place. I take it you like neither of these solutions. You want to compromise between the two solutions. Doing that right (there is not optimal in that sense) would depend on the scale difference between servers slots and space required by VM's. If VM's are small and servers big, you can safely go for load balance. If VM's are big and servers relatively small, you may go for B.
        17y ago
rjprins 17y ago
Is it first come first serve? Very interesting, I'll see what I can work out..

8 points by kuvkir 17y ago

eru 17y ago

I will look into your problem. Perhaps I can work out an integer linear formulation that you can feed into a standard solver for linear optimization problems. If you want to read papers on the subject, look for 'scheduling' or 'production planning'. 'Bin packing' and 'cutting stock' might also be related. Do you need an online solution or do you know all demands in advance? Also what do you do when not enough slots are available for all VMs? That could happen either because the number of slots in demand is higher than the supply --- or a bit more subtle: Say you have n servers, and n+1 VMs each taking M/2+1 slots. The total number of slots suffices, but still your VMs do not fit the machines.

kuvkir 17y ago
Thanks for your reply, eru! > Do you need an online solution or do you know all demands in advance? The online solution, as we don't know the type of load in advance. It resembles tetris in some way, meaning that we don't know which piece you'll get next. > Also what do you do when not enough slots are available for all VMs? If it's not theoretically possible to host all VMs like in examples you provided, nothing can be done. But it's not an algorithmic problem, in real world new servers should be bought in that case.
- rjprins 17y ago
  Wait, this is very simple: Always pick the server with the most slots open. Only when no server has enough space to accomodate the next machine, but together they have enough space, should you apply a packing algorithm.
  - eru 17y ago
    If this is so simple, please prove the optimality of your solution. I can imagine that, when you have a perfect fit i.e. a machine that has l slots open and a VM that takes l slots, putting the VM on that machine might prove a good idea. At least when moving VMs is not too cheap compared to the advantages of a homogeneous load.
    - rjprins 17y ago
      Okay, you have two conflicting criteria: Spreading load and minimizing VM movements: Algorithm A: Always choose the server with the most slots free spreads the load most equally without moving VM's. (Assuming servers are equal in capacity. Minimizing load-balance is defined as minimizing the difference between highest loaded server and lowest loaded server.) Proof: Given a VM to be placed, v, and a set of servers S of which server s' is has most slots free. Say picking s' to place v does not give the most optimal load-balance. Then there must be server with with more slots free then s', contradiction. Algorithm B: Let S be a series of servers ordered by load (lowest number of free slots first). Put a new VM v on the first server s, on which v fits. This maximizes the initial number of VM's you can place without moving VM's, without prior knowledge. Proof: Because we always try to fit each VM in the first server possible, we maximize the amount of consecutive space on the last server. Thus, without prior knowledge, this maximizes the number of VM's we can place. I take it you like neither of these solutions. You want to compromise between the two solutions. Doing that right (there is not optimal in that sense) would depend on the scale difference between servers slots and space required by VM's. If VM's are small and servers big, you can safely go for load balance. If VM's are big and servers relatively small, you may go for B.
      - 17y ago

rjprins 17y ago

Is it first come first serve? Very interesting, I'll see what I can work out..