# US 2014/0195551 A1 · Optimizing snapshot lookups > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2014/0195551 A1 - Document ID: US20140195551A1 - Status: Published application - Kind: A1 - Application number: 14/058,757 - Filed: 2013-10-21 - Published: 2014-07-10 - Earliest claimed: 2013-01-10 - Assignees: Pure Storage, Inc. - Applicants: Pure Storage, Inc. - Inventors: John Colgrove; Ethan Miller; John Hayes; Cary Sandvig; Christopher Golden; Jianting Cao - Web page: https://patentgrep.com/patent/US20140195551A1 ## CPC - G06F 3/065: {Replication mechanisms} - G06F 3/0604: {Improving or facilitating administration, e.g. storage management} - G06F 3/0605: {by facilitating the interaction with a user or administrator} - G06F 3/0608: {Saving storage space on storage systems} - G06F 3/061: {Improving I/O performance} - G06F 3/0611: {in relation to response time} - G06F 3/0614: {Improving the reliability of storage systems} - G06F 3/0619: {in relation to data integrity, e.g. data losses, bit errors} - G06F 3/0626: {Reducing size or complexity of storage systems} - G06F 3/0632: {by initialisation or re-initialisation of storage systems} - G06F 3/0641: {De-duplication techniques} - G06F 3/0644: {Management of space entities, e.g. partitions, extents, pools} - G06F 3/0652: {Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket} - G06F 3/0655: {Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices} - G06F 3/0664: {at device level, e.g. emulation of a storage device or system} - G06F 3/0665: {at area level, e.g. provisioning of virtual or logical volumes} - G06F 3/0667: {at data level, e.g. file, record or object virtualisation} - G06F 3/067: {Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]} - G06F 3/0671: {In-line storage system} - G06F 3/0673: {Single storage device} - G06F 3/0683: {Plurality of storage devices} - G06F 3/0685: {Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays} - G06F 3/0689: {Disk arrays, e.g. RAID, JBOD} - G06F 16/1748: {De-duplication implemented within the file system, e.g. based on file segments (de-duplication techniques in storage systems for the management of data blocks G06F3/0641)} - G06F 16/23: Updating - G06F 2212/1008: Correctness of operation, e.g. memory ordering - G06F 2212/1016: Performance improvement - G06F 2212/1032: Reliability improvement, data loss prevention, degraded operation etc - G06F 2212/1044: Space efficiency improvement - G06F 2212/154: Networked environment - G06F 2212/163: Server or database system - G06F 2212/261: Storage comprising a plurality of storage devices - G06F 2212/263: Network storage, e.g. SAN or NAS - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A system and method for performing search optimization operations. In order to optimize lookups for received data requests, a storage controller attempts to collapse the medium graph, thus reducing the number of mediums in which the storage controller must look to find a given block. One technique for collapsing the medium graph involves promoting individual mappings from a lower-level medium to a higher-level medium. Another technique for collapsing the medium graph involves pushing medium range pointers higher up in the medium mapping table to reduce the number of mediums that must be searched. ## Claims ### Claim 1 A computer system comprising: one or more storage devices; and a storage controller coupled to the one or more storage devices, wherein the storage controller is configured to: maintain a medium mapping table to map underlying mediums to active mediums, wherein each underlying medium represents a snapshot; and maintain an address translation table to map mediums to locations within the one or more storage devices; wherein the storage controller is further configured to: initiate a search optimization operation for a first range of a first medium, wherein the search optimization operation comprises collapsing the medium mapping table for the first range of the first medium, and wherein the first range of the first medium has at least one underlying medium; create one or more first entries in the address translation table; assign the one or more first entries to the first range of the first medium; and copy attributes from one or more second entries in the address translation table to the first entries, wherein the second entries are assigned to a second medium, and wherein the second medium underlies the first range of the first medium. ### Claim 2 (depends on 1) The computer system as recited in claim 1, wherein responsive to determining a third medium underlies a second range of the first medium and a fourth medium underlies the third medium, the storage controller is configured to: create a new entry for the second range of the first medium in the medium mapping table, wherein the new entry indicates the fourth medium underlies the second range of the first medium; and discard an existing entry for the second range of the first medium in the medium mapping table, wherein the existing entry indicates the third medium underlies the second range of the first medium. ### Claim 3 (depends on 2) The computer system as recited in claim 2, wherein the storage controller is configured to create the new entry for the second range of the first medium in the medium mapping table responsive to detecting that there are no existing entries assigned to the third medium in the address translation table which correspond to an address space of the second range of the first medium. ### Claim 4 (depends on 1) The computer system as recited in claim 1, wherein the storage controller is further configured to copy attributes from one or more third entries of the address translation table to the first entries, wherein the third entries are assigned to a third medium, and wherein the third medium underlies the second medium. ### Claim 5 (depends on 1) The computer system as recited in claim 1, wherein the storage controller is further configured to apply an offset to block numbers copied to the first entries responsive to determining the first range of the first medium maps to the second medium using the offset. ### Claim 6 (depends on 1) The computer system as recited in claim 1, wherein the storage controller is configured to update the medium mapping table to indicate the first range of the first medium has no underlying medium responsive to determining mappings assigned to the first range of the first medium in the address translation table cover an entire address space of the first range of the first medium. ### Claim 7 (depends on 1) The computer system as recited in claim 1, wherein responsive to determining the entries in the second medium are no longer externally visible to any user volumes, the storage controller is configured to reclaim the second medium. ### Claim 8 A method for use in a storage system, the method comprising: maintaining a medium mapping table to map underlying mediums to active mediums, wherein each underlying medium represents a snapshot; maintaining an address translation table to map mediums to locations within the one or more storage devices; initiating a search optimization operation for a first range of a first medium, wherein the search optimization operation comprises collapsing the medium mapping table for the first range of the first medium, and wherein the first range of the first medium has at least one underlying medium; creating one or more first entries in the address translation table; assigning the one or more first entries to the first range of the first medium; and copying attributes from one or more second entries in the address translation table to the first entries, wherein the second entries are assigned to a second medium, and wherein the second medium underlies the first range of the first medium ### Claim 9 (depends on 8) The method as recited in claim 8, wherein responsive to determining a third medium underlies a second range of the first medium and a fourth medium underlies the third medium, the method further comprising: creating a new entry for the second range of the first medium in the medium mapping table, wherein the new entry indicates the fourth medium underlies the second range of the first medium; and discarding an existing entry for the second range of the first medium in the medium mapping table, wherein the existing entry indicates the third medium underlies the second range of the first medium. ### Claim 10 (depends on 9) The method as recited in claim 9, further comprising creating the new entry for the second range of the first medium in the medium mapping table responsive to detecting that there are no existing entries assigned to the third medium in the address translation table which correspond to an address space of the second range of the first medium. ### Claim 11 (depends on 8) The method as recited in claim 8, further comprising copying attributes from one or more third entries of the address translation table to the first entries, wherein the third entries are assigned to a third medium, and wherein the third medium underlies the second medium. ### Claim 12 (depends on 8) The method as recited in claim 8, further comprising applying an offset to block numbers copied to the first entries responsive to determining the first range of the first medium maps to the second medium using the offset. ### Claim 13 (depends on 8) The method as recited in claim 8, further comprising updating the medium mapping table to indicate the first range of the first medium has no underlying medium responsive to determining mappings assigned to the first range of the first medium in the address translation table cover an entire address space of the first range of the first medium. ### Claim 14 (depends on 8) The method as recited in claim 8, further comprising reclaiming the second medium responsive to determining the entries in the second medium are no longer externally visible to any user volumes. ### Claim 15 A non-transitory computer readable storage medium storing program instructions, wherein the program instructions are executable by a processor to maintain a medium mapping table to map underlying mediums to active mediums, wherein each underlying medium represents a snapshot; maintain an address translation table to map mediums to locations within the one or more storage devices; initiate a search optimization operation for a first range of a first medium, wherein the search optimization operation comprises collapsing the medium mapping table for the first range of the first medium, and wherein the first range of the first medium has at least one underlying medium; create one or more first entries in the address translation table; assign the one or more first entries to the first range of the first medium; and copy attributes from one or more second entries in the address translation table to the first entries, wherein the second entries are assigned to a second medium, and wherein the second medium underlies the first range of the first medium. ### Claim 16 (depends on 15) The computer readable storage medium as recited in claim 15, wherein responsive to determining a third medium underlies a second range of the first medium and a fourth medium underlies the third medium, the program instructions are executable by a processor to: create a new entry for the second range of the first medium in the medium mapping table, wherein the new entry indicates the fourth medium underlies the second range of the first medium; and discard an existing entry for the second range of the first medium in the medium mapping table, wherein the existing entry indicates the third medium underlies the second range of the first medium. ### Claim 17 (depends on 16) The computer readable storage medium as recited in claim 16, wherein the program instructions are further executable by a processor create the new entry for the second range of the first medium in the medium mapping table responsive to detecting that there are no existing entries assigned to the third medium in the address translation table which correspond to an address space of the second range of the first medium. ### Claim 18 (depends on 15) The computer readable storage medium as recited in claim 15, wherein the program instructions are further executable by a processor to copy attributes from one or more third entries of the address translation table to the first entries, wherein the third entries are assigned to a third medium, and wherein the third medium underlies the second medium. ### Claim 19 (depends on 15) The computer readable storage medium as recited in claim 15, wherein the program instructions are further executable by a processor to apply an offset to block numbers copied to the first entries responsive to determining the first range of the first medium maps to the second medium using the offset. ### Claim 20 (depends on 15) The computer readable storage medium as recited in claim 15, wherein the program instructions are further executable by a processor to update the medium mapping table to indicate the first range of the first medium has no underlying medium responsive to determining mappings assigned to the first range of the first medium in the address translation table cover an entire address space of the first range of the first medium.