Systems and methods for performing lookups on distributed deduplicated data systems
A computer-implemented method for performing lookups on distributed deduplicated data systems may include (1) identifying a collection of deduplicated data stored within a plurality of nodes, (2) identifying a request to locate a deduplicated object of the collection within the plurality of nodes, (3) identifying a fingerprint of the deduplicated object, the fingerprint being generated using an algorithm that maps deduplicated objects onto a fingerprint space, (4) directing the request, based on a partitioning scheme that divides the fingerprint space among the plurality of nodes, to a first node within the plurality of nodes that is responsible for forwarding requests pertaining to a partition of the fingerprint space that includes the fingerprint, and (5) forwarding the request from the first node to a second node identified by the first node as corresponding to the fingerprint. Various other methods, systems, and computer-readable media are also disclosed.
1. A computer-implemented method for performing lookups on distributed deduplicated data systems, at least a portion of the method being performed by a computing device comprising at least one processor, the method comprising:
identifying a collection of deduplicated data stored within a plurality of nodes;
identifying a request to locate a deduplicated object of the collection within the plurality of nodes;
identifying a fingerprint of the deduplicated object, the fingerprint being generated using an algorithm that maps deduplicated objects onto a fingerprint space, the fingerprint space comprising a set of possible fingerprint values generated using the algorithm;
directing the request, based on a partitioning scheme that divides the fingerprint space among the plurality of nodes, to a first node within the plurality of nodes that is responsible for forwarding requests pertaining to a partition of the fingerprint space that comprises the fingerprint;
forwarding the request from the first node to a second node identified by the first node as corresponding to the fingerprint, wherein the first node identifies the second node as corresponding to the fingerprint by using data stored by the first node that associates fingerprints that fall within the partition of the fingerprint space with nodes in which deduplicated data objects corresponding to the fingerprints that fall within the partition of the fingerprint space are expected to be found;
locating the deduplicated data object of the collection as being stored at the second node;
in response to locating the deduplicated data object at the second node, at least one of:
retrieving the deduplicated data object from the second node;
replacing an instance of data with a reference to the deduplicated data object stored at the second node.
2. The computer-implemented method of claim 1 , wherein identifying the collection of deduplicated data comprises identifying a collection of deduplicated data originating from a plurality of clients.
3. The computer-implemented method of claim 2 , wherein:
identifying the request comprises identifying a request from a client within the plurality of clients;
at least one home node within the plurality of nodes is designated for storing unique objects added to the collection of deduplicated data from the client.
4. The computer-implemented method of claim 1 , further comprising:
in response to the request, identifying the deduplicated object on the second node;
identifying a subsequent request to locate an additional deduplicated object of the collection within the plurality of nodes;
forwarding the subsequent request directly to the second node based on having identified the deduplicated object on the second node.
5. The computer-implemented method of claim 1 , further comprising:
in response to an additional request, determining that the deduplicated object does not exist on the second node;
identifying a subsequent request to locate an additional deduplicated object of the collection within the plurality of nodes;
identifying an additional fingerprint of the additional deduplicated object, the additional fingerprint being generated using the algorithm that maps deduplicated objects onto the fingerprint space;
based on determining that the deduplicated object does not exist on the second node:
directing the subsequent request, based on the partitioning scheme, to a third node within the plurality of nodes that is responsible for forwarding requests pertaining to an additional partition of the fingerprint space that comprises the additional fingerprint;
forwarding the subsequent request from the third node to a fourth node identified by the third node as corresponding to the additional fingerprint.
6. The computer-implemented method of claim 1 , further comprising, in response to the request, identifying the deduplicated object on the second node.
7. The computer-implemented method of claim 1 , further comprising:
adding the deduplicated object to the collection of deduplicated data;
updating a fingerprint index on the second node with an association of the fingerprint with the deduplicated object;
updating an additional fingerprint index on the first node with an association of the fingerprint with the second node.
8. The computer-implemented method of claim 1 , further comprising:
identifying a new node added to the plurality of nodes;
updating the partitioning scheme to reassign at least one partition of the fingerprint space to the new node.
9. A system for performing lookups on distributed deduplicated data systems, the system comprising:
an identification module programmed to:
identify a collection of deduplicated data stored within a plurality of nodes;
identify a request to locate a deduplicated object of the collection within the plurality of nodes;
identify a fingerprint of the deduplicated object, the fingerprint being generated using an algorithm that maps deduplicated objects onto a fingerprint space, the fingerprint space comprising a set of possible fingerprint values generated using the algorithm;
a direction module programmed to direct the request, based on a partitioning scheme that divides the fingerprint space among the plurality of nodes, to a first node within the plurality of nodes that is responsible for forwarding requests pertaining to a partition of the fingerprint space that comprises the fingerprint;
a forwarding module programmed to:
forward the request from the first node to a second node identified by the first node as corresponding to the fingerprint, wherein the first node identifies the second node as corresponding to the fingerprint by using data stored by the first node that associates fingerprints that fall within the partition of the fingerprint space with nodes in which deduplicated data objects corresponding to the fingerprints that fall within the partition of the fingerprint space are expected to be found;
locate the deduplicated data object of the collection as being stored at the second node;
in response to locating the deduplicated data object at the second node, at least one of:
retrieve the deduplicated data object from the second node;
replace an instance of data with a reference to the deduplicated data object stored at the second node;
at least one processor configured to execute the identification module, the direction module, and the forwarding module.
10. The system of claim 9 , wherein the identification module is programmed to identify the collection of deduplicated data by identifying a collection of deduplicated data originating from a plurality of clients.
11. The system of claim 10 , wherein:
the identification module is programmed to identify the request by identifying a request from a client within the plurality of clients;
at least one home node within the plurality of nodes is designated for storing unique objects added to the collection of deduplicated data from the client.
12. The system of claim 9 , wherein:
the forwarding module is further programmed to, in response to the request, identify the deduplicated object on the second node;
the identification module is further programmed to identify a subsequent request to locate an additional deduplicated object of the collection within the plurality of nodes;
the forwarding module is further programmed to forward the subsequent request directly to the second node based on having identified the deduplicated object on the second node.
13. The system of claim 9 , wherein:
the forwarding module is further programmed to, in response to an additional request, determine that the deduplicated object does not exist on the second node;
the identification module is further programmed to:
identify a subsequent request to locate an additional deduplicated object of the collection within the plurality of nodes;
identify an additional fingerprint of the additional deduplicated object, the additional fingerprint being generated using the algorithm that maps deduplicated objects onto the fingerprint space;
the directing module is further programmed to, based on determining that the deduplicated object does not exist on the second node, direct the subsequent request, based on the partitioning scheme, to a third node within the plurality of nodes that is responsible for forwarding requests pertaining to an additional partition of the fingerprint space that comprises the additional fingerprint;
the forwarding module is further programmed to forward the subsequent request from the third node to a fourth node identified by the third node as corresponding to the additional fingerprint.
14. The system of claim 9 , wherein the forwarding module is further programmed to, in response to the request, identify the deduplicated object on the second node.
15. The system of claim 9 , further comprising an addition module programmed to:
add the deduplicated object to the collection of deduplicated data;
update a fingerprint index on the second node with an association of the fingerprint with the deduplicated object;
update an additional fingerprint index on the first node with an association of the fingerprint with the second node.
16. The system of claim 9 , further comprising a rebalancing module programmed to:
identify a new node added to the plurality of nodes;
update the partitioning scheme to reassign at least one partition of the fingerprint space to the new node.
17. A non-transitory computer-readable-storage medium comprising one or more computer-executable instructions that, when executed by at least one processor of a computing device, cause the computing device to:
identify a collection of deduplicated data stored within a plurality of nodes;
identify a request to locate a deduplicated object of the collection within the plurality of nodes;
identify a fingerprint of the deduplicated object, the fingerprint being generated using an algorithm that maps deduplicated objects onto a fingerprint space, the fingerprint space comprising a set of possible fingerprint values generated using the algorithm;
direct the request, based on a partitioning scheme that divides the fingerprint space among the plurality of nodes, to a first node within the plurality of nodes that is responsible for forwarding requests pertaining to a partition of the fingerprint space that comprises the fingerprint;
forward the request from the first node to a second node identified by the first node as corresponding to the fingerprint, wherein the first node identifies the second node as corresponding to the fingerprint by using data stored by the first node that associates fingerprints that fall within the partition of the fingerprint space with nodes in which deduplicated data objects corresponding to the fingerprints that fall within the partition of the fingerprint space are expected to be found;
locate the deduplicated data object of the collection as being stored at the second node;
in response to locating the deduplicated data object at the second node, at least one of:
retrieve the deduplicated data object from the second node;
replace an instance of data with a reference to the deduplicated data object stored at the second node.
18. The computer-readable-storage medium of claim 17 , wherein the one or more computer-executable instructions cause the computing device to identify the collection of deduplicated data by causing the computing device to identify a collection of deduplicated data originating from a plurality of clients.
19. The computer-readable-storage medium of claim 18 , wherein:
the one or more computer-executable instructions cause the computing device to identify the request by causing the computing device to identify a request from a client within the plurality of clients;
at least one home node within the plurality of nodes is designated for storing unique objects added to the collection of deduplicated data from the client.