JPS6022781B2 - Initiated duplicate data control method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to an efficient control method for duplicate data in a distributed database system.

Today, with the development of information processing technology, distributed database systems are being discussed.

One of these is a method for controlling duplicate data. Duplicate data refers to data that is managed by physically different computers, but whose contents are the same. The basic principle of the duplicate data control method is to update other duplicate data when one piece of data is updated, thereby maintaining the identity of the duplicate data. The problem in maintaining the sameness is that each computer that manages duplicate data performs processing independently and in parallel, and how to keep the content of the duplicate data managed by these computers the same.

To simplify the explanation, an example in which identity collapses will be explained using FIG. 1. In FIG. 1, there are a computer 1 and a computer 2 that have duplicate data.

Also, record R is one of the duplicate data. Now, an update request is generated in the computer 1 to set the contents of record R to a, and a data update request to set the contents of record R to b is generated in the computer 2. Each computer executes these update requests. At this point, record R in computer 1 is a, and record R in computer 2 is b. Each computer notifies other computers of these update requests. Each computer receives these notifications with a certain time delay,
Update duplicate data. That is, the computer 1 updates the code R to b, and the computer 2 updates the code R to a. In the example of FIG. 1, even if a similar update is performed, the contents of duplicate data managed by each computer will easily collapse. This is because the order of updates differs from outside each conversation. Conventionally, a majority voting method has been proposed as a method for maintaining identity, but it is difficult to put it into practical use because it takes too long to decide whether updates are allowed.

An object of the present invention is to provide a control method for duplicate data that can determine update permission in a short time.

First, the principle of the present invention will be explained. If the data updated at a certain timing is the same data group in each computer, identity can be easily maintained.

The present invention introduces the concept of logical time to this timing. Logical time is a logical time that is not physically the same in each computer but is logically synchronized.
The method for advancing the logical time will be explained below. After confirming that the logical time of all computers other than the privileged computer, which is the leading computer in the distributed database system, is the same logical time as that of the privileged computer, change the logical time of the privileged computer. Advances the logical time by one and notifies computers other than the privileged computer of the logical time change command. When a computer other than the privileged computer receives an instruction to change the logical time from the privileged computer, it advances its own logical time by one and notifies the privileged computer of completion notification.
According to the first embodiment of the present invention, a method for advancing the logical time in a privileged computer is defined, and it includes a function of storing a logical time change completion notification supplied from a computer other than the privileged computer, and A function that advances the logical time of the privileged computer by one when the logical time of all privileged computers other than the privileged computer becomes the same as the logical time of the privileged computer, and a logical time for the outside of the convenience computer other than the privileged computer. This method is characterized by having the function of issuing a change command.

In this method, the logical time of computers other than the privileged computer is equal to or one logical time earlier than the logical time of the privileged computer.

Next, the flow of data in the present invention will be explained using FIG. 2. In order to simplify the explanation, the case of 3 computers will be explained. A computer (hereinafter referred to as A)
Assume that an update request occurs when the logical time of A is k in ". A notifies the privileged computer (hereinafter referred to as B) that an update request has occurred. This event is a
shall be. When B receives a, it notifies a computer other than the privileged computer (hereinafter referred to as C) that a has occurred. Let this event be b. C stores the update request until C's logical time reaches k+N', and executes the update request when C's logical time reaches k+N'. Let this event be c. From the first example of the invention, it can be proven that event b ends before event c.

If update requests are executed according to the above procedure, each computer will execute the same update request at a certain logical time, and it is possible to make the update order the same in each computer.

In the second embodiment of the present invention, an update request generated from each computer at the logical time k of that computer is stored in this computer until the logical time k+N of the computer, and when the logical time reaches k+N. In addition to the first embodiment, a buffer Z buffer that stacks update requests from before the N logic time to the present, and update requests for duplicate data are stored in the buffer. This method is characterized by having a stacking function and a function of executing only an update request issued N logical times ago among the update requests for the buffer when the logical time is changed.

Note that N' is an integer greater than or equal to 2, and the smaller the number, the more efficient it is to achieve the objective. The third embodiment of the present invention is for preventing unnecessary network 10, and in addition to the second embodiment, it has a function of preventing updating of the logical time when there is no update request in the buffer. This method has two characteristics.

Next, details of the present invention will be explained using the block diagram of FIG.

First, a first example will be described. In FIG. 3, the table management device 1 is supplied with a notification of completion of changing the logical time of a computer other than the privileged computer through the terminal 2, and notifies the logical time management device 4 that the contents of the logical time table 3 have been changed. The logical time table 3 is a table that stores the logical time of each computer, and has a number of counters (3.1 to 3.3) equal to the number of all computers.
n). The logical time management device 4 is activated by the table management device 1 when the logical time table is changed,
The content of the logical time table is checked, and when the logical times of all computers other than the privileged computer become equal to the logical time of the privileged computer, the logical time of the privileged computer is advanced by one. It also requests a logical time change command through the terminal 5 to computers other than the privileged computer to advance the logical time. According to the first embodiment, the logical time of computers other than the privileged computer is logically synchronized with the logical time of the privileged computer. Furthermore, since the privileged computer centrally manages the logical time, the system is highly reliable even if a computer other than the privileged computer goes down. The second embodiment has the following functions in addition to the first embodiment.

