Consistent Hashing Algorithm Without Distribution / Load Balancing

Question

I need some help finding or creating a consistent hashing algorithm with the following properties:

1. Given N buckets, only distributes keys to bucket N.
2. When number of buckets are increased from N to N+1, only keys in N have to be migrated to N+1.
3. When number of buckets are reduced from N to N-1, only keys in N are migrated to N-1

More context, I'm building a distributed hash table on an environment, where reliability is not an issue, it's guaranteed that each node would be up, and not added or removed unpredictably (I control the nodes being added or removed)

I don't want replication (replication of data is handled at a lower level), Also when nodes are removed, they can only be removed in a LIFO manner (node 2, cannot be removed before node 3)

I would appreciate any insight into this, and literature suggestions.

Answer 1

The below is with 0-based indexing for the buckets.

• We assume we have some hash function $h(k) \rightarrow [0,1)$.
• When looking up $k$ check the last node (index $N-1$) and the node $\lfloor Nh(k) \rfloor$.
• When inserting $k$ we always insert in the last node (index $N-1$).
• When $N$ changes to $N'$ (which can be either $N+1$ or $N-1$) redistribute all keys (in all buckets) as follows: $\lfloor N'h(k) \rfloor$.

Conceptually this uses a number-line $[0,1)$ for the keys, where each bucket has the same size. Thus, e.g. when $N=4$, the buckets correspond to $\left[0, \frac{1}{4}\right), \left[\frac{1}{4}, \frac{2}{4}\right), \left[\frac{2}{4}, \frac{3}{4}\right), \left[\frac{3}{4}, 1\right)$. The last bucket can also contain keys which were directly inserted there, regardless of $h(k)$.

Looking at $N'=N+1$, then the range for $N'$, $\left[1-\frac{1}{N+1}, 1\right)$, is completely contained in the previous range for $N$, $\left[1-\frac{1}{N},1\right)$, so only keys in bucket $N$ can migrate to $N'$.

Similarly, when $N'=N-1$, then the previous range for $N$ is completely contained in the range for $N-1$ so it will be migrated to $N$. The new range for $N'$ is $\left[1 - \frac{1}{N-1}, 1\right)$. The previous range for $N-i$ was $\left[1 - \frac{i}{N}, 1 - \frac{i-1}{N}\right)$ so for $i > 1$ we see that this doesn't overlap the new range for $N'$ (specifically that $1 - \frac{1}{N-1} > 1 - \frac{i-1}{N}$). So we see that no other bucket migrates keys to $N'$.