Global deduplication on distributed storage using segment usage tables

1. A method of global deduplication on distributed storage, the method comprising:

selecting, by a deduplication process, candidate segments in a storage medium;

reading blocks of the candidate segments;

determining whether any blocks of the candidate segments are duplicates;

updating a reference count for the duplicate blocks of the candidate segments;

identifying unique blocks of the candidate segments;

writing at least a portion of the unique blocks to a log;

determining whether the log has accumulated a full segment of data;

based at least on determining that the log has accumulated a full segment of data, writing the full segment of data to the storage medium;

updating a segment usage table (SUT) to mark the candidate segments as free; and

updating the SUT to mark a segment of the storage medium, used for the full segment of data, as no longer free.

2. The method of claim 1 , wherein determining whether any blocks of the candidate segments have duplicates comprises:

hashing the blocks of the candidate segments to generate block hash values; and

determining whether any block hash values match values within a hash table.

3. The method of claim 1 , further comprising:

identifying a window having a start time and a stop time, wherein the candidate segments have an age starting within the window.

4. The method of claim 3 , further comprising:

making a first window adjustment by changing at least one of the start time and the stop time;

determining an effect of the first window adjustment on a deduplication score; and

based at least on the deduplication score effect, making a second window adjustment.

5. The method of claim 1 , further comprising:

determining whether sufficient free segments are available for writing to the storage medium; and

based at least on determining that insufficient free segments are available for writing to the storage medium, requesting allocation of new segments.

6. The method of claim 1 , further comprising:

prior to writing at least a portion of the unique blocks to a log, determining whether the unique blocks comprise at least a full segment of data;

based at least on determining that the unique blocks comprise at least a full segment of data, writing a full segment portion of the unique blocks to the storage medium, wherein the unique blocks comprise the full segment portion and a remainder portion, and wherein writing at least a portion of the unique blocks to the log comprises writing the remainder portion of the unique blocks to the log; and

updating the SUT to mark a segment of the storage medium, used for the full segment portion, as no longer free.

7. The method of claim 1 , wherein the deduplication process is a part of a global segment cleaning processes.

8. A computer system for global deduplication on distributed storage, the computer system comprising:

a processor; and

a non-transitory computer readable medium having stored thereon program code for transferring data to another computer system, the program code causing the processor to:

select, by a deduplication process, candidate segments in a storage medium;

read blocks of the candidate segments;

determine whether any blocks of the candidate segments are duplicates;

update a reference count for the duplicate blocks of the candidate segments;

identify unique blocks of the candidate segments;

write at least a portion of the unique blocks to a log;

determine whether the log has accumulated a full segment of data;

based at least on determining that the log has accumulated a full segment of data, write the full segment of data to the storage medium;

update a segment usage table (SUT) to mark the candidate segments as free; and

update the SUT to mark a segment of the storage medium, used for the full segment of data, as no longer free.

9. The computer system of claim 8 , wherein determining whether any blocks of the candidate segments have duplicates comprises:

hashing the blocks of the candidate segments to generate block hash values; and

determine whether any block hash values match values within a hash table.

10. The computer system of claim 8 , wherein the program code is further operative to:

identify a window having a start time and a stop time, wherein the candidate segments have an age starting within the window.

11. The computer system of claim 10 , wherein the program code is further operative to:

make a first window adjustment by changing at least one of the start time and the stop time;

determine an effect of the first window adjustment on a deduplication score; and

based at least on the deduplication score effect, make a second window adjustment.

12. The computer system of claim 8 , wherein the program code is further operative to:

determine whether sufficient free segments are available for writing to the storage medium; and

based at least on determining that insufficient free segments are available for writing to the storage medium, request allocation of new segments.

13. The computer system of claim 8 , wherein the program code is further operative to:

prior to writing at least a portion of the unique blocks to a log, determine whether the unique blocks comprise at least a full segment of data;

based at least on determining that the unique blocks comprise at least a full segment of data, write a full segment portion of the unique blocks to the storage medium, wherein the unique blocks comprise the full segment portion and a remainder portion, and wherein writing at least a portion of the unique blocks to the log comprises writing the remainder portion of the unique blocks to the log; and

update the SUT to mark a segment of the storage medium, used for the full segment portion, as no longer free.

14. The computer system of claim 8 , wherein the deduplication process is a part of a global segment cleaning processes.

15. A non-transitory computer readable storage medium having stored thereon program code executable by a first computer system at a first site, the program code embodying a method comprising:

selecting, by a deduplication process, candidate segments in a storage medium;

reading blocks of the candidate segments;

determining whether any blocks of the candidate segments are duplicates;

updating a reference count for the duplicate blocks of the candidate segments;

identifying unique blocks of the candidate segments;

writing at least a portion of the unique blocks to a log;

determining whether the log has accumulated a full segment of data;

based at least on determining that the log has accumulated a full segment of data, writing the full segment of data to the storage medium;

updating a segment usage table (SUT) to mark the candidate segments as free; and

updating the SUT to mark a segment of the storage medium, used for the full segment of data, as no longer free.

16. The non-transitory computer storage medium of claim 15 , wherein determining whether any blocks of the candidate segments have duplicates comprises:

hashing the blocks of the candidate segments to generate block hash values; and

determining whether any block hash values match values within a hash table.

17. The non-transitory computer storage medium of claim 15 , wherein the program code further comprises:

identifying a window having a start time and a stop time, wherein the candidate segments have an age starting within the window.

18. The non-transitory computer storage medium of claim 17 , wherein the program code further comprises:

making a first window adjustment by changing at least one of the start time and the stop time;

determining an effect of the first window adjustment on a deduplication score; and

based at least on the deduplication score effect, making a second window adjustment.

19. The non-transitory computer storage medium of claim 15 , wherein the program code further comprises:

determining whether sufficient free segments are available for writing to the storage medium; and

based at least on determining that insufficient free segments are available for writing to the storage medium, requesting allocation of new segments.

20. The non-transitory computer storage medium of claim 15 , wherein the program code further comprises:

prior to writing at least a portion of the unique blocks to a log, determining whether the unique blocks comprise at least a full segment of data;

based at least on determining that the unique blocks comprise at least a full segment of data, writing a full segment portion of the unique blocks to the storage medium, wherein the unique blocks comprise the full segment portion and a remainder portion, and wherein writing at least a portion of the unique blocks to the log comprises writing the remainder portion of the unique blocks to the log; and

updating the SUT to mark a segment of the storage medium, used for the full segment portion, as no longer free.