Scalabe fitness proportionate selection

I'd like to implement a scalable application in Heroku that provides two APIs: - insert(id, fitness) <-- inserts an item and its fitness to some array - extract() <-- returns an id of an item extracted from the array using the fitness proportionate selection (a.k.a. roulette selection algorithm)

Implementing it with a single dyno is a piece of cake. However, to make it scalable I want to use several dynos. Now it gets tricky.

I think it would be best to use Redis to keep the array in a central place. The problems I see with this approach are: - Race-conditions (several dynos may extract the same item - I can work-around it by using the blpop function, but then I might get long loops if dynos keep extracting the same item) - Choosing an item using the fitness proportionate selection isn't trivial if I have millions/billions of items (the only way I thought of to implement this is read the whole array, choose an item and then try to blpop it, but this would make the operation soooooo long)

Please assist. Thanks!