implementation of VM migration path-finding algorithm
APACHE-2.0 License
In a populated compute cloud, there are several scenarios in which it's beneficial to be able to rearrange VM guest instances into a different placement across the hypervisor hosts via migration (live or otherwise), using a policy based on some business need, such as optimising performance or maximising return on hardware investment.
In this blog post, I went into more detail on these scenarios, took a look at the status quo in OpenStack and the computer science behind the problem, and briefly mentioned that I have a working implementation of an algorithm which reliably calculates a reasonably optimal sequence of VM migrations from a given initial placement to a given final placement. This repository provides the code for that implementation. Here it is in action:
For more details on the algorithm design and implementation, please
see doc/algorithm.md
.
The code is provided as a set of Python classes in the src/
directory, but there are several frontend interfaces with which
you can run the algorithm directly:
src/animate.py
- for a single (current, target) state pair, finds asrc/debug.py
- runs the solver on one ofsrc/demo.py
- randomly generates (current, target) state pairs,src/repl.py
- REPL interface which lets you manually specifysrc/soaktest.py
- randomly generates (current, target) state pairs, launchessrc/test.py
- a test runner which runs the algorithm onThe backend code implementing the algorithm comprises of the following files:
src/pathfinder.py
- base class providing container forsrc/dijkstra.py
- naive Dijkstra implementation Isrc/aspiers.py
- my algorithm
This code is supported by several OO helper classes:
src/vm.py
- models a single VM (RAM / architecture requirements)src/vmhost.py
- models a single VM hypervisor hostsrc/vmmigration.py
- models a single live migration of asrc/vmpoolstate.py
- models a pool of VMs and VM hostssrc/vmpoolpath.py
- models an ordered sequence of VM shutdowns,src/vmpoolstateerrors.py
- exception classessrc/vodict.py
- an implementation of a value-ordered dictionary,src/dijkstra.py
Please see the CONTRIBUTING file.
This repository is released under the Apache 2.0 license in order to be compatible with the OpenStack project; however I am open to the idea of dual-licensing if anyone needs this.
Thanks to the awesomeness of my employer SUSE, once or twice a year I get to work on whatever I want for a whole week. We call it Hack Week! And I've actually been (very sporadically) working in my spare time on designing and implementing this algorithm for the last four years or so. So for Hack Week 10 (7th--11th October 2013), I decided to finally complete this proof of concept implementation. Embarrassingly, it took me until May 2015 to publish the code and blog about it, but better late than never ...
I became fascinated with the potential of using orchestration techniques to optimise large-scale virtualized environments around 2007 or so, when I was a data center architect working in Novell's sales division. Around that time, Novell acquired a small Californian company called RedMojo, together with some amazing orchestration / virtualization management technology which became ZenWorks Orchestrator. It was later rebranded as PlateSpin Orchestrate in 2008 after Novell's acquisition of PlateSpin, which had also some very interesting virtualization environment optimization technology.
As an orchestration engine, PlateSpin Orchestrate was way ahead of its time, and I had fun building demonstrations of the huge potential of policy-based management of large-scale virtualized environments. I left the sales division to join the engineering team for PlateSpin Orchestrate, and it eventually became the backend for NetIQ Cloud Manager.
These experiences got me thinking about possible generalized solutions to the problem of optimizing large-scale virtualized environments, and so the ideal for this path-finding approach was born.