Reclaiming space occupied by duplicated data in a storage system

Abstract

A system and method for performing garbage collection. A system includes a storage medium, a first table including entries which map a virtual address to locations in the storage medium, and a second table with entries which include a reverse mapping of a physical address in a data storage medium to one or more virtual addresses. A storage controller is configured to perform garbage collection. During garbage collection, the controller is configured to identify one or more entries in the second table which correspond to a segment to be garbage collected. In response to determining the first table includes a valid mapping for a virtual address included in an entry of the one of the one or more entries, the controller is configured to copy data from a first location identified in the entry to a second location in the data storage medium, and reclaim the first storage location.

What is claimed is: 
     
       1. A computing storage system comprising:
 a data storage mediumone or more storage devices; 
 a data storage controllerthe storage system configured to:
 determine that a current segment within the data storage medium one or more storage devices is in use by identifying a valid mapping of a location in the current segment to one or more virtual addresses, including:
 creating a sorted list of potentially valid entries from a first table comprising entries mapping an address of a location in the one or more storage devices to one or more virtual addresses; and 
 creating a list of valid entries using the sorted list of potentially valid entries and a second table comprising entries mapping a virtual address to a location in the one or more storage devices; 
   copy data from the location in the current segment to a new storage location in the data storage medium one or more storage devices; and   reclaim the location in the current segment.   
 
     
     
       2. The storage system as recited in  claim 1 , wherein the data storage controller is further configured to identifying the valid mapping of a location in the current segment to one or more virtual addresses further comprises:
 identifying one or more entries in a the first table comprising a plurality of entries, wherein each of the one or more entries of the first table comprises a reverse mapping of an address of a location in the data storage medium to one or more virtual addresses; determine that the first table includes a valid mapping for a virtual address; and 
 determinedetermining the mapping is valid responsive to determining the first table includes at least one valid mapping for a virtual address. 
 
     
     
       3. The storage system as recited in  claim 1 , wherein the data storage controller storage system is further configured to maintain a the second table comprising a plurality of entries, wherein each of the plurality of entries of the second table maps a virtual address to a location in the data storage medium using multi-level shared tables. 
     
     
       4. The storage system as recited in  claim 1 , wherein prior to copying the data from the location to the new location, the method further comprises deduplicating the data is deduplicated. 
     
     
       5. The storage system as recited in  claim 4 , wherein the data storage controller storage system is configured to copy the data from the location to the new location in further response to determining the data has not yet been copied to the new location. 
     
     
       6. The storage system as recited in  claim 1 , wherein the first table is organized as a plurality of time ordered levels, each level comprising a plurality of entries. 
     
     
       7. A method for use in a computing storage system that includes one or more storage devices, the method comprising:
 determining that a current segment within a data storage medium the one or more storage devices is in use by identifying a valid mapping of a location in the current segment to one or more virtual addresses, including:
 creating a sorted list of potentially valid entries from a first table comprising entries mapping an address of a location in the one or more storage devices to one or more virtual addresses; and 
 creating a list of valid entries using the sorted list of potentially valid entries and a second table comprising entries mapping a virtual address to a location in the one or more storage devices; 
 
 copying data from the location in the current segment to a new storage location in the data storage medium one or more storage devices; and 
 reclaiming the location in the current segment. 
 
     
     
       8. The method as recited in  claim 7 , further comprising wherein identifying the valid mapping of a location in the current segment to one or more virtual addresses further comprises:
 identifying one or more entries in a the first table comprising a plurality of entries, wherein each of the one or more entries of the first table comprises a reverse mapping of an address of a location in the data storage medium to one or more virtual addresses; 
 determining that the first table includes a valid mapping for a virtual address; and 
 determining the mapping is valid responsive to determining the first table includes at least one valid mapping for a virtual address. 
 
     
     
       9. The method as recited in  claim 8 , further comprising maintaining a the second table comprising a plurality of entries, wherein each of the plurality of entries of the second table maps a virtual address to a location in the data storage medium using multi-level shared tables. 
     
     
       10. The method as recited in  claim 8 , wherein the first table is organized as a plurality of time ordered levels, each level comprising a plurality of entries. 
     
     
       11. The method as recited in  claim 7 , wherein prior to copying the data from the location to the new location, the method further comprises deduplicating the data. 
     
     
       12. The method as recited in  claim 11 , further comprising copying the data from the location to the new location in further response to determining the data has not yet been copied to the new location. 
     
     
       13. A non-transitory computer readable storage medium comprising with program instructions stored thereon, wherein said program instructions are executable to:
 determine that a current segment within a data storage medium one or more storage devices is in use by identifying a valid mapping of a location in the current segment to one or more virtual addresses, including:
 creating a sorted list of potentially valid entries from a first table comprising entries mapping an address of a location in the one or more storage devices to one or more virtual addresses; and 
 creating a list of valid entries using the sorted list of potentially valid entries and a second table comprising entries mapping a virtual address to a location in the one or more storage devices; 
 
 copy data from the location in the current segment to a new storage location in the data storage medium one or more storage devices; and 
 reclaim the location in the current segment. 
 
     
     
       14. The non-transitory computer readable storage medium as recited in  claim 13 , wherein said program instructions are further executable to identifying the valid mapping of a location in the current segment to one or more virtual addresses further comprises:
 identifying one or more entries in a the first table comprising a plurality of entries, wherein each of the one or more entries of the first table comprises a reverse mapping of an address of a location in the data storage medium to one or more virtual addresses; determine that the first table includes a valid mapping for a virtual address; and 
 determinedetermining the mapping is valid responsive to determining the first table includes at least one valid mapping for a virtual address. 
 
     
     
       15. The non-transitory computer readable storage medium as recited in  claim 14 , wherein said program instructions are further executable to maintain a the second table comprising a plurality of entries, wherein each of the plurality of entries of the second table maps a virtual address to a location in the data storage medium using multi-level shared tables. 
     
     
       16. The non-transitory computer readable storage medium as recited in claim  14  13, wherein said program instructions are further executable to organize the first table as a plurality of time ordered levels, each level comprising a plurality of entries. 
     
     
       17. The non-transitory computer readable storage medium as recited in  claim 13 , wherein prior to copying the data from the location to the new location, the program instructions are further executable to deduplicate the data.