Hybrid memory with associative cache

• US 9,390,020 B2
• Filed: 07/06/2012
• Issued: 07/12/2016
• Est. Priority Date: 07/06/2012
• Status: Active Grant

• Current Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Original Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Inventors: Jannyavula Venkata, Sumanth
• Primary Examiner(s): Thammavong, Prasith
• Application Number:
  US13/543,079
• Publication Number:
  US 20140013025A1
• Time in Patent Office: 1,467 Days
• Field of Search: 711/103
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0873 Mapping of cache memory to specific storage devices or parts thereof
• CPC Class Codes: G06F 2212/205 Hybrid memory, e.g. using both volatile and non-volatile memory
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0638 Organizing or formatting or addressing of data
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/068 Hybrid storage device

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 map the clusters of host LBAs to clusters of solid state drive (SSD) LBAs. The SSD LBAs correspond to a memory space of the cache. Mapping of the host LBA clusters to the SSD LBA clusters is fully associative such that any host LBA cluster can be mapped to any SSD LBA 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; and

a hybrid controller configured to;

map clusters of host LBAs to clusters of solid state drive (SSD) LBAs, the SSD LBAs corresponding to a memory space of the cache, the mapping of the host LBA clusters to the SSD LBA clusters being fully associative wherein any host LBA cluster can be mapped to any SSD LBA cluster;

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

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

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

2. The device of claim 1, wherein:

the host LBA clusters comprise n contiguous host LBAs; and

the SSD LBA clusters comprise n contiguous SSD LBAs.

3. The device of claim 2, wherein n is not a power of two.

4. The device of claim 2, wherein a host LBA does not span multiple host LBA clusters.

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

6. The device of claim 2, wherein a hash table maps the host LBA clusters to the SSD LBA clusters.

7. The device of claim 6, wherein each entry in the hash table points to one or more SSD LBA clusters.

8. The device of claim 7, wherein a linked list points to multiple SSD LBA clusters mapped to one entry in the hash table.

9. The device of claim 8, wherein a predetermined number of bits of a host LBA is used as index in the hash table.

10. The device of claim 5, 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.

11. A method, comprising:

mapping clusters of host logical block addresses (LBAs) corresponding to a host LBA space to solid state drive (SSD) LBA clusters, the host LBA space corresponding to a memory space of a primary memory and the SSD LBA 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 SSD LBA cluster;

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

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

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

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

13. The method of claim 11, wherein:

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

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

14. The method of claim 11, further comprising:

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

reading the SSD LBAs if the SSD LBAs are present in the secondary memory.

15. The method of claim 11, 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 SSD LBA clusters if the secondary memory is saturated; and

allocating SSD LBA clusters for the promotion request; and

writing the host LBA range to the secondary memory.

16. The method of claim 11, 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 SSD LBA clusters to invalidate SSD LBA clusters that correspond to the cluster aligned host LBA range.

17. The method of claim 11, wherein any host LBA cluster can be mapped to any SSD LBA cluster if the secondary memory is not saturated.

18. A device, comprising:

a hard magnetic disk drive (HDD) comprising a memory space arranged as memory sectors corresponding to host logical block addresses (LBAs);

flash memory implemented as a cache for the HDD; and

a hybrid controller configured to;

map the clusters of host LBAs to clusters of solid state drive (SSD) LBAs, the SSD LBAs corresponding to a memory space of the flash memory, the mapping of the host LBA clusters to the SSD LBA clusters being fully associative wherein any host LBA cluster can be mapped to any SSD LBA cluster

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

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

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

19. The device of claim 18, 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 flash memory;

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

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

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