Metadata rewrite and flatten optimization
First Claim
1. A node-based storage cluster, the node-based storage cluster configured to:
- detect a condition for flattening two or more levels within a mapping table that includes a plurality of levels, 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; and
responsive to detecting the condition;
select two or more levels for flattening;
create a new level to be added to the mapping table;
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
19 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 mapping table that includes a plurality of levels, 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; and responsive to detecting the condition; select two or more levels for flattening; create a new level to be added to the mapping table; 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. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A method for use in a storage system, the method comprising:
-
detecting a condition for flattening two or more levels within a mapping table that includes a plurality of levels, 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; and responsive to detecting the condition; selecting two or more levels for flattening; creating a new level to be added to the mapping table; 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; and removing the two or more levels for flattening, including archiving the two or more levels for flattening in offline storage. - View Dependent Claims (9, 10, 11, 12, 13, 14, 15)
-
-
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 mapping table that includes a plurality of levels, 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; and responsive to detecting the condition; select two or more levels for flattening; create a new level to be added to the mapping table; 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 remove the two or more levels for flattening, including archiving the two or more levels for flattening in offline storage. - View Dependent Claims (17, 18, 19)
-
Specification