Method, device and computer program product for managing storage system

Techniques manage a storage system. In accordance with such techniques, an access request for target data is received; a storage position of the target data is determined, the storage position indicating one of a storage device and a cache; a target element corresponding to the target data is determined from a first replacement list and a second replacement list associated with the first replacement list based on the storage position, the first replacement list including at least a counting element, the counting element indicating an access count of data in the storage device, the second replacement list including a low-frequency access element, the low-frequency access element indicating a cache page with a low access frequency in the cache; and a position of the target element in a replacement list where the target element exist is updated. Therefore, the overall performance of the storage system can be improved.

CROSS-REFERENCE TO RELATED APPLICATION(S)

This application claims priority to Chinese Patent Application No. CN201810803486.0, on file at the China National Intellectual Property Administration (CNIPA), having a filing date of Jul. 20, 2018, and having “METHOD, DEVICE, AND COMPUTER PROGRAM PRODUCT FOR MANAGING STORAGE SYSTEM” as a title, the contents and teachings of which are herein incorporated by reference in their entirety.

FIELD

Various implementations of the present disclosure relate to management of storage systems, and more specifically, to a method, device and computer program product for cache page management.

BACKGROUND

In a storage system including a disk array, caches are usually utilized to increase the speed for accessing data in the storage system. Normally the first layer cache is a cache such as DRAM, and the second layer cache is a cache such as SSD/NVMe. For the second layer cache, it is desirable to reduce promotion counts of data on disks to cache pages while increasing the hit rate of cache pages in the cache. Therefore, there is a need for an improved solution to increase the storage system performance.

SUMMARY

Implementations of the present disclosure provide a method, device and computer program product for managing a storage system.

In a first aspect of the present disclosure, provided is a method for managing a storage system. The method includes: receiving an access request for target data; determining a storage position of the target data, the storage position indicating one of a storage device and a cache; determining, based on the storage position, a target element corresponding to the target data from a first replacement list and a second replacement list associated with the first replacement list, the first replacement list including at least a counting element, the counting element indicating an access count of data in the storage device, the second replacement list including a low-frequency access element, the low-frequency access element indicating a cache page with a low access frequency in the cache; and updating a position of the target element in a replacement list where the target element exist.

In a second aspect of the present disclosure, provided is a device for managing a storage system. The device includes at least one processing unit and at least one memory. The at least one memory is coupled to the at least one processing unit and stores instructions executed by the at least one processing unit. The instructions, when executed by the at least one processing unit, causes the device to perform acts including: receiving an access request for target data; determining a storage position of the target data, the storage position indicating one of a storage device and a cache; determining, based on the storage position, a target element corresponding to the target data from a first replacement list and a second replacement list associated with the first replacement list, the first replacement list including at least a counting element, the counting element indicating an access count of data in the storage device, the second replacement list including a low-frequency access element, the low-frequency access element indicating a cache page with a low access frequency in the cache; and updating a position of the target element in a replacement list where the target element exist.

According to a third aspect of the present disclosure, there is provided a computer program product. The computer program product is tangibly stored on a non-transient computer readable medium and includes machine executable instructions, the machine executable instructions, when executed, causing the machine to implement a method according to the first aspect.

Throughout the figures, the same or corresponding numeral refers to the same or corresponding part.

DETAILED DESCRIPTION

The preferred implementations of the present disclosure will be described in more details with reference to the drawings. Although the drawings illustrate the preferred implementations of the present disclosure, it should be appreciated that the present disclosure can be implemented in various manners and should not be limited to the implementations explained herein. On the contrary, the implementations are provided to make the present disclosure more thorough and complete and to fully convey the scope of the present disclosure to those skilled in the art.

As used herein, the term “includes” and its variants are to be read as open-ended terms that mean “includes, but is not limited to.” The term “or” is to be read as “and/or” unless the context clearly indicates otherwise. The term “based on” is to be read as “based at least in part on.” The terms “one example implementation” and “one implementation” are to be read as “at least one example implementation.” The term “a further implementation” is to be read as “at least a further implementation.” The terms “first”, “second” and so on can refer to same or different objects. The following text also can include other explicit and implicit definitions.

Manage Cache by Traditional LRU Algorithm

FIG. 1shows a schematic view of one example of a traditional storage system100100. As depicted, the storage system100includes a cache110and a storage device120. The cache110may be a cache such as SSD/NVMe/NVDIMM, etc. The storage device120may be a Redundant Array of Independent Disks (RAID) and the like. However, examples of the storage device120are not limited to this and may be an electric storage device, a magnetic storage device, an optical storage device, an electromagnetic storage device, a semiconductor storage device, or any appropriate combination thereof.

