Adaptive look-ahead configuration for prefetching data in input/output operations based on request size and frequency

Patent metadata

Field	Value
Publication number	US-10871902-B2
Application number	US-201916397596-A
Country	US
Kind code	B2
Filing date	Apr 29, 2019
Priority date	Apr 29, 2019
Publication date	Dec 22, 2020
Grant date	Dec 22, 2020

Abstract

Techniques are provided for adaptive look-ahead configuration for data prefetching based on request size and frequency. One method comprises performing the following steps: estimating an earning value for a particular portion based on an average size and frequency of past input/output requests for the particular portion; calculating a quota for the particular portion by normalizing the earning value for the particular portion of the storage system based on earning values of one or more additional portions of the storage system; obtaining a size of a look-ahead window for a new request based on the quota for the particular portion over a prefetch budget assigned to the storage system; and moving a requested data item and one or more additional data items within the look-ahead window from the storage system to the cache memory responsive to the requested data item and/or the additional data items within the look-ahead window not being in the cache memory.

First claim

What is claimed is:

1. A method, comprising:
in response to a request for at least one data item residing in a particular portion of a storage system that employs a cache memory, performing the following steps, using at least one processing device:
estimating an earning value for the particular portion of the storage system based on an average size and a numerical value that estimates a frequency of past input/output requests for the particular portion of the storage system;
calculating a quota for the particular portion of the storage system by normalizing the earning value for the particular portion of the storage system based on one or more earning values of one or more additional portions of the storage system;
obtaining a size of a look-ahead window for the request based on the quota for the particular portion of the storage system over a prefetch budget assigned to the storage system; and
moving the requested at least one data item and one or more additional data items within the look-ahead window from the storage system to the cache memory responsive to one or more of the requested at least one data item and the additional data items within the look-ahead window not being in the cache memory.

2. The method of claim 1 , wherein the particular portion of the storage system corresponds to one or more of a particular logical unit and a particular physical unit of the storage system.

3. The method of claim 1 , wherein the requested at least one data item is identified by an address of a storage space of the storage system.

4. The method of claim 1 , further comprising the step of varying one or more of the earning value, the quota and the size of the look-ahead window over time.

5. The method of claim 1 , wherein the calculating comprises determining the quota that identifies how much the particular portion of the storage system will lead a substantially better performance on the cache system for a given update in the size of the look-ahead window, using one or more criteria based on features extracted from observed input/output traces.

6. The method of claim 1 , wherein the obtaining assigns a larger look-ahead window to particular portions of the storage system that one or more of: (i) exhibit a larger average size of the input/output requests and (ii) exhibit a smaller average time distance between requests of the input/output requests.

7. The method of claim 1 , wherein the obtaining assigns a look-ahead window within a predefined boundary that constrains a minimum value and a maximum value for the look-ahead window to particular portions of the storage system.

8. A system, comprising:
a memory; and
at least one processing device, coupled to the memory, operative to implement the following steps:
in response to a request for at least one data item residing in a particular portion of a storage system that employs a cache memory, performing the following steps:
estimating an earning value for the particular portion of the storage system based on an average size and a numerical value that estimates a frequency of past input/output requests for the particular portion of the storage system;
calculating a quota for the particular portion of the storage system by normalizing the earning value for the particular portion of the storage system based on one or more earning values of one or more additional portions of the storage system;
obtaining a size of a look-ahead window for the request based on the quota for the particular portion of the storage system over a prefetch budget assigned to the storage system; and
moving the requested at least one data item and one or more additional data items within the look-ahead window from the storage system to the cache memory responsive to one or more of the requested at least one data item and the additional data items within the look-ahead window not being in the cache memory.

9. The system of claim 8 , wherein the particular portion of the storage system corresponds to one or more of a particular logical unit and a particular physical unit of the storage system.

10. The system of claim 8 , wherein the requested at least one data item is identified by an address of a storage space of the storage system.

11. The system of claim 8 , further comprising the step of varying one or more of the earning value, the quota and the size of the look-ahead window over time.

12. The system of claim 8 , wherein the calculating comprises determining the quota that identifies how much the particular portion of the storage system will lead a substantially better performance on the cache system for a given update in the size of the look-ahead window, using one or more criteria based on features extracted from observed input/output traces.

13. The system of claim 8 , wherein the obtaining assigns a larger look-ahead window to particular portions of the storage system that one or more of: (i) exhibit a larger average size of the input/output requests and (ii) exhibit a smaller average time distance between requests of the input/output requests.

14. The system of claim 8 , wherein the obtaining assigns a look-ahead window within a predefined boundary that constrains a minimum value and a maximum value for the look-ahead window to particular portions of the storage system.

15. A computer program product, comprising a non-transitory machine-readable storage medium having encoded therein executable code of one or more software programs, wherein the one or more software programs when executed by at least one processing device perform the following steps:
in response to a request for at least one data item residing in a particular portion of a storage system that employs a cache memory, performing the following steps:
estimating an earning value for the particular portion of the storage system based on an average size and a numerical value that estimates a frequency of past input/output requests for the particular portion of the storage system;
calculating a quota for the particular portion of the storage system by normalizing the earning value for the particular portion of the storage system based on one or more earning values of one or more additional portions of the storage system;
obtaining a size of a look-ahead window for the request based on the quota for the particular portion of the storage system over a prefetch budget assigned to the storage system; and
moving the requested at least one data item and one or more additional data items within the look-ahead window from the storage system to the cache memory responsive to one or more of the requested at least one data item and the additional data items within the look-ahead window not being in the cache memory.

16. The computer program product of claim 15 , wherein the requested at least one data item is identified by an address of a storage space of the storage system.

17. The computer program product of claim 15 , further comprising the step of varying one or more of the earning value, the quota and the size of the look-ahead window over time.

18. The computer program product of claim 15 , wherein the calculating comprises determining the quota that identifies how much the particular portion of the storage system will lead a substantially better performance on the cache system for a given update in the size of the look-ahead window, using one or more criteria based on features extracted from observed input/output traces.

19. The computer program product of claim 15 , wherein the obtaining assigns a larger look-ahead window to particular portions of the stora

Assignees

• Emc Ip Holding Co Llc

Inventors

• Dias Jonas F
• Pinho Rômulo Teixeira De Abreu
• Prado Adriana Bechara
• Gottin Vinícius Michel
• Calmon Tiago Salviano
• Sousa Eduardo Vera
• Martin Owen

Classifications

• G06F2212/6026

  Prefetching based on access pattern detection, e.g. stride based prefetch · CPC title

• G06F2212/502

  using adaptive policy · CPC title

• G06F2212/154

  Networked environment · CPC title

• G06F2212/152

  Virtualized environment, e.g. logically partitioned system · CPC title

• G06F12/0868

  Data transfer between cache memory and other subsystems, e.g. storage devices or host systems · CPC title