Logical sector mapping in a flash storage array

• US 9,454,477 B2
• Filed: 09/04/2014
• Issued: 09/27/2016
• Est. Priority Date: 08/11/2011
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Pure Storage, Inc.
• Inventors: Colgrove, John, Hayes, John, Miller, Ethan, Wang, Feng
• Primary Examiner(s): PORTKA, GARY J
• Application Number:
  US14/477,470
• Publication Number:
  US 20140372689A1
• Time in Patent Office: 754 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 12/1009 using page tables, e.g. page table structures
• CPC Class Codes: G06F 2212/50 Control mechanisms for virtual memory, cache or TLB
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• 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/0665 at area level, e.g. provisioning of virtual or logical volumes
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

A system and method for efficiently performing user storage virtualization for data stored in a storage system including a plurality of solid-state storage devices. A data storage subsystem supports multiple mapping tables. Records within a mapping table are arranged in multiple levels. Each level stores pairs of a key value and a pointer value. The levels are sorted by time. New records are inserted in a created newest (youngest) level. No edits are performed in-place. All levels other than the youngest may be read only. The system may further include an overlay table which identifies those keys within the mapping table that are invalid.

Claims

1. A computing system comprising:

a data storage medium;

a data storage controller coupled to the data storage medium, the controller configured to;

identify a query value corresponding to a read request;

select, in dependence upon the query value, from a plurality of levels within a mapping table, the youngest level associated with the query value; and

search the selected youngest level for an entry that maps the query value to a value corresponding to a location within the data storage medium.

2. The system as recited in claim 1, further comprising

a plurality of processes;

wherein each mapping table entry comprising a tuple including a tuple key value that may be used to identify data stored within the system;

and wherein only a first process of the processes is permitted to modify data corresponding to a first subset of the tuple key values, and only a second process of the processes is permitted to modify data corresponding to a second subset of the key values, wherein the second subset does not overlap the first subset;

wherein levels which are older than a given time may be accessed by multiple processes of the processes without requiring synchronization between the multiple processes.

3. The system as recited in claim 2, wherein the mapping table includes a third subset of the tuple key values different from the first subset and the second subset, wherein a process is not assigned to manage modifications of the third subset of the tuple key values until an update to data corresponding to the third subset is performed.

4. The system as recited in claim 3, wherein prior to a process being assigned to manage modifications of data corresponding to the third subset, any process of the processes may service a read access to the data corresponding to the third subset.

5. The system as recited in claim 2, wherein two or more processes of the plurality of processes may service queries for a given key to multiple levels of the plurality of levels simultaneously.

6. The system as recited in claim 5, wherein a result corresponding to a most recent level of the plurality of levels provided by the two or more processes is selected as the final result.

7. The system as recited in claim 5, wherein the given key corresponds to a subset managed by a particular process and levels in memory are queried by the particular process, and wherein levels which may be cached by other processes may be queried by those other processes.

8. The system as recited in claim 1, wherein levels of the plurality of levels other than the newest level are read only.

9. A method for use in a storage system, the method comprising:

identifying a query value corresponding to a read request;

selecting, in dependence upon the query value, from a plurality of levels within a mapping table, the youngest level associated with the query value; and

searching the selected youngest level for an entry that maps the query value to a value corresponding to a location within the data storage medium.

10. The method as recited in claim 9, further comprising executing a plurality of processes in the system;

wherein each mapping table entry comprising a tuple including a tuple key value that may be used to identify data stored within the system;

and wherein only a first process of the processes is permitted to modify data corresponding to a first subset of the tuple key values, and only a second process of the processes is permitted to modify data corresponding to a second subset of the key values, wherein the second subset does not overlap the first subset;

the method further comprising permitting multiple processes of the processes to access levels which are older than a given time without requiring synchronization between the multiple processes.

11. The method as recited in claim 10, wherein the mapping table includes a third subset of the tuple key values different from the first subset and the second subset, and wherein a process is not assigned to manage modifications of the third subset of the tuple key values until an update to data corresponding to the third subset is performed.

12. The method as recited in claim 11, further comprising permitting any process of the processes to service a read access to the data corresponding to the third subset prior to a process being assigned to manage modifications of data corresponding to the third subset.

13. The method as recited in claim 10, further comprising permitting two or more processes of the plurality of processes to service queries for a given key to multiple levels of the plurality of levels simultaneously.

14. The method as recited in claim 13, further comprising selecting as a final result of two or more processes servicing queries for the given key, a result corresponding to a most recent level of the plurality of levels provided by the two or more processes.

15. The method as recited in claim 13, wherein the given key corresponds to a subset managed by a particular process and levels in memory are queried by the particular process, and wherein levels which may be cached by other processes may be queried by those other processes.

16. The method as recited in claim 9, wherein levels of the plurality of levels other than the newest level are read only.

17. A non-transitory computer readable storage medium storing program instruction executable by a processor to:

identify a query value corresponding to a read request;

select, in dependence upon the query value, from a plurality of levels within a mapping table, the youngest level associated with the query value; and

search the selected youngest level for an entry that maps the query value to a value corresponding to a location within the data storage medium.

18. The storage medium as recited in claim 17, further comprising executing a plurality of processes in the system;

wherein each mapping table entry comprises a tuple including a tuple key value that may be used to identify data stored within the system;

and wherein only a first process of the processes is permitted to modify data corresponding to a first subset of the tuple key values, and only a second process of the processes is permitted to modify data corresponding to a second subset of the key values, wherein the second subset does not overlap the first subset;

wherein the program instructions are further executable to cause multiple processes of the processes to access levels of the time ordered levels which are older than a given time without requiring synchronization between the multiple processes.

19. The storage medium as recited in claim 18, wherein the mapping table includes a third subset of the tuple key values different from the first subset and the second subset, and wherein the program instructions are executable to not assign a process to manage modifications of the third subset of the tuple key values until an update to data corresponding to the third subset is performed.

20. The storage medium as recited in claim 19, wherein the program instructions are further executable to allow any process of the processes to service a read access to the data corresponding to the third subset prior to a process being assigned to manage modifications of data corresponding to the third subset.