DATA PROCESSING APPARATUS AND METHOD OF PROCESSING DATA

• US 20090112945A1
• Filed: 10/24/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 David, Eshghi, Kave, Trezise, Gregory, Camble, Peter Thomas, Jones, Kevin Lloyd
• Granted Patent: US 8,332,404 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 16/1756 based on delta files

Abstract

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 a data set and each of which 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 processor being operable to: process input data into input data chunks; identify manifests having at least one reference to one of said specimen data chunks that corresponds to one of said input data chunks and on which there is information contained in the sparse chunk index; and prioritize the identified manifests for subsequent operation.

Claims

1. A 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 a data set and each of which 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 manifests having at least one reference to one of said specimen data chunks that corresponds to one of said input data chunks and on which there is information contained in the sparse chunk index; and

prioritize the identified manifests for subsequent operation.

2. The data processing apparatus according to claim 1, operable to prioritize the identified manifests for subsequent operation according to the number of corresponding specimen data chunks upon which there is information contained in the sparse chunk index each references.

3. The data processing apparatus according to claim 2, operable to prioritize the identified manifests in descending order of the number of references each contains to specimen data chunks on which there is information contained in the sparse chunk index and which correspond to input data chunks.

4. The data processing apparatus according to claim 1, wherein the at least one processor is to prioritize the identified manifests according to, at least in part, when each identified manifest was added to the manifest store.

5. The data processing apparatus according to claim 1, wherein for a specimen data chunk, the sparse chunk index contains information of at least one manifest in the manifest store comprising a reference to said specimen data chunk.

6. The data processing apparatus according to claim 5, wherein for a specimen data chunk indexed by the sparse chunk index, the sparse chunk index contains information on only the most recent R manifests added to the manifest store that comprise a reference to said specimen data chunk.

7. The data processing apparatus according to claim 1, wherein said subsequent operation is to identify, in at least one said prioritized manifest, references to specimen data chunks corresponding to input data chunks of the input data set upon which information is not contained in the sparse chunk index.

8. The data processing apparatus according to claim 1, wherein the at least one processor is to re-prioritize the identified manifests during subsequent operation on the identified manifests.

9. The data processing apparatus according to claim 1, wherein the at least one processor is to process each prioritized manifest, in turn, while a predetermined condition of a preceding given manifest has been met.

10. 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 fail to determine that a specimen data chunk corresponding to that input data chunk exists in the chunk store.

11. The data processing apparatus according to claim 1, operable to remove information from the sparse index according to at least one predetermined criterion.

12. The data processing apparatus according to claim 1, operable to remove information from the sparse chunk index according to at least one predetermined criterion.

13. The data processing apparatus according to claim 12, wherein the at least one predetermined criterion is based on when a specimen data chunk to which the information entered in the sparse chunk index relates was added to the chunk store.

14. The data processing apparatus according to claim 12, wherein the at least one predetermined criterion is based on the number of times a specimen data chunk to which information entered in the sparse chunk index relates has corresponded to an input data chunk.

15. A data processing apparatus comprising:

at least one processor to;

prioritize manifests that include at least one reference to a specimen data chunk in a chunk store corresponding to at least one input data chunk that has information about it contained in a sparse chunk index and that belongs to an input data set;

prioritize the identified manifests for subsequent operation according to the number of said corresponding specimen data chunks referenced by each of them.

16. The data processing apparatus according to claim 15, wherein the at least one processor is to re-prioritize the manifests.

17. A data processing apparatus, comprising:

a chunk store containing specimen data chunks;

a manifest store containing manifests, each of which represents at least a part of a data set and comprise 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; and

at least one processor to;

process input data into input data chunks;

identify at least one manifest having at least one reference to one of said specimen data chunks that corresponds to one of said input data chunks and on which there is information contained in the sparse chunk index;

prioritize the identified manifests for subsequent operation; and

subsequently manage the information contained in the sparse chunk index.

18. A method of processing data, comprising:

providing a chunk store containing specimen data chunks;

providing a manifest store containing manifests representing at least a part of a data set, each manifest comprising at least one reference to at least one of said specimen data chunks; and

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

processing input data into input data chunks; and

identifying and prioritising manifests having at least one reference to one of said specimen data chunks that corresponds to one of said input data chunks and on which there is information contained in the sparse chunk index.

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

processing each prioritized manifest, in turn, to identify references to specimen data chunks corresponding to input data chunks of the input data set that do not have information about them contained in the sparse chunk index.

20. A method of data processing, comprising:

identifying manifests which include at least one reference to a specimen data chunk in a chunk store corresponding to at least one input data chunk that has information about it contained in a sparse chunk index and that belongs to an input data set; and

prioritizing the identified manifests for subsequent operation according to the number of corresponding specimen data chunks referenced therein.