We also have such a queue here, and our solution is an algorithm like
this:
1. get the next processor_count * 2 queue ids which are not marked as
taken;
2. choose randomly one of these ids;
3. lock for update with nowait;
4. if locking succeeds:
4.1. check again the item, as it could have been processed in the
meantime - if not available, go to 5.;
4.2. update the DB row to mark the id as taken, and process the
item;
5. there are more ids to try: loop to 2.
6. sleep a small random interval, and loop to 1.
This algorithm should have small enough collision rate on a busy queue
due to the random chosen ids and random sleep (it will have high
collision rate on an almost empty queue, but than you don't really
care), while still allowing all processors to access all entries.
Cheers,
Csaba.