Polytree queue for synchronizing data with a shared resource
A system, method and program product for synchronizing client-based data with data in a shared resource. A system is provided that receives data from a plurality of client devices, the data being indicative of at least one action associated with a shared resource accessible by the plurality of client devices, and inserts a plurality of actions indicated by the data as nodes into a polytree queue, wherein actions that do not depend on other actions in the polytree queue are inserted as root level nodes, and actions that depend on other actions in the polytree queue are inserted as child nodes. The system further executes the nodes in the polytree queue to synchronize the data from the plurality of client devices with the shared resource, wherein root level nodes are scheduled for immediate concurrent execution, and execution of child nodes is delayed until parent nodes of an associated child node are executed.
1. A system comprising:
a memory; and
a processor coupled to the memory, and the processor configured to:
receive data from a plurality of client devices, the data being indicative of actions associated with a shared resource accessible by the plurality of client devices,
insert a plurality of actions as nodes into a polytree queue defined by a tree structure in which root level nodes form branches of the tree structure and are located on a same level in the tree structure as parent nodes, and wherein at least one child node depends from multiple parent nodes, wherein actions that do not depend on other actions in the polytree queue are inserted as root level nodes, and actions that depend on other actions in the polytree queue are inserted as child nodes, and
execute the nodes in the polytree queue to synchronize the data from the plurality of client devices with the shared resource, wherein root level nodes are scheduled for immediate concurrent execution with each other, and execution of child nodes is delayed until parent nodes of an associated child node are executed,
wherein the at least one child node that depends from multiple parent nodes is promoted to a root level node only after execution of all of the multiple parent nodes, and
wherein the polytree queue includes a first root level node that is prioritized over a second root level node based on a first-in first-out scheme, wherein the first root level node has a plurality of child level nodes dependent therefrom, and wherein after execution of the first root level node, the plurality of child nodes are promoted to root level nodes for execution after the second root level node.
2. The system of claim 1 , wherein after execution of the first root level node, the first root level node is removed from the polytree queue, and wherein the multiple parent nodes of the at least one child node are located on a same level in the tree structure as a distinct parent node with a distinct child node.
3. The system of claim 1 , wherein in response to an execution failure of a node, the processor is further configured to:
remove the node from the polytree queue as a failing node;
determine whether at least one dependent node of the failing node is typed as a hard dependency or a soft dependency;
remove dependent nodes from the polytree queue typed as hard dependencies; and
maintain dependent nodes typed as soft dependencies in the polytree queue.
4. The system of claim 3 , wherein the soft dependency indicates that there is no ordering requirement between the dependent node and associated parent node and the dependent node and associated parent node cannot execute simultaneously.
5. The system of claim 3 , wherein the hard dependency indicates that there is an ordering requirement between the dependent node and associated parent node.
6. The system of claim 1 , wherein the processor is further configured to analyze dependent actions and, in response to a determination that a dependent action being inserted into the polytree queue can be combined with an action of a parent node, collapses the dependent action into the parent node.
7. A method, comprising:
receiving data from a client device, the data being indicative of actions associated with a shared resource accessible by a plurality of client devices;
inserting the actions as nodes into a polytree queue defined by a tree structure in which root level nodes form branches of the tree structure and are located on a same level in the tree structure as parent nodes, and wherein at least one child node depends from multiple parent nodes, wherein actions that do not depend on other actions in the polytree queue are inserted as root level nodes, and actions that depend on other actions in the polytree queue are inserted as child nodes; and
executing nodes in the polytree queue to synchronize data from the client device with the shared resource, wherein root level nodes are scheduled for immediate concurrent execution with each other, and execution of child nodes is delayed until parent nodes of an associated child node are executed,
wherein the at least one child node that depends from multiple parent nodes is promoted to a root level node only after execution of all of the multiple parent nodes, and
wherein the polytree queue includes a first root level node that is prioritized over a second root level node based on a first-in first-out scheme, wherein the first root level node has a plurality of child level nodes dependent therefrom, and wherein after execution of the first root level node, the plurality of child nodes are promoted to root level nodes for execution after the second root level node.
8. The method of claim 7 , further comprising analyzing dependent actions and, in response to a determination that a dependent action being inserted into the polytree queue can be combined with a parent node, collapsing the dependent action into the parent node.
9. The method of claim 7 , wherein after execution of the root level node, the root level node is removed from the polytree queue, wherein the actions involve file system operations that include: create, delete, move, rename, upload, save and update, and wherein the multiple parent nodes of the at least one child node are located on a same level in the tree structure as a distinct parent node with a distinct child node.
10. The method of claim 7 , further comprising, in response to a failure while executing a node:
removing the node from the polytree queue as a failing node;
determining whether each dependent node of the failing node is typed as a hard dependency or a soft dependency;
removing dependent nodes from the polytree queue typed as hard dependencies; and
maintaining dependent nodes typed as soft dependencies in the polytree queue.
11. The method of claim 10 , wherein the soft dependency indicates that there is no ordering requirement between the dependent node and associated parent node and that the dependent node and associated parent node cannot execute simultaneously.
12. The method of claim 10 , wherein the hard dependency indicates that there is an ordering requirement between the dependent node and associated parent node.
13. A computer program product stored on a non-transitory computer readable medium, which when executed by a processor, synchronizes client device data, the program product comprising:
program code for receiving data from a client device, the data being indicative of actions associated with a shared resource accessible by a plurality of client devices;
program code for inserting the actions as nodes into a polytree queue defined by a tree structure in which root level nodes form branches of the tree structure and are located on a same level in the tree structure as parent nodes, and wherein at least one child node depends from multiple parent nodes, wherein actions that do not depend on other actions in the polytree queue are inserted as root level nodes, and actions that depend on other actions in the polytree queue are inserted as child nodes; and
program code for executing nodes in the polytree queue to synchronize data from the client device with the shared resource, wherein root level nodes are scheduled for immediate concurrent execution with each other, and execution of child nodes is delayed until all parent nodes of an associated child node are executed,
wherein the at least one child node that depends from multiple parent nodes is promoted to a root level node only after execution of all of the multiple parent nodes, and
wherein the polytree queue includes a first root level node that is prioritized over a second root level node based on a first-in first-out scheme, wherein the first root level node has a plurality of child level nodes dependent therefrom, and wherein after execution of the first root level node, the plurality of child nodes are promoted to root level nodes for execution after the second root level node.
14. The program product of claim 13 , further comprising program code for analyzing dependent actions and, in response to a determination that a dependent action being inserted into the polytree queue can be combined with a parent node, collapsing the dependent action into the parent node.
15. The system of claim 1 , wherein inserting a child node includes examination of different branches of the tree structure to identify a dependency and insert the child node into branches in which a dependency exists.
16. The method of claim 7 , wherein inserting a child node includes examination of different branches of the tree structure to identify a dependency and insert the child node into branches in which a dependency exists.
17. The program product of claim 13 , wherein inserting a child node includes examination of different branches of the tree structure to identify a dependency and insert the child node into branches in which a dependency exists.