[Solution] Buffer Sharing in Multi-tenant Database Environment solution codeforces

Buffer Sharing in Multi-tenant Database Environment solution codeforces

A database is a warehouse where data is organized, stored, and managed by its underlying data structures. Everyone uses some kind of a database.

Some cloud service providers decide to build single instances of database management systems which are shared by multiple customers and isolated among different users. This is the concept of database multi-tenancy. A single database instance is divided into multiple virtual sub-databases, serving different tenants. With the database multi-tenant technology, cloud service providers can efficiently integrate resources and greatly reduce service costs.

To speed up data access, data is split into pages, and some pages are loaded from slow storage, like a hard disk, into a faster memory buffer. This is the concept of a database buffer. When the amount of data in the buffer reaches the capacity, some data pages get evicted by the replacement algorithm so that new ones can be loaded from the disk. This challenge is to implement sharing and isolation mechanisms for database buffers in a multi-tenant environment.

The database can be abstracted as a set of pages with a fixed length, where a page is defined as the basic unit for reading data into the buffer. The access to the database is abstracted as a sequence of MM operations: S=A1,A2,,AMS=A1,A2,…,AM where MM is a given integer. Each access AiAi in the sequence is called an operation. In multi-tenant environment, operations may come from different tenants. Therefore, an operation AiAi consists of a tenant ID (subject) UiUi and a page (object) PiPi. The tenants are numbered by integers from 11 to a given integer NN. Pages for different tenants are local to these tenants. In other words, page 11 of tenant xx is not relevant to page 11 of tenant yy.

The core of buffer sharing is the replacement algorithm (also called the cache eviction algorithm). For an operation sequence SS, if the requested page PiPi already exists in the buffer, it is called a page hit. Otherwise, it is called a page fault. When a page fault occurs, the cache eviction algorithm is used to select a memory page CC in the buffer, evict it and then store the new page PiPi in its slot. Typical cache eviction algorithms include Least Recently Used (LRU), Least Frequently Used (LFU), and Segmented LRU (SLRU).

In single-tenant environment, each tenant tt independently uses a memory block of a fixed size QtQt. While in multi-tenant environment, all tenants share a large memory space with total size QQ. The memory size used by each tenant is dynamically adjusted to perform page swap-in and swap-out. During a cache eviction, please ensure that the memory size being used by each tenant is within the specified range, that is, QmintQtQmaxtQtmin≤Qt≤Qtmax. Specifically, when tenant xx has QminxQxmin or less pages in memory, the pages of other tenants cannot replace pages of tenant xx. Conversely, when tenant yy has QmaxyQymax or more pages in memory, the pages of tenant yy cannot replace pages of other tenants. Note that, when tenant zz has QminzQzmin or QmaxzQzmax pages in memory, the algorithm can evict an existing page of that tenant and replace it with a new one. Contestants need to maximize the overall tenants’ access experience with limited memory space.

Design a replacement algorithm that is applicable to a multi-tenant environment. For each operation AiAi, output a buffer location CiCi that is either the existing or the newly assigned caching location for page PiPi of tenant UiUi.

Input Buffer Sharing in Multi-tenant Database Environment solution codeforces

The first line contains three integers NNQQ, and MM. They respectively represent the number of tenants in the system (1N101≤N≤10), the total buffer size (1Q10000001≤Q≤1000000), and the length of the operation sequence SS (1M10000001≤M≤1000000).

The second line contains NN integers L1,L2,,LNL1,L2,…,LN, where LtLt represents the priority level of tenant tt (1Lt101≤Lt≤10).

The third line contains NN integers D1,D2,,DND1,D2,…,DN, where DtDt represents the database size of tenant tt (1Dt1000001≤Dt≤100000).

The fourth line contains 3N3⋅N integers, which are NN triplets (Qmint,Qbaset,Qmaxt)(Qtmin,Qtbase,Qtmax). They respectively represent the minimum buffer size, the base buffer size, and the maximum buffer size of tenant tt (1QmintQmaxt1000001≤Qtmin≤Qtmax≤100000). The values QbasetQtbase are used to calculate the score (1Qbaset1000001≤Qtbase≤100000). It is guaranteed that Nj=0Qminj∑j=0NQjmin is less than or equal to QQ.

