Convertible leaf memory mapping

• US 9,619,165 B1
• Filed: 10/30/2015
• Issued: 04/11/2017
• Est. Priority Date: 10/30/2015
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Inventors: Shelton, Lance
• Primary Examiner(s): Yu, Jae
• Application Number:
  US14/929,171
• Publication Number:
  US 20170123705A1
• Time in Patent Office: 529 Days
• Field of Search: 711103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0629 Configuration or reconfiguration of storage systems
• CPC Class Codes: G06F 3/0638 Organizing or formatting or addressing of data
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]

Abstract

Systems, methods and/or devices are used to store metadata in a storage system. In one aspect, an indication of data to be stored by the storage system is received by a computing device including non-volatile memory and a tiered data structure. A leaf having a first leaf type is selected from the tiered data structure. Leaves of the first leaf type include locations of variable-length data stored in the non-volatile memory. At least one criterion is used to determine whether to convert the selected leaf to a converted leaf having a second leaf type. Leaves of the second type include locations of fixed-length data. In response to a determination to convert the selected leaf to a converted leaf, first location information is stored in the converted leaf. In response to a determination to not convert the selected leaf, second location information is stored in the second leaf.

Claims

1. A method of storing metadata, the method comprising:

at a computing device of a storage system including non-volatile memory and a tiered data structure, wherein the tiered data structure includes a plurality of leaves;

receiving an indication of data to be stored by the storage system;

selecting, from the plurality of leaves, a leaf to store location information for the data to be stored, wherein the selected leaf has a first leaf type, wherein leaves of the first leaf type include entries indicating locations of variable-length data stored in the non-volatile memory;

determining, using at least one first-type to second-type criterion, whether to convert the selected leaf to a converted leaf, wherein the converted leaf has a second leaf type, wherein leaves of the second type include entries indicating locations of fixed-length data stored in the non-volatile memory;

in response to a determination to convert the selected leaf to a converted leaf, storing, in the converted leaf, first location information of the data to be stored; and

in response to a determination to not convert the selected leaf, storing, in the selected leaf, second location information of the data to be stored.

2. The method of claim 1, wherein the first location information includes a physical address of the data to be stored, and the second location information includes the physical address of the data to be stored and at least one of:

a logical block address of the data to be stored, or

an indication of length of the data to be stored.

3. The method of claim 1, wherein the tiered data structure includes at least one leaf of the first leaf type and at least one leaf of the second leaf type, wherein the at least one leaf of the second leaf type stores a base logical address and a sequence of fixed-size entries, where each fixed-size entry for a mapped location includes a physical block address.

4. The method of claim 1, wherein the at least one first-type to second-type criterion includes a criterion that is satisfied in accordance with an indication that an insertion into the selected leaf will cause the selected leaf to split.

5. The method of claim 1, wherein the at least one first-type to second-type criterion includes a criterion that is satisfied in accordance with:

a determination of a total size of;

potential new entries for the selected leaf, indicating locations of the data to be stored, and

existing entries, if any, in the selected leaf; and

a determination that the determined total size is less than or equal to a maximum size for all entries of a leaf of the second leaf type.

6. The method of claim 1, further comprising:

determining, using at least one second-type to first-type criterion, whether to revert a leaf of the second type into a new leaf of the first leaf type.

7. The method of claim 6, wherein the leaf of the second leaf type has entries for a first number of locations, and the at least one second-type to first-type criterion includes a criterion that is satisfied in accordance with a determination that the new leaf of the first type has sufficient space to contain entries for all mapped locations indicated by the entries of the leaf of the second leaf type plus a predefined margin.

8. The method of claim 6, wherein determining whether to revert the leaf of the second type into the new leaf of the first type occurs in response to an indication of data to be deleted or unmapped by the storage system and wherein the leaf of the second type contains location information for the data to be deleted or unmapped.

9. The method of claim 6, wherein the determining whether to revert the leaf of the second type into the new leaf of the first type occurs in response to an indication of data to be overwritten by the storage system and wherein the leaf of the second type contains location information for the data to be overwritten.

10. The method of claim 1, wherein one or more of the receiving, selecting, determining, storing in the converted leaf, or storing in the selected leaf are performed by a storage device of the storage system, wherein the storage device stores the data to be stored.

