METHODS AND SYSTEMS FOR SPACE RECLAMATION IN IMMUTABLE DEDUPLICATION SYSTEMS

1 . A computer-implemented method comprising:

selecting a unit of data of a backup image;

determining whether a duplicate unit of data is stored in an existing data storage construct, wherein the duplicate unit of data is a duplicate of the selected unit of data, and wherein the existing data storage construct is stored in immutable storage;

in response to a determination that the duplicate unit of data exists in the existing data storage construct, determining whether the existing data storage construct is designated as being available to be referenced; and

in response to the existing data storage construct being designated as being unavailable to be referenced, storing the unit of data in a new data storage construct.

2 . The computer-implemented method of claim 1 , further comprising, in response to the existing data storage construct being designated as being unavailable to be referenced, updating a reference to the duplicate unit of data, wherein the backup image comprises the reference.

3 . The computer-implemented method of claim 1 , further comprising, in response to the existing data storage construct being designated as being available to be referenced, updating a reference to the duplicate unit of data.

4 . The computer-implemented method of claim 1 , further comprising performing an update process on the existing data storage construct, wherein the update process includes:

determining a state of the existing data storage construct;

comparing the state of the existing data storage construct and one or more thresholds determined by performing a threshold determination process;

determining whether the state of the existing data storage construct meets the one or more thresholds; and

in response to the state of the existing data storage construct meeting the one or more thresholds, designating the existing data storage construct as being unavailable.

5 . The computer-implemented method of claim 4 , further comprising, in response to the existing data storage construct being designated as being unavailable to be referenced, adding data object metadata to the new data storage construct, wherein the data object metadata is associated with the unit of data.

6 . The computer-implemented method of claim 1 , wherein:

the backup image is one of a plurality of backup images; and

the immutable storage periodically permits deletion of the existing data storage construct.

7 . The computer-implemented method of claim 6 , further comprising deleting the existing data storage construct if none of the plurality of backup images comprise references to the existing data storage construct.

8 . The computer-implemented method of claim 1 , wherein the method further comprises determining one or more thresholds associated with the existing data storage construct.

9 . The computer-implemented method of claim 8 , further comprising:

determining whether the existing data storage construct is designated as being available; and

in response to a determination that the existing data storage construct is designated as being available, performing an update process on the existing data storage construct.

10 . The computer-implemented method of claim 9 , wherein determining the one or more thresholds comprises:

determining a retention period of a new container stored in the immutable storage; and

determining a remaining retention period, wherein the remaining retention period is a portion of a retention period remaining for the existing data storage construct.

11 . The computer-implemented method of claim 10 , further comprising:

calculating the one or more thresholds, wherein the one or more thresholds are calculated based, at least in part, on the retention period and the remaining retention period; and

determining a state of the existing data storage construct, wherein the state of the existing data storage construct is determined based, at least in part, on the size of the existing data storage construct and the amount of expired data.

12 . The computer-implemented method of claim 11 , wherein determining the state of the existing data storage construct comprises:

determining a size of the at least one of the plurality of existing data storage constructs; and

determining an amount of expired data stored in the existing data storage construct.

13 . The computer-implemented method of claim 11 , wherein the state of the existing data storage construct meets the one or more thresholds if:

G/C>R/R NEW

where

C=the size of the existing data storage construct,

G=the amount of expired data stored in the existing data storage construct,

R =the remaining retention period, and

NEW the retention period.

14 . The computer-implemented method of claim 13 , wherein the state of the existing data storage construct meets the one or more thresholds if, for a cost function Cost (an amount of data, an input retention period),

Cost( C, R +Cost(( C−G ), NEW <Cost( C , NEW

where

C=the size of the existing data storage construct,

G=the amount of expired data stored in the existing data storage construct,

R =the remaining retention period, and

NEW the retention period.

15 . A non-transitory computer-readable storage medium, comprising program instructions, which, when executed by one or more processors of a computing system, perform a method comprising:

selecting a unit of data of a backup image;

determining whether a duplicate unit of data is stored in an existing data storage construct, wherein the duplicate unit of data is a duplicate of the selected unit of data, and wherein the existing data storage construct is stored in immutable storage;

in response to a determination that the duplicate unit of data exists in the existing data storage construct, determining whether the existing data storage construct is designated as being available to be referenced; and

in response to the existing data storage construct being designated as being unavailable to be referenced, storing the unit of data in a new data storage construct.

16 . The non-transitory computer-readable storage medium of claim 15 , wherein the method further comprises, in response to the existing data storage construct being designated as being unavailable to be referenced, updating a reference to the duplicate unit of data, wherein the backup image comprises the reference.

17 . The non-transitory computer-readable storage medium of claim 15 , wherein the method further comprises, in response to the existing data storage construct being designated as being available to be referenced, updating a reference to the duplicate unit of data.

18 . The non-transitory computer-readable storage medium of claim 16 , performing an update process on the existing data storage construct, wherein the update process includes:

determining a state of the existing data storage construct;

comparing the state of the existing data storage construct and one or more thresholds determined by performing a threshold determination process;

determining whether the state of the existing data storage construct meets the one or more thresholds; and

in response to the state of the existing data storage construct meeting the one or more thresholds, designating the existing data storage construct as being unavailable.

19 . The non-transitory computer-readable storage medium of claim 18 , further comprising, in response to the existing data storage construct being designated as being unavailable to be referenced, adding data object metadata to the new data storage construct, wherein the data object metadata is associated with the unit of data.

20 . A computing system comprising:

one or more processors; and

a computer-readable storage medium coupled to the one or more processors, comprising program instructions, which, when executed by the one or more processors, perform a method comprising:

selecting a unit of data of a backup image;

determining whether a duplicate unit of data is stored in an existing data storage construct, wherein the duplicate unit of data is a duplicate of the selected unit of data, and wherein the existing data storage construct is stored in immutable storage;

in response to a determination that the duplicate unit of data exists in the existing data storage construct, determining whether the existing data storage construct is designated as being available to be referenced; and

in response to the existing data storage construct being designated as being unavailable to be referenced, storing the unit of data in a new data storage construct.