Address generation and cluster extension in distributed systems using tree method

• US 8,806,016 B2
• Filed: 01/23/2012
• Issued: 08/12/2014
• Est. Priority Date: 12/24/2003
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Schreter, Ivan
• Primary Examiner(s): Patel, Dhairya A
• Application Number:
  US13/356,238
• Publication Number:
  US 20120124216A1
• Time in Patent Office: 932 Days
• Field of Search: 709/224, 709/225, 709/223
• 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 computer-implemented method, comprising:

establishing a cluster of leaf nodes and a cluster of back-end servers, the cluster of back-end servers organized into a data structure of at least one leaf node, each leaf node in the cluster of leaf nodes assigned a unique leaf node identifier, each element of the leaf node identifier identifying a branch of the data structure traversed to reach the leaf node, and each back-end server assigned to a particular leaf node and mirroring other back-end servers assigned to the same particular leaf node;

storing new data objects on each back-end server assigned to the particular leaf node, the particular leaf node providing for each new data object a universal identifier including;

(i) an object identifier that is unique on the particular leaf node; and

(ii) a server identifier including the leaf node identifier of the particular leaf node to which the assigned back-end servers storing the new data objects are assigned; and

splitting, by operation of a computer, the particular leaf node into at least two new leaf nodes to replace the particular leaf node, wherein splitting the particular leaf node includes reassigning the cluster of back-end servers, originally organized into the particular leaf node, to the at least two new leaf nodes such that each new leaf node is assigned at least two back-end servers of the cluster of back-end servers, and wherein a first back-end server of the back-end servers assigned to each new leaf node mirrors other back-end servers assigned to the same particular new leaf node but does not mirror the back-end servers reassigned to other new leaf nodes replacing the particular leaf node.

2. The computer-implemented method of claim 1, further comprising removing from each back-end server assigned to each new leaf node any data objects that have a server identifier that does not correspond to the leaf node identifier for the new leaf node to which the back-end server is reassigned.

3. The computer-implemented method of claim 1, further comprising using a load measured for each leaf node in the cluster of leaf nodes in selecting the particular leaf node as a leaf node to be split.

4. The computer-implemented method of claim 3, wherein the measured load comprises aggregate data capacity of back-end servers organized in each leaf node in the cluster.

5. The computer-implemented method of claim 1, further comprising, prior to splitting the particular leaf node, determining whether the particular leaf node has fewer than a defined minimum number of assigned back-end servers and, if it does, assigning additional back-end servers to the particular leaf node so that the particular leaf node has at least the defined minimum number of assigned back-end servers, and mirroring all currently stored data objects on non-additional back-end servers to the assigned additional back-end servers.

6. The computer-implemented method of claim 1, further comprising defining a set of ultimate identifiers for leaf nodes to be created in the cluster of leaf nodes, wherein each leaf node is an ultimate identifier.

7. The computer-implemented method of claim 6, wherein each leaf node identifier identifies a subset of the set of ultimate identifiers, each leaf node identifier a beginning part or an ending part of each ultimate identifier in the subset or an only ultimate identifier in the subset.

8. The computer-implemented method of claim 7, wherein:

the particular leaf node has a leaf node identifier that identifies a first subset of the set of ultimate identifiers;

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

a union of the new distinct subsets is the first subset.

9. A computer-accessible, non-transitory, storage medium encoded with computer-readable instructions configured to cause one or more data processing apparatus to:

establish a cluster of leaf nodes and a cluster of back-end servers, the cluster of back-end servers organized into a data structure of at least one leaf node, each leaf node in the cluster of leaf nodes assigned a unique leaf node identifier, each element of the leaf node identifier identifying a branch of the data structure traversed to reach the leaf node, and each back-end server assigned to a particular leaf node and mirroring other back-end servers assigned to the same particular leaf node;

store new data objects on each back-end server assigned to the particular leaf node, the particular leaf node providing for each new data object a universal identifier including;

(i) an object identifier that is unique on the particular leaf node; and

(ii) a server identifier including the leaf node identifier of the particular leaf node to which the assigned back-end servers storing the new data objects are assigned; and

split, by operation of a computer, the particular leaf node into at least two new leaf nodes to replace the particular leaf node, wherein splitting the particular leaf node includes reassigning the cluster of back-end servers, originally organized into the particular leaf node, to the at least two new leaf nodes such that each new leaf node is assigned at least two back-end servers of the cluster of back-end servers, and wherein a first back-end server of the back-end servers assigned to each new leaf node mirrors other back-end servers assigned to the same particular new leaf node but does not mirror the back-end servers reassigned to other new leaf nodes replacing the particular leaf node.

