POLICY-BASED STORAGE STRUCTURE DISTRIBUTION

• US 20110066591A1
• Filed: 04/16/2010
• Published: 03/17/2011
• Est. Priority Date: 04/16/2009
• Status: Active Grant

• Current Assignee: Cloud Software Group
• Original Assignee: TIBCO Software Incorporated (Cloud Software Group)
• Inventors: Moyne, Jean-Noel, Subramani, Suresh, Kim, Tom M.
• Granted Patent: US 9,235,623 B2
• Time in Patent Office: Days
• US Class Current: 707/610
• CPC Class Codes: G06F 16/178 Techniques for file synchronisation in file systems
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/24554 Unary operations; Data partitioning operations
• CPC Class Codes: G06F 16/275 Synchronous replication

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.

Claims

1. A data store located on a system of one or more computing devices, the data store comprising executable code executing the following steps:

receiving a plurality of data entries, the plurality of data entries comprising;

a first data entry having one or more fields, wherein at least one field is a key field, and wherein the first data entry has a first key value in the key field;

a second data entry having one or more fields, wherein at least one field is the key field, and wherein the second data entry has the first key value in the key field; and

storing the plurality of data entries in a space within the data store.

2. The data store of claim 1, wherein the space comprises:

one of a database and a table; and

a policy-based storage structure.

3. The data store of claim 1, wherein the first data entry and the second data entry collectively comprise a policy-based storage structure.

4. The data store of claim 3, wherein the policy-based storage structure is a microqueue.

5. The data store of claim 3, wherein the policy-based storage structure is operable to implement queue semantics.

6. The data store of claim 5, wherein the queue semantics comprise at least one of:

sorting, ordering, first-in-first out, and last-in-first-out queue semantics.

7. The data store of claim 1, wherein the space comprises at least one policy-based storage structure, wherein the at least one policy-based storage structure comprises:

the first data entry;

the second data entry; and

any related data entries in the plurality of data entries, wherein the related data entries have one or more fields, wherein at least one field is the key field, and wherein the any related data entries have the first key value in the key field.

8. The data store of claim 7, wherein the data store further comprises a second policy-based storage structure, the second policy-based storage structure comprising:

a third data entry of the plurality of data entries, wherein the third data entry has one or more fields, wherein at least one field is the key field, and wherein the third data entry has a second key value in the key field; and

a fourth data entry of the plurality of data entries, wherein the fourth data entry has one or more fields, wherein at least one field is the key field, and wherein the fourth data entry has a second key value in the key field.

9. The data store of claim 7, wherein the policy-based storage structure is a microqueue.

10. The data store of claim 7, wherein the policy based storage structure comprises one of a queue, linked list, array, stack, tree, and graph.

11. The data store of claim 1, wherein the plurality of data entries are accessible by specifying the key value.

12. The data store of claim 1, wherein data entries, of the plurality of data entries, having a particular key value comprise a microqueue, and wherein the microqueue is accessible by specifying the particular key value.

13. The data store of claim 1, wherein the plurality of data entries comprises operation or transaction data.

14. A method for distributing policy-based data structures over a system of one or more servers installed on one or more computing devices, the method comprising:

determining at least one policy-based data structure from a space, the determining comprising;

identifying at least one data entry in the space;

determining a key value of the at least one data entry;

mapping the at least one policy-based data structure to one of a node, node cluster, server, and server cluster in the system of one or more servers, the mapping comprising using a distribution algorithm considering the key value.

15. The method of claim 14, wherein the mapping the at least one policy-based data structure comprises distributing at least one microqueue over the system of one or more servers.

16. The method of claim 14, wherein the mapping comprises using a consistent hashing algorithm.

17. The method of claim 14, wherein the mapping comprises:

using a consistent hashing algorithm to map nodes in the system of one or more servers to a scale;

using the consistent hashing algorithm to map the at least one policy-based data structure to the scale;

assigning the at least one policy-based data structure to a closest node, the closest node being the node mapped closest to the policy-based data structure on the scale.

18. The method of claim 17, wherein the using a consistent hashing algorithm to map nodes in the system of one or more servers to a scale results in a substantially even distribution of nodes.

19. The method of claim 17, wherein the using a consistent hashing algorithm to map nodes in the system of one or more servers to a scale results in a substantially uneven distribution of nodes.

20. The method of claim 14, wherein the determining at least one policy-based data structure in the space comprises determining a plurality of policy-based data structures by grouping data entries in the space based on each data entry'"'"'s key value, and wherein the mapping the plurality of policy-based data structures comprises:

using a consistent hashing algorithm to map nodes in the system of one or more servers to a scale;

using the consistent hashing algorithm to map the plurality of policy-based data structures to the scale, wherein each of the plurality of policy-based data structures comprises a grouping of data entries having a same key value, and wherein the mapping the plurality of policy-based data structures to the scale comprises mapping the key values of each of the plurality of policy-based data structures to the scale; and

assigning the plurality of policy-based data structures to the mapped nodes by assigning each of the policy-based data structures to a node mapped closest to it on the scale.

21. The method of claim 14, wherein the mapping the at least one policy-based data structure results in a substantially even distribution of policy-based data structures over a set of nodes or servers.

22. A method of adding a node to a collection of computing nodes, the method comprising:

joining a new node to the collection of computing nodes as a leech node;

receiving, at the leech node, information from other active nodes in the collection of computing nodes; and

thereafter, promoting the leech node to an active node in the collection of computing nodes.

23. The method of claim 22, 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.

24. The method of claim 22, wherein the joining the new node as a leech node comprises the leech node obtaining a key space of the other active nodes in the collection of computing nodes.

25. The method of claim 22, wherein the receiving information comprises receiving copies of key values associated with key values the new node will own once it becomes an active node.

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

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

28. The method of claim 22, 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.

29. A method of removing a leaving node from a collection of computing nodes, the method comprising:

the leaving node signaling to other nodes in the collection of computing nodes that it is leaving the collection;

the other nodes reading information from the leaving node; and

the leaving node leaving the collection of computing nodes and the other nodes taking ownership of data associated with key values previously owned by the leaving node.

30. The method of claim 29, wherein the other nodes receiving information comprises the other nodes receiving copies of the data associated with the key values previously owned by the leaving node.

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

32. The method of claim 29, 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 new node.

33. A method for replicating data over a collection of computing nodes, 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 replication of the policy-based storage structure; and

replicating the policy-based storage structure stored on the primary node and storing the replicated policy-based storage structure on the secondary node.

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

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

36. The method of claim 35, 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.