Method for cleaning a delta storage system

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.

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.

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.

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

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.

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