Hybrid memory with associative cache

• US 9,785,564 B2
• Filed: 08/20/2013
• Issued: 10/10/2017
• Est. Priority Date: 08/20/2013
• Status: Active Grant

• Current Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Original Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Inventors: Venkata, Sumanth Jannyavula
• Primary Examiner(s): TSAI, SHENG JEN
• Application Number:
  US13/971,778
• Publication Number:
  US 20150058527A1
• Time in Patent Office: 1,512 Days
• Field of Search: 711103, 711128, 711113
• CPC Class Codes: G06F 12/0864 using pseudo-associative means, e.g. set-associative or hashing
• CPC Class Codes: G06F 12/0873 Mapping of cache memory to specific storage devices or parts thereof
• CPC Class Codes: G06F 2212/214 Solid state disk
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages

Abstract

A hybrid memory system includes a primary memory comprising a host memory space arranged as memory sectors corresponding to host logical block addresses (host LBAs). A secondary memory is implemented as a cache for the primary host memory. A hybrid controller is configured directly map the clusters of host LBAs to clusters of secondary memory. The secondary memory clusters correspond to a memory space of the cache. Mapping of the host LBA secondary memory clusters is fully associative such that any host LBA cluster can be mapped to any secondary memory cluster.

Claims

1. A device, comprising:

a primary memory comprising a host memory space arranged as memory sectors corresponding to host logical block addresses (LBAs);

a secondary memory implemented as a cache for the primary host memory;

a hybrid controller configured to;

receive incoming memory access requests from a host processor and to manage outgoing memory access requests routed to the secondary memory;

receive the incoming memory access requests from the host processor, the incoming memory access requests including a range of LBAs;

route the incoming memory access requests to a set of incoming queues by implementing a priority scheme, the set of incoming queues comprising an incoming execute queue, the priority scheme comprising;

routing invalidate requests in an invalidate ready queue to the execute queue as a highest priority;

routing read requests in a read ready queue to the execute queue as a second highest priority; and

routing promotion requests in a promotion ready queue as a third highest priority;

directly map clusters of host LBAs to clusters of secondary memory, the secondary memory clusters corresponding to a memory space of the cache, the mapping of the host LBA clusters to the secondary memory clusters being fully associative wherein any host LBA cluster can be mapped to any secondary memory cluster;

responsive to a promotion request that specifies a cluster aligned host LBA range, use the mapping of the host LBA clusters to the cache clusters to determine if the host LBA range corresponds to one or more overlapped cache clusters present in the secondary memory;

if the host LBA range corresponds to the one or more overlapped cache clusters, create a bitmap of the overlapped cache clusters; and

implement a write operation to the secondary memory using the bitmap to skip writing the overlapped cache clusters to the secondary memory.

2. The device of claim 1, wherein the host LBA clusters comprise n contiguous host LBAs.

3. The device of claim 2, wherein each host LBA is mapped to only one secondary memory cluster at any particular time.

4. The device of claim 2, wherein a hash table maps the host LBA clusters to the secondary memory clusters.

5. The device of claim 4, wherein each entry in the hash table points to one or more secondary memory clusters.

6. The device of claim 3, wherein the hybrid controller is configured to implement one or more of:

a look up request that determines whether a host LBA range is present within the secondary memory;

a read request that reads a host LBA range from the secondary memory;

a promote request that promotes a cluster-aligned host LBA range to the secondary memory; and

an invalidate command that invalidates a cluster-aligned host LBA range in the secondary memory.

7. The device of claim 1, wherein the secondary memory is flash memory and has n planes.

8. The device of claim 7, wherein the secondary memory cluster comprises one or more map units.

9. The device of claim 8, wherein the map unit comprises n pages.

10. A method, comprising:

receiving incoming memory access requests from a host processor, the incoming memory access requests including a range of host logical block addresses (LBAs) corresponding to a host LBA space to cache clusters, the host LBA space corresponding to a memory space of a primary memory and the cache clusters corresponding to memory space of a secondary memory arranged to operate as a fully associative cache for the primary memory, wherein any host LBA cluster can be mapped to any cache cluster;

