Data processing apparatus and method of processing data

• US 8,838,541 B2
• Filed: 10/25/2007
• Issued: 09/16/2014
• 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 Keith
• Primary Examiner(s): LEWIS, ALICIA M
• Application Number:
  US12/671,334
• Publication Number:
  US 20100198792A1
• Time in Patent Office: 2,518 Days
• Field of Search: None
• US Class Current: 707/640
• CPC Class Codes: G06F 11/1451 by selection of backup contents

Abstract

Data processing apparatus comprising: a chunk store having a plurality of chunk sections, each operable to store specimen data chunks, the apparatus being operable to: process an input data set into one or more input data chunks; identify a specimen data chunk in one of said chunk sections which corresponds to a first input data chunk; identify a second input data chunk not corresponding to a specimen data chunk in the chunk store; and store the second input data chunk as a specimen data chunk in proximity to the identified specimen data chunk corresponding to the first input data chunk.

Claims

1. An apparatus comprising:

a chunk store having a plurality of chunk sections each storing specimen data chunks;

a manifest store for containing a manifest representing at least part of a data set and having references to said chunk sections;

at least one processor configured to;

process an input data set into input data chunks;

identify, using the manifest, a specimen data chunk in a given one of said chunk sections which corresponds to a first of the input data chunks;

identify a second of the input data chunks not corresponding to a specimen data chunk in the chunk store;

store the second input data chunk as a specimen data chunk in deliberate proximity to the identified specimen data chunk, wherein the storing in deliberate proximity results in selecting the given chunk section rather than another of said chunk sections to store the second input data chunk as a specimen data chunk;

associate a specimen data chunk in at least one chunk section with a back-reference to a manifest referencing that specimen data chunk;

determine when a given specimen data chunk is not associated with a back-reference to a manifest;

delete the given specimen data chunk from a particular chunk section after a predetermined time period or number of iterations in response to determining that the given specimen data chunk is not associated with a back-reference to a manifest; and

after the deleting, reduce fragmentation of the particular chunk section by rearranging chunks remaining in the particular chunk section.

2. The apparatus according to claim 1, wherein the at least one processor is configured to store the second input data chunk as a specimen data chunk in physical proximity to the identified specimen data chunk corresponding to the first input data chunk.

3. The apparatus according to claim 1, wherein the at least one processor is configured to store the second input data chunk as a specimen data chunk in the given chunk section such that both the specimen data chunks corresponding to the first and second input data chunks are readable from the chunk store in a single read/write operation.

4. The apparatus according to claim 1, wherein if at least a predetermined number of input data chunks are found not to correspond to specimen data chunks in the chunk store, the at least one processor is configured to store the said input data chunks as specimen data chunks in proximity to one another in at least one chunk section.

5. The apparatus according to claim 4, wherein the said at least one chunk section is at least one chunk section other than the given chunk section containing the identified specimen data chunk.

6. The apparatus according to claim 1, wherein the at least one processor is configured to analyze the input data set;

and store the second input data chunk as a specimen data chunk in deliberate proximity to the identified specimen data chunk corresponding to the first input data chunk, only if the input data set has a predetermined characteristic.

7. The apparatus according to claim 6, wherein the predetermined characteristic is that the input data set is deemed by the apparatus to represent a full back up.

8. The apparatus according to claim 1, wherein at least one chunk section is configured to contain at least one reference to at least one manifest referencing at least one specimen data chunk contained in the at least one chunk section.

9. The apparatus according to claim 1, wherein at least one chunk section is configured to maintain a record of the location of at least one specimen data chunk contained in the at least one chunk section.

10. The apparatus according to claim 1, wherein the at least one processor is configured to:

analyze back-references to manifests referencing a particular specimen data chunk;

move the particular specimen data chunk within the chunk store; and

amend references of the manifests to refer to the moved particular specimen data chunk.

11. The apparatus according to claim 1, wherein the at least one processor is configured to periodically commission a new chunk store for use by the data processing apparatus, and to retire a previous chunk store from use.

