Methods for increasing cache capacity utilizing delta data

[00002] This application is a continuation and claims priority from U.S. application Ser. No. 09/748,552 filed on Dec. 26, 2000, now abandoned, the disclosure of which is incorporated herein by reference.

[00003] The present invention relates to methods for increasing cache capacity.

[00004] Providing data and application services to large number of concurrent clients via a server poses a number of performance and memory challenges for the server. Some of these performance and memory challenges are alleviated by utilizing relatively small amounts of volatile memory called cache. By storing small frequently accessed or recently accessed data in the cache, clients may quickly use the data in connection with an application, since access to the data are in portions of the random access memory associated with the server and are correspondingly more efficiently retrieved by the server.

[00005] If the capacity of the cache could be improved, then the server would be capable of servicing more clients, addressing the needs of high data volume clients, and more efficiently assisting process intensive client requests. Moreover, the capacity of the cache is often constrained by the hardware architecture and the operating system architecture of the server. However, modifying the hardware and operating system associated with the server is not a practical option for most data and application service providers. This is so, because the hardware and operating system are circumscribed in large part by the state of existing technology available. Therefore, as a practical matter individual software applications must be developed to improve cache capacity and performance by logically expanding the cache capacity.

[00006] Presently, with the advent of the omnipresent Internet and browser technology utilized in connection with the World Wide Web (WWW), an increasing number of clients are making demands on servers, which provide data and application services. Moreover, these servers are expected to handle thousands of concurrent requests by clients without any significant degradation in response time to these clients

[00007] Furthermore, users associated with some clients, which are utilizing the servers, are demanding much higher performance from data and application service providers. Broadband and high speed Internet connections have made the performance expectations of users extremely high, which has correspondingly placed difficult and unrealistic burdens on data and application service providers to become more efficient and more performance oriented.

[00008] Some data and application service providers have attempted to alleviate the growth pains associated with these increase demands by adding additional hardware to support the server services being provided. Yet, additional hardware entails additional maintenance and additional support which is becoming increasingly difficult to manage for the data and application service providers. More staff is required to support the additional hardware, and more software installed on the additional hardware ensures more expense associated with keeping everything in synch. Furthermore, as previously presented there reaches a point of diminishing returns at which time, the additional hardware added to the server does not increase performance but, rather, decreases performance.

[00009] Finally, as computing technology permeates all aspects of society and business, some businesses, which have never had to deal with computing technology and are corresponding ill equipt to manage that technology, are turning to data and application service providers to outsource their technology needs. This demand to outsource business computing technology has added a new layer of demand and complexity on data and application service providers, since business clients of the server demand reliable, instant, and accurate service.

[00010] Accordingly, methods which will increase cache performance are needed so that data and application services being provided to clients utilizing server technologies may support increase demands in a more efficient manner without the need to add additional hardware. Although as one skilled in the art will appreciate, cache performance of an individual computing device which is not servicing multiple clients would benefit by increased cache performance as well.

[00011] Accordingly, an object of the invention is to provide methods of increasing cache capacity. By identifying data in a cache which is an original unmodified version of that data, and by identifying all the variant forms of the original data in the cache, the differences between the variant forms and the original form of the data may be determined, and the variant data may be discarded from the cache. Discarding the variant data from the cache will free up a substantial amount of space which the cache required to house the variant data.

[00012] Moreover, should a client request or need the variant data, the differences between the variant data and the original data may be applied against the original data to reconstruct the variant data on an as needed basis. This will remove large amounts of unused variant data from the cache and make it available only when needed, and increase cache capacity and performance substantially.

[00013] Additional objectives, advantages and novel features of the invention will be set forth in the description that follows and, in part, will become apparent to those skilled in the art upon examining or practicing the invention. The objects and advantages of the invention may be realized and obtained by means of the instrumentalities and combinations particularly pointed out in the appended claims. To achieve the foregoing and other objects and in accordance with the purpose of the present invention, methods for increasing cache capacity are provided.

[00014] A method for increasing cache capacity having executable instructions is provided, comprising receiving in a cache an original data wherein access is required to one or more variants of the original data, and the variants do not reside in the cache. Furthermore, access to one or more of the variants from the cache is provided by using one or more delta data which are operable to be applied against the original data to produce the variants of the original data. The delta data reside in the cache.

