CN115130032B - Deletion rate curve construction method and system in heterogeneous granularity storage system - Google Patents

Abstract

The invention discloses a method for constructing a deletion rate curve in a heterogeneous granularity storage system, which comprises the following steps: receiving an access request sequence, setting a counter i=1, judging whether i is equal to the total number of access requests in the access request sequence, loading an ith access request in the access request sequence into a cache filter if the i is not equal to the total number of the access requests in the access request sequence, judging whether an access object corresponding to the ith access request hits in the cache filter, acquiring the sampling rate of the access object according to the size of the access object corresponding to the ith access request if the i is not equal to the total number of the access requests in the access request sequence, sampling the access object according to the acquired sampling rate of the access object corresponding to the ith access request, calculating the reuse distance of the access object, and setting the counter i=i+1. The invention can solve the technical problem of inaccurate construction of the byte deletion rate curve and the object deletion rate curve caused by the content popularity difference and the object size difference in the existing heterogeneous granularity storage system.

Description

A method and system for constructing a missing rate curve in a heterogeneous granularity storage system

Technical Field

The present invention belongs to the field of computer data storage, and more specifically, relates to a method and system for constructing a missing rate curve in a heterogeneous granularity storage system.

Background technique

Object-level caching is a very common caching technology in the network. Its main evaluation indicators are byte missing rate (BMR) and object missing rate (OMR). In network caching, the byte missing rate can directly reflect the bandwidth overhead and traffic overhead of the cache provider, so its application is very important. Better caching strategies can achieve lower miss rates for a given cache size, and better cache resource management can improve the overall performance of all applications sharing the cache. Miss rate curve (MRC) is a quantitative cache performance modeling technology, and its construction method plays a vital role in cache resource management.

The construction method of MRC has been widely studied in the past, and its construction methods mainly include: accurate MRC construction method, approximate MRC construction method, MRC construction method based on spatial hash sampling, etc. The accurate MRC construction method can obtain more accurate construction results by calculating the reuse distance of each object; the approximate MRC construction uses approximate and equivalent processing methods to reduce the computational overhead and the error is within the tolerable range; the MRC construction method based on spatial hash sampling can realize MRC construction in heterogeneous granularity storage systems with lower computational overhead through hash sampling technology.

However, there are some problems with the existing MRC construction methods in the application of heterogeneous granularity storage systems: First, if the accurate construction of MRC is to be achieved, it is inevitably accompanied by extremely high time and space complexity, resulting in a large computational overhead; Second, in the cache of heterogeneous granularity storage systems (such as object storage), the difference in object size will lead to MRC construction errors, and there will be a large construction error between the Byte missing rate curve (BMRC) and the Object missing rate curve (OMRC); Third, the different content popularity of different objects (i.e., request probability) will lead to inaccurate front-end MRC construction, thereby affecting the overall accuracy of MRC.

Summary of the invention

In response to the above defects or improvement needs of the prior art, the present invention provides a method for constructing a miss rate curve in a heterogeneous granularity storage system, with the aim of solving the technical problems that the existing MRC construction method is inevitably accompanied by extremely high time and space complexity during the accurate construction of MRC, resulting in a large computational overhead, as well as the technical problems that in the cache of a heterogeneous granularity storage system (such as object storage), the difference in object size will cause MRC construction errors, and there is a large construction error between BMRC and OMRC, and the different content popularity of different objects will lead to inaccurate front-end MRC construction, thereby affecting the overall accuracy of MRC.

To achieve the above object, according to one aspect of the present invention, a sampling method for constructing a missing rate curve is provided, comprising the following steps:

(1) Receive access request sequence and set counter i=1;

(2) Determine whether i is equal to the total number of access requests in the access request sequence. If so, proceed to step (8); otherwise, proceed to step (3);

(3) Load the i-th access request in the access request sequence into the cache filter, and determine whether the access object corresponding to the i-th access request hits in the cache filter. If so, proceed to step (4); otherwise, proceed to step (5);

(4) Obtain the reuse distance of the access object corresponding to the i-th access request, and then proceed to step (7);

