EXTENSIBLE DATA DEDUPLICATION SYSTEM AND METHOD

• US 20110231362A1
• Filed: 03/16/2010
• Published: 09/22/2011
• Est. Priority Date: 03/16/2010
• Status: Active Grant

• Current Assignee: CommVault Systems Incorporated
• Original Assignee: CommVault Systems Incorporated
• Inventors: ATTARDE, DEEPAK, Vijayan, Manoj Kumar
• Granted Patent: US 8,732,133 B2
• Time in Patent Office: Days
• US Class Current: 707/609
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/3442 for planning or managing the needed capacity
• CPC Class Codes: G06F 11/3466 Performance evaluation by tracing or monitoring
• 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 2201/81 Threshold

Abstract

A system and method for data deduplication is presented. A deduplication system includes a plurality of data deduplication nodes; and a data deduplication control node communicatively coupled to the plurality of data deduplication nodes. The deduplication control node performs the operations of performing data deduplication operations at a deduplication system having one or more deduplication nodes at which deduplication data blocks are stored; monitoring a performance characteristic of the deduplication system; and adding an additional deduplication node to the deduplication system when the performance characteristic indicates performance of the system below a predetermined minimum.

Claims

1. A computer-implemented method for performing data deduplication for data, the method comprising:

a deduplication control node performing data deduplication operations at a deduplication system having one or more deduplication nodes at which deduplication data blocks are stored, the deduplication control node comprising hardware or a combination of hardware and software;

the deduplication control node monitoring a performance characteristic of the deduplication system; and

the deduplication control node adding an additional deduplication node to the deduplication system when the performance characteristic indicates performance of the system below a predetermined minimum.

2. The computer-implemented method of claim 1, further comprising the step of migrating one or more data blocks from the one or more deduplication nodes of the deduplication system to the additional deduplication node added to the deduplication system.

3. The computer-implemented method of claim 1, further comprising the operation of rebalancing data stored in the data deduplication system across the one or more deduplication nodes and the additional deduplication node.

4. The computer-implemented method of claim 3, wherein data blocks stored in the one or more nodes are represented by hash values stored in a deduplication database and wherein the operation of rebalancing comprises:

performing a modulo arithmetic operation on the hash values of the data blocks stored in the one or more nodes;

determining a remainder from the modulo arithmetic operation; and

relocating some or all of the data blocks among at least one of the one or more deduplication nodes and the additional deduplication node using the remainder from the modulo arithmetic operation for a hash of a given data block to determine in which node to store the given data block.

5. The computer-implemented method of claim 4, wherein the modulo arithmetic operation comprises a modulo N operation, where N is the quantity of the one or more deduplication nodes and the additional deduplication node.

6. The computer-implemented method of claim 1, wherein data blocks stored in the one or more nodes are represented by hash values stored in a deduplication data base, and further comprising:

calculating hash identifiers for the hash values, wherein a hash identifier uniquely identifies a group of one or more hash values; and

associating a hash identifier with hash values in the group of hash values identified by the hash identifier.

7. The computer implemented method of claim 6, wherein the hash identifier comprises a CRC checksum computed for one or more hash values.

8. The computer implemented method of claim 6, further comprising:

receiving a data block for deduplication;

calculating a hash value for the data block received;

calculating a hash identifier for the hash value calculated for the received data block;

comparing the calculated hash identifier with existing hash identifiers to identify a matching hash identifier associated with one or more hash values; and

comparing the hash value with the one or more hash values associated with the identified matching hash identifier to determine whether the hash value calculated for the data block received matches a hash value already stored for a data block in the database.

9. The computer-implemented method of claim 3, wherein data blocks stored in the one or more nodes are represented by hash values stored in a deduplication database and wherein the operation of rebalancing comprises:

defining a plurality of ranges of the hash values;

assigning each of the one or more deduplication nodes and the additional deduplication node to one of the plurality of ranges of hash values; and

relocating some or all of the data blocks to a deduplication node to which their respective hash values are assigned.

10. The computer-implemented method of claim 9, further comprising:

the network control node determining a hash value for a received data block;

determining which one of the plurality of ranges the hash value determined for the received block belongs to; and

storing the received data block in a data deduplication note to which the determined range is assigned.

11. The computer-implemented method of claim 1, wherein the performance characteristic comprises consumed capacities of nodes in the deduplication database, available capacities of nodes in the deduplication database, throughput of nodes in the deduplication database, frequency of hits to nodes in the deduplication database, performance of nodes in the deduplication database, network traffic at nodes in the deduplication database, and speed of nodes in the deduplication database.

12. A computer program product comprising a computer-readable storage medium having computer program code embodied therein for enabling a computing device to perform data deduplication for data received from a plurality of computing systems, the computer-readable program code configured to cause the computing device to perform the operations of:

performing a data deduplication operation at a deduplication system having one or more deduplication nodes at which deduplication data blocks are stored;

monitoring a performance characteristic of the deduplication system;

adding an additional deduplication node to the deduplication system when the performance characteristic indicates performance of the system below a predetermined minimum.

13. The computer program product of claim 12, wherein the computer-readable program code is further configured to cause the computing device to perform the operation of migrating one or more data blocks from the one or more deduplication nodes of the deduplication system to the additional deduplication node added to the deduplication system.

14. The computer program product of claim 12, wherein the computer-readable program code is further configured to cause the computing device to perform the operation of rebalancing data stored in the data deduplication system across the one or more deduplication nodes and the additional deduplication node.

