Buffer Sharing in Multi-tenant Database Environment solution
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.Buffer Sharing in Multi-tenant Database Environment solution 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. Buffer Sharing in Multi-tenant Database Environment solutionThis 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 ofoperations: where is a given integer. Each access in the sequence is called an operation. In multi-tenant environment, operations may come from different tenants. Therefore, an operation consists of a tenant ID (subject) and a page (object) . The tenants are numbered by integers from to a given integer . Pages for different tenants are local to these tenants. In other words, page of tenant is not relevant to page of tenant .
The core of buffer sharing is the replacement algorithm (also called the cache eviction algorithm). For an operation sequence, if the requested page 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 in the buffer, evict it and then store the new page in its slot. Typical cache eviction algorithms include Least Recently Used (LRU), Least Frequently Used (LFU), and Segmented LRU (SLRU).Buffer Sharing in Multi-tenant Database Environment solution
In single-tenant environment, each tenantindependently uses a memory block of a fixed size . While in multi-tenant environment, all tenants share a large memory space with total size . 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, . Specifically, when tenant has or less pages in memory, the pages of other tenants cannot replace pages of tenant . Conversely, when tenant has or more pages in memory, the pages of tenant cannot replace pages of other tenants. Note that, when tenant has or 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, output a buffer location that is either the existing or the newly assigned caching location for page of tenant .
Input Buffer Sharing in Multi-tenant Database Environment solution
The first line contains three integers, , and . They respectively represent the number of tenants in the system ( ), the total buffer size ( ), and the length of the operation sequence ( ).
The second line containsintegers , where represents the priority level of tenant ( ).
The third line containsintegers , where represents the database size of tenant ( ).
The fourth line containsintegers, which are triplets . They respectively represent the minimum buffer size, the base buffer size, and the maximum buffer size of tenant ( ). The values are used to calculate the score ( ). It is guaranteed that is less than or equal to .
Interaction Buffer Sharing in Multi-tenant Database Environment solution
The scheduling algorithm must be real-time. It means the solution must print the answer to -th operation before it gets the line with -th operation.
So, after your program reads the initial part of the input, it needs to interact with the judgertimes. 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 of the operation sequence ( , ). For each of the operations , print a line containing a single integer : the buffer location accessed by that operation ( ).
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.
There aretests in this problem.
For each of them, the online judge checks whether a page fault occurs in each operationbased on the sequence provided by the contestant. To ensure that the experiences of tenants with different database sizes are balanced, the concept of is introduced. Here, SLA stands for Service Level Agreement which is the quality of service expected by the tenants. For tenant , the can be expressed as follows:
The valueindicates the actual number of page faults for tenant in this test based on the contestant’s replacement algorithm. The value indicates the number of page faults obtained by using the LRU algorithm when the buffer size of tenant is . It is guaranteed that is a positive integer.
The contestant’s intermediate scorein test can be expressed as follows:
andis expressed as follows:
The total score of a contestant can be expressed as follows:
andis expressed as follows:
In order to balance the players’ results on different test data, we calculateof each data set in advance, and then score the contestant’s cost according to and get the . We have implemented several baseline algorithms and, among them, calculated the minimum non-zero value for each test .
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.Buffer Sharing in Multi-tenant Database Environment solution
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.
input Buffer Sharing in Multi-tenant Database Environment solution
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