I have N buckets. I have M users. Each user can buy anywhere between 1 and N tickets to an upcoming lottery.
I would like to distribute the tickets more or less evenly between the buckets, with the additional constraint that a user can’t have more than one ticket go into the same bucket.
It would also be nice if when I added or removed buckets, I didn’t have to redistribute a large percentage of the tickets.
This is somewhat similar to a consistent hash ring problem. I could do hash(userId+userTicketNumber), and put that hash on the ring. However, I don’t have any guarantee that the user’s tickets will get put into a unique set of buckets.
One solution would be to allocate user 1, ticket 1 to bucket 1, then increment the bucket number and the ticket number. When the user is out of tickets, increment the bucket number and move to user 2. When we run out of buckets start again at bucket 1, and so on and so forth until all tickets are allocated. Unfortunately this procedure would lead to a lot of reallocation when I added or removed buckets.
I’ve tried searching for variants on the consistent hash ring problem, but I’m not finding anything. I’m sure this problem has been solved before – do you know where the solution is?