Garbage collection in a storage system

Patent metadata

Field	Value
Publication number	US-9251066-B2
Application number	US-201414537709-A
Country	US
Kind code	B2
Filing date	Nov 10, 2014
Priority date	Aug 11, 2011
Publication date	Feb 2, 2016
Grant date	Feb 2, 2016

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.

First claim

What is claimed is:

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.

Assignees

• Pure Storage Inc

Inventors

• Colgrove John
• Hayes John
• Miller Ethan
• Sandvig Cary
• Hasbani Joseph S
• Wang Feng

Classifications

• G06F16/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 title

• G06F3/0608 Primary

  Saving storage space on storage systems · CPC title

• G06F3/0641

  De-duplication techniques · CPC title

• G06F3/0688 Primary

  Non-volatile semiconductor memory arrays · CPC title

• G06F3/0665

  at area level, e.g. provisioning of virtual or logical volumes · CPC title