using database for queuing operations?

[Mark Harrison]

I would like to try and build a queuing mechanism on top of Postgresql.

Imagine an application where a large number of processes generate images
and queue up thumbnail requests. A smaller number of processes (running
on a dedicated set of machines) generate thumbnails for those images.

Adding entries to the queue from multiple processes is easy, by executing
statements such as:

insert into nameq(action,na me) values('add','f oo');

Now comes the part I'm not sure about. I can easily write a front
end program that selects the lowest sequence number

select * from nameq where serial = (select min(serial) from nameq);

and then parcels that out to a subprocess for thumbnail generation.
It would be really great if I could handle this without the front end
program, so that multiple programs could do something like the following:


select next image to be processed (with above select logic)
process the image
delete the row for that image

I think that I can use "select for update" to obtain a write lock (so that
I can safely delete the row when finished), but I'm unsure if it's possible
to avoid the race condition where two processes would get the same row.

Any advice, comments, etc, appreciated!
Mark

---------------------------------------------------------


mh=# \d nameq
Table "public.nam eq"
Column | Type | Modifiers
---------+-----------------------------+----------------------------------------------------
action | text | not null
name | text | not null
serial | bigint | default nextval('nameq_ seq'::text)
addtime | timestamp without time zone | default ('now'::text):: timestamp(6) with time zone
Indexes:
"nameq_addt ime" btree (addtime)
"nameq_ser" btree (serial)


mh=# select * from nameq;
action | name | serial | addtime
--------+------+--------+----------------------------
add | bar | 11 | 2004-09-20 11:50:19.756182
del | bar | 13 | 2004-09-20 11:50:25.080124
add | foo | 14 | 2004-09-20 11:50:28.536398


--
Mark Harrison
Pixar Animation Studios

---------------------------(end of broadcast)---------------------------
TIP 1: subscribe and unsubscribe commands go to majordomo@postg resql.org

[Jeff Amiel]

Re: using database for queuing operations?

Add a column to the nameq table designating the 'state' of the image.
Then your logic changes to "select * from nameq where serial = (select
min(serial) from nameq) and state="UNPROCES SED" (or whatever)
So you select for update, change the state, then process the
image....then delete.
Viola!

Mark Harrison wrote:
[color=blue]
> I would like to try and build a queuing mechanism on top of Postgresql.
>
> Imagine an application where a large number of processes generate images
> and queue up thumbnail requests. A smaller number of processes (running
> on a dedicated set of machines) generate thumbnails for those images.
>
> Adding entries to the queue from multiple processes is easy, by executing
> statements such as:
>
> insert into nameq(action,na me) values('add','f oo');
>
> Now comes the part I'm not sure about. I can easily write a front
> end program that selects the lowest sequence number
>
> select * from nameq where serial = (select min(serial) from nameq);
>
> and then parcels that out to a subprocess for thumbnail generation.
> It would be really great if I could handle this without the front end
> program, so that multiple programs could do something like the following:
>
>
> select next image to be processed (with above select logic)
> process the image
> delete the row for that image
>
> I think that I can use "select for update" to obtain a write lock (so
> that
> I can safely delete the row when finished), but I'm unsure if it's
> possible
> to avoid the race condition where two processes would get the same row.
>[/color]


---------------------------(end of broadcast)---------------------------
TIP 3: if posting/reading through Usenet, please send an appropriate
subscribe-nomail command to majordomo@postg resql.org so that your
message can get through to the mailing list cleanly

[Mark Harrison]

Re: using database for queuing operations?

Jeff Amiel wrote:[color=blue]
> Add a column to the nameq table designating the 'state' of the image.
> Then your logic changes to "select * from nameq where serial = (select
> min(serial) from nameq) and state="UNPROCES SED" (or whatever)
> So you select for update, change the state, then process the
> image....then delete.[/color]

Thanks Jeff, I think that will work perfectly for me!

Cheers,
Mark

--
Mark Harrison
Pixar Animation Studios

---------------------------(end of broadcast)---------------------------
TIP 6: Have you searched our list archives?

http://archives.postgresql.org

[Jim C. Nasby]

Re: using database for queuing operations?

On Mon, Sep 20, 2004 at 03:08:29PM -0500, Jeff Amiel wrote:[color=blue]
> Add a column to the nameq table designating the 'state' of the image.
> Then your logic changes to "select * from nameq where serial = (select
> min(serial) from nameq) and state="UNPROCES SED" (or whatever)
> So you select for update, change the state, then process the
> image....then delete.
> Viola![/color]