The cache110includes multiple volumes, and each volume may include multiple cache pages. In addition, the cache110further includes a mapping table130, an access history list140, a page replacement list150and a controller190. The mapping table130may include access information. When data exists in the cache110, the access information may indicate a correspondence between an address of data in the storage device120and a cache page where data resides. In addition, when data does not exist in the cache110, the access information may indicate an access history of data in the storage device120, e.g. the number of times data in the storage device120has been accessed.

The access history list140may include history information1451-1457(collectively referred to as “history information”). Here, the amount of the history information145is merely example, and the access history list140may include any appropriate amount of the history information145. The history information145may include an access history of data, the data residing in the storage device120and not in the cache110. The access history may be, for example, the number of times data in the storage device120has been accessed. In some implementations, the access information may include identification (e.g. an address, an identifier, a name, etc.) of the history information145, so that the access history included in the history information145may be determined from the access information.

The page replacement list150may include page elements1551-1555(collectively referred to as “page element155”). Here, the number of the page elements155is merely example, and the page replacement list150may include any appropriate number of the page elements155. The page element155may indicate a cache page. In some implementations, the page element155(e.g. page element1551) at a start position of the page replacement list150may indicate the most recently accessed cache page, while the page element155(e.g. page element1555) at an end position of the page replacement list150may indicate the least recently accessed cache page. In addition, in some implementations, for each volume, there may exist one page replacement list150.

The controller190may manage the cache110, e.g. by a Least Recently Used (LRU) algorithm. The controller190may record the number of times data in the storage device120has been accessed, identify data being accessed in a large number of times, and promote or cache the data being accessed in a large number of times from the storage device120to the cache110. In this case, when an access request is received next time, the controller190will look up in the mapping table130and find data is moved to the cache110, so that data is read from/written to the cache110so as to accelerate the processing of the access request.

In some implementations, an example process of the controller190managing the cache110is as below:

Step 1: When the controller190receives an access request for target data, the controller190first looks up in the mapping table130to determine whether in the mapping table130there exists access information corresponding to the target data, and content indicated by the access information. If the access information indicates a correspondence between an address of the target data in the storage device120and a cache page where the target data resides (also called “hit”), then the flow jumps to step 5; if the access information indicates the number of times the target data in the storage device120has been accessed (also called “pseudo hit”), then the flow jumps to step 3; if no access information corresponding to the target data exists in the mapping table130, then the flow jumps to step 2.

Step 2: The controller190allocates the history information145to the target data from the end position of the access history list140, so as to track the number of times the target data in the storage device120has been accessed, and set a position of the allocated history information145as the start position of the access history list140, in other words, insert the allocated history information145to the start position of the access history list140. In addition, the controller190creates in the mapping table130access information pointing to the history information145and creates in the page replacement list150a count element pointing to the history information145based on the allocated history information145. Then, the flow jumps to step 4.

Step 3: The controller190increments the history information145corresponding to the target data, e.g. increasing an access count of the target data in the storage device120by 1; if the access count is larger than a predefined threshold, then the controller190promotes or caches the target data from the storage device120to the cache110, changes the access information in the mapping table130to indicate a correspondence between an address of the target data in the storage device120and a cache page where the target data resides, and adds in the page replacement list150a page element155indicating the cache page where the target data resides. Then, the flow jumps to step 4.

Step 4: The controller190sends the access request to the storage device120, and when an access operation in the storage device120completes, the controller190sends a completion notification to an up-layer driver.

Step 5: The controller190sets a position of the page element155corresponding to the target data as the start position of the page replacement list150, sends the access request to the cache110, and when an access operation in the cache110completes, the controller190sends a completion notification to an up-layer driver.

In this way, the controller190achieves management of the cache110. However, since the controller190does not record access frequency for a cache page, only access time of the cache page will affect the position of the page element155, which corresponds to the cache page, in the page replacement list150, while access frequency for the cache page will not affect the position. Therefore, in this way, it is possible that data in a cache page with a high access frequency in the cache110are replaced by recently accessed data.

For example, as shown inFIG. 1, suppose the predefined threshold is 3, and a hit count of the cache page in the cache110which corresponds to the page element1555at the end position of the page replacement list150is 10. When the access count of the target data in the storage device120indicated by the history information1511is larger than 3, the controller190promotes or caches the target data from the storage device120to the cache110so as to replace data in the cache page corresponding to the page element1555. In other words, least recently accessed data with the access count of 10 in the cache110are replaced by most recently accessed data with the access count of 3 in the storage device120.

The foregoing drawback is especially highlighted in cases of burst of access to infrequently used data, cyclic access to a file that is slightly larger than the cache size of a cache, etc. To solve this problem, the controller190may manage the cache110by other means, e.g. a Low Inter-Reference Recency Set (LIRS) algorithm to be described below.

Manage Cache by Traditional LIRS Algorithm

