System, method and computer program product for efficient caching of hierarchical items

• US 9,183,241 B2
• Filed: 03/24/2014
• Issued: 11/10/2015
• Est. Priority Date: 03/30/2011
• Status: Active Grant

• Current Assignee: Ip Ot Sub Ulc
• Original Assignee: Open TEXT SA (Open Text Corporation)
• Inventors: Wongkar, Adison Hana, Gupta, Shaival
• Primary Examiner(s): OBISESAN, AUGUSTINE KUNLE
• Application Number:
  US14/223,785
• Publication Number:
  US 20140207825A1
• Time in Patent Office: 596 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: H04L 63/0281 Proxies
• CPC Class Codes: H04L 67/5682 Policies or rules for updating, deleting or replacing the stored data
• CPC Class Codes: H04L 7/0008 Synchronisation information channels, e.g. clock distribution lines

Abstract

Embodiments disclosed herein provide a “lazy” approach in caching a hierarchical navigation tree with one or more associated permission trees. In one embodiment, only a portion of a cached permission tree is updated. One embodiment of a method may comprise determining whether a dirty node exists by comparing tree timestamps of the permission tree and the master tree. If the tree timestamp of the master tree is temporally more recent than the tree timestamp of the permission tree, the permission tree has a dirty node and the method may operate to check node timestamps of the master and permission trees. This process may be repeated until the dirty node is found, at which time a portion of the permission tree associated with the dirty node may be reconstructed, rather than the entire permission tree itself, thereby eliminating or significantly reducing access time to the cached permission tree.

Claims

1. A method of caching hierarchical items in a network environment, the method comprising:

performing, by a server computer in the network environment;

caching a copy of a hierarchical navigation tree, the cached copy of the hierarchical navigation tree having nodes representing hierarchical items of a web site, each node in the cached copy of the hierarchical navigation tree having a tree timestamp and a node timestamp;

in response to a change to a first node in the cached copy of the hierarchical navigation tree, updating the tree timestamp and the node timestamp of a parent node of the first node and updating the tree timestamp of any upstream parent node of the parent node of the first node in the cached copy of the hierarchical navigation tree such that only a portion of the cached copy of the hierarchical navigation tree affected by the change to the first node is updated;

comparing the tree timestamp of a root node of the cached copy of the hierarchical navigation tree with a tree timestamp of a root node of a cached copy of a permission tree;

if the tree timestamp of the root node of the cached copy of the hierarchical navigation tree is more recent than the tree timestamp of the root node of the cached copy of the permission tree, comparing the node timestamp of each node in the cached copy of the hierarchical navigation tree and the node timestamp of each node in the cached copy of the permission tree until a dirty node in the cached copy of the permission tree is found;

constructing the dirty node in the cached copy of the permission tree relating to the change to the first node in the cached copy of the hierarchical navigation tree; and

building a portion of the cached copy of the permission tree containing the dirty node by updating the tree timestamp and the node timestamp of the dirty node in the cached copy of the permission tree and traversing the cached copy of the permission tree from the dirty node to the root node of the cached copy of the permission tree to update the tree timestamp of any upstream parent node of the dirty node in the cached copy of the permission tree.

2. The method according to claim 1, further comprising:

associating the hierarchical navigation tree with one or more permission trees, each permission tree of the one or more permission trees having a set of nodes representing access restriction of a group of users to the web site.

3. The method according to claim 2, further comprising:

caching the hierarchical navigation tree and the one or more permission trees in a hierarchical cache on the server computer.

4. The method according to claim 1, further comprising:

tracking a temporal point in time when each node in the hierarchical navigation tree was last updated using the node timestamp.

5. The method according to claim 1, wherein the change represents adding the first node, deleting the first node, reordering the first node, re-permissioning the first node, de-permissioning the first node, re-parenting the first node, or editing the first node.

6. The method according to claim 1, further comprising:

in response to a request from a user, updating a portion of a permission tree associated with the user, the portion of the permission tree containing one or more dirty nodes in comparison to corresponding nodes in the hierarchical navigation tree.

7. The method according to claim 6, further comprising:

determining each of the one or more dirty nodes in the portion of the permission tree by;

comparing a root tree timestamp of the hierarchical navigation tree with a root tree timestamp of the permission tree;

if the root tree time stamp of the hierarchical navigation tree is more recent than the root tree timestamp of the permission tree, comparing node timestamps of nodes in the permission tree with node timestamps of corresponding nodes in the hierarchical navigation tree; and

if a node time stamp for a node in the hierarchical navigation tree is not more recent than a node time stamp for a corresponding node in the permission tree, comparing a tree timestamp for the node in the hierarchical navigation tree with a tree timestamp for the corresponding node in the permission tree.

8. The method according to claim 1, wherein the parent node is a direct parent of the first node.

9. A computer program product comprising at least one non-transitory computer readable medium storing instructions translatable by a server computer where a copy of a hierarchical navigation tree is cached, the cached copy of the hierarchical navigation tree having nodes representing hierarchical items of a web site, each node in the cached copy of the hierarchical navigation tree having a tree timestamp and a node timestamp, the instructions when translated by the server computer cause the server computer to perform:

in response to a change to a first node in the cached copy of the hierarchical navigation tree, updating the tree timestamp and the node timestamp of a parent node of the first node and updating the tree timestamp of any upstream parent node of the parent node of the first node in the cached copy of the hierarchical navigation tree such that only a portion of the cached copy of the hierarchical navigation tree affected by the change to the first node is updated;

comparing the tree timestamp of a root node of the cached copy of the hierarchical navigation tree with a tree timestamp of a root node of a cached copy of a permission tree;