You should also consider what happens if the conversion program can't
update the state to processed for some reason. For example, pgsql might
get shutdown unexpectedly, or the conversion process could.
--
Jim C. Nasby, Database Consultant decibel@decibel .org
Give your computer some brain candy! www.distributed.net Team #1828

Windows: "Where do you want to go today?"
Linux: "Where do you want to go tomorrow?"
FreeBSD: "Are you guys coming, or what?"

---------------------------(end of broadcast)---------------------------
TIP 2: you can get off all lists at once with the unregister command
(send "unregister YourEmailAddres sHere" to majordomo@postg resql.org)

[Jeff Amiel]

Re: using database for queuing operations?

Although....it wont really solve the race condition issue...
you can still have a point where 2 processes select the same
record...one gets the 'for update' lock on it and the other one just
waits for it...
Regardless of the 'state', once that lock releases, the second process
will grab it.
In my world I have a 'main' process that selects all the records that
currently meet the criteria I am interested and them 'parse' them out to
the sub-processes via unique id.

Dont know if this helps....
Jeff



Mark Harrison wrote:
[color=blue]
> Jeff Amiel wrote:
>[color=green]
>> Add a column to the nameq table designating the 'state' of the image.
>> Then your logic changes to "select * from nameq where serial =
>> (select min(serial) from nameq) and state="UNPROCES SED" (or whatever)
>> So you select for update, change the state, then process the
>> image....then delete.[/color]
>
>
> Thanks Jeff, I think that will work perfectly for me!
>
> Cheers,
> Mark
>[/color]


---------------------------(end of broadcast)---------------------------
TIP 4: Don't 'kill -9' the postmaster

[Jeff Amiel]

Re: using database for queuing operations?

......or instead change the logic to:

So you:

1. select for update, with the criteria outlined
2. Check the state (again) to see of we had that particular race condition.
3. If already processed or in processing, somebody else must already be
working on it....go back to step 1
4, change the state
5. process the image
6. delete.
7 go to step 1.



change the state, then process the image....then delete.



Jeff Amiel wrote:
[color=blue]
> Although....it wont really solve the race condition issue...
> you can still have a point where 2 processes select the same
> record...one gets the 'for update' lock on it and the other one just
> waits for it...
> Regardless of the 'state', once that lock releases, the second process
> will grab it.
> In my world I have a 'main' process that selects all the records that
> currently meet the criteria I am interested and them 'parse' them out
> to the sub-processes via unique id.
>
> Dont know if this helps....
> Jeff
>
>
>
> Mark Harrison wrote:
>[color=green]
>> Jeff Amiel wrote:
>>[color=darkred]
>>> Add a column to the nameq table designating the 'state' of the image.
>>> Then your logic changes to "select * from nameq where serial =
>>> (select min(serial) from nameq) and state="UNPROCES SED" (or whatever)
>>> So you select for update, change the state, then process the
>>> image....then delete.[/color]
>>
>>
>>
>> Thanks Jeff, I think that will work perfectly for me!
>>
>> Cheers,
>> Mark
>>[/color]
>
>[/color]


---------------------------(end of broadcast)---------------------------
TIP 5: Have you checked our extensive FAQ?

http://www.postgresql.org/docs/faqs/FAQ.html

[Ron St-Pierre]

Re: using database for queuing operations?

Mark Harrison wrote:
[color=blue]
> select * from nameq where serial = (select min(serial) from nameq);
>[/color]
You might also want to try this as:
select * from nameq where serial = (select serial from nameq order
by serial asc limit 1);
and see if runs faster.

Ron


---------------------------(end of broadcast)---------------------------
TIP 8: explain analyze is your friend

[Scott Ribe]

Re: using database for queuing operations?

> So you:[color=blue]
>
> 1. select for update, with the criteria outlined
> 2. Check the state (again) to see of we had that particular race condition.
> 3. If already processed or in processing, somebody else must already be
> working on it....go back to step 1
> 4, change the state
> 5. process the image
> 6. delete.
> 7 go to step 1.[/color]

You can also rely on the old trick that, having selected min(serial) you
know that:

update nameq set state = 'processing'
where serial = xxx and state = 'unprocessed';

Will execute atomically and will set a row count of 0 or 1. You still have
some racing going on with the selects, but only 1 process ever gets hold of
a row to process. I've done similar things where tests showed that
collisions would be relatively rare--the following could really be bad if
processing didn't take "much time" and you had "a lot" of processes
extracting queue items. Excuse the atrocious mix of pseudo-sql and pseudo-C
and commentary:

