Containers/Guarantees for resources

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 of how a guarantee can be provided:

1. reserve desired amount in advance
2. limit consumers to keep some amount free

The first way has the followong disadvantages:

Reservation is impossible for certain resources

such as CPU time, disk or network bandwidth and similar can not be just reserved as their amount instantly increases;

Reserved amount is essentially a limit, but much more strict

cutting off X megabytes from RAM implies that all the rest groups are limited in their RAM consumption;

Reservation reduces containers density

if one wants to run some identical containers, each requiring 100Mb on 1Gb system, reservations can be done for only 10 containers, and starting the 11th is 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:

if any group $g_{i}$ requires a Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G_i} units of resource from Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} units available then limiting all the rest groups with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R - G_i} units provides a desired guarantee

For Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} groups in the system this implies solving a linear equation set to get limits Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_i} like this:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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} }

In a matrix form this looks like

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A L = G }

where

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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} }

and thus the solution is

$L=A^{-1}G$

Skipping boring calculations, the reverse matrix $A^{-1}$ is

$A^{-1}={\frac {1}{N-1}}\left(A-(N-2)E\right)$

This solutions looks huge, but the $L$ vector is calculated in $O(N)$ time:

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]);
}