JPH047652A - Distributed data controller - Google Patents

Abstract

PURPOSE:To hold wasteful data communication to a minimum by holding data accessed from other node or a self node by providing priority predicting the prospects based on a past accessing trend. CONSTITUTION:A distributed data control system 1 consists of an access requirement analyzing means 11, a requirement staging means 12, an LRU data substitution means 13, an MRU data substitution means 14, an accessing history holding means 15, an accessing trend monitoring means 16, a substitution method justification means 17 and an accessing data returning means 18. When data obtained from the other node is fetched into its own node based on an accessing requirement where the application program 2 of its own node is issued on a computer network, an LRU data substitution method and an MRU data substitution method are appropriately used in accordance with adaptiveness as against a practical system. Thus, an optimum data substitution algorithm becomes approximation much more satisfactorily, and wasteful data communication can be held to a minimum.

Description

[Detailed Description of the Invention] [Industrial Application Field] The present invention provides a data item with arbitrary granularity having a unique identifier, and the data aggregate existing in copies and distributed over a computer network. It can be used for distributed data systems that allow for In particular, in response to a data access request from an application program, if the corresponding data exists in the own node, that data is returned, and if it does not exist, the data obtained from another node is returned, and the accessed data is based on past access trends. The present invention relates to a distributed data control device that maintains within its own node a priority that predicts future prospects based on.

〔overview〕

In a distributed data system in which data aggregates exist in a distributed manner over a computer network, the present invention provides a priority system that predicts the future potential of data accessed from a node and its own node based on past access trends. By providing and maintaining the data, wasteful data communication can be minimized.

[Conventional technology]

Conventionally, this type of distributed data control device has been limited to providing an application program with a means to obtain data that does not exist on its own node from another node via a combinator network transparently over the network. After the data obtained from the application program was passed to the application program, it was left to the application program's own management. On the other hand, there are systems that have a mechanism to cache data from other nodes, but even if you change the entire data population or manage it by dividing it into necessary units, the limited capacity of the own node The retention priority within is uniquely determined,
For ease of implementation, a FIFO replacement algorithm that replaces data in the order of accesses and an LRU replacement algorithm that replaces data in the order of oldest accesses (newer is more effective for the same data) have been used alone.

[Problem to be solved by the invention]

If such a conventional distributed data control device is not equipped with a cache means, the distributed data management system of its own node will forget the data accessed in the past unless the application program independently manages the access data. Therefore, for each data access request issued by an application program, a data acquisition request must be issued to another device to perform data communication even for data that has already been accessed.

Furthermore, even if a cache is provided, a method that stores the entire population containing the data may not function satisfactorily due to the limitations of the data storage capacity of its own node, and unnecessary data that will never be accessed may There are drawbacks such as the waste of data communication and the need to reflect updates to mask data on unnecessary data that will never be accessed.

Next, the above problems can be solved if caching is implemented that performs data replacement at the necessary granularity, but FI
The FO replacement method does not take full advantage of the locality of data access that application programs have (the property that what has been used often in the past will be used often in the future, and what was used earlier will also be used next time). In addition, although the LRU replacement method reflects the locality of data access relatively well, it is not suitable for uniform use, and the predictions can be greatly deviated due to the behavior of the application program, resulting in poor cache hit ratio. There are possible drawbacks.

The present invention aims to eliminate such drawbacks and to provide a distributed data control device that can minimize wasteful data communication.

[Means to solve the problem]

The present invention is included in each of a plurality of nodes having a distributed database, and when first data corresponding to request data of an application program of the own node exists in the own node, this first data is acquired and the data is sent to the own node. In a distributed data control device, the distributed data control device is equipped with a request staging means for requesting another node to obtain second data corresponding to the requested data when the data does not exist, and an access history holding means for holding the first data in access chronological order. , an LRU data replacement means that refers to the access time series and replaces the oldest accessed data when the amount of data added to the second data as the first data exceeds a specified capacity; and the LRU data replacement means an MRU data replacement means that replaces the latest data with the latest data; an access trend monitoring means that records the section access frequency; and a data replacement means that performs switching according to the result of comparing the section access frequency with a reference value. The present invention is characterized by comprising a replacement method optimization means.

[Effect]

Replaced as a countermeasure to limit the data storage capacity of the own node and improve the efficiency of updating information reflection when importing data obtained from other nodes to the own node based on access requests issued by the application program of the own node on the Combi Coater network. In order to select unnecessary data from the required data, corrections are made by using the LRU data replacement method and MRU data replacement method depending on their suitability for the actual system, and by adopting data retention priority specification by the application program. .