(5) obtaining a sampling rate of the access object according to the size of the access object corresponding to the i-th access request;

(6) sampling the access object according to the sampling rate of the access object corresponding to the i-th access request obtained in step (5), calculating the reuse distance of the access object, and then proceeding to step (7);

(7) Set counter i=i+1 and return to step (2);

(8) Construct the first histogram based on the reuse distances of all access objects in the access request queue that hit the cache filter, and then proceed to step (9).

(9) constructing a second histogram according to the reuse distances of all access objects in the access request queue that are not hit in the cache filter, and then proceeding to step (10);

(10) The first histogram and the second histogram are combined to construct a complete reuse distance histogram, and the reuse distance histogram is integrated to obtain the final missing rate curve.

Preferably, step (1) is to obtain the actual running access request sequence from the cache system.

Preferably, each access request corresponds to only one access object, and one access object corresponds to at least one access request.

Preferably, the cache filter only retains the most recently accessed objects whose size is not greater than L, where L ranges from 0 to 5×1/r×log ₂ (1/r), preferably 1/r×log ₂ (1/r), where r is a preset basic sampling rate.

Preferably, the reuse distance of the access object i is the sum of the sizes of all other access objects except the access object i within the interval from the last access of the access object i;

The sampling rate r _D of the access object D is calculated according to the following formula:

r _D ＝r×s _D /s _avg

Where s _D is the size of the access object, s _avg is the average value of the access objects corresponding to all access requests in the access request sequence;

Preferably, step (6) comprises the following sub-steps:

(6-1) Sampling the access object corresponding to the i-th access request according to the sampling rate r _D of the access object corresponding to the i-th access request calculated in step (5) to generate a random number between 0 and 1, and determining whether the random number is less than or equal to r _D . If so, proceed to step (6-2); otherwise, the process ends.

(6-2) Construct a binary tree T _ws , so that the in-order traversal of the binary tree T _ws is equivalent to the order of access objects corresponding to the i-th access request obtained in step (5);

(6-3) Calculate the reuse distance sBRD of the access object corresponding to the i-th access request based on the binary tree T _ws obtained in step (6-2);

(6-4) Use the reuse distance of the access object corresponding to the i-th access request obtained in step (6-3) and obtain the final reuse distance eBRD of the access object corresponding to the i-th access request according to the formula eBRD=sBRD/r+size(T _CF ), where size(T _CF ) is the total size of all access objects stored in the cache filter.

Preferably, in the first histogram, the abscissa 1 represents the reuse distance, and the corresponding ordinate is the total number of access objects with a reuse distance of 1.

In the second histogram, the horizontal axis 1 represents the reuse distance, and the corresponding vertical axis is the total number of access objects with a reuse distance of 1.

According to another aspect of the present invention, a system for constructing a miss rate curve in a heterogeneous granularity storage system is provided, comprising:

The first module is used to receive an access request sequence and set a counter i=1;

The second module is used to determine whether i is equal to the total number of access requests in the access request sequence, if yes, then enter the eighth module, otherwise, then transfer to the third module;

The third module is used to load the i-th access request in the access request sequence into the cache filter, and determine whether the access object corresponding to the i-th access request hits in the cache filter, if yes, transfer to the fourth module, otherwise transfer to the fifth module;

The fourth module is used to obtain the reuse distance of the access object corresponding to the i-th access request, and then transfer to the seventh module;

A fifth module is used to obtain a sampling rate of the access object according to the size of the access object corresponding to the i-th access request;

The sixth module is used to sample the access object corresponding to the i-th access request according to the sampling rate of the access object obtained in the fifth module, calculate the reuse distance of the access object, and then transfer to the seventh module;

The seventh module is used to set the counter i=i+1 and return to the second module;

The eighth module is used to construct a first histogram according to the reuse distances of all access objects in the access request queue that hit the cache filter, and then transfer to the ninth module.

The ninth module is used to construct a second histogram according to the reuse distances of all access objects in the access request queue that are not hit in the cache filter, and then transfer to the tenth module;

The tenth module is used to merge the first histogram and the second histogram to construct a complete reuse distance histogram, and integrate the reuse distance histogram to obtain a final missing rate curve.

