Metadata management in a storage system

Patent metadata

Field	Value
Publication number	US-11662909-B2
Application number	US-202217667756-A
Country	US
Kind code	B2
Filing date	Feb 9, 2022
Priority date	Nov 24, 2014
Publication date	May 30, 2023
Grant date	May 30, 2023

Abstract

A system and method for efficiently maintaining metadata stored among 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 at least pairs of a key value and a physical pointer value. The levels are sorted by time. New records are inserted in a created new highest (youngest) level. No edits are performed in-place. A data storage controller determines both a cost of searching a given table exceeds a threshold and an amount of memory used to flatten levels exceeds a threshold. In response, the controller incrementally flattens selected levels within the table based on key ranges. After flattening the records in the selected levels within the key range, the records may be removed from the selected levels. The process repeats with another different key range.

First claim

The invention claimed is:

1. A storage node configured to:
detect a condition for flattening two or more levels within a multi-level data structure that includes a plurality of levels; and
responsive to detecting the condition:
select two or more levels for flattening;
determine a key range with each of the two or more levels that is smaller than a complete level for incremental flattening;
create a subset of a new level to be added to the multi-level data structure, wherein the new level includes all valid entries from the key range in the two or more levels; and
remove the key range of the two or more levels for incremental flattening, including archiving the key range of the two or more levels for incremental flattening in external storage.

2. The storage node of claim 1 wherein each level includes one or more entries and each entry within a level is associated with a key that is unique from all other entries in the level.

3. The storage node of claim 1 , wherein the storage node is further configured to:
insert, within the new level, each entry in the two or more levels whose key does not match the key of any other entry in the two or more levels; and
insert, within the new level, each valid entry in the two or more levels whose key does match the key of another entry in the two or more levels.

4. The storage node of claim 1 wherein the plurality of levels are organized based on temporal relationships between the levels.

5. The storage node of claim 1 wherein the entry in the two or more levels whose key does match the key of another entry in the two or more levels is valid if the entry is included within a more recent level than any other entries in the two or more levels that are associated with the same key.

6. The storage node of claim 1 wherein the entry in the two or more levels whose key does match the key of another entry in the two or more levels is invalid if the entry is included within a less recent level than any other entries in the two or more levels that are associated with the same key.

7. The storage node of claim 1 wherein the storage node is further configured to select the two or more levels based at least in part on an age of the two or more levels relative to other levels in the multi-level data structure.

8. A method comprising:
detecting a condition for flattening two or more levels within a multi-level data structure that includes a plurality of levels; and
responsive to detecting the condition:
selecting two or more levels for flattening;
determining a key range with each of the two or more levels that is smaller than a complete level for incremental flattening;
creating a subset of a new level to be added to the multi-level data structure, wherein the new level includes all valid entries from the key range in the two or more levels; and
removing the key range of the two or more levels for incremental flattening, including archiving the key range of the two or more levels for incremental flattening in external storage.

9. The method of claim 8 wherein each level includes one or more entries and each entry within a level is associated with a key that is unique from all other entries in the level.

10. The method of claim 8 further comprising:
inserting, within the new level, each entry in the two or more levels whose key does not match the key of any other entry in the two or more levels; and
inserting, within the new level, each valid entry in the two or more levels whose key does match the key of another entry in the two or more levels.

11. The method of claim 8 wherein the plurality of levels are organized based on temporal relationships between the levels.

12. The method of claim 8 wherein the entry in the two or more levels whose key does match the key of another entry in the two or more levels is valid if the entry is included within a more recent level than any other entries in the two or more levels that are associated with the same key.

13. The method of claim 8 wherein the entry in the two or more levels whose key does match the key of another entry in the two or more levels is invalid if the entry is included within a less recent level than any other entries in the two or more levels that are associated with the same key.

14. The method of claim 8 further comprising selecting the two or more levels based at least in part on an age of the two or more levels relative to other levels in the multi-level data structure.

15. An apparatus that includes a computer processor and a computer memory, the computer memory including computer program instructions that, when executed by the computer processor, cause the apparatus to carry out the steps of:
detecting a condition for flattening two or more levels within a multi-level data structure that includes a plurality of levels; and
responsive to detecting the condition:
selecting two or more levels for flattening;
determining a key range with each of the two or more levels that is smaller than a complete level for incremental flattening;
creating a subset of a new level to be added to the multi-level data structure, wherein the new level includes all valid entries from the key range in the two or more levels; and
removing the key range of the two or more levels for incremental flattening, including archiving the key range of the two or more levels for incremental flattening in offline storage.

16. The apparatus of claim 15 wherein each level includes one or more entries and each entry within a level is associated with a key that is unique from all other entries in the level.

17. The apparatus of claim 15 further comprising computer program instructions that, when executed by the computer processor, cause the storage system to carry out the steps of:
inserting, within the new level, each entry in the two or more levels whose key does not match the key of any other entry in the two or more levels; and
inserting, within the new level, each valid entry in the two or more levels whose key does match the key of another entry in the two or more levels.

18. The apparatus of claim 15 wherein the plurality of levels are organized based on temporal relationships between the levels.

19. The apparatus of claim 15 wherein the entry in the two or more levels whose key does match the key of another entry in the two or more levels is valid if the entry is included within a more recent level than any other entries in the two or more levels that are associated with the same key.

20. The apparatus of claim 15 wherein the entry in the two or more levels whose key does match the key of another entry in the two or more levels is invalid if the entry is included within a less recent level than any other entries in the two or more levels that are associated with the same key.

Assignees

• Pure Storage Inc

Inventors

• Sanvido Marco
• Hankins Richard
• Mcauliffe Mark
• Vachharajani Neil

Classifications

• G06F3/0641

  De-duplication techniques · CPC title

• G06F3/0665

  at area level, e.g. provisioning of virtual or logical volumes · CPC title

• G06F3/0689

  Disk arrays, e.g. RAID, JBOD · CPC title

• G06F12/0292 Primary

  using tables or multilevel address translation means (G06F12/023 takes precedence; address translation in virtual memory systems G06F12/10) · CPC title

• G06F12/0238

  Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory · CPC title