JPH1153322A - Object searching and acquiring method, search server and recording medium - Google Patents

Abstract

PROBLEM TO BE SOLVED: To enable a search server to search the objects in a sufficiently wide range with a small inquiring times by searching first its own object and then searching an object for another search server having a search key that is the same as that of the object search key when a search server searches the objects. SOLUTION: When a cache server tries to search and acquire an object, the server first searches its own information management part 1 and checks whether it caches its desired object. If the desired object is cached, the object searching and acquiring operations are over. If the desired object is not cached, a hash value calculation part 2 converts the object name into a natural number. Then an inquiry function part 3 inquires of a cache server (another cache server having the same search key as that of the object search key) corresponding to the natural number about the object and receives a reply.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION The present invention relates to a World Wide Web (W) in which cache servers are distributed over a network.
In networks that perform storage-type data transfer such as WW), various systems such as a mutual use system of cache data in a large-scale cache server network realized by coordinating a plurality of cache servers, an address resolution system using a domain name system, and the like. Related to directory services.

In the mutual use of cache data in a large-scale cache server network, a cache server corresponds to a search server, and in an address resolution system using a domain name system, a domain name system server corresponds to a search server.

For example, in a cache server, each client accesses an original server having a WWW page or the like having a target object (data, application program, etc.) via the cache server. In the cache server, the server itself, the name of the object that has been inquired about the presence or absence of possession in the past from other servers and the name of the server that made the inquiry
The name of the object and the name of the server that sent the notification in the past from other servers are handled as cache data.

When a certain client accesses an original server such as a certain WWW server through a cache server and transfers data from the cache server to the client, the cache server caches the object. When another client requests the same object, the cache server forwards the already cached object to the client instead of the original server object. This speeds up browsing of the client's WWW page and the like by using the cache server in the network.

However, in many cases, since the cache server is used alone, if the object requested by the client is not cached in the cache server accessed first, another cache server that can download the object at high speed is used. However, even if it is cached, it cannot be used, and it will directly access the original server that has the original object. If it takes time to access the original server due to the network configuration and status, if the cache hit rate in the cache server is low, it takes time to acquire the requested object.

Accordingly, if a plurality of cache servers can cooperate to specify a server at which an object is cached at a high speed, the server selects a server from which a client can obtain the object at a high speed, and selects a server therefrom. Data transfer can be performed.
In this way, faster browsing can be expected for the client. Also, if the cache data of other cache servers can be used, the cache hit rate will improve, and the larger the cache server network, the larger the cache hit rate.
The effect can be expected to increase.

As a technique for coordinating a plurality of search servers, there is a technique conventionally implemented in a cache server network. As a cache server network for coordinating a plurality of cache servers, there is a system (for example, skid) for inquiring another cache server about the existence of a cached object when accessed by a client. In this system, a cache server directly inquired by a client makes an inquiry to all cache servers existing in a cache server network. The cache server that has received the inquiry replies to the cache server that has made the inquiry whether or not the target object is cached. If the cache server that has cached the target object is found, the cache server that has received the inquiry directly from the client requests the cache server that has cached the object to transfer the object.

Further, in a system for inquiring about the existence of a cached object, a server stores a history of inquiries, and the next time an inquiry is received from another server, an object held by the server itself is displayed. In some cases, the server that holds the object is specified from the object name in the history (see Japanese Patent Application No. 9-31874). In this case, in order to increase the cache hit rate, it is necessary to inquire the number of cache servers corresponding to the total number of cache servers.

When a plurality of search servers do not cooperate, if the search server does not hold the requested object, the search server accesses the master server every time an object is requested. And the data transfer rate may be reduced. Further, even when the object is held in another search server that can acquire the object at a higher speed than the master server, the search server cannot be found unless the search servers cooperate. Therefore, the master server is always accessed, and the data transfer speed is reduced.

[0010] Further, in the system for inquiring other search servers in the prior art, there is a problem that the number of inquiries between search servers increases as the size increases. If the number of inquiries increases, the control traffic increases, and further, the search processing in each search server increases, and the server load also increases. Therefore, it is difficult to efficiently use a large number of search servers.

[0011]

SUMMARY OF THE INVENTION It is an object of the present invention to provide a system for obtaining and searching an object which can search a sufficient range with a small number of queries when searching for an object in cooperation with a search server. Is to do.

[0012]

