Method for cleaning a delta storage system

• US 8,972,672 B1
• Filed: 06/13/2012
• Issued: 03/03/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): KROFCHECK, MICHAEL C
• Application Number:
  US13/495,893
• Time in Patent Office: 993 Days
• Field of Search: None
• US Class Current: 711/154
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 2212/401 Compressed data
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 2212/7207 management of metadata or control data
• 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/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

A computer-implemented method and system for performing garbage collection in a delta compressed data storage system selects a file recipe to traverse to identify live data chunks and selects a chunk identifier from the file recipe. The chunk identifier is added to a set of live data chunks. Delta references in the file metadata 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 then discarded.

Claims

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

selecting a file recipe identifying a plurality of data chunks within the data storage system that can be joined to reconstruct a file, where each of the plurality of data chunks is different and includes a plurality of bytes;

selecting a chunk identifier from the file recipe, where the chunk identifier is an identifier of a specific one of the plurality of data chunks;

adding the chunk identifier to a set of live data chunks;

adding a base chunk that is identified by a delta reference to the set of live data chunks, wherein the delta reference is stored in metadata of the specific data chunk;

discarding dead data chunks in the data storage system, where the dead data chunks are not identified by the set of live data chunks; and

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

2. The method of claim 1, wherein adding the base chunk further comprises:

accessing the set of live data chunks to obtain the delta reference.

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

copying all data chunks in the set of live data chunks and deleting all 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 dead data chunks further comprises:

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

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

6. The method of claim 1, wherein the specific data chunk is a delta encoded data chunk.

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

selecting a file recipe identifying a plurality of data chunks within the data storage system that can be joined to reconstruct a file, where each of the plurality of data chunks is different and includes a plurality of bytes;

selecting a chunk identifier from the file recipe, where the chunk identifier is an identifier of a specific one of the plurality of data chunks;

adding the chunk identifier to a set of live data chunks;

adding a base chunk that is identified by a delta reference to the set of live data chunks, wherein the delta reference is stored in metadata of the specific data chunk;

discarding dead data chunks in the data storage system, where the dead data chunks are not identified by the set of live data chunks; and

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

8. The non-transitory computer-readable storage medium of claim 7, wherein adding the base chunk further comprises:

accessing the set of live data chunks to obtain the delta reference.

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

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

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

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

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

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

12. The non-transitory computer-readable storage medium of claim 7, wherein the specific data chunk is a delta encoded data chunk.

13. A delta compression system, comprising:

a delta processing module to delta compress a first set of data chunks;

a data storage system to store a second set of data chunks;

a garbage collection module coupled to the delta processing module and the data storage system, the garbage collection module operable to traverse each of a plurality of data chunk identifiers in each file recipe in the data storage system, wherein each data chunk identifier identifies a data chunk, wherein each file recipe identifies a plurality of data chunks that can be joined to reconstruct a file, wherein each of the plurality of data chunks is different and includes a plurality of bytes, the garbage collection module further operable to generate a set of live data chunks, the set of live data chunks including delta references, each delta reference identifying a base chunk, each delta reference retrieved from metadata of a data chunk corresponding to one of the plurality of data chunk identifiers, the garbage collection module further operable to discard dead data chunks not referenced in the set of live data chunks; and

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

14. The delta compression system of claim 13, wherein each delta reference is obtained through accessing the set of live data chunks.

15. 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 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 difference between 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 data chunks and the difference.

18. The delta compression system of claim 13, wherein the data chunk is a delta encoded data chunk.