The present invention relates to a computer system, and more particularly to a method and system for managing distributed data, suitable particularly for the world wide web (WWW), in which a plurality of computers interconnected by a network distribute, share and exchange data in an information system.
First, several terms used in the following description will be explained.
An information system such as WWW and anonymous FTP on the Internet is configured as a "client-server system" which is one type of distributed computer systems. In the client-server system, the processes in the whole system are classified into two parts. The first part is executed by a program (hereinafter called a process) called a "server", and the second part is executed by processes called "clients". A client in the information system generally runs on a computer operated by a home user or a company user. The server in the information system stores information to be supplied to clients. The client in the information system stores new information in the server or requests information from the server.
It is common in a computer system that the same information is temporarily copied to a plurality of sites in order to access the information at high speed or increase a possibility of accessibility. Such a copy is discriminably called hint, cache, replica, stash and the like (refer to a document "Distributed Systems (1st ed.) compiled by Sape Mullender, pp. 13-15, ACM press, 1989). In the following, these copies are collectively called a "cache". To make a cache is called "cache".
A WWW server in WWW stores information to be serviced, in a unit called a "home page". Each home page has a name called URL (abbreviation for uniform resource locator). URL is a character string capable of designating a protocol used in WWW, a host name of a computer as an information source, and specific data in the information source. For example, "http://www.hitachi.co.jp/index.html" is a URL.
Generally, each URL is in correspondence with a collection of data including character and image data of a home page. In the following, a collection of such data is called "URL corresponding information" or "URL contents". A second URL contained in the first URL corresponding information is called a "hyper text link (or simply link)". That the first URL corresponding information contains a second URL is hereinafter described as "there is a link from the first URL to the second URL".
The techniques (hereinafter called prior example 1) used by WWW will be explained in the following.
A user of a WWW client supplies a URL of the home page to be accessed, to the WWW server. In the first process type between a WWW server and client, the WWW client requests the WWW server designated by the second element of URL to transmit the home page of URL. In response to this request, the WWW server supplies the home page to the WWW client.
In the second process type, instead of requesting the WWW server designated by the second element of URL supplied from the user, the WWW client requests a second server called a "proxy server" to transmit the home page. The second server acquires the home page of URL from the first WWW server or requests another proxy server to acquire the URL corresponding information. At the repetitive stage of proxy server requests, these proxy servers have parent-child relationships. Proxy servers having a parent-child relationship are described, for example, in a document "A Hierarchical Internet Object Cache" by A. Chankhunthod, et.al., 1996 USENIX Technical Conference, pp. 153-163, 1996.
A WWW client and proxy server can have caches. A cache of a client stores home pages the client acquired in the past, and can be used only by this client. A cache of a proxy server stores home pages acquired by the proxy server in response to a request from one or more clients, a request from another or more other servers, or a request from both, and can be shared by the clients using this proxy server or by this proxy server itself.
The Network News System (hereinafter called prior example 2) is described, for example, in a document "Network News Transfer Protocol: A proposed Standard for the Stream-Based Transmission of News" by B. Kantor, et.al., Network Working Group RFC-977. This system is configured by one or more servers. Generally, a user selects one of the servers by using its client. The information unit in the Network News System is called "news". Generally, a user supplies news to the server by using its client, and acquires news from the server. As the user supplies news to a first server, the first server sends a copy of the news to a second server, and the second server supplies a copy of the news to another server, and so on. Finally, the copy of the news is supplied to all the servers.
Next, the global area name service, Domain Name System (hereinafter called prior example 3, abbreviated as DNS) will be explained. DNS is described, for example, in a document "Domain Names-Implementation and Specification" by P. Mockapetris, Network Working Group RFC-1035, particularly in the second section thereof. DNS has a correspondence mainly between a symbolic host name and host related information (IP address and mail address). A plurality of DNS servers have a tree structure. A request from a client is processed by tracing the tree structure and transferring the request to a plurality of servers. A resolver which is a DNS client requests the host related information corresponding to a host name to one of the servers. This server returns the host related information corresponding to the host name back to the client, or transfers the request to a parent server of this server (a DNS server nearer to the root of the DSN server tree structure from this server). The parent server grasps which of its child servers have what host related information. Therefore, after the request is transferred to the root of the tree structure, the request is then transferred downward the tree structure to the DNS server capable of processing the request. The request finally reaches the DNS server having the host related information from which the host related information is returned to the client, or alternatively a failure is returned back to the client if every DNS server cannot supply the host related information corresponding to the host name while the request is transferred downward the tree structure.
A method (hereinafter called prior example 4) is also known in which a space of caches is shared by a plurality of computers in a distributed file system of a local area network (LAN). According to a document "Cooperative Caching: Using Remote Client Memory to Improve File System Performance" by Michael Dahlin, et.al., First USENIX Symposium on Operating Systems Design and Implementation, pp. 267-280, 1994, a client first requests for a file block to a server called a "manager". The manager grasps which file block is stored in what computer. The manager informs the client of the computer which stores the file block, or transfers the request of the client to the computer. Similar methods are known as described in a document "Implementing Global Memory Management in an Workstation Cluster" by M. J. Feeley, et.al., ACM 15th Symposium on Operating Systems Principles, pp. 201-212, 1995, or in a document "Efficient Cooperative Caching Using Hints" by P. Sarkar, et.al., Second USENIX Symposium on Operating Systems Design and Implementation, pp. 35-46, 1996. A plurality of managers can be provided. However, a correspondence between file blocks and managers is prefixed and is known by all clients and servers. This correspondence does not change during system running.
Techniques used by computers called cache-coherent non-uniform memory access (CC-NUMA) and cache only memory access (COMA) will be explained by using following prior examples 5 and 6. The CC-NUMA computer or COMA computer has a mechanism of maintaining coherency between memory fragments (cache lines) cached near at a number of processors. The following two methods are known in particular.
With the first method (hereinafter called prior example 5), a processor or data called a "home" corresponding to the "manager" grasps which memory fragment is cached to what processor. This first method is used in a system described, for example, in a document "The Stanford FLASH Multiprocessor" by Jeffrey Kuskin, et.al., Proceedings of the 21th Annual International Symposium on Computer Architecture, pp. 302-314, ACM, 1994.
With the second embodiment (hereinafter called prior example 6), some restrictions are imposed on the formation, deletion and communications of caches, to thereby ensure identification and coherence of caches during a predetermined number of communications (generally including multicast or broadcast). This second method is used in a system described, for example, in a document "The Data Diffusion Machine with a Scalable Point-to-Point Network" by Henk L. Muller, et.al., Technical Report CSTR-93-17, Department of Computer Science, University of Bristol, October 1993.
The current communications performance of the Internet is much more slower than the speed users desire, and has various unstable factors. Because of rocketing spread of the WWW, a number of wide area networks (WAN) are congested. While high speed backbone communications lines are being increased and enhanced day after day, users at homes connect to the Internet via communication lines much slower than a general LAN. The number of users of WWW servers and the Internet is increasing even at present. According to certain statistics as of January 1996, the number of computers connecting the Internet in the world is nine million, and increasing by twofold in less than six months.
These circumstances make Internet communications lines irregular and unstable. "Irregular" means congestions of various communications lines. For example, each communications line has a different throughput (communications data amount per unit time) and a different latency (communications delay time). "Unstable" means that the throughput and latency of a communications line change from time to time and at worst the communications becomes impossible. For example, the congestion degree of a communications line changes with a time zone and a day of the week, or a routing pattern changes because of some enhanced communications line so that another communications line becomes congested or becomes free of congestion.
Under such circumstances, it is required to shorten the time from when a user issues a request to a client to when the request is satisfied, in order for the information system to provide services more comfortable to users. The following issues (1) to (5) regarding such user requirements will be explained.
(1) Under the conditions that some communications line is unstable, a client request may not be processed at high speed even if another communications line operates normally.
A WWW client and a WWW proxy server of the prior example 1 communicate with a specific WWW server and a specific proxy server designated by URLs. Therefore, if the communications line to the server (or proxy server) is congested or interrupted, it takes a long time for the client (or proxy server) to access a home page, or the home page cannot be accessed, even if another communications line operates normally. From the same reasons, even if some communications line is enhanced to have a high speed, it has been difficult to enjoy the high performance of this line. These problems are also true for the prior example 2 to 5, because communications between a client and a server or between a server and another server is performed by prefixed partners, similar to the prior example 1. The prior example 6 pertains to the techniques to be used by a single computer or by a plurality of computers physically in tight contact with each other, in which multicast or broadcast is assumed to be normally operative. Therefore, it is difficult to widely apply these techniques to the LAN and WAN environments. From the same reasons, if a particular communications line is congested or interrupted, it takes a long time to obtain a cache line or the cache line cannot be obtained, even if another communications line operates normally.
(2) A usage factor of caches cannot be improved under the unstable state of communications lines.
In the prior examples 1, 2, 3 and 5, a plurality of caches at a plurality of servers (or clients and servers) have a hierarchical structure. A request issued by a client is processed by a specific first server responsible for this process. This request is either directly transmitted to the first server or sequentially transferred to one or more second servers present between the first server and the client (in this case, one or more second servers are determined definitely in accordance with the contents of the request). In the former case, the request can use the cache of only the first server. In the latter case, the request can use only cache or caches of one or more second servers. Namely, the request cannot use caches of servers other than the first and second servers so that the usage factor of caches is small. For example, in the prior example 1, WWW proxy servers have a parent-child relationship. It is assumed here that there are three proxy servers A, B and C, the server A being a parent and the servers B and C being children of the server A. In this case, although B can use the cache of A by transferring a request to A, B cannot use the cache of C. In the prior example 2, each news is copied to all servers requesting it. Therefore, each child server does not use at all the cache of another child server so that each child server is required to prepare a large scale secondary memory. The prior example 4 assumes the LAN environment in which in order to improve the usage factor of caches, it is controlled to make copies of one data set be as small as in a plurality of caches. However, if a communications line is unstable, a client request may not reach such a small number of caches, resulting in a low cache usage factor. In the prior example 6, of a plurality of caches, a cache which can be acquired in shortest time is selected. For this selection, multicast or broadcast is performed. Therefore, this technique is difficult to be widely applied to the LAN and WAN environments whose communications lines may become unstable.
(3) A method of exchanging among a plurality of servers a use frequency of data reference relationships, has not been applied.
As typical in WWW home pages and hyper text links, data provided by an information system has reference relationships. Of these reference relationships, there is in many cases a reference relationship frequently accessed (reference relationship having a high use frequency). This use frequency of reference relationships can be used for prefetch. If a series of information linked by reference relationships frequently accessed is prefetched before a client issues a request, this series of information can be processed at high speed when a client issues a request, even if communications lines are congested. If there are a plurality of servers, information on the use frequency of reference relationships can be made more reliable if a plurality of servers collect and exchange the information and summarize it, than if the information is collected independently by each server. However, the prior examples 1 to 6 have not the method of exchanging among a plurality of servers a use frequency of data reference relationships. Therefore, reliability of the information on a use frequency of reference relationships is limited and the effect of prefetch is also limited.
(4) It has been a possibility of discarding an important cache when caches are replaced, because irregular and unstable communications lines have not been taken into consideration.
In the prior examples 1, 2 and 3, each server (or client) replaces caches by referring to a use history or the like. Since the prior example 4 assumes the LAN environment, the states of communications lines are not taken into consideration when the priority level of caches is determined to replace them. The prior examples 5 and 6 also assume one computer or a plurality of computers physically in tight contact with each other. Therefore, the states of communications lines are not taken into consideration when the priority level of caches is determined to replace them. In all the prior examples 1 to 6, therefore, a cache unable to be obtained under the current communications conditions or a cache taking a long time to obtain, may be discarded.
(5) While a first server accepts a request from one or more second servers, if the second servers use the first server limitlessly, the first server may be overloaded. A countermeasure for this has not been applied to the prior examples 1 to 6. It is therefore difficult for a plurality of servers to pass requests from users other than a predetermined society of a plurality of users. In the prior examples 1, 2 and 3, since the client-server system is adopted, if the server rejects a client request, this request cannot be processed. In the prior examples 4, 5 and 6, since servers of a limited number pass requests, an overload of the first server does not become a problem.