FIG. 2shows a schematic view of one example of a traditional storage system200using a LIRS algorithm. The principles of the LIRS algorithm lie in dividing storage blocks into two sets: a high-frequency access storage block set and a low-frequency access storage block set. Each block in the cache has a high-frequency access status or a low-frequency access status. Some low-frequency access storage blocks might not reside on the cache, but the cache has a non-resident low-frequency access element indicating the non-resident low-frequency access storage block.

In addition, the principles of the LIRS algorithm also lie in dividing the cache into a major part and a minor part. The major part is used to store high-frequency access storage blocks, while the minor part is used to store low-frequency access storage blocks. The sum of the size of the major part and the size of the minor part is equal to the size of the cache. When an access request for target data encounters a miss in the cache, and a storage block in the cache needs to be replaced with target data, the LIRS algorithm chooses a low-frequency access storage block residing on the cache. High-frequency access storage blocks always reside on the cache, so there are no misses for access requests for high-frequency access storage blocks. On the contrary, since the minor part of the cache which is used to store low-frequency access storage blocks is very small (usually as small as 1% of the cache size), an access request for a low-frequency access storage block is likely to encounter a miss.

Further, the principles of the LIRS algorithm lie in using a global list to manage all storage blocks in the cache. When a cached block evicts out of the cache, information associated with the storage block still exists in the global list.

The storage system200shown inFIG. 2is a LISR algorithm-based storage system. Like the storage system100, the storage system200includes a cache210and a storage device220. The cache210includes multiple volumes, and each volume may include multiple cache pages. In addition, the cache210further includes a mapping table230and a controller290.

Unlike the storage system100, access information in the mapping table230in the storage system200cannot indicate an access history of data in the storage system220, and the cache210is managed using two page replacement lists270and280.

The page replacement list270may be used to store elements indicating recently accessed storage blocks, which elements may include high-frequency access block elements (e.g. elements2753,2754), low-frequency access block elements (e.g. element2751) as well as non-resident low-frequency access elements (e.g. element2752). The high-frequency access block element indicates a storage block with a high access frequency in the cache210. The low-frequency access block element indicates a storage block with a low access frequency in the cache210. By contrast, the page replacement list280may be used to store elements indicating less recently accessed storage blocks, which elements may only include low-frequency access block elements (e.g. elements2851,2852).

However, since non-resident low-frequency access elements may exist in the page replacement list270, the length of the page replacement list270is not fixed and even might exceed the limit of the storage system200. In addition, once target data is accessed, the target data is cached to the cache210, which brings about expensive overheads to the storage system200because promoting/caching the target data from the storage device220to the cache210and flushing/storing low-frequency access storage blocks in the cache210to the storage device220is expensive. Therefore, although the storage system200improves the hit rate of target data as compared with the storage system100, the storage system200also increases counts of promoting/caching data from the storage device220to the cache210, which is not desired.

Storage System of Present Disclosure

Example implementations of the present disclosure propose a solution for managing a storage system. In the solution, a controller in the storage system receives an access request for target data and determines a storage position of the target data. The storage position indicates one of a storage device and a cache. Then, the controller determines a target element corresponding to the target data from a first replacement list and a second replacement list associated with the first replacement list based on the storage position. The first replacement list at least includes a counting element, which indicates the number of times data in the storage device has been accessed. The second replacement list includes a low-frequency access element, which indicates a cache page with a low access frequency in the cache. Next, the controller updates a position of the target element in a replacement list where the target element exists. In this way, a hit rate of the target data in the storage system may be increased, and counts of promoting/caching data from the storage device to the cache may be reduced. Therefore, the efficiency and performance of the storage system may be increased in a concise and effective manner, and further the user experience can be improved.

FIG. 3shows a schematic view of a storage system300in which implementations of the present disclosure may be implemented. As depicted, the storage system300includes a cache310and a storage device320. The cache310may be a cache such as SSD/NVMe/NVDIMM, etc. The storage device320may be a Redundant Array of Independent Disks (RAID) and the like. However, examples of the storage device320are not limited to this and may be an electric storage device, a magnetic storage device, an optical storage device, an electromagnetic storage device, a semiconductor storage device, or any appropriate combination thereof.

The cache310includes multiple volumes, and each volume may include multiple cache pages. In addition, the cache310further includes a mapping table330, an access history list340, a page replacement list370(also referred to as “a first replacement list”), a page replacement list380(also referred to as “a second replacement list”) and a controller390. Although this figure only illustrates one first replacement list370and one second replacement list380, in some implementations, there may exist one first replacement list370and one second replacement list380for each volume. Therefore, when the cache310includes multiple volumes, there may exist the first replacement lists370and the second replacement lists380corresponding to each volume respectively. In addition, the controller390may manage the cache310. Management operations executed by the controller390will be described in conjunction withFIGS. 5 to 9.

The mapping table330may include access information. When data exists in the cache310, the access information may indicate a correspondence between an address of data in the storage device120and a cache page where data exists. In addition, when data does not exist in the cache310, the access information may indicate an access history of data in the storage device320, e.g. the number of times data in the storage device120has been accessed.

