Although I am quite happy to have this tool at my disposal, implementing it was much more difficult and time consuming than I expected. Aside from the fact that the problem is not as obvious as it may sound, the main reason is that the Dynamic Disnix toolset was originally developed as a proof of concept implementation for a research paper under very high time pressure. As a result, it has accumulated quite a bit of technical debt, that as of today, is still at a fairly high level (but much better than it was when I completed the PoC).
For the ID assigner tool, I needed to make changes to the foundations of the tools, such as the model parsing libraries. As a consequence, all kinds of related aspects in the toolset started to break, such as the deployment planning algorithm implementations.
Fixing some of these algorithm implementations was much more difficult than I expected -- they were not properly documented, not decomposed into functions, had little to no reuse of common concepts and as a result, were difficult to understand and change. I was forced to re-read the papers that I used as a basis for these algorithms.
To prevent myself from having to go through such a painful process again, I have decided to revise them in such a way that they are better understandable and maintainable.
Dynamically distributing services
The deployment models in the core Disnix toolset are static. For example, the distribution of services to machines in the network is done in a distribution model in which the user has to manually map services in the services model to target machines in the infrastructure model (and optionally to container services hosted on the target machines).
Each time a condition changes, e.g. the system needs to scale up or a machine crashes and the system needs to recover, a new distribution model must be configured and the system must be redeployed. For big complex systems that need to be reconfigured frequently, manually specifying new distribution models becomes very impractical.
As I have already explained in older blog posts, to cope with the limitations of static deployment models (and other static configuration aspects), I have developed Dynamic Disnix, in which various configuration aspects can be automated, including the distribution of services to machines.
A strategy for dynamically distributing services to machines can be specified in a QoS model, that typically consists of two phases:
- First, a candidate target selection must be made, in which for each service the appropriate candidate target machines are selected.
Not all machines are capable of hosting a certain service for functional and non-functional reasons -- for example, a i686-linux machine is not capable of running a binary compiled for a x86_64-linux machine.
A machine can also be exposed to the public internet, and as a result, may not be suitable to host a service that exposes privacy-sensitive information. - After the suitable candidate target machines are known for each service, we must decide to which candidate machine each service gets distributed.
This can be done in many ways. The strategy that we want to use is typically based on all kinds of non-functional requirements.
For example, we can optimize a system's reliability by minimizing the amount of network links between services, requiring a strategy in which services that depend on each other are mapped to the same machine, as much as possible.
Graph-based optimization problems
In the Dynamic Disnix toolset, I have implemented various kinds of distribution algorithms/strategies for all kinds of purposes.
I did not "invent" most of them -- for some, I got inspiration from papers in the academic literature.
Two of the more advanced deployment planning algorithms are graph-based, to accomplish the following goals:
- Reliable deployment. Network links are a potential source making a distributed system unreliable -- connections may fail, become slow, or could be interrupted frequently. By minimizing the amount of network links between services (by co-locating them on the same machine), their impact can be reduced. To not make deployments not too expensive, it should be done with a minimal amount of machines.
As described in the paper: "Reliable Deployment of Component-based Applications into Distributed Environments" by A. Heydarnoori and F. Mavaddat, this problem can be transformed into a graph problem: the multiway cut problem (which is NP-hard).
It can only be solved in polynomial time with an approximation algorithm that comes close to the optimal solution, unless a proof that P = NP exists. - Fragile deployment. Inspired by the above deployment problem, I also came up with the opposite problem (as my own "invention") -- how can we make any connection between a service a true network link (not local), so that we can test a system for robustness, using a minimal amount of machines?
This problem can be modeled as a graph coloring problem (that is a NP-hard problem as well). I used one of the approximation algorithms described in the paper: "New Methods to Color the Vertices of a Graph" by D. Brélaz to implement a solution.
To work with these graph-based algorithms, I originally did not apply any transformations -- because of time pressure, I directly worked with objects from the Disnix models (e.g. services, target machines) and somewhat "glued" these together with generic data structures, such as lists and hash tables.
As a result, when looking at the implementation, it is very hard to get an understanding of the process and how an implementation aspect relates to a concept described in the papers shown above.
In my revised version, I have implemented a general purpose graph library that can be used to solve all kinds of general graph related problems.
Aside from using a general graph library, I have also separated the graph-based generation processes into the following steps:
- After opening the Disnix input models (such as the services, infrastructure, and distribution models) I transform the models to a graph representing an instance of the problem domain.
- After the graph has been generated, I apply the approximation algorithm to the graph data structure.
- Finally, I transform the resolved graph back to a distribution model that should provide our desired distribution outcome.
This new organization provides better separation of concerns, common concepts can be reused (such as graph operations), and as a result, the implementations are much closer to the approximation algorithms described in the papers.
Visualizing the generation process
Another advantage of having a reusable graph implementation is that we can easily extend it to visualize the problem graphs.
When I combine these features together with my earlier work that visualizes services models, and a new tool that visualizes infrastructure models, I can make the entire generation process transparent.
For example, the following services model:
{system, pkgs, distribution, invDistribution}:
let
customPkgs = import ./pkgs { inherit pkgs system; };
in
rec {
testService1 = {
name = "testService1";
pkg = customPkgs.testService1;
type = "echo";
};
testService2 = {
name = "testService2";
pkg = customPkgs.testService2;
dependsOn = {
inherit testService1;
};
type = "echo";
};
testService3 = {
name = "testService3";
pkg = customPkgs.testService3;
dependsOn = {
inherit testService1 testService2;
};
type = "echo";
};
}
can be visualized as follows:
$ dydisnix-visualize-services -s services.nix
The above services model and corresponding visualization capture the following properties:
- They describe three services (as denoted by ovals).
- The arrows denote inter-dependency relationships (the dependsOn attribute in the services model).
When a service has an inter-dependency on another service means that the latter service has to be activated first, and that the dependent service needs to know how to reach the former.
testService2 depends on testService1 and testService3 depends on both the other two services.
We can also visualize the following infrastructure model:
{
testtarget1 = {
properties = {
hostname = "testtarget1";
};
containers = {
mysql-database = {
mysqlPort = 3306;
};
echo = {};
};
};
testtarget2 = {
properties = {
hostname = "testtarget2";
};
containers = {
mysql-database = {
mysqlPort = 3306;
};
};
};
testtarget3 = {
properties = {
hostname = "testtarget3";
};
};
}
with the following command:
$ dydisnix-visualize-infra -i infrastructure.nix
resulting in the following visualization:
The above infrastructure model declares three machines. Each target machine provides a number of container services (such as a MySQL database server, and echo that acts as a testing container).
With the following command, we can generate a problem instance for the graph coloring problem using the above services and infrastructure models as inputs:
$ dydisnix-graphcol -s services.nix -i infrastructure.nix \ --output-graph
resulting in the following graph:
The graph shown above captures the following properties:
- Each service translates to a node
- When an inter-dependency relationship exists between services, it gets translated to a (bi-directional) link representing a network connection (the rationale is that a service that has an inter-dependency on another service, interact with each other by using a network connection).
Each target machine translates to a color, that we can represent with a numeric index -- 0 is testtarget1, 1 is testtarget2 and so on.
The following command generates the resolved problem instance graph in which each vertex has a color assigned:
$ dydisnix-graphcol -s services.nix -i infrastructure.nix \ --output-resolved-graph
resulting in the following visualization:
(As a sidenote: in the above graph, colors are represented by numbers. In theory, I could also use real colors, but if I also want that the graph to remain visually appealing, I need to solve a color picking problem, which is beyond the scope of my refactoring objective).
The resolved graph can be translated back into the following distribution model:
$ dydisnix-graphcol -s services.nix -i infrastructure.nix
{
"testService2" = [
"testtarget2"
];
"testService1" = [
"testtarget1"
];
"testService3" = [
"testtarget3"
];
}
As you may notice, every service is distributed to a separate machine, so that every network link between a service is a real network connection between machines.
We can also visualize the problem instance of the multiway cut problem. For this, we also need a distribution model that, declares for each service, which target machine is a candidate.
The following distribution model makes all three target machines in the infrastructure model a candidate for every service:
{infrastructure}:
{
testService1 = [ infrastructure.testtarget1 infrastructure.testtarget2 infrastructure.testtarget3 ];
testService2 = [ infrastructure.testtarget1 infrastructure.testtarget2 infrastructure.testtarget3 ];
testService3 = [ infrastructure.testtarget1 infrastructure.testtarget2 infrastructure.testtarget3 ];
}
With the following command we can generate a problem instance representing a host-application graph:
$ dydisnix-multiwaycut -s services.nix -i infrastructure.nix \ -d distribution.nix --output-graph
providing me the following output:
The above problem graph has the following properties:
- Each service translates to an app node (prefixed with app:) and each candidate target machine to a host node (prefixed with host:).
- When a network connection between two services exists (implicitly derived from having an inter-dependency relationship), an edge is generated with a weight of 1.
- When a target machine is a candidate target for a service, then an edge is generated with a weight of n2 representing a very large number.
The objective of solving the multiway cut problem is to cut edges in the graph in such a way that each terminal (host node) is disconnected from the other terminals (host nodes), in which the total weight of the cuts is minimized.
When applying the approximation algorithm in the paper to the above graph:
$ dydisnix-multiwaycut -s services.nix -i infrastructure.nix \ -d distribution.nix --output-resolved-graph
we get the following resolved graph:
that can be transformed back into the following distribution model:
$ dydisnix-multiwaycut -s services.nix -i infrastructure.nix \
-d distribution.nix
{
"testService2" = [
"testtarget1"
];
"testService1" = [
"testtarget1"
];
"testService3" = [
"testtarget1"
];
}
As you may notice by looking at the resolved graph (in which the terminals: testtarget2 and testtarget3 are disconnected) and the distribution model output, all services are distributed to the same machine: testtarget1 making all connections between the services local connections.
In this particular case, the solution is not only close to the optimal solution, but it is the optimal solution.
Conclusion
In this blog post, I have described how I have revised the deployment planning algorithm implementations in the Dynamic Disnix toolset. Their concerns are now much better separated, and the graph-based algorithms now use a general purpose graph library, that can also be used for generating visualizations of the intermediate steps in the generation process.
This revision was not on my short-term planned features list, but I am happy that I did the work. Retrospectively, I regret that I never took the time to finish things up properly after the submission of the paper. Although Dynamic Disnix's quality is still not where I want it to be, it is quite a step forward in making the toolset more usable.
Sadly, it is almost 10 years ago that I started Dynamic Disnix and still there is no offical release yet and the technical debt in Dynamic Disnix is one of the important reasons that I never did an official release. Hopefully, with this step I can do it some day. :-)
The good news is that I made the paper submission deadline and that the paper got accepted for presentation. It brought me to the SEAMS 2011 conference (co-located with ICSE 2011) in Honolulu, Hawaii, allowing me to take pictures such as this one:
Availability
The graph library and new implementations of the deployment planning algorithms described in this blog post are part of the current development version of Dynamic Disnix.
The paper: "A Self-Adaptive Deployment Framework for Service-Oriented Systems" describes the Dynamic Disnix framework (developed 9 years ago) and can be obtained from my publications page.
Acknowledgements
To generate the visualizations I used the Graphviz toolset.
No comments:
Post a Comment