Serverless Database Scheduling

Обмеження: 10 сек., 1024 МіБ

Modern cloud database platforms support elastic scaling of compute nodes and dynamic request routing. Each customer owns one database instance with one primary node and zero or more secondary nodes. Write queries must be executed on the primary node of the corresponding instance, while read queries can be executed on any node of that instance.

At each second, the platform receives new query requests and may perform scaling and migration operations. Your task is to implement an online scheduler that decides:

• how to scale nodes and servers,

• how to place new nodes,

• and how to dispatch query requests to nodes,

so that the total cost is minimized.

Please note that this is an interactive optimization problem. Your solution communicates with the interactor through standard input and standard output.

Model definition

Time is discrete: \(t = 1, 2, \dots, T\), one step per second.

All CPU values in the input, output, constraints, and formulas are measured in CPU time slices per second.

Queries. There are \(k\) query types. Query type \(q\) is described by \[Q_q = (cpu_q, mem_q, qto_q, type_q),\] where:

• \(cpu_q\) is the required CPU amount in time slices per one execution,

• \(mem_q\) is the required memory in MiB per one execution,

• \(qto_q\) is the maximum tolerable overload time in seconds,

• \(type_q \in \{0, 1\}\): 0 means write, 1 means read.

Customers and instances. There are \(m\) customers. Customer \(u\) is described by \[U_u = (level_u, inst_u, b_u, n_{u,1}, n_{u,2}, \dots, n_{u,b_u}),\] where:

• \(level_u \in \{1,2,\dots,9\}\) is the customer level,

• \(inst_u\) is the instance identifier,

• \(b_u\) is the number of initially purchased nodes,

• \(n_{u,1}\) is the primary node, and \(n_{u,2}, \dots, n_{u,b_u}\) are secondary nodes.

The primary node of an instance cannot be released. It must remain active throughout the whole interaction. Scale-down is not allowed to reduce an instance below \(b_u\) active nodes.

Customer support weights. Let \(L_1, L_2, \dots, L_9\) be positive integers with \[L_1 \le L_2 \le \dots \le L_9.\] If customer \(u\) has level \(level_u\), then its overload weight is \(L_{level_u}\).

Node specification bounds and granularity.

• \(F_{min} = (cpu_{min}, mem_{min})\),

• \(F_{max} = (cpu_{max}, mem_{max})\),

• \(G_e = (g_{cpu}, g_{mem})\).

Each active node must satisfy: \[cpu_{min} \le cpu(node) \le cpu_{max}, \quad mem_{min} \le mem(node) \le mem_{max},\] and all scaling changes must be integer multiples of \(g_{cpu}\) and \(g_{mem}\). All initially purchased nodes start at \(F_{min}\).

Server models. There are \(n\) server models. Model \(s\) is \[M_s = (cpu^{srv}_s, mem^{srv}_s, cost_s),\] where \(cpu^{srv}_s\) is the total CPU capacity (in time slices per second), \(mem^{srv}_s\) is the total memory capacity (in MiB), and \(cost_s\) is the running cost per second. For every active server of model \(s\), the sum of CPU and memory allocated to nodes on that server must not exceed \(cpu^{srv}_s\) and \(mem^{srv}_s\), respectively.

Execution semantics. At each node, requests are executed in a FIFO queue.

• At each second, the node has a fixed CPU budget (in time slices per second) equal to its current CPU specification.

• The request at the head of the queue may start only if full memory \(mem_q\) is currently available.

• If memory is insufficient, the head request waits and makes no progress; requests behind it also wait.

• Once a request starts, its memory is reserved until that request completes.

• While processing the head request, the node spends CPU time slices on it. If the remaining CPU budget of the current second is enough to finish it, the request completes during this second and the node continues with the next request in the same second.

• If the remaining CPU budget is not enough, the request makes partial progress, keeps its remaining required time slices, and continues at the next second from where it stopped.

• A node remains usable while a pending LOCAL_SCALE, CROSS_SCALE, or release-to-\((0,0)\) operation is in progress. Until that operation finishes, the node continues processing requests with its currently active specification; the new specification becomes available only when the operation takes effect.

For a request \(r\), define overload time as \[To_r = finish_r - arrive_r.\] The support penalty of request \(r\) is \[penalty_r = L_{level(r)} \cdot \max(0, To_r - qto_{type(r)}).\]

