# US 8,788,788 B2 · Logical sector mapping in a flash storage array > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,788,788 B2 - Document ID: US8788788B2 - Status: Granted - Kind: B2 - Application number: 13/208,094 - Filed: 2011-08-11 - Published: 2013-02-14 - Granted: 2014-07-22 - Earliest claimed: 2011-08-11 - Assignees: Pure Storage, Inc. - Applicants: John Colgrove; John Hayes; Ethan Miller; Feng Wang - Inventors: John Colgrove; John Hayes; Ethan Miller; Feng Wang - Web page: https://patentgrep.com/patent/US8788788B2 ## CPC - G06F 12/0246: {in block erasable memory, e.g. flash memory} - G06F 3/0608: {Saving storage space on storage systems} - G06F 3/061: {Improving I/O performance} - G06F 3/0638: {Organizing or formatting or addressing of data} - G06F 3/0665: {at area level, e.g. provisioning of virtual or logical volumes} - G06F 3/067: {Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]} - G06F 12/0802: Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches - G06F 12/1009: using page tables, e.g. page table structures - G06F 2212/50: Control mechanisms for virtual memory, cache or TLB - G06F 2212/7201: Logical to physical mapping or translation of blocks or pages - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A system and method for efficiently performing user storage virtualization for data stored in a storage system including 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 pairs of a key value and a pointer value. The levels are sorted by time. New records are inserted in a created newest (youngest) level. No edits are performed in-place. All levels other than the youngest may be read only. The system may further include an overlay table which identifies those keys within the mapping table that are invalid. ## Claims ### Claim 1 A computer system comprising: a data storage medium; a data storage controller coupled to the data storage medium; and a mapping table that includes a plurality of entries, each of the mapping table entries comprising a tuple including a key; wherein the mapping table is organized as a hierarchy including a plurality of time ordered levels such that younger levels of the plurality of time ordered levels appear higher in the hierarchy than older levels of the plurality of time ordered levels, each level comprising one or more mapping table entries; wherein in response to receiving a request comprising a first key, the data storage controller is configured to: determine if a duplicate key corresponding to the first key exists in the mapping table; and create a new level to be added to the plurality of levels, in response to determining the duplicate key exists. ### Claim 2 (depends on 1) The computer system as recited in claim 1, further comprising a cache configured to store a cached copy of at least a portion of the mapping table. ### Claim 3 (depends on 1) The computer system as recited in claim 1, wherein in response to receiving a request, the data storage controller is further configured to: access the mapping table with at least a given key corresponding to the request; identify one or more entries that correspond to the given key; determine which of the one or more entries corresponds to a youngest level of the time ordered levels; and return an entry that corresponds to the youngest level of the time ordered levels to satisfy the request. ### Claim 4 (depends on 3) The computer system as recited in claim 3, wherein the controller is configured to sort each level by tuple key value. ### Claim 5 (depends on 4) The computer system as recited in claim 4, wherein entries of the mapping table stored in a storage medium are grouped into pages, and wherein a result of the query is utilized to retrieve a particular page of the pages. ### Claim 6 (depends on 5) The computer system as recited in claim 5, wherein in response to receiving the particular page, the controller is configured to use the given key to identify a mapping within the particular page, the mapping including an identification of a location of a data item stored in the storage medium that corresponds to the given key. ### Claim 7 (depends on 1) The computer system as recited in claim 1, wherein the data storage controller is further configured to: insert the one or more new entries in the new level. ### Claim 8 (depends on 1) The computer system as recited in claim 1, wherein each of the mapping table entries further comprise an indication as to where the user data corresponding to a given key is stored on a data storage medium. ### Claim 9 (depends on 8) The computer system as recited in claim 8, wherein the data storage medium comprises one or more solid state storage devices. ### Claim 10 (depends on 1) The computer system as recited in claim 1, wherein all levels of the plurality of the time ordered levels other than a youngest level are read only and the youngest level is writable. ### Claim 11 (depends on 1) The computer system as recited in claim 1, further comprising an overlay table that overlays the mapping table, wherein the overlay table and mapping table are indexed by different keys. ### Claim 12 (depends on 11) The computer system as recited in claim 11, wherein the overlay table identifies one or more tuples in the mapping table that are not valid. ### Claim 13 (depends on 11) The computer system as recited in claim 11, wherein the overlay table contains one or more entries that correspond to a range of values. ### Claim 14 (depends on 11) The computer system as recited in claim 11, wherein the entry in the overlay table can be used to modify one or fields in a tuple returned from the mapping table in response to a query. ### Claim 15 (depends on 11) The computer system as recited in claim 11, wherein the key used to index the overlay table is generated from fields in the key used to access the mapping table. ### Claim 16 (depends on 11) The computer system as recited in claim 11, wherein the key used to index the overlay table is generated from fields in the tuple resulting from accessing the mapping table. ### Claim 17 (depends on 11) The computer system as recited in claim 11, further comprising a cache configured to store a cached copy of at least a portion of the overlay table. ### Claim 18 (depends on 11) The computer system as recited in claim 11, wherein the overlay table is organized as a plurality of time ordered levels, each level comprising one or more overlay table entries. ### Claim 19 A method for use in a storage system, the method comprising: storing a mapping table that includes a plurality of entries, each of the mapping table entries comprising a tuple including a key; and storing a mapping table index that includes a plurality of entries; wherein the mapping table is organized as a hierarchy including a plurality of time ordered levels such that younger levels of the plurality of time ordered levels appear higher in the hierarchy than older levels of the plurality of time ordered levels, each level comprising one or more mapping table entries; in response to receiving a request comprising a first key: determining if a duplicate key corresponding to the first key exists in the mapping table; and creating a new level to be added to the plurality of levels, in response to determining the duplicate key exists. ### Claim 20 (depends on 19) The method as recited in claim 19, wherein in response to receiving a particular page, the method further comprises using a given key that was used to access the mapping table to identify a mapping within the particular page, the mapping including an identification of a location of a data item stored in the storage medium that corresponds to the given key. ### Claim 21 (depends on 20) The method as recited in claim 20, further comprising storing a cached copy of at least a portion of the mapping table. ### Claim 22 (depends on 20) The method as recited in claim 20, wherein in response to receiving a request, the method further comprises: accessing the mapping table with at least a given key corresponding to the request; identifying one or more entries that correspond to the given key; determining which of the one or more entries corresponds to a youngest level of the time ordered levels; and returning an entry that corresponds to a youngest level of the time ordered levels to satisfy the request. ### Claim 23 (depends on 22) The method as recited in claim 22, further comprising sorting each level by tuple key value. ### Claim 24 (depends on 23) The method as recited in claim 23, wherein entries of the mapping table stored in a storage medium are grouped into pages, and wherein a result of the query is utilized to retrieve a particular page of the pages. ### Claim 25 (depends on 19) The method as recited in claim 19, further comprising: inserting the one or more new entries in the new level. ### Claim 26 (depends on 19) The method as recited in claim 19, wherein each of the mapping table entries further comprise an indication as to where the user data corresponding to a given key is stored on a data storage medium. ### Claim 27 (depends on 26) The method as recited in claim 26, wherein the data storage medium comprises one or more solid state storage devices. ### Claim 28 (depends on 19) The method as recited in claim 19, wherein all levels of the plurality of the time ordered levels other than a youngest level are read only. ### Claim 29 (depends on 19) The method as recited in claim 19, further comprising an overlay table that overlays the mapping table, wherein the overlay table and mapping table are indexed by different keys. ### Claim 30 (depends on 29) The method as recited in claim 29, wherein the overlay table identifies one or more tuples in the mapping table that are not valid. ### Claim 31 (depends on 29) The method as recited in claim 29, wherein the overlay table contains one or more entries that correspond to a range of values. ### Claim 32 (depends on 29) The method as recited in claim 29, further comprising using the entry in the overlay table to modify one or fields in a tuple returned from the mapping table in response to a query. ### Claim 33 (depends on 29) The method as recited in claim 29, wherein the key used to index the overlay table is generated from fields in the key used to access the mapping table. ### Claim 34 (depends on 29) The method as recited in claim 29, wherein the key used to index the overlay table is generated from fields in the tuple resulting from accessing the mapping table. ### Claim 35 A non-transitory computer readable storage medium storing program instruction executable by a processor to: store a mapping table that includes a plurality of entries, each of the mapping table entries comprising a tuple including a key; and store a mapping table index that includes a plurality of entries; wherein the mapping table is organized as a hierarchy including a plurality of time ordered levels such that younger levels of the plurality of time ordered levels appear higher in the hierarchy than older levels of the plurality of time ordered levels, each level comprising one or more mapping table entries; in response to receiving a request comprising a first key: determine if a duplicate key corresponding to the first key exists in the mapping table; and create a new level to be added to the plurality of levels, in response to determining the duplicate key exists. ### Claim 36 (depends on 35) The computer readable storage medium as recited in claim 35, wherein the program instructions are further executable to store in a cache a cached copy of at least a portion of the mapping table index. ### Claim 37 (depends on 35) The computer readable storage medium as recited in claim 35, wherein the program instructions are further executable to sort the cached copy by tuple key value.