The access history list340may be used to track access history information of missed target data in the cache310. In some implementations, the access history list340may include history information3451-3457(collectively referred to as “history information345”). Here, the amount of the history information345is merely example, and the access history list340may include any appropriate amount of the history information345. The history information345may include an access history of data, the data existing in the storage device320and not in the cache310. The access history may be, for example, the number of times data in the storage device320has been accessed.

The access history list340may be associated with the mapping list330and the first replacement list370. In some implementations, the history information345may be linked to the access information in the mapping list330and a counting element375in the first replacement list370. For example, the access information345and the counting element375may include identification (e.g. an address, an identifier, a name, etc.) of the history information345, so that the access history included in the history information345may be determined from the access information345and the counting element375. On the contrary, the access history list340cannot be associated with the second replacement list380, e.g. the history information345cannot be linked to any element in the second replacement list380.

In some implementations, the size (e.g. the amount of the included history information345) of the access history list340depends on the total cache size, the cache page size and the percentage of effective caches. For example, the amount of the history information345may be derived from an equation below:

n=(sd⁢_⁢1+sd⁢_⁢2+…+sd_m)⋆p⁢⁢%sc,(1)
N denotes the total amount of the history information345in the access history list340; Sd_1to Sd_mdenote the size of m caches (collectively denoted as the cache310) in the storage system300respectively, m being a natural number larger than 1; p denotes the percentage of effective caches; and Scdenotes the size of one cache page.

The first replacement list370may be used to store elements3751-3754(collectively referred to as “element375”) indicating recently accessed cache pages. Here, the number of the elements375is merely example, and the first replacement list370may include any appropriate number of the elements375. The elements may include high-frequency access elements (e.g. elements3753,3754), low-frequency access elements (e.g. element3751) as well as counting elements (e.g. element3752). The high-frequency access element indicates a cache page with a high access frequency in the cache310. The low-frequency access element indicates a cache page with a low access frequency in the cache310. The counting element indicates access counts of data in the storage device320.

In some implementations, the element375(e.g. low-frequency access element3751) at the start position of the first replacement list370may indicate the most recently accessed cache page in the first replacement list370, and the element375(e.g. high-frequency access element3754) at the end position of the first replacement list370may indicate the least recently accessed cache page in the first replacement list370.

By contrast, the second replacement list380may be used to store elements3851-3852(collectively referred to as “element385”) indicating less recently accessed cache pages. Here, the number of the elements385is merely example, and the second replacement list380may include any appropriate number of the elements385. The elements only include low-frequency access elements (e.g. elements3851and3852). In some implementations, the element385(e.g. low-frequency access element3851) at the start position of the second replacement list380may indicate the most recently accessed cache page in the second replacement list380, and the element385(e.g. high-frequency access element3852) at the end position of the second replacement list380may indicate the least recently accessed cache page in the second replacement list380.

In some implementations, the size (e.g. number) of high-frequency access elements and low-frequency access elements depends on the total cache size, the cache page size and the percentage of effective caches. For example, the number of high-frequency access elements and low-frequency access elements may be derived from an equation below:
Σj=0m(sd_j)*p%=Σi=0n(hi+li)*sc(2)
N denotes the total number of elements in both the first replacement list370and the second replacement list380, i.e. the total number of cache pages in the cache310; h1to hndenote the number of high-frequency access elements in the first replacement list370for the 1stvolume to the nthvolume respectively; l1to lndenote the number of low-frequency access elements in both the first replacement list370and the second replacement list380for the 1stvolume to the nthvolume respectively; Sd_1to Sd_mdenote the size of m caches (collectively denoted as the cache310) in the storage system300respectively, m being a natural number larger than 1; p denotes the percentage of effective caches; and Scdenotes the size of one cache page.

As seen by comparing Equation (1) with Equation (2), the total number of elements in both the first replacement list370and the second replacement list380or the total number of cache pages in the cache310is equal to the total amount of the history information345in the access history list340. In other words, for each cache page, there exist a corresponding element in the replacement list and history information in the access history list340.

In addition, in some implementations, the proportion of high-frequency access elements (or the cache pages to which the high-frequency access elements indicate) to low-frequency access elements (or the cache pages to which the low-frequency access elements indicate) is fixed for each volume. Further, the number of high-frequency access elements is typically larger than the number of low-frequency access elements. For example, the ratio of the number of high-frequency access elements to the number of low-frequency access elements may be 4:1 or 5:1, which may be denoted as an example equation below:

l0h0=l1h1=l2h2=…=lnhn,(3)
h1to hndenote the number of high-frequency access elements in the first replacement list370for the 1stvolume to the nthvolume respectively; 11to 1ndenote the number of low-frequency access elements in both the first replacement list370and the second replacement list380for the 1stvolume to the nthvolume respectively.

