DEDUPLICATION OF FILE

• US 20150347445A1
• Filed: 05/29/2015
• Published: 12/03/2015
• Est. Priority Date: 05/30/2014
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Zhu, Guo Feng
• Granted Patent: US 10,769,112 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/1752 based on file chunks

Abstract

The present invention discloses a method for deduplication of a file, a computer program product, and an apparatus thereof. In the method, the file is partitioned into at least one composite block, wherein the composite block includes a fixed-size block and a variable-size block, the variable-size block being determined based on content of the file. Then a deduplication operation is performed on the at least one composite block.

Claims

1. A method for deduplication of a file, comprising:

partitioning, by one or more processors, a file into at least one composite block, wherein each composite block includes;

a fixed-size block, wherein the fixed-size block is of a first fixed length; and

a variable-size block, wherein the variable-size block is of a length determined based on content of the file; and

performing, by one or more processors, a deduplication operation on at least a first composite block of the at least one composite block.

2. The method of claim 1, wherein partitioning the file into the at least one composite block comprises:

determining, by one or more processors, a start boundary for the fixed-size block;

determining, by one or more processors, an end boundary for the fixed-size block, such that the length of the fixed-size block is the first fixed length;

identifying, by one or more processors, the end boundary for the fixed-size block as a start boundary for the variable-size block; and

determining, by one or more processors, an end boundary for the variable-size block based on, at least, the content of the file.

3. The method of claim 2, wherein determining the start boundary for the fixed-size block comprises:

identifying, by one or more processors, a beginning of the file as the start boundary of the fixed-size block.

4. The method of claim 2, wherein determining the start boundary for the fixed-size block comprises:

identifying, by one or more processors, another composite block in the file; and

identifying, by one or more processors, an end boundary for a variable-size block of the another composite block as the start boundary for the fixed-size block.

5. The method of claim 2, wherein determining the end boundary for the variable-size block based on, at least, the content of the file comprises:

moving, by one or more processors, a sliding window of a second fixed length along the file to a position, starting from the end boundary for the fixed-size block;

obtaining, by one or more processors, a data block within a sliding window;

calculating, by one or more processors, a hash value of the data block within the sliding window;

determining, by one or more processors, that the hash value of the data block within the sliding window meets a first predetermined condition; and

identifying, by one or more processors, the end boundary for the variable-size block based on, at least, the position of the sliding window.

6. The method of claim 2, wherein determining the end boundary for the variable-size block based on, at least the content of the file comprises:

moving, by one or more processors, a sliding window of a second fixed length along the file to a position, starting from the end boundary for the fixed-size block;

obtaining, by one or more processors, a data block within the sliding window;

calculating, by one or more processors, a hash value of the data block within the sliding window;

determining, by one or more processors, that the hash value of the data block within the sliding window does not meet a first predetermined condition;

determining, by one or more processors, a length from the start boundary for the variable-size block to the position of the sliding window;

determining, by one or more processors, that the length from the start boundary for the variable-size block to the position of the sliding window is at least equal to a predetermined maximum length; and

identifying, by one or more processors, the end boundary for the variable-size block based on, at least, the position of the sliding window.

7. The method of claim 5, wherein the first predetermined condition is satisfied if the hash value of the data block modulo a first integer equals a first value, wherein the first value is less than the first integer.

8. The method of claim 2, wherein determining the end boundary for the variable-size block based on, at least the content of the file comprises:

moving, by one or more processors, a sliding window of a second fixed length along the file to a position, starting from the end boundary for the fixed-size block;

obtaining, by one or more processors, a data block within the sliding window;

calculating, by one or more processors, a hash value of the data block within the sliding window;

determining, by one or more processors, that the hash value of the data block within the sliding window does not meet a first predetermined condition, wherein the first predetermined condition is satisfied if the hash value of the data block modulo a first integer equals a first value, wherein the first value is less than the first integer;

determining, by one or more processors, that the hash value of the data block within the sliding window does meet a second predetermined condition, wherein the second predetermined condition is satisfied if the hash value of the data block modulo a second integer equals a second value, wherein the second integer is less than the first integer, and wherein the second value is less than the second integer; and

identifying, by one or more processors, the end boundary for the variable-size block based on, at least, the position of the sliding window.

9. The method of claim 2, further comprising:

moving, by one or more processors, a sliding window of a second fixed length along the file to a first position, starting from the end boundary for the fixed-size block;

obtaining, by one or more processors, a data block within the sliding window;

calculating, by one or more processors, a hash value of the data block within the sliding window;

determining, by one or more processors, that the hash value of the data block within the sliding window does meet a second predetermined condition, wherein the second predetermined condition is satisfied if the hash value of the data block modulo a second integer equals a second value, wherein the second integer is less than a first integer of a first predetermined condition, and wherein the second value is less than the second integer;

determining, by one or more processors, that the first position of the sliding window has not previously been recorded for the variable-size block; and

recording, by one or more processors, an alternative end boundary for the variable-size block based on, at least, the first position of the sliding window.

10. The method of claim 9, wherein determining the end boundary for the variable-size block based on, at least the content of the file comprises:

