×

Cluster extension in distributed systems using tree method

  • US 8,103,772 B2
  • Filed: 12/24/2003
  • Issued: 01/24/2012
  • Est. Priority Date: 12/24/2003
  • Status: Active Grant
First Claim
Patent Images

1. A computer-implemented method for managing data storage servers, the method steps performed by one or more processors and comprising:

  • establishing, by the one or more processors, a cluster of back-end servers organized into at least one leaf node, every back-end server in any leaf node mirroring every other back-end server in the same leaf-node;

    establishing, by the one or more processors, a predefined set of ultimate identifiers for nodes that could be created in the cluster, each leaf node in the cluster having a node identifier that is unique in the cluster and one of the predefined set of ultimate identifiers;

    storing every new data object on the cluster on particular back-end servers assigned to a particular leaf node of the at least one leaf node, the particular leaf node having a particular node identifier that identifies a subset of the set of ultimate identifiers, and providing for each new data object a universal identifier that combines(i) an object identifier that is unique on the particular leaf node; and

    (ii) a server identifier, where the server identifier includes(a) a leaf node ID part having a value corresponding to the particular identifier of the particular leaf node to which the particular back-end server is assigned, and(b) an unused part having an at least partially arbitrary value, andWhere the node identifiers for nodes existing in the cluster at any one time identify non-overlapping subsets of the set of ultimate identifiers;

    splitting, by the one or more processors, a first leaf node of the at least one leaf node into at least two new leaf nodes that replace the first leaf node; and

    assigning, by the one or more processors, to each new leaf node, at least one of the back-end servers of the first leaf node such that replacing the first leaf node reassigns the back-end servers, originally organized in the first leaf node, to the new leaf nodes, where assigning back-end servers to one of the new leaf nodes includes;

    appending a portion of the unused part of the server identifier, of each of the back-end servers of the first leaf node, to the leaf node ID part of the server identifier to create an updated leaf node ID part, wherein each updated leaf node ID part corresponds to a node identifier of one of the new leaf nodes; and

    assigning each back-end server of the first leaf node to the new leaf node having a node identifier corresponding to the updated leaf node ID part of the back-end server.

View all claims
  • 2 Assignments
Timeline View
Assignment View
    ×
    ×