15. The computer program product of claim 14, wherein data blocks stored in the one or more nodes are represented by hash values stored in a deduplication database and wherein the operation of rebalancing comprises:

performing a modulo arithmetic operation on the hash values of the data blocks stored in the one or more nodes;

determining a remainder from the modulo arithmetic operation; and

relocating some or all of the data blocks among at least one of the one or more deduplication nodes and the additional deduplication node using the remainder from the modulo arithmetic operation for a hash of a given data block to determine in which node to store the given data block.

16. The computer program product of claim 14, wherein the modulo arithmetic operation comprises a modulo N operation, where N is the quantity of the one or more deduplication nodes and the additional deduplication node.

17. The computer program product of claim 12, wherein data blocks stored in the one or more nodes are represented by hash values stored in a deduplication data base, and further comprising:

calculating hash identifiers for the hash values, wherein a hash identifier uniquely identifies a group of one or more hash values; and

associating a hash identifier with hash values in the group of hash values identified by the hash identifier.

18. The computer program product of claim 12, wherein the hash identifier comprises a CRC checksum computed for one or more hash values.

19. The computer program product of claim 12, wherein the computer-readable program code is further configured to cause the computing device to perform the operations of:

receiving a data block for deduplication;

calculating a hash value for the data block received;

calculating a hash identifier for the hash value calculated for the received data block;

comparing the calculated hash identifier with existing hash identifiers to identify a matching hash identifier associated with one or more hash values; and

comparing the hash value with the one or more hash values associated with the identified matching hash identifier to determine whether the hash value calculated for the data block received matches a hash value already stored for a data block in the database.

20. The computer program product of claim 14, wherein data blocks stored in the one or more nodes are represented by hash values stored in a deduplication database and wherein the operation of rebalancing comprises:

defining a plurality of ranges of the hash values;

assigning each of the one or more deduplication nodes and the additional deduplication node to one of the plurality of ranges of hash values; and

relocating some or all of the data blocks to a deduplication node to which their respective hash values are assigned.

21. The computer program product of claim 14, wherein the computer-readable program code is further configured to cause the computing device to perform the operations of:

determining a hash value for a received data block;

determining which one of the plurality of ranges the hash value determined for the received block belongs to; and

storing the received data block in a data deduplication note to which the determined range is assigned.

22. A computing system, comprising:

a plurality of data deduplication nodes; and

a data deduplication control node communicatively coupled to the plurality of data deduplication nodes and comprising a processor and memory communicatively coupled to the processor, the memory storing instructions to cause the processor to perform the operations of;

performing data deduplication operations at a deduplication system having one or more deduplication nodes at which deduplication data blocks are stored;

monitoring a performance characteristic of the deduplication system; and

adding an additional deduplication node to the deduplication system when the performance characteristic indicates performance of the system below a predetermined minimum.

23. The computing system of claim 22, wherein the deduplication control node comprises one of the plurality of deduplication nodes or is distributed across a plurality of deduplication nodes.

24. The computing system of claim 22, wherein the instructions further cause the computing device to perform the operation of migrating one or more data blocks from the one or more deduplication nodes of the deduplication system to the additional deduplication node added to the deduplication system.

25. The computing system of claim 22, wherein the instructions further cause the computing device to perform the operation of rebalancing data stored in the data deduplication system across the one or more deduplication nodes and the additional deduplication node.

26. The computing system of claim 25, wherein data blocks stored in the one or more nodes are represented by hash values stored in a deduplication database and wherein the operation of rebalancing comprises:

performing a modulo arithmetic operation on the hash values of the data blocks stored in the one or more nodes;

determining a remainder from the modulo arithmetic operation; and

relocating some or all of the data blocks among at least one of the one or more deduplication nodes and the additional deduplication node using the remainder from the modulo arithmetic operation for a hash of a given data block to determine in which node to store the given data block.

27. The computing system of claim 26, wherein the modulo arithmetic operation comprises a modulo N operation, where N is the quantity of the one or more deduplication nodes and the additional deduplication node.

28. The computing system of claim 22, wherein data blocks stored in the one or more nodes are represented by hash values stored in a deduplication data base, and further comprising:

calculating hash identifiers for the hash values, wherein a hash identifier uniquely identifies a group of one or more hash values; and

associating a hash identifier with hash values in the group of hash values identified by the hash identifier.

29. The computing system of claim 28, wherein the hash identifier comprises a CRC checksum computed for one or more hash values.

30. The computing system of claim 28, wherein the instructions further cause the computing device to perform the operations of:

receiving a data block for deduplication;

calculating a hash value for the data block received;

calculating a hash identifier for the hash value calculated for the received data block;

comparing the calculated hash identifier with existing hash identifiers to identify a matching hash identifier associated with one or more hash values;

comparing the hash value with the one or more hash values associated with the identified matching hash identifier to determine whether the hash value calculated for the data block received matches a hash value already stored for a data block in the database.

31. The computing system of claim 25, wherein data blocks stored in the one or more nodes are represented by hash values stored in a deduplication database and wherein the operation of rebalancing comprises:

defining a plurality of ranges of the hash values;

assigning each of the one or more deduplication nodes and the additional deduplication node to one of the plurality of ranges of hash values; and

relocating some or all of the data blocks to a deduplication node to which their respective hash values are assigned.

32. The computing system of claim 25, wherein the instructions further cause the computing device to perform the operations of:

determining a hash value for a received data block;

determining which one of the plurality of ranges the hash value determined for the received block belongs to; and

storing the received data block in a data deduplication note to which the determined range is assigned.