Method for cleaning a delta storage system

• US 9,405,764 B1
• Filed: 07/16/2015
• Issued: 08/02/2016
• Est. Priority Date: 06/13/2012
• Status: Active Grant

• Current Assignee: EMC Corporation (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Wallace, Grant R., Shilane, Philip N.
• Primary Examiner(s): Choi, Yuk Ting
• Application Number:
  US14/801,773
• Time in Patent Office: 383 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/162 Delete operations erasing in storage systems G06F3/0652
• CPC Class Codes: G06F 16/1756 based on delta files
• 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/0683 Plurality of storage devices

Abstract

A computer-implemented method for performing garbage collection in a delta compressed data storage system selects a file recipe to traverse to identify live data chunks and a chunk identifier from the file recipe. The chunk identifier is added to a set of live data chunks. Delta references in the file recipe corresponding to the chunk identifier are added to the set of live data chunks. Data chunks in a data storage system not identified by the set of live data chunks are discarded.

Claims

1. A computer-implemented method for performing garbage collection in a delta compressed data storage system, the method comprising:

traversing a plurality of file recipes stored in the data storage system to identify a plurality of data chunks, the plurality of file recipes representing a plurality of files, wherein each file recipe includes a plurality of chunk identifiers identifying a plurality of data chunks that constitute a corresponding file represented by the file recipe;

for each of the file recipes,

adding chunk identifiers contained in the file recipe to a set of live data chunks, and

for each of the chunk identifiers in the file recipe,

performing a lookup operation in an index of the storage system to determine whether there is a delta reference associated with the data chunk identifier, wherein each entry of the index stores a chunk identifier of a corresponding data chunk and a delta reference when the corresponding data chunk has been delta encoded from another data chunk,

traversing the index using the chunk identifiers referenced in each of the file recipes to determine matches between the chunk identifiers and entries in the index,

selecting base data chunk identifiers associated with matched entries as the delta references, and

adding the delta reference corresponding to the chunk identifier to the set of live data chunks; and

discarding data chunks in a data storage system that are not identified by the set of live data chunks, wherein the set of live data chunks is a listing that identifies live data chunks in the data storage system.

2. The method of claim 1, wherein discarding the data chunks further comprises:

copying all data chunks in the set of live data chunks to a new storage location; and

deleting all dead data chunks that are not listed in the set of live data chunks.

3. The method of claim 2, further comprising sanitizing the dead data chunks by decompressing live data chunks referencing the dead data chunks.

4. The method of claim 1, further comprising:

eliminating duplicate data chunks in the set of live data chunks by retaining a base chunk version; and

discarding a delta chunk version of a duplicate data chunk.

5. The method of claim 1, wherein discarding the data chunks further comprises:

determining a difference of the set of live data chunks from a previous set of live chunks; and

discarding data chunks that are not referenced by the set of live data chunks and the difference.

6. The method of claim 1, wherein each file recipe further includes a storage location within a corresponding file for each of the data chunks represented by the chunk identifiers.

7. The method of claim 1, wherein each of entries of the index further stores a storage location within a storage device of the storage system of a data chunk corresponding to the entry.

8. A non-transitory machine-readable medium having instructions stored therein, which when executed by a processor, cause the processor to perform operations of garbage collection in a delta compressed data storage system, the operations comprising:

traversing a plurality of file recipes stored in the data storage system to identify a plurality of data chunks, the plurality of file recipes representing a plurality of files,

wherein each file recipe includes a plurality of chunk identifiers identifying a plurality of data chunks that constitute a corresponding file represented by the file recipe;

for each of the file recipes,

adding chunk identifiers contained in the file recipe to a set of live data chunks, and for each of the chunk identifiers in the file recipe,

performing a lookup operation in an index of the storage system to determine whether there is a delta reference associated with the data chunk identifier, wherein each entry of the index stores a chunk identifier of a corresponding data chunk and a delta reference when the corresponding data chunk has been delta encoded from another data chunk,

traversing the index using the chunk identifiers referenced in each of the file recipes to determine matches between the chunk identifiers and entries in the index,

selecting base data chunk identifiers associated with matched entries as the delta references, and

adding the delta reference corresponding to the chunk identifier to the set of live data chunks; and

discarding data chunks in a data storage system that are not identified by the set of live data chunks, wherein the set of live data chunks is a listing that identifies live data chunks in the data storage system.

9. The non-transitory machine-readable medium of claim 8, wherein discarding the data chunks further comprises:

copying all data chunks in the set of live data chunks to a new storage location; and

deleting all dead data chunks that are not listed in the set of live data chunks.

10. The non-transitory machine-readable medium of claim 9, wherein the operations further comprise sanitizing the dead data chunks by decompressing live data chunks referencing the dead data chunks.

11. The non-transitory machine-readable medium of claim 8, wherein the operations further comprise:

eliminating duplicate data chunks in the set of live data chunks by retaining a base chunk version; and

discarding a delta chunk version of a duplicate data chunk.

12. The non-transitory machine-readable medium of claim 8, wherein discarding the data chunks further comprises:

determining a difference of the set of live data chunks from a previous set of live chunks; and

discarding data chunks that are not referenced by the set of live data chunks and the difference.

13. The non-transitory machine-readable medium of claim 8, wherein each file recipe further includes a storage location within a corresponding file for each of the data chunks represented by the chunk identifiers.

14. The non-transitory machine-readable medium of claim 8, wherein each of entries of the index further stores a storage location within a storage device of the storage system of a data chunk corresponding to the entry.

15. A data processing system, comprising:

a processor;

a memory coupled to the processor; and

a garbage collection module loaded in the memory and executed by the processor to perform operations of garbage collection, the operations including

traversing a plurality of file recipes stored in the data storage system to identify a plurality of data chunks, the plurality of file recipes representing a plurality of files, wherein each file recipe includes a plurality of chunk identifiers identifying a plurality of data chunks that constitute a corresponding file represented by the file recipe,

for each of the file recipes,

adding chunk identifiers contained in the file recipe to a set of live data chunks, and for each of the chunk identifiers in the file recipe,

performing a lookup operation in an index of the storage system to determine whether there is a delta reference associated with the data chunk identifier, wherein each entry of the index stores a chunk identifier of a corresponding data chunk and a delta reference when the corresponding data chunk has been delta encoded from another data chunk,

traversing the index using the chunk identifiers referenced in each of the file recipes to determine matches between the chunk identifiers and entries in the index,

selecting base data chunk identifiers associated with matched entries as the delta references, and

adding the delta reference corresponding to the chunk identifier to the set of live data chunks, and

discarding data chunks in a data storage system that are not identified by the set of live data chunks, wherein the set of live data chunks is a listing that identifies live data chunks in the data storage system.

16. The system of claim 15, wherein discarding the data chunks further comprises:

copying all data chunks in the set of live data chunks to a new storage location; and

deleting all dead data chunks that are not listed in the set of live data chunks.

17. The system of claim 16, wherein the operations further comprise sanitizing the dead data chunks by decompressing live data chunks referencing the dead data chunks.

18. The system of claim 15, wherein the operations further comprise:

eliminating duplicate data chunks in the set of live data chunks by retaining a base chunk version; and

discarding a delta chunk version of a duplicate data chunk.

19. The system of claim 15, wherein discarding the data chunks further comprises:

determining a difference of the set of live data chunks from a previous set of live chunks; and

discarding data chunks that are not referenced by the set of live data chunks and the difference.

20. The system of claim 15, wherein each file recipe further includes a storage location within a corresponding file for each of the data chunks represented by the chunk identifiers.

21. The system of claim 15, wherein each of entries of the index further stores a storage location within a storage device of the storage system of a data chunk corresponding to the entry.