Identification of data stored in memory

• US 8,738,865 B1
• Filed: 03/22/2012
• Issued: 05/27/2014
• 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, Yin, Zhigang, Burns, John
• Primary Examiner(s): Alsip, Michael
• Application Number:
  US13/427,422
• Time in Patent Office: 796 Days
• Field of Search: 711/154, 707/999.103, 707/999.106
• US Class Current: 711/154
• CPC Class Codes: G06F 12/02 Addressing or allocation; Relocation program address sequencing G06F9/00; arrangements for selecting an address in a digital store G11C8/00
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/121 using replacement algorithms
• CPC Class Codes: G06F 2212/1008 Correctness of operation, e.g. memory ordering
• CPC Class Codes: G06F 2212/6026 Prefetching based on access pattern detection, e.g. stride based prefetch
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99947 Object-oriented database structure reference

Abstract

Systems and methods for identification of data stored in memory are provided. A data packet is received and a first packet byte within the data packet is compared to a first memory byte within a memory. A mismatch is determined between the first packet byte and the first memory byte. A memory location is jumped to that contains a second memory byte that is non-consecutive with the first memory byte. A packet location is jumped to that contains a second packet byte that is non-consecutive with the first packet byte. The second packet byte is compared to the second memory byte. A retrieval instruction is generated based at least in part on a result of the comparison between the second packet byte and the second memory byte. 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 comprising:

receiving packet data;

comparing individually a first packet byte within the packet data to a first memory byte within memory data;

determining a mismatch between the first packet byte and the first memory byte;

after determining the mismatch between the first packet byte and the first memory byte, accessing a memory location containing a second memory byte, the second memory byte being non-consecutive-with the first memory byte;

accessing a packet location containing a second packet byte, the second packet byte being non-consecutive with any other compared packet byte;

comparing the second packet byte to the second memory byte; and

reassembling the packet data from the memory data based at least in part on a result of the comparison between the second packet byte and the second memory byte.

2. The method of claim 1, wherein a number of packet bytes between the first packet byte and the second packet byte is equal to a number of memory bytes between the first memory byte and the second memory byte.

3. The method of claim 1, further comprising comparing the second packet byte to a third memory byte that is consecutive with the second memory byte.

4. The method of claim 1, further comprising generating an insertion command to insert missing packet bytes into the memory data.

5. The method of claim 1, further comprising generating a deletion command to delete memory bytes not matching the packet data.

6. The method of claim 1, further comprising generating an overwrite command to replace memory bytes with packet bytes.

7. The method of claim 1, wherein the memory data is stored in a faster memory in a network memory appliance.

8. The method of claim 1, further comprising:

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

identifying stored fingerprints identical to the sample fingerprint; and

copying the first memory byte associated with the identified stored fingerprints into the memory.

9. The method of claim 1, further comprising:

comparing a final packet byte to a fourth memory byte;

receiving a second packet data comprising an initial second packet byte; and

comparing the initial second packet byte of the second packet data to a fifth memory byte consecutive with the fourth memory byte.

10. A system comprising:

a comparison module configured to compare individually a first packet byte within a packet data to a first memory byte within a memory data, determine a mismatch between the first packet byte and the first memory byte, access a memory location containing a second memory byte that is non-consecutive with the first memory byte after determining the mismatch between the first packet byte and the first memory byte, access a packet location containing a second packet byte that is non-consecutive with any other compared packet byte, and compare the second packet byte to the second memory byte; and

a data module configured to reassemble the packet data from the memory data based at least in part on a result of the comparison between the second packet byte and the second memory byte.

11. The system of claim 10, wherein a number of packet bytes between the first packet byte and the second packet byte is equal to a number of memory bytes between the first memory byte and the second memory byte.

12. The system of claim 10, wherein the comparison module is further configured to compare the second packet byte to a third memory byte that is consecutive with the second memory byte.

13. The system of claim 10, wherein the data module is further configured to generate an insertion command to insert missing packet bytes into the memory data.

14. The system of claim 10, wherein the data module is further configured to generate a deletion command to delete memory bytes not matching the packet data.

15. The system of claim 10, wherein the data module is further configured to generate an overwrite command to replace memory bytes with packet bytes.

16. The system of claim 10, wherein the memory data is stored in a faster memory in a network memory appliance.

17. The system of claim 10, further comprising a prescan module configured to pre-scan the packet data to generate a sample fingerprint, identify stored fingerprints identical to the sample fingerprint, and copy the first memory byte associated with the identified stored fingerprints into the memory.

18. The system of claim 10, wherein the comparison module is further configured to compare a final packet byte to a fourth memory byte, receive a second packet data comprising an initial second packet byte, and compare the initial second packet byte of the second packet data to a fifth memory byte consecutive with the fourth memory byte.

19. A non-transitory computer readable medium having embodied thereon a program, the program being executable by a processor for performing a method for generating a retrieval instruction based on matched data, the method comprising:

receiving packet data;

comparing individually a first packet byte within the packet data to a first memory byte within memory data;

determining a mismatch between the first packet byte and the first memory byte;

after determining the mismatch between the first packet byte and the first memory byte, accessing a memory location containing a second memory byte, the second memory byte being non-consecutive with the first memory byte;

accessing a packet location containing a second packet byte, the second packet byte being non-consecutive with any other compared packet byte;

comparing the second packet byte to the second memory byte; and

reassembling the packet data from the memory data based at least in part on a result of the comparison between the second packet byte and the second memory byte.

20. The non-transitory computer readable medium of claim 19, wherein a number of packet bytes between the first packet byte and the second packet byte is equal to a number of memory bytes between the first memory byte and the second memory byte.

21. The non-transitory computer readable medium of claim 19, wherein the method further comprises comparing the second packet byte to a third memory byte that is consecutive with the second memory byte.

22. The non-transitory computer readable medium of claim 19, wherein the method further comprises generating an insertion command to insert missing packet bytes into the memory data.

23. The non-transitory computer readable medium of claim 19, wherein the method further comprises generating a deletion command to delete memory bytes not matching the packet data.

24. The non-transitory computer readable medium of claim 19, wherein the method further comprises generating an overwrite command to replace memory bytes with packet bytes.

25. The non-transitory computer readable medium of claim 19, wherein the memory data is stored in a faster memory in a network memory appliance.

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

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

identifying stored fingerprints identical to the sample fingerprint; and

copying the first memory byte associated with the identified stored fingerprints into the memory.

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

comparing a final packet byte to a fourth memory byte;

receiving a second packet data comprising an initial second packet byte; and

comparing the initial second packet byte of the second packet data to a fifth memory byte consecutive with the fourth memory byte.