Interaction Buffer Sharing in Multi-tenant Database Environment solution codeforces

The scheduling algorithm must be real-time. It means the solution must print the answer to ii-th operation before it gets the line with (i+1)(i+1)-th operation.

So, after your program reads the initial part of the input, it needs to interact with the judger MM times. For each interaction, the judger will provide a single line as an input for your program. This line contains two integers which represent the pair Ai=(Ui,Pi)Ai=(Ui,Pi) of the operation sequence (1UiN1≤Ui≤N1PiDUi1≤Pi≤DUi). For each of the MM operations AiAi, print a line containing a single integer CiCi: the buffer location accessed by that operation (1CiQ1≤Ci≤Q).

For correct interaction, print the end-of-line after each command and flush the output buffer with the respective functions of your programming language:

  • cout.flush() or fflush(stdout) for C/C++;
  • stdout.flush() for Python;
  • System.out.flush() in Java;
  • see documentation for other languages.

Otherwise, your solution will get the “Idleness Limit Exceeded” outcome.

 

Scoring Buffer Sharing in Multi-tenant Database Environment solution codeforces

There are TT tests in this problem.

For each of them, the online judge checks whether a page fault occurs in each operation AiAi based on the sequence CiCi provided by the contestant. To ensure that the experiences of tenants with different database sizes are balanced, the concept of SLArateSLArate is introduced. Here, SLA stands for Service Level Agreement which is the quality of service expected by the tenants. For tenant tt, the SLAratetSLAtrate can be expressed as follows:

SLAratet=max(SLAactualt,SLAbaset)SLAbasetSLAbasetSLAtrate=max(SLAtactual,SLAtbase)−SLAtbaseSLAtbase

The value SLAactualtSLAtactual indicates the actual number of page faults for tenant ii in this test based on the contestant’s replacement algorithm. The value SLAbasetSLAtbase indicates the number of page faults obtained by using the LRU algorithm when the buffer size of tenant tt is QbasetQtbase. It is guaranteed that SLAbasetSLAtbase is a positive integer.

The contestant’s intermediate score CostjCostj in test jj can be expressed as follows:

Costj=i=1Nf1(SLAratei)LiCostj=∑i=1Nf1(SLAirate)⋅Li

and f1f1 is expressed as follows:

f1(x)=3x2f1(x)=3×2

The total score of a contestant can be expressed as follows:

Score=j=1Tf2(CostjCostbasej)Score=∑j=1Tf2(CostjCostjbase)

and f2f2 is expressed as follows:

f2(x)=100max(0,5x)f2(x)=100⋅max(0,5−x)

In order to balance the players’ results on different test data, we calculate CostbaseCostbase of each data set in advance, and then score the contestant’s cost according to CostbaseCostbase and get the ScoreScore. We have implemented several baseline algorithms and, among them, calculated the minimum non-zero value CostbaseCostbase for each test jj.

There are two sets of tests in this problem. For the duration of the competition, each submission is tested on the preliminary set of tests. When the competition is finished, for each contestant:

  • the jury takes the latest submission with non-zero score on preliminary tests;
  • this submission is tested on the final set of tests;
  • the score on final tests is the final score for the contestant.

The contestants are then ranked according to their final score.

The final tests are similar, but not identical, to the preliminary tests. The number of final tests may be larger, but their distribution is similar to the distribution of preliminary tests.

 

Example

input Buffer Sharing in Multi-tenant Database Environment solution codeforces

Copy

2 10 10
3 5
10 10
1 5 10 1 5 10
1 1
2 1
1 2
2 2
1 3
2 3
1 4
2 4
1 5
2 5
output

Copy

1 6 2 7 3 8 4 9 5 10

Buffer Sharing in Multi-tenant Database Environment solution codeforces

Leave a Comment