Network routing of data based on content thereof

• US 7,689,764 B1
• Filed: 04/13/2006
• Issued: 03/30/2010
• Est. Priority Date: 04/13/2006
• Status: Active Grant

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Symantec Operating Corporation (NortonLifeLock Inc.)
• Inventors: De Spiegeleer, Kristof, D'Hondt, Koen
• Primary Examiner(s): BATAILLE, PIERRE MICHE
• Application Number:
  US11/404,105
• Time in Patent Office: 1,447 Days
• Field of Search: 711/144, 711/108, 711/162, 711/154, 345/745
• US Class Current: 711/108
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence

Abstract

A system may be provided which is operable to determine a routing node for a data object. The system can comprise an identifier generator operable to generate an identifier for the data object on the basis of data content thereof, and a lookup engine operable to compare the identifier for the data object to a routing table to determine a routing node for the data element.

Claims

1. A distributed storage system comprising:

a storage agent operable to perform a look-up in a routing table to determine a routing node for a data object on the basis of an identifier therefore, the identifier for the data object being based on data content thereof, and to send a message including the identifier relating to that data object to the identified routing node; and

a plurality of routing nodes, each operable to perform a look-up in a routing table to determine a further routing node for a data object described in an identifier included in a message received at the routing node, and to forward the message to the identified further routing node;

wherein at least a subset of the routing nodes are each operable to store data objects having an identifier within a predetermined range, and wherein the routing table for each such node indicates that the further routing node is the current node for identifiers within said predetermined range.

2. The system of claim 1, wherein the routing table at the agent and the routing tables at the routing nodes are different.

3. The system of claim 1, wherein the data object is a data file or a data file segment.

4. The system of claim 1, wherein the identifier is a checksum value for the data object.

5. The system of claim 1, wherein the routing table at the storage agent contains an indication of a routing node for every possible identifier value.

6. The system of claim 1, wherein the routing table at each routing node contains an indication of a routing node for every identifier value which can be caused to arrive at that routing node.

7. The system of claim 1, wherein the storage agent is operable to use two routing tables to determine a routing node, and wherein at least each routing node which is directly addressable by the storage agent is operable to use two routing tables to determine a further routing node.

8. The system of claim 7, wherein a first routing table indicates a new routing node for the identifier and wherein a second routing table indicates an old routing node for the identifier.

9. The system of claim 8, wherein one of the two routing tables includes at least one routing node which is a member of the subset of routing nodes and does not currently have a copy of all data described in that routing table.

10. The system of claim 1, wherein at least one routing node of the at least a subset of routing nodes is operable to store a data object in a storage element of the routing node.

11. The system of claim 1, wherein at least one routing node of the at least a subset of routing nodes is operable to store a data object in a storage element directly or indirectly attached to the routing node.

12. The system of claim 1, wherein the message is a query to determine whether any of the routing nodes has a responsibility for a stored copy of the data object.

13. The system of claim 1, wherein the message is a request to store the data object.

14. The system of claim 1, wherein only a single copy of the data object is to be stored within the system.

15. The system of claim 1, wherein the message is a request to retrieve a copy of the data object.

16. A distributed storage system comprising:

means for performing a look-up in a routing table to determine a routing node for a data object on the basis of an identifier therefore, the identifier for the data object being based on data content thereof, and for sending a message including the identifier relating to that data object to the identified routing node; and

a plurality of routing means, each for performing a look-up in a routing table to determine a further routing means for a data object described in an identifier included in a message received at the routing means, and for forwarding the message to the identified further routing means;

wherein at least a subset of the routing means are further for storing data objects having an identifier within a predetermined range, and wherein the routing table for each such routing means indicates that the further routing means is the current routing means for identifiers within said predetermined range.