[00015] Further, a method of reducing cache storage requirements having executable instructions is provided, comprising identifying an original data in the cache and locating one or more variants of the original data in the cache. Next, one or more delta data are produced by noting one or more differences between the original data and the variants. After the delta data are produced, the variants are purged from the cache.

[00016] Moreover, a method of producing derivatives from an original data having executable instructions is provided, comprising identifying an original data residing in a cache and identifying one or more variants of the original data. Further, one or more delta data are produced by recording the difference between each variant and the original data. The original data and the delta data are retained in the cache.

[00017] Still other aspects of the present invention will become apparent to those skilled in the art from the following description of an exemplary embodiment, which is by way of illustration, one of the exemplary modes contemplated for carrying out the invention. As will be realized, the invention is capable of other different and obvious aspects, all without departing from the invention. Accordingly, the drawings and descriptions are illustrative in nature and not restrictive.

[00024] The present invention provides methods for increasing cache capacity. One embodiment of the present invention is implemented in NOVELL's NetWare operating system environment providing concurrent web data and application services to clients via a web server and implemented with the Active Server Pages (ASP), Java, C, and C++ programming languages. Of course other operating systems, computing architectures, and programming languages (now known or hereafter developed) may also readily employed.

[00025] Further, another embodiment of the present invention augments existing software caching applications, such as applications developed specifically to assist in caching, for example NOVELL's Internet Caching System (ICS). ICS is an application which sits between a client and a server used by the client, and it facilitates caching for the client in connection with the server. Of course other caching applications (now known or hereafter developed) may also benefit from the present invention as well.

[00026] Data which reside in a cache may be used for a variety of purpose, for example and by way of example only, data may be viewed by a requester not having the ability to modify the data, data may be modified by a requestor, and the like. Moreover, a requestor may be an application residing on a computing device associated with the cache, an application residing remotely from the computing device associated with the cache, and the like.

[00027] As previously presented, access to data residing in cache is critical to the performance of an application requiring the data, and the more capacity that the cache has to retain data, the better performance an application will experience since access to data required by the application may be readily retrieved from the random access memory of the computing device having the data.

[00028] Moreover, in a multi-computing environment, such as by way of example only, a client-server based architecture, multiple clients may rely on a server to provide data or application services. It is also readily apparent to one skilled in the art that a single server may also be a client, and that a server may actually entail multiple computing devices. Furthermore, a single client may be associated with a user, an application, and the like. At the lowest level, accesses to a cache associated with a computing device occurs by software applications. Further, these applications are accessing the cache to retrieve references to data needed by the applications to perform some function or operation of the application.

[00029] With this context, being used for purposes of illustration only, consider FIG. 5 which depicts a schematic of original data 360, variant data 390, and delta data 420. These data may at different points in time reside in the cache associated with a computing device. Original data 360 refers to data which is unaltered, or a first version of data beginning with some initial point in time which may or may not become altered at some later point in time. If alterations occur to the original data 360, each instance of these alterations may be viewed as variant data 390, which are altered original data 360, or a subsequent version of the original data 360.

[00030] The original data 360 in FIG. 5 comprises a string of textual characters 370. Although, text characters are used for illustrative purposes in FIG. 5, it will be readily apparent to those skilled in the art that any computer readable medium data will suffice as data for purposes of the present invention, and that any computer readable medium data are capable of residing in the cache of a computing device. Variant data 390 are a derivative of the original data 360, having a single substring “variant” 410 in the variant data 390 which replaces the substring “original” 380 occurring in the original data 360.

[00031] Moreover, the differences between the original data 360 and the variant data 390 may be reflected by a delta data 420 which is operable to be read by a set of executable instructions on a computing device and applied against the original data 360 to produce the variant data 390. In this way, the delta data 420, may be retained in the cache of a computing device together with the original data 360, and the variant data may be discarded or purged freeing up significant space within the cache and thereby increasing cache capacity. Furthermore, the efficiency of accessing the cache is improved since variant data 390 are not stored in the cache.

