Address generation in distributed systems using tree method

• US 9,444,732 B2
• Filed: 07/29/2013
• Issued: 09/13/2016
• Est. Priority Date: 12/24/2003
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Schreter, Ivan
• Primary Examiner(s): Ibrahim, Mohamed
• Application Number:
  US13/953,557
• Publication Number:
  US 20130318254A1
• Time in Patent Office: 1,142 Days
• Field of Search: None
• US Class Current: 1/1
• 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. A computer-implemented method comprising:

generating an identifier for each of a plurality of data objects 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;

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 plurality of data objects are to be stored;

for each data object of the plurality of data objects, generating a universal identifier for the 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 data object in the first node, wherein, for each data object, one or more leading reserve bits of the reserve part for the data object have the same value;

based on a node split creating at least two new nodes from the first node, i) maintaining a locality of the plurality of data objects based on the one or more leading reserve bits having the same value, and ii) setting, for each data object of the plurality of data objects, one or more other bits of the reserve part to identify a particular node of the new nodes, on which the data object is stored following the split; and

load balancing the nodes by navigating the binary tree to select particular node based on relative loads on the other nodes of the cluster.

2. The method claim 1, wherein:

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

3. The method of claim 2, wherein:

the node identifier part is modified for load balancing.

4. The method of claim 1, 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.

5. A non-transitory computer-readable medium comprising instructions operable to cause data processing apparatus to:

generate an identifier for each of a plurality of data objects 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;

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 in which the plurality of data objects are to be stored;

for each data object of the plurality of data objects, generate a universal identifier for 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 data object in the first node, wherein, for each data object, one or more leading reserve bits of the reserve part for the data object have the same value;

based on a node split creating at least two new nodes from the first node, i) maintain a locality of the plurality of data objects based on the one or more leading reserve bits having the same value, and ii) set, for each data object of the plurality of data objects, one or more other bits of the reserve part to identify a particular node of the nodes, on which the new data object is stored following the split; and

load balancing the nodes by navigating the binary tree to select particular node based on relative loads on the other nodes of the cluster.

6. The product of claim 5, 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.

7. The product of claim 6, wherein:

the node identifier part is modified for load balancing.

8. The product claim 5, wherein:

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

9. A system comprising:

data processing apparatus; and

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

generating an identifier for each of a plurality of data objects 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;

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 plurality of data objects are 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;

for each data object of the plurality of data objects, generating a universal identifier for 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 data object in the first node, wherein, for each data object, one or more leading reserve bits of the reserve part for the data object have the same value;

based on a node split creating at least two new nodes from the first node, i) maintaining a locality of the plurality of data objects based on the one or more leading reserve bits having the same value, and ii) setting, for each data object of the plurality of data objects, one or more other bites of the reserve part to identify a particular node of the new nodes, on which the data object is stored following the split; and

load balancing the nodes by navigating the binary tree to select particular node based on relative loads on the other nodes of the cluster.

10. The system of claim 9, 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.

11. The system of claim 10, the operations further comprising:

modifying the node identifier for load balancing.

12. The system of claim 9, wherein:

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