Dynamic caches with miss tables

• US 6,487,641 B1
• Filed: 09/05/2000
• Issued: 11/26/2002
• Est. Priority Date: 04/19/1999
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle Corporation
• Inventors: Sunkara, Ramu V., DʼSilva, Anil J., Almeida, Marcos G., Cusson, Michael J.
• Primary Examiner(s): Yoo, Do Hyun
• Assistant Examiner(s): GOODARZI, NASSER MOAZZAMI
• Application Number:
  US09/654,653
• Time in Patent Office: 812 Days
• Field of Search: 711/141-144, 711/118, 707/2, 707/10, 707/202, 709/202-203, 709/220, 712/218
• US Class Current: 711/144
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching

Abstract

A middle-tier Web server with a queryable cache that contains items from one or more data sources. Items are included in the cache on the basis of the probability of future hits on the items. When the data source determines that an item that has been included in the cache has changed, it sends an update message to the server, which updates the item if it is still included in the cache. In a preferred embodiment, the data source is a database system and triggers in the database system are used to generate update messages. In a preferred embodiment, the data access layer determines whether a data item required by an application program is in the cache. If it is, the data access layer obtains the item from the cache; otherwise, it obtains the item from the data source. The queryable cache includes a miss table that accelerates the determination of whether a data item is in the cache. The miss table is made up of miss table entries that relate the status of a data item to the query used to access the data item. There are three statuses: miss, indicating that the item is not in the cache, hit, indicating that it is, and unknown, indicating that it is not known whether the item is in the cache. When an item is referenced, the query used to access it is presented to the table. If the entry for the query has the status miss, the data access layer obtains the item from the data source instead of attempting to obtain it from the cache. If the entry has the status unknown, the data access layer attempts to obtain it from the cache and the miss table entry for the item is updated in accordance with the result. When a copy of an item is added to the cache, miss table entries with the status miss are set to indicate unknown.

Claims

1. An improved network server of a type that includes a cache containing a copy of a rowset from a remote location, the network server responding to a rowset specifier specifying the remote location and the rowset therein by providing the copy from the cache when the copy is therein,

the network server having the improvement comprising:

a miss table that relates the rowset specifier to a status indicator, the status indicator being able to indicate at least whether the copy is in the cache, the network server using the miss table prior to applying the rowset specifier to the cache to determine whether the copy is in the cache, and when not, responding to the rowset specifier by fetching the rowset from the remote location.

2. The network server set forth in claim 1 wherein:

the miss table employs an entry that includes at least the status indicator to relate the rowset specifier to the status indicator; and

the status indicator is further able to indicate that it is unknown whether the copy is in the cache,

the network server responding when the status indicator indicates that it is unknown whether the copy is in the cache by searching for the copy in the cache and setting the status indicator in the entry according to whether the copy is in the cache.

3. The improved network server set forth in claim 2 wherein:

the network server further fetches the copy from the cache when the copy is therein.

4. The improved network server set forth in claim 2 wherein:

when a copy is added to the cache and the status indicator affected thereby currently indicates that the copy is not in the cache, the network server sets at least that status indicator to indicate unknown.

5. The improved network server set forth in claim 4 wherein:

the miss table further comprises a plurality of the miss table entries, each entry having an index; and

when the network server responds to the rowset specifier, the network server hashes the rowset specifier to obtain an index of a miss table entry.

6. The improved network server set forth in any one of claims 1 through 5 wherein:

the cache and the remote location are queryable; and

the rowset specifier specifies a query.

7. An improved method of obtaining a rowset stored in a remote data source in response to a rowset specifier that specifies the remote data source and the rowset therein by performing the steps of

applying the rowset specifier to a local cache to retrieve a copy of the rowset therefrom;

and retrieving the rowset from the remote data source only if the copy is not in the local cache, the improved method further comprising the step of;

prior to the step of applying the rowset specifier to the local cache, applying the rowset specifier to a miss table that relates the rowset specifier to a status indicator indicating at least whether the copy is in the local cache,

the step of applying the rowset specifier to the local cache being performed only if the status indicator indicates that the copy is in the local cache.

8. The method set forth in claim 7 wherein

the miss table employs an entry that includes at least the status indicator to relate the rowset specifier to the,status indicator; and

the status indicator is further capable of indicating that it is unknown whether the copy is in the cache; and

the method further comprises the step performed when the status indicator indicates that it is unknown whether the copy is in the cache of;

searching for the copy in the cache and setting the status indicator in the entry according to whether the copy is in the cache.

9. The method set forth in claim 8 further comprising the step of:

fetching the copy from the cache when the copy is therein.

10. The method set forth in claim 8 further comprising the step of:

when a copy is added to the cache and the status indicator affected thereby currently indicates that the copy is not in the cache, setting at least that status indicator to indicate unknown.

11. The method set forth in claim 10 wherein

the miss table further comprises a plurality of the miss table entries, each entry having an index;

and

the method further comprises the step of;

hashing the rowset specifier to obtain an index of a miss table entry.

12. The method set forth in any one of claims 7 through 11 wherein:

the cache and the remote location are queryable; and

the rowset specifier specifies a query.

13. Apparatus that fetches items of data from a remote location, the apparatus comprising:

a cache that stores copies of the items and provides an item'"'"'s copy in response to an item specifier for the item;

a miss table that relates an item specifier to a status indicator that indicates at least whether there is a copy of the item specified by the item specifier in the cache; and

a dispatcher that responds to the item specifier by presenting the item specifier to the miss table prior to applying the item specifier to the cache and on receiving an indication from the miss table that there is no copy in the cache, fetching the item of data from the remote location.

14. The apparatus set forth in claim 13 wherein the apparatus further comprises:

a miss table manager that modifies the miss table;

the miss table employs an entry that includes at least the status indicator to relate the rowset specifier to the status indicator;

the status indicator may further indicate that it is unknown whether there is a copy of the item; and

when the status indicator indicates that it is unknown whether there is a copy of the item, the cache responds to the item specifier and provides an indication whether there is a copy of the item to the miss table manager, the miss table manager updating the miss table in accordance with the indication.

15. The apparatus set forth in claim 14 wherein:

the cache provides a change event notification to the miss table manager when a copy of a data item has been added to the cache; and

when the status indicator affected thereby currently indicates that the copy is not in the cache, the miss table manager responds to the change event notification by setting the status indicator to indicate unknown.

16. The apparatus set forth in any one of claims 13 through 15 wherein:

the cache and the remote location are queryable; and

the item specifier specifies a query.