According to the object search and acquisition method of the present invention, in order to achieve the above object, each search server has (1) its own server name and its own search key, and (2) its own Object name of the object to be searched, (3) the name of the object that was previously inquired by other search servers about the existence of
(4) Each server has four types of information including the server names of all search servers other than itself and their search keys, and each search server has (a) an inquiry function, (b) a response function to an inquiry, and (c) The search server has three functions of uniquely converting an object name into a search key. When the search server searches for an object, first the object held by itself, and then the search key that matches the search key of the object are searched. The search is performed with respect to another search server having the object, and if the object cannot be obtained in these steps, the object is obtained from the master server.

[0013] In another object search and acquisition method of the present invention, each search server comprises: (1) its own server name and its own search key; (2) the object name of its own object; (4) Object names and notifications for which search information has been received in the past from the search server and the query source search server name, and The original search server name, and (5) the server name of all search servers other than the self and the five types of information of their search key, further, each search server, (a) query function,
(b) response to inquiries, (c) notification, and
(d) Equipped with four functions of a function of uniquely converting an object name into a search key, and when the search server searches for an object, first receives the object owned by itself, and then receives and deletes the notification of possession in the past. Search for other search servers that have not received the notification of, and then search for other search servers that have a search key that matches the search key of the object.If these objects cannot be obtained in these steps, The method is characterized in that an object is obtained from a master server.

In such a method of the present invention, all search keys equal to or less than the number of search servers are assigned to all search servers. That is, the same search key may be assigned to a plurality of search servers, but all search keys are assigned to at least one search server. It is desirable that each search server has a correspondence table between each search server and a search key assigned thereto.

On the other hand, a search key is also given to the object. When the search server tries to find an object, the search server converts the object name into a search key and inquires the search server to which the search key is assigned. Since the search server receiving the inquiry records the inquiry history of the object having the search key, the search server holding the object is returned as to the object which has been previously inquired. be able to.

In the method of the present invention, which search server has the object or which search server has the minimum number of queries (2 times or less) without depending on the total number of search servers. Since the search server can also recognize whether or not the object is possessed, economies of scale can be expected. Therefore, a large number of cache servers can be efficiently used with a small number of queries.

By making the search server correspond to the cache server and the master server to correspond to the original server, when the method of the present invention is applied to a cache server network, a large number of cache servers can be efficiently used with a small number of queries. become. In fact, in the conventional method, the number of inquiries to determine whether there is a cache server holding a cache increases as the number of all cache servers increases,
According to the method of the present invention, the minimum number of queries (2 or less) is always required without depending on the total number of cache servers at all. Therefore, economies of scale can be expected. Also, it is possible to easily cope with the dynamic addition of a cache server by allocating an appropriate search key and rewriting the correspondence tables between the cache servers and their search keys in all the cache servers.

[0018]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS Next, embodiments of the present invention will be described with reference to the drawings.

[First Embodiment] FIG. 1 is a diagram showing a first embodiment of the configuration of a cache server. The information management unit 1
(1) its own server name and its own search key; (2) the object name of its own object; and (3) the object name and inquiry source cache server that has received an inquiry from another cache server in the past whether or not it owns it. Name,
And (4) manages the four information of the server names of all the cache servers other than the self and their search keys. These pieces of information are treated as a cache (temporary storage). These pieces of information are stored in a recording medium.

The hash value calculation unit 2 converts an object name into a natural number using a hash function. As a hash function, for example, each alphabetic character is made to correspond to a natural number, the alphabetic characters are converted into natural numbers sequentially from the beginning of the object name, the sum is obtained, and the remainder is divided by the number of search keys of all cache servers. May be made to correspond to the object name. In this way, each object name corresponds to a natural number from 1 to the number of search keys of all cache servers, and each object always corresponds to one or more cache servers.

In order to find an object, the query function unit 3 determines whether or not the cache of the object is provided to the cache server to which the same natural number as the natural number obtained by converting the object name by the hash value calculation unit 2 is assigned. Alternatively, the cache server is inquired about the name of the cache server that caches the object, and if there is a response that the object is cached, the object is downloaded and cached by the cache server itself.

When receiving a query from another cache server (server name S0), the response function unit 4 for the query (A) caches the queried object in information held by the cache server itself. If so, reply [caches the object], and (B) In the information cached by the cache server itself, another cache server that has inquired about the queried object in the past. If (server name S2) is recorded, the cache server S0 is replied to the cache server S2 by saying [inquire the cache server S2 again (inquire again)],
(C) If none of (A) and (B) above apply,
(The existence of the cache server that caches the object is unknown.) (D) Subsequently, the object name and the cache server name S0 of the inquiry source are recorded as cache information.