select serial from nameq
where state = 'unprocessed' order by serial limit 10;
for( i = 0; i < 10 && i < actual num rows selected; ++i )
{
curserial = currow.seral;
update nameq set state = 'processing'
where serial = curserial and state = 'unprocessed';
if( rowcount == 1 )
{
process row;
update nameq set state = 'processed' where serial = curserial;
break;
}
else
{
pause some brief random time to prevent lock-step race
fetch next row
}
}


--
Scott Ribe
scott_ribe@kill erbytes.com

http://www.killerbytes.com/

(303) 665-7007 voice


---------------------------(end of broadcast)---------------------------
TIP 3: if posting/reading through Usenet, please send an appropriate
subscribe-nomail command to majordomo@postg resql.org so that your
message can get through to the mailing list cleanly

[Chris Gamache]

Re: using database for queuing operations?


SELECT ... FOR UPDATE can and will produce a race condition if multiple
back-ends attempt to access the same row at the exact same time. If you don't
believe me, ask my gray hairs! :) Instead use

LOCK TABLE your_table IN EXCLUSIVE MODE;

Here's what I do:

BEGIN;
LOCK TABLE your_table IN EXCLUSIVE MODE;
UPDATE your_table SET claimed_by = 'unique_process or_id', status = 'IN PROCESS'
WHERE serial_pkey = (SELECT min(serial_pkey ) FROM your_table WHERE status =
'UNPROCESSED')
COMMIT;

Then I can

SELECT * FROM your_table WHERE claimed_by = 'unique_process or_id' AND status =
'IN PROCESS';

and I can be sure my multiple processors get one and only one row, marked for
processing by one processor. The statements in the LOCKed transaction are
completely serialized, but the subsequent selects are unencumbered by a lock.

Many thanks to Tom Lane for this solution. It has worked like a charm for two
years and counting.

CG

--- Jeff Amiel <jamiel@istream imaging.com> wrote:
[color=blue]
> .....or instead change the logic to:
>
> So you:
>
> 1. select for update, with the criteria outlined
> 2. Check the state (again) to see of we had that particular race condition.
> 3. If already processed or in processing, somebody else must already be
> working on it....go back to step 1
> 4, change the state
> 5. process the image
> 6. delete.
> 7 go to step 1.
>
>
>
> change the state, then process the image....then delete.
>
>
>
> Jeff Amiel wrote:
>[color=green]
> > Although....it wont really solve the race condition issue...
> > you can still have a point where 2 processes select the same
> > record...one gets the 'for update' lock on it and the other one just
> > waits for it...
> > Regardless of the 'state', once that lock releases, the second process
> > will grab it.
> > In my world I have a 'main' process that selects all the records that
> > currently meet the criteria I am interested and them 'parse' them out
> > to the sub-processes via unique id.
> >
> > Dont know if this helps....
> > Jeff
> >
> >
> >
> > Mark Harrison wrote:
> >[color=darkred]
> >> Jeff Amiel wrote:
> >>
> >>> Add a column to the nameq table designating the 'state' of the image.
> >>> Then your logic changes to "select * from nameq where serial =
> >>> (select min(serial) from nameq) and state="UNPROCES SED" (or whatever)
> >>> So you select for update, change the state, then process the
> >>> image....then delete.
> >>
> >>
> >>
> >> Thanks Jeff, I think that will work perfectly for me!
> >>
> >> Cheers,
> >> Mark
> >>[/color]
> >
> >[/color]
>
>
> ---------------------------(end of broadcast)---------------------------
> TIP 5: Have you checked our extensive FAQ?
>
> http://www.postgresql.org/docs/faqs/FAQ.html
>[/color]




_______________ _______________ _
Do you Yahoo!?
Declare Yourself - Register online to vote today!

http://vote.yahoo.com

---------------------------(end of broadcast)---------------------------
TIP 5: Have you checked our extensive FAQ?

http://www.postgresql.org/docs/faqs/FAQ.html

[Christopher Browne]

Re: using database for queuing operations?

Clinging to sanity, jamiel@istreami maging.com (Jeff Amiel) mumbled into her beard:[color=blue]
> .....or instead change the logic to:
>
> So you:
>
> 1. select for update, with the criteria outlined
> 2. Check the state (again) to see of we had that particular race condition.
> 3. If already processed or in processing, somebody else must already
> be working on it....go back to step 1
> 4, change the state
> 5. process the image
> 6. delete.
> 7 go to step 1.
>
> change the state, then process the image....then delete.[/color]

