Storing chunks in containers

• US 8,782,368 B2
• Filed: 05/11/2010
• Issued: 07/15/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: Lillibridge, Mark David, Bhagwat, Deepavali Mahendra, Camble, Peter Thomas, Trezise, Gregory
• Primary Examiner(s): PATEL, KAUSHIKKUMAR M
• Application Number:
  US12/777,478
• Publication Number:
  US 20100223441A1
• Time in Patent Office: 1,526 Days
• Field of Search: 711/165, 711/170, 711/154, 711/161, 711/162, 711/E12.001, 711/E12.002, 711/E12.009
• 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, 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.

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 the splitting comprises:

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

4. The method of claim 1, wherein the system has multiple 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 multiple containers based on identifying respective neighboring chunks already in the multiple containers.

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

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

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

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

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

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, 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; and

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.

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

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; and

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, wherein the neighbor information further indicates, for a given pair of neighbors, which of the neighbors in the pair is on the left side.

11. 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, wherein moving the at least one chunk is performed as part of a housekeeping procedure that removes garbage chunks associated with deleted data.

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

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;

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.

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

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

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

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

17. 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, wherein the data store further includes a third container and a fourth container storing corresponding chunks;

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

split the resulting container into plural containers.

18. The article of claim 17, wherein the data store has multiple 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 multiple containers according to a neighbor condition, where the neighbor condition specifies that the new input data chunk is to be stored into a container containing another data chunk that is a neighbor of the new input data chunk.