This provides a better approximation to the optimal data replacement algorithm.

〔Example〕

An embodiment of the present invention will be described below with reference to the drawings.

FIG. 1 is a block diagram showing the configuration of this embodiment.

FIG. 2 is a structural diagram of a distributed database. FIG. 3 is a flowchart showing the operations of the access trend monitoring means and the replacement method optimization means.

First, the configuration of this embodiment will be explained based on FIGS. 1 and 2. This embodiment consists of a distributed data management system 1, an application program 2, and a distributed database. Distributed data management system 1 is
Access request analysis means 11 and request staging means 1
2, LRU data replacement means 13, MRU data replacement means 14, access history holding means 15, access trend monitoring means 16, replacement method optimization means 17, and access data return means 18. The application program 2 is composed of a data access requesting means 21 and an access data receiving means 22. Here, the request staging means 12 includes the existing node determining means 121
, own node data access execution means 122 , and other node data acquisition request receiving means 123 , and access history holding means 15 includes automatic priority setting means 151 .
and designated priority setting means 152. In addition, a distributed database consists of an access time series section, an index section, and a data section, and the data section contains data items of arbitrary granularity (for example, fields, records, blocks, tables, files, etc.) in random order. It is a set of data arranged in a row and uniquely determined by a data identifier (hereinafter referred to as a key). The index section is made up of an array of pairs of keys and pointers pointing to the corresponding data.
Sorted by key value.

The access time series part is made up of a chain of keys such that the corresponding data is in the order of the most recent access (for the same data, the most recent one is taken), and is made up of two special pointers, the newest pointer and the oldest pointer. Pointers are provided, the former pointing to the newest entry in the key chain and the latter pointing to the oldest entry.

Also, among the n entries (the number of data is n), the first half access counter is used as a counter that counts the number of accesses to the data corresponding to the n/2th (rounded up) entries from the newest one in the chain. C1 is the second half access counter C2 for the rest, and external access counter C3 is the counter for counting the number of times other nodes are accessed without data existing in the own node.
A total access counter CO is provided as a counter for counting all access times. However, the above distributed database does not necessarily exist on secondary storage,
It is loaded into main memory as needed, and may exist only in main memory.

That is, this embodiment is included in each of a plurality of nodes having a distributed database, and when first data corresponding to request data of an application program of the own node exists, this first data is acquired; The present invention further includes a request staging means 12 for requesting another node to obtain second data corresponding to the requested data when the data does not exist in the own node. an access history holding means 15 that holds the data in series; and an LRU that refers to the access time series and replaces the oldest accessed data when the amount of data added to the second data as the first data exceeds a specified capacity. A data replacement means 13 and an M for replacing the latest data in this LRU data replacement means 13.
RU data replacement means 14, access trend monitoring means 16 for recording the section access frequency, and replacement method optimization means 17 for switching the data replacement means according to the result of comparing the section access frequency with a reference value. Be prepared.

Next, the operation of this embodiment will be explained based on FIGS. 1, 2, and 3.

First, we will explain how data is passed to the application program 2 in response to a data access request issued by the application program 2, and then we will explain the mechanism for optimizing the replacement method of data held on the own node. .

When the application program 2 issues a data access request via the key X to the distributed data management system 1 by the data access request means 21, the access request analysis means 11 analyzes the received request and requests key information. The access data is passed to the staging means 12, and the retention priority of the access data at its own node is passed to the access history holding means 15.

The existing node determining means 121 executes a key search using an index in the distributed database of its own node based on the key information. Since the keys are sorted, −
We aim to speed up the process by using a binary search method (binary search). If the corresponding data exists in the own node, control is passed to the own node data access execution means 122; otherwise, control is passed to the other node data acquisition request receiving means 123. The self-node data access execution means 122 executes reading of corresponding data from the data section based on the pointer obtained by the key search, and reads the corresponding data from the access history holding means 15.
Pass control to. Other node data acquisition request receiving means 123
sends a data acquisition request to a predetermined specific node (for example, a parent computer) or to a plurality of unspecified nodes (for example, LAN broadcast), and receives and receives the data.

