Finally, the database can be scaled up (as well as out) to an extremely high capacity. We'll go into database scalability further, but first let's examine the design of BQF in more detail.

Fields in each BQF queue record

A BQF queue is a database table whose records contain the following fields:

1. Priority: a number from 1 to 9999, where 1 is regarded as the highest priority. Tasks are processed in priority order.
2. Date/Time Scheduled: the earliest date and time when this task may be executed. Within a given priority, this determines the sequence of processing.
3. Payload Type: names the record type (i.e., a table name) containing an associated "payload" for this task.
4. Payload Id: identifies a unique corresponding record in the payload table. The payload provides any additional static parameters needed to process this unit of work.
5. Status: a code indicating whether the task is:
   1. Waiting: to be picked up for execution,
   2. InProcess: currently executing (or crashed), or
   3. Done: completed and ready for deletion
6. Last Modified: a unique identifier specifying when this record was last changed, and by whom. (Used only for recovery, audit, and debugging.)

The BQF table index

The queue has a single index, which defines a primary key formed from the concatenation of fields 1 - 5, i.e. all except the Last Modified information. Keys are guaranteed unique, because each queue record is associated with a unique payload.

This index allows fast lookup of a given queue record, as well as providing an efficient basis for prioritized, first-in, first-out (FIFO) processing. By avoiding the need to maintain multiple indexes, queue manipulations are kept as fast as possible, and the chance of deadlock is reduced.

Another aspect of BQF index optimization is the characteristic that the location of keys within the index tends to be relatively stable as entries are added, updated, and deleted. This minimizes the extent of dynamic index reorganization, further reducing contention during updates to index pages under intensive concurrent usage.

Now let's look at the basic queuing operations to see how these are designed not only to work efficiently with the index, but also to make use of the most efficient modes of synchronization and transaction processing.

AddQueueItem

Adds an item to the queue, effectively scheduling a piece of work to be performed by another machine. This entails inserting a single new key into the queue's index, with a status of "Waiting".
 

GetNextWaiting

Obtains the next eligible task from the queue, in index sequence, changing this item's status from "Waiting" to "InProcess". The algorithm is described in Figure 3, at right.
 

MarkAsDone

Indicates the completion of task in the queue, causing its status to go from "InProcess" to "Done". This is accomplished by a simple update, affecting a single, known key in the index, and leaving its position unchanged.

As an optimization, BQF automatically reuses precompiled SQL for repeatedly used commands. Additional BQF functions allow dynamic batching of multiple queue items, to further reduce the overhead of handling a high volume of small transactions.

BQF garbage collection can operate automatically, as well as support various flexible cleanup options. A novel aspect of BQF's approach is its separation of the action that marks the completion of a task from the actual deletion of the corresponding queue record and its associated resources. Instead of doing an immediate deletion upon the MarkAsDone operation, a very fast update is made to the Status field, and the deletion is deferred. This delayed method of dynamic garbage collection provides a substantial boost in efficiency, as we shall explain.

However fast the individual queuing operations, another factor that can dramatically affect queue performance is the pattern of locality among the many operations that take place under intensive usage. If too many actions require locking a common index page, those operations may be slowed down considerably, waiting in turn, instead of running in parallel. Conversely, if the actions are more spread out across multiple index pages, the effect of locking diminishes, because conflicts are less frequent. This is the point of delayed garbage collection: it reduces contention for the most active index pages, thereby enhancing concurrency.

Leveraging Database Transaction Processing

One of the primary motivations for implementing the queue as a database file is to get the benefit of database transaction processing (TP) reliability and recovery features. The queue generally contains valuable information about work to be done, some of which has not yet been recorded elsewhere. The underlying database TP facilities provide assurance, to an arbitrarily high degree of certainty, that the queue itself can be recovered after any crash, up to the most recently committed transaction.

Beyond guaranteeing recoverability of the queue, BQF's design further assures that both the queue and the rest of the database can be collectively recovered to a mutually consistent state, one of the fundamental tenets of TP. To accomplish this, BQF simply incorporates the queue directly into the database, rather that treating it as an external entity that must somehow be integrated to work in concert with the DBMS-provided TP mechanism. Besides greatly simplifying a thorny problem, BQF is thus able to employ the most efficient, low-level methods for coordinating fine-grained, asynchronous processing.

Recovering from Interruptions and Partial Failures

DBMS-level TP only handles a portion of the complete recovery problem, that of restoring the queue and the database to its most recent state. One must also consider how to deal with the system's interrupted condition, so that normal operation can be resumed as soon as possible. Also we must contend with the common situation of partial failures, where one or more application servers crash, but the database and rest of the distributed system keeps running.

BQF supports a recovery procedure that enables rapid resumption of normal system operation after such interruptions and partial failures. Only those queue items whose Status is "InProcess" need to be considered, and the recovery of these tasks generally reduces to simply resetting their Status to "Waiting". For partial failures, BQF can use the identifier of a crashed server and time of its demise to narrow down the selection, since the id and timestamp are stored as a part of the "Last Modified" field of each queue record. In short, BQF's recovery procedure is fast, because it can be done in a single efficient pass.