Optimizing flattening in a multi-level data structure

• US 9,977,600 B1
• Filed: 06/30/2017
• Issued: 05/22/2018
• Est. Priority Date: 11/24/2014
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Pure Storage, Inc.
• Inventors: Sanvido, Marco, Hankins, Richard, McAuliffe, Mark, Vachharajani, Neil
• Primary Examiner(s): Thammavong, Prasith
• Assistant Examiner(s): Kwong, Edmund H
• Application Number:
  US15/638,912
• Time in Patent Office: 326 Days
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/0238 Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory
• CPC Class Codes: G06F 12/0292 using tables or multilevel address translation means G06F12/023 takes precedence; address translation in virtual memory systems G06F12/10
• CPC Class Codes: G06F 12/121 using replacement algorithms
• CPC Class Codes: G06F 2212/401 Compressed data
• 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/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0665 at area level, e.g. provisioning of virtual or logical volumes
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

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.

Claims

1. A node-based storage cluster, the node-based storage cluster configured to:

detect a condition for flattening two or more levels within a multi-level data structure that includes a plurality of levels, where 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; and

responsive to detecting the condition;

select two or more levels for flattening;

create a new level to be added to the multi-level data structure;

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;

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;

receive, from each node in the node-based storage cluster, verification that the node is ready to utilize the new level; and

remove, from the node-based storage cluster, the two or more levels for flattening, including archiving the two or more levels for flattening in offline storage.

2. The node-based storage cluster as recited in claim 1, wherein the plurality of levels are organized based on temporal relationships between the levels.

3. The node-based storage cluster as recited in 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.

4. The node-based storage cluster as recited in 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.

5. The node-based storage cluster as recited in claim 3, wherein the node-based storage cluster 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.

6. The node-based storage cluster as recited in claim 1, wherein the condition for flattening the two or more levels comprises an amount of memory used to store the plurality of levels exceeds a threshold.

7. The node-based storage cluster as recited in claim 1, wherein the condition for flattening the two or more levels comprises a time to search for a given key in the plurality of levels exceeds a threshold.

20. The node-based storage cluster of claim 1, wherein the multi-level data structure is an append log.

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

detecting a condition for flattening two or more levels within a multi-level data structure, where 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; and

responsive to detecting the condition;

selecting two or more levels for flattening;

creating a new level to be added to the multi-level data structure;

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;

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;

receiving, from each node in the node-based storage cluster, verification that the node is ready to utilize the new level; and

removing, from the node-based storage cluster, the two or more levels for flattening, including archiving the two or more levels for flattening in offline storage.

9. The method as recited in claim 8, wherein the plurality of levels are organized based on temporal relationships between the levels.

10. The method as recited in 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.

11. The method as recited in 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.

12. The method as recited in 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 mapping table.

13. The method as recited in claim 8, wherein the condition for flattening the two or more levels comprises an amount of memory used to store the plurality of levels exceeds a threshold.

14. The method as recited in claim 8, wherein each of the one or more entries is associated with a key value and entries within a level are sorted by key value.

15. The method as recited in claim 8, wherein the condition for flattening the two or more levels comprises a time to search for a given key in the plurality of levels exceeds a threshold.

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

detect a condition for flattening two or more levels within a multi-level data structure, where 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; and

responsive to detecting the condition;

select two or more levels for flattening;

create a new level to be added to the multi-level data structure;

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;

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;

receive, from each node in the node-based storage cluster, verification that the node is ready to utilize the new level; and

remove, from the node-based storage cluster, the two or more levels for flattening, including archiving the two or more levels for flattening in offline storage.

17. The computer readable storage medium as recited in claim 16, wherein the plurality of levels are organized based on temporal relationships between the levels.

18. The computer readable storage medium as recited in claim 16, 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.

19. The computer readable storage medium as recited in claim 16, 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.