In general, the above technical solutions conceived by the present invention can achieve the following beneficial effects compared with the prior art:

1. Since the present invention adopts step (5) to step (6) and applies a sampling calculation method, it can reduce the time and space complexity, thereby reducing the calculation overhead of MRC curve construction; in addition, since step (3) to step (6) are adopted, the construction problems of the head and tail of the missing rate curve are considered separately, which reduces the overhead while ensuring that the accuracy meets the requirements.

2. Since the present invention adopts steps (5) to (6) and adopts different sampling rates for objects of different sizes to perform variable weight sampling processing, it can avoid the problem of inaccurate construction of the miss rate curve caused by the difference in object size, reduce the construction error between BMRC and OMRC, and greatly improve the accuracy of cache miss rate curve construction.

3. Since the present invention adopts step (3) to step (4), the reuse distance of objects with high content popularity is calculated separately, and the construction problems of the head and tail of the missing rate curve are considered separately, which improves the statistical accuracy of the reuse distance of objects with high content popularity and greatly improves the head construction accuracy of the MRC curve.

4. As a universal tool, the present invention can be easily and flexibly migrated and applied in other application scenarios such as content distribution networks and web page caches, and can help cache systems achieve more flexible and efficient multi-objective cache optimization.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a flow chart of a method for constructing a miss rate curve in a heterogeneous granularity storage system according to the present invention. In all drawings, the same reference numerals are used to represent the same elements or structures.

Detailed ways

In order to make the purpose, technical solutions and advantages of the present invention more clearly understood, the present invention is further described in detail below in conjunction with the accompanying drawings and embodiments. It should be understood that the specific embodiments described herein are only used to explain the present invention and are not intended to limit the present invention. In addition, the technical features involved in the various embodiments of the present invention described below can be combined with each other as long as they do not conflict with each other.

As shown in Figure 1, the present invention provides a method for constructing a miss rate curve in a heterogeneous granularity storage system, which mainly includes two parts: a cache filter and a variable weight sampling stage. The two parts are respectively used to construct the head and tail of the miss rate curve to improve the construction accuracy of the miss rate curve.

Specifically, the method for constructing a missing rate curve in a heterogeneous granularity storage system of the present invention comprises the following steps:

(1) Receive access request sequence and set counter i=1;

Specifically, this step is to obtain the actual running access request sequence record from the cache system.

(2) Determine whether i is equal to the total number of access requests in the access request sequence. If so, proceed to step (8); otherwise, proceed to step (3);

(3) Load the i-th access request in the access request sequence into the cache filter, and determine whether the access object corresponding to the i-th access request hits in the cache filter. If so, proceed to step (4); otherwise, proceed to step (5);

Specifically, each access request corresponds to only one access object, and one access object can correspond to multiple access requests.

The cache filter uses a binary tree T _CF to construct an access request sequence, so that the in-order traversal of the binary tree is equivalent to the order of accessing objects in the access request sequence, so as to quickly calculate the reuse distance of the access objects corresponding to the access request sequence. In addition, only the most recent access objects whose size is not greater than L are retained in the cache filter, where the value range of L is 0 to 5×1/r×log ₂ (1/r), preferably 1/r×log ₂ (1/r), where r is a preset basic sampling rate, which can be arbitrarily selected between 0 and 1, and is the same as the basic sampling rate in step (5).

(4) Obtain the reuse distance of the access object corresponding to the i-th access request, and then proceed to step (7);

Specifically, the reuse distance of access object i is the sum of the sizes of all other access objects except the access object i within the interval from the last access to the access object i.

The advantage of the above steps (3) to (4) is that the reuse distance is calculated separately for objects with high content popularity, and an accurate reuse distance histogram is subsequently constructed for them, which can improve the accuracy of the missing rate curve at the head, thereby improving the accuracy of the missing rate curve as a whole.

(5) obtaining a sampling rate of the access object according to the size of the access object corresponding to the i-th access request;

Specifically, the sampling rate r _D of the access object D is calculated according to the following formula:

r _D ＝r×s _D /s _avg

