Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1997-11-03
2002-03-05
Kim, Matthew (Department: 2186)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C710S052000, C714S015000, C714S016000
Reexamination Certificate
active
06353834
ABSTRACT:
FIELD OF INVENTION
This invention relates to message queuing, and more particularly to a fast, reliable message queuing system for both client-server and mobile agent applications.
BACKGROUND OF THE INVENTION
Message queuing is the most fundamental paradigm for communication between applications on different computer systems due to its inherent flexibility in allowing both synchronous and asynchronous processing. The message queuing middleware infrastructure is a very flexible framework for a number of application domains in both general client-server as well as mobile agent computing arenas, to wit work flow computing, object messaging, transactional messaging and data replication services.
It will be appreciated that in many transactional messaging scenarios data is oftentimes lost during the transmission. This is no more catastrophic than in the banking industry in which banking records transmitted from one location to another can be lost due to server failures, transmission line failures or other artifacts. It is incumbent upon the system managers to be able to quickly locate the fact that an error has occurred and to be able to reconstruct the data from a known point where the data was valid.
Establishing that point at which an error has occurred has in the past been accomplished by systems which scan an entire so-called log file to reconstruct the up-to-date state of the system before the crash. Log files are routinely utilized with their associated time stamps to identify messages and the data they contain. However, the scanning of entire log files to ascertain the up-to-date state can require scanning as many as 1,000 log records.
Not only is the scanning of the overall log record an inefficient way to ascertain where an error occurred and to be able to reconstruct files from that point, systems in the past have required two disk files, one serving as a data file, and the other serving as a log file.
Moreover, the correlation between the log entries and the data files or sectors is complicated by the fact that in the past, sectors were stored in some indiscriminant order, leaving the mapping between the log file and the sectors a somewhat time consuming process.
By way of further background, it will be appreciated that message queuing is used in general to be able to provide a fail-safe storage for data records which are transmitted from one point to another. If, for instance, an error occurs and data is lost at one location, it can be reconstructed at a second location due to the storage inherent in message queuing.
As an example, it is desirable, especially in stock market trades, that any interruption in trading to be minimized to minutes as opposed to hours. On occasion, however, when system servers go down, recovery can take from two to eight hours depending on the number of trades in the system at that time. There is thus a need to minimize down time and expense of locating and reconstructing damaged files.
Note that as used herein, the term queue file refers to the physical storage of messages that are in transmission. Queue files may also be viewed as holding cells for uncompleted operations. Basically, what this means is that if the receiver is not there to receive a given message, the message is held in the queue file and is deliverable at a later time. As a result, the queue files offer reliability in the retention of information that is transmitted.
Moreover, in traditional systems, the recovery data is not provided by the queue file itself. Thus, queue files have not been utilized to identify the state of the file when an error or lost data has occurred, and have thus not been used to reconstruct the data file from data which is previously uncorrupted. In a traditional system, the recovery data is not provided by the queue file itself.
Another example of how message queuing is applied to a real-world application involves how a message queuing infrastructure may support real-time on-line transaction processing using mobile agents. In this example, the customer, for instance, is a bank with geographically dispersed branches. Customer accounts are created and kept at the local branches where the account was opened. For illustrative purposes, this is called the home branch of the account. A copy of each account is also kept at the main office. A read operation on an account can be made from either the local branch or the main office. An update to an account, however, will require that both the home branch copy and the main office copy be updated in a coordinated fashion.
If the update request occurred at the home branch, the local copy must then be updated. This update can trigger an agent which then automatically submits an enqueue request to the queue manager or queue server. This queue manager in turn dequeues the request across a wide area network to another queue manager, which in turn, dequeues the update request to the database server for the mirror office accounts.
A message queue in this example provides asynchronous and reliable processing. Asynchronous processing begins with the agent that is triggered by the database update at one location. The agent submits the update request to the message queue manager in an asynchronous manner, and need not wait around for a response. The message queue manager serves as holding cell for the request so that the requester can continue processing without the need to wait for a response. The message queue manager also provides reliability in this example in that it maintains a copy of the update request in its queue until the recipient of this update request has acknowledged its receipt via a well-known handshaking protocol called the Two Phase Commit protocol, known in the industry as transactional message queuing.
While these types of message queuing systems have operated reliably in the past, they have relied on a data architecture that uses separate queue data and log record files to store the messages that are appended to a message queue. This architecture prevents rapid repair at the time of a serve crash and requires two storage disks, one for data and one for the log records. Moreover, traditional message queuing architectures are generally not optimized for write operations without requiring extra hardware to work efficiently, and are not appropriate for high throughput systems with low message residence times. The separate queue data and log files mentioned above also introduce an extra level of unreliability since there exists two points of potential file corruption and media failure. Additionally, there is usually no means for the message queuing systems administrator to predefine the amount of work needed to do recovery a priori.
Note, the above systems are commercially available as Digital Equipment Corporation's DECmessageQ, IBM's MQ Series, and Transarc's Encina RQS.
SUMMARY OF INVENTION
In order to solve the above noted problems with traditional message queuing, a message queuing system is provided that saves and stores messages and their state in an efficient single file on a single disk to enable rapid recovery from server failures. The single disk, single file storage system into which messages and their states are stored eliminates writes to three different disks, the data disk, the index structure disk and the log disk. The single disk, single file storage is made possible by clustering all information together in a contiguous space on the same disk. The result is that all writes are contained in one sweeping motion of the write head in which the write head moves only in one direction and only once to find the area where it needs to start writing messages and their states are stored. In order to keep track of the clustered information, a unique Queue Entry Map Table is used which includes control information, message blocks and log records in conjunction with single file disk storage that allows the write head never to have to back-up to traverse saved data when writing new records. The system also permits locating damaged files without the requirement of scanning entire log fi
Schwenke Derek L.
Wong David W. H.
Brinkman Dirk
Curtin Andrew J.
Kim Matthew
Mitsubishi Electric Research Laboratories Inc.
Vital Pierre M.
LandOfFree
Log based data architecture for a transactional message... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Log based data architecture for a transactional message..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Log based data architecture for a transactional message... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2882513