Allowed operations

At time step \(t\), you may output these operations:

1. NEW_SERVER\((server\_id, model\_id)\)

   Request a new server. It becomes available immediately at time \(t\), and billing starts at time \(t\).

2. DEL_SERVER\((server\_id)\)

   Release an empty server. It takes effect immediately at time \(t\), and billing stops from time \(t\).

3. LOCAL_SCALE\((node\_id, \Delta cpu, \Delta mem)\)

   Change node resources on its current server. The new resources become effective at time \(t + T_{lu}\).

   To release a node, output LOCAL_SCALE\((node\_id, -cpu(node), -mem(node))\). This reduces its specification to \((0,0)\) at time \(t + T_{lu}\), makes it permanently inactive, and frees its server resources.

4. CROSS_SCALE\((node\_id, target\_server\_id, \Delta cpu, \Delta mem)\)

   Migrate a node to another server and adjust resources. The resulting node specification is \[(cpu(node) + \Delta cpu,\; mem(node) + \Delta mem),\] and becomes effective at time \(t + T_{cu}\). During the whole interval from time \(t\) until the migration takes effect, resources for that node are considered occupied on both the source server and the target server.

   If the resulting specification is \((0,0)\), CROSS_SCALE instead releases the node at time \(t + T_{cu}\). The target server must still exist and differ from the source when the operation is issued, but no resources are reserved on it.

5. SCALE_OUT\((instance\_id, target\_node\_id, target\_server\_id, cpu, mem)\)

   Add one new node to the instance and place it on a server with specification \((cpu, mem)\). The created node receives identifier \(target\_node\_id\). Equivalently, this may be viewed as scaling a not-yet-existing node from \((0,0)\) to \((cpu, mem)\). The target server capacity is reserved starting from time \(t\), and the new node becomes available for dispatch and further operations only at time \(t + T_{so}\).

Additional validity rules:

• Before using a server in CROSS_SCALE or SCALE_OUT, that server must already exist.

• A node can be released only when both CPU and memory become 0 simultaneously.

• When a release takes effect, the node’s queue must be empty, with no partially executed request. For an effect time \(e\), all requests on that node must finish by the end of time \(e-1\). You may request a release and dispatch requests while it is pending, provided this condition holds. Otherwise, the release is invalid.

• It is invalid to make only one of CPU or memory equal to 0.

• LOCAL_SCALE\((node\_id, 0, 0)\) is invalid (no-op).

• While a node has a pending LOCAL_SCALE, CROSS_SCALE, SCALE_OUT, or release operation, no other operation may target that node until the pending operation takes effect.

• Primary nodes cannot be released.

• All active nodes must satisfy bounds and granularity constraints.

• Total node allocations on a server must never exceed the server capacity.

• An instance may contain more than its initial \(b_u\) nodes, and any non-primary node, including an initially purchased secondary node, may be released, but after every operation takes effect the instance must still have at least \(b_u\) active nodes. Nodes with a pending SCALE_OUT operation do not count as active.

Optimization objective

Minimize total cost: \[Cost = C_r + C_s.\]

Running cost: \[C_r = \sum_{t=1}^{T} \sum_{v \in ActiveServers(t)} cost_{model(v)}.\]

Support cost: \[C_s = \sum_{r \in AllRequests} L_{level(r)} \cdot \max(0, To_r - qto_{type(r)}).\]

Interaction protocol

First, read static input:

1. Integer \(k\).

2. \(k\) lines: \(query\_id\; cpu\; mem\; qto\; type\).

3. Integer \(m\).

4. \(m\) lines: \(instance\_id\; level\; b\; node_1\; \dots\; node_b\).

5. Integer \(n\).

6. \(n\) lines: \(model\_id\; cpu\; mem\; cost\).

7. One line: \(cpu_{min}\; mem_{min}\).

8. One line: \(cpu_{max}\; mem_{max}\).

9. One line: \(g_{cpu}\; g_{mem}\).

10. One line: \(T_{lu}\; T_{cu}\; T_{so}\).

11. One line: \(L_1\; L_2\; \dots\; L_9\).

12. Integer \(T\).

All identifiers that you choose during the interaction (server IDs in NEW_SERVER and node IDs in SCALE_OUT) must be integers in \([0, 2^{31} - 1]\), pairwise distinct across both kinds, never reused, and different from every node ID given in the input.

