Intelligent redundant array of independent disks with high performance recompaction

A system for efficiently freeing unused storage space in at least one storage device comprising non-volatile memory, the system comprising:

• a controller comprising a processor and a memory;
• a first log file (L1) in the controller memory and comprising entries of free storage space available from a plurality of physical storage regions each comprising a plurality of storage chunks;
• a second log file (L2) in the controller memory, based on L1, comprising a respective bitmap identifying the free storage space available from each corresponding storage chunk;
• a statistical distribution in the controller memory, based on the bitmaps, corresponding to each storage region and representing a percentage of free storage space available from each of the storage chunks;
• a weight value in the controller memory and corresponding to each storage region, wherein the weight value of a particular storage region is based on the number of storage chunks in that particular storage region that are associated with each of the percentages represented in the corresponding distribution for that particular storage region;
• and
• a sorted representation of the storage region weights in the controller memory.

A non-transitory processor-readable storage medium storing one or more sequences of instructions which, when executed by at least one processing circuit, cause performance of:

• maintaining a first log file (L1) of free storage space available from a plurality of physical storage regions each comprising a plurality of storage chunks;
• based on L1, maintaining a second log file (L2) comprising a respective bitmap identifying the free storage space available from each corresponding storage chunk;
• based on the bitmaps, generating a distribution corresponding to each storage region and representing a percentage of free storage space available from each of the storage chunks;
• generating a weight corresponding to each storage region, wherein the weight of a particular storage region is based on the number of storage chunks in that particular storage region that are associated with each of the percentages represented in the corresponding distribution for that particular storage region;
• and
• loading at least a portion of the storage region weights in sorted order into random access memory.

A system comprising:

• means for maintaining a first log file (L1) of free storage space available from a plurality of physical storage regions each comprising a plurality of storage chunks;
• means for maintaining, based on L1, a second log file (L2) comprising a respective bitmap identifying the free storage space available from each corresponding storage chunk;
• means for generating, based on the bitmaps, a distribution corresponding to each storage region and representing a percentage of free storage space available from each of the storage chunks having free storage space available;
• means for generating a weight corresponding to each storage region, wherein the weight of a particular storage region is based on the number of storage chunks in that particular storage region that are associated with each of the percentages represented in the corresponding distribution for that particular storage region;
• and
• means for loading at least a portion of the storage region weights in sorted order into random access memory.