99
edits
Changes
no edit summary
This page describes how guarantees for resources can be implemented.
= How to guarantee a guarantee =
It's not obvious at the first glance, but ''there are only two ways how a guarantee can be provided'':
# reserving desired amount in advance
# limiting consumers to keep some amount free
The first way has the followong disadvantages:
; reserving is impossible for certain resources
: such resources as CPU time, disk or network bandwidth and similar can not be just reserved as theirs amount instatntly increases;
; reserving is essentially a limit, but much more strict
: cutting off X megabytes from RAM implies that all the rest groups are limited in theis RAM consumption;
; reserving reduces containers density on the node
: if one wants to run some identical containers each requiring 100Mb on 1Gb system reservations can be done for 10 only and starting the 11th becomes impossible.
On the other hand ''limiting'' of containers can provide guarantees for them as well.
= Providing a guarantee through limiting =
The idea of getting a guarantee is simple:
{{out|if any group <math>g_i</math> requires a <math>G_i</math> units of resource from <math>R</math> units available then limiting all the rest groups with <math>R - G_i</math> units provides a desired guarantee}}
For <math>N</math> groups in the system this implies solving a linear equation set to get limits <math>L_i</math> like this:
<center><math>
\begin{cases}
L_2 + L_3 + \ldots + L_N = R - G_1 \\
L_1 + L_3 + \ldots + L_N = R - G_2 \\
\ldots \\
L_1 + L_2 + \ldots + L_{N-1} = R - G_N \\
\end{cases}
</math></center>
In a matrix form this looks like
<center><math>
A L = G
</math></center>
where
<center><math>
A = \begin{bmatrix}
0 & 1 & 1 & \cdots & 1 & 1 \\
1 & 0 & 1 & \cdots & 1 & 1 \\
& & \cdots \\
1 & 1 & 1 & \cdots & 1 & 0 \\
\end{bmatrix}
,
L = \begin{bmatrix} L_1 \\ L_2 \\ \vdots \\ L_N \end{bmatrix}
,
G = \begin{bmatrix} R - G_1 \\ R - G_2 \\ \vdots \\ R - G_N \end{bmatrix}
</math></center>
and thus the solution is
<center><math>
L = A^{-1}G
</math></center>
Skipping boring calculations, the reverse matrix <math>A^{-1}</math> is
<center><math>
A^{-1} = \frac {1} {N - 1} \left( A - (N - 2) E \right)
</math></center>
This solutions looks huge, but the <math>L</math> vector is calculated in <math>O(N)</math> time:
<pre>
void calculate_limits(int N, int *g, int *l)
{
int sum;
sum = 0;
for (i = 0; i < N; i++)
sum += g[i];
for (i = 0; i < N; i++)
l[i] = sum - (R - g[i]) - (N - 2) * (R - g[i]);
}
</pre>
= How to guarantee a guarantee =
It's not obvious at the first glance, but ''there are only two ways how a guarantee can be provided'':
# reserving desired amount in advance
# limiting consumers to keep some amount free
The first way has the followong disadvantages:
; reserving is impossible for certain resources
: such resources as CPU time, disk or network bandwidth and similar can not be just reserved as theirs amount instatntly increases;
; reserving is essentially a limit, but much more strict
: cutting off X megabytes from RAM implies that all the rest groups are limited in theis RAM consumption;
; reserving reduces containers density on the node
: if one wants to run some identical containers each requiring 100Mb on 1Gb system reservations can be done for 10 only and starting the 11th becomes impossible.
On the other hand ''limiting'' of containers can provide guarantees for them as well.
= Providing a guarantee through limiting =
The idea of getting a guarantee is simple:
{{out|if any group <math>g_i</math> requires a <math>G_i</math> units of resource from <math>R</math> units available then limiting all the rest groups with <math>R - G_i</math> units provides a desired guarantee}}
For <math>N</math> groups in the system this implies solving a linear equation set to get limits <math>L_i</math> like this:
<center><math>
\begin{cases}
L_2 + L_3 + \ldots + L_N = R - G_1 \\
L_1 + L_3 + \ldots + L_N = R - G_2 \\
\ldots \\
L_1 + L_2 + \ldots + L_{N-1} = R - G_N \\
\end{cases}
</math></center>
In a matrix form this looks like
<center><math>
A L = G
</math></center>
where
<center><math>
A = \begin{bmatrix}
0 & 1 & 1 & \cdots & 1 & 1 \\
1 & 0 & 1 & \cdots & 1 & 1 \\
& & \cdots \\
1 & 1 & 1 & \cdots & 1 & 0 \\
\end{bmatrix}
,
L = \begin{bmatrix} L_1 \\ L_2 \\ \vdots \\ L_N \end{bmatrix}
,
G = \begin{bmatrix} R - G_1 \\ R - G_2 \\ \vdots \\ R - G_N \end{bmatrix}
</math></center>
and thus the solution is
<center><math>
L = A^{-1}G
</math></center>
Skipping boring calculations, the reverse matrix <math>A^{-1}</math> is
<center><math>
A^{-1} = \frac {1} {N - 1} \left( A - (N - 2) E \right)
</math></center>
This solutions looks huge, but the <math>L</math> vector is calculated in <math>O(N)</math> time:
<pre>
void calculate_limits(int N, int *g, int *l)
{
int sum;
sum = 0;
for (i = 0; i < N; i++)
sum += g[i];
for (i = 0; i < N; i++)
l[i] = sum - (R - g[i]) - (N - 2) * (R - g[i]);
}
</pre>
