DATA PROCESSING APPARATUS AND METHOD OF PROCESSING DATA

• US 20090113167A1
• Filed: 10/22/2008
• Published: 04/30/2009
• 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: Deolalikar, Vinay, Lillibridge, Mark, Eshghi, Kave, Trezise, Gregory, Camble, Peter Thomas
• Granted Patent: US 8,099,573 B2
• Time in Patent Office: Days
• US Class Current: 711/216
• 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 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,

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 bit value.

5. The data processing apparatus according to claim 1, operable to analyse 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 an input data chunk in the chunk store as a specimen data chunk, should it be determined that a specimen data chunk corresponding to that input data chunk does not exist in the chunk store.

7. The data processing apparatus according to claim 6, operable to populate the sparse chunk index with information on said corresponding specimen data chunk if said 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 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.

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

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

11. The data processing apparatus according to claim 10, operable to generate and compare a chunk identifier of another input data chunk with the chunk identifiers in said manifest, 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.

12. A 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 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;

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 specimen data chunks corresponding to the selected at least one candidate data chunk; 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.

13. 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 chunk index with information relating to at least one of the specimen data chunks corresponding to the selected at least one candidate data chunk.

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

15. The data processing apparatus according to claim 13, 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.

16. The data processing apparatus according to claim 13, wherein a selection criterion is that there are at least a predetermined number of input data chunks between selected candidate data chunks.

17. The data processing apparatus according to claim 13, wherein a selection criterion is that there are no more than a second predetermined number of input data chunks between selected candidate data chunks

18. 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;

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.

19. The method of processing data according to claim 18, further comprising:

analysing 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

20. 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 chunk index with information relating to a specimen data chunk corresponding to one of the selected at least one candidate data chunk.