Constrained backup image defragmentation optimization within deduplication system

Patent metadata

Field	Value
Publication number	US-9928210-B1
Application number	US-201213459987-A
Country	US
Kind code	B1
Filing date	Apr 30, 2012
Priority date	Apr 30, 2012
Publication date	Mar 27, 2018
Grant date	Mar 27, 2018

Abstract

The present disclosure provides for defragmenting deduplicated data, such as one or more backup image files, stored in a deduplicated data store. A defragmentation module can be implemented on a deduplication server to reduce fragmentation of backup images and improve processing time for restoring a backup image. A defragmentation module can be configured to defragment a backup image file by migrating portions of data of the backup image file that are stored in various containers at non-contiguous locations throughout deduplicated data store. A defragmentation module can contiguously write the portions to one or more containers, which are stored at one or more new locations in the deduplicated data store. A defragmentation module can be configured to evaluate whether portions of a backup image file meet criteria for defragmentation. A defragmentation module can also be configured to update location information about the portions that are migrated to the new container(s).

First claim

What is claimed is:

1. A method comprising:
determining whether a chunk of deduplicated file data needs to be defragmented, wherein the chunk comprises a plurality of segments,
the plurality of segments are stored in a first plurality of containers,
the first plurality of containers comprises a first number of containers,
the determining is based, at least in part, on the first number of containers a second number of containers, and a first total number of the plurality of segments,
the determining comprises calculating a ratio of the first total number of the plurality of segments to the second number of containers, and
the ratio is associated with the chunk; and

in response to a determination that the chunk needs to be defragmented, migrating the plurality of segments from the first plurality of containers to a second plurality of containers, wherein
the second plurality of containers comprises no more than the second number of containers, and
the second number of containers is less than the first number of containers.

2. The method of claim 1 , wherein the migrating comprises:
reading the plurality of segments from the first plurality of containers; and
contiguously writing the plurality of segments into the second plurality of containers.

3. The method of claim 2 , wherein
a first portion of segments of the plurality of segments are presently stored in the first plurality of containers,
the first portion of segments are contiguously written into a first container of the second plurality of containers, and
the first container is located in cache memory.

4. The method of claim 3 , further comprising:
writing the first container to data storage; and
deleting the first portion of segments from the first plurality of containers.

5. The method of claim 1 , further comprising:
updating metadata about the plurality of segments, wherein

a location associated with each segment of the plurality of segments is updated to include an identification of one of the second plurality of containers.

6. The method of claim 1 , further comprising:
determining that the ratio falls below a threshold value, wherein the ratio indicates that the chunk needs to be defragmented.

7. A computer program product comprising:
a non-transitory computer readable medium storing program instructions executable by a processor, wherein the program instructions are configured to
make a determination whether a chunk of deduplicated file data needs to be defragmented, wherein
the chunk comprises a plurality of segments, the plurality of segments are stored in a first plurality of containers,
the first plurality of containers comprises a first number of containers,
the determination is based, at least in part, on the first number of containers, a second number of containers, and a first total number of the plurality of segments,
the determining comprises calculating a ratio of the first total number of the plurality of segments to the second number of containers, and
the ratio is associated with the chunk; and

in response to a determination that the chunk needs to be defragmented, migrate the plurality of segments from the first plurality of containers to a second plurality of containers, wherein
the second plurality of containers comprises no more than the second number of containers, and
the second number of containers is less than the first number of containers.

8. The computer program product of claim 7 , wherein
the program instructions are further configured to
read the plurality of segments from the first plurality of containers, and
contiguously write the plurality of segments into the second plurality of containers.

9. The computer program product of claim 8 , wherein
a first portion of segments of the plurality of segments are presently stored in the first plurality of containers,
the first portion of segments are contiguously written into a first container of the second plurality of containers, and
the first container is located in cache memory.

10. The computer program product of claim 9 , wherein
the program instructions are further configured to
write the first container to data storage, and
delete the first portion of segments from the first plurality of containers.

11. The computer program product of claim 7 , wherein
the program instructions are further configured to update metadata about the plurality of segments, wherein
a location associated with each segment of the plurality of segments is updated to include an identification of one of the second plurality of containers.

12. The computer program product of claim 7 , wherein the program instructions are further configured to
determine that the ratio falls below a threshold value, wherein
the ratio indicates that the chunk needs to be defragmented.

13. A system comprising:
a defragmentation module, wherein
the defragmentation module is implemented on a server,
the defragmentation module is communicatively coupled to a data store, and
the defragmentation module is configured to make a determination whether a chunk of deduplicated file data needs to be defragmented, wherein
the chunk is stored in the data store,
the chunk comprises a plurality of segments,
the plurality of segments are stored in a first plurality of containers,
the first plurality of containers comprises a first number of containers,
the determination is based, at least in part, on the first number of containers, a second number of containers, and a first total number of the plurality of segments,
the determining comprises calculating a ratio of the first total number of the plurality of segments to the second number of containers, and
the ratio is associated with the chunk; and

in response to a determination that the chunk needs to be defragmented, migrate the plurality of segments from the first plurality of containers to a second plurality of containers, wherein
the second plurality of containers comprises no more than the second number of containers, and
the second number of containers is less than the first number of containers.

14. The system of claim 13 , wherein
the defragmentation module is further configured to
read the plurality of segments from the first plurality of containers, and
contiguously write the plurality of segments into the second plurality of containers.

15. The system of claim 14 , wherein
a first portion of segments of the plurality of segments are presently stored in the first plurality of containers,
the first portion of segments are contiguously written into a first container of the second plurality of containers, and
the first container is located in cache memory.

16. The system of claim 13 , wherein
the defragmentation module is communicatively coupled to a metadata store, and
the defragmentation module is further configured to
update metadata about the plurality of segments, wherein
the metadata is stored in the metadata store,
a location associated with each segment of the plurality of segments is updated to include an identification of one of the second plurality of containers.

17. An apparatus comprising:
an analysis module configured to
make a determination whether a chunk of file data needs to be defragmented, wherein the chunk comprises a plurality of segments,
the plurality of segments are stored in a first plurality of containers,
the first plurality of containers comprises a first number of containers,
the determination is based, at least in part, on the first number of containers, a second number

Assignees

• Zhang Xianbo
• Potvien Benjamin
• Hartnett Thomas
• Wu Weibao
• Parlikar Satyajit Gorhe
• Veritas Technologies Llc

Inventors

• Zhang Xianbo
• Potvien Benjamin
• Hartnett Thomas
• Wu Weibao
• Parlikar Satyajit Gorhe

Classifications

• G06F15/8084 Primary

  Special arrangements thereof, e.g. mask or switch · CPC title

• G06F16/1724 Primary

  Details of de-fragmentation performed by the file system (saving storage space on storage systems G06F3/0608; management of blocks in storage devices G06F3/064) · CPC title