Method for cleaning a delta storage system

• US 9,400,610 B1
• Filed: 06/13/2012
• Issued: 07/26/2016
• 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): Savla, Arpan P.
• Application Number:
  US13/495,926
• Time in Patent Office: 1,504 Days
• Field of Search: 711/154, 711/159, 711/161, 711/162, 707/661, 707692-694, 707813-820
• US Class Current: 1/1
• 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/0613 in relation to throughput
• CPC Class Codes: G06F 3/0623 in relation to content
• 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]
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

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 an entry of an index 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 for each file of a plurality of files in the delta compressed data storage system, wherein each file in the plurality of files has been segmented into data chunks, and each file recipe comprises a plurality of identifiers of data chunks that comprise the file;

traversing the selected file recipe to determine the plurality of data chunk identifiers of the data chunks of the file;

for each data chunk identifier in the selected file recipe;

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

determining whether the data chunk identifier comprises a base chunk identifier identifying a base chunk and whether the file recipe contains a delta reference identifying a data chunk that is delta encoded relative to the base chunk;

adding the delta reference to the set of live data chunks, in response to determining that the data chunk identifier comprises a base chunk identifier and the file recipe contains a delta reference identifying a data chunk that is delta encoded relative to the base data chunk; and

discarding data chunks in the delta compressed data storage system that are not identified by the set of live data chunks.

2. The method of claim 1, wherein the base chunk identifier references a previously stored data chunk that was selected as a base chunk for use in delta encoding the data chunk based upon a similarity value between the data chunk to be delta encoded and the previously stored data chunk.

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

4. 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 dead data chunks that are not in the set of live data chunks;

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

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 data chunks and referenced data chunks; and

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

16. The method of claim 1, wherein the delta reference is retrieved from an entry of an index corresponding to the data chunk.

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

selecting a file recipe for each file of a plurality of files in the delta compressed data storage system, wherein each file in the plurality of files has been segmented into data chunks, and each file recipe comprises a plurality of identifiers of data chunks that comprise the file;

traversing the selected file recipe to determine the plurality of data chunk identifiers of the data chunks of the file;

for each data chunk identifier in the file recipe;

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

determining whether the data chunk identifier comprises a base chunk identifier identifying a base chunk and whether the file recipe contains a delta reference identifying a data chunk that is delta encoded relative to the base chunk;

adding the delta reference to the set of live data chunks, in response to determining that the chunk identifier contains a delta reference identifying a data chunk that is delta encoded to the data chunk; and

discarding data chunks in the delta compressed data storage system that are not identified by the set of live data chunks.

7. The non-transitory computer-readable storage medium of claim 6, wherein the base chunk identifier references a previously stored data chunk that was selected as a base chunk for use in delta encoding the data chunk based upon a similarity value between the data chunk to be delta encoded and the previously stored data chunk.

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

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

copying all data chunks in the set of live data chunks and deleting dead data chunks that are not in the set of live data chunks; and

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 6, 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 data chunks; and

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

17. The non-transitory computer-readable storage medium of claim 6, wherein the delta reference is retrieved from an entry of an index corresponding to the data chunk.

11. A delta compression system, comprising:

a delta processing module to delta compresses data chunks;

a data storage system to store delta compressed data chunks; and

a garbage collection module coupled to the data storage system configured to;

select a file recipe for each file of a plurality of files in the delta compression system, wherein each file in the plurality of files has been segmented into data chunks, and each file recipe comprises a plurality of identifiers of data chunks that comprise the file;

traverse the selected file recipe to determine the plurality of data chunk identifiers of the data chunks of the file;

for each data chunk identifier in the selected file recipe;

add the data chunk to a set of live data chunks,

determine whether the chunk identifier comprises a base chunk identifier identifying a base chunk and whether the file recipe contains a delta reference identifying a data chunk that is delta encoded relative to the base chunk,

adding the delta reference to the set of live data chunks in response to determining that the data chunk identifier contains a reference identifying a data chunk that is delta encoded relative to the data chunk,

the garbage collection module is configured to discard all data chunks that in the delta compression system that are not identified by the set of live data chunks.

12. The delta compression system of claim 11, wherein the base chunk identifier references a previously stored data chunk that was selected as a base chunk for use in delta encoding the data chunk based upon a similarity value between the data chunk to be delta encoded and the previously stored data chunk.

13. The delta compression system of claim 11, 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.

14. The delta compression system of claim 11, wherein discarding data chunks further comprises:

copying all data chunks in the set of live data chunks and deleting dead data chunks that are in the live 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.

15. The delta compression system of claim 11, 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 data chunks and the diff.

18. The system of claim 11, wherein the delta reference is retrieved from an entry of an index corresponding to the data chunk.