I used to work for a company that had a similar problem (hundreds of millions or billions of 'potential' work items). We ended up hacking up a well-tuned MySQL

I used to work for a company that had a similar problem (hundreds of millions or billions of 'potential' work items). We ended up hacking up a well-tuned MySQL table into behaving as a work queue that would distribute batches of work via an update query that also acted as an atomic lock on the "in-flight" work items. Not really the way you're supposed to do it, but hey, it was a helluva lot easier than trying to make a RabbitMQ instance, or cluster for that matter, retain the state of a billion rows. Ludicrous. Message queues are really designed for just that, low-latency message dispatch. Long-standing work to be done just isn't feasible with the design of most MQs. I'd love to see some shake-n-bake scalable database -> worker libraries crop up so that I don't have to hack up something like that godawful MySQL table again. And before you ask, no, MapReduce isn't appropriate for this. The tricky part is the race conditions and the retention of state long term, not the distribution/parallelization of work. Another aspect that proved interesting was keeping the MySQL instance from getting eaten alive by workers asking for jobs to perform. EDIT: Re: 'shake-n-bake libraries', I'm considering hacking up what I have in mind, if nothing else but to inspire some better talented coders to create a framework or library that serves this need.