Well, of course we'll need a retrying system with delay, so that's a sorted set then together with the work item list.

I prefer simple solutions and I know it was our fault we got a data loss with Redis. Still Beanstalkd queues have been causing less pain than Resque and Redis together. Integrated delays, tubes and deadlines are really nice.

Altogether the reliability comes from the deadlines. If my worker gets stuck (well, it's Ruby), we don't lose the work item. Doing pop on Redis will delete the item from the queue, but in Beanstalkd you reserve the item and delete it when you're done.