Cross Platform FIFO Queue
Peter Olcott
FIFO queue for inter-process communication for processes or
threads that will execute on the same hardware platform. I
would like whatever mechanism is chosen to be portable
across Unix/Linux/Windows and optionally Max OS X.
This process will be invoked by an HTTP web-server. Multiple
HTTP requests will be placed at the end of this FIFO queue,
and one or multiple servers will pull these requests from
the front of the FIFO queue. The only web-servers that I am
currently considering have source code available.
I would like suggestions for implementing this architecture.
Marcel Müller
> This process will be invoked by an HTTP web-server. Multiple
> HTTP requests will be placed at the end of this FIFO queue,
> and one or multiple servers will pull these requests from
> the front of the FIFO queue. The only web-servers that I am
> currently considering have source code available.
Use a database that has either no read locks like Oracle or skip the
locked entries (like the readpast hint for MSSQL). Note that ANSI SQL
will not be sufficient. But usually there is a database specific solution.
Marcel
Peter Olcott
"Marcel Müller" <news.5...@spamgourmet.com> wrote in
message
news:4ba8e261$0$6892$9b4e...@newsspool2.arcor-online.net...
Yes that was one of the ideas that I was thinking. It may be
the best idea. From what I recall Unix/Linux is apparently
not very robust in its OS level support for file based
locks. Perhaps a standard package such as MySQL circumvents
this issue by providing its own support.
Marcel Müller
> the best idea. From what I recall Unix/Linux is apparently
> not very robust in its OS level support for file based
> locks.
Why? Using a directory with small files as a queue is another solution.
All you have to do is to add time stamps to your file names and execute
them in sorted order.
Of course you have to care about synchronization yourself. E.g. skip
files that cannot be moved to the private working dir of each server,
use a low and a high water mark for reading the directory content to
avoid O(n�) in the number of currently queued items. Furthermore you
have to provide some rollback mechanism if a server dies.
All of that handles the database out of the box.
But files are reliable. E.g. the integration platform IBM DataStageTX
uses File based Queues like this, at least in older Versions.
Marcel
Peter Olcott
I am now leaning towards MySQL to handle this. I will need a
database to handle user accounts anyway. Hopefully MySQL can
handle record locking. I could simply read from the front of
the table (in record number order) and append to the back of
the table.
The read would mark this item a being actively processed,
and delete it (or mark it to be considered as deleted) when
processing is complete. I am guessing that the append to the
end of the table will may require a file lock. (Unless I
recycle deleted records first).
If I recycle deleted records then the process must look for
the first of several records that are marked as available
for processing. To speed things up I could initialize the
table to some large size (maximum concurrent process limit)
to prevent the need for the more expensive file locks.
Does this sound good? Are there any issues that I have not
considered? Hopefully MySQL is stable and robust enough.
Marcel Müller
Peter Olcott wrote:
> I am now leaning towards MySQL to handle this. I will need a
> database to handle user accounts anyway. Hopefully MySQL can
> handle record locking.
any database must implement locks.
> I could simply read from the front of
> the table (in record number order) and append to the back of
> the table.
There is no 'front' and 'back' in the table unless you introduce a
strongly monotonic column as primary key. Of course, you could do that
with an auto increment column as primary key.
> The read would mark this item a being actively processed,
> and delete it (or mark it to be considered as deleted) when
> processing is complete.
This does not work. Think about the LUWs.
Either the consumer updates a line and set the status to 'in process'
and /immediately/ commits this change. In this case the request is
forever lost in this state if the consumer dies for some reason.
Or the consumer does /not/ commit the DB immediately. In this case the
behavior depends on the database and the transaction isolation level. In
READ COMMITED mode (which is the default) other consumer are either
forced to wait on the row to become unlocked or see the old value. The
first case would block all other consumers at the SELECT. The second
case will cause the request to be serviced multiple times but the
following consumers will block on the UPDATE statement. Any case is
unusable since it will block all servers with only one request.
In fact you have to place a exclusive write lock at the moment where the
consumer selects the next work item (isolation level serializable). And
furthermore the SELECT must not wait on locked records, instead it must
skip them. If a consumer dies unexpectedly the database does a rollback
and the incomplete work item is implicitly put back in the queue.
This gives you maximum throughput while keeping transactional data
integrity at service level EO (exactly once).
If the database does not support the write lock at select you could use
a trick. Issue an update statement on the status column with a row count
limit of 1. This will fetch exactly one work item and place a write lock
on it.
Btw. I am in doubt that MySQL fully supports transaction isolation
levels. So you have to study the database documentation very carefully,
to get a reliable implementation even when the DB kernel is updated.
> I am guessing that the append to the
> end of the table will may require a file lock. (Unless I
> recycle deleted records first).
Databases do not work with file locks. The use exclusive access anyway.
So the synchronization is no longer distributed over different processes.
> If I recycle deleted records then the process must look for
> the first of several records that are marked as available
> for processing.
I would strongly recommend not to do this.
Use a strongly monotonic column. And delete serviced records
immediately. Anything else would blow up your table. If you want a
logging, move the records to another table after completion, and do this
in the same transaction.
> Does this sound good? Are there any issues that I have not
> considered? Hopefully MySQL is stable and robust enough.
Sorry, I have not implemented this pattern in MySQL so far. Only MSSQL,
Oracle and OpenSQL (ABAP).
Marcel
Peter Olcott
> Hi,
>
> Peter Olcott wrote:
>> I am now leaning towards MySQL to handle this. I will
>> need a database to handle user accounts anyway. Hopefully
>> MySQL can handle record locking.
>
> any database must implement locks.
>
>> I could simply read from the front of the table (in
>> record number order) and append to the back of the table.
>
> There is no 'front' and 'back' in the table unless you
> introduce a strongly monotonic column as primary key. Of
> course, you could do that with an auto increment column as
> primary key.
Isn't there always some sort of sequential record number
that is based on the order that rows were initially added to
a table? I want to avoid indexes on this because they would
unnecessarily degrade performance.
>
>> The read would mark this item a being actively processed,
>> and delete it (or mark it to be considered as deleted)
>> when processing is complete.
>
> This does not work. Think about the LUWs.
I don't know that acronym.
My database experience is at a lower level of programming.
In this case it seems that the problem is simple. If SQL
does not work this way I can always do this myself from
scratch.
Two tables:
(1) (InProcess Table) A tiny table of records that are
currently being processed, this is expected to have far
fewer than 100 rows. (based on a multiple of the expected
peak load) This is the table that controls the process flow.
It is kept very small so it can be read sequentially very
quickly. There are three status values:
(a) Available for Processing
(b) Currently being Processed.
(c) Empty, available to be re-used.
This table has a direct link by record number in the
Transaction History table.
(2) (Transaction History Table) A much larger table audit
and recovery purposes. This table contains all of the
details of every transaction along with two status codes:
(a) Currently being Processed.
(b) Processed is completed
The HTTP WebServer process adds records to the Transaction
History Table, and the InProcess table. It adds records to
the InProcess table by first looking for an record that is
marked as Empty. If it does not find one, it reports this as
an error. For now we can assume that this never occurs. The
number of available records will be initialized to a
multiple of the expected peak load.
(1) Read the first sequential record in the InProcess table.
(2) If its status indicates that it is available lock this
record and if the record lock is successful change its
status to in processing, commit this change.
(3) When processing successfully completes mark the
in-processing record as empty (available for re-use) in the
InProcess table and also update the transaction history
table status to Completed commit this change and unlock the
record. (The Transaction History table record should not
have to be locked because record access is limited by the
InProcess table, a one-to-one mapping).
If all of the data access goes through a single process,
(such as a single instance of MySQL) then it would be
possible to be accomplished much more quickly than actual
disk access time. In this case the record lock would lock a
region of memory instead of a region of disk space. The SQL
provider could write these changes to disk when it gets a
free moment. Changes would be lost if the SQL provider
crashed, before the changes are written but processing of
the transaction could be much faster. If the changes are
lost, the transaction history table would provide the means
of recovery.
Peter Olcott
"Peter Olcott" <NoS...@OCR4Screen.com> wrote in message
news:09ednakBvaREpjfW...@giganews.com...
This is just a rough sketch to assess feasibility. I already
thought of ways to improve it. If it is not easy to do in
SQL, I will go back to the sockets level of IPC.
Marcel Müller
[SQL-Tables]
> Isn't there always some sort of sequential record number
> that is based on the order that rows were initially added to
> a table?
No.
If you select the same result set (e.g. the entire table) twice you may
get the rows in different order unless you used ORDER BY with some
unique key. But the latter is unusable in your case, because it will not
return any data before it read the entire table.
But in your case you want to get exactly one row.
> I want to avoid indexes on this because they would
> unnecessarily degrade performance.
The index is definitely better than table scans.
>>> The read would mark this item a being actively processed,
>>> and delete it (or mark it to be considered as deleted)
>>> when processing is complete.
>> This does not work. Think about the LUWs.
>
> I don't know that acronym.
Logical Unit of Work, i.e. a transaction.
> My database experience is at a lower level of programming.
> In this case it seems that the problem is simple. If SQL
> does not work this way I can always do this myself from
> scratch.
Of course. You could write a dispatcher service that use a TCP socket to
each consumer to dispatch the requests.
> (1) (InProcess Table) A tiny table of records that are
> currently being processed, this is expected to have far
> fewer than 100 rows. (based on a multiple of the expected
> peak load) This is the table that controls the process flow.
> It is kept very small so it can be read sequentially very
> quickly. There are three status values:
> (a) Available for Processing
> (b) Currently being Processed.
> (c) Empty, available to be re-used.
> This table has a direct link by record number in the
> Transaction History table.
I would prefer single linkes lists. One for the unserviced requests, one
for the unused records and /none/ for curently processed records. The
processed records are kept in the control blocks for each registered
server (consumer). Once a server completes a request the completed block
is appended to the empty queue and the next block is taken from the
request queue (if any). If a server disconnects unexpectedly the request
is placed back to the front of the request queue. You may introduce a
retry counter to discard requests that crash the servers.
There is no need to enumerate the blocks at all. All operations are
O(1). I would further recommend to write this queue manager as single
threaded application with select() unless the number of consumers grows
rather large. This avoids any need for locking in the application code.
> (2) (Transaction History Table) A much larger table audit
> and recovery purposes. This table contains all of the
> details of every transaction along with two status codes:
> (a) Currently being Processed.
> (b) Processed is completed
I would only write completed records to this log. The processed records
can be easily accessed by enumerating the control blocks of the servers.
And there is no longer a need to access the records in the history table
a second time in this case.
Marcel