Initialization round (\(t = 0\)). You must create initial servers and place all initially purchased nodes.

Output format:

1. Integer \(a_0\) — number of NEW_SERVER actions.

2. \(a_0\) lines: \(server\_id\; model\_id\).

3. Integer \(p_0\) — number of initial placements.

4. \(p_0\) lines: \(node\_id\; server\_id\).

Then flush output and read one integer \(verdict\).

• \(verdict = 0\): continue.

• \(verdict = -1\): your previous output is incorrect. The interactor will return -1; your program must terminate immediately. In this case, the test receives Wrong Answer. If your program does not terminate, it may receive Runtime Error, Time Limit Exceeded, or Wrong Answer.

Regular rounds (\(t = 1,2,\dots,T\)). Delayed operations take effect at the beginning of the round, before arrivals and execution, in the order they were issued. If an effect is invalid, the interactor sends -1 instead of \(r_t\), and your program must terminate immediately.

For each \(t\), interactor sends:

1. Integer \(r_t\) — number of incoming request groups at time \(t\).

2. \(r_t\) lines: \(instance\_id\; query\_id\; qps\).

You then output one decision block for time \(t\).

First line of the block: \[cnt_{new}\; cnt_{del}\; cnt_{local}\; cnt_{cross}\; cnt_{out}.\]

Then output actions in fixed order:

1. \(cnt_{new}\) lines: NEW_SERVER as \(server\_id\; model\_id\).

2. \(cnt_{del}\) lines: DEL_SERVER as \(server\_id\).

3. \(cnt_{local}\) lines: LOCAL_SCALE as \(node\_id\; \Delta cpu\; \Delta mem\).

4. \(cnt_{cross}\) lines: CROSS_SCALE as \(node\_id\; target\_server\_id\; \Delta cpu\; \Delta mem\).

5. \(cnt_{out}\) lines: SCALE_OUT as \(instance\_id\; target\_node\_id\; target\_server\_id\; cpu\; mem\), where the last two values are the exact CPU and memory of the new node.

After operation lines:

1. Output integer \(d_t\) — number of dispatch records at time \(t\).

2. Output \(d_t\) lines: \(instance\_id\; query\_id\; node\_id\; amount\).

Dispatch rules:

• Write queries can be dispatched only to the primary node of the instance.

• Read queries can be dispatched to any node of the instance.

• For each pair \((instance\_id, query\_id)\), dispatch order must preserve arrival order across timestamps.

• Middleware buffering is allowed: when requests arrive at time \(t\), you may dispatch all, some, or none of them at time \(t\).

• Any undisbursed part of requests stays in the middleware buffer and is carried to later time steps.

• For each pair \((instance\_id, query\_id)\), the buffer behaves as FIFO across time: units that arrived earlier must be dispatched earlier.

• You may interleave dispatches of different query types and different instances arbitrarily, as long as each individual \((instance\_id, query\_id)\) FIFO order is preserved.

• By the end of the interaction, every arrived request unit must be fully dispatched and executed.

Then flush output and read one integer \(verdict\).

• \(verdict = 0\): continue to next time step.

• \(verdict = -1\): your previous output is incorrect. The interactor will return -1; your program must terminate immediately. In this case, the test receives Wrong Answer. If your program does not terminate, it may receive Runtime Error, Time Limit Exceeded, or Wrong Answer.

After the response for time \(T\), interaction is over and your program must terminate.

Input constraints

\(1 \le k \le 100\),

\(1 \le m \le 10\),

\(1 \le n \le 5\),

\(3600 \le T \le 86400\),

\(10 \le cpu_q \le 10^8\),

\(1 \le mem_q \le 10^5\),

\(0 \le qto_q \le 3600\),

\(type_q \in \{0,1\}\),

\(320000 \le cpu^{srv}_s \le 1180000\),

\(64000 \le mem^{srv}_s \le 1024000\),

\(10 \le cost_s \le 1000\),

\(100 \le cpu_{min}, mem_{min} \le cpu_{max}, mem_{max}\),

\(100 \le g_{cpu}, g_{mem} \le 5000\),

\(1 \le T_{lu}, T_{cu}, T_{so} \le 100\),

\(1 \le L_1 \le L_2 \le \dots \le L_9 \le 100\),

\(1 \le qps \le 10000\).

Output constraints

