Managing least recently used cache using reduced memory footprint sequence container
Techniques are provided for managing a least recently used cache using a linked list with a reduced memory footprint. A cache manager receives an I/O request comprising a target address, wherein the cache manager manages a cache memory having a maximum allocated amount of cache entries, and a linked list having a maximum allocated amount of list elements which is less than the maximum allocated amount of cache entries. If the target address does correspond to a cache entry, the cache manager accesses the cache entry to obtain the cache data from cache memory, removes a list element from the linked list, which corresponds to the accessed cache entry, selects an existing cache entry which currently does not have a corresponding list element in the linked list, and adds a list element to a head position of the linked list which corresponds to the selected cache entry.
1. A method, comprising:
receiving, by a cache management system, an input/output (I/O) request comprising a target address for accessing data, wherein the cache management system manages a cache memory having a maximum allocated amount of cache entries, and a linked list data structure having a maximum allocated amount of list elements, wherein the maximum allocated amount of list elements is less than the maximum allocated amount of cache entries;
commencing, by the cache management system, a cache access operation to determine whether the target address corresponds to a cache entry; and
in response to determining that the target address does correspond to a cache entry;
accessing, by the cache management system, the cache entry to obtain cache data from cache memory and returning the obtained cache data to a requesting cache client;
removing, by the cache management system, a list element from the linked list data structure, wherein the removed list element corresponds to the accessed cache entry;
selecting, by the cache management system, an existing cache entry which currently does not have a corresponding list element in the linked list data structure; and
adding, by the cache management system, a list element to a head position of the linked list data structure which corresponds to the selected cache entry.
2. The method of claim 1 , wherein selecting the existing cache entry comprises randomly selecting an existing cache entry which currently does not have a corresponding list element in the linked list data structure.
3. The method of claim 1 , wherein in response to determining that the target address does correspond to a cache entry, the method further comprising:
determining, by the cache management system, whether the linked list data structure comprises a list element which corresponds to the accessed cache entry; and
in response to determining that the linked list data structure does not comprise a list element which corresponds to the accessed cache entry, the cache management system:
removing a list element at a tail position of the linked list data structure;
randomly selecting an existing cache entry which currently does not have a corresponding list element in the linked list data structure; and
adding a list element to the head position of the linked list data structure which corresponds to the randomly selected cache entry.
4. The method of claim 1 , wherein in response to the cache management system determining that the target address of the I/O request does not correspond to a cache entry, the method further comprising:
determining, by the cache management system, whether there is an unused cache entry available to service the I/O request, and in response to determining that an unused cache entry is not available;
evicting, by the cache management system, a list element at a tail position of the linked list data structure;
evicting, by the cache management system, a cache entry which corresponds to the evicted list element;
randomly selecting, by the cache management system, an existing cache entry which currently does not have a corresponding list element in the linked list data structure; and
adding, by the cache management system, a list element to the head position of the linked list data structure which corresponds to the randomly selected cache entry.
5. The method of claim 4 , wherein in response to determining that an unused cache entry is not available, the method further comprising:
adding a new cache entry associated with the I/O request;
accessing data associated with the I/O request from one of a storage device and another cache memory; and
adding to the new cache entry a null pointer to the linked list data structure.
6. The method of claim 4 , further comprising destaging cache data associated with the evicted cache entry to one of another cache memory and a storage device.
7. The method of claim 4 , wherein in response to the cache management system determining that an unused cache entry is available, the method further comprising:
removing a list element at the tail position of the linked list data structure;
randomly selecting an existing cache entry which currently does not have a corresponding list element in the linked list data structure; and
adding a list element to the head position of the linked list data structure which corresponds to the randomly selected cache entry.
8. The method of claim 1 , wherein the cache memory comprises a write cache memory that is configured to store data records, wherein a size of each data record is less than a total size of metadata that is stored in data fields of a single list element.
9. The method of claim 1 , wherein the maximum allocated amount of list elements is in a range of about 1/1000 to about 1/200 of the maximum allocated amount of cache entries.
10. An article of manufacture comprising a non-transitory processor-readable storage medium having stored therein program code of one or more software programs, wherein the program code is executable by one or more processors to implement a method comprising:
receiving, by a cache management system, an input/output (I/O) request comprising a target address for accessing data, wherein the cache management system manages a cache memory having a maximum allocated amount of cache entries, and a linked list data structure having a maximum allocated amount of list elements, wherein the maximum allocated amount of list elements is less than the maximum allocated amount of cache entries;
commencing, by the cache management system, a cache access operation to determine whether the target address corresponds to a cache entry; and
in response to determining that the target address does correspond to a cache entry;
accessing, by the cache management system, the cache entry to obtain cache data from cache memory and returning the obtained cache data to a requesting cache client;
removing, by the cache management system, a list element from the linked list data structure, wherein the removed list element corresponds to the accessed cache entry;
selecting, by the cache management system, an existing cache entry which currently does not have a corresponding list element in the linked list data structure; and
adding, by the cache management system, a list element to a head position of the linked list data structure which corresponds to the selected cache entry.
11. The article of manufacture of claim 10 , wherein selecting the existing cache entry comprises randomly selecting an existing cache entry which currently does not have a corresponding list element in the linked list data structure.
12. The article of manufacture of claim 10 , wherein in response to determining that the target address does correspond to a cache entry, the method further comprising:
determining, by the cache management system, whether the linked list data structure comprises a list element which corresponds to the accessed cache entry; and
in response to determining that the linked list data structure does not comprise a list element which corresponds to the accessed cache entry, the cache management system:
removing a list element at a tail position of the linked list data structure;
randomly selecting an existing cache entry which currently does not have a corresponding list element in the linked list data structure; and
adding a list element to the head position of the linked list data structure which corresponds to the randomly selected cache entry.
13. The article of manufacture of claim 10 , wherein in response to the cache management system determining that the target address of the I/O request does not correspond to a cache entry, the method further comprising:
determining, by the cache management system, whether there is an unused cache entry available to service the I/O request, and in response to determining that an unused cache entry is not available;
evicting, by the cache management system, a list element at a tail position of the linked list data structure;
evicting, by the cache management system, a cache entry which corresponds to the evicted list element;
randomly selecting, by the cache management system, an existing cache entry which currently does not have a corresponding list element in the linked list data structure; and
adding, by the cache management system, a list element to the head position of the linked list data structure which corresponds to the randomly selected cache entry.
14. The article of manufacture of claim 13 , wherein in response to determining that an unused cache entry is not available, the method further comprising:
adding a new cache entry associated with the I/O request;
accessing data associated with the I/O request from one of a storage device and another cache memory; and
adding to the new cache entry a null pointer to the linked list data structure.
15. The article of manufacture of claim 13 , wherein in response to the cache management system determining that an unused cache entry is available, the method further comprising:
removing a list element at the tail position of the linked list data structure;
randomly selecting an existing cache entry which currently does not have a corresponding list element in the linked list data structure; and
adding a list element to the head position of the linked list data structure which corresponds to the randomly selected cache entry.
16. An apparatus, comprising:
at least one processor; and
system memory configured to store program code, wherein the program code is executable by the at least one processor to implement a storage control system which is configured to:
receive an input/output (I/O) request comprising a target address for accessing data, wherein the cache management system manages a cache memory having a maximum allocated amount of cache entries, and a linked list data structure having a maximum allocated amount of list elements, wherein the maximum allocated amount of list elements is less than the maximum allocated amount of cache entries;
commence a cache access operation to determine whether the target address corresponds to a cache entry; and
in response to determining that the target address does correspond to a cache entry;
access the cache entry to obtain cache data from cache memory and returning the obtained cache data to a requesting cache client;
remove a list element from the linked list data structure, wherein the removed list element corresponds to the accessed cache entry;
select an existing cache entry which currently does not have a corresponding list element in the linked list data structure; and
add, by the cache management system, a list element to a head position of the linked list data structure which corresponds to the selected cache entry.
17. The apparatus of claim 16 , wherein in selecting the existing cache entry the cache management system is configured to randomly select an existing cache entry which currently does not have a corresponding list element in the linked list data structure.
18. The apparatus of claim 16 , wherein in response to determining that the target address does correspond to a cache entry, the cache management system is further configured to:
determine whether the linked list data structure comprises a list element which corresponds to the accessed cache entry; and
in response to determining that the linked list data structure does not comprise a list element which corresponds to the accessed cache entry, the cache management system is configured to:
remove a list element at a tail position of the linked list data structure;
randomly select an existing cache entry which currently does not have a corresponding list element in the linked list data structure; and
add a list element to the head position of the linked list data structure which corresponds to the randomly selected cache entry.
19. The apparatus of claim 16 , wherein in response to determining that the target address of the I/O request does not correspond to a cache entry, the cache management system is further configured to:
determine whether there is an unused cache entry available to service the I/O request, and in response to determining that an unused cache entry is not available;
evict a list element at a tail position of the linked list data structure;
evict a cache entry which corresponds to the evicted list element;
randomly select an existing cache entry which currently does not have a corresponding list element in the linked list data structure;
add a list element to the head position of the linked list data structure which corresponds to the randomly selected cache entry; and
wherein in response to the cache management system determining that an unused cache entry is not available, the cache management system is further configured to:
add a new cache entry associated with the I/O request;
access data associated with the I/O request from one of a storage device and another cache memory; and
add to the new cache entry a null pointer to the linked list data structure.
20. The apparatus of claim 19 , wherein the cache management system is further configured to destage cache data associated with the evicted cache entry to one of another cache memory and a storage device.