Shifting compute node identifiers
AssigneeHewlett Packard Enterprise Development LP
InventorDylan Farrer
Life of this patent
Estimating the term…
Abstract
In some examples, a distributed system assigns key-value pairs to respective compute nodes of a plurality of compute nodes based on relationships of key identifiers of keys in the key-value pairs and node identifiers of the respective compute nodes on an identifier ring. A compute node determines whether a first gap on the identifier ring between node identifiers of first successive compute nodes is larger than a second gap on the identifier ring between node identifiers of second successive compute nodes. Based on determining that the first gap is larger than the second gap, the compute node initiates a shift operation that changes a node identifier of the compute node of the first successive compute nodes to reduce a size of the first gap on the identifier ring.
Claims20
A non-transitory machine-readable storage medium comprising instructions executable in a distributed system comprising a plurality of compute nodes to:
- assign key-value pairs to respective compute nodes of the plurality of compute nodes based on relationships of key identifiers of keys in the key-value pairs and node identifiers of the respective compute nodes on an identifier ring, wherein the node identifiers of the respective compute nodes are placed at corresponding positions on the identifier ring;
- determine whether a first gap on the identifier ring between node identifiers of first successive compute nodes is larger than a second gap on the identifier ring between node identifiers of second successive compute nodes;
- and
- based on determining that the first gap is larger than the second gap, initiate a shift operation that changes a node identifier of a first compute node of the first successive compute nodes to reduce a size of the first gap on the identifier ring.
A first compute node comprising:
- a hardware processor;
- and
- a non-transitory machine-readable storage medium storing instructions executable on the hardware processor to:
- store, at the first compute node, a collection of key-value pairs, wherein the first compute node is part of a distributed system in which keys of key-value pairs are assigned to respective compute nodes of a plurality of compute nodes based on relationships of key identifiers of the keys and node identifiers of the respective compute nodes on an identifier ring, wherein the node identifiers of the respective compute nodes are placed at corresponding positions on the identifier ring;
- determine whether a first gap on the identifier ring between a first node identifier of the first compute node and a second node identifier of a first neighbor compute node is different, by at least a difference threshold, from a second gap on the identifier ring between the first node identifier and a third node identifier of a second neighbor compute node;
- based on determining that the first gap is different from the second gap by at least the difference threshold, initiate a shift operation that changes the first node identifier to a different value to reduce a difference between the first gap and the second gap.
A method comprising:
- assigning key-value pairs to respective compute nodes of a plurality of compute nodes in a distributed system based on relationships of key identifiers of keys in the key-value pairs and node identifiers of the respective compute nodes on an identifier ring, wherein the node identifiers of the respective compute nodes are placed at corresponding positions on the identifier ring;
- obtaining, by a first compute node, a first distance on the identifier ring between a first node identifier of the first compute node and a second node identifier of a second compute node that is a first neighbor compute node of the first compute node;
- obtaining, by the first compute node, a second distance on the identifier ring between the first node identifier of the first compute node and a third node identifier of a third compute node that is a second neighbor compute node of the first compute node;
- determining, by the first compute node, whether the first distance differs from the second distance by at least a difference threshold;
- and
- based on determining that the first distance differs from the second distance by at least the difference threshold, initiating, by the first compute node, a shift operation that changes the first node identifier of the first compute node to reduce a difference between the first distance and the second distance.
Dependencies are inferred from the claim text.