Consolidating garbage collector in a data storage system

Patent metadata

Field	Value
Publication number	US-11093386-B2
Application number	US-201916718776-A
Country	US
Kind code	B2
Filing date	Dec 18, 2019
Priority date	Dec 18, 2019
Publication date	Aug 17, 2021
Grant date	Aug 17, 2021

Abstract

The technology described herein is directed towards consolidating garbage collection of data stored in data structures such as chunks, to facilitate efficient garbage collection. Low capacity utilization chunks are detected as source chunks, and live data of an object (e.g., in segments) is copied from the source chunks to new destination chunk(s). A source chunk is deleted when it no longer contains live data. By copying the data on an object-determined basis, new chunks contain more coherent object data, which increases the possibility of future chunk deletion without data copying or with a reduced amount of copying. When data segments of an object are adjacent, the consolidating garbage collector may unite them into a united segment, which reduces an amount of system metadata per object. New chunks can be associated with a generation number (e.g., indicating the oldest previous generation) to further facilitate more efficient future chunk deletion.

First claim

What is claimed is:

1. A system, comprising:
a processor, and
a memory that stores executable instructions that, when executed by the processor, facilitate performance of operations, the operations comprising:
determining garbage collection candidate chunks in a data storage system;
scanning object metadata of the data storage system to determine a selected object with live segments in the garbage collection candidate chunks;
copying the live segments of the selected object from the garbage collection candidate chunks to contiguous destination chunk storage space;
detecting adjacent live segments of the selected object in the contiguous destination chunk storage space; and
modifying object metadata of the adjacent live segments to unite the adjacent live segments into a combined segment in the contiguous destination chunk storage space.

2. The system of claim 1 , wherein the operations further comprise garbage collecting a garbage collection candidate chunk in response to no live segment of the garbage collection candidate chunk remains being determined to be uncopied.

3. The system of claim 1 , wherein the contiguous destination chunk storage space comprises storage space of a single chunk.

4. The system of claim 1 , wherein the contiguous destination chunk storage space comprises storage space of a sequence of two or more chunks, wherein at least one chunk of the sequence of two or more chunks comprises contiguous storage space.

5. The system of claim 1 , wherein the operations further comprise determining one or more expanded source chunks that maintain one or more live segments of the selected object, and copying the one or more live segments of the selected object from the one or more expanded source chunks to the contiguous destination chunk storage space.

6. The system of claim 1 , wherein a first one of the live segments corresponds to a first chunk associated with a first generation number, wherein a second one of the live segments corresponds to a second chunk associated with a second generation number that is different from the first generation number, and wherein the operations further comprise selecting the first generation number, and associating the first generation number with the contiguous destination chunk storage space.

7. The system of claim 6 , wherein the selecting the first generation number comprises determining that the first generation number represents an older generation than a generation represented by the second generation number.

8. The system of claim 1 , wherein the scanning object metadata of the data storage system to determine the selected object with the live segments comprises locating one or more expanded chunks that contain the live segments.

9. A method comprising:
determining, by a system comprising a processor, respective objects with live segments in source chunks, the source chunks comprising garbage collection candidate chunks;
consolidating the live segments of the respective objects into respective destination chunk storage space corresponding to one or more chunks, wherein the consolidating comprises:
accessing metadata of an object of the respective objects to determine segments of the live segments of the object, and
in response to determining that the segments of the live segments of the object are unable to fit into a space of a single chunk, copying the segments of the live segments of the object to two or more chunks; and

garbage collecting the garbage collection candidate chunks when no live segments remain uncopied in the garbage collection candidate chunks.

10. The method of claim 9 , wherein the determining the respective objects with the live segments in the source chunks comprises locating one or more expanded chunks that contain the live segments.

11. The method of claim 9 , wherein the consolidating the live segments of the respective objects into the respective destination chunk storage space further comprises in response to determining that the segments of the live segments of the object are able to fit into the space of the single chunk, copying the segments of the live segments of the object to the single chunk.

12. The method of claim 9 , further comprising detecting adjacent live segments of another object in the destination chunk storage space, and modifying object metadata of the adjacent live segments to unite the adjacent live segments into a combined segment in the destination chunk storage space.

13. The method of claim 9 , wherein a first live segment of the object corresponds to a first chunk associated with a first generation number, wherein a second live segment of the object corresponds to a second chunk associated with a second generation number that is older than the first generation number, and wherein the method further comprises associating the second generation number with the destination chunk storage space.

14. The method claim 9 , wherein a destination chunk storage space of the respective destination chunk storage space comprises storage space of the single chunk.

15. A non-transitory machine-readable medium, comprising executable instructions that, when executed by a processor, facilitate performance of operations, the operations comprising:
determining source chunks comprising chunks with low usage capacity in a data storage system, wherein the determining the source chunks comprising chunks with the low usage capacity comprises scanning an object table to determine low-capacity utilization chunks and to determine an expanded chunk set comprising at least one chunk that contains at least one live segment of a selected object;
processing object metadata of the data storage system to determine the selected object with live segments in the source chunks;
allocating a destination chunk; and
consolidating the live segments of the selected object from the source chunks into the destination chunk.

16. The non-transitory machine-readable medium of claim 15 , wherein the operations further comprise determining that a source chunk that contained a live segment of the object before the consolidating has no live segments of an object remaining therein after the consolidating, and, in response to the determining, garbage collecting the source chunk.

17. The non-transitory machine-readable medium of claim 15 , wherein the selected object with the live segments in the source chunks comprises a first selected object, and wherein the operations further comprise processing the object metadata of the data storage system to determine a second selected object with live segments in the source chunks, and consolidating the live segments of the second selected object from the source chunks into the destination chunk.

18. The non-transitory machine-readable medium of claim 15 , wherein the operations further comprise detecting adjacent live segments of the object in the destination chunk, and modifying the object metadata of the adjacent to unite the adjacent live segments into a combined segment in the destination chunk.

19. The non-transitory machine-readable medium of claim 15 , wherein a first live segment of an object corresponds to a first source chunk associated with a first generation number, wherein a second live segment of the object corresponds to a second source chunk associated with a second generation number that is older than the first generation number, and wherein the operations further comprise, associating the second generation number with the destination chunk.

20. The non-transitory machine-readable medium of claim 15 , w

Assignees

• Emc Ip Holding Co Llc

Inventors

• Danilov Mikhail
• Buinov Konstantin

Classifications

• G06F12/0276

  Generational garbage collection · CPC title

• G06F12/0253 Primary

  Garbage collection, i.e. reclamation of unreferenced memory · CPC title

• G06F2212/1024

  Latency reduction · CPC title