0
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ may I ask to clarify "Given N buckets, only distributes keys to bucket N" - let's say I have 3 nodes (n1,n2,n3); and I am adding key K1 - does it go to n3? what about nodes n0, n1? are they empty as all keys are migrated up? $\endgroup$
    – AndrewR
    Apr 19 at 1:50
  • $\begingroup$ Only keys in N-1 ever get migrated to N. New keys all go to the last created bucket (N) So yeah K1 goes to n3, and only some keys in n2 go to n3. $\endgroup$
    – scroobius
    Apr 27 at 7:30
  • $\begingroup$ It sounds like you're looking for a function $h(k,curr,total)$, where $curr$ is the current bucket (or say $0$ assuming we're using 1-based indexing for new keys), and $total$ is the number of buckets. So $h(k,0,N) = N$ always. $h(k, c, N) = c$ for $c < N-1$. And $h(k, N-1, N) \in \{N-1,N\}$. Which in this case should be equivalent to some randomly selected hash we use to generate a single bit indicating whether it goes to $N-1$ or $N$. $\endgroup$
    – MotiNK
    Apr 27 at 8:56
  • $\begingroup$ "Given N buckets, only distributes keys to bucket N": in what way does this describe a hashing process ?? $\endgroup$ Apr 27 at 10:01
  • $\begingroup$ In hash-tables terminology, a bucket can accommodate a single key. $\endgroup$ Apr 27 at 10:03

1 Answer 1

2
+25
$\begingroup$

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'$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.