Granted Patent B2

US 9,626,373 · App. 13/802,167 · Granted Apr 18, 2017

Abstract

Claims (49)

1. A computer-implemented method for determining a first data block size for deduplicating a file type, the method comprising:

constructing a function relating a plurality of compression ratios to a plurality of test data block sizes, wherein a compression ratio of the plurality of compression ratios is calculated by transforming a file of the file type using a deduplication technology and a test data block size of the plurality of test data block sizes;

determining a maximum compression ratio of the function;

choosing a test data block size associated with the maximum compression ratio to be the first data block size for the file type; and

deduplicating a data block of the first data block size based on a sliding window, wherein deduplicating the data block comprises:

calculating a first hash value to identify a potential data block; and

calculating a second hash value to identify the duplicate data block,

wherein a beginning of the sliding window is set at an end of a duplicate data block when the duplicate data block is detected, and wherein the sliding window moves backwards when the duplicate data block is not detected.

2. The computer-implemented method of claim 1 wherein constructing the function relating a plurality of compression ratios to a plurality of test data block sizes further comprises:

providing a file of the file type, wherein the file has a file size;

generating a plurality of data blocks from the file, wherein each data block of the plurality of data blocks has a size that is the test data block size;

applying the deduplication technology to the plurality of data blocks to produce a deduplicated result file, wherein the deduplicated result file has a deduplicated size; and

calculating a compression ratio from the file size and the deduplicated size.

3. The computer-implemented method of claim 1 wherein the file is selected from a collection of files of the same file type.

4. The computer-implemented method of claim 3 wherein the function is constructed using all files from the collection of files of the same file type.

5. The computer-implemented method of claim 1 wherein:

the file comprises a plurality of data bytes; and

the file type is determined by examining a data byte from the plurality of data bytes.

6. The computer-implemented method of claim 1 wherein:

the file has an extension; and

the file type is determined from the extension.

7. The computer-implemented method of claim 1 wherein the file type is selected from the group consisting of application, image, text file, source code, audio, video, database, spreadsheet, word processing document, system file, directory, disk image, archive, portable document, binary file, vector image, font, computer aided design, compressed, physical recordable media archiving, electronic design automation, desktop publishing, document, geographic information system, graphical information organizer, color palette, raster graphics, 3D graphics, mathematical, object code, shared library, dynamic linked library, page description, personal information manager, presentation, project management, reference management, scientific data, script, game, virtual machine, man file, webpage, markup language, and financial record.

8. The computer-implemented method of claim 1 wherein:

the file has a resource fork; and

the file type is determined from the resource fork.

9. The computer-implemented method of claim 1 wherein:

the file has metadata; and

the file type is determined from the metadata.

10. The computer-implemented method of claim 1 wherein the function is a model relating the plurality of compression ratios to the plurality of test data block sizes.

11. The computer-implemented method of claim 1 wherein the function is an interpolation based on the plurality of compression ratios and the plurality of test data block sizes.

12. A data backup system comprising:

a table relating a plurality of file types to a plurality of selected data block sizes;

a deduplication technology;

a functionality to receive a data source having a file type; and

a hardware processor configured to:

generate a plurality of data blocks from the data source, wherein each data block of the plurality of data blocks has a size that is the selected data block size associated with the file type; and

deduplicate a data block based on a sliding window wherein deduplicating the data block comprises:

calculating a first hash value to identify a potential data block; and

calculating a second hash value to identify the duplicate data block,

wherein a beginning of the sliding window is set at an end of a duplicate data block when the duplicate data block is detected, and wherein the sliding window moves backwards when the duplicate data block is not detected.

13. The data backup system of claim 12 further comprising a functionality to construct the table based on a function, wherein the hardware processor is further configured to:

construct the function relating a plurality of compression ratios to a plurality of test data block sizes, wherein a compression ratio of the plurality of compression ratios is calculated by transforming a file of the file type using a deduplication technology and a test data block size of the plurality of test data block sizes.

14. The data backup system of claim 12 wherein the data source is a file.

15. The data backup system of claim 12 wherein the data source is a file system.

16. The data backup system of claim 12 wherein the data source comprises a plurality of files.

17. The data backup system of claim 16 wherein the plurality of files resides on a plurality of machines, computers, volumes, storage media, memories, locations, or network nodes.

18. The data backup system of claim 12 wherein the data backup system is local to the data source.

19. The data backup system of claim 12 wherein the data backup system is remote from the data source.

20. The data backup system of claim 12 further comprising a pre-populated plurality of data blocks generated from standard files of an operating system or file system.

Assignments (12)