Method and system for address table eviction management
A system and method are disclosed for handling logical-to-physical mapping and increasing the amount of mapping table information that may be stored in a cache in volatile memory. The system includes a storage device having non-volatile memory, an input/output interface, a cache manager, a cache utilization manager, a cache swap manager, and a storage controller configured to service a storage command using a physical address provided by the cache manager. The method includes receiving a storage command comprising a logical address, the logical address comprising a partition identifier, implementing a cache eviction policy in response to determining that a mapping table cache does not have a cache entry that matches the logical address. The method also includes evicting the cache entry with a ranking, or score, that satisfies a cache eviction threshold and loading a replacement cache entry from an address mapping table stores on non-volatile memory.
1. An apparatus, comprising:
a cache utilization manager configured to track cache utilization metrics of a mapping table cache based on a logical address, the logical address comprising a partition identifier, a starting logical block address, and a count; and
a cache swap manager configured to, in response to a cache miss, replace a cache entry in the mapping table cache with a replacement cache entry, the cache entry having cache utilization metrics based on a partition access frequency, the cache utilization metrics satisfying a cache eviction threshold.
2. The apparatus of claim 1 , wherein the cache utilization manager comprises a utilization tracker configured to monitor, for each cache entry, which partitions are associated with the cache entry and to monitor a partition access frequency that identifies how many times a partition associated with the cache entry is referenced by a storage command being serviced by the apparatus.
3. The apparatus of claim 1 , wherein the partition access frequency comprises how often the apparatus receives a read command with a logical address identifying a partition identifier referenced within a cache entry.
4. The apparatus of claim 1 , wherein the cache utilization manager comprises a comparator configured to determine a score for each cache entry, the score based on the cache utilization metrics.
5. The apparatus of claim 4 , wherein the comparator is configured to determine the score based on a partition similarity score, the comparator determining the partition similarity score by determining the partition access frequency in relation to the partition identifier.
6. An apparatus, comprising:
a cache utilization manager configured to track cache utilization metrics of a mapping table cache based on a logical address, the logical address comprising a partition identifier, a starting logical block address, and a count, the cache utilization manager comprising a comparator configured to:
determine a score for each cache entry, the score based on the cache utilization metrics; and
determine the score based on both a partition similarity score and a modified least recently used score relative to a logical address of a read command received by the apparatus; and
a cache swap manager configured to replace a cache entry in the mapping table cache with a replacement cache entry, the cache entry having cache utilization metrics based on a partition access frequency, the cache utilization metrics satisfying a cache eviction threshold.
7. The apparatus of claim 6 , wherein the comparator is configured to weight the partition similarity score and to weight the modified least recently used score based on a weighting parameter.
8. A system, comprising:
a non-volatile memory configured to store an address mapping table;
a volatile memory configured to store a mapping table cache comprising a set of cache entries;
an input/output (IO) interface configured to receive a storage command comprising a logical address that uniquely identifies a set of data blocks stored on the non-volatile memory;
a cache manager configured to load cache entries from the non-volatile memory into the volatile memory;
a cache utilization manager configured to manage cache utilization metrics based on a partition access frequency and a cache access frequency;
a cache swap manager configured to determine, in response to a cache miss, a cache eviction candidate based on the cache utilization metrics and on the logical address and to replace the cache eviction candidate in the mapping table cache with a replacement cache entry corresponding to the logical address of the storage command; and
a storage controller configured to service the storage command using a physical address provided by the cache manager.
9. The system of claim 8 , wherein the cache utilization manager comprises a utilization tracker configured to monitor, for each cache entry, which partitions are associated with the cache entry and a partition access frequency that identifies how many times a partition associated with the cache entry is referenced by a storage command serviced by the system.
10. The system of claim 8 , wherein the cache utilization manager comprises a utilization tracker configured to monitor, for each cache entry, a cache access frequency relative to other cache entries in the mapping table cache.
11. The system of claim 8 , wherein the partition access frequency comprises how often the system receives a storage command with a logical address identifying a partition identifier referenced within a cache entry.
12. The system of claim 8 , wherein the cache utilization manager comprises a comparator configured to determine a score for each cache entry, the score based on the cache utilization metrics.
13. The system of claim 12 , wherein the comparator is configured to apply a different weight to the partition access frequency than to the cache access frequency to determine the score.
14. The system of claim 13 , wherein the cache access frequency comprises a modified least recently used score comprising a combination of which cache entry was least recently used to service a storage command and which cache entry was most frequently used relative to other cache entries in the mapping table cache during a sliding lookback window.
15. A method, comprising:
receiving a read command comprising a logical address, the logical address comprising a partition identifier;
implementing a cache eviction policy to determine which cache entry to evict when a cache miss occurs, wherein the cache eviction policy is implemented in response to determining that a mapping table cache does not have a cache entry that matches the logical address, wherein the cache eviction policy comprises, ranking each cache entry in the mapping table cache based on cache utilization metrics that include a partition access frequency;
evicting the cache entry having a ranking that satisfies a cache eviction threshold; and
loading a replacement cache entry from an address mapping table stored on non-volatile memory, the replacement cache entry comprising a mapping of the logical address to a physical address.
16. The method of claim 15 , wherein ranking comprises determining a score for each cache entry in the mapping table cache.
17. A method, comprising:
receiving a read command comprising a logical address, the logical address comprising a partition identifier;
implementing a cache eviction policy in response to determining that a mapping table cache does not have a cache entry that matches the logical address, wherein the cache eviction policy comprises, ranking each cache entry in the mapping table cache based on cache utilization metrics that include a partition access frequency, wherein the ranking comprises determining a score for each cache entry in the mapping table cache, and wherein the score comprises a combination of a weighted partition similarity score and a weighted modified least recently used score;
evicting the cache entry having a ranking that satisfies a cache eviction threshold; and
loading a replacement cache entry from an address mapping table stored on non-volatile memory, the replacement cache entry comprising a mapping of the logical address to a physical address.
18. The method of claim 15 , further comprising storing a ranking for each cache entry and the ranking comprises updating a stored ranking for each cache entry in the mapping table cache within a sliding lookback window.
19. The method of claim 18 , wherein the sliding lookback window comprises cache utilization metrics for N prior read commands, N>1000.
20. The method of claim 15 , modifying the cache eviction policy based on a tuning parameter provided by a host configured to send the read command.