Dynamic clustering-based allocation of free chunks at L2P in thin provisioning
Large gaps in a L2P table that are disturbed by a few occupied addresses may be efficiently utilized by locating and considering the low-density of these occupied addresses in regards to the large gap (i.e., the gap free region altogether). By identifying a gap in a L2P table and then determining if the number of occupied addresses in the gap are less than a threshold value, the gap with the limited number of occupied addresses may be indicated as available RAM buffers for the system. The limited number of occupied addresses may then be marked and replaced with other addresses to evacuate a longer sequence of free addresses that can be used by the system, thereby optimizing data storage operations. In some embodiments, conventional clustering algorithms may be used to determine gap availability. In some embodiments, the stability several gaps may be tracked and used to determine storage priority.
1 . A data storage device, comprising:
a memory device; and
a controller coupled to the memory device, wherein the controller is configured to:
locate at least one gap in a L2P table, wherein a gap is a sequence of free addresses;
identify an address range of the gap in the L2P table;
determine whether the address range of the gap has a number of outliers less than or equal to a threshold, wherein the threshold is greater than 0 and an outlier is an occupied address within the gap;
indicate the address range of the gap is available if the number of the outliers is less than or equal to the threshold;
indicate the address range of the gap is not available if the number of the outliers is greater than the threshold;
relocate, to a L2P relocation table, the outliers in the address range of the gap identified as available; and
in response to a request to the L2P table, obtain a L2P address from the relocated outliers in the L2P relocation table.
2 . The data storage device of claim 1 , wherein the threshold is a number of addresses equal to 0.1% of the gap.
3 . The data storage device of claim 1 , wherein the controller is further configured to determine whether the address range of the gap is available using cluster analysis.
4 . The data storage device of claim 3 , wherein the cluster analysis comprises a k-means algorithm or a Gaussian Mixture Models (GMM) algorithm.
5 . The data storage device of claim 3 , wherein the controller is further configured to indicate the address range of the gap is available based on the cluster analysis.
6 . A data storage device, comprising:
a memory device; and
a controller coupled to the memory device, wherein the controller is configured to:
locate at least one gap in a L2P table, wherein a gap is a sequence of free addresses;
scan an address region of the L2P table;
identify the gap in the address region for use as a random access memory (RAM) buffer, wherein identifying the gap comprises:
determining whether an address in the L2P table is occupied, adding the address to an address range of the gap, and
determining whether the address range of the gap has a number of occupied addresses less than or equal to a threshold;
in response to determining that the address range in the gap has the number of the occupied addresses less than or equal to the threshold, indicate the address range of the gap as available;
relocate, to a L2P relocation table, the occupied addresses in the address range of the gap identified as available; and
in response to a request to the L2P table, obtain a L2P address from the relocated occupied addresses in the L2P relocation table.
7 . The data storage device of claim 6 , wherein identifying the gap further comprises determining whether the address range of the gap has a number of non-occupied addresses greater than or equal to a second threshold.
8 . The data storage device of claim 7 , wherein the address range of the gap is indicated as available if i) the address range of the gap has the number of occupied addresses less than or equal to the threshold and ii) the number of non-occupied addresses greater than or equal to the second threshold.
9 . The data storage device of claim 8 , wherein the threshold is five occupied addresses and the second threshold is 1,024 addresses.
10 . The data storage device of claim 7 , wherein identifying the gap further comprises scanning a next address in the address region if the number of non-occupied addresses is less than the second threshold.
11 . The data storage device of claim 6 , wherein the controller is further configured to increase a start address of the address range of the at least one gap by one when the gap is indicated as not unavailable.
12 . A data storage device, comprising:
means to store data; and
a controller coupled to the means to store data, wherein the controller is configured to:
receive at least one read/write command for an address in an address range of at least one gap, wherein the at least one gap is a sequence of free addresses;
track a number of read/write commands for addresses in the address range of the at least one gap;
determine whether the address range of the at least one gap is stable for a period greater than or equal to a threshold;
indicate a first address range of a first gap as available if a number of first outliers, in the first address range, is less than or equal to a first threshold;
relocate, to a L2P relocation table, the first outliers in the first address range identified as available; and
in response to a request to the L2P table, obtain a L2P address from the relocated first outliers in the L2P relocation table.
13 . The data storage device of claim 12 , wherein the controller is further configured to allocate the address range of the at least one gap as a temporal buffer if the address range of the at least one gap is stable for a period greater than or equal to the threshold.
14 . The data storage device of claim 12 , wherein the controller is further configured to track at least one parameter of the at least one read/write command for the addresses in the address range of the at least one gap, and wherein the at least one parameter comprises a rate of write/erase commands for a user, a size of the received at least one read/write command, a size of the at least one gap, or a combination thereof.
15 . The data storage device of claim 14 , wherein the controller is further configured to build and update a model using i) the tracked number of read/write commands for the addresses in the address range of the at least one gap and ii) the tracked at least one parameter.
16 . The data storage device of claim 12 , wherein the controller is further configured to prioritize a plurality of gaps for data storage based on stability of each gap, wherein the at least one gap is one of the plurality of gaps.