Optimizing snapshot lookups

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.

What is claimed is: 
     
         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. 
   
     
     
         2 . 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.   
     
     
         3 . 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. 
     
     
         4 . 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. 
     
     
         5 . 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. 
     
     
         6 . 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. 
     
     
         7 . 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. 
     
     
         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   
     
     
         9 . 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.   
     
     
         10 . 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. 
     
     
         11 . 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. 
     
     
         12 . 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. 
     
     
         13 . 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. 
     
     
         14 . 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. 
     
     
         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.   
     
     
         16 . 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.   
     
     
         17 . 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. 
     
     
         18 . 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. 
     
     
         19 . 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. 
     
     
         20 . 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.