Method and system for using a two-tiered cache

• US 6,516,336 B1
• Filed: 09/08/1999
• Issued: 02/04/2003
• Est. Priority Date: 09/08/1999
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Davis, Charlotte Elizabeth, Fisher, Bradford Austin, Greenfield, Jonathan Scott
• Primary Examiner(s): Wiley, David
• Assistant Examiner(s): Jean, Frantz B.
• Application Number:
  US09/392,035
• Time in Patent Office: 1,245 Days
• Field of Search: 709/201, 709/203, 709/220, 709/223, 707/8
• US Class Current: 709/201
• CPC Class Codes: G06F 16/252 between a Database Management System and a front-end application
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

A method, system, and computer program product code using a two-tiered cache for hierarchically structured data. The present invention significantly reduces the frequency of computationally intense processing used to retrieve hierarchically structured data and reduces the system cache storage requirements for maintaining coalesced images.

Claims

1. A computer program product embodied on a computer-readable medium in a computing environment, for using a two-tiered cache for storing and accessing hierarchical data, comprising:

a hierarchical structure of data comprising a top-level node, one or more intermediate levels having one or more intermediate-level nodes, and one or more user nodes, wherein each of said user nodes is a child node of said top-level node or one of said intermediate-level nodes, wherein said hierarchical structure is stored in a data repository accessible in said computing environment and wherein each of said nodes has a corresponding last update timestamp stored in said repository, said last update timestamp for said user nodes and said top-level node representing a last update to one or more data values of said node and said last update timestamp for said intermediate nodes representing an update of data values of said intermediate node or a parent of said intermediate node;

computer-readable program code means for creating coalesced data images (CDls) for each of said top-level or intermediate-level nodes which is a group node, wherein a particular node is one of said group nodes when said particular node has one or more of said user nodes as a child, and wherein said CDI for said particular node comprises a coalescence of data values for said particular node, said top-level node, and all of said intermediate-level nodes in a hierarchical path from said particular node to said top-level node;

computer-readable program code means for storing said created CDIs in a central data cache along with a CDI timestamp for each of said stored CDIs wherein said CDI timestamp for each of said CDIs is set to said corresponding last update timestamp for said corresponding node; and

computer-readable program code means for storing user data for each of one or more users in a client cache for said user along with a client cache timestamp, wherein;

each of said users is associated with a selected one of said user nodes;

said client cache timestamp is set to said corresponding last update timestamp for said corresponding user node; and

said stored user data is uncoalesced.

2. The computer program product according to claim 1, further comprising:

computer readable program code means for updating one or more of said data values for a selected node, further comprising;

computer readable program code means for applying an update to said data values in said repository;

computer readable program code means for updating said last update timestamp corresponding to said selected node;

computer readable program code means for determining whether said selected node is one of said group nodes; and

computer readable program code means for propagating said updated timestamp to each of said group nodes subordinate to said selected group node in said hierarchical structure when said computer readable program code means for determining has a positive result.

3. The computer program product according to claim 2, further comprising:

computer readable program code means for retrieving a coalesced result in response to a request from a particular one of said users, wherein said request may specify a refreshed result or an unrefreshed result.

4. The computer program product according to claim 3, wherein said computer readable program code means for retrieving a refreshed result further comprises:

computer readable program code means for retrieving said user data for said particular user, further comprising;

computer readable program code means for retrieving said user data from said client cache when (1) said client cache for said particular user exists and (2) said client cache timestamp for said particular user'"'"'s client cache is not older than said last update timestamp corresponding to said particular user'"'"'s user node in said repository; and

computer readable program code means for populating said particular user'"'"'s client cache otherwise, wherein said populating further comprises;

computer readable program code means for retrieving said user data from said particular user'"'"'s user node in said repository;

computer readable program code means for storing said retrieved user data in said client cache for said user; and

computer readable program code means for setting said client cache timestamp for said user to said last update timestamp for said corresponding user node; and

computer readable program code means for retrieving said CDI for said group node of which said user node is one of said children, further comprising;

computer readable program code means for retrieving said CDI from said central data cache when (1) said CDI for said group node exists and (2) said CDI timestamp for said CDI is not older than said last update timestamp corresponding to said group node in said repository; and

computer readable program code means for creating said CDI otherwise, wherein said creating further comprises;

computer readable program code means for retrieving said data values from said repository for said group node, said top-level node, and all of said intermediate-level nodes in said hierarchical path from said group node to said top-level node;

