ceph/ceph — pull request #2402 by yukohe (2014-09-05 08:54:30+00:00)
Title: cursh: optimized crush algorithm for balanced pg distribution among osds

We met an issue of read performance issues (17% degradation) when working on ceph object storage performance evaluation, and found the root cause is unbalanced pg distribution among all osd disks, due to current CRUSH algorithm. We decided to do some optimization on it.

At first, we add a new pps hash algorithm based on the "congruential pseudo-random number generator", which hashes the original raw pgid sequence to some permutation of it. It can produce a uniform pps key space as input for CRUSH.
Then we introduce a new bucket type called "linear", and apply a new modulo based hash algorithm to it, with a balance parameter to adjust for the best distribution uniformity.
At last, we make it an adaptive procedure by adjusting the balance parameter automatically during the preparation for creating a new pool, according to different cluster topology, PG# and replica#, in order to gain a most uniform distribution.

Signed-off-by: yujiehe