10. The medium of claim 9, further comprising removing from each back-end server assigned to each new leaf node any data objects that have a server identifier that does not correspond to the leaf node identifier for the new leaf node to which the back-end server is reassigned.

11. The medium of claim 9, further comprising using a load measured for each leaf node in the cluster of leaf nodes in selecting the particular leaf node as a leaf node to be split.

12. The medium of claim 11, wherein the measured load comprises aggregate data capacity of back-end servers organized in each leaf node in the cluster.

13. The medium of claim 9, further comprising, prior to splitting the particular leaf node, determining whether the particular leaf node has fewer than a defined minimum number of assigned back-end servers and, if it does, assigning additional back-end servers to the particular leaf node so that the particular leaf node has at least the defined minimum number of assigned back-end servers, and mirroring all currently stored data objects on non-additional back-end servers to the assigned additional back-end servers.

14. The medium of claim 9, further comprising defining a set of ultimate identifiers for leaf nodes to be created in the cluster of leaf nodes, wherein each leaf node is an ultimate identifier.

15. The medium of claim 14, wherein each leaf node identifier identifies a subset of the set of ultimate identifiers, each leaf node identifier a beginning part or an ending part of each ultimate identifier in the subset or an only ultimate identifier in the subset.

16. The medium of claim 15, wherein:

the particular leaf node has a leaf node identifier that identifies a first subset of the set of ultimate identifiers;

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

a union of the new distinct subsets is the first subset.

17. A system, comprising:

at least one computer configured to;

establish a cluster of leaf nodes and a cluster of back-end servers, the cluster of back-end servers organized into a data structure of at least one leaf node, each leaf node in the cluster of leaf nodes assigned a unique leaf node identifier, each element of the leaf node identifier identifying a branch of the data structure traversed to reach the leaf node, and each back-end server assigned to a particular leaf node and mirroring other back-end servers assigned to the same particular leaf node;

store new data objects on each back-end server assigned to the particular leaf node, the particular leaf node providing for each new data object a universal identifier including;

(i) an object identifier that is unique on the particular leaf node; and

(ii) a server identifier including the leaf node identifier of the particular leaf node to which the assigned back-end servers storing the new data objects are assigned; and

split, by operation of a computer, the particular leaf node into at least two new leaf nodes to replace the particular leaf node, wherein splitting the particular leaf node includes reassigning the cluster of back-end servers, originally organized into the particular leaf node, to the at least two new leaf nodes such that each new leaf node is assigned at least two back-end servers of the cluster of back-end servers, and wherein a first back-end server of the back-end servers assigned to each new leaf node mirrors other back-end servers assigned to the same particular new leaf node but does not mirror the back-end servers reassigned to other new leaf nodes replacing the particular leaf node.

18. The system of claim 17, further comprising removing from each back-end server assigned to each new leaf node any data objects that have a server identifier that does not correspond to the leaf node identifier for the new leaf node to which the back-end server is reassigned.

19. The system of claim 17, further comprising using a load measured for each leaf node in the cluster of leaf nodes in selecting the particular leaf node as a leaf node to be split.

20. The system of claim 19, wherein the measured load comprises aggregate data capacity of back-end servers organized in each leaf node in the cluster.

21. The system of claim 17, further comprising, prior to splitting the particular leaf node, determining whether the particular leaf node has fewer than a defined minimum number of assigned back-end servers and, if it does, assigning additional back-end servers to the particular leaf node so that the particular leaf node has at least the defined minimum number of assigned back-end servers, and mirroring all currently stored data objects on non-additional back-end servers to the assigned additional back-end servers.

22. The system of claim 17, further comprising defining a set of ultimate identifiers for leaf nodes to be created in the cluster of leaf nodes, wherein each leaf node is an ultimate identifier.

23. The system of claim 22, wherein each leaf node identifier identifies a subset of the set of ultimate identifiers, each leaf node identifier a beginning part or an ending part of each ultimate identifier in the subset or an only ultimate identifier in the subset.

24. The system of claim 23, wherein:

the particular leaf node has a leaf node identifier that identifies a first subset of the set of ultimate identifiers;

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

a union of the new distinct subsets is the first subset.