computer readable program code means for coalescing said retrieved data values;

computer readable program code means for storing said coalesced data values as said CDI for said group node in said central data cache; and

computer readable program code means for setting said CDI timestamp for said CDI to said last update timestamp for said corresponding group node; and

computer readable program code means for merging said retrieved user data with said retrieved CDI.

5. The computer program product according to claim 3, wherein said computer readable program code means for retrieving an unrefreshed result further comprises:

computer readable program code means for retrieving said user data for said particular user, further comprising;

computer readable program code means for retrieving said user data from said client cache when said client cache for said particular user exists; and

computer readable program code means for populating said particular user'"'"'s client cache otherwise, wherein said populating further comprises;

computer readable program code means for retrieving said user data from said particular user'"'"'s user node in said repository;

computer readable program code means for storing said retrieved user data in said client cache for said user; and

computer readable program code means for setting said client cache timestamp for said user to said last update timestamp for said corresponding user node;

computer readable program code means for retrieving said CDI for said group node of which said user node is one of said children, further comprising;

computer readable program code means for retrieving said CDI from said central data cache when said CDI for said group node exists; and

computer readable program code means for creating said CDI otherwise, wherein said creating further comprises;

computer readable program code means for retrieving said data values from said repository for said group node, said top-level node, and all of said intermediate-level nodes in said hierarchical path from said group node to said top-level node;

computer readable program code means for coalescing said retrieved data values;

computer readable program code means for storing said coalesced data values as said CDI for said group node in said central data cache; and

computer readable program code means for setting said CDI timestamp for said CDI to said last update timestamp for said corresponding group node; and

computer readable program code means for merging said retrieved user data with a parent CDI associated with a parent node of said user node.

6. The computer program product according to claim 4, wherein said computer readable program code means for creating further comprises:

computer readable program code means for repeating said creating for each of said group nodes above said group node in said hierarchical path until reaching a first of said group nodes for which said CDI timestamp for said CDI of said first group node is not older than said last update timestamp corresponding to said group node in said repository.

7. The computer program product according to claim 4, wherein:

said computer readable program code means for retrieving said user data from said client cache determines whether said client cache timestamp for said particular user'"'"'s client cache is different from said last update timestamp corresponding to said particular user'"'"'s user node in said repository rather than whether said client cache timestamp is not older than said last update timestamp; and

said computer readable program code means for retrieving said CDI from said central data cache determines whether said CDI timestamp for said CDI is different from said last update timestamp corresponding to said group node in said repository rather than whether said CDI timestamp is not older than said last update timestamp.

8. A system for using a two-tiered cache for storing and accessing hierarchical data, comprising:

a hierarchical structure of data comprising a top-level node, one or more intermediate levels having one or more intermediate-level nodes, and one or more user nodes, wherein each of said user nodes is a child node of said top-level node or one of said intermediate-level nodes, wherein said hierarchical structure is stored in a data repository accessible in said computing environment and wherein each of said nodes has a corresponding last update timestamp stored in said repository, said last update timestamp for said user nodes and said top-level node representing a last update to one or more data values of said node and said last update timestamp for said intermediate nodes representing an update of data values of said intermediate node or a parent of said intermediate node;

means for creating coalesced data images (CDIs) for each of said top-level or intermediate-level nodes which is a group node, wherein a particular node is one of said group nodes when said particular node has one or more of said user nodes as a child, and wherein said CDI for said particular node comprises a coalescence of data values for said particular node, said top-level node, and all of said intermediate-level nodes in a hierarchical path from said particular node to said top-level node;

means for storing said created CDIs in a central data cache along with a CDI timestamp for each of said stored CDIs wherein said CDI timestamp for each of said CDIs is set to said corresponding last update timestamp for said corresponding node; and

means for storing user data for each of one or more users in a client cache for said user along with a client cache timestamp, wherein;

each of said users is associated with a selected one of said user nodes;

said client cache timestamp is set to said corresponding last update timestamp for said corresponding user node; and

said stored user data is uncoalesced.

9. The system according to claim 8, further comprising:

means for updating one or more of said data values for a selected node, further comprising;

means for applying an update to said data values in said repository;

means for updating said last update timestamp corresponding to said selected node;

means for determining whether said selected node is one of said group nodes; and

means for propagating said updated timestamp to each of said group nodes subordinate to said selected group node in said hierarchical structure when said means for determining has a positive result.

