METHOD AND APPARATUS FOR COMPRESSION AND NETWORK TRANSPORT OF DATA IN SUPPORT OF CONTINUOUS AVAILABILITY OF APPLICATIONS

• US 20110179341A1
• Filed: 01/15/2010
• Published: 07/21/2011
• Est. Priority Date: 01/15/2010
• Status: Active Grant

• Current Assignee: Neverfail
• Original Assignee: Clydesdale Bank PLC (National Australia Bank Limited)
• Inventors: Senf, Wouter, Clarke, Lyndon John, Falls, Patrick Terence
• Granted Patent: US 8,633,838 B2
• Time in Patent Office: Days
• US Class Current: 714/807
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 69/04 Protocols for data compression, e.g. ROHC
• CPC Class Codes: H04L 69/40 for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection management of faults, events, alarms or notifications in data switching networks H04L41/06

Abstract

Methods and apparatus for compressing data for network transport in support of continuous availability of applications are described. One computer-implemented method of compressing data includes receiving a current instance of data in an input buffer. A candidate chunk of data is selected from the input buffer. A signature hash is computed from a signature length range of data within the candidate chunk. A matching dictionary entry having a matching signature hash from a multi-tiered dictionary is identified. The matching dictionary entry prospectively identifies a location of a prior occurrence of a selected range of consecutive symbols including the signature length range of data within at least one of the current instance of data and a prior instance of data in the input buffer. A dedupe processed representation of the instance of data is formed wherein a dedupe item is substituted for the selected range of consecutive symbols if the selected range is verified as recurring. The dedupe item identifies the location of the prior occurrence of the selected range in accordance with the matching dictionary entry.

Claims

1. A computer-implemented method of compressing data, comprising:

a) receiving a current instance of data in an input buffer;

b) selecting a candidate chunk of a representation of the current instance;

c) computing a signature hash from a signature length range of data starting in the candidate chunk;

d) identifying a matching dictionary entry having a matching signature hash from a multi-tiered dictionary, wherein the matching dictionary entry prospectively identifies a location of a prior occurrence of a selected range of consecutive symbols including the signature length range of data within at least one of the representation of the current instance of data and a representation of a prior instance of data in the input buffer; and

e) forming a dedupe processed representation of the instance of data, wherein a dedupe item is substituted for the selected range of consecutive symbols if the selected range is verified as recurring, wherein the dedupe item identifies the location of the prior occurrence of the selected range.

2. The method of claim 1 wherein the dictionary entries are typed to enable varying levels of persistence of entries within the dictionary.

3. The method of claim 1 wherein the dictionary entries are typed to enable varying levels of match verification.

4. The method of claim 1 wherein the dictionary entries are typed to enable persistence based upon proximity to the current instance of data.

5. The method of claim 1 wherein the dictionary entries are typed to enable persistence based upon frequency of recurrence.

6. The method of claim 1 wherein the dictionary entries are typed to enable persistence based upon length of time since initial matched occurrence.

7. The method of claim 1 wherein the verification of recurrence of step e) includes the step of performing a symbol by symbol comparison of the selected range and the prospective prior occurrence of the selected range.

8. The method of claim 1 wherein the selected range of step d) is a longest recurring selected range of consecutive symbols containing the signature length range as determined in accordance with the dictionary.

9. The method of claim 1 wherein the verification of recurrence of step e) includes the step of comparing a chunk hash from the prospective matching dictionary entry with a chunk hash computed from the selected range.

10. The method of claim 9 wherein a location of the selected range is determined by offset to the signature length range of data, wherein the offset is a same offset identified in the matching dictionary entry for the matching signature hash and associated prospective prior occurrence.

11. The method of claim 9 wherein each chunk hash is a cyclic redundancy check.

12. The method of claim 1 further comprising:

f) updating the dictionary wherein a type of the matching dictionary entry is modified to increase a likelihood of persistence of a dictionary entry having that matching signature hash.

13. The method of claim 1 further comprising:

f) updating the matching dictionary entry to increase the likelihood of persistence of a dictionary entry having the matching signature hash within the dictionary, wherein the matching dictionary entry is updated to change the location associated with the prior occurrence to the location of the selected range.

14. The method of claim 1 further comprising:

f) performing a deflate compression on at least a portion of the data resulting from step e).

15. The method of claim 14 wherein deflate compression comprises:

i) performing a sliding window compression wherein a recurrence of a pattern within the window is replaced with a length-distance pair identifying a prior occurrence of the pattern within the sliding window; and

ii) performing entropy encoding on the sliding window compressed deflate view range to form a deflate processed representation of the dedupe processed representation of the instance of data within the input buffer.

