Systems, devices and methods using a solid state device as a caching medium with a hashing algorithm to maintain sibling proximity
A method for managing a caching medium for a storage system includes providing an SSD cache including a plurality of cache lines, providing a data structure including a plurality of buckets for managing the SSD cache, and providing a plurality of cache headers for managing the cache lines. Each cache line has a first predetermined size, and each bucket corresponds to a contiguous region of a physical storage capacity having a second predetermined size. Each cache header associates a cache line and a corresponding data block stored in the data storage system. The method also includes assigning two or more cache headers for cache lines associated with corresponding data blocks stored in a same contiguous region of the physical storage capacity to a same bucket, and maintaining the two or more cache headers as a first group of cache headers within the same bucket.
1. A computer-implemented method for managing a caching medium for a data storage system, comprising:
providing an SSD cache including a plurality of cache lines, each cache line having a first predetermined size;
providing a data structure including a plurality of buckets for managing the SSD cache, each bucket corresponding to at least one contiguous region of a physical storage capacity of the data storage system, the at least one contiguous region of the physical storage capacity having a second predetermined size that is greater than the first predetermined size;
providing a plurality of cache headers for managing the cache lines, each cache header associating a cache line and a corresponding data block stored in the data storage system;
assigning two or more cache headers to a same bucket of the data structure, the two or more cache headers being cache headers for cache lines associated with corresponding data blocks stored in a first contiguous region of the physical storage capacity;
maintaining the two or more cache headers as a first group of cache headers within the same bucket of the data structure;
receiving an I/O operation directed to a data block stored in the first contiguous region of the physical storage capacity;
obtaining a hash value with a hashing algorithm based on the first contiguous region of the physical storage capacity to which the I/O operation is directed;
identifying the same bucket of the data structure based on the hash value; and
searching the first group of cache headers within the same bucket of the data structure to determine whether the I/O operation is a cache hit or a cache miss.
2. The computer-implemented method of claim 1 , wherein the first group of cache headers forms a doubly-linked list.
3. The computer-implemented method of claim 1 , further comprising maintaining a second group of cache headers within the same bucket of the data structure, the second group of cache headers including cache headers for cache lines associated with corresponding data blocks stored in a second contiguous region of the physical storage capacity.
4. The computer-implemented method of claim 3 , wherein the first group of cache headers and the second group of cache headers form a doubly-linked list.
5. The computer-implemented method of claim 4 , further comprising arranging the first group of cache headers and the second group of cache headers within the doubly-linked list based on a time or frequency of access.
6. The computer-implemented method of claim 5 , wherein the first group of cache headers or the second group of cache headers containing a cache header for a most-recently or most-frequently accessed cache line is arranged closer to a head of the doubly-linked list.
7. The computer-implemented method of claim 1 , wherein the first predetermined size is 8 KB and the second predetermined size is 64 KB.
8. The computer-implemented method of claim 1 , wherein at least one of the cache headers comprises a logical block number, a previous pointer, a subsequent pointer and a counter.
9. A non-transitory computer-readable storage medium having computer-executable instructions stored thereon for managing a caching medium for a data storage system that, when executed by a data storage system computer, cause the data storage system computer to:
provide an SSD cache including a plurality of cache lines, each cache line having a first predetermined size;
provide a data structure including a plurality of buckets for managing the SSD cache, each bucket corresponding to at least one contiguous region of a physical storage capacity of the data storage system, the at least one contiguous region of the physical storage capacity having a second predetermined size that is greater than the first predetermined size;
provide a plurality of cache headers for managing the cache lines, each cache header associating a cache line and a corresponding data block stored in the data storage system;
assign two or more cache headers to a same bucket of the data structure, the two or more cache headers being cache headers for cache lines associated with corresponding data blocks stored in a first contiguous region of the physical storage capacity;
maintain the two or more cache headers as a first group of cache headers within the same bucket of the data structure;
receive an I/O operation directed to a data block stored in the first contiguous region of the physical storage capacity;
obtain a hash value with a hashing algorithm based on the first contiguous region of the physical storage capacity to which the I/O operation is directed;
identify the same bucket of the data structure based on the hash value; and
search the first group of cache headers within the same bucket of the data structure to determine whether the I/O operation is a cache hit or a cache miss.
10. The non-transitory computer-readable storage medium of claim 9 , having further computer-executable instructions stored thereon that, when executed by the data storage system computer, cause the data storage system computer to maintain a second group of cache headers within the same bucket of the data structure, the second group of cache headers including cache headers for cache lines associated with corresponding data blocks stored in a second contiguous region of the physical storage capacity.
11. The non-transitory computer-readable storage medium of claim 10 , wherein the first group of cache headers and the second group of cache headers form a doubly-linked list.
12. The non-transitory computer-readable storage medium of claim 11 , having further computer-executable instructions stored thereon that, when executed by the data storage system computer, cause the data storage system computer to arrange the first group of cache headers and the second group of cache headers within the doubly-linked list based on a time or frequency of access.
13. The non-transitory computer-readable storage medium of claim 12 , wherein the first group of cache headers or the second group of cache headers containing a cache header for a most-recently or most-frequently accessed cache line is arranged closer to a head of the doubly-linked list.
14. A data storage system, comprising:
a plurality of disks providing a physical storage capacity of the data storage system;
an SSD cache providing a caching medium for the data storage system, the SSD cache including a plurality of cache lines, each cache line having a first predetermined size;
a data storage system computer comprising a processor and a memory in communication with the processor, the memory having computer-executable instructions stored thereon that, when executed by the processor, cause the data storage system computer to:
provide a data structure including a plurality of buckets for managing the SSD cache, each bucket corresponding to at least one contiguous region of the physical storage capacity, the at least one contiguous region of the physical storage capacity having a second predetermined size that is greater than the first predetermined size;
provide a plurality of cache headers for managing the cache lines, each cache header associating a cache line and a corresponding data block stored in the data storage system;
assign two or more cache headers to a same bucket of the data structure, the two or more cache headers being cache headers for cache lines associated with corresponding data blocks stored in a first contiguous region of the physical storage capacity; and
maintain the two or more cache headers as a first group of cache headers within the same bucket of the data structure;
receive an I/O operation directed to a data block stored in the first contiguous region of the physical storage capacity;
obtain a hash value with a hashing algorithm based on the first contiguous region of the physical storage capacity to which the I/O operation is directed;
identify the same bucket of the data structure based on the hash value; and
search the first group of cache headers within the same bucket of the data structure to determine whether the I/O operation is a cache hit or a cache miss.
15. The data storage system of claim 14 , wherein the memory has further computer-executable instructions stored thereon that, when executed by the processor, cause the data storage system computer to maintain a second group of cache headers within the same bucket of the data structure, the second group of cache headers including cache headers for cache lines associated with corresponding data blocks stored in a second contiguous region of the physical storage capacity.
16. The data storage system of claim 15 , wherein the first group of cache headers and the second group of cache headers form a doubly-linked list.
17. The data storage system of claim 16 , wherein the memory has further computer-executable instructions stored thereon that, when executed by the processor, cause the data storage system computer to arrange the first group of cache headers and the second group of cache headers within the doubly-linked list based on a time of last access.