Let admins add a region without melting their cluster

[OpenStack Infra]

https://review.openstack.org/115441
commit 6d77c379bd8f51e520896967cdcfc9add3d934a4
Author: Samuel Merritt <email address hidden>
Date: Tue Aug 19 16:44:56 2014 -0700

    Let admins add a region without melting their cluster

    Prior to this commit, swift-ring-builder would place partitions on
    devices by first going for maximal dispersion and breaking ties with
    device weight. This commit flips the order so that device weight
    trumps dispersion.

    Note: if your ring can be balanced, you won't see a behavior
    change. It's only when device weights and maximal-dispersion come into
    conflict that this commit changes anything.

    Example: a cluster with two regions. Region 1 has a combined weight of
    1000, while region 2 has a combined weight of only 400. The ring has 3
    replicas and 2^16 partitions.

    Prior to this commit, the balance would look like so:

      Region 1: 2 * 2^16 partitions
      Region 2: 2^16 partitions

    After this commit, the balance will be:

      Region 1: 10/14 * 2^16 partitions (more than before)
      Region 2: 4/14 * 2^16 partitions (fewer than before)

    One consequence of this is that some partitions will not have a
    replica in region 2, since it's not big enough to hold all of them.

    This way, a cluster operator can add a new region to a single-region
    cluster in a gradual fashion so as not to destroy their WAN link with
    replication traffic. As device weights are increased in the second
    region, more replicas will shift over to it. Once its weight is half
    that of the first region's, every partition will have a replica there.

    DocImpact

    Change-Id: I945abcc4a2917bb12be554b640f7507dd23cd0da