US 10,254,964 B1 · Managing mapping information in a storage system

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.

Claims20

Dependent claims

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, wherein the condition includes a time needed to search multiple levels in a mapping table exceeding a threshold;
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;
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 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.

6 more elements

An apparatus for use in a storage system that includes a plurality of storage devices, the apparatus including a computer processor and a computer memory, the computer memory including computer program instructions that, when executed by the computer processor, cause the storage system 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, wherein the condition includes a time needed to search multiple levels in a mapping table exceeding a threshold;
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;
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 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.

6 more elements

Dependencies are inferred from the claim text.

Managing mapping information in a storage system

Life of this patent

Managing mapping information in a storage system

Life of this patent

Abstract

Claims20