In view of the example structure described above, implementations of the present disclosure may be implemented based on principles below. In some implementations, when target data is promoted/cached from the storage device320to the cache310, first an element corresponding to a cache page where the target data is stored is added to the first replacement list370, and the element is set as a high-frequency access element. When a high-frequency access element cools (e.g. has not been accessed for a long time), the high-frequency access element is moved to the second replacement list380and is set as a low-frequency access element.

Additionally, in some implementations, when the cache310is created, all history information345in the access history list340is also created. If there exists a counting element in the first replacement list370, then history information corresponding to the counting element also exists in the access history list340.

Moreover, in some implementations, an element at the end position of the first replacement list370must be a high-frequency access element or a low-frequency access element. When a high-frequency access element in the first replacement list370cools and hence is moved to the second replacement list380, if an element at the end position of the first replacement list370is a counting element, then the counting element will be removed from the first replacement list370but still exists in the access history list340. In addition, the order of other elements in the first replacement list370from which the counting element has been removed remains unchanged.

Further, in some implementations, for an access request missed in the mapping table330, history information at the end position of the access history list340is set as history information of target data which the access request is aimed to, and the history information will be added to the start position of the access history list340. In addition, a counting element is created for the target data, and the counting element is added to the start position of the first replacement list370. Further, access information indicating the number of times the target data in the storage device320has been accessed is created for the target data.

In this way, implementations of the present disclosure cause high-frequency accessed cache pages to be stored much longer than low-frequency accessed cache pages in the cache310, thereby increasing the utilization and efficiency of the cache310and improving the overall performance of the storage system300.

Method for Managing Storage System of Present Disclosure

FIG. 4shows an example flowchart of a method400for managing a storage system according to implementations of the present disclosure. For example, the method400may be executed at the storage system300as shown inFIG. 3or other appropriate system. For example, the method400may be executed by the controller390in the storage system300or the cache310or other associated computing device. The controller or computing device may be any appropriate controller or computing device that is implemented in the storage system300or the cache310in a centralized or distributed way, including but not limited to, a personal computer, a server, a client, a handheld or laptop device, a multiprocessor, a microprocessor, a set-top box, programmable consumer electronics, a network PC, a minicomputer, a mainframe computer, a distributed cloud as well as combinations thereof. In addition, the method400may further include an additional step that is not shown and/or omit a step that is shown, and the scope of the present disclosure is not limited in this regard.

The controller390receives an access request for target data at410, and determines a storage position of the target data at420. The storage position may indicate one of the storage device320and the cache310. In some implementations, the controller390looks up access information associated with the target data in the cache310, and determines, based on the access information, whether the target data exists on a cache page of the cache310.

For example, the controller390may look up access information associated with the target data in the mapping table330. As described above, when data exists in the cache310, the access information may indicate a correspondence between an address of the data in the storage device320and a cache page where the data exists. In addition, when data does not exist in the cache, the access information may indicate an access history of the data in the storage device320, e.g. access counts of the data in the storage device320.

At430, the controller390determines a target element corresponding to the target data from the first replacement list370and the second replacement list380associated with the first replacement list370. In some implementations, when the controller390finds access information associated with the target data in the mapping table330, and the access information indicates a correspondence between an address of the target data in the storage device320and a cache page where the target data exists, the controller390may determine the target data exists on a cache page of the cache310. In this case, an element corresponding to the cache page in the first replacement list370and the second replacement list380is determined as a target element. The target element is one of a low-frequency access element and a high-frequency access element.

The first replacement list370at least includes a counting element. The counting element may indicate the number of times data in the storage device320has been accessed. In some implementations, the first replacement list370may further include a low-frequency access element and/or a high-frequency access element. The low-frequency access element indicates a cache page with a low access frequency in the cache310. The high-frequency access element indicates a cache page with a high access frequency in the cache310. The second replacement list380only includes a low-frequency access element.

Alternatively, when the target data does not exist on a cache page of the cache310, the controller390may determine whether access information associated with the target data exists in the cache310, the access information indicating the number of times the target data in the storage device320has been accessed. When the access information is determined as existing in the cache310, the controller390determines a counting element corresponding to the access information in the first replacement list370as the target element.

Alternatively, when the access information is determined as not existing in the cache310, the controller390allocates history information at an end position of the access history list340as history information associated with the target data, and adds the history information to a start position of the access history list340. In addition, the controller390creates a counting element, which is linked to the history information and associated with the target data, as the target element in the first replacement list370. Furthermore, the controller390further creates in the mapping table330access information that is linked to the history information and associated with the target data. Since the access information is linked to the history information, the access information may indicate the number of times the target data in the storage device320has been accessed.

