Optimizing garbage collection copy forward operation by generating a live instance table

1 . A method for managing a garbage collection operation in a storage system, the method comprising:

generating a live filter using a Level 1 (L1) table,

wherein the L1 table comprises information with respect to Level 0 (L0) segments;

iterating an index table to obtain fingerprints (FPs) of the L0 segments and container identifiers (CIDs) associated with the FPs;

generating a live instance table based on the index table and the live filter,

wherein, while the live instance table is being generated, inactive FPs of the FPs or duplicated FPs of the FPs are eliminated and active FPs of the FPs are considered;

iterating the live instance table to count the active FPs for each CID,

wherein, in response to counting the active FPs, a reference table is populated to indicate how many of the active FPs are related to each CID;

identifying, based on the reference table and a liveness threshold, a first container that has a low-liveness state and a second container that has a high-liveness state;

assigning the first container to a batch;

identifying FPs of the L0 segments associated with each CID in the batch,

wherein the FPs are populated to a hash table;

obtaining metadata of each CID in the batch from a container metadata table;

generating a bitmap based on the hash table and the metadata;

identifying, based on the bitmap, a set of live compression regions (CRs), a set of inactive CRs, a set of live L0 segments within each of the set of live CRs, and a set of inactive L0 segments within each of the set of inactive CRs;

copying forward the set of live L0 segments to newer containers; and

deleting containers of the set of inactive L0 segments as part of the garbage collection operation.

2 . The method of claim 1 ,

wherein the inactive FPs are a set of FPs that is not included in the live filter, and

wherein an inactive FP of the inactive FPs indicates that a corresponding L0 segment of the L0 segments is not being used in a file system of the storage system.

3 . The method of claim 1 ,

wherein the live instance table comprises a first part of the duplicated FPs that has the highest CIDs, and

wherein a data segment pointed by the first part of the duplicated FPs is assumed active as the data segment pointed by the first part of the duplicated FPs is being used in a file system of the storage system.

4 . The method of claim 1 ,

wherein the live instance table is stored in a key-value store (KVS),

wherein the storage system is a distributed dedupe storage system, and

wherein the KVS and the distributed dedupe storage system are operatively connected to each other over a network.

5 . The method of claim 4 ,

wherein the L0 segments are data segments of a segment tree,

wherein the segment tree is stored to the distributed dedupe storage system,

wherein the L0 segments are the lowest level segments in the segment tree, and

wherein remaining segments of the segment tree are assigned as metadata segments.

6 . The method of claim 5 ,

wherein the metadata segments of the segment tree are stored to the KVS, and

wherein a key in the KVS represents a parent segment and a value associated with the key represents a plurality of child segments hosted by the parent segment.

7 . The method of claim 1 , wherein the container metadata table specifies third FPs that are associated with the set of live CRs, a CID that is associated with the set of live CRs, and a position of each of the set of live CRs in a container that is related to the CID.

8 . A non-transitory computer readable medium comprising computer readable program code, which when executed by a computer processor enables the computer processor to perform a method for managing a garbage collection operation in a storage system, the method comprising:

generating a live filter using a Level 1 (L1) table,

wherein the L1 table comprises information with respect to Level 0 (L0) segments;

iterating an index table to obtain fingerprints (FPs) of the L0 segments and container identifiers (CIDs) associated with the FPs;

generating a live instance table based on the index table and the live filter,

wherein, while the live instance table is being generated, inactive FPs of the FPs or duplicated FPs of the FPs are eliminated and active FPs of the FPs are considered;

iterating the live instance table to count the active FPs for each CID,

wherein, in response to counting the active FPs, a reference table is populated to indicate how many of the active FPs are related to each CID;

identifying, based on the reference table and a liveness threshold, a first container that has a low-liveness state and a second container that has a high-liveness state;

assigning the first container to a batch;

identifying FPs of the L0 segments associated with each CID in the batch,

wherein the FPs are populated to a hash table;

obtaining metadata of each CID in the batch from a container metadata table;

generating a bitmap based on the hash table and the metadata;

identifying, based on the bitmap, a set of live compression regions (CRs), a set of inactive CRs, a set of live L0 segments within each of the set of live CRs, and a set of inactive L0 segments within each of the set of inactive CRs;

copying forward the set of live L0 segments to newer containers; and

deleting containers of the set of inactive L0 segments as part of the garbage collection operation.

