Garbage collection in a storage system

• US 9,251,066 B2
• Filed: 11/10/2014
• Issued: 02/02/2016
• Est. Priority Date: 08/11/2011
• Status: Expired

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Pure Storage, Inc.
• Inventors: Colgrove, John, Hayes, John, Miller, Ethan, Sandvig, Cary, Hasbani, Joseph S., Wang, Feng
• Primary Examiner(s): Woo, Isaac M
• Application Number:
  US14/537,709
• Publication Number:
  US 20150067286A1
• Time in Patent Office: 449 Days
• Field of Search: 707600-899
• US Class Current: 1/1
• CPC Class Codes: 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
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays

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.

Claims

1. A computing system comprising:

a data storage medium;

a data storage controller configured to;

determine that a current segment within the data storage medium is in use by identifying a valid mapping of a location in the current segment to one or more virtual addresses;

copy data from the location in the current segment to a new storage location in the data storage medium; and

reclaim the location in the current segment.

2. The system as recited in claim 1, wherein the data storage controller is further configured to:

identify one or more entries in a 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

determine the mapping is valid responsive to determining the first table includes at least one valid mapping for a virtual address.

3. The system as recited in claim 1, wherein the data storage controller is further configured to maintain a 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.

4. The 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.

5. The system as recited in claim 4, wherein the data storage controller is configured to 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 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 system, the method comprising:

determining that a current segment within a data storage medium is in use by identifying a valid mapping of a location in the current segment to one or more virtual addresses;

copying data from the location in the current segment to a new storage location in the data storage medium; and

reclaiming the location in the current segment.

8. The method as recited in claim 7, further comprising:

identifying one or more entries in a 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 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.

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 program instructions, wherein said program instructions are executable to:

determine that a current segment within a data storage medium is in use by identifying a valid mapping of a location in the current segment to one or more virtual addresses;

copy data from the location in the current segment to a new storage location in the data storage medium; 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:

identify one or more entries in a 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

determine 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 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.

16. The non-transitory computer readable storage medium as recited in claim 14, 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.