At440, the controller390updates a position of the target element in a replacement list where the target element exists. A detailed example of the act440will be described in conjunction withFIGS. 5 to 9. In this way, implementations of the present disclosure may reduce counts of promoting/caching data from the storage device320to the cache310while increasing the hit rate of target data. Further, the utilization and efficiency of the cache310is increased, and the overall performance of the storage system300is improved.

FIG. 5shows a flowchart of an example of a method500for updating a position of a target element in a replacement list according to implementations of the present disclosure. For example, the method500may be executed by the controller390as shown inFIG. 3. It should be understood the method500is an example implementation of the act440, whereas implementations of the act440are not limited to this. In addition, the method500may further include an additional step that is not shown and/or may omit a step that is shown, and the scope of the present disclosure is not limited in this regard.

The method500pertains to the circumstance where a target element is in the first replacement list370and target data exists on a cache page of the cache310. At510, the controller390determines whether the target element is a low-frequency access element or a high-frequency access element in the first replacement list370. When the target element is a high-frequency access element, at520, the controller390sets a position of the target element as a start position of the first replacement list370. Otherwise, when the target element is a low-frequency access element, at530, the controller390determines an access interval of a cache page indicated by the target element. For example, the controller has received3access requests, among which the 1staccess request is aimed at cache page 1, the 2ndaccess request is aimed at cache page 2 and the 3rdaccess request is aimed at cache page 1. In this case, an access interval of cache page 1 is 2.

At540, the controller390obtains a maximum value of access intervals of cache pages indicated by high-frequency access elements and low-frequency access elements in the first replacement list370and the second replacement list380. At550, the controller390determines whether the access interval is larger than the maximum value. When the access interval is less than the maximum value, at560, the controller390sets the target element as the high-frequency access element from the low-frequency access element, and sets a position of the target element as a start position of the first replacement list370. Alternatively, when the access interval is larger than the maximum value, at580, the controller390sets a position of the target element as a start position of the first replacement list370.

In this way, by means of implementations of the present disclosure, when the target element is in the first replacement list370and the target data exists on a cache page of the cache310, a position of the target element in the replacement list may be updated, and hence the cache page may be replaced.

FIG. 6shows a flowchart of an example of a method600for updating a position of a target element in a replacement list according to implementations of the present disclosure. For example, the method600may be executed by the controller390as shown inFIG. 3. It should be understood the method600is an example implementation of the act440, whereas implementations of the act440are not limited to this. In addition, the method600may further include an additional step that is not shown and/or may omit a step that is shown, and the scope of the present disclosure is not limited in this regard.

The method600pertains to the circumstance where a target element is in the second replacement list380and target data exists on a cache page of the cache310. At610, the controller390determines an access interval of a cache page indicated by the target element. At615, the controller390obtains a maximum value of access intervals of cache pages indicated by high-frequency access elements and low-frequency access elements in the first replacement list370and the second replacement list380.

At620, the controller390determines whether the access interval is less than the maximum value. When the access interval is larger than the maximum value, at625, the controller390sets a position of the target element as a start position of the second replacement list380. Otherwise, when the access interval is less than the maximum value, at630, the controller390determines the number (also referred to as “first number”) of elements in the first replacement list370.

At635, the controller390determines whether the first number is less than a predefined threshold (also referred to as “first predefined threshold”). When the first number is less than the first predefined threshold, at640, the controller390adds the target element from the second replacement list380to a start position of the first replacement list370. Otherwise, when the first number is larger than the first predefined threshold, at645, the controller390determines the number (also referred to as “second number”) of elements in the second replacement list380.

At650, the controller390determines whether the second number is less than a predefined threshold (also referred to as “second predefined threshold”). When the second number is less than the second predefined threshold, at655, the controller390moves a high-frequency access element or a low-frequency access element at an end position of the first replacement list370to the second replacement list380. In addition, at660, the controller390determines whether an element at an end position of the first replacement list370is a counting element. When the element at the end position of the first replacement list370is a counting element, at665, the controller390removes the counting element from the first replacement list370. At670, the controller390adds the target element from the second replacement list380to a start position of the first replacement list370.

Alternatively, when the second number is larger than the second predefined threshold, at675, the controller390removes a low-frequency access element at an end position of the second replacement list380. In addition, the controller390further releases a cache page corresponding to the removed low-frequency access element, e.g. returns the cache page to a page free list. At680, the controller390moves a high-frequency access element or a low-frequency access element at the end position of the first replacement list370to the second replacement list380. In addition, at685, the controller390determines whether an element at an end position of the first replacement list370is a counting element. When the element at the end position of the first replacement list370is a counting element, at690, the controller390removes the counting element from the first replacement list370. At695, the controller390adds the target element from the second replacement list380to a start position of the first replacement list370.

In this way, by means of implementations of the present disclosure, when the target element is in the second replacement list380and the target data exists on a cache page of the cache310, a position of the target element in the replacement list may be updated, and hence the cache page may be replaced.

