ADDRESS GENERATION IN DISTRIBUTED SYSTEMS USING TREE METHOD

• US 20130318254A1
• Filed: 07/29/2013
• Published: 11/28/2013
• 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 9,444,732 B2
• Time in Patent Office: Days
• US Class Current: 709/238
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/289 Object oriented databases
• CPC Class Codes: H04L 2101/604 Address structures or formats
• CPC Class Codes: H04L 45/48 Routing tree calculation
• 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. (canceled)

2. A computer-implemented method for generating an identifier for a new data object to be stored in a cluster of back-end servers of the kind where the cluster is organized into a plurality of nodes where each of the plurality of nodes in the cluster has a node identifier that is unique in the cluster, and where every back-end server in any of the plurality of nodes mirrors every other back-end server in the same node, the method comprising:

selecting a path of a binary tree structure based on a capacity of nodes along the path, the tree structure comprising the plurality of nodes organized in the structure;

identifying a first node at an end of the path in which the new data object is to be stored;

generating a universal identifier for the new data object, the universal identifier having a node identifier part that uniquely identifies the first node in the cluster, a reserve part that is generated, at least in part, as a pseudo-random value, and an object identifier part that uniquely identifies the object in the first node; and

based on a node split creating at least two new nodes from the first node, setting one or more bits of the reserve part to identify a particular node of the new nodes, on which the new data object is stored following the split.

3. The method of claim 2, wherein:

the node identifier part and the reserve part have a combined length that is a predetermined fixed length; and

the object identifier part does not uniquely identify the new data object on the cluster.

4. The method claim 2, wherein:

the reserve part is generated by the first node and given a value to maintain some locality between the new data object and certain other data objects stored on the first node.

5. The method claim 2, wherein:

the node identifier part and the reserve part are both generated as pseudo-random values.

6. The method of claim 5, wherein:

the node identifier part is modified for load balancing.

7. The method of claim 6, wherein:

the node identifiers have a structure represented as the binary tree in a front-end server, and

load balancing comprises navigating the binary tree to select a node based on the relative loads on the nodes of the cluster.

8. A non-transitory computer-readable medium for generating an identifier for a new data object to be stored in a cluster of back-end servers of the kind where the cluster is organized into a plurality of nodes where each of the plurality of nodes in the cluster has a node identifier that is unique in the cluster, and where every back-end server in any of the plurality of nodes mirrors every other back-end server in the same node, the medium comprising instructions operable to cause data processing apparatus to:

select a path of a binary tree structure based on a capacity of nodes along the path, the tree structure comprising the plurality of nodes organized in the structure;

determine a first node at an end of the path;

generate a universal identifier for the new data object, the universal identifier having a node identifier part that uniquely identifies the first node in the cluster, a reserve part that is generated, at least in part, as a pseudo-random value, and an object identifier part that uniquely identifies the object in the first node; and

based on a node split creating at least two new nodes from the first node, set one or more bits of the reserve part to identify a particular node of the new nodes, on which the new data object is stored following the split.

9. The product of claim 8, wherein:

the node identifier part and the reserve part have a combined length that is a predetermined fixed length; and

the object identifier part does not uniquely identify the new data object on the cluster.

10. The product claim 8, wherein:

the reserve part is generated by the first node and given a value to maintain some locality between the new data object and certain other data objects stored on the first node.

11. The product claim 8, wherein:

the node identifier part and the reserve part are both generated as pseudo-random values.

12. The product of claim 9, wherein:

the node identifier part is modified for load balancing.

13. The product of claim 10, wherein:

the node identifiers have a structure represented as the binary tree in a front-end server, and

load balancing comprises navigating the binary tree to select a node based on the relative loads on the nodes of the cluster.

14. A system for generating an identifier for a new data object to be stored in a cluster of back-end servers of the kind where the cluster is organized into a plurality of nodes where each of the plurality of nodes in the cluster has a node identifier that is unique in the cluster, and where every back-end server in any of the plurality of nodes mirrors every other back-end server in the same node, the system comprising:

data processing apparatus; and

a computer-readable medium storing instructions executable by the data processing apparatus to perform operations comprising;

selecting a path of a binary tree structure based on a capacity of nodes along the path, the tree structure comprising the plurality of nodes organized in the structure;

determining a first node at an end of the path in which the new data object is to be stored;

generating a node identifier for the new data object that uniquely identifies the first node in the cluster for storing the new data object;

generating a universal identifier for the new data object, the universal identifier having a node identifier part for the node identifier, a reserve part that is generated, at least in part, as a pseudo-random value, and an object identifier part that uniquely identifies the object in the first node; and

setting one or more bits of the reserve part, based on a node split creating at least two new nodes from the first node, to identify a particular node of the new nodes, on which the new data object is stored following the split.

15. The system of claim 14, wherein:

the node identifier part and the reserve part have a combined length that is a predetermined fixed length; and

the object identifier part does not uniquely identify the new data object on the cluster.

16. The system of claim 14, wherein:

the reserve part is generated by the first node and given a value to maintain some locality between the new data object and certain other data objects stored on the first node.

17. The system of claim 14, wherein:

the node identifier part and the reserve part are both generated as pseudo-random values.

18. The system of claim 15, the operations further comprising:

modifying the node identifier for load balancing.

19. The system of claim 18, wherein:

the node identifiers have a structure represented as the binary tree in a front-end server, and

modifying the node identifier for load balancing comprises navigating the binary tree to select a node based on the relative loads on the nodes of the cluster.