[00032] Consider delta data 420, which depict a single example of how executable instructions may be embodied in the delta data 420, such that when these instructions are executed using the original data 360, variant data 390 is produced. In the present example, the single character “d” 430 is an indication that a delete operation is to take place on the first line “11” 440 of the original data 360. Further, the substring “original” 450 is what is to be deleted from the original data. The character “i” 460 in the delta data 420 is an indication that an insert operation is also to be performed on the original data 360 in order to generate the variant data 390. The insertion is to occur on line 1 “11” 470 with the substring “variant” 480 to be inserted before “b” 490 the substring “data” 500 which occurs in the original data 360. After executing these instructions comprising the delta data 420, the variant data 390 is produced, since all unaltered aspects of the original data 360 carry over to the generated variant data 390. In this way, variant data 390 may be recreated as needed by applying one or more delta data 420 against the original data 360.

[00033] As one skilled in the art will appreciate, the exact form of the delta data 420 may take on a variety of syntaxes without departing from the present invention, just like computing programming languages do. The syntax of the delta data 420 is presented by way of example only to demonstrate how executable instructions defining the differences between original data 360 and variant data 420 may be assembled so that when applied against the original data 360 the variant data 390 is reproduced. Moreover, delta data may include any instructions which are operable to be applied against an original data and produce a variant data.

[00034] In this way, delta data may include, by way of example only, user specific extensible stylesheets language (XSL) files which are operable to be applied against original data (e.g. extensible markup language (XML) files) to produced individualized variant data. As one skilled in the art will readily appreciate, any data which may be interpreted or applied against an original data to produce variant data may be considered delta data.

[00035] Further, the construction of the original delta data 420 may be achieved with any number of readily available software applications which compare two data files and produce a report as to the differences. The report itself may be used as the delta data 420, with a customized application written to read the report and apply it against the original data 360 to produce the variant data 390.

[00036] For example, and by way of example only, the UNIX operating system provides an operation entitled “diff” which produces a report as to the differences between two data files. This well known UNIX command also provides an option “e” where the report produced is in a script format which may be directly executed using the original data as input to produce a variant data. As one skilled in the art will readily appreciate, producing delta data are easily achieved with a variety of existing tools in the art.

[00037] By way of example only, consider a client-server based architecture in which the clients are web browsers remotely accessing the web server to acquire a specific web page housed on the server. Initially, the web page may not reside in the server's cache so the first request by a client for the web page causes the server to acquire the web page and place it in the cache. A profile of the client, or a security associated with the requested web page may require a variant version of the web page to be provided to the client, rather than the unaltered form of the web page. If this is the case, the original web page is altered and a variant web page is produced, placed in cache, and made available to the client.

[00038] After the variant page is created and placed in cache, it is noted that a variant web page now resides in the cache along with an original web page. An application may be applied to compare the original web page and the variant web page while in the cache, producing a delta data which are operable to be applied against the original web page to produce the variant web page. These delta data are stored in the server cache as well, and the variant web page is flushed out of the server cache, but the delta data remain.

[00039] Subsequently, the variant web page is again requested wherein it is determined that the variant web page does not reside in the cache, but the delta data and the original web page necessary to create the variant web page does. Therefore, the delta data and the original web page are used to create the variant web page as needed, while the variant web page need not reside in the server cache, thereby freeing up resources of the server cache to house other data needed to service additional clients and client requests.

[00040] In this way a web server, servicing a variety of concurrent clients and requests, may house a single original web page in its cache, along with one or more much smaller delta data operable to produce multiple variant web pages, wherein each variant web page may be quickly and efficiently generated from the original web page using the appropriate delta data which does reside in cache. This permits the web server to handle more requests and service more clients since the cache capacity is increased, because the delta data are much smaller compact data files then the complete variant data files.

[00041] FIG. 1 depicts a flow diagram of a method of increasing the capacity of a cache. Initially, original data are received in step 10, concurrently a request to modify the original data may occur wherein variant data are received in step 20. The original data and the variant data are then compared to one another in step 30. Comparison may occur using any number of readily available software utilities, such as by way of example only, the UNIX “diff” facility. The output of the compare in step 30, is the production of a delta data 40, which are operable to be applied against the original data to produce a variant data.

