Identification of non-sequential data stored in memory

• US 9,152,574 B2
• Filed: 11/19/2014
• Issued: 10/06/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, Yin, Zhigang, Burns, John
• Primary Examiner(s): Alsip, Michael
• Application Number:
  US14/548,195
• Publication Number:
  US 20150074361A1
• Time in Patent Office: 321 Days
• US Class Current: 1/1
• 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 accessed that contains a second memory byte that is non-consecutive with the first memory byte. A packet location accessed 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 a first packet byte within the packet data to a first memory byte within memory data;

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

comparing a second packet byte to a second memory byte, the second packet byte being adjacent to the first matched packet byte and the second memory byte being adjacent to the first matched memory byte;

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

after determining the mismatch between the second packet byte and the second memory byte, accessing a memory location containing a third memory byte, the third memory byte being non-adjacent to any matched memory byte;

accessing a packet location containing a third packet byte, the third packet byte being at least two bytes from the location of the mismatched second packet byte;

determining a match between the third packet byte and the third memory byte;

determining that a search threshold has been met;

generating instructions to reassemble the packet data from the memory data; and

processing the instructions to reassemble the packet data based at least in part on a result of the comparison between the packet bytes and the memory bytes.

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

3. The method of claim 1, wherein the search threshold is based on at least one of a percentage of a memory searched and a total number of memory bytes searched.

4. The method of claim 1, further comprising determining that a match threshold between the matched packet bytes and the memory bytes is met.

5. The method of claim 4, wherein the match threshold is based on at least one of a number of bytes having a match and a percentage of the bytes having a match.

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

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

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

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

10. 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.

11. A system comprising:

a comparison module configured to compare a first packet byte within a packet data to a first memory byte within a memory data, determine a match between the first packet byte and the first memory byte, compare a second packet byte to a second memory byte, the second packet byte being adjacent to the first matched packet byte and the second memory byte being adjacent to the first matched memory byte, determine a mismatch between the second packet byte and the second memory byte, access a memory location containing a third memory byte that is non-adjacent to any matched memory byte after determining the mismatch between the second packet byte and the second memory byte, access a packet location containing a third packet byte, the third packet byte being at least two bytes from the location of the mismatched second packet byte, determine a match between the third packet byte and the third memory byte, and determine that a search threshold has been met; and

a data module that generates instructions to reassemble the packet data from the memory data based at least in part on a result of the comparison between the packet bytes and the memory bytes.

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

13. The system of claim 11, wherein the determination that the search threshold has been met is based on at least one of a percentage of a memory searched and a total number of memory bytes searched.

14. The system of claim 11, wherein the comparison module is further configured to determine that a match threshold between the matched packet bytes and the matched the memory bytes is met.

15. The system of claim 14, wherein the match threshold is based on at least one of a threshold number of bytes having a match and a percentage of the bytes having a match.

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

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

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

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

20. The system of claim 11, 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.

21. 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 a first packet byte within the packet data to a first memory byte within memory data;

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

comparing a second packet byte to a second memory byte, the second packet byte being adjacent to the first matched packet byte and the second memory byte being adjacent to the first matched memory byte;

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

after determining the mismatch between the second packet byte and the second memory byte, accessing a memory location containing a third memory byte, the third memory byte being non-adjacent to any matched memory byte;

accessing a packet location containing a third packet byte, the third packet byte being at least two bytes from the location of the mismatched second packet byte;

determining a match between the third packet byte and the third memory byte;

determining that a search threshold for the memory has been met;

generating instructions to reassemble the packet data from the memory data; and

processing the instructions to reassemble the packet data based at least in part on a result of the comparison between the packet bytes and the memory bytes.

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

23. The non-transitory computer readable medium of claim 21, wherein the search threshold based on at least one of a percentage of a memory searched and a total number of memory bytes searched.

24. The non-transitory computer readable medium of claim 21, further comprising determining that a match threshold between the matched packet bytes and the memory bytes is met.

25. The non-transitory computer readable medium of claim 24, wherein the match threshold is based on at least one of a number of bytes having a match and a percentage of the bytes having a match.

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

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

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

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

30. The non-transitory computer readable medium of claim 21, 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.