moving, by one or more processors, the sliding window of the second fixed length along the file to a second position;

determining, by one or more processors, a length from the start boundary for the variable-size block to the second position of the sliding window;

determining, by one or more processors, that the length from the start boundary for the variable-size block to the second position of the sliding window is at least equal to a predetermined maximum length; and

identifying, by one or more processors, the alternative end boundary for the variable-size block as the end boundary for the variable-size block.

11. The method of claim 1, wherein performing the deduplication operation on at least the first composite block of the at least one composite block comprises:

calculating, by one or more processors, a hash value of the fixed-size block;

determining, by one or more processors, that the hash value of the fixed-size block is found in a hash table;

discarding, by one or more processors, the fixed-size block;

calculating, by one or more processors, a hash value of the variable-size block;

determining, by one or more processors, that the hash value of the variable-size block is found in the hash table; and

discarding, by one or more processors, the variable-size block.

12. An apparatus for deduplication of a file, comprising:

a partitioning module configured to partition a file into at least one composite block, wherein each composite block includes;

a fixed-size block, wherein the fixed-size block is of a first fixed length; and

a variable-size block, wherein the variable-size block is of a length determined based on content of the file; and

a deduplication module configured to perform a deduplication operation on the at least a first composite block of the at least one composite block.

13. The apparatus of claim 12, wherein the partitioning module includes:

a fixed-size block determination module configured to determine a start boundary for the fixed-size block and to determine an end boundary for the fixed-size block, such that the length of the fixed-size block is the first fixed length; and

a variable-size block determination module configured to identify the end boundary for the fixed-size block as a start boundary for the variable-size block and determine an end boundary of the variable-size block based on the content of the file, with the end boundary for the variable-size block based on, at least, the content of the file.

14. The apparatus of claim 13, wherein the fixed-size block determination module is further configured to identify another composite block in the file and determine an end boundary for a variable-size block of the another composite block as the start boundary for the fixed-size block.

15. The apparatus of claim 13, wherein the variable-size block determination module includes:

a data block obtaining unit configured to obtain a data block within a sliding window having a second fixed length, wherein the sliding window is moved along the file to a position, starting from the end boundary for the fixed-size block; and

a boundary determination unit configured to determine that a calculated hash value of the data block within the sliding window meets a first predetermined condition and identify the end boundary for the variable-size block based on, at least, the position of the sliding window.

16. The apparatus of claim 13, wherein the variable-size block determination module further includes:

a data block obtaining unit configured to obtain a data block within a sliding window having a second fixed length, wherein the sliding window is moved along the file to a position, starting from the end boundary for the fixed-size block;

a length determination unit configured to determine that a hash value of the data block within the sliding window does not meet a first predetermined condition and determine a length from the start boundary for the variable-size block to the position of the sliding window; and

a boundary determination unit configured to determine that the length from the start boundary for the variable-size block to the position of the sliding window is at least equal to a predetermined maximum length and identify the end boundary for the variable-size block based on, at least, the position of the sliding window.

17. The apparatus of claim 15, wherein the predetermined condition is satisfied if the has value of the data block modulo a first integer equals a first value, wherein the first value is less than the first integer.

18. The apparatus of claim 13, wherein the variable-size block determination module further includes:

a data block obtaining unit configured to obtain a data block within a sliding window having a second fixed length, wherein the sliding window is moved along the file to a position, starting from the end boundary for the fixed-size block; and

a boundary determination unit configured to;

determine that a calculated hash value of the data block within the sliding window does not meets a first predetermined condition, wherein the first predetermined condition is satisfied if the hash value of the data block modulo a first integer equals a first value, wherein the first value is less than the first integer;

determine that the calculated hash value of the data block within the sliding window does meet a second predetermined condition, wherein the second predetermined condition is satisfied if the hash value of the data block modulo a second integer equals a second value, wherein the second integer is less than the first integer, and wherein the second value is less than the second integer; and

identify the end boundary for the variable-size block based on, at least, the position of the sliding window.

19. The apparatus of claim 13, wherein the variable-size block determination module further includes:

a data block obtaining unit configured to obtain a data block within a sliding window having a second fixed length, wherein the sliding window is moved along the file to a first position, starting from the end boundary for the fixed-size block;

a boundary determination unit configured to determine that a hash value of the data block within the sliding window does meet a second predetermined condition, wherein the second predetermined condition is satisfied if the hash value of the data block modulo a second integer equals a second value, wherein the second integer is less than a first integer of a first predetermined condition, and wherein the second value is less than the second integer;

a checking unit configured to determine that the first position of the sliding window has not previously been recorded for the variable-size block; and

a recording unit configured to record an alternative end boundary for the variable-size block based on, at least, the first position of the sliding window.

20. A computer program product for deduplication of a file, comprising:

one or more computer readable storage media and program instructions stored on the one or more computer readable storage media, the program instructions comprising;

program instructions to partition a file into at least one composite block, wherein each composite block includes;

a fixed-size block, wherein the fixed-size block is of a first fixed length; and

a variable-size block, wherein the variable-size block is of a length determined based on content of the file; and

program instructions to perform a deduplication operation on at least a first composite block of the at least one composite block.