Logical sector mapping in a flash storage array

Patent metadata

Field	Value
Publication number	US-9454476-B2
Application number	US-201414312088-A
Country	US
Kind code	B2
Filing date	Jun 23, 2014
Priority date	Aug 11, 2011
Publication date	Sep 27, 2016
Grant date	Sep 27, 2016

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.

First claim

What is claimed is:

1. A computer system comprising:
a data storage medium;
a data storage controller coupled to the data storage medium; and
a mapping table that includes a plurality of levels, each level comprising one or more mapping table entries, wherein each respective mapping table entry corresponds to a respective mapping from a respective logical address to a respective physical address;
wherein the data storage controller is configured to:
receive a request, wherein the request indicates a logical address;
generate, in dependence upon the logical address, a query key; and
determine, in dependence upon the query key, a youngest level of the plurality of levels that includes a mapping table entry corresponding to a mapping from the logical address to a physical address.

2. The computer system as recited in claim 1 , further comprising a cache configured to store a cached copy of at least a portion of the mapping table.

3. The computer system as recited in claim 1 , wherein each level of the plurality of levels is associated with a particular time period encompassing addition of one or more mapping table entries.

4. The computer system as recited in claim 3 , wherein the controller is configured to sort each level by a key value.

5. The computer system as recited in claim 4 , wherein entries of the mapping table are grouped into pages, and wherein a result of generating the query key is utilized to retrieve a particular page of the pages.

6. The computer system as recited in claim 5 , wherein in response to receiving the particular page, the controller is configured to use the query key to identify a mapping within the particular page, the mapping including an identification of a location of a data item stored in the storage medium that corresponds to the query key.

7. The computer system as recited in claim 1 , wherein the data storage controller is further configured to:
create a new level to be added to the plurality of levels, in response to detecting a condition for inserting one or more new mapping table entries in the mapping table; and
insert the one or more new mapping table entries in the new level.

8. The computer system as recited in claim 1 , wherein each of the mapping table entries further comprise an indication as to where the user data corresponding to a given key is stored on the data storage medium.

9. The computer system as recited in claim 8 , wherein the data storage medium comprises one or more solid state storage devices.

10. The computer system as recited in claim 1 , wherein all levels of the plurality of the levels other than a youngest level are read only.

11. The computer system as recited in claim 1 , wherein each mapping table entry comprising a tuple, and each tuple including a key; the system further comprising an overlay table that overlays the mapping table, wherein the overlay table and mapping table are indexed by different keys.

12. The computer system as recited in claim 11 , wherein the overlay table identifies one or more tuples in the mapping table that are not valid.

13. The computer system as recited in claim 11 , wherein the overlay table contains one or more entries that correspond to a range of values.

14. The computer system as recited in claim 11 , wherein the entry in the overlay table can be used to modify one or fields in a tuple returned from the mapping table in response to a query.

15. The computer system as recited in claim 11 , wherein the key used to index the overlay table is generated from fields in the key used to access the mapping table.

16. The computer system as recited in claim 11 , wherein the key used to index the overlay table is generated from fields in the tuple resulting from accessing the mapping table.

17. The computer system as recited in claim 11 , further comprising a cache configured to store a cached copy of at least a portion of the overlay table.

18. The computer system as recited in claim 11 , wherein the overlay table is organized as a plurality of time ordered levels, each level comprising one or more overlay table entries.

19. A method comprising:
storing a mapping table that includes a plurality of levels, each level comprising one or more mapping table entries, wherein each respective mapping table entry corresponds to a respective mapping from a respective logical address to a respective physical address;
receiving a request, wherein the request indicates a logical address;
generating, in dependence upon the logical address, a query key; and
determining, in dependence upon the query key, a youngest level of the plurality of levels that includes a mapping table entry corresponding to a mapping from the logical address to a physical address.

20. The method as recited in claim 19 , further comprising storing a cached copy of at least a portion of the mapping table.

21. The method as recited in claim 19 , wherein each level of the plurality of levels is associated with a particular time period encompassing addition of one or more mapping table entries.

22. The method as recited in claim 21 , further comprising sorting each level by a key value.

23. The method as recited in claim 22 , wherein the mapping table entries of the mapping table are grouped into pages, and wherein a result of generating the query key is utilized to retrieve a particular page of the pages.

24. The method as recited in claim 19 , further comprising:
creating a new level to be added to the plurality of levels, in response to detecting a condition for inserting one or more new mapping table entries in the mapping table; and
inserting the one or more new mapping table entries in the new level.

25. The method as recited in claim 19 , wherein each of the mapping table entries further comprise an indication as to where the user data corresponding to a given key is stored on a data storage medium.

26. The method as recited in claim 25 , wherein the data storage medium comprises one or more solid state storage devices.

27. The method as recited in claim 19 , wherein all levels of the plurality of the levels other than a youngest level are read only.

28. The method as recited in claim 19 , wherein each mapping table entry comprising a tuple, and each tuple including a key; the method further comprising an overlay table that overlays the mapping table, wherein the overlay table and mapping table are indexed by different keys.

29. The method as recited in claim 28 , wherein the overlay table identifies one or more tuples in the mapping table that are not valid.

30. The method as recited in claim 28 , wherein the overlay table contains one or more entries that correspond to a range of values.

31. The method as recited in claim 28 , further comprising using the entry in the overlay table to modify one or fields in a tuple returned from the mapping table in response to a query.

32. The method as recited in claim 28 , wherein the key used to index the overlay table is generated from fields in the key used to access the mapping table.

33. The method as recited in claim 28 , wherein the key used to index the overlay table is generated from fields in the tuple resulting from accessing the mapping table.

34. A non-transitory computer readable storage medium storing program instr

Assignees

• Pure Storage Inc

Inventors

• Colgrove John
• Hayes John
• Miller Ethan
• Wang Feng

Classifications

• G06F3/0638

  Organizing or formatting or addressing of data · CPC title

• G06F12/1009

  using page tables, e.g. page table structures · CPC title

• G06F3/0608 Primary

  Saving storage space on storage systems · CPC title

• G06F16/1748

  De-duplication implemented within the file system, e.g. based on file segments (de-duplication techniques in storage systems for the management of data blocks G06F3/0641) · CPC title

• G06F12/0246 Primary

  in block erasable memory, e.g. flash memory · CPC title