I would like to implement a form of consistent hashing using a set of permutations. The rules are as follows:
- I have Y=~32 buckets and X items. Buckets may be "alive" or "dead". Items are to be distributed evenly across "alive" buckets, regardless of the subset of buckets which are alive. By distributed evenly I mean that the bucket with the most items will not have many more items than the bucket with the least items (hopefully a difference of at most 1 item).
- To do this I want to generate permutations of the buckets - one permutation per item, such that each item will fall into the first "alive" bucket in that item's permutation.
From what I can gather, if each row is a permutation and we generate a table with X rows and Y columns - we want permutations with the following traits:
- The first column should have (roughly) the same amount of appearances for each of the Y buckets.
- Assuming a subset S of the buckets are dead, all permutations which begin with a subset T of S should have (roughly) the same amount of apearances for each of the Y buckets when observing the spots directly after (T) in each of these permutations. (T is obviously not necessarily the same subset of S for each permutation)
The questions are: Do there exist such permutations for X which is approximately equal to Y^2 or smaller, for a gap of at most 1 item between buckets in the worst case? For a gap of 2? Etc... If there do exist such permutations - how can they be built?