Pre-fetching data into a memory

• US 8,225,072 B2
• Filed: 05/20/2011
• Issued: 07/17/2012
• 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:
  US13/112,936
• Publication Number:
  US 20110219181A1
• Time in Patent Office: 424 Days
• Field of Search: 711/213, 711/104, 711/137, 711/216
• US Class Current: 711/213
• 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 copying stored data into a faster memory, the method comprising:

receiving data from a network;

pre-scanning the received data to generate a sample fingerprint;

identifying stored fingerprints similar to the sample fingerprint;

copying stored data associated with the identified stored fingerprints into a faster memory;

comparing first data bytes in the received data with first memory bytes within the faster memory;

determining a mismatch between one of the first data bytes and one of the first memory bytes;

jumping a number of bytes in the faster memory to second memory bytes that are non-consecutive with the first memory bytes;

jumping a number of bytes in the data to second data bytes that are non-consecutive with the first data bytes;

comparing the second data bytes to the second memory bytes; and

generating a patch instruction based on the comparisons.

2. The method of claim 1, further comprising retrieving the stored data associated with the identified stored fingerprints according to a prioritization algorithm.

3. The method of claim 1, wherein the faster memory comprises random access memory and a slower memory comprises a hard disk.

4. The method of claim 1, further comprising determining whether the received data represented by the sample fingerprint is similar to positioned data in the faster memory.

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

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

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

8. The method of claim 7, further comprising:

determining whether the received data represented by the sample fingerprint is in the 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 copying stored data into a faster memory, the system comprising:

a scan module configured to pre-scan received data to generate a sample fingerprint, the received data being received from a network;

a search module configured to identify stored fingerprints similar to the sample fingerprint;

a duplication module configured to copy stored data associated with the identified stored fingerprints into a faster memory; and

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, jump to a memory location containing a second memory byte that is non-consecutive with the first memory byte, jump to a packet location containing a second data byte that is non-consecutive with the first data byte, compare the second data byte to the second memory byte, and generate a patch instruction based at least in part on a result of the comparison between the second packet byte and the second memory byte.

10. The system of claim 9, further comprising a priority module configured to retrieve the stored data associated with the identified stored fingerprints according to a prioritization algorithm.

11. The system of claim 9, wherein the faster memory comprises random access memory and a slower memory comprises a hard disk.

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

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

14. The system of claim 9, wherein the fingerprint comprises a hash value.

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

16. The system of claim 15, wherein the comparison module is configured to determine whether the received data represented by the sample fingerprint is in the slower memory and transmit at least a portion of the received data to the second digital device.

17. A non-transitory computer readable medium having embodied thereon a program, the program being executable by a processor for performing a method for copying stored data into a faster memory, the method comprising:

receiving data from a network;

pre-scanning the received data to generate a sample fingerprint;

identifying stored fingerprints similar to the sample fingerprint;

copying stored data associated with the identified stored fingerprint into a faster memory;

comparing first data bytes in the received data with first memory bytes within the faster memory;

determining a mismatch between one of the first data bytes and one of the first memory bytes;

jumping a number of bytes in the faster memory to second memory bytes that are non-consecutive with the first memory bytes;

jumping a number of bytes in the data to second data bytes that are non-consecutive with the first data bytes;

comparing the second data bytes to the second memory bytes; and

generating a patch instruction based on the comparisons.

18. The computer readable medium of claim 17, wherein the method further comprises retrieving the stored data associated with the identified stored fingerprints according to a prioritization algorithm.

19. The computer readable medium of claim 17, wherein the faster memory comprises random access memory and a slower memory comprises a hard disk.

20. The computer readable medium of claim 17, wherein the method further comprises determining whether the received data represented by the sample fingerprint is similar to positioned data in the faster memory.

21. The computer readable medium of claim 17, wherein the faster memory is associated with a network memory appliance.

22. The computer readable medium of claim 17, wherein the fingerprint comprises a hash value.

23. The computer readable medium of claim 17, wherein the stored data corresponds to other stored data in a slower memory in a second digital device.

24. The computer readable medium of claim 23, wherein the method further comprises:

determining whether the received data represented by the sample fingerprint is in the slower memory; and

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