Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1996-09-03
2001-02-20
Von Buhr, Maria N. (Department: 2771)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06192365
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the management of transaction logs which contain updates representing operations performed on separated disconnectable computers, and more particularly to log compression that is suitable for use with transaction synchronization and with the handling of clashes that may arise during such synchronization.
TECHNICAL BACKGROUND OF THE INVENTION
“Disconnectable” computers are connected to one another only sporadically or at intervals. Familiar examples include “mobile-link” portable computers which are connectable to a computer network by a wireless links and separate server computers in a wide-area network (WAN) or other network. Disconnectable computers can be operated either while connected to one another or while disconnected. During disconnected operation, each computer has its own copy of selected files (or other structures) that may be needed by a user. Use of the selected items may be either direct, as with a document to be edited, or indirect, as with icon files to be displayed in a user interface.
Unfortunately, certain operations performed on the selected item copies may not be compatible or consistent with one another. For instance, one user may modify a file on one computer and another user may delete the “same” file from the other computer. A “synchronization” process may be performed after the computers are reconnected. At a minimum, synchronization attempts to propagate operations performed on one computer to the other computer so that copies of items are consistent with one another.
During synchronization, some disconnectable computers also attempt to detect inconsistencies and to automatically resolve them. These attempts have met with limited success.
For instance, the Coda File System (“Coda”) is a client-server system that provides limited support for disconnectable operation. To prepare for disconnection, a user may hoard data in a client cache by providing a prioritized list of files. On disconnection, two copies of each cached file exist: the original stored on the server, and a duplicate stored in the disconnected client's cache. The user may alter the duplicate file, making it inconsistent with the server copy. Upon reconnection, this inconsistency may be detected by comparing timestamps.
However, the inconsistency is detected only if an attempt is made to access one of the copies of the file. The Coda system also assumes that the version stored in the client's cache is the correct version, so situations in which both the original and the duplicate were altered are not properly handled. Moreover, Coda is specifically tailored, not merely to file systems, but to a particular file system (a descendant of the Andrew File System). Coda provides no solution to the more general problem of detecting and resolving inconsistencies in a distributed database that can include objects other than file and directory descriptors.
Various approaches to distributed database replication attempt to ensure consistency between widely separated replicas that collectively form the database. Examples include, without limitation, the replication subsystem in Lotus Notes and the partition synchronization subsystem in Novell NetWare® 4.1 (LOTUS NOTES is a trademark of International Business Machines, Inc. and NETWARE is a registered trademark of Novell, Inc.).
However, some of these approaches to replication are not transactional. Non-transactional approaches may allow partially completed update operations to create inconsistent internal states in network nodes. Non-transactional approaches may also require a synchronization time period that depends directly on the total number of files, directories, or other objects in the replica. This seriously degrades the performance of such approaches when the network connection used for synchronization is relatively slow, as many modem or WAN links are.
Moreover, in some conventional approaches potentially conflicting changes to a given set of data are handled by simply applying the most recent change and discarding the others. In other conventional systems, users must resolve conflicts with little or no assistance from the system. This can be both tedious and error-prone.
It is well-known in the database arts to maintain a log of transactions. However, conventional disconnectable systems are not traditional database systems. Conventional disconnectable systems lack transaction logs which can be used to identify and then modify or remove certain apparently inconsistent operations to improve the synchronization process. Conventional systems provide no way to compress transaction logs based on the semantics of the logged update operations. Conventional systems also lack a way to use such transaction logs to recreate earlier versions of database objects.
Thus, it would be an advancement in the art to provide a system and method for compressing a log of transactions performed on disconnectable computers.
It would be a further advancement to provide such a system and method which are suited for use with systems and methods for transaction synchronization.
It would also be an advancement to provide such a system and method which are not limited to file system operations but can instead be extended to support a variety of database objects.
Such a system and method are disclosed and claimed herein.
BRIEF SUMMARY OF THE INVENTION
The present invention provides systems and methods for managing a transaction log which represents a sequence of transactions in a network of connectable computers. Each transaction contains at least one update targeting an object in a replica of a distributed target database. The replicas reside on separate computers in the network. In one embodiment the network includes a server computer and a client computer and a replica of the target database resides on each of the two computers.
One method of the present invention compresses the transaction log by identifying redundant updates and then removing them from the log. Redundant updates are identified by examining the operations performed by the updates and the status of the replicas. The compression is thus based on update semantics, unlike data compression methods such as run-length-encoding which are based only on data values. Semantic tests are also used to identify incompressible update sequences such as file name swaps or sequences that cross a transaction boundary.
A hierarchical log database representing at least a portion of the transaction log assists log management. The log database contains objects corresponding to the updates and transactions in the specified portion of the transaction log. The specified portion of the transaction log may be the entire log, or a smaller portion that only includes recent transactions. The remainder of the transaction log is represented by a compressed linearly accessed log.
Transactions and updates are appended to the log by inserting corresponding objects into the log database. The log database includes an unreplicated attribute or other update history structure. The update history structure is accessed to identify any earlier update referencing an object in the target database that is also referenced by an update in the appended transaction.
The invention also provides other log management capabilities. For instance, each completed transaction in the transaction log has a corresponding transaction sequence number. By specifying a range of one or more transaction sequence numbers, one can retrieve transactions from the transaction log in order according to their respective transaction sequence numbers. In addition, one can locate a desired transaction checkpoint, access the update history structure in the log database, and then construct a prior version of a target database object at it existed at the time represented by that checkpoint.
The present log management invention is suitable for use with various transaction synchronization systems and methods. According to one such, synchronization of the database replicas is performed after the computers are reconnecte
Collins Brian J.
Draper Stephen P. W.
Falls Patrick T.
Computer Law++
Novell Inc.
Von Buhr Maria N.
LandOfFree
Transaction log management in a disconnectable computer and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Transaction log management in a disconnectable computer and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Transaction log management in a disconnectable computer and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2578006