rebalance crashes after removing many devices

[Samuel Merritt]

You can get RingBuilder.rebalance to leave the ring in an invalid state if you remove enough devices.

If more than one replica of a partition has to move due to devices being deleted, rebalance() only moves one, leaving the ring in an invalid state, and then validate() complains about it.

You can make it happen for an N-replica ring by removing more than 1/N of the devices; however, there's a chance it'll happen any time more than one device is removed between rebalances.

Example reproduction:

vagrant@ocelot:/tmp$ swift-ring-builder foo.builder create 8 3 1
vagrant@ocelot:/tmp$ swift-ring-builder foo.builder add z1-10.1.1.1:6000/d0 1000
Device z1-10.1.1.1:6000/d0_"" with 1000.0 weight got id 0
vagrant@ocelot:/tmp$ swift-ring-builder foo.builder add z2-10.1.1.2:6000/d1 1000
Device z2-10.1.1.2:6000/d1_"" with 1000.0 weight got id 1
vagrant@ocelot:/tmp$ swift-ring-builder foo.builder add z3-10.1.1.3:6000/d2 1000
Device z3-10.1.1.3:6000/d2_"" with 1000.0 weight got id 2
vagrant@ocelot:/tmp$ swift-ring-builder foo.builder add z1-10.1.1.1:6000/d3 1000
Device z1-10.1.1.1:6000/d3_"" with 1000.0 weight got id 3
vagrant@ocelot:/tmp$ swift-ring-builder foo.builder add z2-10.1.1.1:6000/d4 1000
Device z2-10.1.1.1:6000/d4_"" with 1000.0 weight got id 4
vagrant@ocelot:/tmp$ swift-ring-builder foo.builder add z3-10.1.1.1:6000/d5 1000
Device z3-10.1.1.1:6000/d5_"" with 1000.0 weight got id 5
vagrant@ocelot:/tmp$ swift-ring-builder foo.builder rebalance
Reassigned 256 (100.00%) partitions. Balance is now 0.00.

vagrant@ocelot:/tmp$ swift-ring-builder foo.builder remove d3
d3z1-10.1.1.1:6000/d3_"" marked for removal and will be removed next rebalance.
vagrant@ocelot:/tmp$ swift-ring-builder foo.builder remove d4
d4z2-10.1.1.1:6000/d4_"" marked for removal and will be removed next rebalance.
vagrant@ocelot:/tmp$ swift-ring-builder foo.builder remove d5
d5z3-10.1.1.1:6000/d5_"" marked for removal and will be removed next rebalance.

vagrant@ocelot:/tmp$ swift-ring-builder foo.builder rebalance
-------------------------------------------------------------------------------
An error has occurred during ring validation. Common
causes of failure are rings that are empty or do not
have enough devices to accommodate the replica count.
Original exception message:
 All partitions are not double accounted for: 600 != 768
-------------------------------------------------------------------------------

This occurs on tag 1.4.6 as well as master (1a7453f).

[OpenStack Infra (hudson-openstack)]

Fix proposed to branch: master
Review: https://review.openstack.org/4710

[OpenStack Infra (hudson-openstack)]

Reviewed: https://review.openstack.org/4710
Committed: http://github.com/openstack/swift/commit/7fe0c6c695364c4c1226d89175ec0fd91e15ec58
Submitter: Jenkins
Branch: master

commit 7fe0c6c695364c4c1226d89175ec0fd91e15ec58
Author: Samuel Merritt <email address hidden>
Date: Tue Feb 28 18:25:14 2012 -0800

    Fix rebalancing when 2+ of a partition's replicas are on deleted devices.

    RingBuilder._reassign_parts assumed that only replica for a given
    partition would move. This isn't necessarily true in the case where a
    bunch of devices have been removed. This would leave invalid entries
    in _replica2part2dev and also cause validation to fail.

    One easy way to reproduce this is to create a 3-replica, 3-zone,
    6-device ring with 2 drives per zone (all of equal weight), rebalance,
    and then remove one drive from each zone and rebalance again.

    Bug: 943493

    Change-Id: I0d399bed5d733448ad877fa2823b542777d385a4