De-duplication system and method thereof

• US 10,191,934 B2
• Filed: 05/13/2013
• Issued: 01/29/2019
• Est. Priority Date: 05/13/2013
• Status: Active Grant

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Hayasaka, Mitsuo, Kamei, Hitoshi, Sutoh, Atsushi
• Primary Examiner(s): Harper, Eliyah S.
• Application Number:
  US14/760,721
• Publication Number:
  US 20150356134A1
• Time in Patent Office: 2,087 Days
• Field of Search: 707698
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 16/1752 based on file chunks
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/2291 User-Defined Types; Storage management thereof
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• 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]

Abstract

Chunk de-duplication performance is improved. A de-duplication system has a cut-out processing unit which inputs a content from a client terminal thereinto, determines a calculation range from a predetermined maximum chunk size and a predetermined minimum chunk size, divides the calculation range into at least two small calculation ranges, sets the positions of windows for rolling hash calculation so that the rolling hash calculation is continuous between the two small calculation ranges, and subjects the at least two small calculation ranges to the rolling hash calculation with shifting of the windows based on parallel processing to cut out a chunk from the content, and a de-duplication processing unit which does not store the cut-out chunk into a storage device when the chunk having the same contents as those of the cut-out chunk is already stored in the storage device.

Claims

1. A de-duplication system comprising:

a memory;

a first storage device;

a second storage device;

a first processor, wherein the processor;

determines a calculation range of content input from a client terminal based upon a predetermined maximum chunk size and a predetermined minimum chunk size,

sets at least a first and second small calculation ranges, both the first and second small calculation ranges being smaller than the first calculation range,

sets the positions of windows for rolling hash calculation with respect to the first and second small calculation ranges at integral multiples of a width of each of the windows so that successive windows overlap, and

subjects the at least first and second small calculation ranges to a rolling hash calculation with shifting of the windows set to the first and second small calculation ranges based on parallel processing to form a cut-out chunk from the content; and

a second processor communicatively coupled to the memory, the first storage device, the second storage device, and the first processor, wherein the second processor;

does not store the cut-out chunk into the first storage device when the chunk having the same contents as the cut-out chunk is already stored in the first storage device.

2. The de-duplication system according to claim 1, wherein the first processor divides the calculation range into at least two division ranges, and divides each of the division ranges into the at least first and second small calculation ranges.

3. The de-duplication system according to claim 2, wherein the first processor subjects the calculation range less than a predetermined minimum fine grain calculation length to the rolling hash calculation with shifting of the windows based on serial processing to cut out the chunk from the content.

4. The de-duplication system according to claim 3, wherein the first processor subjects the at least first and second division ranges to the rolling hash calculation with shifting of the windows based on parallel processing by a plurality of CPUs.

5. The de-duplication system according to claim 2, wherein first processor sets each of the division ranges to a variable fine grain calculation length, measures performance of parallel processing in the at least first and second small calculation ranges of the rolling hash calculation with shifting of the windows, updates the variable fine grain calculation length when the measured performance is improved, and sets the division ranges to the updated variable fine grain calculation length to repeat the measurement of the performance.

6. The de-duplication system according to claim 1, wherein first processor assumes that 0×

0 data is continuous by the size of the windows before setting the window position, changes the position of the windows so that the windows include the 0×

0 data, and executes the rolling hash calculation with shifting of the windows.

7. The de-duplication system according to any one of claim 1, wherein the first processor divides the content into a number of multiple nodes so that the rolling hash calculation between the multiple nodes is continuous, each of the multiple nodes setting the calculation range in the divided content to cut out the chunk.

8. A de-duplication method in a de-duplication system which de-duplicates a chunk stored into a storage device, the de-duplication method comprising the steps of:

inputting a content from a client terminal;

determining a calculation range from a predetermined maximum chunk size and a predetermined minimum chunk size;

dividing the calculation range into at least first and second small calculation ranges;

setting the positions of windows for rolling hash calculation at integral multiples of a width of each of the windows so that successive windows overlap;

subjecting the at least first and second small calculation ranges to a rolling hash calculation with shifting of the windows based on parallel processing to form a cut-out chunk from the content; and

not storing the cut-out chunk into the storage device when the chunk having the same contents as those of the cut-out chunk is already stored into the storage device.

9. The de-duplication method according to claim 8, further comprising the steps of:

dividing the calculation range into at least first and second division ranges; and

dividing each of the division ranges into the at least first and second small calculation ranges.

10. The de-duplication method according to claim 9, further comprising the step of subjecting the calculation range less than a predetermined minimum fine grain calculation length to the rolling hash calculation with shifting of the windows based on serial processing to cut out the chunk from the content.

11. The de-duplication method according to claim 10, further comprising the step of subjecting the at least first and second division ranges to the rolling hash calculation with shifting of the windows based on parallel processing by a plurality of CPUs.

12. The de-duplication method according to claim 9, further comprising the steps of:

setting each of the division ranges to a variable fine grain calculation length;

measuring performance of parallel processing in the at least first and second small calculation ranges of the rolling hash calculation with shifting of the windows;

updating the variable fine grain calculation length when the measured performance is improved; and

setting the division range to the updated variable fine grain calculation length to repeat the measurement of the performance.

13. The de-duplication method according to claim 8, further comprising the steps of:

assuming that 0×

0 data is continuous by the size of the windows before setting the position of the windows

changing the positions of the windows so that the windows include the 0×

0 data; and

executing the rolling hash calculation with shifting of the windows.

14. The de-duplication method according to claim 8, further comprising the step of dividing the content into a number of multiple nodes so that the rolling hash calculation between the multiple nodes is continuous, each of the multiple nodes setting the calculation range in the divided content to cut out the chunk.