FIG. 7shows a flowchart of an example of a method700for updating a position of a target element in a replacement list according to implementations of the present disclosure. For example, the method700may be executed by the controller390as shown inFIG. 3. It should be understood the method700is an example implementation of the act440, whereas implementations of the act440are not limited to this. In addition, the method700may further include an additional step that is not shown and/or may omit a step that is shown, and the scope of the present disclosure is not limited in this regard.

The method700pertains to the circumstance where a target element is a counting element in the first replacement list370and target data does not exist on a cache page of the cache310. At710, the controller390determines whether the target element is a newly created counting element. When the target element is a newly created counting element, at720, the controller390sets a position of the target element as a start position of the first replacement list370.

Otherwise, at730, the controller390determines whether an access count of the target data in the storage device320indicated by the target element is less than a predefined threshold. When the access count is less than the predefined threshold, at740, the controller390sets a position of the target element as a start position of the first replacement list370. Alternatively, when the access count is larger than the predefined threshold, at750, the controller390sets the target element as a high-frequency access element from the counting element, and at760, sets a position of the target element as a start position of the first replacement list370.

In addition, in some implementations, when the access count is larger than the predefined threshold, the controller390may copy the target data from the storage device320to a cache page in the cache310. Further, the controller390may store in the access information a correspondence between an address of the target data in the storage device320and the cache page to which the target data is copied, so that the access information no longer indicates the number of times the target data in the storage device320has been accessed.

In this way, by means of implementations of the present disclosure, when the target element is a counting element in the first replacement list370and the target data does not exist on a cache page of the cache310, a position of the target element in the replacement list may be updated, and hence the cache page may be replaced.

FIGS. 8A to 8Cshow respective schematic views of examples800A-800C for updating a position of a target element in a replacement list.FIG. 8Ashows an access history list810A, a first replacement list820A and a second replacement list830A.

As shown inFIG. 8A, the access history list810A includes history information2, history information6, history information0, history information7and history information9. The first replacement list820A includes a high-frequency access element4, a low-frequency access element5, a low-frequency access element3, a counting element2, a high-frequency access element10, a counting element6, a counting element9as well as a high-frequency access element8. The counting element2, the counting element6and the counting element9correspond to the history information2, the history information6and the history information9respectively. In addition, the second replacement list830A includes a low-frequency access element5and a low-frequency access element3.

When the controller390receives an access request for target data1and there is no high-frequency access element, low-frequency access element or counting element associated with the target data1, as shown inFIG. 8B, the controller390replaces history information9at an end position of an access history list810B with history information1associated with the target data and replaces a counting element9in a first replacement list820B with a counting element1associated with the target data.

Then, as shown inFIG. 8C, the controller390sets a position of the history information1as a start position of an access history list810C. In addition, the controller390replaces a position of the counting element1with a start position of a first replacement list820C. In this way, implementations of the present disclosure can increase the utilization and efficiency of the cache and improve the overall performance of the storage system.

FIG. 9shows a schematic block diagram of an example device900which is applicable to implement implementations of the present disclosure. For example, the storage system300as shown inFIG. 3may be implemented by the device900. As depicted, the device900includes a central process unit (CPU)910, which can execute various suitable actions and processing based on the computer program instructions stored in the read-only memory (ROM)920or computer program instructions loaded in the random-access memory (RAM)930from a storage unit980. The RAM930can also store all kinds of programs and data required by the operations of the device900. CPU910, ROM920and RAM930are connected to each other via a bus940. The input/output (I/O) interface950is also connected to the bus940.

A plurality of components in the device900is connected to the I/O interface950, including: an input unit960, such as keyboard, mouse and the like; an output unit970, e.g., various kinds of display and loudspeakers etc.; a storage unit980, such as magnetic disk and optical disk etc.; and a communication unit990, such as network card, modem, wireless transceiver and the like. The communication unit990allows the device900to exchange information/data with other devices via the computer network, such as Internet, and/or various telecommunication networks.

The above described each procedure and processing, such as the methods400to700, can also be executed by the processing unit910. For example, in some implementations, the methods400to700can be implemented as a computer software program tangibly included in the machine-readable medium, e.g., the storage unit980. In some implementations, the computer program can be partially or fully loaded and/or mounted to the device900via ROM920and/or the communication unit990. When the computer program is loaded to the RAM930and executed by the CPU910, one or more steps of the above described methods400to700can be implemented. Alternatively, in other implementations, the CPU910also can be configured in other suitable manners to realize the above procedure/method.

The present disclosure can be method, device, system and/or computer program product. The computer program product can include a computer-readable storage medium, on which the computer-readable program instructions for executing various aspects of the present disclosure are loaded.

