Represent dispersion worse than one replicanth
With a sufficiently undispersed ring it's possible to move an entire replicas worth of parts and yet the value of dispersion may not get any better (even though in reality dispersion has dramatically improved). The problem is dispersion will currently only represent up to one whole replica worth of parts being undispersed. However with EC rings it's possible for more than one whole replicas worth of partitions to be undispersed, in these cases the builder will require multiple rebalance operations to fully disperse replicas - but the dispersion value should improve with every rebalance. N.B. with this change it's possible for rings with a bad dispersion value to measure as having a significantly smaller dispersion value after a rebalance (even though they may not have had their dispersion change) because the total amount of bad dispersion we can measure has been increased but we're normalizing within a similar range. Closes-Bug: #1697543 Change-Id: Ifefff0260deac0c3e8b369a1e158686c89936686
This commit is contained in:
Clay Gerrard
parent
aa82d2cba8
commit
7013e70ca6
|
|
@ -120,25 +120,24 @@ out were you need to add capacity or to help tune an :ref:`ring_overload` value.
|
|||
Now let's take an example with 1 region, 3 zones and 4 devices. Each device has
|
||||
the same weight, and the ``dispersion --verbose`` might show the following::
|
||||
|
||||
Dispersion is 50.000000, Balance is 0.000000, Overload is 0.00%
|
||||
Dispersion is 16.666667, Balance is 0.000000, Overload is 0.00%
|
||||
Required overload is 33.333333%
|
||||
Worst tier is 50.000000 (r1z3)
|
||||
Worst tier is 33.333333 (r1z3)
|
||||
--------------------------------------------------------------------------
|
||||
Tier Parts % Max 0 1 2 3
|
||||
--------------------------------------------------------------------------
|
||||
r1 256 0.00 3 0 0 0 256
|
||||
r1 768 0.00 3 0 0 0 256
|
||||
r1z1 192 0.00 1 64 192 0 0
|
||||
r1z1-127.0.0.1 192 0.00 1 64 192 0 0
|
||||
r1z1-127.0.0.1/sda 192 0.00 1 64 192 0 0
|
||||
r1z2 192 0.00 1 64 192 0 0
|
||||
r1z2-127.0.0.2 192 0.00 1 64 192 0 0
|
||||
r1z2-127.0.0.2/sda 192 0.00 1 64 192 0 0
|
||||
r1z3 256 50.00 1 0 128 128 0
|
||||
r1z3-127.0.0.3 256 50.00 1 0 128 128 0
|
||||
r1z3 384 33.33 1 0 128 128 0
|
||||
r1z3-127.0.0.3 384 33.33 1 0 128 128 0
|
||||
r1z3-127.0.0.3/sda 192 0.00 1 64 192 0 0
|
||||
r1z3-127.0.0.3/sdb 192 0.00 1 64 192 0 0
|
||||
|
||||
|
||||
The first line reports that there are 256 partitions with 3 copies in region 1;
|
||||
and this is an expected output in this case (single region with 3 replicas) as
|
||||
reported by the "Max" value.
|
||||
|
|
|
|||
|
|
@ -623,22 +623,22 @@ class RingBuilder(object):
|
|||
|
||||
if old_device != dev['id']:
|
||||
changed_parts += 1
|
||||
part_at_risk = False
|
||||
# update running totals for each tiers' number of parts with a
|
||||
# given replica count
|
||||
part_risk_depth = defaultdict(int)
|
||||
part_risk_depth[0] = 0
|
||||
for tier, replicas in replicas_at_tier.items():
|
||||
if tier not in dispersion_graph:
|
||||
dispersion_graph[tier] = [self.parts] + [0] * int_replicas
|
||||
dispersion_graph[tier][0] -= 1
|
||||
dispersion_graph[tier][replicas] += 1
|
||||
if replicas > max_allowed_replicas[tier]:
|
||||
part_at_risk = True
|
||||
# this part may be at risk in multiple tiers, but we only count it
|
||||
# as at_risk once
|
||||
if part_at_risk:
|
||||
parts_at_risk += 1
|
||||
part_risk_depth[len(tier)] += (
|
||||
replicas - max_allowed_replicas[tier])
|
||||
# count each part-replica once at tier where dispersion is worst
|
||||
parts_at_risk += max(part_risk_depth.values())
|
||||
self._dispersion_graph = dispersion_graph
|
||||
self.dispersion = 100.0 * parts_at_risk / self.parts
|
||||
self.dispersion = 100.0 * parts_at_risk / (self.parts * self.replicas)
|
||||
return changed_parts
|
||||
|
||||
def validate(self, stats=False):
|
||||
|
|
|
|||
|
|
@ -618,8 +618,11 @@ def dispersion_report(builder, search_filter=None, verbose=False):
|
|||
if search_filter and not re.match(search_filter, tier_name):
|
||||
continue
|
||||
max_replicas = int(max_allowed_replicas[tier])
|
||||
at_risk_parts = sum(replica_counts[max_replicas + 1:])
|
||||
placed_parts = sum(replica_counts[1:])
|
||||
at_risk_parts = sum(replica_counts[i] * (i - max_replicas)
|
||||
for i in range(max_replicas + 1,
|
||||
len(replica_counts)))
|
||||
placed_parts = sum(replica_counts[i] * i for i in range(
|
||||
1, len(replica_counts)))
|
||||
tier_dispersion = 100.0 * at_risk_parts / placed_parts
|
||||
if tier_dispersion > max_dispersion:
|
||||
max_dispersion = tier_dispersion
|
||||
|
|
|
|||
|
|
@ -1927,74 +1927,41 @@ class TestCommands(unittest.TestCase, RunSwiftRingBuilderMixin):
|
|||
# device won't acquire any partitions, so the ring's balance won't
|
||||
# change. However, dispersion will improve.
|
||||
|
||||
ring = RingBuilder(6, 5, 1)
|
||||
ring.add_dev({
|
||||
'region': 1, 'zone': 1,
|
||||
'ip': '10.0.0.1', 'port': 20001, 'weight': 1000,
|
||||
'device': 'sda'})
|
||||
ring.add_dev({
|
||||
'region': 1, 'zone': 1,
|
||||
'ip': '10.0.0.1', 'port': 20001, 'weight': 1000,
|
||||
'device': 'sdb'})
|
||||
ring.add_dev({
|
||||
'region': 1, 'zone': 1,
|
||||
'ip': '10.0.0.1', 'port': 20001, 'weight': 1000,
|
||||
'device': 'sdc'})
|
||||
ring.add_dev({
|
||||
'region': 1, 'zone': 1,
|
||||
'ip': '10.0.0.1', 'port': 20001, 'weight': 1000,
|
||||
'device': 'sdd'})
|
||||
ring.add_dev({
|
||||
'region': 1, 'zone': 1,
|
||||
'ip': '10.0.0.1', 'port': 20001, 'weight': 1000,
|
||||
'device': 'sde'})
|
||||
ring = RingBuilder(6, 6, 1)
|
||||
devs = ('d%s' % i for i in itertools.count())
|
||||
for i in range(6):
|
||||
ring.add_dev({
|
||||
'region': 1, 'zone': 1,
|
||||
'ip': '10.0.0.1', 'port': 20001, 'weight': 1000,
|
||||
'device': next(devs)})
|
||||
ring.rebalance()
|
||||
|
||||
# The last guy in zone 1
|
||||
ring.add_dev({
|
||||
'region': 1, 'zone': 1,
|
||||
'ip': '10.0.0.1', 'port': 20001, 'weight': 1000,
|
||||
'device': 'sdf'})
|
||||
'device': next(devs)})
|
||||
|
||||
# Add zone 2 (same total weight as zone 1)
|
||||
ring.add_dev({
|
||||
'region': 1, 'zone': 2,
|
||||
'ip': '10.0.0.2', 'port': 20001, 'weight': 1000,
|
||||
'device': 'sda'})
|
||||
ring.add_dev({
|
||||
'region': 1, 'zone': 2,
|
||||
'ip': '10.0.0.2', 'port': 20001, 'weight': 1000,
|
||||
'device': 'sdb'})
|
||||
ring.add_dev({
|
||||
'region': 1, 'zone': 2,
|
||||
'ip': '10.0.0.2', 'port': 20001, 'weight': 1000,
|
||||
'device': 'sdc'})
|
||||
ring.add_dev({
|
||||
'region': 1, 'zone': 2,
|
||||
'ip': '10.0.0.2', 'port': 20001, 'weight': 1000,
|
||||
'device': 'sdd'})
|
||||
ring.add_dev({
|
||||
'region': 1, 'zone': 2,
|
||||
'ip': '10.0.0.2', 'port': 20001, 'weight': 1000,
|
||||
'device': 'sde'})
|
||||
ring.add_dev({
|
||||
'region': 1, 'zone': 2,
|
||||
'ip': '10.0.0.2', 'port': 20001, 'weight': 1000,
|
||||
'device': 'sdf'})
|
||||
for i in range(7):
|
||||
ring.add_dev({
|
||||
'region': 1, 'zone': 2,
|
||||
'ip': '10.0.0.2', 'port': 20001, 'weight': 1000,
|
||||
'device': next(devs)})
|
||||
ring.pretend_min_part_hours_passed()
|
||||
ring.save(self.tmpfile)
|
||||
del ring
|
||||
|
||||
# Rebalance once: this gets 1/5 replica into zone 2; the ring is
|
||||
# Rebalance once: this gets 1/6th replica into zone 2; the ring is
|
||||
# saved because devices changed.
|
||||
argv = ["", self.tmpfile, "rebalance", "5759339"]
|
||||
self.assertSystemExit(EXIT_WARNING, ringbuilder.main, argv)
|
||||
rb = RingBuilder.load(self.tmpfile)
|
||||
self.assertEqual(rb.dispersion, 100)
|
||||
self.assertEqual(rb.dispersion, 33.333333333333336)
|
||||
self.assertEqual(rb.get_balance(), 100)
|
||||
self.run_srb('pretend_min_part_hours_passed')
|
||||
|
||||
# Rebalance again: this gets 2/5 replica into zone 2, but no devices
|
||||
# Rebalance again: this gets 2/6th replica into zone 2, but no devices
|
||||
# changed and the balance stays the same. The only improvement is
|
||||
# dispersion.
|
||||
|
||||
|
|
@ -2009,7 +1976,7 @@ class TestCommands(unittest.TestCase, RunSwiftRingBuilderMixin):
|
|||
with mock.patch('swift.common.ring.RingBuilder.save', capture_save):
|
||||
self.assertSystemExit(EXIT_WARNING, ringbuilder.main, argv)
|
||||
self.assertEqual(captured, {
|
||||
'dispersion': 0,
|
||||
'dispersion': 16.666666666666668,
|
||||
'balance': 100,
|
||||
})
|
||||
|
||||
|
|
|
|||
|
|
@ -27,6 +27,7 @@ from tempfile import mkdtemp
|
|||
from shutil import rmtree
|
||||
import random
|
||||
import uuid
|
||||
import itertools
|
||||
|
||||
from six.moves import range
|
||||
|
||||
|
|
@ -36,6 +37,16 @@ from swift.common.ring import utils
|
|||
from swift.common.ring.builder import MAX_BALANCE
|
||||
|
||||
|
||||
def _partition_counts(builder, key='id'):
|
||||
"""
|
||||
Returns a dictionary mapping the given device key to (number of
|
||||
partitions assigned to that key).
|
||||
"""
|
||||
return Counter(builder.devs[dev_id][key]
|
||||
for part2dev_id in builder._replica2part2dev
|
||||
for dev_id in part2dev_id)
|
||||
|
||||
|
||||
class TestRingBuilder(unittest.TestCase):
|
||||
|
||||
def setUp(self):
|
||||
|
|
@ -44,21 +55,12 @@ class TestRingBuilder(unittest.TestCase):
|
|||
def tearDown(self):
|
||||
rmtree(self.testdir, ignore_errors=1)
|
||||
|
||||
def _partition_counts(self, builder, key='id'):
|
||||
"""
|
||||
Returns a dictionary mapping the given device key to (number of
|
||||
partitions assigned to that key).
|
||||
"""
|
||||
return Counter(builder.devs[dev_id][key]
|
||||
for part2dev_id in builder._replica2part2dev
|
||||
for dev_id in part2dev_id)
|
||||
|
||||
def _get_population_by_region(self, builder):
|
||||
"""
|
||||
Returns a dictionary mapping region to number of partitions in that
|
||||
region.
|
||||
"""
|
||||
return self._partition_counts(builder, key='region')
|
||||
return _partition_counts(builder, key='region')
|
||||
|
||||
def test_init(self):
|
||||
rb = ring.RingBuilder(8, 3, 1)
|
||||
|
|
@ -320,7 +322,7 @@ class TestRingBuilder(unittest.TestCase):
|
|||
'port': 10000 + region * 100 + zone,
|
||||
'device': 'sda%d' % dev_id})
|
||||
rb.rebalance()
|
||||
self.assertEqual(self._partition_counts(rb, 'zone'),
|
||||
self.assertEqual(_partition_counts(rb, 'zone'),
|
||||
{0: 256, 10: 256, 11: 256})
|
||||
wanted_by_zone = defaultdict(lambda: defaultdict(int))
|
||||
for dev in rb._iter_devs():
|
||||
|
|
@ -777,7 +779,7 @@ class TestRingBuilder(unittest.TestCase):
|
|||
# replica should have been moved, therefore we expect 256 parts in zone
|
||||
# 0 and 1, and a total of 256 in zone 2,3, and 4
|
||||
expected = defaultdict(int, {0: 256, 1: 256, 2: 86, 3: 85, 4: 85})
|
||||
self.assertEqual(expected, self._partition_counts(rb, key='zone'))
|
||||
self.assertEqual(expected, _partition_counts(rb, key='zone'))
|
||||
|
||||
zone_histogram = defaultdict(int)
|
||||
for part in range(rb.parts):
|
||||
|
|
@ -804,7 +806,7 @@ class TestRingBuilder(unittest.TestCase):
|
|||
self.assertAlmostEqual(rb.get_balance(), 0, delta=0.5)
|
||||
|
||||
# every zone has either 153 or 154 parts
|
||||
for zone, count in self._partition_counts(
|
||||
for zone, count in _partition_counts(
|
||||
rb, key='zone').items():
|
||||
self.assertAlmostEqual(153.5, count, delta=1)
|
||||
|
||||
|
|
@ -872,18 +874,18 @@ class TestRingBuilder(unittest.TestCase):
|
|||
self.assertFalse(rb.ever_rebalanced)
|
||||
rb.rebalance()
|
||||
self.assertTrue(rb.ever_rebalanced)
|
||||
counts = self._partition_counts(rb)
|
||||
counts = _partition_counts(rb)
|
||||
self.assertEqual(counts, {0: 256, 1: 256, 2: 256})
|
||||
rb.add_dev({'id': 3, 'region': 0, 'zone': 3, 'weight': 1,
|
||||
'ip': '127.0.0.1', 'port': 10003, 'device': 'sda1'})
|
||||
rb.pretend_min_part_hours_passed()
|
||||
rb.rebalance()
|
||||
self.assertTrue(rb.ever_rebalanced)
|
||||
counts = self._partition_counts(rb)
|
||||
counts = _partition_counts(rb)
|
||||
self.assertEqual(counts, {0: 192, 1: 192, 2: 192, 3: 192})
|
||||
rb.set_dev_weight(3, 100)
|
||||
rb.rebalance()
|
||||
counts = self._partition_counts(rb)
|
||||
counts = _partition_counts(rb)
|
||||
self.assertEqual(counts[3], 256)
|
||||
|
||||
def test_add_rebalance_add_rebalance_delete_rebalance(self):
|
||||
|
|
@ -1632,7 +1634,7 @@ class TestRingBuilder(unittest.TestCase):
|
|||
rb.validate()
|
||||
|
||||
# sanity check: balance respects weights, so default
|
||||
part_counts = self._partition_counts(rb, key='zone')
|
||||
part_counts = _partition_counts(rb, key='zone')
|
||||
self.assertEqual(part_counts[0], 192)
|
||||
self.assertEqual(part_counts[1], 192)
|
||||
self.assertEqual(part_counts[2], 384)
|
||||
|
|
@ -1643,7 +1645,7 @@ class TestRingBuilder(unittest.TestCase):
|
|||
rb.pretend_min_part_hours_passed()
|
||||
rb.rebalance(seed=12345)
|
||||
|
||||
part_counts = self._partition_counts(rb, key='zone')
|
||||
part_counts = _partition_counts(rb, key='zone')
|
||||
self.assertEqual({0: 212, 1: 211, 2: 345}, part_counts)
|
||||
|
||||
# Now, devices 0 and 1 take 50% more than their fair shares by
|
||||
|
|
@ -1653,7 +1655,7 @@ class TestRingBuilder(unittest.TestCase):
|
|||
rb.pretend_min_part_hours_passed()
|
||||
rb.rebalance(seed=12345)
|
||||
|
||||
part_counts = self._partition_counts(rb, key='zone')
|
||||
part_counts = _partition_counts(rb, key='zone')
|
||||
self.assertEqual({0: 256, 1: 256, 2: 256}, part_counts)
|
||||
|
||||
# Devices 0 and 1 may take up to 75% over their fair share, but the
|
||||
|
|
@ -1664,7 +1666,7 @@ class TestRingBuilder(unittest.TestCase):
|
|||
rb.pretend_min_part_hours_passed()
|
||||
rb.rebalance(seed=12345)
|
||||
|
||||
part_counts = self._partition_counts(rb, key='zone')
|
||||
part_counts = _partition_counts(rb, key='zone')
|
||||
self.assertEqual(part_counts[0], 256)
|
||||
self.assertEqual(part_counts[1], 256)
|
||||
self.assertEqual(part_counts[2], 256)
|
||||
|
|
@ -1704,7 +1706,7 @@ class TestRingBuilder(unittest.TestCase):
|
|||
rb.rebalance(seed=12345)
|
||||
|
||||
# sanity check: our overload is big enough to balance things
|
||||
part_counts = self._partition_counts(rb, key='ip')
|
||||
part_counts = _partition_counts(rb, key='ip')
|
||||
self.assertEqual(part_counts['127.0.0.1'], 216)
|
||||
self.assertEqual(part_counts['127.0.0.2'], 216)
|
||||
self.assertEqual(part_counts['127.0.0.3'], 336)
|
||||
|
|
@ -1716,7 +1718,7 @@ class TestRingBuilder(unittest.TestCase):
|
|||
rb.pretend_min_part_hours_passed()
|
||||
rb.rebalance(seed=12345)
|
||||
|
||||
part_counts = self._partition_counts(rb, key='ip')
|
||||
part_counts = _partition_counts(rb, key='ip')
|
||||
|
||||
self.assertEqual({
|
||||
'127.0.0.1': 237,
|
||||
|
|
@ -1732,7 +1734,7 @@ class TestRingBuilder(unittest.TestCase):
|
|||
rb.pretend_min_part_hours_passed()
|
||||
rb.rebalance(seed=12345)
|
||||
|
||||
part_counts = self._partition_counts(rb, key='ip')
|
||||
part_counts = _partition_counts(rb, key='ip')
|
||||
self.assertEqual(part_counts['127.0.0.1'], 256)
|
||||
self.assertEqual(part_counts['127.0.0.2'], 256)
|
||||
self.assertEqual(part_counts['127.0.0.3'], 256)
|
||||
|
|
@ -1765,7 +1767,7 @@ class TestRingBuilder(unittest.TestCase):
|
|||
'127.0.0.4': 192,
|
||||
}
|
||||
|
||||
part_counts = self._partition_counts(rb, key='ip')
|
||||
part_counts = _partition_counts(rb, key='ip')
|
||||
self.assertEqual(part_counts, expected)
|
||||
|
||||
def test_overload_keeps_balanceable_things_balanced_initially(self):
|
||||
|
|
@ -1798,7 +1800,7 @@ class TestRingBuilder(unittest.TestCase):
|
|||
rb.set_overload(99999)
|
||||
rb.rebalance(seed=12345)
|
||||
|
||||
part_counts = self._partition_counts(rb)
|
||||
part_counts = _partition_counts(rb)
|
||||
self.assertEqual(part_counts, {
|
||||
0: 128,
|
||||
1: 128,
|
||||
|
|
@ -1842,7 +1844,7 @@ class TestRingBuilder(unittest.TestCase):
|
|||
rb.set_overload(99999)
|
||||
|
||||
rb.rebalance(seed=123)
|
||||
part_counts = self._partition_counts(rb)
|
||||
part_counts = _partition_counts(rb)
|
||||
self.assertEqual(part_counts, {
|
||||
0: 128,
|
||||
1: 128,
|
||||
|
|
@ -1863,7 +1865,7 @@ class TestRingBuilder(unittest.TestCase):
|
|||
rb.set_dev_weight(1, 8)
|
||||
|
||||
rb.rebalance(seed=456)
|
||||
part_counts = self._partition_counts(rb)
|
||||
part_counts = _partition_counts(rb)
|
||||
self.assertEqual(part_counts, {
|
||||
0: 128,
|
||||
1: 128,
|
||||
|
|
@ -2268,7 +2270,7 @@ class TestRingBuilder(unittest.TestCase):
|
|||
self.assertRaises(exceptions.RingValidationError, rb.validate)
|
||||
|
||||
rb.rebalance()
|
||||
counts = self._partition_counts(rb, key='zone')
|
||||
counts = _partition_counts(rb, key='zone')
|
||||
self.assertEqual(counts, {0: 128, 1: 128, 2: 256, 3: 256})
|
||||
|
||||
dev_usage, worst = rb.validate()
|
||||
|
|
@ -2450,7 +2452,7 @@ class TestRingBuilder(unittest.TestCase):
|
|||
# we'll rebalance but can't move any parts
|
||||
rb.rebalance(seed=1)
|
||||
# zero weight tier has one copy of 1/4 part-replica
|
||||
self.assertEqual(rb.dispersion, 75.0)
|
||||
self.assertEqual(rb.dispersion, 25.0)
|
||||
self.assertEqual(rb._dispersion_graph, {
|
||||
(0,): [0, 0, 0, 256],
|
||||
(0, 0): [0, 0, 0, 256],
|
||||
|
|
@ -2509,7 +2511,7 @@ class TestRingBuilder(unittest.TestCase):
|
|||
# so the first time, rings are still unbalanced becase we'll only move
|
||||
# one replica of each part.
|
||||
self.assertEqual(rb.get_balance(), 50.1953125)
|
||||
self.assertEqual(rb.dispersion, 99.609375)
|
||||
self.assertEqual(rb.dispersion, 16.6015625)
|
||||
|
||||
# N.B. since we mostly end up grabbing parts by "weight forced" some
|
||||
# seeds given some specific ring state will randomly pick bad
|
||||
|
|
@ -2519,14 +2521,14 @@ class TestRingBuilder(unittest.TestCase):
|
|||
# ... this isn't a really "desirable" behavior, but even with bad luck,
|
||||
# things do get better
|
||||
self.assertEqual(rb.get_balance(), 47.265625)
|
||||
self.assertEqual(rb.dispersion, 99.609375)
|
||||
self.assertEqual(rb.dispersion, 16.6015625)
|
||||
|
||||
# but if you stick with it, eventually the next rebalance, will get to
|
||||
# move "the right" part-replicas, resulting in near optimal balance
|
||||
changed_part, _, _ = rb.rebalance(seed=7)
|
||||
self.assertEqual(changed_part, 240)
|
||||
self.assertEqual(rb.get_balance(), 0.390625)
|
||||
self.assertEqual(rb.dispersion, 99.609375)
|
||||
self.assertEqual(rb.dispersion, 16.6015625)
|
||||
|
||||
def test_undispersable_server_converge_on_balance(self):
|
||||
rb = ring.RingBuilder(8, 6, 0)
|
||||
|
|
@ -2562,7 +2564,7 @@ class TestRingBuilder(unittest.TestCase):
|
|||
# but the first time, those are still unbalance becase ring builder
|
||||
# can move only one replica for each part
|
||||
self.assertEqual(rb.get_balance(), 16.9921875)
|
||||
self.assertEqual(rb.dispersion, 59.765625)
|
||||
self.assertEqual(rb.dispersion, 9.9609375)
|
||||
|
||||
rb.rebalance(seed=7)
|
||||
|
||||
|
|
@ -2570,7 +2572,7 @@ class TestRingBuilder(unittest.TestCase):
|
|||
self.assertGreaterEqual(rb.get_balance(), 0)
|
||||
self.assertLess(rb.get_balance(), 1)
|
||||
# dispersion doesn't get any worse
|
||||
self.assertEqual(rb.dispersion, 59.765625)
|
||||
self.assertEqual(rb.dispersion, 9.9609375)
|
||||
|
||||
def test_effective_overload(self):
|
||||
rb = ring.RingBuilder(8, 3, 1)
|
||||
|
|
@ -3623,7 +3625,7 @@ class TestGetRequiredOverload(unittest.TestCase):
|
|||
# when overload can not change the outcome none is required
|
||||
self.assertEqual(0.0, rb.get_required_overload())
|
||||
# even though dispersion is terrible (in z1 particularly)
|
||||
self.assertEqual(100.0, rb.dispersion)
|
||||
self.assertEqual(20.0, rb.dispersion)
|
||||
|
||||
def test_one_big_guy_does_not_spoil_his_buddy(self):
|
||||
rb = ring.RingBuilder(8, 3, 0)
|
||||
|
|
@ -4358,5 +4360,148 @@ class TestGetRequiredOverload(unittest.TestCase):
|
|||
wr.items() if len(t) == tier_len})
|
||||
|
||||
|
||||
class TestRingBuilderDispersion(unittest.TestCase):
|
||||
|
||||
def setUp(self):
|
||||
self.devs = ('d%s' % i for i in itertools.count())
|
||||
|
||||
def assertAlmostPartCount(self, counts, expected, delta=3):
|
||||
msgs = []
|
||||
for k, p in sorted(expected.items()):
|
||||
try:
|
||||
self.assertAlmostEqual(counts[k], p, delta=delta)
|
||||
except KeyError:
|
||||
self.fail('%r is missing the key %r' % (counts, k))
|
||||
except AssertionError:
|
||||
msgs.append('parts in %s was %s expected %s' % (
|
||||
k, counts[k], p))
|
||||
if msgs:
|
||||
self.fail('part counts not close enough '
|
||||
'to expected:\n' + '\n'.join(msgs))
|
||||
|
||||
def test_rebalance_dispersion(self):
|
||||
rb = ring.RingBuilder(8, 6, 0)
|
||||
|
||||
for i in range(6):
|
||||
rb.add_dev({'region': 0, 'zone': 0, 'ip': '127.0.0.1',
|
||||
'port': 6000, 'weight': 1.0,
|
||||
'device': next(self.devs)})
|
||||
rb.rebalance()
|
||||
self.assertEqual(0, rb.dispersion)
|
||||
|
||||
for z in range(2):
|
||||
for i in range(6):
|
||||
rb.add_dev({'region': 0, 'zone': z + 1, 'ip': '127.0.1.1',
|
||||
'port': 6000, 'weight': 1.0,
|
||||
'device': next(self.devs)})
|
||||
|
||||
self.assertAlmostPartCount(_partition_counts(rb, 'zone'),
|
||||
{0: 1536, 1: 0, 2: 0})
|
||||
rb.rebalance()
|
||||
self.assertEqual(rb.dispersion, 50.0)
|
||||
expected = {0: 1280, 1: 128, 2: 128}
|
||||
self.assertAlmostPartCount(_partition_counts(rb, 'zone'),
|
||||
expected)
|
||||
report = dict(utils.dispersion_report(
|
||||
rb, r'r\d+z\d+$', verbose=True)['graph'])
|
||||
counts = {int(k.split('z')[1]): d['placed_parts']
|
||||
for k, d in report.items()}
|
||||
self.assertAlmostPartCount(counts, expected)
|
||||
rb.rebalance()
|
||||
self.assertEqual(rb.dispersion, 33.333333333333336)
|
||||
expected = {0: 1024, 1: 256, 2: 256}
|
||||
self.assertAlmostPartCount(_partition_counts(rb, 'zone'),
|
||||
expected)
|
||||
report = dict(utils.dispersion_report(
|
||||
rb, r'r\d+z\d+$', verbose=True)['graph'])
|
||||
counts = {int(k.split('z')[1]): d['placed_parts']
|
||||
for k, d in report.items()}
|
||||
self.assertAlmostPartCount(counts, expected)
|
||||
rb.rebalance()
|
||||
self.assertEqual(rb.dispersion, 16.666666666666668)
|
||||
expected = {0: 768, 1: 384, 2: 384}
|
||||
self.assertAlmostPartCount(_partition_counts(rb, 'zone'),
|
||||
expected)
|
||||
report = dict(utils.dispersion_report(
|
||||
rb, r'r\d+z\d+$', verbose=True)['graph'])
|
||||
counts = {int(k.split('z')[1]): d['placed_parts']
|
||||
for k, d in report.items()}
|
||||
self.assertAlmostPartCount(counts, expected)
|
||||
rb.rebalance()
|
||||
self.assertEqual(0, rb.dispersion)
|
||||
expected = {0: 512, 1: 512, 2: 512}
|
||||
self.assertAlmostPartCount(_partition_counts(rb, 'zone'), expected)
|
||||
report = dict(utils.dispersion_report(
|
||||
rb, r'r\d+z\d+$', verbose=True)['graph'])
|
||||
counts = {int(k.split('z')[1]): d['placed_parts']
|
||||
for k, d in report.items()}
|
||||
self.assertAlmostPartCount(counts, expected)
|
||||
|
||||
def test_weight_dispersion(self):
|
||||
rb = ring.RingBuilder(8, 3, 0)
|
||||
|
||||
for i in range(2):
|
||||
for d in range(3):
|
||||
rb.add_dev({'region': 0, 'zone': 0, 'ip': '127.0.%s.1' % i,
|
||||
'port': 6000, 'weight': 1.0,
|
||||
'device': next(self.devs)})
|
||||
for d in range(3):
|
||||
rb.add_dev({'region': 0, 'zone': 0, 'ip': '127.0.2.1',
|
||||
'port': 6000, 'weight': 10.0,
|
||||
'device': next(self.devs)})
|
||||
|
||||
rb.rebalance()
|
||||
# each tier should only have 1 replicanth, but the big server has 2
|
||||
# replicas of every part and 3 replicas another 1/2 - so our total
|
||||
# dispersion is greater than one replicanth, it's 1.5
|
||||
self.assertEqual(50.0, rb.dispersion)
|
||||
expected = {
|
||||
'127.0.0.1': 64,
|
||||
'127.0.1.1': 64,
|
||||
'127.0.2.1': 640,
|
||||
}
|
||||
self.assertAlmostPartCount(_partition_counts(rb, 'ip'),
|
||||
expected)
|
||||
report = dict(utils.dispersion_report(
|
||||
rb, r'r\d+z\d+-[^/]*$', verbose=True)['graph'])
|
||||
counts = {k.split('-')[1]: d['placed_parts']
|
||||
for k, d in report.items()}
|
||||
self.assertAlmostPartCount(counts, expected)
|
||||
|
||||
def test_multiple_tier_dispersion(self):
|
||||
rb = ring.RingBuilder(8, 8, 0)
|
||||
tiers = {
|
||||
(0, 0): 2,
|
||||
(1, 1): 1,
|
||||
(1, 2): 2,
|
||||
}
|
||||
ip_index = 0
|
||||
for (r, z), ip_count in tiers.items():
|
||||
for i in range(ip_count):
|
||||
ip_index += 1
|
||||
for d in range(3):
|
||||
rb.add_dev({'region': r, 'zone': z,
|
||||
'ip': '127.%s.%s.%s' % (r, z, ip_index),
|
||||
'port': 6000, 'weight': 1.0,
|
||||
'device': next(self.devs)})
|
||||
|
||||
rb.rebalance()
|
||||
self.assertAlmostEqual(15.52734375, rb.dispersion, delta=5.0)
|
||||
expected = {
|
||||
'127.1.2.1': 414,
|
||||
'127.1.2.2': 413,
|
||||
'127.0.0.3': 410,
|
||||
'127.0.0.4': 410,
|
||||
'127.1.1.5': 401,
|
||||
}
|
||||
self.assertAlmostPartCount(_partition_counts(rb, 'ip'), expected,
|
||||
delta=5)
|
||||
report = dict(utils.dispersion_report(
|
||||
rb, r'r\d+z\d+-[^/]*$', verbose=True)['graph'])
|
||||
counts = {k.split('-')[1]: d['placed_parts']
|
||||
for k, d in report.items()}
|
||||
self.assertAlmostPartCount(counts, expected, delta=5)
|
||||
|
||||
|
||||
if __name__ == '__main__':
|
||||
unittest.main()
|
||||
|
|
|
|||
|
|
@ -619,10 +619,10 @@ class TestUtils(unittest.TestCase):
|
|||
rb.rebalance(seed=100)
|
||||
rb.validate()
|
||||
|
||||
self.assertEqual(rb.dispersion, 55.46875)
|
||||
self.assertEqual(rb.dispersion, 18.489583333333332)
|
||||
report = dispersion_report(rb)
|
||||
self.assertEqual(report['worst_tier'], 'r1z1')
|
||||
self.assertEqual(report['max_dispersion'], 44.921875)
|
||||
self.assertEqual(report['worst_tier'], 'r1z1-127.0.0.1')
|
||||
self.assertEqual(report['max_dispersion'], 22.68370607028754)
|
||||
|
||||
def build_tier_report(max_replicas, placed_parts, dispersion,
|
||||
replicas):
|
||||
|
|
@ -633,17 +633,15 @@ class TestUtils(unittest.TestCase):
|
|||
'replicas': replicas,
|
||||
}
|
||||
|
||||
# Each node should store less than or equal to 256 partitions to
|
||||
# avoid multiple replicas.
|
||||
# 2/5 of total weight * 768 ~= 307 -> 51 partitions on each node in
|
||||
# zone 1 are stored at least twice on the nodes
|
||||
# every partition has at least two replicas in this zone, unfortunately
|
||||
# sometimes they're both on the same server.
|
||||
expected = [
|
||||
['r1z1', build_tier_report(
|
||||
2, 256, 44.921875, [0, 0, 141, 115])],
|
||||
2, 627, 18.341307814992025, [0, 0, 141, 115])],
|
||||
['r1z1-127.0.0.1', build_tier_report(
|
||||
1, 242, 29.33884297520661, [14, 171, 71, 0])],
|
||||
1, 313, 22.68370607028754, [14, 171, 71, 0])],
|
||||
['r1z1-127.0.0.2', build_tier_report(
|
||||
1, 243, 29.218106995884774, [13, 172, 71, 0])],
|
||||
1, 314, 22.611464968152866, [13, 172, 71, 0])],
|
||||
]
|
||||
report = dispersion_report(rb, 'r1z1[^/]*$', verbose=True)
|
||||
graph = report['graph']
|
||||
|
|
@ -668,15 +666,15 @@ class TestUtils(unittest.TestCase):
|
|||
# can't move all the part-replicas in one rebalance
|
||||
rb.rebalance(seed=100)
|
||||
report = dispersion_report(rb, verbose=True)
|
||||
self.assertEqual(rb.dispersion, 11.71875)
|
||||
self.assertEqual(rb.dispersion, 3.90625)
|
||||
self.assertEqual(report['worst_tier'], 'r1z1-127.0.0.2')
|
||||
self.assertEqual(report['max_dispersion'], 8.875739644970414)
|
||||
self.assertEqual(report['max_dispersion'], 8.152173913043478)
|
||||
# do a sencond rebalance
|
||||
rb.rebalance(seed=100)
|
||||
report = dispersion_report(rb, verbose=True)
|
||||
self.assertEqual(rb.dispersion, 50.0)
|
||||
self.assertEqual(rb.dispersion, 16.666666666666668)
|
||||
self.assertEqual(report['worst_tier'], 'r1z0-127.0.0.3')
|
||||
self.assertEqual(report['max_dispersion'], 50.0)
|
||||
self.assertEqual(report['max_dispersion'], 33.333333333333336)
|
||||
|
||||
# ... but overload can square it
|
||||
rb.set_overload(rb.get_required_overload())
|
||||
|
|
|
|||
Loading…
Reference in New Issue