Apparatus, systems, and methods for providing a memory efficient cache
The present disclosure relates to apparatus, systems, and methods that implement a less-recently-used data eviction mechanism for identifying a memory block of a cache for eviction. The less-recently-used mechanism can achieve a similar functionality as the least-recently-used data eviction mechanism, but at a lower memory requirement. A memory controller can implement the less-recently-used data eviction mechanism by selecting a memory block and determining whether the memory block is one of the less-recently-used memory blocks. If so, the memory controller can evict data in the selected memory block; if not, the memory controller can continue to select other memory blocks until the memory controller selects one of the less-recently-used memory blocks.
1. A method comprising:
receiving, at a memory controller in a storage system coupled to a host device via an interface, a memory access request, wherein the memory access request comprises a memory block identifier that identifies a memory block;
determining, at the memory controller, that data associated with the memory access request should be stored in one of memory blocks in the cache and that each of the memory blocks in the cache is already occupied with valid data;
selecting, by the memory controller, one of the memory blocks;
determining a first transaction count associated with the selected memory block, wherein the first transaction count is indicative of a time instance at which the selected memory block was accessed; and
when the first transaction count satisfies a predetermined criterion, causing, by the memory controller, the selected memory block to store the data, and
when the first transaction count does not satisfy the predetermined criterion, selecting, by the memory controller, another one of the memory blocks until the memory controller selects a memory block whose transaction count satisfies the predetermined criterion and
maintaining a transaction count list having at least one entry, wherein the at least one entry is indicative of a number of memory blocks having a transaction count that is within a preconfigured range; and
determining a transaction count threshold based on the number of memory blocks having a transaction count that is within the preconfigured range.
2. The method of claim 1 , wherein selecting the one of the memory blocks comprises selecting a memory block identifier using a random number generator.
3. The method of claim 1 , further comprising maintaining the transaction count threshold, and wherein the first transaction count satisfies the predetermined criterion when the first transaction count satisfies a predetermined condition with respect to the transaction count threshold.
4. The method of claim 3 , wherein the first transaction count satisfies the predetermined condition with respect to the transaction count threshold when the first transaction count is less than the transaction count threshold.
5. The method of claim 3 , wherein when an average number of iterations used for identifying the selected memory block is small, causing a modification of the transaction count threshold to reduce a number of memory blocks that satisfy the predetermined criterion.
6. The method of claim 1 , further comprising:
receiving a parameter indicative of a number of memory blocks that satisfy the predetermined criterion; and
determining the preconfigured range based on the parameter.
7. The method of claim 1 , further comprising:
receiving, at the memory controller, a first memory access request, wherein the first memory access request comprises a first memory block identifier that identifies a first memory block;
determining, at the memory controller, that data associated with the first memory access request is already stored in one of memory blocks in the cache; and
updating a transaction count of the one of memory blocks in the cache to reflect the first memory access request.
8. The method of claim 1 , further comprising identifying an entry of the transaction count list associated with the first memory block, and updating the number of memory blocks in the entry to reflect the first memory access request.
9. A storage system comprising:
a cache comprising a plurality of memory blocks for maintaining data; and
a memory controller configured to process a memory access request received from a host device, wherein the memory access request comprises a memory block identifier that identifies a memory block, wherein the memory controller is further configured to:
determine that data associated with the memory access request should be stored in one of memory blocks in the cache and that each of the memory blocks in the cache is already occupied with valid data;
select one of the memory blocks in the cache;
determine a first transaction count associated with the selected memory block, wherein the first transaction count is indicative of a time instance at which the selected memory block was accessed; and
when the first transaction count satisfies a predetermined criterion, cause the selected memory block to store the data, and
when the first transaction count does not satisfy the predetermined criterion, select another one of the memory blocks until the memory controller selects a memory block whose transaction count satisfies the predetermined criterion; and
maintain a transaction count list having at least one entry, wherein the at least one entry is indicative of a number of memory blocks having a transaction count that is within a preconfigured range; and
determine a transaction count threshold based on the number of memory blocks having a transaction count that is within the preconfigured range.
10. The storage system of claim 9 , wherein the memory controller is configured to select a memory block identifier using a random number generator.
11. The storage system of claim 9 , wherein the first transaction count satisfies the predetermined criterion when the first transaction count satisfies a predetermined condition with respect to the transaction count threshold.
12. The storage system of claim 11 , wherein when an average number of iterations used for identifying the selected memory block is small, the memory controller is configured to cause a modification of the transaction count threshold to reduce a number of memory blocks that satisfy the predetermined criterion.
13. The storage system of claim 9 , wherein the memory controller is configured to:
receive a parameter indicative of a number of memory blocks that satisfy the predetermined criterion; and
determine the preconfigured range based on the parameter.
14. The storage system of claim 9 , wherein the memory controller is configured to:
receive a first memory access request, wherein the first memory access request comprises a first memory block identifier that identifies a first memory block;
determine that data associated with the first memory access request is already stored in one of memory blocks in the cache; and
update a transaction count of the one of memory blocks in the cache to reflect the first memory access request.
15. A non-transitory computer readable medium having executable instructions operable to cause a memory controller to:
receive a memory access request from a host device over an interface, wherein the memory access request comprises a memory block identifier that identifies a memory block;
determine that data associated with the memory access request should be stored in one of memory blocks in the cache and that each of the memory blocks in the cache is already occupied with valid data;
select one of the memory blocks in the cache;
determine a first transaction count associated with the selected memory block, wherein the first transaction count is indicative of a time instance at which the selected memory block was accessed; and
when the first transaction count satisfies a predetermined criterion, cause the selected memory block to store the data, and
when the first transaction count does not satisfy the predetermined criterion, select another one of the memory blocks until the memory controller selects a memory block whose transaction count satisfies the predetermined criterion; and
maintain a transaction count list having at least one entry, wherein the at least one entry is indicative of a number of memory blocks having a transaction count that is within a preconfigured range; and
determine a transaction count threshold based on the number of memory blocks having a transaction count that is within the preconfigured range.
16. The computer readable medium of claim 15 , wherein the first transaction count satisfies the predetermined criterion when the first transaction count satisfies a predetermined condition with respect to the transaction count threshold.
17. The computer readable medium of claim 15 , further comprising executable instructions operable to cause the memory controller to:
receive a first memory access request, wherein the first memory access request comprises a first memory block identifier that identifies a first memory block;
determine that data associated with the first memory access request is already stored in one of memory blocks in the cache;
update a transaction count of the one of memory blocks in the cache to reflect the first memory access request.