Manipulating the Actual or Effective Window Size in a Data-Dependant Variable-Length Sub-Block Parser

• US 20120191668A1
• Filed: 01/25/2011
• Published: 07/26/2012
• Est. Priority Date: 01/25/2011
• Status: Active Grant

• Current Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Original Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Inventors: LEPPARD, Andrew
• Granted Patent: US 8,572,042 B2
• Time in Patent Office: Days
• US Class Current: 707/692
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: G06F 16/90 Details of database functions independent of the retrieved data types

Abstract

Example systems and methods concern a sub-block parser that is configured with a variable sized window whose size varies as a function of the actual or expected entropy of data to be parsed by the sub-block parser. Example systems and methods also concern a sub-block parser configured to compress a data sequence to be parsed before parsing the data sequence. One example method facilitates either actually changing the window size or effectively changing the window size by manipulating the data before it is parsed. The example method includes selectively reconfiguring a data set to be parsed by a data-dependent parser based, at least in part, on the entropy level of the data set, selectively reconfiguring the data-dependent parser, based, at least in part, on the entropy level of the data set, and parsing the data set.

Claims

1. A sub-block parser configured with a variable sized window, where the size of the variable sized window varies as a function of the entropy of data to be parsed by the sub-block parser.

28. The sub-block parser of claim 1, where the entropy of the data set is one of, the actual entropy of the data set, and the expected entropy of the data set.

2. A sub-block parser configured to compress a data sequence to be parsed before parsing the data sequence.

3. A method, comprising:

selectively reconfiguring a data set to be parsed by a data-dependent parser based, at least in part, on the entropy level of the data set;

selectively reconfiguring the data-dependent parser, based, at least in part, on the entropy level of the data set; and

parsing the data set.

4. The method of claim 3, where selectively reconfiguring the data-dependent parser comprises:

determining a desired length for a variable-length window employed by the parser, where the desired length is a function of the entropy level of the data set; and

setting the length of the variable-length window to the desired length.

5. The method of claim 4, where the desired length is selected to facilitate the parser parsing the data set into a set of sub-blocks having a geometric distribution of sub-block sizes.

6. The method of claim 3, comprising:

establishing the entropy level for the data set as one of, the expected entropy level of the data set, and the actual entropy of the data set.

7. The method of claim 3, where selectively reconfiguring the data set comprises:

compressing the data set one or more of, before parsing the set of data, and while parsing the set of data.

8. The method of claim 7, where compressing the data set is performed using one or more of, a lossy compression technique, and an irreversible compression technique.

9. The method of claim 3, where selectively reconfiguring the data set occurs upon determining that the entropy level of the data set exceeds a desired threshold.

10. The method of claim 3, where selectively reconfiguring the data set comprises increasing the information density of the data set by one or more of, performing run length coding on the data set, identifying a known common byte sequence in the data set and replacing the known common byte sequence with replacement data in the data set, identifying a known common byte sequence in the data set and removing the known common byte sequence from the data set, performing a Huffman coding on the data set, and performing an arithmetic coding on the data set.

11. The method of claim 3, where selectively reconfiguring the data set comprises:

selectively replacing a patterned sequence in the data set with an iterative sequence.

12. The method of claim 11, where the patterned sequence is one of, a repeated single byte pattern of length N, N being an integer, and a repeated multi-byte pattern occurring at least M times in the data set, M being an integer.

13. The method of claim 11, where the iterative sequence is produced by an iterative sequence function as a deterministic sequence of numbers based on an initial state.

14. The method of claim 13, where the iterative sequence function is seeded by previous data in the data set.

15. The method of claim 13, where the iterative sequence function is seeded by the current state of the parser.

16. The method of claim 15, where the current state of the parser depends, at least in part, on a rolling hash value used by the parser.

17. The method of claim 13, where the iterative sequence function is one or more of, a pseudo-random number generator, a hash function, and an encryption function.

18. The method of claim 3, comprising:

identifying a first portion of the data set that includes a patterned sequence;

identifying a second portion of the data set that does not include a patterned sequence; and

controlling the parser to parse the second portion and to not parse the first portion.

19. The method of claim 18, where the patterned sequence is a repeated single byte pattern of length N, N being an integer.

20. The method of claim 18, where the patterned sequence is a repeated multi-byte pattern occurring at least N times, N being an integer.

21. The method of claim 18, comprising:

storing the first portion in one or more of, a compacted form, and a descriptive form.

22. An apparatus, comprising:

a processor;

a memory;

a set of logics; and

an interface connecting the processor, the memory, and the set of logics,

the set of logics comprising;

a window alteration logic configured to change one or more of, the actual size of a window, and the effective size of the window, the window being used by a data-dependent deduplication parser to identify sub-block boundary locations in a set of data to be deduplicated.

23. The apparatus of claim 22, where the window alteration logic is configured to change the actual size of the window by:

determining a desired length for the window, where the desired length is a function of the entropy level of the data set, and where the desired length is selected to facilitate the parser parsing the data set into a set of sub-blocks having a desired distribution of sub-block sizes; and

setting the window length to the desired length.

24. The apparatus of claim 22, where the window alteration logic is configured to change the effective size of the window by:

increasing the information density of the data set by one or more of, performing run length coding on the data set, identifying a known common byte sequence in the data set and replacing the known common byte sequence with replacement data in the data set, identifying a known common byte sequence in the data set and removing the known common byte sequence from the data set, performing a Huffman coding on the data set, and performing an arithmetic coding on the data set.

25. The apparatus of claim 22, where the window alteration logic is configured to change the effective size of the window by:

selectively replacing a patterned sequence in the data set with an iterative sequence.

26. A computer-readable medium storing computer-executable instructions that when performed by a data deduplication computer control the data deduplication computer to perform a method, the method comprising:

selectively changing an actual window size based on the entropy of data presented to the data deduplication computer; and

selectively changing an effective window size based on the entropy of data presented to the data deduplication computer,

where the data deduplication computer employs a window based approach to identify boundary locations in data presented to the data deduplication computer, and where the window based approach selectively identifies a boundary in the data presented to the data deduplication computer as a function of whether data in a window satisfies a constraint.

27. A sub-block parser configured with a variable sized window, where the size of the variable sized window varies as a function of the expected entropy of data to be parsed by the sub-block parser.