All identifiers used in actions must be valid and consistent. All resource operations must preserve feasibility at all times, including delayed effect times. If any operation or dispatch line is invalid, the interactor returns -1.

Scoring

If your solution outputs an invalid action, violates the interaction/output constraints, or leaves at least one arrived request unit not fully executed by the end of the simulation, then the score for this test case is 0.

Otherwise, define your total cost as \[Cost = C_r + C_s.\]

Let \(req_{t,u,q}\) be the number of request units that arrive at time \(t\) for instance \(u\) and query type \(q\). Define total required CPU work: \[W = \sum_{t=1}^{T}\sum_{u=1}^{m}\sum_{q=1}^{k} req_{t,u,q} \cdot cpu_q.\]

Define the best server price per CPU time slice: \[BP = \min_{1 \le s \le n} \frac{cost_s}{cpu^{srv}_s}.\]

Define the reference cost \[Cost^* = W \cdot BP.\]

Then your score for this test case is \[score = \left\lfloor \frac{Cost^*}{Cost} \cdot 10^7 \right\rfloor.\]

Larger score corresponds to a better solution.

Your overall contest score is the sum of test case scores.

Submissions

• The execution time limit is 10 seconds per test case and the memory limit is 1024 mebibytes.

• The code size limit is 64 kibibytes.

• The compilation time limit is 1 minute.

• You can submit your code no more than once every 10 minutes, and you will get feedback with your score for each of the provisional tests.

• Submission feedback is provided on a provisional test set.

• Final ranking is computed on a separate hidden test set.

Quick start

A simple baseline strategy:

• initialize each purchased node on a separate server,

• set each initialized node to the maximal specification \(F_{max}\),

• dispatch all requests (both write and read) to the primary node of the corresponding instance,

• after initialization, do not perform additional scaling or migration operations.

Check the sample solution source code:

• C++

• Python

• C#

Local testing

You have access to the generator, checker, and scorer, as well as a tool for local testing of your solution. All of them are implemented using Algotester Library and Algotester Generator Library. You can download the source codes of both libraries using the following links: algotester.h, algotester_generator.h. Both files should be placed into the same directory as the problem source codes.

Please note that the generator, checker, and scorer provided to you are actually used to score your solutions on the Algotester website. You can use the source codes to clarify any questions that you have about the test cases, scoring, or the interaction protocol. All test cases, including provisional and final sets, are generated by the generator.

You can use the generator to create tests for local testing by using a few simple steps:

1. Save the generator source code to a file named generator.cpp

2. Compile the source code:

   g++ generator.cpp -O2 -o generator

3. Generate a test case

   ./generator <seed>

   This will print a test case for a specific seed to standard output.

The purpose of the checker in this problem is to read the test input data and interact with your solution: provide it with test data and read your solution’s output. The checker also checks your solution for validity: it will print an error message to stdout if your solution is incorrect on a given test case. If the stdout of the checker is empty, this means that your solution is correct on the current test case.

The scorer reads the test case input data as well as an interaction log created by the checker and scores your solution. Please note that the scorer assumes that the solution provided correct outputs for the test case, i.e. the checker did not print anything into stdout.

The tool for local testing automates the process of managing the solution, checker, scorer, and generator. In order to use the local testing tool, follow these steps:

1. Save the interactor source code to a file named interactor.py.

2. Save the checker source code to a file named checker.cpp.

3. Save the scorer source code to a file named scorer.cpp.

4. Save the generator source code to a file named generator.cpp.

5. Compile the checker, scorer, and generator source codes:

   g++ checker.cpp -O2 -o checker
   g++ scorer.cpp -O2 -o scorer
   g++ generator.cpp -O2 -o generator

6. Prepare your solution for execution (compile the code for compiled languages (C++, Java, C#); do nothing for interpreted languages (Python, Node)).

7. Write down the command for the solution execution (for example: C++: ./solution, Python: python solution.py, Java: java solution.class).

8. Pass the command and the path to the input file to the interactor. Use the --help command to find out what the tool can do.

   python interactor.py --solution "./solution" --test_file "in.txt"
   python interactor.py --solution "python solution.py" --test_file "in.txt" --seed 47
   python interactor.py --help

9. The interactor will generate the test (in case that seed is specified), launch your solution with the checker, and then if the checker finds no errors in your solution, launch the scorer to calculate your score for the test. The interactor prints a detailed log of the process to stdout.