Pre-fetching data into a memory

• US 9,092,342 B2
• Filed: 02/26/2014
• Issued: 07/28/2015
• Est. Priority Date: 07/05/2007
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Silver Peak Systems Incorporated (Hewlett-Packard Enterprise Company)
• Inventors: Hughes, David Anthony, Burns, John
• Primary Examiner(s): Chery, Mardochee
• Application Number:
  US14/190,940
• Publication Number:
  US 20140181381A1
• Time in Patent Office: 517 Days
• Field of Search: 711/103, 711/104
• US Class Current: 1/1
• CPC Class Codes: G06F 12/00 Accessing, addressing or allocating within memory systems or architectures digital input from, or digital output to record carriers, e.g. to disk storage units, G06F3/06
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H04L 67/5681 Pre-fetching or pre-delivering data based on network characteristics

Abstract

Systems and methods for pre-fetching of data in a memory are provided. By pre-fetching stored data from a slower memory into a faster memory, the amount of time required for data retrieval and/or processing may be reduced. First, data is received and pre-scanned to generate a sample fingerprint. Fingerprints stored in a faster memory that are similar to the sample fingerprint are identified. Data stored in the slower memory associated with the identified stored fingerprints is copied into the faster memory. The copied data may be compared to the received data. Various embodiments may be included in a network memory architecture to allow for faster data matching and instruction generation in a central appliance.

Claims

1. A method for pre-fetching stored data from a slower memory, the method comprising:

receiving data from a network at a first digital device, the first digital device comprising at least one slower memory and at least one faster memory, wherein the at least one slower memory comprises a hard disk and the at least one faster memory comprises random access memory, the first digital device in communication with a second digital device over a communication network;

pre-scanning the received data to generate a set of fingerprints;

identifying stored fingerprints similar to the set of fingerprints;

determining that the received data is not stored in the at least one faster memory;

comparing the set of fingerprints with the stored fingerprints in the at least one slower memory to identify a fingerprint match;

copying stored data associated with the set of fingerprints from the at least one slower memory into the at least one faster memory; and

retrieving the stored data associated with the identified stored fingerprints according to a prioritization algorithm.

2. The method of claim 1, wherein the prioritization algorithm comprises counting the number of matching fingerprints associated with each block of stored data and retrieving the block with the highest number of matching fingerprints.

3. The method of claim 1, wherein the data associated with the set of fingerprints comprises a block of bytes which includes data patterns that match the set of fingerprints.

4. The method of claim 1, further comprising determining whether the received data represented by the set of fingerprints is similar to positioned data in the at least one faster memory.

5. The method of claim 1, wherein the at least one faster memory is associated with a network memory appliance.

6. The method of claim 1, wherein the set of fingerprints comprises a hash value.

7. The method of claim 1, wherein the stored data corresponds to other stored data in the at least one slower memory in the second digital device.

8. The method of claim 1, further comprising:

determining whether the received data represented by the set of fingerprints is in the at least one slower memory of the second digital device; and

transmitting at least a portion of the received data to the second digital device.

9. A system for pre-fetching stored data from a slower memory, the system comprising:

a scan module configured to pre-scan received data at a first digital device to generate a set of fingerprints the received data being received from a network;

a second digital device in communication with the first digital device over the network;

a search module configured to identify at least one stored fingerprint identical to the set of fingerprints the at least one stored fingerprint corresponding to stored data in the slower memory, the slower memory comprising a hard disk;

a priority module configured to retrieve the stored data associated with the set of fingerprints according to a prioritization algorithm; and

a duplication module configured to copy the stored data corresponding to the set of fingerprints from the slower memory into a faster memory, the faster memory comprising random access memory.

10. The system of claim 9, further comprising:

a slip search module configured to compare a first data byte in the received data with a first memory byte within the faster memory, determine a mismatch between the first data byte and the first memory byte, access a memory location containing a second memory byte that is non-consecutive with the first memory byte to determine a second data byte that matches the second memory byte, and send instructions to a second device to reconstruct the received data.

11. The system of claim 9, wherein the prioritization algorithm comprises counting the number of matching fingerprints associated with each block of stored data and retrieving the block with the highest number of matching fingerprints.

12. The system of claim 9, wherein the data associated with the set of fingerprints comprises a block of bytes which includes data patterns that match the set of fingerprints.

13. The system of claim 9, further comprising a comparison module configured to determine whether the received data represented by the set of fingerprints is similar to positioned data in the faster memory.

14. The system of claim 9, wherein the faster memory is associated with a network memory appliance.

15. The system of claim 9, wherein the set of fingerprints comprises a hash value.

16. The system of claim 9, wherein the stored data corresponds to other stored data in the slower memory in the second digital device.

17. The system of claim 9, further comprising a comparison module, wherein the comparison module is configured to determine whether the received data represented by the set of fingerprints is in the slower memory of the second digital device and transmit at least a portion of the received data to the second digital device.

18. A non-transitory computer readable medium having embodied thereon a program, the program being executable by a processor for performing a method for pre-fetching stored data from a slower memory into a faster memory, wherein the slower memory comprises a hard disk and the faster memory comprises random access memory, a first digital device in communication with a second digital device over a communication network, the method comprising:

receiving data from a network at the first digital device, the first digital device comprising at least one slower memory and at least one faster memory;

pre-scanning the received data to generate a set of fingerprints;

determining that the received data is not stored in the at least one faster memory;

comparing the set of fingerprints with a plurality of stored fingerprints in the slower memory to identify a fingerprint match;

copying stored data associated with the set of fingerprints from the slower memory into the faster memory; and

retrieving the stored data associated with the set of fingerprints according to a prioritization algorithm.

19. The non-transitory computer readable medium of claim 18, wherein the prioritization algorithm comprises counting the number of matching fingerprints associated with each block of stored data and retrieving the block with the highest number of matching fingerprints.

20. The method of claim 18, wherein the data associated with the set of fingerprints comprises a block of bytes which includes data patterns that match the set of fingerprints.

21. The non-transitory computer readable medium of claim 18, wherein the method further comprises determining whether the received data represented by the set of fingerprints is similar to positioned data in the faster memory.

22. The non-transitory computer readable medium of claim 18, wherein the faster memory is associated with a network memory appliance.

23. The non-transitory computer readable medium of claim 18, wherein the set of fingerprints comprises a hash value.

24. The non-transitory computer readable medium of claim 18, wherein the stored data corresponds to other stored data in a slower memory in the second digital device.

25. The non-transitory computer readable medium of claim 18, wherein the method further comprises:

determining whether the received data represented by the set of fingerprints is in the slower memory; and

transmitting at least a portion of the received data to the second digital device.