If you can identify some form of "process ID" for each of the
processors running concurrently, you might do something like:

1. Update for selection (converse of 'select for update' :-)

update nameq set action = 'in process', pid = 45676
where action <> 'in process' and (other criteria for grabbing the
record)

2. select * from nameq where pid = 45676 and action = 'in progress'

3. do your work, processing the image

4. update nameq set action= 'done', -- Or whatever is the appropriate
-- state
pid = NULL
where [criterion for the processed image...]

This way only one of the PIDs will get ownership of any given row for
step #2...

At the Unix level, this would be like making a "work" directory for
each work process, and having Step #1 try to do "mv file
$pid_work_dir".

The file can only get placed in one spot; if one "mv" wins, the others
necessarily lose. If one "set pid = my_pid" wins, no other one can do
so later.
--
let name="cbbrowne" and tld="acm.org" in String.concat "@" [name;tld];;

http://www3.sympatico.ca/cbbrowne/linux.html

"It's like a house of cards that Godzilla has been blundering
through." -- Moon, describing how system messages work on ITS

[Jim C. Nasby]

Re: using database for queuing operations?

What's the race in the SELECT FOR UPDATE?

BTW, this is one nice thing about Oracle... it comes with a built-in
queuing mechanism. It would probably be worth trying to write a generic
queuing system and stick it in Gborg.

Incidentally, Oracle also supports user-named locks, which would
probably make this easier to do. LOCK TABLE works, but it's more brute
force than is needed. Unfortunately, I don't see a way to simply add
such a thing onto PostgreSQL without adding it to the core.

On Mon, Sep 20, 2004 at 02:17:38PM -0700, Chris Gamache wrote:[color=blue]
>
> SELECT ... FOR UPDATE can and will produce a race condition if multiple
> back-ends attempt to access the same row at the exact same time. If you don't
> believe me, ask my gray hairs! :) Instead use
>
> LOCK TABLE your_table IN EXCLUSIVE MODE;
>
> Here's what I do:
>
> BEGIN;
> LOCK TABLE your_table IN EXCLUSIVE MODE;
> UPDATE your_table SET claimed_by = 'unique_process or_id', status = 'IN PROCESS'
> WHERE serial_pkey = (SELECT min(serial_pkey ) FROM your_table WHERE status =
> 'UNPROCESSED')
> COMMIT;
>
> Then I can
>
> SELECT * FROM your_table WHERE claimed_by = 'unique_process or_id' AND status =
> 'IN PROCESS';
>
> and I can be sure my multiple processors get one and only one row, marked for
> processing by one processor. The statements in the LOCKed transaction are
> completely serialized, but the subsequent selects are unencumbered by a lock.
>
> Many thanks to Tom Lane for this solution. It has worked like a charm for two
> years and counting.
>
> CG
>
> --- Jeff Amiel <jamiel@istream imaging.com> wrote:
>[color=green]
> > .....or instead change the logic to:
> >
> > So you:
> >
> > 1. select for update, with the criteria outlined
> > 2. Check the state (again) to see of we had that particular race condition.
> > 3. If already processed or in processing, somebody else must already be
> > working on it....go back to step 1
> > 4, change the state
> > 5. process the image
> > 6. delete.
> > 7 go to step 1.
> >
> >
> >
> > change the state, then process the image....then delete.
> >
> >
> >
> > Jeff Amiel wrote:
> >[color=darkred]
> > > Although....it wont really solve the race condition issue...
> > > you can still have a point where 2 processes select the same
> > > record...one gets the 'for update' lock on it and the other one just
> > > waits for it...
> > > Regardless of the 'state', once that lock releases, the second process
> > > will grab it.
> > > In my world I have a 'main' process that selects all the records that
> > > currently meet the criteria I am interested and them 'parse' them out
> > > to the sub-processes via unique id.
> > >
> > > Dont know if this helps....
> > > Jeff
> > >
> > >
> > >
> > > Mark Harrison wrote:
> > >
> > >> Jeff Amiel wrote:
> > >>
> > >>> Add a column to the nameq table designating the 'state' of the image.
> > >>> Then your logic changes to "select * from nameq where serial =
> > >>> (select min(serial) from nameq) and state="UNPROCES SED" (or whatever)
> > >>> So you select for update, change the state, then process the
> > >>> image....then delete.
> > >>
> > >>
> > >>
> > >> Thanks Jeff, I think that will work perfectly for me!
> > >>
> > >> Cheers,
> > >> Mark
> > >>
> > >
> > >[/color]
> >
> >
> > ---------------------------(end of broadcast)---------------------------
> > TIP 5: Have you checked our extensive FAQ?
> >
> > http://www.postgresql.org/docs/faqs/FAQ.html
> >[/color]
>
>
>
>
> _______________ _______________ _
> Do you Yahoo!?
> Declare Yourself - Register online to vote today!
> http://vote.yahoo.com
>
> ---------------------------(end of broadcast)---------------------------
> TIP 5: Have you checked our extensive FAQ?
>
> http://www.postgresql.org/docs/faqs/FAQ.html
>[/color]