FIG. 2 is a diagram showing a configuration example of a cache server network when the present invention is implemented. The cache servers S0, S1, and S2 are cache servers each having a function of searching for and obtaining an object. Although FIG. 2 shows three cache servers,
There is no limit on the number. On the other hand, the master server is a server that holds all objects.

Next, an operation for making an inquiry and a response operation for receiving an inquiry will be described. FIG.
Is a flow chart for making an inquiry, and the operation when the cache server S0 attempts to search for and obtain the object Obj will be described with reference to FIG. Server S0
First searches its own information management unit 1 and checks whether the object Obj to be found is cached (step 11). When the object is cached, the operation of searching for and obtaining the object ends. If not cached, the hash value calculator 2 converts the object name Obj to a natural number K (step 12). Next, the inquiry function unit 3 makes an inquiry about the object Obj to the cache server corresponding to the natural number K (step 13), and receives the response.

The following operation is performed based on the response. (Case A) From the cache server S1 [the cache server S1 caches the object Obj]
(Step 14), the cache server S0 sends the object O from the cache server S1.
bj is acquired, this is cached, the fact that it is cached is recorded in the information management unit 1, and the process ends (step 1).
Five).

(Case B) From the cache server S 1,
If there is a response that "the cache server S2 has cached the object Obj" (step 14),
The cache server S0 makes an inquiry (re-inquiry) to the cache server S2 (step 16). When the cache server S2 responds [caches the object Obj] (step 17), it obtains the object Obj from the cache server S2, caches it, and caches it in the information management unit 1. The recording is completed and the processing is terminated (step 18). Cache server S
If the object Obj is not cached from Step 2 (step 17), the object Obj is obtained from the master server, cached, and the information management unit 1 records that it is cached. The process ends (step 19).

(Case C) From the cache server S 1,
If there is a response that "the existence of the object Obj is unknown" (step 14), the object Obj is obtained from the master server, cached, recorded as being cached in the information management unit 1, and terminated. (Step 1
9).

FIG. 4 is a flow chart in the case of receiving an inquiry, and the response operation when the cache server S1 receives an inquiry about the object Obj from the cache server S0 will be described with reference to FIG. When the cache server S1 receives an inquiry from the cache server S0, it first searches its own information management unit 1 and checks whether or not the object Obj inquired is cached (step 21). If cached, reply [cached] (step 22),
The fact that an inquiry about the object Obj is received from the cache server S0 is recorded in the information management unit 1 as cache data (step 23), and the process is terminated.

If the object Obj is not cached, it is checked whether the inquiry is a re-query (step 24). If the query is a re-query, a response is returned (not cached) (step 25), and the process ends. As a result of the check (step 24), if this inquiry is the first inquiry, the information management unit 1 is searched to check whether or not there is a cache server that has inquired about the object Obj in the past (step 26). . If it exists, it responds to the cache server S0 that [the cache server S2 has made an inquiry in the past] (step 27), and sends the cache server S0 of the inquiry source and the object name of the object Obj to the information management unit 1 as cache data. Record (step 28) and end.

On the other hand, if there is no cache server inquiring about the object Obj in the past,
Reply to the cache server S0 [unknown existence of server caching object Obj] (step 2)
9) The cache server S0 of the inquiry source and the object name of the object Obj are recorded as cache data in the information management unit 1 (step 30), and the process ends.

[Embodiment 2] FIG. 5 is a diagram showing a second embodiment of the configuration of the cache server. The information management unit 1
(1) its own server name and its own search key; (2) the object name of its own object; and (3) an object that has received an inquiry from another cache server in the past as to whether or not it is owned and has not been notified of deletion. Name and cache server name of the query source; (4) object name and notification source cache server name that have been notified from other cache servers that they have been held in the past and have not been notified of deletion; and (5) other than their own Manages the server names of all cache servers and their search keys.
These pieces of information are treated as a cache (temporary storage). These pieces of information are stored in a recording medium.

[0032] Hash value calculation unit 2, inquiry function unit 3
The response function unit 4 responds to the inquiry in the same manner as in the first embodiment. When the cache server caches an object or deletes the cache, the notification function unit 5 sends the object name to all the cache servers that hold the same hash value as the converted hash value. Notifies that the object has been cached or deleted.

Next, an operation for making an inquiry and a response operation for receiving an inquiry will be described. FIG.
And 7 are flow charts in the case of making an inquiry, with reference to which the operation when the cache server S0 seeks and obtains the object Obj will be described. The server S0 first searches its own information management unit 1 and checks whether the object Obj to be found is cached (step 41). When the object is cached, the operation of searching for and obtaining the object ends.