9 . The non-transitory computer readable medium of claim 8 ,

wherein the inactive FPs are a set of FPs that is not included in the live filter, and

wherein an inactive FP of the inactive FPs indicates that a corresponding L0 segment of the L0 segments is not being used in a file system of the storage system.

10 . The non-transitory computer readable medium of claim 8 ,

wherein the live instance table comprises a first part of the duplicated FPs that has the highest CIDs, and

wherein a data segment pointed by the first part of the duplicated FPs is assumed active as the data segment pointed by the first part of the duplicated FPs is being used in a file system of the storage system.

11 . The non-transitory computer readable medium of claim 8 ,

wherein the live instance table is stored in a key-value store (KVS),

wherein the storage system is a distributed dedupe storage system, and

wherein the KVS and the distributed dedupe storage system are operatively connected to each other over a network.

12 . The non-transitory computer readable medium of claim 11 ,

wherein the L0 segments are data segments of a segment tree,

wherein the segment tree is stored to the distributed dedupe storage system,

wherein the L0 segments are the lowest level segments in the segment tree, and

wherein remaining segments of the segment tree are assigned as metadata segments.

13 . The non-transitory computer readable medium of claim 12 ,

wherein the metadata segments of the segment tree are stored to the KVS, and

wherein a key in the KVS represents a parent segment and a value associated with the key represents a plurality of child segments hosted by the parent segment.

14 . The non-transitory computer readable medium of claim 8 , wherein the container metadata table specifies third FPs that are associated with the set of live CRs, a CID that is associated with the set of live CRs, and a position of each of the set of live CRs in a container that is related to the CID.

15 . A system for managing a garbage collection operation in a storage system, the system comprising:

a processor comprising circuitry;

memory comprising instructions, which when executed by the processor perform a method, the method comprising:

generating a live filter using a Level 1 (L1) table,

wherein the L1 table comprises information with respect to Level 0 (L0) segments;

iterating an index table to obtain fingerprints (FPs) of the L0 segments and container identifiers (CIDs) associated with the FPs;

generating a live instance table based on the index table and the live filter,

wherein, while the live instance table is being generated, inactive FPs of the FPs or duplicated FPs of the FPs are eliminated and active FPs of the FPs are considered;

iterating the live instance table to count the active FPs for each CID,

wherein, in response to counting the active FPs, a reference table is populated to indicate how many of the active FPs are related to each CID;

identifying, based on the reference table and a liveness threshold, a first container that has a low-liveness state and a second container that has a high-liveness state;

assigning the first container to a batch;

identifying FPs of the L0 segments associated with each CID in the batch, wherein the FPs are populated to a hash table;

obtaining metadata of each CID in the batch from a container metadata table;

generating a bitmap based on the hash table and the metadata;

identifying, based on the bitmap, a set of live compression regions (CRs), a set of inactive CRs, a set of live L0 segments within each of the set of live CRs, and a set of inactive L0 segments within each of the set of inactive CRs;

copying forward the set of live L0 segments to newer containers; and

deleting containers of the set of inactive L0 segments as part of the garbage collection operation.

16 . The system of claim 15 ,

wherein the inactive FPs are a set of FPs that is not included in the live filter, and

wherein an inactive FP of the inactive FPs indicates that a corresponding L0 segment of the L0 segments is not being used in a file system of the storage system.

17 . The system of claim 15 ,

wherein the live instance table comprises a first part of the duplicated FPs that has the highest CIDs, and

wherein a data segment pointed by the first part of the duplicated FPs is assumed active as the data segment pointed by the first part of the duplicated FPs is being used in a file system of the storage system.

18 . The system of claim 15 ,

wherein the live instance table is stored in a key-value store (KVS),

wherein the storage system is a distributed dedupe storage system, and

wherein the KVS and the distributed dedupe storage system are operatively connected to each other over a network.

19 . The system of claim 18 ,

wherein the L0 segments are data segments of a segment tree,

wherein the segment tree is stored to the distributed dedupe storage system,

wherein the L0 segments are the lowest level segments in the segment tree, and

wherein remaining segments of the segment tree are assigned as metadata segments.

20 . The system of claim 19 ,

wherein the metadata segments of the segment tree are stored to the KVS, and

wherein a key in the KVS represents a parent segment and a value associated with the key represents a plurality of child segments hosted by the parent segment.