11. The method of claim 1, wherein one or more of the receiving, selecting, determining, storing in the converted leaf, or storing in the selected leaf are performed by one or more subsystems of the storage system distinct from a storage device, wherein the storage device stores the data to be stored.

12. A storage device, comprising:

non-volatile memory; and

a controller having one or more processors and controller memory storing one or more programs, which when executed by the one or more processors, cause the storage device to;

receive an indication of data to be stored by the storage device;

select, from the plurality of leaves, a leaf to store location information for the data to be stored, wherein the selected leaf has a first leaf type, wherein leaves of the first leaf type include entries indicating locations of variable-length data stored in the non-volatile memory;

determine, using at least one first-type to second-type criterion, whether to convert the selected leaf to a converted leaf, wherein the converted leaf has a second leaf type, wherein leaves of the second type include entries indicating locations of fixed-length data stored in the non-volatile memory;

in response to a determination to convert the selected leaf to a converted leaf, store, in the converted leaf, first location information of the data to be stored; and

in response to a determination to not convert the selected leaf, store, in the selected leaf, second location information of the data to be stored.

13. The storage device of claim 12, wherein the selected leaf comprises a leaf node of a tiered data structure stored in the non-volatile memory, and the controller includes a tiered data structure module that stores and retrieves information within the tiered data structure.

14. The storage device of claim 12, wherein the first location information includes a physical address of the data to be stored, and the second location information includes the physical address of the data to be stored and at least one of:

a logical block address of the data to be stored, or

an indication of length of the data to be stored.

15. The storage device of claim 12, wherein the tiered data structure includes at least one leaf of the first leaf type and at least one leaf of the second leaf type, wherein the at least one leaf of the second leaf type stores a base logical address and a sequence of fixed-size entries, where each fixed-size entry for a mapped location includes a physical block address.

16. The storage device of claim 12, wherein the at least one first-type to second-type criterion includes a criterion that is satisfied in accordance with an indication that an insertion into the selected leaf will cause the selected leaf to split.

17. The storage device of claim 12, wherein the at least one first-type to second-type criterion includes a criterion that is satisfied in accordance with:

a determination of a total size of;

potential new entries for the selected leaf, indicating locations of the data to be stored, and

existing entries, if any, in the selected leaf; and

a determination that the determined total size is less than or equal to a maximum size for all entries of a leaf of the second leaf type.

18. The storage device of claim 12, wherein the one or more programs, when executed by the one or more processors, further cause the storage device to determine, using at least one second-type to first-type criterion, whether to revert a leaf of the second type into a new leaf of the first leaf type.

19. The storage device of claim 18, wherein the leaf of the second leaf type has entries for a first number of locations, and the at least one second-type to first-type criterion includes a criterion that is satisfied in accordance with a determination that the new leaf of the first type has sufficient space to contain entries for all mapped locations indicated by the entries of the leaf of the second leaf type plus a predefined margin.

20. A non-transitory computer readable storage medium, storing one or more programs configured for execution by one or more processors of the controller of a storage device, the storage device including non-volatile memory, the one or more programs including instructions that when executed by the one or more processors, cause the storage device to:

receive an indication of data to be stored by the storage device;

select, from the plurality of leaves, a leaf to store location information for the data to be stored, wherein the selected leaf has a first leaf type, wherein leaves of the first leaf type include entries indicating locations of variable-length data stored in the non-volatile memory;

determine, using at least one first-type to second-type criterion, whether to convert the selected leaf to a converted leaf, wherein the converted leaf has a second leaf type, wherein leaves of the second type include entries indicating locations of fixed-length data stored in the non-volatile memory;

in response to a determination to convert the selected leaf to a converted leaf, store, in the converted leaf, first location information of the data to be stored; and

in response to a determination to not convert the selected leaf, store, in the selected leaf, second location information of the data to be stored.

21. The non-transitory computer readable storage medium of claim 20, wherein the selected leaf comprises a leaf node of a tiered data structure stored in the non-volatile memory, and the controller includes a tiered data structure module that stores and retrieves information within the tiered data structure.