Electrical computers and digital processing systems: multicomput – Distributed data processing
Reexamination Certificate
1999-09-08
2003-02-04
Wiley, David (Department: 2155)
Electrical computers and digital processing systems: multicomput
Distributed data processing
C709S203000, C709S220000, C709S223000, C707S793000
Reexamination Certificate
active
06516336
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a computer system, and deals more particularly with a method, system, and computer program product for using a two-tiered cache for storing and accessing hierarchical data, in order to minimize memory usage and improve performance.
2. Description of the Related Art
In the distributed client/server environment, there is a need to disseminate information within a company or corporation that is required by users for everyday operation. This information typically includes such things as accounting information, computer configuration information, etc., and is typically available on one or more servers which are accessed by the users. Since companies, particularly large corporations, are often organized hierarchically (such as divisions, departments, etc.), each of these hierarchical levels may specify information pertinent to that level, where each lower level of hierarchical information augments or overrides the level(s) above it. In particular, this hierarchical approach to specifying information is often used for computer configuration information. In this scenario, each user of the company systems accesses the information provided by the higher levels of the hierarchy, for example to use when connecting to the company network or when installing software on his computer. The user at this point occupies the lowest level of the hierarchy, and may customize the information obtained from the hierarchy above him. These customized values are often referred to as “user preferences” and may be unique to any user within the hierarchy.
FIG. 1
is an example of this type of hierarchical structure. This structure represents hierarchically stored information, which typically mirrors the hierarchy of the organization. Company X
100
represents information stored for the corporate or highest level of the company. Any information defined at this level typically pertains to all elements of the hierarchy throughout the company, from organizations to individual users, because corporate settings tend to be broad in scope and define boundaries for the subordinate levels to follow. In this example, there is a subordinate level in Company X
100
which represents the development organization
105
and the sales organization
110
. At this level, each subordinate organization uses the information from Company X
100
and may specify additional information to be used by its subordinate levels. Either or both of the development and sales organizations may also make changes (i.e. augmenting or overriding defined values) to the original information from the Company X level. This changed information is then made available to the subordinates of the level at which the change was made.
Moving down the hierarchy to the next level under development
105
, we have two more organizations or possibly groups (such as a department of employees): (1) the user interface group
115
and (2) the API group
120
. Both of these groups will inherit the information provided by the higher levels in this hierarchy. These groups also may add or modify information to further refine the data from the higher levels of the hierarchy, where these changes are then made available to the subordinate levels of the hierarchy. In this example, the subordinates to the user interface group
115
are the users (
140
,
145
) of the company resources. Here, for example, Sue
140
inherits all the information available from following a path from the node
140
representing Sue up through and including all of the higher levels in the hierarchy.
The information provided to Sue
140
may include values for things such as system configuration attributes, including the colors displayed on her screen and the size of the windows on her display. Sue may choose to override these values (or any values provided by a higher level) in order to customize her display to her own preferences. In doing so, Sue has now created her own customized set of values representing a coalesced version of all the higher level values from the highest level
100
down to and including the values Sue
140
provides. This customized set of information is typically stored in a database or other repository on a server for access by the user any time he needs to use the information. (It should be noted that overriding values defined at a higher level of the hierarchy may in some cases be limited to a subset of all the defined values, since some higher level values may be mandatory.)
When a user of a client machine requests data that is stored in a hierarchical structure (such as the example for FIG.
1
), what the user wants in response is the “coalesced” set of data. As used herein, a coalesced set of data refers to gathering all the data in the hierarchy, and merging data together such that the value for any given attribute is set by the lowest level in the hierarchy which has that attribute defined. From the user's point of view, he receives a complete set of data, which is really a composite of the actual data from the user level and all levels above it in the hierarchical chain.
These complex types of stored data may impact overall performance of the server when information is retrieved since the coalescing of the stored data may involve a combination of several memory accesses as well as disk retrievals to collect, and then coalesce, all the necessary information before responding to a user request. For example, if Sue requests information for the hierarchy of
FIG. 1
, separate disk accesses (which may further require round trips through a distributed network) may be needed to retrieve the information for Company X
100
, Development
105
, User Interface
115
, and finally for Sue
140
.
While only a simple hierarchy is shown in
FIG. 1
, many more levels (with many nodes at each level) may exist in an organization or corporation. Performing multiple disk accesses to retrieve information for each level is a computationally expensive operation. In addition, having to continually recalculate the coalesced image of the data when changes occur is compute intensive. Conversely, caching the complete set of coalesced data for every user is very storage or memory intensive and requires a complete recoalescence any time data represented in the coalescence is changed.
Accordingly, what is needed is a technique that avoids the performance penalty of this continual recalculation, and avoids the storage penalty of storing large amounts of coalesced data.
SUMMARY OF THE INVENTION
An object of the present invention is to provide a technique which avoids continual recalculation for coalescing complex hierarchical data and minimizes the impact on performance and memory consumption in a client/server environment.
Another object of the present invention is to provide this technique using a two-tiered cache.
Yet another object of the present invention is to provide this technique in a manner that allows a server to determine if a set of coalesced cached values is out-of-date with the data store it represents.
Other objects and advantages of the present invention will be set forth in part in the description and in the drawings which follow and, in part, will be obvious from the description or may be learned by practice of the invention.
To achieve the foregoing objects, and in accordance with the purpose of the invention as broadly described herein, the present invention provides a method, system, and computer program product for use in a computing environment for using a two-tiered cache for storing and accessing hierarchical data. This technique comprises: 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 the user nodes is a child node of the top-level node or one of the intermediate-level nodes, wherein the hierarchical structure is stored in a data repository accessible in the computing environment and wherein each of the nodes has a corresponding last up
Davis Charlotte Elizabeth
Fisher Bradford Austin
Greenfield Jonathan Scott
Doubet Marcia L.
Jean Frantz B.
Ray-Yarletts Jeanine S.
Wiley David
LandOfFree
Method and system for using a two-tiered cache does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for using a two-tiered cache, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for using a two-tiered cache will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3179642