[00042] Once the delta data are created, the original data and the delta data are retained in the cache in step 50. The variant data may be removed from the cache if it was placed in the cache during the compare step 30 (not shown). Next, a request is received for variant data in step 60, wherein the delta data and the original data are acquired from the cache in step 50, and the delta data are applied against the original data in step 70, producing the requested variant data in step 80. The variant data are then sent to the requestor and are purged from the cache in step 90. As one skilled in the art will readily appreciate, management of a server cache using the method depicted in FIG. 1 permits a cache to flush itself of large amounts of data and retain only smaller more efficient delta data, this additional space will increase cache throughput and capacity.

[00043] Referring to FIG. 2, which depicts a schematic diagram of a method for increasing the cache capacity of a server. Considering, by way of example only, a server cache 100 wherein original data 110 resides and multiple delta data, such as delta data₀ 120 and delta data_N 130. Client₀ 160 makes a request to receive original data 110 in request step 170, this request is sent to a server, wherein the server checks the server cache 100 and determines that the original data 1110 are present and provides the original data to the request in step 170.

[00044] Concurrently to the request by client₀ 160, a client_N 190 makes a request of a server to receive variant date in step 180, this causes the server to check the server cache 100 wherein it is determined that delta data₀ 120 are present along with original data 110. The delta data₀ are then executed using the original data 110 to produce variant data₀ 140, which are immediately sent to client_N 190 via step 180. Next, the variant data₀ 140 are removed from the server cache 100 in step 150.

[00045] Although FIG. 2 depicts a server cache 100, which is serving multiple clients, one skilled in the art will readily appreciate that the cache may reside on a stand alone computing device, and the clients may be applications residing on the stand alone computing device. In this way, management of the cache is improved in a single computing environment as well as in a multi-computing environment, such as by way of example only in a client-server based architecture.

[00046] FIG. 3 depicts a flow diagram of a method of reducing cache storage requirements. By reducing the storage requirements of a cache, its throughput and performance may be improved as previously presented. Moreover, a cache may provide simultaneous access or concurrent access to clients or applications in step 200, wherein requests are being made to access original data or variants associated with original data.

[00047] In step 210, original data are identified. Identification of original data may occur in a variety of ways, such as by way of example only, applications which use a first data and produce a second data, detecting the production of the second data identifies the first data as original data. For example, a web page which is modified by a personal profile to produce a customized web page. Further, ad hoc software utilities may be written to periodically scan the cache for data which appear similar. As one skilled in the art will appreciate, there are a variety of ways to identify original data residing in the cache.

[00048] Once the original data are identified in the cache in step 210, the variants are located in step 230. As previously presented, these variants may be, by way of example only, customized client views, or security restricted views of original data as depicted in step 220. Next, delta data are produced in step 240 using the identified original data and the located variant data. Once delta data exist in the cache to reproduce the variant data, the variant data may be purged in step 250. Upon a request in step 260, variant data are reproduced by applying the delta data to the original data, and in step 270 the variant data are delivered to the requester.

[00049] FIG. 4 depicts a flow diagram of a method of producing derivatives from an original data. Initially, in step 280 original data are identified in a cache. Next, variant data associated with the original data are identified in step 300. Further, the variant data are compared to the original data to generate a delta data in step 290. The delta data reflect differences between the original data and the variant data, and are operable to be executed and applied against the original data to produce variant data associated with a version of the original data. Moreover, the variant data may be removed from the cache, in step 290, once the delta data has been generated.

[00050] Multiple clients may access the cache in parallel, concurrently, or simultaneously, such as client_N in step 310 where client_N is requesting access to the original unaltered data residing in the cache, which are delivered to client_N in step 340. Moreover, client₀ requests a variant form of the original data in step 320, wherein the delta data and original data are acquired and applied in step 330 to generate and deliver the variant form of the original data to client₀ in step 350.

[00051] The foregoing description of an exemplary embodiment of the invention has been presented for purposes of illustration and description. It is not intended to be exhaustive nor to limit the invention to the precise form disclosed. Many alternatives, modifications, and variations will be apparent to those skilled in the art in light of the above teaching. Accordingly, this invention is intended to embrace all alternatives, modifications, and variations that fall within the spirit and broad scope of the attached claims.