routing the incoming memory access requests to a set of incoming queues by implementing a priority scheme, the set of incoming queues comprising an incoming execute queue, the priority scheme comprising;

routing invalidate requests in an invalidate ready queue to the execute queue as a highest priority;

routing read requests in a read ready queue to the execute queue as a second highest priority; and

routing promotion requests in a promotion ready queue as a third highest priority;

directly mapping the clusters of LBA to cache clusters

responsive to a promotion request that specifies a cluster aligned host LBA range, using the mapping of the host LBA clusters to the cache clusters to determine if the host LBA range corresponds to one or more overlapped cache clusters present in the secondary memory; and

if the host LBA range corresponds to the one or more overlapped cache clusters, creating a bitmap of the overlapped cache clusters; and

implementing a write operation to the secondary memory using the bitmap to skip writing the overlapped cache clusters to the secondary memory.

11. The method of claim 10, wherein mapping the host LBA clusters to cache clusters comprises implementing a hash function to determine an index to a hash table, the index pointing to one or more cache clusters.

12. The method of claim 10, wherein:

clustering the host LBAs comprises clustering the host LBAs into clusters of n contiguous host LBAs; and

mapping the host LBA clusters to cache clusters comprises mapping the host LBA clusters to cache cluster comprising n contiguous cache clusters.

13. The method of claim 10, further comprising:

responsive to a read request that specifies a host LBA range, using the mapping of the host LBA clusters to the cache clusters to determine if the host LBA range corresponds to cache clusters present in the secondary memory; and

reading the cache clusters if the cache clusters are present in the secondary memory.

14. The method of claim 10, wherein any host LBA cluster can be mapped to any cache cluster if the secondary memory is not saturated.

15. The method of claim 10, further comprising:

responsive to a promotion request that involves a cluster aligned host LBA range, determining if the secondary memory is saturated;

evicting a number of cache clusters if the secondary memory is saturated; and

allocating cache clusters for the promotion request; and

writing the host LBA range to the secondary memory.

16. The method of claim 10, further comprising:

responsive to a invalidate request that involves a cluster aligned host LBA range, using the mapping of the host LBA clusters to the cache clusters to invalidate cache clusters that correspond to the cluster aligned host LBA range.

17. A controller system for a hybrid memory system, the controller comprising:

a hybrid controller configured data transfers between the host processor and a flash memory, the flash memory configured to serve as a cache for a magnetic disk, the hybrid controller comprising;

a flash control and transfer management (FCTM) layer configured to;

receive incoming memory access requests from a host processor and to manage outgoing memory access requests routed to the cache;

receive the incoming memory access requests from the host processor, the incoming memory access requests including a range of LBAs;

route the incoming memory access requests to a set of incoming queues by implementing a priority scheme, the set of incoming queues comprising an incoming execute queue, the priority scheme comprising;

routing invalidate requests in a invalidate ready queue to the execute queue as a highest priority;

routing read requests in a read ready queue to the execute queue as a second highest priority; and

routing promotion requests in a promotion ready queue as a third highest priority;

directly map clusters of host logical block addresses (LBAs) corresponding to a host LBA space to cache clusters, the host LBA space corresponding to a memory space of a primary memory and the cache clusters corresponding to memory space of a secondary memory arranged to operate as a fully associative cache for the primary memory, wherein any host LBA cluster can be mapped to any cache cluster;

responsive to a promotion request that specifies a cluster aligned host LBA range, use the mapping of the host LBA clusters to the cache clusters to determine if the host LBA range corresponds to one or more overlapped cache clusters present in the secondary memory; and

if the host LBA range corresponds to the one or more overlapped cache clusters, create a bitmap of the overlapped cache clusters; and

implement a write operation to the secondary memory using the bitmap to skip writing the overlapped cache clusters to the secondary memory.

18. The controller system of claim 17, wherein the host LBA clusters comprise n contiguous host LBAs.

19. The method of claim 17, wherein the FCTM layer is configured to directly map the host LBA clusters to cache clusters by implementing a hash function to determine an index to a hash table, the index pointing to one or more cache clusters.