if the tree timestamp of the root node of the cached copy of the hierarchical navigation tree is more recent than the tree timestamp of the root node of the cached copy of the permission tree, comparing the node timestamp of each node in the cached copy of the hierarchical navigation tree and the node timestamp of each node in the cached copy of the permission tree until a dirty node in the cached copy of the permission tree is found;

constructing the dirty node in the cached copy of the permission tree relating to the change to the first node in the cached copy of the hierarchical navigation tree; and

building a portion of the cached copy of the permission tree containing the dirty nodes in node by updating the tree timestamp and the node timestamp of the dirty node in the cached copy of the permission tree and traversing the cached copy of the permission tree from the dirty node to the root node of the cached copy of the permission tree to update the tree timestamp of any upstream parent node of the dirty node in the cached copy of the permission tree.

10. The computer program product of claim 9, wherein the instructions when translated by the server computer further cause the server computer to perform:

associating the hierarchical navigation tree with one or more permission trees, each permission tree of the one or more permission trees having a set of nodes representing access restriction of a group of users to the web site.

11. The computer program product of claim 9, wherein the instructions when translated by the server computer further cause the server computer to perform:

tracking a temporal point in time when each node in the hierarchical navigation tree was last updated using the node timestamp.

12. The computer program product of claim 9, wherein the change represents adding the first node, deleting the first node, reordering the first node, re-permissioning the first node, de-permissioning the first node, re-parenting the first node, or editing the first node.

13. The computer program product of claim 9, wherein the instructions when translated by the server computer further cause the server computer to perform:

in response to a request from a user, updating a portion of a permission tree associated with the user, the portion of the permission tree containing one or more dirty nodes in comparison to corresponding nodes in the hierarchical navigation tree.

14. The computer program product of claim 13, wherein the instructions when translated by the server computer further cause the server computer to perform:

determining each of the one or more dirty nodes in the portion of the permission tree by;

comparing a root tree timestamp of the hierarchical navigation tree with a root tree timestamp of the permission tree;

if the root tree time stamp of the hierarchical navigation tree is more recent than the root tree timestamp of the permission tree, comparing node timestamps of nodes in the permission tree with node timestamps of corresponding nodes in the hierarchical navigation tree; and

if a node time stamp for a node in the hierarchical navigation tree is not more recent than a node time stamp for a corresponding node in the permission tree, comparing a tree timestamp for the node in the hierarchical navigation tree with a tree timestamp for the corresponding node in the permission tree.

15. A system, comprising:

a server computer caching a copy of a hierarchical navigation tree, the cached copy of the hierarchical navigation tree having nodes representing hierarchical items of a web site, each node in the cached copy of the hierarchical navigation tree having a tree timestamp and a node timestamp, the server computer configured to perform;

in response to a change to a first node in the cached copy of the hierarchical navigation tree, updating the tree timestamp and the node timestamp of a parent node of the first node and updating the tree timestamp of any upstream parent node of the parent node of the first node in the cached copy of the hierarchical navigation tree such that only a portion of the cached copy of the hierarchical navigation tree affected by the change to the first node is updated;

comparing the tree timestamp of a root node of the cached copy of the hierarchical navigation tree with a tree timestamp of a root node of a cached copy of a permission tree;

if the tree timestamp of the root node of the cached copy of the hierarchical navigation tree is more recent than the tree timestamp of the root node of the cached copy of the permission tree, comparing the node timestamp of each node in the cached copy of the hierarchical navigation tree and the node timestamp of each node in the cached copy of the permission tree until a dirty node in the cached copy of the permission tree is found;

constructing the dirty node in the cached copy of the permission tree relating to the change to the first node in the cached copy of the hierarchical navigation tree; and

building a portion of the cached copy of the permission tree containing the dirty node by updating the tree timestamp and the node timestamp of the dirty node in the cached copy of the permission tree and traversing the cached copy of the permission tree from the dirty node to the root node of the cached copy of the permission tree to update the tree timestamp of any upstream parent node of the dirty node in the cached copy of the permission tree.

16. The system of claim 15, wherein the server computer is further configured to perform:

associating the hierarchical navigation tree with one or more permission trees, each permission tree of the one or more permission trees having a set of nodes representing access restriction of a group of users to the web site.

17. The system of claim 16, wherein the hierarchical navigation tree and the one or more permission trees are cached in a hierarchical cache on the server computer.

18. The system of claim 15, wherein the server computer is further configured to perform:

tracking a temporal point in time when each node in the hierarchical navigation tree was last updated using the node timestamp.

19. The system of claim 15, wherein the change represents adding the first node, deleting the first node, reordering the first node, re-permissioning the first node, de-permissioning the first node, re-parenting the first node, or editing the first node.

20. The system of claim 15, wherein the server computer is further configured to perform:

in response to a request from a user, updating a portion of a permission tree associated with the user, the portion of the permission tree containing one or more dirty nodes in comparison to corresponding nodes in the hierarchical navigation tree.

21. The system of claim 20, wherein the server computer is further configured to perform:

determining each of the one or more dirty nodes in the portion of the permission tree;

comparing a root tree timestamp of the hierarchical navigation tree with a root tree timestamp of the permission tree;

if the root tree time stamp of the hierarchical navigation tree is more recent than the root tree timestamp of the permission tree, comparing node timestamps of nodes in the permission tree with node timestamps of corresponding nodes in the hierarchical navigation tree; and

if a node time stamp for a node in the hierarchical navigation tree is not more recent than a node time stamp for a corresponding node in the permission tree, comparing a tree timestamp for the node in the hierarchical navigation tree with a tree timestamp for the corresponding node in the permission tree.