Where s _D is the size of the access object, s _avg is the average value of the access objects corresponding to all access requests in the access request sequence;

(6) sampling the access object according to the sampling rate of the access object corresponding to the i-th access request obtained in step (5), calculating the reuse distance of the access object, and then proceeding to step (7);

Specifically, the calculation strategy of reuse distance is:

(6-1) Sampling the access object corresponding to the i-th access request according to the sampling rate r _D of the access object corresponding to the i-th access request calculated in step (5) to generate a random number between 0 and 1, and determining whether the random number is less than or equal to r _D . If so, proceed to step (6-2); otherwise, the process ends.

(6-2) Construct a binary tree T _ws , so that the in-order traversal of the binary tree T _ws is equivalent to the order of access objects corresponding to the i-th access request obtained in step (5);

(6-3) Calculate the reuse distance sBRD of the access object corresponding to the i-th access request based on the binary tree T _ws obtained in step (6-2);

Specifically, the calculation method in this step is exactly the same as that in step (4), and will not be repeated here.

(6-4) Use the reuse distance of the access object corresponding to the i-th access request obtained in step (6-3) and obtain the final reuse distance eBRD of the access object corresponding to the i-th access request according to the formula eBRD=sBRD/r+size(T _CF ), where size(T _CF ) is the total size of all access objects stored in the cache filter.

The advantage of the above steps (6-1) to (6-4) is that different sampling rates are used for objects of different sizes, which reduces the variance of random sampling, further reduces the error at the tail of the missing rate curve, and reduces the impact of object size differences on MRC construction, thereby improving the accuracy of the overall missing rate curve.

(7) Set counter i=i+1 and return to step (2);

(8) constructing a first histogram according to the reuse distances of all access objects in the access request queue that hit the cache filter, and then proceeding to step (9);

Specifically, in the first histogram, the horizontal axis 1 represents the reuse distance, and the corresponding vertical axis is the total number of access objects with a reuse distance of 1.

(9) constructing a second histogram according to the reuse distances of all access objects in the access request queue that are not hit in the cache filter, and then proceeding to step (10);

Specifically, in the second histogram, the horizontal axis 1 represents the reuse distance, and the corresponding vertical axis is the total number of access objects with a reuse distance of 1.

(10) The first histogram and the second histogram are combined to construct a complete reuse distance histogram, and the reuse distance histogram is integrated to obtain the final missing rate curve.

It can be seen from the workflow of the missing rate curve that, compared with the traditional construction process, the present invention adds a cache filter so that objects with high content popularity are calculated separately, thereby reducing the problem of large errors in the head of the missing rate curve caused by traditional sampling calculations. In addition, based on traditional sampling, the present invention uses different sampling rates for different objects according to the size of the object, thereby reducing the impact of object size differences on the accuracy of missing rate curve construction.

It will be easily understood by those skilled in the art that the above description is only a preferred embodiment of the present invention and is not intended to limit the present invention. Any modifications, equivalent substitutions and improvements made within the spirit and principles of the present invention should be included in the protection scope of the present invention.

Claims (8)

