Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2000-09-05
2002-11-26
Yoo, Do Hyun (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S141000, C711S118000, C709S220000
Reexamination Certificate
active
06487641
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention concerns caching of data in networks generally and more specifically concerns the caching of queryable data in network servers.
2. Description of the Prior Art
Once computers were coupled to communications networks, remote access to data became far cheaper and easier than ever before. Remote access remained the domain of specialists, however, since the available user interfaces for remote access were hard to learn and hard to use. The advent of World Wide Web protocols on the Internet have finally made remote access to data available to everyone. A high school student sitting at home can now obtain information about Karlsruhe, Germany from that city's Web site and a lawyer sitting in his or her office can use a computer manufacturer's Web site to determine what features his or her new PC ought to have and then configure, order, and pay for the PC.
A consequence of the new ease of remote access and the new possibilities it offers for information services and commerce has been an enormous increase in the amount of remote access. This has in turn lead to enormous new burdens on the services that provide remote access and the resulting performance problems are part of the reason why the World Wide Web has become the World Wide Wait.
FIG. 1
shows one of the causes. of the performance problems. At
101
, there is shown the components of the system which make it possible for a user at his or her PC to access an information source via the World Wide Web. Web browser
103
is a PC which is running Web browser software. The Web browser software outputs a universal resource locator (URL)
104
which specifies the location of a page of information in HTML format in the World Wide Web and displays HTML pages to the user. The URL may have associated with it a message containing data to be processed at the site of the URL as part of the process of obtaining the HTML page. For example, if the information is contained in a database, the message may specify a query on the data base. The results of the query would then be returned as part of the HTML page. Internet
105
routes the URL
104
and its associated message to the location specified by the URL, namely Web server
107
. There, HTML program
109
in Web server
107
makes the HTML page
106
specified by the URL and returns it to Web browser
103
. If the message specifies a query on the database in database server
115
, HTML program
109
hands the message off to Web application program
111
, which translates the message into a query in the form required by data access layer
112
.
Data access layer
112
is generally provided by the manufacturer of database server
115
. It takes queries written in standard forms such as OLE-DB, ODBC, or JOBC, converts the queries into the form required by database server
115
, and places the queries in messages in the form required by network
113
. Database server
115
then executes the query and returns the result via network
113
to data access layer
112
, which puts the results into the required standard form and returns them to Web application
111
, which in turn puts the result into the proper format for HTML program
109
. HTML program
109
then uses the result in making the HTML page
106
to be returned to browser
103
.
As may be seen from the above description, a response to a URL specifying a page whose construction involves database server
115
requires four network hops: one on Internet
105
from browser
103
to Web server
107
, one on network
113
from server
107
to server
115
, one on network
113
from server
115
to server
107
, and one on Internet
105
from server
107
to browser
103
. If more than one query is required for an HTML page, there will be a round trip on network
113
for each query.
Moreover, as shown at
117
, a typical Web transaction is a series of such responses: the first HTML page includes the URL for a next HTML page, and so forth. The transaction shown at
117
begins with a request for an HTML page that is a form which the user will fill out to make the query; data base server
115
provides the information for the HTML page. When that page is returned, the user fills out the form and when he or she is finished, the browser returns a URL with the query from the form to server
107
, which then deals with the query as described above and returns the result in another HTML page. That page permits the user to order, and when the user orders, the result is another query to database server
115
, this time, one which updates the records involved in the transaction.
Not only do Web transactions made as shown in
FIG. 1
involve many network hops, they also place a tremendous burden on data base server
115
. For example, if data base server
115
belongs to a merchant who sells goods on the Web and the merchant is having a special, many of the;transactions will require exactly the same sequence of HTML pages and will execute exactly the same queries, but because system
101
deals with each request from a web browser individually, each query must be individually executed by database server
115
.
The problems of system
101
are not new to the designers of computer systems. There are many situations in a computer system where a component of the system needs faster access to data from a given source, and when these situations occur, the performance of the system can be improved if copies of data that is frequently used by the component are kept at a location in the system to which the component has faster access than it has to the source of the data. When such copies exist, the location at which the copies are kept is termed a cache and the data is said to be cached in the system.
Caching is used at many levels in system
101
. For example, browser
103
keeps a cache of previously-displayed HTML pages, so that, it can provide a previously-displayed HTML page to the user without making a request for the page across Internet
105
. Web server
107
similarly may keep a cache of frequently-requested HTML pages, so that it can simply return the page to the user, instead of constructing it. Database server
115
, finally, may keep a cache of the information needed to answer frequently-made queries, so that it can return a result more quickly than if it were starting from scratch. In system
101
, the most effective use of caching is in Web server
107
, since data that is cached there is still accessible to all users of internet
105
, while the overhead of the hops on data access
113
is avoided.
Any system which includes caches must deal with two problems: maintaining consistency between the data in the cache and the data in the data source and choosing which data to cache. In system
101
, the first problem is solved in the simplest way possible: it is the responsibility of the component using the data to determine when it needs a new copy of the data from the data source. Thus, in browser
103
, the user will see a cached copy of a previously-viewed HTML page unless the user specifically clicks on his browser's “reload” button. Similarly, it is up to HTML program
109
to determine when it needs to redo the query that provided the results kept in a cached HTML page. The second problem is also simply solved: when a new page is viewed or provided, it replaces the least recently-used cached page.
Database systems such as the Oracle8™ server, manufactured by Oracle Corporation and described in Leverenz, et al., Oracle8 Server Concepts, release 8.0, Oracle Corporation, Redwood City, Calif., 1998., move a copy of a database closer to its users by replicating the original database at a location closer to the user. The replicated data base may replicate the entire original or only a part of it. Partial replications of a database are termed table snapshots. Such table snapshots are read-only. The user of the partial replication determines what part of the original database is in the table snapshot. Consistency with the original database is maintained by snapshot refresh
Almeida Marcos G.
Cusson Michael J.
D'Silva Anil J.
Sunkara Ramu V.
Moazzami Nasser
Nelson Gordon E.
Oracle Corporation
Yoo Do Hyun
LandOfFree
Dynamic caches with miss tables does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Dynamic caches with miss tables, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic caches with miss tables will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2980488