10. The system according to claim 9, further comprising:

means for retrieving a coalesced result in response to a request from a particular one of said users, wherein said request may specify a refreshed result or an unrefreshed result.

11. The system according to claim 10, wherein said means for retrieving a refreshed result further comprises:

means for retrieving said user data for said particular user, further comprising;

means for retrieving said user data from said client cache when (1) said client cache for said particular user exists and (2) said client cache timestamp for said particular user'"'"'s client cache is not older than said last update timestamp corresponding to said particular user'"'"'s user node in said repository; and

means for populating said particular user'"'"'s client cache otherwise, wherein said populating further comprises;

means for retrieving said user data from said particular user'"'"'s user node in said repository;

means for storing said retrieved user data in said client cache for said user; and

means for setting said client cache timestamp for said user to said last update timestamp for said corresponding user node;

means for retrieving said CDI for said group node of which said user node is one of said children, further comprising;

means for retrieving said CDI from said central data cache when (1) said CDI for said group node exists and (2) said CDI timestamp for said CDI is not older than said last update timestamp corresponding to said group node in said repository; and

means for creating said CDI otherwise, wherein said creating further comprises;

means for retrieving said data values from said repository for said group node, said top-level node, and all of said intermediate-level nodes in said hierarchical path from said group node to said top-level node;

means for coalescing said retrieved data values;

means for storing said coalesced data values as said CDI for said group node in said central data cache; and

means for setting said CDI timestamp for said CDI to said last update timestamp for said corresponding group node; and

means for merging said retrieved user data with said CDI of said parent node.

12. The system according to claim 10, wherein said means for retrieving an unrefreshed result further comprises:

means for retrieving said user data for said particular user, further comprising;

means for retrieving said user data from said client cache when said client cache for said particular user exists; and

means for populating said particular user'"'"'s client cache otherwise, wherein said populating further comprises;

means for retrieving said user data from said particular user'"'"'s user node in said repository;

means for storing said retrieved user data in said client cache for said user; and

means for setting said client cache timestamp for said user to said last update timestamp for said corresponding user node;

means for retrieving said CDI for said group node of which said user node is one of said children, further comprising;

means for retrieving said CDI from said central data cache when said CDI for said group node exists; and

means for creating said CDI otherwise, wherein said creating further comprises;

means for retrieving said data values from said repository for said group node, said top-level node, and all of said intermediate-level nodes in said hierarchical path from said group node to said top-level node;

means for coalescing said retrieved data values;

means for storing said coalesced data values as said CDI for said group node in said central data cache; and

means for setting said CDI timestamp for said CDI to said last update timestamp for said corresponding group node; and

means for merging said retrieved user data with a parent CDI associated with a parent node of said user node.

13. The system according to claim 11, wherein said means for creating further comprises:

means for repeating said creating for each of said group nodes above said group node in said hierarchical path until reaching a first of said group nodes for which said CDI timestamp for said CDI of said first group node is not older than said last update timestamp corresponding to said group node in said repository.

14. The system according to claim 11, wherein:

said means for retrieving said user data from said client cache determines whether said client cache timestamp for said particular user'"'"'s client cache is different from said last update timestamp corresponding to said particular user'"'"'s user node in said repository rather than whether said client cache timestamp is not older than said last update timestamp; and

said means for retrieving said CDI from said central data cache determines whether said CDI timestamp for said CDI is different from said last update timestamp corresponding to said group node in said repository rather than whether said CDI timestamp is not older than said last update timestamp.

15. A method for using a two-tiered cache for storing and accessing hierarchical data, comprising the steps of:

providing a hierarchical structure of data comprising a top-level node, one or more intermediate levels having one or more intermediate-level nodes, and one or more user nodes, wherein each of said user nodes is a child node of said top-level node or one of said intermediate-level nodes, wherein said hierarchical structure is stored in a data repository accessible in said computing environment and wherein each of said nodes has a corresponding last update timestamp stored in said repository, said last update timestamp for said user nodes and said top-level node representing a last update to one or more data values of said node and said last update timestamp for said intermediate nodes representing an update of data values of said intermediate node or a parent of said intermediate node;

creating coalesced data images (CDIs) for each of said top-level or intermediate-level nodes which is a group node, wherein a particular node is one of said group nodes when said particular node has one or more of said user nodes as a child, and wherein said CDI for said particular node comprises a coalescence of data values for said particular node, said top-level node, and all of said intermediate-level nodes in a hierarchical path from said particular node to said top-level node;

