# US 10,871,902 B2 · Adaptive look-ahead configuration for prefetching data in input/output operations based on request size and frequency > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,871,902 B2 - Document ID: US10871902B2 - Status: Granted - Kind: B2 - Application number: 16/397,596 - Filed: 2019-04-29 - Published: 2020-10-29 - Granted: 2020-12-22 - Earliest claimed: 2019-04-29 - Assignees: EMC IP Holding Company LLC - Applicants: EMC IP Holding Company LLC - Inventors: Jonas F. Dias; Rômulo Teixeira de Abreu Pinho; Adriana Bechara Prado; Vinícius Michel Gottin; Tiago Salviano Calmon; Eduardo Vera Sousa; Owen Martin - Web page: https://patentgrep.com/patent/US10871902B2 ## CPC - G06F 3/061: {Improving I/O performance} - G06F 3/0656: {Data buffering arrangements} - G06F 3/0683: {Plurality of storage devices} - G06F 12/0862: with prefetch - G06F 12/0868: Data transfer between cache memory and other subsystems, e.g. storage devices or host systems - G06F 12/0895: of parts of caches, e.g. directory or tag array - G06F 2212/1016: Performance improvement - G06F 2212/152: Virtualized environment, e.g. logically partitioned system - G06F 2212/154: Networked environment - G06F 2212/502: using adaptive policy - G06F 2212/6026: Prefetching based on access pattern detection, e.g. stride based prefetch - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## 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. ## Claims ### Claim 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. ### Claim 2 (depends on 1) 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. ### Claim 3 (depends on 1) 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. ### Claim 4 (depends on 1) 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. ### Claim 5 (depends on 1) 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. ### Claim 6 (depends on 1) 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. ### Claim 7 (depends on 1) 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. ### Claim 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. ### Claim 9 (depends on 8) 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. ### Claim 10 (depends on 8) 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. ### Claim 11 (depends on 8) 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. ### Claim 12 (depends on 8) 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. ### Claim 13 (depends on 8) 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. ### Claim 14 (depends on 8) 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. ### Claim 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. ### Claim 16 (depends on 15) 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. ### Claim 17 (depends on 15) 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. ### Claim 18 (depends on 15) 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. ### Claim 19 (depends on 15) The computer program product of claim 15, 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. ### Claim 20 (depends on 15) The computer program product of claim 15, 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.