12. The apparatus according to claim 1, wherein the manifest store is to store manifests, each of the manifests representing a corresponding input data set and containing references to respective chunk sections in the chunk store,

wherein the at least one processor is configured to:

use a particular one of the manifests to identify the specimen data chunk corresponding to the first input data chunk; and

associate a particular specimen data chunk with back-references to plural ones of the manifests, each of the plural manifests containing a reference to the particular specimen data chunk.

13. The apparatus according to claim 12, wherein the at least one processor is configured to further:

in response to a deletion of one of the plural manifests, remove a corresponding one of the back-references associated with the particular specimen data chunk.

14. The apparatus according to claim 13, wherein the at least one processor is configured to further:

delete the particular specimen data chunk in response to detecting that there are no back-references to manifests associated with the particular specimen data chunk resulting from deletion of each of the plural manifests.

15. A data storage apparatus comprising:

a data storage medium provisioned with a plurality of chunk sections, at least one of said chunk sections storing specimen data chunks;

a read/write head to read information from, or write information to, the data storage medium, the read/write head being configured to read/write a predetermined maximum extent of data in a single operation;

a manifest store to store manifests, each of the manifests representing a corresponding input data set and containing references to respective specimen data chunks or chunk sections;

at least one processor configured to;

divide a particular input data set into input data chunks;

identify a specimen data chunk in one of the chunk sections that corresponds to a first of the input data chunks, where the identifying is based on use of one of the manifests;

store a further one of the input data chunks of the particular input data set as a specimen data chunk in the data storage medium, such that both the specimen data chunks may be accessed by the read/write head in a single operation;

associate a given specimen data chunk with back-references to plural ones of the manifests, each of the plural manifests containing a reference to the given specimen data chunk;

determine when a particular specimen data chunk is not associated with a back-reference to a manifest;

delete the particular specimen data chunk from a particular one of the chunk sections after a predetermined time period or number of iterations; and

after the deleting, reduce fragmentation of the particular chunk section by rearranging chunks remaining in the particular chunk section.

16. The data storage apparatus according to claim 15, wherein the at least one processor is configured to further:

in response to a deletion of one of the plural manifests, remove a corresponding one of the back-references.

17. The data storage apparatus according to claim 16, wherein the at least one processor is configured to further:

delete the given specimen data chunk in response to detecting that there are no back-references to manifests associated with the given specimen data chunk resulting from deletion of each of the plural manifests.

18. A method comprising:

storing a chunk store containing a plurality of chunk sections each storing specimen data chunks;

storing a manifest store that contains manifests, each of the manifests representing a corresponding input data set and containing references to respective specimen data chunks or chunk sections;

processing an input data set into input data chunks;

identifying, using one of the manifests, a specimen data chunk in a given one of the chunk sections which corresponds to a first of the input data chunks;

identifying a second of the input data chunks not corresponding to a specimen data chunk in the chunk store;

storing the second input data chunk as a specimen data chunk in deliberate proximity to the identified specimen data chunk, wherein the storing in deliberate proximity results in selecting the given chunk, section rather than another of the chunk sections to store the second input data chunk as a specimen data chunk;

associating a given specimen data chunk with back-references to plural ones of the manifests, each of the plural manifests containing a reference to the given specimen data chunk;

determining when a particular specimen data chunk is not associated with a back-reference to a manifest;

deleting the particular specimen data chunk from a particular one of the chunk sections after a predetermined time period or number of iterations; and

after the deleting, reducing fragmentation of the particular chunk section by rearranging chunks remaining in the particular chunk section.

19. The method according to claim 18, comprising:

identifying further input data chunks not corresponding to specimen data chunks already in the chunk store; and

storing said further input data chunks as specimen data chunks in at least one chunk section containing at least one specimen data chunk that does correspond to at least one input data chunk of the input data set.

20. The method according to claim 18, further comprising:

in response to a deletion of one of the plural manifests, removing a corresponding one of the back-references associated with the given specimen data chunk.

21. The method according to claim 20, further comprising:

deleting the given specimen data chunk in response to detecting that there are no back-references to manifests associated with the given specimen data chunk resulting from deletion of each of the plural manifests.