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

• US 9,674,150 B2
• Filed: 10/22/2015
• Issued: 06/06/2017
• Est. Priority Date: 03/30/2011
• Status: Active Grant

• Current Assignee: Ip Ot Sub Ulc
• Original Assignee: Open Text Sa Ulc (Open Text Corporation)
• Inventors: Wongkar, Adison Hana, Gupta, Shaival
• Primary Examiner(s): OBISESAN, AUGUSTINE KUNLE
• Application Number:
  US14/920,265
• Publication Number:
  US 20160043999A1
• Time in Patent Office: 593 Days
• 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:

receiving, by a server machine from a computing device communicatively connected to the server machine, a request for a change to a web site;

updating, by the server machine, a master tree to reflect the change to the web site, the master tree having nodes representing hierarchical items of the web site and edges representing hierarchical relationships among the hierarchical items, each node of the nodes in the master tree having a tree timestamp and a node timestamp, the updating including updating the tree timestamp and the node timestamp of a first node affected by the change and updating the tree timestamp of any upstream parent node of the first node in the master tree;

determining, by the server machine, a permission tree affected by the change, the permission tree associated with a user group permitted to view a particular portion of the hierarchical items of the web site, the permission tree having a set of nodes corresponding to the particular portion of the hierarchical items of the web site and representing access restriction of the user group to the particular portion of the hierarchical items of the web site;

identifying, by the server machine, a dirty node in the permission tree, the identifying including comparing the tree timestamp of a root node of the master tree with a tree timestamp of a root node of the permission tree; and

constructing, by the server machine, a portion of the permission tree containing the dirty node, the constructing including updating the tree timestamp and the node timestamp of the dirty node and updating the tree timestamp of any upstream parent node of the dirty node in the portion of the permission tree containing the dirty node such that only the portion of the permission tree affected by the change is updated.

2. The method according to claim 1, wherein the server machine is part of a cluster of server machines in the network environment and wherein each server machine in the cluster has access to a cached copy of the permission tree.

3. The method according to claim 2, wherein the cluster of server machines has different internal time clocks and wherein cached copies of the permission tree have different timestamps.

4. The method according to claim 2, wherein the cluster of server machines has synchronized internal time clocks and wherein cached copies of the permission tree have synchronized timestamps.

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

6. The method according to claim 1, wherein the node timestamp is configured for tracking a temporal point in time when a node was last updated and wherein the tree timestamp is configured for tracking a temporal point in time when the master tree was last accessed.

7. The method according to claim 1, wherein the constructing including:

comparing a node time stamp of a node in the master tree with a node time stamp of a corresponding node in the permission tree; and

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

8. A computer program product comprising at least one non-transitory computer readable medium storing instructions translatable by a server machine to perform:

receiving, from a computing device communicatively connected to the server machine, a request for a change to a web site;

updating a master tree to reflect the change to the web site, the master tree having nodes representing hierarchical items of the web site and edges representing hierarchical relationships among the hierarchical items, each node of the nodes in the master tree having a tree timestamp and a node timestamp, the updating including updating the tree timestamp and the node timestamp of a first node affected by the change and updating the tree timestamp of any upstream parent node of the first node in the master tree;

determining a permission tree affected by the change, the permission tree associated with a user group permitted to view a particular portion of the hierarchical items of the web site, the permission tree having a set of nodes corresponding to the particular portion of the hierarchical items of the web site and representing access restriction of the user group to the particular portion of the hierarchical items of the web site;

identifying a dirty node in the permission tree, the identifying including comparing the tree timestamp of a root node of the master tree with a tree timestamp of a root node of the permission tree; and

constructing a portion of the permission tree containing the dirty node, the constructing including updating the tree timestamp and the node timestamp of the dirty node and updating the tree timestamp of any upstream parent node of the dirty node in the portion of the permission tree containing the dirty node such that only the portion of the permission tree affected by the change is updated.

9. The computer program product of claim 8, wherein the change represents adding a hierarchical item, deleting a hierarchical item, reordering a hierarchical item, re-permissioning a hierarchical item, de-permissioning a hierarchical item, re-parenting a hierarchical item, or editing a hierarchical item.

10. The computer program product of claim 8, wherein the node timestamp is configured for tracking a temporal point in time when a node was last updated and wherein the tree timestamp is configured for tracking a temporal point in time when the master tree was last accessed.

11. The computer program product of claim 8, wherein the constructing including:

comparing a node time stamp of a node in the master tree with a node time stamp of a corresponding node in the permission tree; and

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

13. The system of claim 11, further comprising:

a cluster of server machines, wherein the server machine is part of the cluster of server machines in the network environment and wherein each server machine in the cluster has access to a cached copy of the permission tree.

14. The system of claim 13, wherein the cluster of server machines has different internal time clocks and wherein cached copies of the permission tree have different timestamps.

15. The system of claim 13, wherein the cluster of server machines has synchronized internal time clocks and wherein cached copies of the permission tree have synchronized timestamps.

16. The system of claim 13, wherein the cluster of server machines resides in different physical locations.

17. The system of claim 11, further comprising:

a database storing the master tree, the database accessible by the server machine.

18. The system of claim 11, wherein the change represents adding a hierarchical item, deleting a hierarchical item, reordering a hierarchical item, re-permissioning a hierarchical item, de-permissioning a hierarchical item, re-parenting a hierarchical item, or editing a hierarchical item.

19. The system of claim 11, wherein the node timestamp is configured for tracking a temporal point in time when a node was last updated and wherein the tree timestamp is configured for tracking a temporal point in time when the master tree was last accessed.

20. The system of claim 11, wherein the constructing including:

comparing a node time stamp of a node in the master tree with a node time stamp of a corresponding node in the permission tree; and

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

12. A system, comprising:

a server machine having at least one processor, at least one non-transitory computer readable medium, and stored instructions translatable by the at least one processor to perform;

receiving, from a computing device communicatively connected to the server machine, a request for a change to a web site;

updating a master tree to reflect the change to the web site, the master tree having nodes representing hierarchical items of the web site and edges representing hierarchical relationships among the hierarchical items, each node of the nodes in the master tree having a tree timestamp and a node timestamp, the updating including updating the tree timestamp and the node timestamp of a first node affected by the change and updating the tree timestamp of any upstream parent node of the first node in the master tree;

determining a permission tree affected by the change, the permission tree associated with a user group permitted to view a particular portion of the hierarchical items of the web site, the permission tree having a set of nodes corresponding to the particular portion of the hierarchical items of the web site and representing access restriction of the user group to the particular portion of the hierarchical items of the web site;

identifying a dirty node in the permission tree, the identifying including comparing the tree timestamp of a root node of the master tree with a tree timestamp of a root node of the permission tree; and

constructing a portion of the permission tree containing the dirty node, the constructing including updating the tree timestamp and the node timestamp of the dirty node and updating the tree timestamp of any upstream parent node of the dirty node in the portion of the permission tree containing the dirty node such that only the portion of the permission tree affected by the change is updated.