# Why does appending permutations of servers at the end of hash table avoid bottlenecks?

I was reading the following FDS paper:

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

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

where:

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

-
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? – D.W. Mar 28 '14 at 4:28

Adding permutations isn't about preventing slow servers from becoming bottlenecks, rather it's about dispersing a convoy once one forms behind a slow server. Because of the way tract locations are hashed, sequential reads of any blob always walk the tract locator table in the same order. Suppose you have six tract servers and your tract locator table looks like this

123456

and server 3 is slower than the others. Since sequential readers walk the table in the same order the slowness of server 3 will cause a convoy of sequential clients to form waiting for server 3. Once server 3 serves them, they all move on server 4 which may also become overloaded. Then 5, then 6, and before long the convoy is big enough to hammer each server in turn instead of spreading the load evenly across all of them.

If your tract locator table looks like this

643512623154125364213546

i.e. four permutations of 123456, events transpire differently if there is a slow server. If server 3 is slow, satisfied sequential readers will move from server 3 to servers 5, 1 or 6 depending on where they are in the table. This instead of all sequential I/O clients turning their attention to the same server after visiting server 3. The extra permutations have the effect of breaking up convoys if they form and lessening the likelihood of convoys forming at all.

-
The thing that confuses me is, in every n sequence of 1 to n, you will always encounter the slow server, say s, at some point, just at a different point. How come this makes any difference at all if we will always "get stuck" at the slow server s eventually? – Pinocchio Mar 28 '14 at 3:16
I see, the key sentence you wrote is "This instead of all sequential I/O clients turning their attention to the same server after visiting server 3." Right? It just means that after reading 3, it just means that all server will NOT pile up to the same "next" server and spread the load better, right? – Pinocchio Mar 28 '14 at 3:21
Exactly. That's the key difference. – Kyle Jones Mar 28 '14 at 3:26