Systems and methods for using excitement values to predict future access to resources

• US 20070094452A1
• Filed: 10/21/2005
• Published: 04/26/2007
• Est. Priority Date: 10/21/2005
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Isilon Systems Incorporated (Dell Technologies Inc.)
• Inventors: Fachan, Neal
• Granted Patent: US 7,386,675 B2
• Time in Patent Office: Days
• US Class Current: 711/137
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache

Abstract

Systems and methods using an excitement protocol enable prediction of which blocks of a resource to prefetch and store in memory. The system maintains a set of excitement values corresponding to the resource being accessed. The system also maintains a threshold. As blocks of the resource are requested, the system updates the set of excitement values. The system compares the excitement level to the threshold to determine whether to prefetch the corresponding resource block.

Claims

1. A system for predicting future accesses to a set of resources comprising:

a processor configured to;

access a set of resources, the set of resources comprising resource blocks;

store a set of excitements, the set of excitements comprising excitement values that correspond to a plurality of the resource blocks;

store a threshold;

receive a request for a resource block;

access the requested resource block;

update the set of excitements, wherein a change in the excitement values is related to the requested resource block;

determine a set of predicted resource blocks by comparing the excitement values to the threshold;

access the set of predicted resource blocks; and

return the requested and predicted resource blocks.

2. A system for improved access to a set of resources comprising:

a processor configured to;

access a set of resources, the set of resources comprising resource blocks;

maintain a set of excitements, the set of excitements comprising excitement values that correspond to a plurality of the resource blocks;

maintain a threshold;

receive a request for a resource block;

update the set of excitements, wherein a change in the excitement values is related to the requested resource block;

determine a set of predicted resource blocks by comparing the excitement values to the threshold.

3. The system of claim 2, wherein the processor is further configured to retrieve a plurality of the predicted resource blocks.

4. The system of claim 2, wherein the predicted resource blocks have excitement values greater than or equal to the threshold.

5. The system of claim 2, wherein the change in the excitement values comprises a convolution.

6. The system of claim 2, wherein the change in excitement values comprises a function depending on an offset from the requested resource block.

7. The system of claim 6, wherein the function enables just-in-time access to the set of predicted resource blocks.

8. The system of claim 6, wherein the function is at least one of inversely proportional to the offset over a range of offsets, substantially constant over a range of offsets, non-zero over a range of offsets, symmetric with respect to zero offset, zero for negative offsets, and less than or equal to zero for a first range of offsets and greater than or equal to zero for a second range of offsets.

9. The system of claim 2, wherein the change in excitement values comprises a decrease in value with time.

10. The system of claim 9, wherein the decrease is linear or exponential.

11. The system of claim 2, wherein the set of predicted resource blocks is accessed according to a just-in-time policy.

12. A method of predicting future accesses to a resource, the method comprising:

accessing a set of resources, the set of resources comprising resource blocks;

maintaining a set of excitements, the set of excitements comprising excitement values that correspond to a plurality of the resource blocks;

maintaining a threshold;

receiving a request for a resource block;

accessing the requested resource block;

updating the set of excitements, further comprising calculating a change in the excitement values is related to the requested resource block;

determining a set of predicted resource blocks, further comprising comparing the excitement values to the threshold;

accessing the set of predicted resource blocks; and

returning the requested and predicted resource blocks.

13. The method of claim 12, wherein the step of comparing the excitement value to the threshold further comprises using an inequality.

14. The method of claim 12, wherein the step of accessing the predicted resource blocks further comprises providing the resource blocks just-in-time.

15. The method of claim 12, wherein the step of updating the set of excitements further comprises calculating a decrease in excitement value with time.

16. The method of claim 15, wherein the step of calculating the decrease in excitement values with time comprises a linear decrease or an exponential decrease.

17. The method of claim 12, wherein the step of calculating the change in the excitement values further comprises calculating an offset from the requested resource block.

18. The method of claim 12, wherein the step of calculating an offset further comprises evaluating a function that is inversely proportional to the offset over a range of offsets or substantially constant over a range of offsets.

19. A system for improved access to a data file by using an excitement array comprising:

a storage medium comprising a stored data file;

a processor operably coupled to the storage medium, the processor configured to;

maintain an excitement array;

maintain a threshold;

receive a read request for a block of the data file;

retrieve the block from the storage medium; and

determine a set of predicted blocks by comparing the excitement array to the threshold.

20. The system of claim 19, wherein the processor is further configured to update the excitement array, retrieve at least one of the set of predicted blocks, or store at least one of the set of predicted blocks in a cache.

21. The system of claim 19, wherein the processor is further configured to:

return the retrieved block; and

return at least one of the retrieved predicted blocks.

22. A system for improved access to data comprising:

a storage device configured to store data blocks;

a memory configured to store one or more of the data blocks;

a processor operably coupled to the memory and the storage device, the processor configured to;

maintain one or more excitement values corresponding to the data blocks;

maintain a threshold;

receive a location corresponding to a request for a data block stored in the storage device or in the memory;

update the one or more excitement values based on the location of the requested data block;

determine a set of predicted data blocks by comparing the one or more excitement values to the threshold; and

return a signal corresponding to the set of predicted data blocks to the storage device or the memory.