Mapping in a storage system

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.

What is claimed is: 
     
      
       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; 
 wherein at least one record corresponding to a range of key values in the group is replaced in the new level by a plurality of records corresponding to subranges of the at least one record. 
 
       
      
     
     
      
       2. The computer system as recited in  claim 1 , wherein the plurality of levels of the mapping table are organized as time ordered levels. 
      
     
     
      
       3. The computer system as recited in  claim 1 , wherein the data storage controller is further configured to sort records within the new level. 
      
     
     
      
       4. The computer system as recited in  claim 1 , wherein the mapping table entries within a level of the plurality of levels are sorted by key. 
      
     
     
      
       5. The computer system as recited in  claim 1 , wherein the data storage controller is configured to perform flattening operations on the mapping table asynchronously with respect to updates to the mapping table. 
      
     
     
      
       6. The computer system as recited in  claim 1 , wherein in response to detecting the flattening condition, the data storage controller is further configured to insert one or more second records stored within the group into the new level, in response to detecting each of the one or more second records: 
       
         corresponds to two or more records storing a same non-unique key within the group; and 
         is in a youngest level containing a record with the non-unique key of the group. 
       
      
     
     
      
       7. The computer system as recited in  claim 6 , wherein a single record within the mapping table corresponds to a range of key values. 
      
     
     
      
       8. The computer system as recited in  claim 6 , further comprising an overlay table, wherein at least some of the first and second records inserted into the new level are modified or elided based on entries in the overlay table. 
      
     
     
      
       9. The computer system as recited in  claim 1 , wherein the data storage controller is further configured to create a new level from fewer than all of the records in the group of two or more adjacent levels. 
      
     
     
      
       10. The computer system as recited in  claim 1 , wherein the flattening condition is based on at least one of a current or predicted value of: a number of levels in the mapping table, a number of entries in one or more levels of the plurality of levels, a number of mapping entries that would be elided or modified as part of a flattening operation, and a load on the system. 
      
     
     
      
       11. The computer system as recited in  claim 1 , wherein the data storage controller is further configured to utilize a filtering condition to determine which of the first records are inserted into the new level. 
      
     
     
      
       12. The computer system as recited in  claim 11 , further comprising an overlay table, and wherein the filtering condition comprises a validity of a given record as determined by the overlay table. 
      
     
     
      
       13. The computer system as recited in  claim 11 , wherein the filtering condition is based at least in part on a current or predicted number of entries in the new level. 
      
     
     
      
       14. 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; 
 wherein at least one record corresponding to a range of key values in the group is replaced in the new level by a plurality of records corresponding to subranges of the at least one record. 
 
       
      
     
     
      
       15. The method as recited in  claim 14 , wherein only a youngest level of the plurality of levels may be updated with new mapping table entries. 
      
     
     
      
       16. The method as recited in  claim 14 , wherein the data storage controller is further configured to sort records within the new level. 
      
     
     
      
       17. The method as recited in  claim 14 , wherein the mapping table entries within a level of the plurality of levels are sorted by key. 
      
     
     
      
       18. The method as recited in  claim 14 , further comprising performing flattening operations on the mapping table asynchronously with respect to updates to the mapping table. 
      
     
     
      
       19. The method as recited in  claim 14 , wherein in response to detecting the flattening condition, the method further comprises inserting one or more second records stored within the group into the new level, in response to detecting each of the one or more second records: 
       
         corresponds to two or more records storing a same non-unique key within the group; and 
         is in a youngest level containing a record with the non-unique key of the group. 
       
      
     
     
      
       20. 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; 
 wherein at least one record corresponding to a range of key values in the group is replaced in the new level by a plurality of records corresponding to subranges of the at least one record. 
 
       
      
     
     
       21. A computer system comprising:
 a data storage medium;   a deduplication table;   a cached portion of entries in the deduplication table stored in a cache, wherein a number of entries in the cached portion is less than all the entries in the deduplication table; and   a data storage controller coupled to the data storage medium, wherein the data storage controller comprises a controller storage medium comprising computer program instructions, that, when executed, cause the data storage controller to carry out the steps of:
 generate a hash corresponding to a write request; 
 before a subsequent search of all the entries in the deduplication table, search, in the cache, only the cached portion of the entries in the deduplication table to determine whether the hash matches an entry in the cached portion of the entries in the deduplication table; 
 in response to determining that the hash does not match an entry in the cached portion, write the data associated with the write request and store a new deduplication table entry for the data in the cache; 
 perform the subsequent search of all the entries in the deduplication table including the entries in the cached portion; and 
 based on the subsequent search and in response to determining that the hash matches one of the entries in the deduplication table, perform a deduplication operation to eliminate one or more detected copies. 
   
     
     
       22. The computer system as recited in claim 21, wherein the subsequent search of all of the entries in the deduplication table is performed during a post-processing deduplication operation. 
     
     
       23. The computer system as recited in claim 22, wherein the post-processing deduplication operation is a garbage collection operation. 
     
     
       24. The computer system as recited in claim 21, wherein the data storage controller is further configured to:
 based on the subsequent search and in response to determining that the hash does not match any of the entries in the deduplication table, perform the write operation that stores the new deduplication table entry into the deduplication table.   
     
     
       25. The computer system as recited in claim 24 wherein performing the write operation that stores the new deduplication table entry in the deduplication table is combined with other write operations. 
     
     
       26. The computer system as recited in claim 21, wherein the new deduplication table entry is a hash-to-physical pointer mapping. 
     
     
       27. A method for use in a storage system, the method comprising:
 generating a hash corresponding to a write request;   before a subsequent search of all the entries in the deduplication table, search, in the cache, only a cached portion of the entries in a deduplication table to determine whether the hash matches an entry in the cached portion, wherein the number of entries in the cached portion is less than all the entries in the deduplication table, and wherein the cached portion is stored in the cache;   in response to determining that the hash does not match an entry in the cached portion, writing the data associated with the write request and storing a new deduplication table entry for the data in the cache;   performing the subsequent search of all the entries in the deduplication table including the entries in the cached portion; and   based on the subsequent search and in response to determining that the hash matches one of the entries in the deduplication table, performing a deduplication operation to eliminate one or more detected copies.   
     
     
       28. The method as recited in claim 27, wherein the subsequent search of all of the entries in the deduplication table is performed during a post-processing deduplication operation. 
     
     
       29. The method as recited in claim 28, wherein the post-processing deduplication operation is a garbage collection operation. 
     
     
       30. The method as recited in claim 27, further comprising:
 based on the subsequent search and in response to determining that the hash does not match any of the entries in the deduplication table, perform the write operation that stores the new deduplication table entry into the deduplication table.   
     
     
       31. The method as recited in claim 30, wherein performing the write operation that stores the new deduplication table entry in the deduplication table is combined with other write operations. 
     
     
       32. The method as recited in claim 27, wherein the new deduplication table entry is a hash-to-physical pointer mapping. 
     
     
       33. A computer program product disposed upon a non-transitory computer readable storage medium, the computer program product comprising computer program instructions, that, when executed, cause a computer to carry out the steps of:
 generate a hash corresponding to a write request;   before a subsequent search of all the entries in the deduplication table, search, in the cache, only a cached portion of the entries in a deduplication table to determine whether the hash matches an entry in the cached portion, wherein the number of entries in the cached portion is less than all the entries in the deduplication table, and wherein the cached portion is stored in the cache;   in response to determining that the hash does not match an entry in the cached portion, write the data associated with the write request and storing a new deduplication table entry for the data in the cache; and   perform the subsequent search of all the entries in the deduplication table including the entries in the cached portion; and   based on the subsequent search and in response to determining that the hash matches one of the entries in the deduplication table, perform a deduplication operation to eliminate one or more detected copies.   
     
     
       34. The computer program product of claim 33, wherein the subsequent search of all of the entries in the deduplication table is performed during a post-processing deduplication operation. 
     
     
       35. The computer program product of claim 34, wherein the post-processing deduplication operation is a garbage collection operation. 
     
     
       36. The of computer program product claim 33, wherein the program instructions are further executable by the processor to:
 based on the subsequent search and in response to determining that the hash does not match any of the entries in the deduplication table, perform the write operation that stores the new deduplication table entry into the deduplication table.   
     
     
       37. The computer program product of claim 36, wherein performing the write operation that stores the new deduplication table entry in the deduplication table is combined with other write operations. 
     
     
       38. The computer program product of claim 33, wherein the new deduplication table entry is a hash-to-physical pointer mapping.