Granted Patent B1

US 8,898,120 · App. 13/269,620 · Granted Nov 25, 2014

Inventor: Petros Efstathopoulos (Los Angeles, CA)

Assignee: Symantec Corporation

G06F17/3007G06F17/30097

Abstract

Claims (50)

1. A computer-implemented method for distributed data deduplication, at least a portion of the method being performed by a computing device comprising at least one processor, the method comprising:

identifying a deduplicated data system, the deduplicated data system comprising a plurality of nodes, wherein each node within the plurality of nodes is configured to deduplicate data stored on the node;

identifying a data object to store within the deduplicated data system;

generating a similarity hash of the data object, the similarity hash representing a probabilistic dimension-reduction of the data object;

determining, based on at least one characteristic of the data object, that block-level deduplication is more efficient for the data object that file-level deduplication;

selecting a target node from the plurality of nodes that uses block-level deduplication instead of a candidate node that uses file-level deduplication based at least in part on the similarity hash and at least in part on a determination that the target node uses block-level deduplication instead of file-level deduplication;

routing the data object for storage on the target node based on the selection of the target node.

2. The computer-implemented method of claim 1 , wherein selecting the target node from the plurality of nodes is further based on an aggregation of similarity hashes of data objects stored on the target node.

3. The computer-implemented method of claim 1 , wherein:

generating the similarity hash comprises generating the similarity hash using an algorithm that maps data objects onto a hash space;

the hash space is partitioned among the plurality of nodes;

selecting the target node from the plurality of nodes comprises determining that the similarity hash falls within a partition of the hash space corresponding to the target node.

4. The computer-implemented method of claim 1 , further comprising determining, based on at least one attribute of the data object, to generate at least one additional similarity hash of the data object;

wherein selecting the target node is further based on the additional similarity hash.

5. The computer-implemented method of claim 4 , wherein the attribute of the data object comprises the size of the data object.

6. The computer-implemented method of claim 4 , wherein the attribute of the data object comprises a file type of the data object.

7. The computer-implemented method of claim 1 , wherein selecting the target node is further based on a file type of the data object.

8. The computer-implemented method of claim 1 , wherein selecting the target node is further based on a storage load on the target node falling below a determined threshold.

9. The computer-implemented method of claim 1 , wherein selecting the target node is further based on a frequency with which a client that accesses the deduplicated data system accesses the target node.

10. A system for distributed data deduplication, the system comprising:

an identification module programmed to:

identify a deduplicated data system, the deduplicated data system comprising a plurality of nodes, wherein each node within the plurality of nodes is configured to deduplicate data stored on the node;

identify a data object to store within the deduplicated data system;

a hashing module programmed to generate a similarity hash of the data object, the similarity hash representing a probabilistic dimension-reduction of the data object;

a selection module programmed to:

determine, based on at least one characteristic of the data object, that block-level deduplication is more efficient for the data object that file-level deduplication;

select a target node from the plurality of nodes that uses block-level deduplication instead of a candidate node that uses file-level deduplication based at least in part on the similarity hash and at least in part on a determination that the target node uses block-level deduplication instead of file-level deduplication;

a routing module programmed to route the data object for storage on the target node based on the selection of the target node;

at least one processor configured to execute the identification module, the hashing module, the selection module, and the routing module.

11. The system of claim 10 , wherein the selection module is programmed to select the target node from the plurality of nodes further based on an aggregation of similarity hashes of data objects stored on the target node.

12. The system of claim 10 , wherein:

the hashing module is programmed to generate the similarity hash by using an algorithm that maps data objects onto a hash space;

the hash space is partitioned among the plurality of nodes;

the selection module is programmed to select the target node from the plurality of nodes by determining that the similarity hash falls within a partition of the hash space corresponding to the target node.

13. The system of claim 10 , wherein:

the hashing module is further programmed to determine, based on at least one attribute of the data object, to generate at least one additional similarity hash of the data object;

the selection module is programmed to select the target node further based on the additional similarity hash.

14. The system of claim 13 , wherein the attribute of the data object comprises the size of the data object.

15. The system of claim 13 , wherein the attribute of the data object comprises a file type of the data object.

16. The system of claim 10 , wherein the selection module is programmed to select the target node further based on a file type of the data object.

17. The system of claim 10 , wherein the selection module is programmed to select the target node further based on a storage load on the target node falling below a determined threshold.

18. The system of claim 10 , wherein the selection module is programmed to select the target node further based on a frequency with which a client that accesses the deduplicated data system accesses the target node.

19. A non-transitory computer-readable-storage medium comprising one or more computer-executable instructions that are executed by at least one processor of a computing device and cause the computing device to:

identify a deduplicated data system, the deduplicated data system comprising a plurality of nodes, wherein each node within the plurality of nodes is configured to deduplicate data stored on the node;

identify a data object to store within the deduplicated data system;

generate a similarity hash of the data object, the similarity hash representing a probabilistic dimension-reduction of the data object;

determine, based on at least one characteristic of the data object, that block-level deduplication is more efficient for the data object that file-level deduplication;

select a target node from the plurality of nodes that uses block-level deduplication instead of a candidate node that uses file-level deduplication based at least in part on the similarity hash and at least in part on a determination that the target node uses block-level deduplication instead of file-level deduplication;

route the data object for storage on the target node based on the selection of the target node.

20. The computer-readable-storage medium of claim 19 , wherein selecting the target node from the plurality of nodes is further based on an aggregation of similarity hashes of data objects stored on the target node.

Assignments (14)