STORING CHUNKS IN CONTAINERS

• US 20100223441A1
• Filed: 05/11/2010
• Published: 09/02/2010
• 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: Trezise, Gregory, Camble, Peter Thomas, Bhagwat, Deepavali Mahendra, LILLIBRIDGE, MARK DAVID
• Granted Patent: US 8,782,368 B2
• Time in Patent Office: Days
• US Class Current: 711/165
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0646 Horizontal data movement in storage systems, i.e. moving data in between storage devices or systems
• CPC Class Codes: G06F 3/0671 In-line storage system

Abstract

Chunks are stored in a container of a data store, where the chunks are produced by dividing input data as part of a deduplication process. In response to determining that the size of the container has reached a predefined size threshold, at least one of the chunks in the container is moved to another container.

Claims

1. A method comprising:

storing, in a system having a processor, chunks in a first container of a data store, wherein the chunks are produced by dividing input data as part of a deduplication process,

determining, by the system, whether a size of the first container has reached a predefined size threshold; and

in response to determining that the size of the first container has reached the predefined size threshold, moving at least one of the chunks in the first container to a second container.

2. The method of claim 1, wherein moving the at least one of the chunks in the first container to the second container comprises:

splitting, by the system, the first container into plural containers, wherein the second container is one of the plural containers.

3. The method of claim 2, wherein splitting comprises:

distributing the chunks of the first container among the plural containers.

4. The method of claim 2, further comprising:

tracking a number of times the first container has been part of a split,

wherein a number of the plural containers split from the first container depends on the tracked number of times.

5. The method of claim 1, wherein the system has plural containers including the first and second containers, the method further comprising:

receiving the input data;

dividing the input data into chunks; and

storing the input data chunks in the plural containers based on identifying respective neighboring chunks already in the plural containers.

6. The method of claim 1, further comprising:

maintaining neighbor information for at least one of the chunks in the first container, wherein the neighbor information identifies which of the chunks are known to be neighbors of others of the chunks.

7. The method of claim 6, wherein moving the at least one of the chunks in the first container to the second container takes into account the neighbor information.

8. The method of claim 6, wherein the neighbor information further indicates, for a given pair of neighbors, which of the neighbors in the pair is on the left side.

9. The method of claim 1, wherein moving the at least one chunk is performed as part of a housekeeping procedure that removes garbage chunks associated with deleted data.

10. The method of claim 1, wherein moving the at least one of the chunks in the first container to the second container comprises:

redistributing chunks of a plurality of containers including the first container and the second container, wherein after the redistributing, each of the plurality of containers has a respective size below a second predefined size threshold.

11. The method of claim 10, further comprising reordering the chunks in the plurality of containers according to neighbor information.

12. The method of claim 1, wherein the data store further includes a third container and a fourth container storing corresponding chunks, the method further comprising:

merging the third and fourth containers into a resulting container; and

splitting the resulting container into plural containers.

13. A computer system comprising:

a storage media to store a data store having containers of chunks; and

at least one processor to;

receive input data;

divide the input data into chunks as part of a deduplication process;

determine which of the input data chunks correspond to chunks already present in the data store, and which of the input data chunks are new;

in response to identifying a new input data chunk, store the new input data chunk into one of the containers according to a neighbor condition; and

in response to determining that a size of a particular one of the containers has reached a predefined size threshold, moving at least one chunk from the particular container to another container.

14. The computer system of claim 13, wherein the at least one processor is to further:

rewrite a given one of the containers to remove garbage chunks from the given container;

determine whether a size of the given container is smaller than a second predefined size threshold; and

in response to determining that the size of the given container is smaller than the second predefined size threshold, merge the given container with another container.

15. The computer system of claim 13, wherein moving of the at least one chunk from the particular container to the another container is performed by splitting the particular container into plural containers, wherein the another container is one of the plural containers.

16. The computer system of claim 13, wherein the at least one processor is to further:

maintain neighbor information for at least one of the chunks in the particular container, wherein the neighbor information identifies which of the chunks are known to be neighbors of others of the chunks.

17. The computer system of claim 16, wherein moving of the at least one chunk in the particular container to the another container takes into account the neighbor information.

18. The computer system of claim 13, wherein moving of the at least one chunk from the particular container to the another container is performed by redistributing chunks of a plurality of containers including the particular container and the another container, wherein after the redistributing, each of the plurality of containers has a respective size below a second predefined size threshold.

19. An article comprising at least one computer-readable storage medium storing instructions that upon execution cause a computer system to:

store chunks in a first container of a data store, wherein the chunks are produced by dividing input data as part of a deduplication process,

determine whether a size of the first container has reached a predefined size threshold; and

in response to determining that the size of the first container has reached the predefined size threshold, move at least one of the chunks in the first container to a second container.

20. The article of claim 19, wherein the data store has plural containers, and wherein the instructions upon execution cause the computer system to further:

receive the input data;

divide the input data into chunks;

determine which of the input data chunks correspond to chunks already present in the data store, and which of the input data chunks are new;

in response to identifying a new input data chunk, store the new input data chunk into one of the plural containers according to a neighbor condition.