16. The method of claim 1 wherein the dictionary includes only signature hashes having a pre-determined property such that the set of signature hashes permitted in the dictionary is a proper subset of the set of possible signature hashes for a signature length of data.

17. The method of claim 1 wherein the dictionary includes only signatures having the property that mod(signature hash, signature marker) equals a pre-determined value, wherein signature marker is a pre-determined value.

18. The method of claim 1 wherein the dictionary provides a single signature hash per dictionary entry.

19. The method of claim 1 wherein the dictionary provides for a plurality of signature hashes per associated dictionary entry.

20. The method of claim 1 wherein the dictionary provides a signature count number of signature hash and offset pairs for dictionary entries, wherein each signature hash for a given dictionary entry is associated with a unique remainder as determined from mod(signature hash, signature count).

21. A computer-implemented method of compressing data, comprising:

a) receiving a current instance of data in an input buffer; and

b) receiving at least one dedupe exclude range defining a portion of the input buffer to be excluded from dedupe compression, wherein the dedupe exclude range logically partitions the input buffer into at least one dedupe view range, wherein dedupe compression is a substitution of a dedupe item for occurrences of a recurring range of data, wherein the dedupe item identifies the location of a prior occurrence of the recurring range within at least one of a representation of the current instance of data and a representation of a prior instance of data in the input buffer.

22. The method of claim 21 further comprising:

c) performing the following steps for each selected dedupe view range eligible for dedupe compression;

i) performing a repeat pattern recognition (RPR) compression on the selected dedupe view range to store a corresponding RPR processed range at a next available position in a reference log; and

ii) performing a dedupe compression on each RPR processed range to store a corresponding dedupe processed range at a next available position in a temporary buffer.

23. The method of claim 21 further comprising:

c) storing the selected dedupe view range as a NODEDUPE item at a next available position of a temporary buffer for each selected dedupe view range ineligible for dedupe compression.

24. The method of claim 22 wherein c)(ii) comprises substituting a dedupe item for at least one selected recurring range of the RPR processed range, wherein the dedupe item identifies an offset to a prior occurrence of the selected recurring range.

25. The method of claim 22 wherein the RPR compression substitutes an RPR item for a consecutive range of symbols within the selected dedupe view range, wherein the value of the RPR item is independent of the location of any prior occurrence of the consecutive range of symbols within the selected dedupe view range or any previously selected dedupe view range.

26. The method of claim 22 wherein if the consecutive range of symbols comprises a number of adjacent recurrences of a pattern, the RPR item identifies the pattern and number of recurrences of the pattern.

27. A computer-implemented method of compressing data, comprising:

a) receiving a current instance of data in an input buffer;

b) performing a repeat pattern replacement (RPR) compression on at least a portion of the current instance of data to store a corresponding RPR processed range at a next available position in a reference log, wherein the RPR compression substitutes an RPR item for a consecutive range of symbols, wherein the value of the RPR item is independent of the location of the consecutive range of symbols; and

c) performing a dedupe compression on each RPR processed portion to store a corresponding dedupe processed range at a next available position in a temporary buffer, wherein a dedupe item is substituted for a selected range of consecutive symbols of the RPR processed range if the selected range is verified as recurring, wherein the dedupe item identifies an offset to the location of the prior occurrence of the selected range in a same RPR processed range or a prior RPR processed range from one of the current instance and a prior instance of data in the input buffer.

28. The method of claim 27 wherein at least one offset identifies a prior occurrence of the selected range from the prior instance of data in the input buffer.

29. The method of claim 27 wherein at least one offset identifies a prior occurrence selected range in the current instance of data in the input buffer.

30. The method of claim 27 further comprising:

d) processing deflate compression on the dedupe processed range.

31. The method of claim 27 further comprising:

d) locating any deflate exclude range defining a portion of the temporary buffer to be excluded from deflate compression, wherein the deflate exclude range logically partitions the temporary buffer into at least one deflate view range; and

e) processing each deflate view range for deflate compression, wherein each deflate view range eligible for deflation is deflated to store an associated DEFLATE item in an output buffer, wherein each deflate view range ineligible for deflation is stored as a NODEFLATE item in the output buffer.

32. The method of claim 27 wherein step b) further comprises identifying any deflate exclude range boundaries within the input buffer, wherein RPR compression is performed only on portions of the input buffer that are not within the deflate exclude range boundaries.

33. The method of claim 27 wherein the RPR compression replaces a number of adjacent consecutive occurrences of a symbol pattern with a RPR item identifying the symbol pattern and a number of occurrences.

34. The method of claim 27 wherein the RPR compression replaces any occurrences of a predefined list of symbol patterns with an RPR item.