Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2000-12-18
2004-10-19
Portka, Gary (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C709S203000, C709S217000, C709S219000, C711S122000, C711S124000
Reexamination Certificate
active
06807606
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention is related to the field of network servers and, more particularly, to the use of cache memory to enhance network server performance.
2. Description of the Related Art
Internet traffic is growing at a rate that greatly exceeds increases in the number of users or the number of transactions. A major factor in this growth is the changing nature of Internet websites themselves. Formerly, web pages comprised mainly static content, such as text, images and links to other sites. The extent of the user's interaction with the website was to occasionally download an HTML page. And, since the content was the same regardless of who requested the page, it was comparatively simple for the web server to support numerous users. The present trend however, is toward interactive websites in which the content and appearance of the website change in response to user input. This is particularly true for e-commerce sites, which support online product selection and purchasing. Such sites are distinguished from earlier websites by their greater dynamic content. A familiar example of this is the “online catalog” provided at many Internet business sites. Each customer logged onto the site to make a purchase has the opportunity to browse the catalog, and even peruse detailed information on thousands of products. Seemingly, the web server must maintain and update a unique web page for each shopper. Internet users enjoy the convenience of such customizable, interactive websites, and customer expectations will undoubtedly provide an impetus for further use of dynamic content in web pages.
The burgeoning use of dynamic content in Internet web pages causes a problem however. Today's e-commerce sites are characterized by extremely high “browse-to-buy ratios.” For shopping sites, a typical ratio is 60 interactions that do not update permanent business records (“requests” or “queries”) to each one that does (“transactions”)—browsing a product description is an example of a request, while making a purchase exemplifies a transaction. One effect of the increasing prevalence of dynamic content is that, although the number of transactions is growing at a predictable (and manageable) rate, the number of requests is growing explosively. The high user-interactivity of modern dynamic content-based web pages is responsible for the large number of requests per transaction. Dynamic content-based pages must be executed for each user request, to update the user's browser screen in response to his input. This results in a tremendous amount of content that must be prepared and conveyed to the user during a single session.
Dealing with the sheer volume of Internet traffic may impose an inordinate financial burden on the e-business. User expectations compel the site provider to provide dynamic web content promptly in response to their requests. If potential customers perceive the website as too slow, they may cease visiting the site, resulting in lost business. The obvious way for a website to meet the increasing demand for information by potential customers is to augment its server-side hardware—i.e., add more computers, routers, etc. But this solution may be prohibitively expensive, and a more cost effective approach is preferable.
One such approach is caching, a technique commonly employed in digital computers to enhance performance. The main memory used in a computer for data storage is typically much slower than the processor. To accommodate the slower memory during a data access, wait states are customarily added to the processor's normal instruction timing. If the processor were required to always access data from the main memory, its performance would suffer significantly. Caching utilizes a small, but extremely fast memory buffer, and takes advantage of a statistical characteristic known as “data locality” to overcome the main memory access bottleneck. Data locality refers to the common tendency for consecutive data accesses to involve the same general region of memory. This is sometimes stated in terms of the “80/20” rule—i.e., 80% of the data accesses are to the same 20% of memory.
The following example, although not web-related, illustrates the benefits of caching in general. Assume we have a computer running a program to multiply two large arrays of numbers, and we want to consider ways the computer might be modified to allow it to run the program faster. The most obvious modification would be to increase the speed of the processor—but this helps only to a point. Each individual multiply operation in the program requires the processor to fetch two operands from memory, compute the product, and then write the result back to memory. At higher processor speeds, as the time required for the computation becomes less significant, the limiting factor is the time required for the processor to interact with memory. Faster memory would seem to be called for, but the use of high-speed memory throughout the computer is too expensive to be practical. Fortunately, the matrix multiplication program exhibits high data locality, since the elements of each of the two input arrays occupy consecutive addresses within a certain range of memory. Therefore, instead of using high-speed memory everywhere in the computer, we employ a small amount of it as a cache. At the start of the program, the input arrays from the main memory are transferred to the cache buffer. While the program executes, the processor fetches operands from the cache, and writes back corresponding results to the cache. Since data accesses use the high-speed cache, the processor is able to execute the program much faster than if it had used main memory. In fact, the use of cache results in a speed improvement nearly as great as if the entire main memory were upgraded, but at a significantly lower cost. Note that a cache system is beneficial only in situations where the assumption of data locality is justified—if the processor frequently has to go outside the cache for data, the speed advantage of the cache disappears.
Another issue connected with the use of a data cache is “cache coherency.” As described above, data are typically copied to a cache to permit faster access. Each datum in the cache is an identical copy of the original version in main memory. A problem can arise if one application within the computer accesses a variable in main memory, and another application accesses the copy in the cache. If either version of the variable is changed independently of the other, the cache loses coherency—a potentially harmful result. For example, if the variable is a pointer to critical operating system data, a fatal error may occur. To avoid this, the state of the cache must be monitored. Then, when data in the cache is modified, the “stale” copies in the main memory are temporarily invalidated until they can be updated. An important aspect of any cache-equipped system is a mechanism to maintain cache coherency.
As it turns out, web traffic is well suited to caching. As mentioned above, the majority of e-commerce Internet traffic is from the server to the user, rather than vice-versa. In most cases, the user requests information from the website, which must be culled from the website database. Relatively infrequently, the user sends information to the website, which is entered into the website database. Because often, many users request the same information, it is more convenient to cache the information at some point than to repeatedly retrieve it from the database. Caching dynamic web content can improve the responsiveness of the website without a heavy investment in servers and other hardware.
A major consideration for the suitability of caching is the frequency with which the web content changes. Caching generally becomes feasible as the access rate increases and the update rate decreases—i.e., the user frequently reads from the database, and infrequently writes to the database. If a number of users frequently request the same content, it is much more efficient to fetch it from cache
Conner Michael H.
Copeland George P.
Flurry Gregory A.
Daffer Kevin L.
International Business Machines Corp.
LaBaw, IBM Jeffery S.
P.C. Conley Rose
Portka Gary
LandOfFree
Distributed execution coordination for web caching with... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Distributed execution coordination for web caching with..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributed execution coordination for web caching with... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3318191