3
$\begingroup$

I was reading the following FDS paper:

https://www.usenix.org/system/files/conference/osdi12/osdi12-final-75.pdf

and it says that the the following hash function does not distribute things uniformly (instead it creates a binomial distribution):

$$i = (hash(g + t)) \pmod n$$

while the following did distribute things uniformly:

$$i = (hash(g) + t) \pmod n$$

Why does the above distribute things evenly while the other one doesn't?

g = is the global UID for a blob

t = tract number. (tract is the measure/units of reads and writes to a blob).

n = is the number of tract servers or a multiple of the tract servers.

hash = SHA-1 (according to the paper)


Paper Reference:

Title: Flat Datacenter Storage

Author(s): Edmund B. Nightingale, Jeremy Elson, Jinliang Fan, Owen Hofmann, Jon Howell, Yutaka Suzue

Institution(s): Microsoft Research, Univeristy of Texas at Austin

$\endgroup$
  • 1
    $\begingroup$ Would you mind editing the question to add a full reference (paper title, author names, and conference name) to the paper so that this question is more readily findable by search and thus more likely to be useful to others? $\endgroup$ – D.W. Mar 28 '14 at 4:29
  • $\begingroup$ I wouldn't mind at all, where do I put all that info? In the title or in the body of the question? $\endgroup$ – Pinocchio Mar 28 '14 at 4:55
  • $\begingroup$ Also, whats a conference name? Is that info in the paper? $\endgroup$ – Pinocchio Mar 28 '14 at 4:55
  • $\begingroup$ I'd suggest you edit the question and add it to the body of the question: where you currently just have a link, provide the full citation. Conference name is the place where it was published. A quick search on Google Scholar or looking at the authors web pages should turn that up for you. $\endgroup$ – D.W. Mar 28 '14 at 4:55
4
$\begingroup$

The second function is easier to explain: it sends tract $t$ to position $t + h \pmod{n}$, where $h = hash(g)$. The function $t \mapsto t + h \pmod{n}$ is injective (one-to-one), and so every index $i$ gets mapped exactly once (in fact, by $i - h \pmod{n}$).

For the first function, we can think of $t \mapsto hash(g+t)$ as a random function (this is a common assumption whenever hash functions are involved; the fact that we use SHA-1 is completely irrelevant). Therefore for each fixed index $i$, the probability that $t$ is mapped to $i$ is $1/n$, and the total number of $t$s mapped to $i$ is distributed $\mathrm{Bin}(1/n,1) \approx \mathrm{Po}(1)$, that is it has binomial distribution which is approximated well by a Poisson distribution with mean $1$.

$\endgroup$
  • $\begingroup$ I understand now why the first one is uniform. But I got lost on your second argument after your comment about the SHA-1, do you mind explaining that in a little more detail? Thanks so far though! :) $\endgroup$ – Pinocchio Mar 28 '14 at 0:56
  • $\begingroup$ The thing that confuses me is, if the probability of i mapping to 1/n, doesn't that mean its uniform if every slot has the same chance to ending up in any server? $\endgroup$ – Pinocchio Mar 28 '14 at 0:58
  • $\begingroup$ It's not uniform, since things will get clumped together. Some indices $i$ will receive no hits, and some will receive more than one. That's not a flat distribution. A flat distribution is what you get in the other case, in which each index gets exactly one hit. $\endgroup$ – Yuval Filmus Mar 28 '14 at 1:30

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.