--
Jim C. Nasby, Database Consultant decibel@decibel .org
Give your computer some brain candy! www.distributed.net Team #1828

Windows: "Where do you want to go today?"
Linux: "Where do you want to go tomorrow?"
FreeBSD: "Are you guys coming, or what?"

---------------------------(end of broadcast)---------------------------
TIP 9: the planner will ignore your desire to choose an index scan if your
joining column's datatypes do not match

[Tom Lane]

Re: using database for queuing operations?

Mark Harrison <mh@pixar.com > writes:[color=blue]
> It would be really great if I could handle this without the front end
> program, so that multiple programs could do something like the following:[/color]
[color=blue]
> select next image to be processed (with above select logic)
> process the image
> delete the row for that image[/color]
[color=blue]
> I think that I can use "select for update" to obtain a write lock (so that
> I can safely delete the row when finished), but I'm unsure if it's possible
> to avoid the race condition where two processes would get the same row.[/color]

See the archives; this has been discussed in great detail before
(several times before, if memory serves).

regards, tom lane

---------------------------(end of broadcast)---------------------------
TIP 8: explain analyze is your friend

[Mark Harrison]

Re: using database for queuing operations?

Tom Lane wrote:[color=blue]
> See the archives; this has been discussed in great detail before
> (several times before, if memory serves).
>
> regards, tom lane[/color]

Sorry for the cluelessness, but searching on queuing, scheduling,
and their spelling variants isn't turning up anything useful. Got
something else I can search on?

TIA!
Mark

PS, so far the comments received have been very useful... thanks so much!!!

---------------------------(end of broadcast)---------------------------
TIP 4: Don't 'kill -9' the postmaster

[Tom Lane]

Re: using database for queuing operations?

Mark Harrison <mh@pixar.com > writes:[color=blue]
> Tom Lane wrote:[color=green]
>> See the archives; this has been discussed in great detail before
>> (several times before, if memory serves).[/color][/color]
[color=blue]
> Sorry for the cluelessness, but searching on queuing, scheduling,
> and their spelling variants isn't turning up anything useful.[/color]

I got a bunch of hits on "select for update queue" from
http://www.pgsql.ru/db/pgsearch/ , for instance

http://archives.postgresql.org/pgsql-general/2003-05/msg00342.php

http://archives.postgresql.org/pgsql-general/2001-02/msg00977.php

http://archives.postgresql.org/pgsql-sql/2001-11/msg00378.php

There seems to be some disconnect between that search engine and the
archives though. For instance it also pointed me to

http://archives.postgresql.org/pgsql-sql/2002-11/msg00001.php

which does not exist; in fact archives.postgr esql.org has hardly
anything for that whole month of pgsql-sql. Marc, any idea what's wrong
there? The data was obviously there last time Oleg trolled for it.

regards, tom lane

---------------------------(end of broadcast)---------------------------
TIP 1: subscribe and unsubscribe commands go to majordomo@postg resql.org

[Chris Ochs]

Re: using database for queuing operations?


[color=blue]
> Tom Lane wrote:[color=green]
> > See the archives; this has been discussed in great detail before
> > (several times before, if memory serves).
> >
> > regards, tom lane[/color]
>
> Sorry for the cluelessness, but searching on queuing, scheduling,
> and their spelling variants isn't turning up anything useful. Got
> something else I can search on?
>
> TIA!
> Mark
>
> PS, so far the comments received have been very useful... thanks so[/color]
much!!!

As a side note on searching the archives, the search is broken at the
moment, and has been for at least several days. I couldn't get any search
results on just common terms like freebsd or linux...

Chris



---------------------------(end of broadcast)---------------------------
TIP 8: explain analyze is your friend