Data processing apparatus and method of processing data

• US 8,332,404 B2
• Filed: 10/24/2008
• Issued: 12/11/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, Jones, Kevin Lloyd, Eshghi, Kave, Deolalikar, Vinay
• Primary Examiner(s): Alam, Hosain
• Assistant Examiner(s): Zhao, Yu
• Application Number:
  US12/257,659
• Publication Number:
  US 20090112945A1
• Time in Patent Office: 1,509 Days
• Field of Search: None
• US Class Current: 707/736
• 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, wherein for a particular specimen data chunk indexed by the sparse chunk index, the sparse chunk index contains information on the most recent predetermined number of manifests added to the manifest store that comprise a reference to said particular specimen data chunk, and wherein the sparse chunk index further contains information for manifests that reference other specimen data chunks; 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 a number of corresponding specimen data chunks upon which there is information contained in the sparse chunk index.

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 the 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 when each of the identified manifests was added to the manifest store.

5. 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 upon which information is not contained in the sparse chunk index.

6. The data processing apparatus according to claim 1, wherein the at least one processor is to re-prioritize a subset of the identified manifests after a particular one of the identified manifests has been used in the subsequent operation, wherein the re-prioritizing considers presence of references to specimen data chunks in each of the subset of identified manifest which are also present in the particular manifest.

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

8. The data processing apparatus according to claim 1, operable to store a particular input data chunk in the chunk store as a specimen data chunk, in response to failing to determine that a specimen data chunk corresponding to the particular input data chunk exists in the chunk store.

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

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

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

18. The data processing apparatus according to claim 1, wherein the sparse chunk index includes groups of manifests for corresponding ones of the some specimen data chunks, wherein the identified manifests correspond to one of the groups.

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

identify manifests in the sparse chunk index, wherein each of the identified manifests includes at least one reference to a specimen data chunk in a chunk store corresponding to at least one input data chunk in an input data set, wherein for a particular specimen data chunk indexed by the sparse chunk index, the sparse chunk index contains information on the most recent predetermined number of manifests added to the manifest store that comprise a reference to said particular specimen data chunk, and wherein the sparse chunk index further contains information for manifests that reference other specimen data chunks;

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

13. The data processing apparatus according to claim 12, wherein the at least one processor is to re-prioritize a subset of the identified manifests after a particular one of the identified manifests has been used in the subsequent operation, wherein the re-prioritizing considers presence of references to specimen data chunks in each of the subset of identified manifest which are also present in the particular manifest, and wherein the subset excludes the particular identified manifest.

19. The data processing apparatus according to claim 12, wherein the sparse chunk index includes groups of manifests for corresponding ones of some specimen data chunks, and wherein the identified manifests correspond to one of the groups.

20. The data processing apparatus according to claim 19, wherein the at least one processor is to further:

compare references in a particular one of the identified manifests to references calculated for input data chunks of the input data set;

based on the comparing, identify ones of the input data chunks that correspond to specimen data chunks already present in the data store; and

to perform deduplication, decide to not store the identified input data chunks as specimen data chunks in the data store.

14. 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 manifests each 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, wherein for a particular specimen data chunk indexed by the sparse chunk index, the sparse chunk index contains information on the most recent predetermined number of manifests added to the manifest store that comprise a reference to said particular specimen data chunk, and wherein the sparse chunk index further contains information for manifests that reference other specimen data chunks;

prioritize the identified manifests for subsequent operation according to a prioritization criterion;

in the subsequent operation, use the prioritized identified manifests in an order according to the prioritizing; and

subsequently manage the information contained in the sparse chunk index.

15. 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 of the manifests 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, wherein for a particular specimen data chunk indexed by the sparse chunk index, the sparse chunk index contains information on the most recent predetermined number of manifests added to the manifest store that comprise a reference to said particular specimen data chunk, and wherein the sparse chunk index further contains information for manifests that reference other specimen data chunks;

processing input data into input data chunks;

identifying 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

prioritizing the identified manifests according to a prioritization criterion.

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

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

21. The method according to claim 15, wherein the sparse chunk index includes groups of manifests for corresponding ones of the some specimen data chunks, wherein the identified manifests correspond to one of the groups.

22. The method according to claim 15, further comprising:

comparing references in a particular one of the identified manifests to references calculated for the input data chunks;

based on the comparing, identifying ones of the input data chunks that correspond to specimen data chunks already present in the data store; and

to perform deduplication, deciding to not store the identified input data chunks as specimen data chunks in the data store.

17. A method of data processing, 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 of the manifests 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;

identifying manifests in the sparse chunk index, wherein each of the identified manifests includes at least one reference to a specimen data chunk in a chunk store corresponding to at least one input data chunk in an input data set, wherein for a particular specimen data chunk indexed by the sparse chunk index, the sparse chunk index contains information on the most recent predetermined number of manifests added to the manifest store that comprise a reference to said particular specimen data chunk, and wherein the sparse chunk index further contains information for manifests that reference other specimen data chunks; and

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

23. The method of claim 17, wherein the sparse chunk index includes groups of manifests for corresponding ones of some specimen data chunks, and wherein the identified manifests correspond to one of the groups.