2
$\begingroup$

I was reading the paper on Jump consistent hashing, and I'm having some trouble understanding one particular line (page 5, paragraph 2)

"Since we want P(j ≥ i) = (b+1) / i, we set P(j ≥ i) iff r ≤ (b+1) / i."

My understanding is that:

  • P(j ≥ i) is the probability that a key "jumps"/moves to a different bucket after bucket#i
  • r is a pseudo random number between [0, 1) with a uniform distribution
  • b is the last bucket# for which a jump occurred for this key

In particular, I am having trouble understanding this phrase: "we set P(j ≥ i) iff".

Set it to what? Do they mean to say "We want a key to jump to a different bucket ≥ i with a random probability r. This means that P(j ≥ i) ≥ r, which implies that (b+1)/i ≥ r. Hence the smallest such bucket number is obtained by the equation i = floor((b+1)/r)"?

$\endgroup$
  • $\begingroup$ Yeah, that phrase makes no sense. Errors happen. I guess you'll have to reconstruct their reasoning from context. The "we set (j ≥ i) iff" can't be right, and similarly in the next two sentences. $\endgroup$ – D.W. Aug 15 '18 at 17:51
  • $\begingroup$ @D.W. Thank you. I guess there is no good way of knowing what the authors meant unless they publish a new revision, or I'm able to reach out to one of them (which seems unlikely). $\endgroup$ – skittish Aug 15 '18 at 18:56
  • $\begingroup$ I think it's a great question for this site; maybe someone here will work through their logic, reconstruct the gaps, and explain in an answer. $\endgroup$ – D.W. Aug 15 '18 at 20:14
  • $\begingroup$ Today it's really hard to find someone who CAN'T be reached :) First author has profiles on linkedin and google+, I don't even checked the second one. $\endgroup$ – Bulat Aug 15 '18 at 23:12
  • $\begingroup$ I did find them on LinkedIn, but I had to send them a connection invite. I'm not so sure they'll accept. :) I'm sure they're swamped with many requests every day. $\endgroup$ – skittish Aug 17 '18 at 0:06
2
$\begingroup$

I suggest this as a better version of the paragraph.

Now, for a given $i$ and $k$, we generate a pseudo­random variable, $r$, that is uniformly distributed between 0 and 1, and set $j = \lfloor(b+1) / r\rfloor$. This gives $P(j \ge i) = (b+1) / i$, as we want:
$P(j \ge i)$
$ = P(\lfloor(b+1) / r\rfloor ≥ i)\quad$ substituting the definition of j
$ = P((b+1) / r \ge i)\quad$ because $i$ is an integer
$ = P(r \le (b+1) / i)\quad$ solving the inequality for $r$
$ = (b+1) / i\quad$ because $r$ is uniformly distributed between 0 and 1

$\endgroup$
  • $\begingroup$ Thank you for responding Mr. Lamping.<br /> 1. "Now, for a given k and j" -> Do you mean for a given i and j? 2. While this is easier to follow mathematically, I'm still having a hard time understanding the intuition behind setting j = floor((b+1)/r)? What is the relation between j, b, r (a randomly chosen number)? $\endgroup$ – skittish Aug 18 '18 at 0:47
  • $\begingroup$ Or put in a different way, how does sampling from k (k = number of keys) uniform distributions result in the selection of 1/(j+1) keys being moved? Kindly excuse my ignorance in case my probability theory is not up to the mark. :) $\endgroup$ – skittish Aug 18 '18 at 0:59
  • $\begingroup$ I see this explanation in page 4, para 1: "In order to jump for the right fraction of keys, it uses a pseudo­random number generator with the key as its seed. To jump for 1/(j+1) of keys, it generates a uniform random number between 0.0 and 1.0, and jumps if the value is less than 1/(j+1)." Do the samplings of k independent uniform distributions themselves form a uniform distribution (X)? Is that the piece I'm missing? Because if they do, then I understand that P(X ≤ 1/(j+1)) = 1/(j+1) [because X is a uniform distribution, and P(X ≤ T) = T]. Meaning that 1/j+1 are expected to be chosen. $\endgroup$ – skittish Aug 18 '18 at 1:18
  • $\begingroup$ Caught again! it now reads "for a given i and k". It's trying to say that you should generate a new r for computing each jump. Perhaps saying just that would be simpler. I don't have a great intuition about the formula. I got to it by working the derivation backwards. For an intuition for why is is roughly right, you know that the next jump should be to something on the order of 2*(b+1), and since r is 1/2 on average, (b+1)/r will be on the order of 2*(b+1). P.S. I find it quite disappointing that we couldn't find a shorter explanation for 10 lines of code! $\endgroup$ – John Lamping Aug 18 '18 at 1:33
  • $\begingroup$ Thank you! The statement about next jump being in the order of 2*(b+1) provides a much better intuition to me as to why the algo works. $\endgroup$ – skittish Aug 20 '18 at 16:36

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.