Techniques for garbage collecting zones in a file system
Described are examples for performing garbage collection in a file system having multiple zones of data. A garbage rate associated with an amount of invalid data in the zone can be computed for each zone of the multiple zones in the file system. One or more candidate zones, of the multiple zones, can be determined for garbage collection based on the garbage rate and a sequence number assigned to the zone. Garbage collection of the one or more candidate zones in the file system can be performed.
1 . A computer-implemented method for performing garbage collection, in a file system having multiple zones of data, using sequence numbers assigned to the multiple zones to assess hotness or coldness of the data, comprising:
computing, for each zone of the multiple zones in the file system, a garbage rate associated with an amount of invalid data in the zone;
determining, based on the garbage rate and a sequence number assigned to each zone, one or more candidate zones, of the multiple zones, for garbage collection to prioritize garbage collection of zones having colder data than other zones, wherein the sequence number is assigned to each zone at a time the zone is created for storing data; and
performing garbage collection of the one or more candidate zones in the file system.
2 . The computer-implemented method of claim 1 , wherein determining the one or more candidate zones includes determining that the sequence number of the one or more candidate zones is outside of a dwell time from a highest sequence number of the multiple zones, wherein the dwell time represents a range of sequence numbers, from the highest sequence number, which corresponds to a latest assigned zone, to be avoided during garbage collection.
3 . The computer-implemented method of claim 1 , wherein the one or more candidate zones includes multiple candidate zones, and wherein determining the multiple candidate zones includes:
determining a subset of multiple ones of the one or more candidate zones having a highest garbage rate; and
removing, from the subset of multiple ones of the one or more candidate zones, at least one candidate zone having a garbage rate that is less than a garbage rate gap from the highest garbage rate of a top candidate zone in the subset, wherein the garbage rate gap is configured by the file system and represents a range of garbage rate from the highest garbage rate to be considered in garbage collection.
4 . The computer-implemented method of claim 3 , wherein performing the determining of the multiple candidate zones is based at least in part on determining that a capacity of the file system achieves a threshold.
5 . The computer-implemented method of claim 1 , wherein the one or more candidate zones includes multiple candidate zones, and wherein determining the multiple candidate zones includes:
determining a subset of multiple ones of the one or more candidate zones having a highest garbage rate; and
removing, from the subset of multiple ones of the one or more candidate zones, at least one candidate zone having a higher sequence number than other candidate zones in the subset to prioritize garbage collecting zones with colder data.
6 . The computer-implemented method of claim 5 , wherein performing the determining of the multiple candidate zones is based at least in part on determining that a capacity of the file system achieves a threshold.
7 . The computer-implemented method of claim 1 , wherein the one or more candidate zones includes multiple candidate zones, and wherein determining the multiple candidate zones includes:
determining a subset of multiple ones of the one or more candidate zones having a highest garbage rate; and
removing, from the subset of multiple ones of the one or more candidate zones, at least one candidate zone having a sequence number that is greater than a sequence number gap from a candidate zone in the subset having a lowest sequence number, wherein the sequence number gap is configured by the file system and represents a range of sequence numbers from the lowest sequence number to be considered in garbage collection.
8 . The computer-implemented method of claim 7 , wherein performing the determining of the multiple candidate zones is based at least in part on determining that a capacity of the file system achieves a threshold.
9 . The computer-implemented method of claim 1 , wherein determining the one or more candidate zones includes determining the one or more candidate zones having a highest garbage rate and having a sequence number that is outside of a dwell time from a highest sequence number of the multiple zones, wherein the dwell time represents a range of sequence numbers, from the highest sequence number, which corresponds to a latest assigned zone, to be avoided during garbage collection.
10 . The computer-implemented method of claim 9 , wherein determining the one or more candidate zones is based at least in part on determining that a capacity of the file system achieves a threshold.
11 . The computer-implemented method of claim 1 , wherein determining the one or more candidate zones includes determining that the one or more candidate zones are opened by a host application, such that zones opened by the file system for rewriting valid data are not considered for garbage collection.
12 . An apparatus for performing garbage collection in a file system having multiple zones of data, the apparatus comprising one or more processors and one or more non-transitory memories with instructions thereon, wherein the instructions upon execution by the one or more processors, cause the one or more processors to:
compute, for each zone of the multiple zones in the file system, a garbage rate associated with an amount of invalid data in the zone;
determine, based on the garbage rate and a sequence number assigned to each zone, one or more candidate zones, of the multiple zones, for garbage collection; and
perform garbage collection of the one or more candidate zones in the file system.
13 . The apparatus of claim 12 , wherein the instructions upon execution by the one or more processors, cause the one or more processors to determine the one or more candidate zones at least in part by determining that the sequence number of the one or more candidate zones is outside of a dwell time from a highest sequence number of the multiple zones.
14 . The apparatus of claim 12 , wherein the one or more candidate zones includes multiple candidate zones, and wherein the instructions upon execution by the one or more processors, cause the one or more processors to determine the multiple candidate zones at least in part by:
determining a subset of multiple ones of the one or more candidate zones having a highest garbage rate; and
removing, from the subset of multiple ones of the one or more candidate zones, at least one candidate zone having a garbage rate that is less than a garbage rate gap from the highest garbage rate of a top candidate zone in the subset.
15 . The apparatus of claim 12 , wherein the one or more candidate zones includes multiple candidate zones, and wherein the instructions upon execution by the one or more processors, cause the one or more processors to determine the multiple candidate zones at least in part by:
determining a subset of multiple ones of the one or more candidate zones having a highest garbage rate; and
removing, from the subset of multiple ones of the one or more candidate zones, at least one candidate zone having a higher sequence number than other candidate zones in the subset.
16 . The apparatus of claim 12 , wherein the one or more candidate zones includes multiple candidate zones, and wherein the instructions upon execution by the one or more processors, cause the one or more processors to determine the multiple candidate zones at least in part by:
determining a subset of multiple ones of the one or more candidate zones having a highest garbage rate; and
removing, from the subset of multiple ones of the one or more candidate zones, at least one candidate zone having a sequence number that is greater than a sequence number gap from a candidate zone in the subset having a lowest sequence number.
17 . The apparatus of claim 12 , wherein the instructions upon execution by the one or more processors, cause the one or more processors to determine the one or more candidate zones at least in part by determining the one or more candidate zones having a highest garbage rate and having a sequence number that is outside of a dwell time from a highest sequence number of the multiple zones.
18 . The apparatus of claim 12 , wherein the instructions upon execution by the one or more processors, cause the one or more processors to determine the one or more candidate zones at least in part by determining that the one or more candidate zones are opened by a host application.
19 . One or more non-transitory computer-readable storage media storing instructions that when executed by one or more processors cause the one or more processors to execute a method for performing garbage collection in a file system having multiple zones of data, wherein the method comprises:
computing, for each zone of the multiple zones in the file system, a garbage rate associated with an amount of invalid data in the zone;
determining, based on the garbage rate and a sequence number assigned to each zone, one or more candidate zones, of the multiple zones, for garbage collection; and
performing garbage collection of the one or more candidate zones in the file system.
20 . The one or more non-transitory computer-readable storage media of claim 19 , wherein determining the one or more candidate zones includes determining that the sequence number of the one or more candidate zones is outside of a dwell time from a highest sequence number of the multiple zones.