1. A method for constructing a missing rate curve in a heterogeneous granularity storage system, characterized by comprising the following steps: (1) Receive access request sequence and set counter i=1; (2) Determine whether i is equal to the total number of access requests in the access request sequence. If so, proceed to step (8); otherwise, proceed to step (3); (3) Load the i-th access request in the access request sequence into the cache filter, and determine whether the access object corresponding to the i-th access request hits in the cache filter. If so, proceed to step (4); otherwise, proceed to step (5); (4) Obtain the reuse distance of the access object corresponding to the i-th access request, and then proceed to step (7); (5) obtaining a sampling rate of the access object according to the size of the access object corresponding to the i-th access request; (6) sampling the access object according to the sampling rate of the access object corresponding to the i-th access request obtained in step (5), calculating the reuse distance of the access object, and then proceeding to step (7); (7) Set counter i=i+1 and return to step (2); (8) constructing a first histogram according to the reuse distances of all access objects in the access request queue that hit the cache filter, and then proceeding to step (9); (9) constructing a second histogram according to the reuse distances of all access objects in the access request queue that are not hit in the cache filter, and then proceeding to step (10); (10) The first histogram and the second histogram are combined to construct a complete reuse distance histogram, and the reuse distance histogram is integrated to obtain the final missing rate curve. 2. The miss rate curve construction method in a heterogeneous granularity storage system according to claim 1 is characterized in that step (1) is an actual running access request sequence obtained from the cache system. 3. The method for constructing a miss rate curve in a heterogeneous granularity storage system according to claim 1 or 2, characterized in that each access request corresponds to only one access object, and one access object corresponds to at least one access request. 4. The miss rate curve construction method in a heterogeneous granularity storage system according to claim 3 is characterized in that only the most recent access objects whose size is not greater than L are retained in the cache filter, where the value range of L is 0 to 5×1/r×log ₂ (1/r), where r is a preset basic sampling rate size. 5. The method for constructing a missing rate curve in a heterogeneous granularity storage system according to claim 4, characterized in that: The reuse distance of access object i is the sum of the sizes of all other access objects except the access object i within the interval from the last access to the access object i; The sampling rate r _D of the access object D is calculated according to the following formula: r _D ＝r×s _D /s _avg Where s _D is the size of the access object, and s _avg is the average value of the access objects corresponding to all access requests in the access request sequence. 6. The method for constructing a miss rate curve in a heterogeneous granularity storage system according to claim 5, wherein step (6) comprises the following sub-steps: (6-1) Sampling the access object corresponding to the i-th access request according to the sampling rate r _D of the access object corresponding to the i-th access request calculated in step (5) to generate a random number between 0 and 1, and determining whether the random number is less than or equal to r _D . If so, proceed to step (6-2); otherwise, the process ends. (6-2) Construct a binary tree T _ws , so that the in-order traversal of the binary tree T _ws is equivalent to the order of access objects corresponding to the i-th access request obtained in step (5); (6-3) Calculate the reuse distance sBRD of the access object corresponding to the i-th access request based on the binary tree T _ws obtained in step (6-2); (6-4) Use the reuse distance of the access object corresponding to the i-th access request obtained in step (6-3) and obtain the final reuse distance eBRD of the access object corresponding to the i-th access request according to the formula eBRD=sBRD/r+size(T _CF ), where size(T _CF ) is the total size of all access objects stored in the cache filter. 7. The method for constructing a missing rate curve in a heterogeneous granularity storage system according to claim 6, characterized in that: In the first histogram, the horizontal axis 1 represents the reuse distance, and its corresponding vertical axis is the total number of access objects with a reuse distance of 1; In the second histogram, the horizontal axis 1 represents the reuse distance, and the corresponding vertical axis is the total number of access objects with a reuse distance of 1. 8. A system for constructing a missing rate curve in a heterogeneous granularity storage system, comprising: The first module is used to receive an access request sequence and set a counter i=1; The second module is used to determine whether i is equal to the total number of access requests in the access request sequence, if yes, then enter the eighth module, otherwise, then transfer to the third module; The third module is used to load the i-th access request in the access request sequence into the cache filter, and determine whether the access object corresponding to the i-th access request hits in the cache filter, if yes, transfer to the fourth module, otherwise transfer to the fifth module; The fourth module is used to obtain the reuse distance of the access object corresponding to the i-th access request, and then transfer to the seventh module; A fifth module is used to obtain a sampling rate of the access object according to the size of the access object corresponding to the i-th access request; The sixth module is used to sample the access object corresponding to the i-th access request according to the sampling rate of the access object obtained in the fifth module, calculate the reuse distance of the access object, and then transfer to the seventh module; The seventh module is used to set the counter i=i+1 and return to the second module; The eighth module is used to construct a first histogram according to the reuse distances of all access objects in the access request queue that hit the cache filter, and then transfer to the ninth module; The ninth module is used to construct a second histogram according to the reuse distances of all access objects in the access request queue that are not hit in the cache filter, and then transfer to the tenth module; The tenth module is used to merge the first histogram and the second histogram to construct a complete reuse distance histogram, and integrate the reuse distance histogram to obtain a final missing rate curve.