I was reading the following FDS paper:
The paper has a TLT (tract locator table) for identifying where to write in each server. The table is basically a hash table where the index i maps to some (tract) server to do writes to or reads to.
Say that there are n (tract) servers. It says that if instead of just having index i mapping to server i, if instead we appended n more indexes mapping to some permutation of the servers (and having a table of size 2n in this example), we can avoid having a bottleneck at any specific server when doing reads or writes. Basically it claims that as we append more permutations the better. Why is this?
Why would this be?
Just for reference the index mapping function is:
$$i = (hash(g) + t) \pmod n$$
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)
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