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

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.

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.