Cluster extension in distributed systems using tree method

• US 20050160170A1
• Filed: 12/24/2003
• Published: 07/21/2005
• Est. Priority Date: 12/24/2003
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Schreter, Ivan
• Granted Patent: US 8,103,772 B2
• Time in Patent Office: Days
• US Class Current: 709/226
• CPC Class Codes: H04L 2101/604 Address structures or formats
• CPC Class Codes: H04L 61/5069 for group communication, multicast communication or broadcast communication
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes

Abstract

Methods and apparatus, including computer program products, for managing a cluster of servers organized into nodes. A method of one aspect includes establishing a cluster; establishing a set of ultimate identifiers for nodes resulting from splitting in the cluster; and storing every new data object on a node that has a node identifier that identifies a subset of the set of ultimate identifiers, and providing for the object a universal identifier that combines (i) an object identifier that is unique on the node and (ii) a server identifier that is one of the ultimate identifiers in the subset. A method of another aspect includes generating for a new data object a universal identifier that has a node identifier part that uniquely identifies a node, a reserve part generated at least in part as a pseudo-random value, and an object identifier part that uniquely identifies the object in the node.

Claims

1. A method for managing data storage servers, comprising:

establishing a cluster of back-end servers organized into nodes, every node in the cluster having a node identifier that is unique in the cluster, every back-end server in any node mirroring every other back-end server in the same node;

establishing a predefined set of ultimate identifiers for nodes that could be created in the cluster; and

storing every new data object on the cluster on a particular node, the particular node having a particular node identifier that identifies a subset of the set of ultimate identifiers, and providing for the object a universal identifier that combines (i) an object identifier that is unique on the particular node and (ii) a server identifier, where the server identifier is one of the ultimate identifiers in the subset, and where the node identifiers for nodes existing in the cluster at any one time identify non-overlapping subsets of the set of ultimate identifiers.

2. The method of claim 1, wherein:

the set of ultimate identifiers is a set of binary numbers of a fixed length; and

each node in the cluster has a node identifier that is a binary number of the fixed length or of a length less than the fixed length.

3. The method of claim 2, wherein:

the set of ultimate identifiers is the set of 32-bit binary numbers; and

the object identifier is a 32-bit binary number.

4. The method of claim 1, wherein:

each node identifier identifies a subset of the set of ultimate identifiers by being a beginning part or an ending part of each identifier in the subset or by being the only identifier in the subset.

5. The method of claim 1, wherein:

the particular node identifier is not an ultimate identifier; and

the server identifier comprises a part generated as a pseudo-random value.

6. The method of claim 5, wherein:

the pseudo-random value is generated by a back-end server.

7. The method of claim 5, wherein:

the pseudo-random value is generated by a front-end server.

8. The method of claim 1, further comprising:

splitting a first node into new nodes, where

the first node had a first node identifier that identified a first subset of the set of ultimate identifiers,

the new nodes each have a distinct node identifier that identifies a new distinct subset of the first subset, and

the union of the new distinct subsets is the first subset;

assigning to each new node at least one of the back-end servers of the first node; and

removing from each back-end server of each new node any data objects that have a server identifier that does not correspond to the node identifier for the new node to which the back-end server is assigned.

9. The method of claim 8, wherein:

the set of ultimate identifiers is a set of binary numbers of a fixed length;

the first node has a first node identifier that is a binary number of a length less than the fixed length; and

the node identifier of each new node includes within it the binary number of the first node identifier.

10. The method of claim 8, further comprising:

using a load measured for each node in the cluster in selecting the first node as a node to be split.

11. The method of claim 8, further comprising:

determining whether the first node has fewer than four back-end servers and, if it does, adding back-end servers to the first node so that the first node has at least four back-end servers, and populating the added back-end servers with all of the data objects stored on the first node, before splitting the first node.

12. A computer program product, tangibly embodied on an information carrier, for managing data storage servers, the product being operable to cause data processing apparatus to perform operations comprising:

establishing a cluster of back-end servers organized into nodes, every node in the cluster having a node identifier that is unique in the cluster, every back-end server in any node mirroring every other back-end server in the same node;

establishing a predefined set of ultimate identifiers for nodes that could be created in the cluster; and

storing every new data object on the cluster on a particular node, the particular node having a particular node identifier that identifies a subset of the set of ultimate identifiers, and providing for the object a universal identifier that combines (i) an object identifier that is unique on the particular node and (ii) a server identifier, where the server identifier is one of the ultimate identifiers in the subset, and where the node identifiers for nodes existing in the cluster at any one time identify non-overlapping subsets of the set of ultimate identifiers.

13. The product of claim 12, wherein:

the set of ultimate identifiers is a set of binary numbers of a fixed length; and