When registering the received data in the distributed database of its own node, if there is enough data storage capacity (if the number of entries in the index is less than n), it writes the data, adds the corresponding key entry, and updates the index. Sort the entire section by key value. If there is not enough room (the number of entries in the index is n), if LRU data replacement is in progress, the LRU data replacement means 13 replaces the entry indicated by the oldest pointer in the access time series with the corresponding entry in the index section. , and the corresponding data in the data section, the above-mentioned process for when there is no margin is performed, and control is transferred to the access history holding means 15. If the MRU data replacement operation is in progress, the entry indicated by the latest pointer is treated in the same way. Access history holding means 15
In order to reflect information about the data that has just been accessed in the access time series section, if there is no retention priority specification from the application program 2, the automatic priority setting means 151 selects the most recent pointer for the corresponding key entry. If the entry is re-inserted at the beginning, the originally existing entry is replaced, and if not, the addition is done by re-stretching the chain), if retention priority is specified,
It is inserted at a corresponding position (for example, the end pointed to by the oldest pointer) predetermined by the specified priority setting means 152.

When the above processing is completed, the access data return means 18
The data is passed to the access data receiving means 22 of the application program 2, and the data access request processing is completed.

Next, a mechanism for optimizing the replacement method of data held in the own node will be explained.

The access trend monitoring means 16 monitors the total access counter CO
, a first half access counter C1, a second half access counter C2, and an external access counter C3, each of which is counted up within the access history holding means 15. In addition, the counter is cleared to 0 at a predetermined time interval that can be considered appropriate for operation, and serves as the basis for the access frequency for knowing the suitability of the data replacement method in operation, which is the basis for judgment by the replacement method optimization means 17. Revamp the monitoring section. The replacement method optimization means 17 determines whether the newer half of the access time series has a higher hit rate than the other half during the LRU data replacement operation, that is, whether the data access trend is compatible with the LRU data replacement method. It is determined by comparing the first-half access counter c1 and the second-half access counter C2, and if so, the operational status is considered to be good, otherwise it is determined to be unsuitable and switched to the MRU data replacement method. The same applies during MRU data replacement operation.
In case of non-conformity, switch to LRU data replacement method.

Furthermore, although these measures are based on the assumption that the situation in the near past will continue in the near future, it is important to declare priorities individually for application programs with special access tendencies. This compensates for the inconvenient behavior caused by this measure.

〔Effect of the invention〕

As explained above, the present invention enables a distributed data management system that guarantees transparency of data locations to automatically access data obtained from other nodes based on access requests issued by application programs of its own nodes on a computer network. When importing data into a node, in order to select unnecessary data from the data that should be replaced in order to cope with the data retention capacity limit on the own node and to improve the efficiency of updating information reflection, the possibility of access in the near future is determined based on access trends in the near past. The estimation methods are the LRU data replacement method, which assumes that "what was used earlier will be used soon", and the MRU data replacement method, which assumes that "what was used earlier will probably not be used". By monitoring and analyzing and using the correct data, and by correcting it by explicitly specifying data retention priority by the application program, we can determine the optimal data replacement algorithm that would ideally be possible if all future accesses could be known. This has the effect of providing better approximation and minimizing wasteful data communication.

[Brief explanation of the drawing]

FIG. 1 is a block configuration diagram showing the configuration of an embodiment of the present invention. FIG. 2 is a structural diagram of a distributed database. FIG. 3 is a flowchart showing the operations of the access trend monitoring means and replacement method optimization means. 1... Distributed data management system, 2... Application program, 11... Access request analysis means,
12... Request staging means, 13... LRU data replacement means, 14... MRU data replacement means, 15
... Access history holding means, 16... Access trend monitoring means, 17... Replacement method optimization means, 18...
Access data return means, 21... Data access request means, 22... Access data reception means, 121.
...Existence node determination means, 122... Own node data access execution means, 123... Other node data acquisition request receiving means, 151... Automatic priority setting means, 152
... Specified priority setting means.

Claims (1)

[Claims] 1. When first data included in each of a plurality of nodes having a distributed database and corresponding to request data of an application program of the own node exists, this first data is acquired. , a distributed data control device equipped with a request staging means for requesting another node to obtain second data corresponding to the requested data when the data does not exist in the own node; a history holding means; an LRU data replacement means that refers to the access time series and replaces the oldest accessed data when the amount of data added to the second data as the first data exceeds a specified capacity; MRU data replacement means for replacing the latest data with the LRU data replacement means; access trend monitoring means for recording section access frequency; 1. A distributed data control device comprising: replacement method optimization means for performing switching.