Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-02-03
2002-10-15
Homere, Jean R. (Department: 2776)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06466950
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a technique to transmit and receive data between a plurality of devices connected in a network environment, and maintain identical data at each one of the plurality of devices.
2. Background Arts
The network environment where the transmission and reception of data between information processing devices (simply referred to as devices) takes place includes not only communication in highly reliable and high speed network environments using a LAN (local area network) and a special channel, but also includes communication using channels that are less reliable and relatively low in speed such as a mobile communication and a public network. Supposing that a device transmits data which is received by another device using the channels mentioned above, in the system where the data can only be stored to a server having sufficiently large memory and high processing performance and data stored in the server is manipulated from other devices, the transmission and reception of data must take place frequently in large amounts, resulting in problems of increased processing time and increased communication cost.
In order to resolve such problems, a method of storing a copy of the server data to each terminal is adopted, and the server data is manipulated from each terminal. However, even by this method, the result of data manipulation that takes place at each terminal must further be transmitted to all other terminals present in the system. As a general method to reduce the communication cost upon transmitting the result of data manipulation to the other terminals, there is a method not to transmit and receive the data itself but to transmit and receive the update log instead. Each terminal stores contents of all other updates of the data which took place at the other terminals as the update logs. When the updated data of each terminal is being synchronized with the data of the other terminals and the server data, then the update logs are transmitted and received instead of the updated data itself. At this time, a conflict between these data may need to be solved. Various well-known techniques are used to treat such conflicts. For instance, when the data is a file in a file system, one can adopt a method mentioned in the following document: P. Reiher, et. al., “Resolving File Conflicts in the Ficus File System”, USENIX Conference Proceedings, pp. 183-195. USENIX, June 1994.
For a first terminal to transmit an update log of the updated data to a second terminal, a method for selecting the update log that is not present in the second terminal is required, among all the update logs that are present in the first terminal. To achieve this selection method, the second terminal that needs to obtain an update log from the first terminal must transfer an information informing a server or the first terminal having all the update logs which one of the update logs are already being stored in the second terminal. This information is called a log record information. Based on the log record information of the second terminal, the update log which is required for transmitting to the second terminal (or to the server) is extracted from the first terminal. The first terminal then transmits the extracted update log to the second terminal.
Accordingly, a content of the update log that is transmitted and received depends on the log record information of the second terminal. It is not generally possible to predict from another terminal which terminal copies data and when such a terminal copies the data of the server. When the terminal does not have the required update log, then the data itself can possibly be transmitted instead of the update log, although this invites a problem of increased amount of data transferring between the terminals. It is therefore desirable that each terminal stores as much of the update logs as possible.
However, a capacity of the non-volatile storage memory at each terminal is limited, and storing all of the update logs there is virtually impossible. Also, storing a large amount of update logs may suppress the capacity of the memory at each terminal which effects other processing that need be performed by the terminal.
If an update log is distributed to all the terminals storing the log record information, then there will be no more terminals that will be requiring this update log. It is then possible to delete this update log. By deleting the update log that is no longer required, the amount of memory which has been used for storing the update logs is decreased.
For example, a version vector that records data updating counts per each terminal is used as the log record information in the following document: Popek, et. al., “Replication in Ficus Distributed File Systems”, Proceedings of the IEEE Workshop on Management of Replicated Data, November, 1990. In another document by D. Ratner, et. al., “Dynamic Version Vector Maintenance”, UCLA Technical Report CSD-970022, June 1997, an information indicating the data updating counts per each terminal is also included in the version vector. In this document, a verification means called an one-phase bit vector is used to verify that this information included in the version vector is distributed to all the terminals. The one-phase bit vector uses a method to decrement a value of the data updating counts per each terminal by an amount of version vectors distributed to all the terminals. By using this concept, it is possible to delete the update logs, in order from the oldest update log, by a number of times equating to the decremented value of the data updating counts. This means that the update logs which are distributed to all of the terminals can be deleted from all the terminals.
When there are many terminals in a system, verifying whether or not all the terminals store a specific update log is time consuming and is costly because the verification means must also be accompanied by a transmission of the updated content. When engaging a long time in the verification process, the number of update logs that need to be verified will be increased during this verification time. The number of update logs that need be stored in the terminal will also be increased in a case involving many terminals compared to a case involving fewer terminals in the system. For the purpose of avoiding this from happening, the first terminal may inquire all the terminals. However, it is not preferable for the first terminal to directly inquire all the terminals, because this leads to an increase in the communication cost.
Also, suppose that if all the terminals in the system are being used (i.e. all the terminals are turned-on), then even though an enormous amount of time may be required for copying a specific update log to all of the terminals, the update log will eventually be distributed to all of the terminals, and after that the update log can be deleted. However, the update log cannot be deleted if there is a terminal in the system which is not being used for a long period of time, because this terminal which is not being used (i.e. a terminal is turned-off) has not at all received any update logs during the period of non-operation, and therefore this will result in an increased amount of update logs that cannot be deleted from the terminals for a long period of time. Also, when there is a terminal which participated in a system at one time but ceased to participate from a certain point of time, then the update logs could never be deleted using the conventional method.
The present invention attempts to solve the problems described above, aiming to facilitate a deleting of the update logs as early as possible. Also, the present invention aims to reduce an amount of update logs recorded in the memory of a terminal.
SUMMARY OF THE INVENTION
According to one aspect of the present invention, an update log management device used in a data sharing system for maintaining and storing a data replicated among a plurality of the devices connected in a network, comprises: a storage for record
Homere Jean R.
Wassum Luke S.
LandOfFree
UPDATE LOG MANAGEMENT DEVICE AND AN UPDATE LOG MANAGEMENT... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with UPDATE LOG MANAGEMENT DEVICE AND AN UPDATE LOG MANAGEMENT..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and UPDATE LOG MANAGEMENT DEVICE AND AN UPDATE LOG MANAGEMENT... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2926236