If the cache has not been cached, it is determined whether or not there is a cache server that has been queried in the past or a cache server that has not been notified that the object Obj has been cached. The information is checked by the information management unit 1 (step 42). If they exist, their cache servers S
2 is selected, and an inquiry is made for the object Obj (step 43). Cache server S2
If the response is that the object Obj is cached (step 44), the object Obj is obtained from the cache server S2 and cached, and the fact that the object Obj is cached is recorded in its own information management unit 1. (Step 45). If the cache server S2 responds that the object Obj has not been cached (step 44), it is determined that the object Obj is acquired from the master server and cached, and that the object Obj is cached in its own information management unit 1. Record (step 46). Subsequently, the cache server to which a natural number corresponding to the converted natural number K is assigned to the object Obj is notified that the object Obj is cached (step 47). When the cache of the object Obj is deleted, the cache server to which a natural number corresponding to the converted natural number K of the object Obj is assigned is notified that the cache of the object Obj is to be deleted.

On the other hand, if there is no cache server that has been inquired in the past or that has been cached in the past and has not been notified that the object Obj has been deleted (step 4).
2) Perform the following. That is, the hash value calculation unit 2 converts the object name Obj into a natural number K (step 48), and then the inquiry function unit 3 makes an inquiry about the object Obj to the cache server corresponding to the natural number K (step 48). 49), receive the response.

The following operation is performed based on the response. (Case A) From the cache server S1 [the cache server S1 caches the object Obj]
(Step 50), the cache server S0 sends the object O from the cache server S1.
bj is acquired, cached, and the fact that it is cached is recorded in the information management unit 1 (step 51).

(Case B) From the cache server S 1,
If there is a response that "the cache server S2 is caching the object Obj" (step 50),
The cache server S0 makes an inquiry to the cache server S2 (re-query) (step 52). When the cache server S2 responds [caches the object Obj] (step 53), it is determined that the object Obj is acquired from the cache server S2, cached, and cached in the information management unit 1. Record (step 54). When the cache server S2 responds [not cache the object Obj] (step 53), it acquires the object Obj from the master server, caches it, and records that it is cached in the information management unit 1. (Step 55).

(Case C) From the cache server S 1,
If there is a response of [the existence of the object Obj is unknown] (step 50), the object Obj is acquired from the master server, cached, and the fact that it is cached in the information management unit 1 is recorded (step 50). 55).

In all cases, when the cache server S0 caches the object Obj,
The cache server to which a natural number that matches the converted natural number K of the object name Obj of the object Obj is notified that the object Obj is cached (step 56). When the cache of the object Obj is deleted, the object Obj is sent to the cache server to which a natural number corresponding to the converted natural number K is added to the object name Obj of the object Obj.
Notify to clear cache (Step 5
7).

FIG. 8 is a flow chart when an inquiry is received. Using this, the response operation when the cache server S1 receives an inquiry about the object Obj from the cache server S0 will be described. When the cache server S1 receives an inquiry from the server S0,
First, it searches its own information management unit 1 to check whether the object Obj for which the inquiry has been made is cached (step 61). If cached, the response is "cached" (step 62), and the information management unit 1
Then, the fact that an inquiry about the object Obj has been received from the cache server S0 is recorded as cache data (step 63), and the process is terminated.

If the object Obj has not been cached, the cache server that has been queried in the past or the cache server that has been notified in the past that has cached the object Obj has not notified that the object Obj has been deleted. Information management unit 1 whether or not it exists
Is checked (step 64). If so, the cache server S2 responds to the cache server S0 (step 65), and the information management unit 1
The fact that an inquiry about the object Obj has been received from 0 is recorded as cache data (step 66), and the process ends.

On the other hand, regarding the object Obj, it is determined that there is no cache server that has been queried in the past or notified that the object has been cached, or that the object Obj has been deleted among the cache servers that have been notified that the object Obj has been cached. If there is no one that has not been notified, a response is sent to the cache server S0 [the existence of the server that caches the object Obj is unknown] (step 67), and the object names of the cache server S0 and the object Obj of the inquiry source are entered. The data is recorded as cache data in the information management unit 1 (step 68), and the process ends.

Next, the operation of the cache server notified that the object Obj is cached will be described.
The cache server notified that the object Obj is cached records the notified cache server name and the object name of the object Obj in the information management unit 1 as cache data. When notified that the object Obj is to be deleted, the cache data that the notification source cache server has cached the object Obj is deleted.

