MAPPING IN A STORAGE SYSTEM
First Claim
1. A computer system comprising:
- a data storage medium;
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; and
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.
1 Assignment
0 Petitions
Accused Products
Abstract
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.
-
Citations
35 Claims
-
1. A computer system comprising:
-
a data storage medium; 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; and 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
-
-
19. A method for use in a storage system, the method comprising:
-
storing 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 responsive to detecting a flattening condition; identifying a group of two or more levels of the plurality of levels which are logically adjacent in time; creating a new level in the plurality of levels; and inserting 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. - View Dependent Claims (20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31)
-
-
32. A non-transitory computer readable storage medium storing program instruction executable by a processor to:
-
store 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 responsive to detecting a flattening condition; 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; and 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. - View Dependent Claims (33, 34, 35)
-
Specification