storing said created CDIs in a central data cache along with a CDI timestamp for each of said stored CDIs wherein said CDI timestamp for each of said CDIs is set to said corresponding last update timestamp for said corresponding node; and

storing user data for each of one or more users in a client cache for said user along with a client cache timestamp, wherein;

each of said users is associated with a selected one of said user nodes;

said client cache timestamp is set to said corresponding last update timestamp for said corresponding user node; and

said stored user data is uncoalesced.

16. The method according to claim 15, further comprising the step of:

updating one or more of said data values for a selected node, further comprising the steps of;

applying an update to said data values in said repository;

updating said last update timestamp corresponding to said selected node;

determining whether said selected node is one of said group nodes; and

propagating said updated timestamp to each of said group nodes subordinate to said selected group node in said hierarchical structure when said determining step has a positive result.

17. The method according to claim 16, further comprising the step of:

retrieving a coalesced result in response to a request from a particular one of said users, wherein said request may specify a refreshed result or an unrefreshed result.

18. The method according to claim 17, wherein said retrieving a refreshed result step further comprises the steps of:

retrieving said user data for said particular user, further comprising the steps of;

retrieving said user data from said client cache when (1) said client cache for said particular user exists and (2) said client cache timestamp for said particular user'"'"'s client cache is not older than said last update timestamp corresponding to said particular user'"'"'s user node in said repository; and

populating said particular user'"'"'s client cache otherwise, wherein said populating further comprises the steps of;

retrieving said user data from said particular user'"'"'s user node in said repository;

storing said retrieved user data in said client cache for said user; and

setting said client cache timestamp for said user to said last update timestamp for said corresponding user node;

retrieving said CDI for said group node of which said user node is one of said children, further comprising the steps of;

retrieving said CDI from said central data cache when (1) said CDI for said group node exists and (2) said CDI timestamp for said CDI is not older than said last update timestamp corresponding to said group node in said repository; and

creating said CDI otherwise, wherein said creating further comprises the steps of;

retrieving said data values from said repository for said group node, said top-level node, and all of said intermediate-level nodes in said hierarchical path from said group node to said top-level node;

coalescing said retrieved data values;

storing said coalesced data values as said CDI for said group node in said central data cache; and

setting said CDI timestamp for said CDI to said last update timestamp for said corresponding group node; and

merging said retrieved user data with said CDI of said parent node.

19. The method according to claim 17, wherein said retrieving an unrefreshed result step further comprises the steps of:

retrieving said user data for said particular user, further comprising the steps of;

retrieving said user data from said client cache when said client cache for said particular user exists; and

populating said particular user'"'"'s client cache otherwise, wherein said populating step further comprises the steps of;

retrieving said user data from said particular user'"'"'s user node in said repository;

storing said retrieved user data in said client cache for said user; and

setting said client cache timestamp for said user to said last update timestamp for said corresponding user node;

retrieving said CDI for said group node of which said user node is one of said children, further comprising the steps of;

retrieving said CDI from said central data cache when said CDI for said group node exists; and

creating said CDI otherwise, wherein said creating step further comprises the steps of;

retrieving said data values from said repository for said group node, said top-level node, and all of said intermediate-level nodes in said hierarchical path from said group node to said top-level node;

coalescing said retrieved data values;

storing said coalesced data values as said CDI for said group node in said central data cache; and

setting said CDI timestamp for said CDI to said last update timestamp for said corresponding group node; and

merging said retrieved user data with a parent CDI associated with a parent node of said user node.

20. The method according to claim 18, wherein said creating step further comprises the step of:

repeating said creating step for each of said group nodes above said group node in said hierarchical path until reaching a first of said group nodes for which said CDI timestamp for said CDI of said first group node is not older than said last update timestamp corresponding to said group node in said repository.

21. The method according to claim 18, wherein:

said retrieving said user data from said client cache step determines whether said client cache timestamp for said particular user'"'"'s client cache is different from said last update timestamp corresponding to said particular user'"'"'s user node in said repository rather than whether said client cache timestamp is not older than said last update timestamp; and

said retrieving said CDI from said central data cache step determines whether said CDI timestamp for said CDI is different from said last update timestamp corresponding to said group node in said repository rather than whether said CDI timestamp is not older than said last update timestamp.