Garbage collection in a storage system

• US 8,527,544 B1
• Filed: 12/29/2011
• Issued: 09/03/2013
• Est. Priority Date: 08/11/2011
• Status: Active Grant

• 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:
  US13/340,119
• Time in Patent Office: 614 Days
• Field of Search: 707600-899
• US Class Current: 707/791
• 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 first table comprising a plurality of entries, each of which includes a mapping of a virtual address to a physical location in the data storage medium;

a second table comprising a plurality of entries, each of which includes a reverse mapping of a physical address in the data storage medium to one or more virtual addresses; and

a data storage controller configured to;

identify one or more entries in the second table, wherein said one or more entries are identified as corresponding to a given segment;

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;

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

wherein the data storage controller is further configured to;

access the given segment and identify further entries which comprise a mapping of a location in the segment to one or more virtual addresses;

determine whether the first table includes a valid mapping for each of the further entries;

copy data from a current storage location in the segment corresponding to a valid mapping in the further entries to a new storage location in the data storage medium; and

reclaim the current storage location.

2. The system as recited in claim 1, wherein said identifying comprises creating a sorted list of entries including the one or more entries and the further entries, and wherein said determining comprises comparing entries in the sorted list to entries in the first table.

3. The system as recited in claim 2, wherein said determining comprises creating a list which includes an identification of data which is to be copied from a current location to a new location.

4. The system as recited in claim 1, wherein prior to copying given data from a current location to a new location, the method further comprises deduplicating the given data.

5. The system as recited in claim 4, wherein the data storage controller is configured to copy the data from the current location to a new location in further response to determining the given data has not yet been copied to a new location.

6. The system as recited in claim 5,

wherein in response to determining particular data is not duplicative, the particular data is copied to a first segment;

and

wherein in response to determining the particular data corresponds to duplicate data, the particular data is copied to a second segment different from the first segment and a corresponding entry is added to the second table.

7. The system as recited in claim 4, wherein in response to determining the given data is duplicative and corresponds to data already existing in a new location, the data storage controller is configured to add a new entry to the second table and foregoing copying of the given data to a new location.

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

9. The system as recited in claim 8, wherein entries in a newer level of the time ordered levels supercede matching entries in an older level of the time ordered level.

10. The system as recited in claim 9, further comprising flattening one or more levels of the time ordered levels which are older than the newer level.

11. The system as recited in claim 9, wherein the data storage controller is configured to append mappings for new writes to a different level of the first table than that used for mappings resulting from garbage collection.

12. The system as recited in claim 1, wherein the data storage controller is further configured to correct detected data errors in said data prior to copying the data from the first location to the second location.

13. The system as recited in claim 1, wherein in response to determining the first table includes a valid mapping for a virtual address included in an entry of the one or more entries, the data storage controller is configured to copy data of a first type to a first segment, and copy data of second type to a second segment.

14. The system as recited in claim 13, wherein the first type corresponds to data which is identified as at least one of:

data that is accessed together, data that compresses well together, and data that is deduplicated.

15. The system as recited in claim 1, wherein the second location corresponds to a different RAID geometry than the first location.

16. The system as recited in claim 1, wherein the data storage controller is configured to identify a candidate segment for garbage collection without examining the candidate segment data.

17. A method for use in a computing system, the method comprising:

maintaining a first table comprising a plurality of entries, wherein each of the plurality of entries of the first table maps a virtual address to a location in a data storage medium;

identifying one or more entries in a second table comprising a plurality of entries, wherein each of the one or more entries of the second table includes a reverse mapping of an address of a location in the data storage medium to one or more virtual addresses, and wherein said one or more entries are identified as corresponding to a given segment;

in response to determining the second table includes a valid mapping for a virtual address included in an entry of the one of the one or more entries;

copying data from a first location identified in the entry to a second location in the data storage medium; and

reclaiming the first storage location;

accessing the given segment and identifying further entries which comprise a mapping of a location in the segment to one or more virtual addresses;

determining whether the first table includes a valid mapping for each of the further entries;

copying data from a current storage location in the segment corresponding to a valid mapping in the further entries to a new storage location in the data storage medium; and

reclaiming the current storage location.

18. The method as recited in claim 17, wherein said identifying comprises creating a sorted list of entries including the one or more entries and the further entries, and wherein said determining comprises comparing entries in the sorted list to entries in the first table.

19. The method as recited in claim 18, wherein said determining comprises creating a list which includes an identification of data which is to be copied from a current location to a new location.

20. The method as recited in claim 17, wherein prior to copying given data from a current location to a new location, the method further comprises deduplicating the given data.

21. The method as recited in claim 20, wherein copying the data from the current location to a new location is in further response to determining the given data has not yet been copied to a new location.

22. The method as recited in claim 21,

wherein in response to determining particular data is not duplicative, the particular data is copied to a first segment;

and

wherein in response to determining the particular data corresponds to duplicate data, the particular data is copied to a second segment different from the first segment and a corresponding entry is added to the second table.

23. The method as recited in claim 20, wherein in response to determining the given data is duplicative and corresponds to data already existing in a new location, the method comprises adding a new entry to the second table and foregoing copying of the given data to a new location.

24. The method as recited in claim 17, wherein the first table is organized as a plurality of time ordered levels, each level comprising a plurality of entries.

25. The method as recited in claim 24, wherein entries in a newer level of the time ordered levels supercede matching entries in an older level of the time ordered level.

26. The method as recited in claim 24, further comprising flattening one or more levels of the time ordered levels which are older than a newest level of the time ordered levels.

27. The method as recited in claim 17, further comprising appending mappings for new writes to a different level of the first table than that used for mappings resulting from garbage collection.

28. The method as recited in claim 17, further comprising correcting detected data errors in said data prior to copying the data from the first location to the second location.

29. The method as recited in claim 28, wherein 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 method further comprises copying data of a first type to a first segment, and copying data of second type to a second segment.

30. The method as recited in claim 29, wherein the first type corresponds to data which is identified as at least one of:

data that is accessed together, data that compresses well together, and data that is deduplicated.

31. The method as recited in claim 17, wherein the second location corresponds to a different RAID geometry than the first location.

32. The method as recited in claim 17, further comprising maintaining segment data in a given segment separate from corresponding segment metadata, and identifying a candidate segment for garbage collection without examining the candidate segment data.

33. A non-transitory computer readable storage medium comprising program instructions, wherein said program instructions are executable to:

maintain a first table comprising a plurality of entries, wherein each of the plurality of entries of the first table maps a virtual address to a location in a data storage medium;

identify one or more entries in a second table comprising a plurality of entries, wherein each of the one or more entries of the second table comprises a reverse mapping of an address of a location in the data storage medium to one or more virtual addresses, and wherein said one or more entries are identified as corresponding to a given segment;

in response to determining the second table includes a valid mapping for a virtual address included in an entry of the one of the one or more entries;

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;

access the given segment and identify further entries which comprise a mapping of a location in the segment to one or more virtual addresses;

determine whether the first table includes a valid mapping for each of the further entries;

copy data from a current storage location in the segment corresponding to a valid mapping in the further entries to a new storage location in the data storage medium; and

reclaim the current storage location.