Redis's lpush, and rpop plus some naming scheme might suffice. Everything is atomic, so the thread bit is covered.