Policy-based storage structure distribution

Patent metadata

Field	Value
Publication number	US-9367600-B2
Application number	US-201514952884-A
Country	US
Kind code	B2
Filing date	Nov 25, 2015
Priority date	Apr 16, 2009
Publication date	Jun 14, 2016
Grant date	Jun 14, 2016

Abstract

Policy-based storage and retrieval combined with a distribution algorithm results in automatic and even distribution of policy-based storage structures across a set of nodes and dynamic, automated homing or ownership of policy-based storage structures. Large numbers of policy-based storage structures may be distributed without manual administration, allowing for rapid creation and destruction of storage structures. The overall load may be distributed and balanced across the server pool. Multiple entries having the same key value in a database- or table-like structure allow for distribution of policy-based storage and retrieval by key value and for queue semantics to be utilized for microqueues in the large database- or table-like structure.

First claim

What is claimed is:

1. A method of removing a leaving node from a collection of computing nodes of a distributed storage system, the method comprising:
the leaving node signaling to all other nodes in the collection of computing nodes that it is leaving the collection;
all the other nodes reading information from the leaving node;
all the other nodes synchronizing the information from the leaving node prior to the leaving node leaving the collection;
the leaving node leaving the collection of computing nodes, and
all the other nodes taking ownership of data associated with key values previously owned by the leaving node once the leaving node leaves the collection,
wherein all the other nodes reading information comprises all the other nodes receiving copies of the data associated with the key values owned by the leaving node, the date associated with the key values being the data whose ownership will be transferred from the leaving node to the other nodes once the leaving node leaves the collection.

2. The method of claim 1 , further comprising replicating key values previously replicated on the leaving node.

3. The method of claim 1 , wherein reading information from the leaving node further comprises calculating, using a consistent hashing algorithm, a distribution of key values over the collection of computing nodes excluding the leaving node.

4. A method for replicating data over a collection of computing nodes of a distributed storage system, the method comprising:
calculating a primary node for storing a policy-based storage structure associated with a key value;
calculating a secondary node for storing a copy of the policy-based storage structure associated with the key value; and
replicating the policy-based storage structure stored on the primary node and storing the copy of the policy-based storage structure on the secondary node,
wherein ownership of the policy-based storage structure is transferred from the primary node to the secondary node once the primary node leaves the collection.

5. The method of claim 4 , wherein the calculating the primary node and the calculating the secondary node comprises using a distribution algorithm having monotone behavior.

6. The method of claim 4 , wherein the calculating the primary node and the calculating the secondary node comprises using a consistent hashing algorithm.

7. The method of claim 6 , wherein the primary node comprises the node closest to a mapped key value associated with the policy-based storage structure on a consistent hashing scale, and wherein the secondary node comprises the next closest node to the mapped key value associated with the policy-based storage structure on the consistent hashing scale.

8. A method of adding a node to a collection of computing nodes of a distributed storage system, the method comprising:
joining a new node to the collection of computing nodes as a leech node;
receiving, at the leech node, information from all other active nodes in the collection of computing nodes;
synchronizing the leech node based on the received information; and
thereafter, promoting the leech node to an active node in the collection of computing nodes;
wherein the joining the new node as a leech node comprises the leech node obtaining a key space from all of the other active nodes in the collection of computing nodes;
wherein prior to promoting the leech node to an active node, the leech node is not an active node, and
wherein the receiving information comprises receiving copies of key values from all other active nodes, the key values being key values whose ownership will be transferred from the other active nodes to the leech node once the leech node once it becomes an active node.

9. The method of claim 8 , wherein the joining the new node as a leech node comprises the leech node interacting with the other active nodes in the collection of computing nodes.

10. The method of claim 8 , wherein the receiving information comprises reconciling data between the leech node and the other active nodes in the collection of computing nodes.

11. The method of claim 8 , wherein the receiving information comprises the leech node monitoring updated key values.

12. The method of claim 8 , wherein receiving information further comprises calculating, using a consistent hashing algorithm, a distribution of key values over the collection of computing nodes including the new node.

Assignees

• Tibco Software Inc

Inventors

• Moyne Jean-Noel
• Subramani Suresh
• Kim Tom M

Classifications

• G06F17/30174

  Physics · mapped topic

• G06F17/30581 Primary

  Physics · mapped topic

• G06F17/30486

  Physics · mapped topic

• G06F17/30336

  Physics · mapped topic

• G06F16/24554 Primary

  Unary operations; Data partitioning operations · CPC title