The logical time management device 4 activates the data update device 6 when changing the logical time.

The command management device 7 is supplied with all update requests for duplicate data through a terminal 8 and records them in a buffer 9 together with their logical time. The data update device 6 is activated by the logical time management device 4 and executes the update request issued at the logical time of the computer minus N from among the update requests stored in the buffer 9. According to the second embodiment, the data group updated at each logical time becomes the same data group in each computer processing the data independently. The third embodiment has the following functions in addition to the second embodiment.

The logical time management device 4 uses the buffer 9 when changing the logical time.
Refer to , and stop changing the logical time when there is no update request in the buffer. According to the third embodiment, it is possible to reduce the number of networks 10 that prevent the logical time from advancing when unnecessary.

Next, details of the logical time management device 4 will be explained using FIG. 3. The logical time management device 4 is composed of a switch circuit 41, a coincidence circuit 42, and a change determination circuit 43.

The switch circuit 41 sequentially sends the values of the counters 31 to 1 of the logical time table 3 to the matching circuit 42. The matching circuit checks whether the values supplied from the switch circuit all match. If all match, the change determination circuit 43 is activated. The change determination circuit 43 checks the contents of the buffer 9, and if there is even one update request, determines the progression of the logical time, advances the logical time of the computer by one,
Start up the data update device 6. It also requests a logical time change command through the terminal 5 to computers other than the privileged computer 0 to advance the logical time. Next, details of the data updating device 6 will be explained using FIG. 3.

The data update device 6 includes a subtracter 61, a counter 62, a coincidence circuit 63, and a gate circuit 64.

The subtracter 42 is activated by the logical time management device 4, subtracts N from the logical time value of the computer, and sets the result in the counter 62. The matching circuit 63 checks the logical time in the buffer 9 and the value of the counter 62, and when they match, notifies the gate circuit 64 that there is a match. The gate circuit 64 notifies the computer of the contents of the update request in accordance with the notification from the coincidence circuit 63. According to the present invention, the data group updated at each logical time becomes the same data group in each out-of-conview unit that is processed independently and in parallel.

This makes it possible to maintain consistency in the same way as standalone. In addition, in order to simplify the explanation in the embodiments, the present invention has been explained as a device independent of a computer, but the present invention can also be built into a computer.
Further, it is also possible to implement it by software, and these do not define the scope of the claims of the present invention.

[Brief explanation of drawings]

FIG. 1 is an explanatory diagram showing an example in which identity collapses, FIG. 2 is an explanatory diagram showing the flow of data in the present invention, and FIG. 3 is a block diagram showing an embodiment of the present invention. In the figure, 1 is a table management device, 2 is an input terminal, and 3 is a table management device.
is a logical time table, 4 is a logical time management device, 5 is an output terminal, 6 is a data update device, 7 is a command management device, 8
9 represents an input terminal, 9 represents a buffer, 41 represents a switch circuit, 42 represents a match circuit, 43 represents a change decision circuit, 61 represents a subtracter, 62 represents a counter, 63 represents a match circuit, and 64 represents a gate circuit. . O diagram O 2 diagram O 3 diagram

Claims (1)

[Scope of Claims] 1. Each computer in a distributed database system having duplicate data has a logical time, and one privileged computer among them receives a notification of completion of changing the logical time supplied from the privileged computer and changes the logical time. a table management device that outputs a change signal; a logical time table that receives the change signal from the table management device and changes the stored logical time of each computer; and a table management device that determines the contents stored in the logical time table and determines the privilege Logical time management that advances the logical time of the privileged computer by one when the logical time of all computers other than the computer becomes the same as the logical time of the privileged computer, and issues a logical time change command to computers other than the privileged computer. A redundant data control method characterized by having a device. 2. Each computer in a distributed database system with duplicate data has a logical time, and one privileged computer among them receives a logical time change completion notification supplied from a computer other than the privileged computer and sends a logical time change signal. A table management device to output,
A logical time table for changing the stored logical time of each computer upon receiving a change signal from the table management device, and determining the contents stored in the logical time table, and determining the logical time of all computers other than the privileged computer. a logical time management device that advances the logical time of the privileged computer by one when the logical time of the privileged computer becomes the same as the logical time of the privileged computer and issues a command to change the logical time to computers other than the privileged computer; A buffer that stacks update requests that avoid duplicate data, and N of the update requests in the buffer when the logical time changes.
1. A duplicate data control method comprising: a data update device that executes only update requests issued before a logical time. 3. Each computer in a distributed database system with duplicate data has a logical time, and one privileged computer among them receives a logical time change completion notification supplied from a computer other than the privileged computer and sends a logical time change signal. A table management device to output,
A logical time table for changing the stored logical time of each computer upon receiving a change signal from the table management device, and the contents of the stored logical time table are determined, and the logical time of all computers other than the privileged computer is set to privileged. A logical time management device that advances the logical time of the privileged computer by one when it becomes the same as the logical time of the computer, and issues a command to change the logical time to computers other than the privileged computer; A buffer that stacks update requests for duplicate data, and N of the update requests in the buffer when the logical time changes
1. A duplicate data control system comprising: a data update device that executes only update requests issued before a logical time; and means for preventing updating of the logical time when there is no data in the buffer.