Mapping engine for a storage device

• US 9,069,676 B2
• Filed: 02/12/2013
• Issued: 06/30/2015
• Est. Priority Date: 06/03/2009
• Status: Expired due to Fees

• Current Assignee: Violin Systems LLC
• Original Assignee: Violin Memory Incorporated
• Inventors: de la Iglesia, Erik, Sikdar, Som, Parker, David, Dommeti, Sivaram
• Primary Examiner(s): ELMORE, STEPHEN C
• Application Number:
  US13/764,975
• Publication Number:
  US 20140229653A1
• Time in Patent Office: 868 Days
• Field of Search: 711/118, 711/3, 711/4, 711/103, 711/112, 711/114, 711/154, 711/156, 711/205, 711/206, 711/207, 365/185.33
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 12/0871 Allocation or management of cache space

Abstract

A hardware search structure determines the status of cache lines associated with a large disk array and at the same time reduces the amount of memory space needed for tracking the status. The search structure is configurable in hardware to different cache line sizes and different primary and secondary index sizes. A maintenance feature invalidates state record entries based both on their time stamps and on associated usage statistics.

Claims

1. A apparatus disposable between a user device and a storage array, comprising:

a processor having;

a proxy engine configured to receive a message from the user device and interpret the message in accordance with a message protocol to perform storage operations associated with a storage address in the storage array;

a mapping engine configured to map the storage address to a state record within a state records table, the state record corresponding to a cache line stored in a cache resource;

a search data structure for locating the state record corresponding to the stored cache line,

wherein the cache resource is managed in accordance with a policy.

2. The apparatus according to claim 1, wherein the search data structure includes a primary index table addressed by a first portion of the storage address and a secondary index table addressed by the second portion of the storage address.

3. The apparatus according to claim 2, wherein the state records table is addressed by an address offset of a third portion of the storage address.

4. The apparatus of claim 3, wherein the size of the first portion, the size of the second portion and the size of the third portion is adjustable.

5. The apparatus according to claim 2, wherein the primary index table includes primary index entries that contain at least one of an address or an address offset to a group of entries in the secondary index table and the secondary index table is configured to store pointers that contain at least one of an address or an address offset of a state record in the state records table.

6. The apparatus according to claim 1, wherein the cache resource is a solid state memory.

7. The apparatus according to claim 6, wherein the solid state memory is a solid state disk.

8. The apparatus of claim 1, wherein the storage array is a memory system in communication with the apparatus.

9. The apparatus of claim 8, wherein the storage array is a disk memory system.

10. The apparatus of claim 1, wherein the cache line size is dynamically adjustable.

11. The apparatus according to claim 1, wherein the search data structure is configured to manage cache resources by executing a policy based on a plurality of measures of cache line activity.

12. The apparatus according to claim 11, wherein the management of the cache resources includes the step of one of invalidating the cache line or updating a time interval counter for the cache line in the state table.

13. The apparatus according to claim 11, wherein at least one of the measures is a statistical measure.

14. The apparatus processor according to claim 1, wherein the processor is configured to update the search data structure responsive to the completion of a storage operation initiated by the processor.

15. A method, comprising:

configuring a processor to perform the steps of;

receiving a message having a storage operation request having a storage address;

addressing a primary index table with a primary index address of the storage address;

using a primary index entry addressed in the primary index table to address an index group in a secondary index table;

identifying a pointer in the addressed index group with a secondary index address of the storage address;

using the identified pointer to address a state record entry in a state record table; and

updating the state record table.

16. The method according to claim 15, further comprising invalidating the state record entry according to both a time stamp value in the state record entry and cache line access statistics in the state record entry.

17. The method according to claim 15, further comprising storing a cache line corresponding to the storage address in a cache resource.

18. The method according to claim 15, further comprising dynamically determining a cache line size based on an average number of blocks of data accessed by the received storage address.

19. The method of claim 16, further comprising adjusting the cache line access statistics in accordance with a policy.