Mapping in a storage system

摘要

A system and method for maintaining a mapping table in a data storage subsystem. A data storage subsystem supports multiple mapping tables. Records within a mapping table are arranged in multiple levels which may be logically ordered by time. Each level stores pairs of a key value and a pointer value. New records are inserted in a created new (youngest) level. All levels other than the youngest may be read only. In response to detecting a flattening condition, a data storage controller is configured to identify a group of two or more adjacent levels of the plurality of levels for flattening which are logically adjacent in time. A new level is created and one or more records stored within the group are stored in the new level, in response to detecting each of the one or more records stores a unique key among keys stored within the group.

主权项

1. A computer system comprising:
a data storage medium; an overlay table; a mapping table organized as a plurality of levels, each level of the plurality of levels comprising one or more mapping table entries, where each of the plurality of entries comprises a tuple including a key; and a data storage controller coupled to the data storage medium; wherein in response to detecting a flattening condition, the data storage controller is configured to:
identify a group of two or more levels of the plurality of levels which are logically adjacent in time;create a new level in the plurality of levels;insert one or more first records stored within the group into the new level, in response to detecting each of the one or more first records stores a unique key among keys stored within the group; andutilize a filtering condition to determine which of the first records are inserted into the new level, wherein the filtering condition comprises a validity of a given record as determined by the overlay table.