The computer-readable storage medium can be a tangible apparatus that maintains and stores instructions utilized by the instruction executing apparatuses. The computer-readable storage medium can be, but not limited to, such as electrical storage device, magnetic storage device, optical storage device, electromagnetic storage device, semiconductor storage device or any appropriate combinations of the above. More concrete examples of the computer-readable storage medium (non-exhaustive list) include: portable computer disk, hard disk, random-access memory (RAM), read-only memory (ROM), erasable programmable read-only memory (EPROM or flash), static random-access memory (SRAM), portable compact disk read-only memory (CD-ROM), digital versatile disk (DVD), memory stick, floppy disk, mechanical coding devices, punched card stored with instructions thereon, or a projection in a slot, and any appropriate combinations of the above. The computer-readable storage medium utilized here is not interpreted as transient signals per se, such as radio waves or freely propagated electromagnetic waves, electromagnetic waves propagated via waveguide or other transmission media (such as optical pulses via fiber-optic cables), or electric signals propagated via electric wires.

The described computer-readable program instruction can be downloaded from the computer-readable storage medium to each computing/processing device, or to an external computer or external storage via Internet, local area network, wide area network and/or wireless network. The network can include copper-transmitted cable, optical fiber transmission, wireless transmission, router, firewall, switch, network gate computer and/or edge server. The network adapter card or network interface in each computing/processing device receives computer-readable program instructions from the network and forwards the computer-readable program instructions for storage in the computer-readable storage medium of each computing/processing device.

The computer program instructions for executing operations of the present disclosure can be assembly instructions, instructions of instruction set architecture (ISA), machine instructions, machine-related instructions, microcode, firmware instructions, state setting data, or source codes or target codes written in any combinations of one or more programming languages, wherein the programming languages consist of object-oriented programming languages, e.g., Smalltalk, C++ and so on, and traditional procedural programming languages, such as “C” language or similar programming languages. The computer-readable program instructions can be implemented fully on the user computer, partially on the user computer, as an independent software package, partially on the user computer and partially on the remote computer, or completely on the remote computer or server. In the case where remote computer is involved, the remote computer can be connected to the user computer via any type of networks, including local area network (LAN) and wide area network (WAN), or to the external computer (e.g., connected via Internet using the Internet service provider). In some implementations, state information of the computer-readable program instructions is used to customize an electronic circuit, e.g., programmable logic circuit, field programmable gate array (FPGA) or programmable logic array (PLA). The electronic circuit can execute computer-readable program instructions to implement various aspects of the present disclosure.

Various aspects of the present disclosure are described here with reference to flow chart and/or block diagram of method, apparatus (system) and computer program products according to implementations of the present disclosure. It should be understood that each block of the flow chart and/or block diagram and the combination of various blocks in the flow chart and/or block diagram can be implemented by computer-readable program instructions.

The computer-readable program instructions can be provided to the processing unit of general-purpose computer, dedicated computer or other programmable data processing apparatuses to manufacture a machine, such that the instructions that, when executed by the processing unit of the computer or other programmable data processing apparatuses, generate an apparatus for implementing functions/actions stipulated in one or more blocks in the flow chart and/or block diagram. The computer-readable program instructions can also be stored in the computer-readable storage medium and cause the computer, programmable data processing apparatus and/or other devices to work in a particular manner, such that the computer-readable medium stored with instructions contains an article of manufacture, including instructions for implementing various aspects of the functions/actions stipulated in one or more blocks of the flow chart and/or block diagram.

The computer-readable program instructions can also be loaded into computer, other programmable data processing apparatuses or other devices, so as to execute a series of operation steps on the computer, other programmable data processing apparatuses or other devices to generate a computer-implemented procedure. Therefore, the instructions executed on the computer, other programmable data processing apparatuses or other devices implement functions/actions stipulated in one or more blocks of the flow chart and/or block diagram.

The flow chart and block diagram in the drawings illustrate system architecture, functions and operations that may be implemented by system, method and computer program product according to multiple implementations of the present disclosure. In this regard, each block in the flow chart or block diagram can represent a module, a part of program segment or code, wherein the module and the part of program segment or code include one or more executable instructions for performing stipulated logic functions. In some alternative implementations, it should be noted that the functions indicated in the block can also take place in an order different from the one indicated in the drawings. For example, two successive blocks can be in fact executed in parallel or sometimes in a reverse order dependent on the involved functions. It should also be noted that each block in the block diagram and/or flow chart and combinations of the blocks in the block diagram and/or flow chart can be implemented by a hardware-based system exclusive for executing stipulated functions or actions, or by a combination of dedicated hardware and computer instructions.

Various implementations of the present disclosure have been described above and the above description is only example rather than exhaustive and is not limited to the implementations of the present disclosure. Many modifications and alterations, without deviating from the scope and spirit of the explained various implementations, are obvious for those of ordinary skill in the art. The selection of terms in the text aims to best explain principles and actual applications of each implementation and technical improvements made in the market by each implementation, or enable other ordinary skilled in the art to understand implementations of the present disclosure.