Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2001-08-31
2004-04-06
Rones, Charles (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C709S230000
Reexamination Certificate
active
06718327
ABSTRACT:
BACKGROUND
The invention relates to a distributed queuing system, such as a system providing timed delivery of messages.
Distributed message queue systems are currently available, including several commercial solutions such as IBM's Message Queue (MQ) Series and Microsoft's Message Queue Server (MSMQ). However, the existing systems invariably involve a centralized server or process for control of the queue. Therefore, there is a need for a system utilizing decentralized processes.
SUMMARY
The invention provides a queuing system using decentralized processes for coordinated access to queue entries. It offers decentralized synchronization and notification mechanisms by use of a library of queue access methods operating against a remote file system access protocol, such as the CIFS (Common Internet File System) protocol, that provides enforced, network-wide file locking processes. Implementing synchronization using such file-locking processes avoids any need for a master synchronization process. The queue is accessed by clients (by which is meant client applications running on nodes on a network) that communicate with the queue through coordinated access of the queue data structures, which are stored on a remote file system implementing the remote file system access protocol.
The invention provides methods for adding and removing entries from a queue. The methods are invoked by clients separately; that is, each client operates autonomously and independently of all other clients, and there is no master process operating to synchronize access to the queue. Because the clients operate autonomously, no client is dependent on the continued operation of any other client, and there is no need to provide failover to handle client failures. If a client fails, the only consequence is that the system loses a corresponding amount of processing capacity.
The invention is preferably implemented with the file system running on a network-attached RAID (Redundant Array of Independent Disks) array storage device that maintains file locks on the RAID controller. Such network attached storage (NAS) devices include the NetApp Filer products available from Network Appliance, Inc. of Sunnyvale, Calif., with a 4.0 release or later of NetApp® Data ONTAP™ operating system software, which implements the CIFS protocol as a native file system protocol. With this implementation, the file system locks are arbitrated on the NAS device controller, which implements CIFS, rather than by a master client or some master arbitration agent, which would have to be protected by some kind of failover mechanism.
With the file system implemented by an NAS device and the clients programmed to operate autonomously, the queue system has no single point of failure, providing a high degree of reliability without having to rely on any specialized hardware or software recovery.
Furthermore, the invention provides a notification mechanism that notifies and wakes up all receivers when an entry newly appears or becomes available for processing in the queue, so that all receivers will attempt to process the entry. Such a notification mechanism allows the clients to operate autonomously, because no assumption is made as to which individual client will handle or process a particular queue entry.
Some of the advantages that can be realized by particular implementations of the invention are listed below.
Fault tolerance: The invention offers the advantages of persistence and fault tolerance, which are accomplished by maintaining the queue data structures as files on a redundant networked storage device. Many critical faults may occur during normal operation of the queue—such as a disk drive failure, a network failure, or software problems such as resource corruption—interfering directly or indirectly with the operation of the queue clients. By storing the persistent (on-disk) data on fault tolerant storage, hardware failure impact is minimized, freeing the queuing system from any need for special hardware recovery. For example, if a hard disk holding a queue fails, the storage device has built-in redundancy to enable an immediate backup or to provide a secondary copy of the queue data. Thus, the integrity of the queue is ensured. In addition, the queue is not affected by a software fault such as an unexpected process termination. A persistent copy of the queue data remains unchanged and thus software faults do not affect the operation nor corrupt the state of the queue.
Cluster-Wide Accessibility: The queue data structures are stored on a high-speed network-accessible data store, which makes the queue accessible from any client that can communicate with the data store. As long as a client application can identify the queue it, wishes to access by a globally unique identifier, coordinated access is possible.
Multi-Client Access: Any number of client applications can access a queue almost simultaneously. The suite of methods provided to perform queue operations can be divided into three general categories: addition methods, removal methods, and administrator methods. (In the time queue implementation that will be described later, these are called sender methods, receiver methods, and administrator methods.) File locks are used to synchronize access to the queue data structures. It is required that the file system provide file locks that are strictly enforced, meaning that if one client on node A locks the queue for a given operation, another client application on node B will not be able to access it until the client on node A releases its lock.
High performance: Another advantage of the invention is its high performance. A queue can be implemented so that entries can be added to a queue not only at the tail of the queue, but also within the queue according to a priority associated with the entry when it is added. In an implementation of a time queue, for example, messages (which would be the queue entries) are inserted in ascending order of their delivery times (which would be, in effect, their queue priorities), so that the receiving clients can simply pop the top message off the time queue for processing instead of having to traverse the queue for the next message to be processed. This allows the time queue to handle requests from many clients at any given time, even when there are a significant number of messages in the time queue with the same delivery time. When the queue data structures include a kernel file that stores entries using an indexed scheme, a receiving client read the entry data directly using its offset in the kernel file.
REFERENCES:
patent: 5623666 (1997-04-01), Pike et al.
patent: 6389433 (2002-05-01), Bolosky et al.
patent: 6535855 (2003-03-01), Cahill et al.
patent: 2002/0055950 (2002-05-01), Witteman
patent: 2002/0120763 (2002-08-01), Miloushev et al.
Paul Leach and Dan Perry, “CIFS: A Common Internet File System,” http://www.microsoft.com/mind/1196/cifs.htm, Nov. 1996.
SNIA CIFS Documentation Work Group, “Common Internet File System (CIFS), Version: CIFS-Spec 0.9,” SNIA (Storage Network Industry Association), Revision Date Mar. 26, 2001.
Fish & Richardson P.C.
Mahmoudi Hassan
Openwave Systems Inc.
Rones Charles
LandOfFree
Fault-tolerant queue with autonomous client operation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fault-tolerant queue with autonomous client operation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fault-tolerant queue with autonomous client operation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3239115