[0044]

According to the present invention, when a certain search server wants to obtain a certain object, it can make an inquiry to another appropriate search server, thereby making it possible to obtain the desired number of queries without depending on the total number of cache servers. Objects can be found. Furthermore, it can be expected that the processing load on the search server is also small due to the small number of inquiries. Therefore, as described above, according to the present invention, a scalable object search and acquisition method can be realized.

[Brief description of the drawings]

FIG. 1 is a diagram showing a first embodiment of a configuration of a cache server of the present invention.

FIG. 2 is a diagram illustrating a configuration example of a cache server network when implementing the present invention.

FIG. 3 is a flowchart of an operation when making an inquiry in the first embodiment.

FIG. 4 is a flowchart of an operation when an inquiry is received in the first embodiment.

FIG. 5 is a diagram showing a second embodiment of the configuration of the cache server of the present invention.

FIG. 6 is a flowchart of an operation when making an inquiry in the second embodiment.

FIG. 7 is a flowchart of an operation when making an inquiry in the second embodiment.

FIG. 8 is a flowchart of an operation when an inquiry is received in the second embodiment.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 Information management part 2 Hash value calculation part 3 Inquiry function part 4 Response function part to inquiry 5 Notification function part

Claims (6)

[Claims] A search server having a function of holding a plurality of objects and a function of finding an object by inquiring another server, and a master server holding all objects are connected by a communication network. In a large-scale distributed server network, the search and retrieval method for each object is as follows: (1) its own server name and its own search key, (2) the object name of its own object, (3) other It has four types of information: the name of the object that has been previously inquired from the search server and the name of the search server from which it was queried, and (4) the server names of all search servers other than itself and their search keys. , Each search server has (a) an inquiry function, (b) a response function to an inquiry, and (c) an object. The search server has three types of functions that uniquely convert a name into a search key. When a search server searches for an object, it first has its own object, and then has a search key that matches the search key of the object. A search server, and if the object cannot be obtained in these steps, the object is obtained from the master server. 2. A search server having a function of holding a plurality of objects and a function of finding an object by querying another server, and a master server holding all objects are connected by a communication network. In a large-scale distributed server network, the search and retrieval method for each object is as follows: (1) its own server name and its own search key, (2) the object name of its own object, (3) other Object name and query source search server name that have been previously inquired by the search server for the presence or absence, and (4) Object names and notification sources that have been previously notified of possession from other search servers and have not been notified of deletion. Search server name, and (5) Server names of all search servers other than self and their search key 5 Each search server has (a) an inquiry function, (b) a response function to an inquiry, (c) a notification function, and (d) a function of uniquely converting an object name into a search key. When the search server searches for an object, the search server first searches for an object held by itself, and then searches for another search server that has received notification of the object holding in the past and has not received notification of deletion. Next, a search is performed on another search server having a search key that matches the search key of the object, and if the object cannot be obtained in these steps, the object is obtained from the master server. Search acquisition method. 3. The search server: (1) own server name and own search key; (2) object name of an object held by the search server; and (3) inquiry about presence / absence of possession in the past from another search server. It has four types of information: the received object name and the query source search server name, and (4) the server names of all search servers other than itself and their search keys, and (a) a query function, (b) a query And (c) a function of uniquely converting an object name into a search key. 4. The search server: (1) own server name and own search key, (2) object name of an object held by itself, and (3) inquiry from another search server about presence / absence of possession in the past. (4) Object name and notification source search server name that have received notification of possession from other search servers in the past and have not received notification of deletion, and (5) Other than self It has five types of information, the server names of all search servers and their search keys. Furthermore, (a) the query function, (b) the response function to the query, (c) the notification function, and (d) the object name are unique. A search server comprising four types of functions of converting a search key into a search key. 5. A recording medium comprising: (1) its own server name and its own search key; (2) the object name of its own object; and (3) an inquiry from another search server as to whether or not it has been held in the past. (4) A storage medium storing four types of information of the received object name and the query source search server name, and (4) the server names of all search servers other than the self and the search keys thereof. 6. A recording medium comprising: (1) its own server name and its own search key; (2) the object name of an object held by itself; and (3) an inquiry from another search server as to whether or not it has been held in the past. (4) Object name and notification source search server name that have received notification of possession from other search servers in the past and have not received notification of deletion, and (5) Other than self A recording medium storing five types of information of server names of all search servers and their search keys.