Method for cleaning a delta storage system

• US 9,141,301 B1
• Filed: 06/13/2012
• Issued: 09/22/2015
• Est. Priority Date: 06/13/2012
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (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:
  US13/495,881
• Time in Patent Office: 1,196 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:

selecting each of a plurality of file recipes stored in the data storage system to traverse 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 and locations of the data chunks within the corresponding file, wherein each chunk identifier includes a fingerprint of an associated data chunk;

selecting each chunk identifier included in each of the file recipes;

adding each of the chunk identifiers to a set of live data chunks;

for each of the data chunks identified by the chunk identifiers of the file recipes, performing a lookup operation in an index of the storage system to determine whether there is a delta reference associated with the data chunk, the index including a plurality of entries corresponding to the plurality of data chunks stored in the data storage system respectively, wherein each entry of the index stores a fingerprint of a corresponding data chunk, a storage location of the corresponding data chunk, and a delta reference if the corresponding data chunk has been delta encoded;

adding delta references for the file recipes corresponding to the chunk identifiers that are obtained from the index to the set of live data chunks, wherein the index is stored separately from the file recipes; and

discarding data chunks in a data storage system 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 distinct from the listing of data chunks in the data storage system and the file recipes.

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

copying all data chunks in the set of live data chunks and deleting all dead 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 diff of the set of live data chunks and referenced data chunks from a previous set of live chunks and referenced data chunks; and

discarding data chunks not directly or indirectly referenced by the set of live data chunks and the diff.

6. The method of claim 1, further comprising:

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; and

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

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

selecting each of a plurality of file recipes stored in the data storage system to traverse 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 and locations of the data chunks within the corresponding file, wherein each chunk identifier includes a fingerprint of an associated data chunk;

selecting each chunk identifier included in each of the file recipes;

adding each of the chunk identifiers to a set of live data chunks;

for each of the data chunks identified by the chunk identifiers of the file recipes, performing a lookup operation in an index of the storage system to determine whether there is a delta reference associated with the data chunk, the index including a plurality of entries corresponding to the plurality of data chunks stored in the data storage system respectively, wherein each entry of the index stores a fingerprint of a corresponding data chunk, a storage location of the corresponding data chunk, and a delta reference if the corresponding data chunk has been delta encoded;

adding delta references for the file recipes corresponding to the chunk identifiers that are obtained from the index to the set of live data chunks, wherein the index is sstored separately from the file recipes; and

discarding data chunks in a data storage system 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 distinct from the listing of data chunks in the data storage system and the file recipes.

8. The non-transitory computer-readable storage medium of claim 7, wherein discarding the data chunks further comprises:

copying all data chunks in the set of live data chunks and deleting all dead data chunks.

9. The non-transitory computer-readable storage medium of claim 8, wherein the operations further comprise:

sanitizing the dead data chunks by decompressing live data chunks referencing the dead data chunks.

10. The non-transitory computer-readable storage medium of claim 7, 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.

11. The non-transitory computer-readable storage medium of claim 7, wherein discarding the data chunks further comprises:

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

discarding data chunks not directly or indirectly referenced by the set of live data chunks and the diff.

12. The non-transitory computer-readable storage medium of claim 7, wherein the operations further comprise:

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; and

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

13. A delta compression system, comprising:

a processor;

a memory; and

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

selecting each of a plurality of file recipes stored in the data storage system to traverse 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 and locations of the data chunks within the corresponding file, wherein each chunk identifier includes a fingerprint of an associated data chunk,

selecting each chunk identifier included in each of the file recipes,

adding each of the chunk identifiers to a set of live data chunks,

for each of the data chunks identified by the chunk identifiers of the file recipes, performing a lookup operation in an index of the storage system to determine whether there is a delta reference associated with the data chunk, the index including a plurality of entries corresponding to the plurality of data chunks stored in the data storage system respectively, wherein each entry of the index stores a fingerprint of a corresponding data chunk, a storage location of the corresponding data chunk, and a delta reference if the corresponding data chunk has been delta encoded,

adding delta references for the file recipes corresponding to the chunk identifiers that are obtained from the index to the set of live data chunks, wherein the index is stored separately from the file recipes, and

discarding data chunks in a data storage system 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 distinct from the listing of data chunks in the data storage system and the file recipes.

14. The delta compression system of claim 13, wherein the garbage collection module performs discarding by copying all data chunks in the set of live data chunks and deleting dead data chunks.

15. The delta compression system of claim 14, further comprising:

a sanitization module to sanitize dead data chunks by decompressing live data chunks referencing the dead data chunks.

16. The delta compression system of claim 13, further comprising:

a deduplication module to eliminate 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.

17. The delta compression system of claim 13, wherein the garbage collection module determines a diff of the set of live data chunks and referenced data chunks from a previous set of live data chunks and referenced data chunks and discards data chunks not directly or indirectly referenced by the set of live chunks and the diff.

18. The delta compression system of claim 13, wherein the garbage collection module further traverses 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 and selects base data chunk identifiers associated with matched entries as the delta references.