each node in the cluster has a node identifier that is a binary number of the fixed length or of a length less than the fixed length.

14. The product of claim 13, wherein:

the set of ultimate identifiers is the set of 32-bit binary numbers; and

the object identifier is a 32-bit binary number.

15. The product of claim 12, wherein:

each node identifier identifies a subset of the set of ultimate identifiers by being a beginning part or an ending part of each identifier in the subset or by being the only identifier in the subset.

16. The product of claim 12, wherein:

the particular node identifier is not an ultimate identifier; and

the server identifier comprises a part generated as a pseudo-random value.

17. The product of claim 16, wherein:

the pseudo-random value is generated by a back-end server.

18. The product of claim 16, wherein:

the pseudo-random value is generated by a front-end server.

19. The product of claim 12, further operable to cause data processing apparatus to perform operations comprising:

splitting a first node into new nodes, where

the first node had a first node identifier that identified a first subset of the set of ultimate identifiers,

the new nodes each have a distinct node identifier that identifies a new distinct subset of the first subset, and

the union of the new distinct subsets is the first subset;

assigning to each new node at least one of the back-end servers of the first node; and

removing from each back-end server of each new node any data objects that have a server identifier that does not correspond to the node identifier for the new node to which the back-end server is assigned.

20. The product of claim 19, wherein:

the set of ultimate identifiers is a set of binary numbers of a fixed length;

the first node has a first node identifier that is a binary number of a length less than the fixed length; and

the node identifier of each new node includes within it the binary number of the first node identifier.

21. The product of claim 19, further operable to cause data processing apparatus to perform operations comprising:

using a load measured for each node in the cluster in selecting the first node as a node to be split.

22. The product of claim 19, further operable to cause data processing apparatus to perform operations comprising:

determining whether the first node has fewer than four back-end servers and, if it does, adding back-end servers to the first node so that the first node has at least four back-end servers, and populating the added back-end servers with all of the data objects stored on the first node, before splitting the first node.

23. A system for managing data storage, comprising:

means for establishing a cluster of back-end servers organized into nodes, every node in the cluster having a node identifier that is unique in the cluster, every back-end server in any node mirroring every other back-end server in the same node;

means for establishing a predefined set of ultimate identifiers for nodes that could be created in the cluster; and

means for storing every new data object on the cluster on a particular node, the particular node having a particular node identifier that identifies a subset of the set of ultimate identifiers, and providing for the object a universal identifier that combines (i) an object identifier that is unique on the particular node and (ii) a server identifier, where the server identifier is one of the ultimate identifiers in the subset, and where the node identifiers for nodes existing in the cluster at any one time identify non-overlapping subsets of the set of ultimate identifiers.

24. The system of claim 23, wherein:

the set of ultimate identifiers is a set of binary numbers of a fixed length; and

each node in the cluster has a node identifier that is a binary number of the fixed length or of a length less than the fixed length.

25. The system of claim 24, wherein:

the set of ultimate identifiers is the set of 32-bit binary numbers; and

the object identifier is a 32-bit binary number.

26. The system of claim 23, wherein:

each node identifier identifies a subset of the set of ultimate identifiers by being a beginning part or an ending part of each identifier in the subset or by being the only identifier in the subset.

27. The system of claim 23, wherein:

the particular node identifier is not an ultimate identifier; and

the server identifier comprises a part generated as a pseudo-random value.

28. The system of claim 27, wherein:

the pseudo-random value is generated by a back-end server.

29. The system of claim 27, wherein:

the pseudo-random value is generated by a front-end server.

30. The system of claim 23, further comprising:

means for splitting a first node into new nodes, where

the first node had a first node identifier that identified a first subset of the set of ultimate identifiers,

the new nodes each have a distinct node identifier that identifies a new distinct subset of the first subset, and

the union of the new distinct subsets is the first subset;

means for assigning to each new node at least one of the back-end servers of the first node; and

means for removing from each back-end server of each new node any data objects that have a server identifier that does not correspond to the node identifier for the new node to which the back-end server is assigned.

31. The system of claim 30, wherein:

the set of ultimate identifiers is a set of binary numbers of a fixed length;

the first node has a first node identifier that is a binary number of a length less than the fixed length; and

the node identifier of each new node includes within it the binary number of the first node identifier.

32. The system of claim 30, further comprising:

means for using a load measured for each node in the cluster in selecting the first node as a node to be split.

33. The system of claim 30, further comprising:

means for determining whether the first node has fewer than four back-end servers and, if it does, adding back-end servers to the first node so that the first node has at least four back-end servers, and populating the added back-end servers with all of the data objects stored on the first node, before splitting the first node.

34-51. -51. (canceled)