DATA PROCESSING APPARATUS AND METHOD OF PROCESSING DATA

• US 20110040763A1
• Filed: 04/25/2008
• Published: 02/17/2011
• Est. Priority Date: 04/25/2008
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Deolalikar, Vinay, Lillibridge, Mark
• Granted Patent: US 8,959,089 B2
• Time in Patent Office: Days
• US Class Current: 707/737
• CPC Class Codes: G06F 11/1453 using de-duplication of the data

Abstract

One embodiment is a data processing apparatus that has a chunk store containing specimen data chunks, a manifest store containing a plurality of manifests, each of which represents at least a part of previously processed data and includes at least one reference to at least one of the specimen data chunks, and a sparse chunk index containing information on only some specimen data chunks. Input data is processed into a plurality of input data segments. Each manifest of the first set has at least one reference to one of said specimen data chunks that corresponds to one of the input data chunks of a first input data segment. Specimen data chunks corresponding to other input data chunks of the first input data segment are identified by using the identified first set of manifests and at least one manifest identified when processing previous data.

Claims

1. Data processing apparatus comprising:

a chunk store containing specimen data chunks,

a manifest store containing a plurality of manifests, each of which represents at least a part of previously processed data and comprises at least one reference to at least one of said specimen data chunks,

a sparse chunk index containing information on only some specimen data chunks,

the processing apparatus being operable to;

process input data into a plurality of input data segments, each composed of input data chunks;

identify a first set of manifests, where each manifest of the first set has at least one reference to one of said specimen data chunks that corresponds to one of the input data chunks of a first input data segment, and on which there is information contained in the sparse chunk index;

identify specimen data chunks corresponding to other input data chunks of the first input data segment by using the identified first set of manifests and at least one manifest identified when processing previous data.

2. Data processing apparatus according to claim 1, wherein the sparse chunk index contains information on specimen data chunks having a predetermined characteristic.

3. Data processing apparatus according claim 1, operable to compare the input data chunks of the first input data segment with the specimen data chunks referenced by at least one of the identified first set of manifests or the at least one manifest identified when processing previous data, to identify specimen data chunks corresponding to input data chunks of the first input data segment.

4. Data processing apparatus according to claim 1, further comprising a cache, the apparatus being operable to store at least one of said first set of identified manifests in the cache.

5. Data processing apparatus according to claim 1, operable to prioritise the said identified first set of manifests and said at least one manifest identified when processing previous data, wherein the prioritization criteria are based at least in part on the number of references each manifest contains to specimen data chunks corresponding to input data chunks of the first input data segment and on which there is information contained in the sparse chunk index.

6. Data processing apparatus according to claim 1, operable to prioritise the said identified first set of manifests and said at least one manifest identified when processing previous data, wherein the criteria when prioritising the at least one manifest identified when processing previous data, are based at least in part on a prioritisation of the at least one manifest when processing that previous data.

7. Data processing apparatus according to claim 1, operable to prioritise the said identified first set of manifests and said at least one manifest identified when processing previous data, wherein the prioritization criteria are based at least in part on when each manifest was added to the manifest store.

8. Data processing apparatus according to claim 1, operable to prioritise the said identified first set of manifests and said at least one manifest identified when processing previous data, wherein the prioritization criteria are based at least in part on whether each manifest is currently held in the cache.

9. Data processing apparatus according to claim 1, operable to select at least one of the prioritised manifests to identify specimen data chunks corresponding to said other input data chunks of the first input data segment.

10. Data processing apparatus comprising:

a chunk store containing specimen data chunks,

a manifest store containing a plurality of manifests, each of which represents at least a part of previously processed data and comprises at least one reference to at least one of said specimen data chunks,

a sparse chunk index containing information on only some specimen data chunks,

the processing apparatus being operable to;

process input data into a plurality of input data segments, each composed of input data chunks;

identify a first set of manifests, where each manifest of the first set has references to specimen data chunks which correspond to input data chunks of a first input data segment and on which there is information contained in the sparse chunk index;

retrieve manifests having references to specimen data chunks which correspond to at least one input data chunk of previously processed data,

use the identified and retrieved manifests to identify specimen data chunks corresponding to other input data chunks of the first input data segment

11. Data processing apparatus according to claim 10, wherein the at least one input data chunk of previously processed data is a predetermined portion of input data chunks of an input data segment of previously processed data.

12. Data processing apparatus according to claim 11, wherein the input data segment of previously processed data immediately proceeds said first input data segment in the input data.

13. A data processor, operable to:

process input data into input data chunks, the input data chunks being arranged into input data segments;

for a given input data segment, select at least some of the input data chunks of the input data segment having a predetermined characteristic,

compile a list of candidate manifests from a manifest store, the list comprising;

at least one manifest having a reference to a specimen data chunk corresponding to at least one of the selected input data chunks; and

at least one manifest identified in processing at least one other segment of input data; and

prioritise and process the candidate manifests to identify specimen data chunks corresponding to other input data chunks of the input data segment being processed.

14. A method of processing data, using:

a chunk store containing specimen data chunks,

a manifest store containing a plurality of manifests, each of which represents at least a part of previously processed data and comprises at least one reference to at least one of said specimen data chunks; and

a sparse chunk index containing information on only some specimen data chunks,

the method comprising;

processing input data into a plurality of input data segments, each composed of input data chunks;

identifying a first set of manifests, where each manifest of the first set has at least one reference to one of said specimen data chunks that corresponds to one of the input data chunks of a first input data segment and on which there is information contained in the sparse chunk index; and

using the identified first set of manifests and at least one manifest identified when processing previous input data to identify specimen data chunks corresponding to other input data chunks of the first input data segment

15. A method of processing data according to claim 14, comprising:

comparing the input data chunks of the first input data segment with the specimen data chunks referenced by at least one of the identified first set of manifests or at least one manifest identified when processing previous data.