OPTIMIZING DATA BLOCK SIZE FOR DEDUPLICATION

• US 20140095439A1
• Filed: 03/13/2013
• Published: 04/03/2014
• Est. Priority Date: 10/01/2012
• Status: Active Grant

• Current Assignee: JP Morgan Chase Bank, N.A. (JP Morgan Chase & Co)
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: RAM, TAMIR
• Granted Patent: US 9,626,373 B2
• Time in Patent Office: Days
• US Class Current: 707/640
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: G06F 16/1752 based on file chunks
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• 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/0671 In-line storage system

Abstract

Provided herein is technology relating to data deduplication and particularly, but not exclusively, to methods and systems for determining an efficiently optimal size of data blocks to use for backing up a data source. Also provided herein are systems for identifying duplicate data in data backup applications.

Claims

1. A method for determining an optimal data block size for deduplicating a file type, the method comprising:

a) 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;

b) determining a maximum compression ratio of the function; and

c) choosing a test data block size associated with the maximum compression ratio to be the optimal data block size for the file type.

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

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

b) 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;

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

d) calculating a compression ratio from the file size and the deduplicated result file size.

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

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

5. The 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 method of claim 1 wherein the file has an extension and the file type is determined from the extension.

7. The 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 method of claim 1 wherein the file has a resource fork and the file type is determined from the resource fork.

9. The method of claim 1 wherein the file has metadata and the file type is determined from the metadata.

10. The 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 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.

13. The data backup system of claim 12 further comprising a functionality to construct the table using a method according to claim 1.

12. A data backup system comprising:

i) a table relating a plurality of file types to a plurality of optimal data block sizes;

ii) a deduplication technology;

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

iii) a 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 optimal data block size associated with the file type.

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

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