Data processing apparatus and method of processing data

• US 8,099,573 B2
• Filed: 10/22/2008
• Issued: 01/17/2012
• Est. Priority Date: 10/25/2007
• 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: Camble, Peter Thomas, Trezise, Gregory, Lillibridge, Mark David, Eshghi, Kave, Deolalikar, Vinay
• Primary Examiner(s): Rutz, Jared
• Assistant Examiner(s): Bertram, Ryan
• Application Number:
  US12/256,329
• Publication Number:
  US 20090113167A1
• Time in Patent Office: 1,182 Days
• Field of Search: 711/154, 711161-162, 711/170
• US Class Current: 711/162
• CPC Class Codes: G06F 11/1451 by selection of backup contents

Abstract

Data processing apparatus comprising: a chunk store containing specimen data chunks, a manifest store containing at least one manifest that represents at least a part of a data set and that comprises at least one reference to at least one of said specimen data chunks, a sparse chunk index containing information on only those specimen data chunks having a predetermined characteristic, the processing apparatus being operable to process input data into input data chunks and to use the sparse chunk index to identify at least one of said at least one manifest that includes at least one reference to one of said specimen data chunks that corresponds to one of said input data chunks having the predetermined characteristic.

Claims

1. A data processing apparatus comprising:

a chunk store configured for containing specimen data chunks,

a manifest store configured for containing at least one manifest that represents at least a part of a data set and that comprises at least one reference to at least one of said specimen data chunks,

a sparse chunk index configured for containing information on only those specimen data chunks having a predetermined characteristic, wherein said information of said sparse chunk index refers to at least one manifest in the manifest store comprising a reference to at least one of said specimen data chunks having said predetermined characteristic,

at least one processor to;

process input data into input data chunks, and use the sparse chunk index to identify at least one of said at least one manifest that includes at least one reference to one of said specimen data chunks that corresponds to one of said input data chunks having the predetermined characteristic.

2. The data processing apparatus according to claim 1, wherein a specimen data chunk possesses said predetermined characteristic when that specimen data chunk'"'"'s chunk identifier possesses said predetermined characteristic.

3. The data processing apparatus according to claim 2, wherein the chunk identifier is a hash.

4. The data processing apparatus according to claim 3, wherein a hash possesses said predetermined characteristic when at least M bits of that hash have a predetermined value.

5. The data processing apparatus according to claim 1, wherein the at least one processor is to further analyze said identified at least one manifest and identify at least one reference to one of said specimen data chunks that corresponds to at least one other input data chunk of the input data set.

6. The data processing apparatus according to claim 1, operable to store a particular input data chunk in the chunk store as a particular specimen data chunk, should it be determined that a specimen data chunk corresponding to the particular input data chunk does not exist in the chunk store.

7. The data processing apparatus according to claim 6, wherein the at least the processor is to populate the sparse chunk index with information on said particular specimen data chunk if said particular specimen data chunk has said predetermined characteristic.

8. The data processing apparatus according to claim 1, wherein said information contained in said sparse chunk index includes a chunk identifier of at least one of said specimen data chunks having said predetermined characteristic.

9. The data processing apparatus according to claim 1, wherein at least one of the at least one manifest in the manifest store further comprises a chunk identifier of each specimen data chunk referenced by that manifest.

10. The data processing apparatus according to claim 9, wherein the at least one processor is to generate and compare a chunk identifier of another input data chunk with the chunk identifiers in said manifest, and to identify at least one reference to one of said specimen data chunks that corresponds to said other input data chunk of the input data set.

11. A data processing apparatus comprising:

a chunk store configured for containing specimen data chunks,

a manifest store configured for containing at least one manifest that represents at least a part of a data set and that comprises at least one reference to at least one of said specimen data chunks,

a sparse chunk index configured for containing information on only some specimen data chunks having a predetermined characteristic,

at least one processor to;

process input data into input data chunks;

identify candidate data chunks from the input data chunks, where the candidate data chunks have the predetermined characteristic;

select less than all of candidate data chunks according to at least one selection criterion to populate the sparse chunk index with information relating to the selected candidate data chunks, where the at least one selection criterion selects a particular one of the candidate data chunks to populate the sparse chunk index based on a position of the particular candidate data chunk to another one of the candidate data chunks that has been selected to populate the sparse chunk index; and

use the sparse chunk index to identify at least one manifest that includes at least one reference to one of said specimen data chunks corresponding to an input data chunk having the predetermined characteristic.

12. A data processing apparatus comprising:

a chunk store configured for containing specimen data chunks,

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

at least one processor to;

process input data into input data chunks;

identify at least one candidate data chunk from the input data chunks having a predetermined characteristic; and

select at least one candidate data chunk according to at least one selection criterion to populate the sparse chunk index with information relating to at least one of the specimen data chunks corresponding to the selected at least one candidate data chunk, wherein the selection criterion is that there are at least a predetermined number of input data chunks between selected candidate data chunks.

13. The data processing apparatus according to claim 12, wherein the sparse chunk index is configured for containing information on only said at least one candidate data chunk.

14. The data processing apparatus according to claim 12, wherein the at least one processor is to select a candidate data chunk, according to the at least one selection criteria, based, at least in part, on the position in the input data of a previously selected candidate data chunk.

15. A data processing apparatus comprising:

a chunk store configured for containing specimen data chunks,

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

at least one processor to;

process input data into input data chunks;

identify at least one candidate data chunk from the input data chunks having a predetermined characteristic; and

select at least one candidate data chunk according to at least one selection criterion to populate the sparse chunk index with information relating to at least one of the specimen data chunks corresponding to the selected at least one candidate data chunk, wherein the selection criterion is that there are no more than a predetermined number of input data chunks between selected candidate data chunks.

16. A method of processing data comprising:

providing a chunk store containing specimen data chunks;

providing a manifest store containing at least one manifest that represents at least a part of a data set and that comprises at least one reference to at least one of said specimen data chunks;

providing a sparse chunk index containing information on only those specimen data chunks having a chunk identifier having a predetermined characteristic, wherein said information contained in said sparse chunk index refers to at least one manifest in the manifest store comprising a reference to at least one of said specimen data chunks having said predetermined characteristic;

processing input data into input data chunks; and

using the sparse chunk index to identify at least one manifest in the manifest store that includes at least one reference to a said specimen data chunk corresponding to at least one of said input data chunks having a chunk identifier having the predetermined characteristic.

17. The method of processing data according to claim 16, further comprising:

analyzing said identified at least one manifest and identifying at least one reference to a said specimen data chunk corresponding to at least one further input data chunk.

18. A method of processing data comprising:

providing a chunk store configured for containing specimen data chunks;

providing a sparse chunk index, configured for containing information on only some specimen data chunks;

processing input data into input data chunks;

generating a chunk identifier for each input data chunk;

identifying at least one candidate data chunk from the input data chunks having a chunk identifier having a predetermined characteristic; and

selecting at least one candidate data chunk according to at least one selection criterion to populate the sparse chunk index with information relating to a specimen data chunk corresponding to one of the selected at least one candidate data chunk, wherein the selection criterion is selected from the group consisting of;

(1) a selecting criterion specifying that there are at least a first predetermined number of input data chunks between selected candidate data chunks, and (2) a selection criterion specifying that there are no more than a second predetermined number of input data chunks between selected candidate data chunks.