diff options
Diffstat (limited to 'ironic')
| -rw-r--r-- | ironic/common/hash_ring.py | 85 | ||||
| -rw-r--r-- | ironic/tests/test_hash_ring.py | 107 |
2 files changed, 192 insertions, 0 deletions
diff --git a/ironic/common/hash_ring.py b/ironic/common/hash_ring.py new file mode 100644 index 000000000..008ee9781 --- /dev/null +++ b/ironic/common/hash_ring.py @@ -0,0 +1,85 @@ +# vim: tabstop=4 shiftwidth=4 softtabstop=4 + +# Copyright 2013 Hewlett-Packard Development Company, L.P. +# All Rights Reserved. +# +# Licensed under the Apache License, Version 2.0 (the "License"); you may +# not use this file except in compliance with the License. You may obtain +# a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, WITHOUT +# WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the +# License for the specific language governing permissions and limitations +# under the License. + +import array +import hashlib +import struct + +from oslo.config import cfg + +hash_opts = [ + cfg.IntOpt('hash_partition_exponent', + default=16, + help='Exponent to determine number of hash partitions to use ' + 'when distributing load across conductors.'), +] + +CONF = cfg.CONF +CONF.register_opts(hash_opts) + + +class HashRing(object): + + def __init__(self, hosts, replicas=1): + """Create a new hash ring across the specified hosts. + + :param hosts: array of hosts which will be mapped + :param replicas: number of replicas. Default: 1 + + """ + self.hosts = hosts + self.replicas = replicas + self.partition_shift = 32 - CONF.hash_partition_exponent + self.part2host = array.array('H') + for p in xrange(2 ** CONF.hash_partition_exponent): + self.part2host.append(p % len(hosts)) + + def _get_partition(self, data): + return (struct.unpack_from('>I', hashlib.md5(data).digest())[0] + >> self.partition_shift) + + def get_hosts(self, data, ignore_hosts=None): + """Get the list of hosts which the supplied data maps onto. + + :param data: A string identifier to be mapped across the ring. + :param ignore_hosts: A list of hosts to skip when performing the hash. + Useful to temporarily skip down hosts without + performing a full rebalance. + Default: None. + :returns: a list of hosts. + The length of this list depends on the number of replicas + this `HashRing` was created with. It may be less than this + if ignore_hosts is not None. + """ + host_ids = [] + if ignore_hosts is None: + ignore_host_ids = [] + else: + ignore_host_ids = [self.hosts.index(h) + for h in ignore_hosts if h in self.hosts] + + partition = self._get_partition(data) + for replica in xrange(0, self.replicas): + if len(host_ids + ignore_host_ids) == len(self.hosts): + # prevent infinite loop + break + while self.part2host[partition] in host_ids + ignore_host_ids: + partition += 1 + if partition >= len(self.part2host): + partition = 0 + host_ids.append(self.part2host[partition]) + return [self.hosts[h] for h in host_ids] diff --git a/ironic/tests/test_hash_ring.py b/ironic/tests/test_hash_ring.py new file mode 100644 index 000000000..3bf407def --- /dev/null +++ b/ironic/tests/test_hash_ring.py @@ -0,0 +1,107 @@ +# vim: tabstop=4 shiftwidth=4 softtabstop=4 + +# Copyright 2013 Hewlett-Packard Development Company, L.P. +# All Rights Reserved. +# +# Licensed under the Apache License, Version 2.0 (the "License"); you may +# not use this file except in compliance with the License. You may obtain +# a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, WITHOUT +# WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the +# License for the specific language governing permissions and limitations +# under the License. + +from oslo.config import cfg + +from ironic.common import hash_ring as hash +from ironic.tests import base + +CONF = cfg.CONF + + +class HashRingTestCase(base.TestCase): + + # NOTE(deva): the mapping used in these tests is as follows: + # if hosts = [foo, bar]: + # fake -> foo, bar + # if hosts = [foo, bar, baz]: + # fake -> foo, bar, baz + # fake-again -> bar, baz, foo + + def test_create_ring(self): + hosts = ['foo', 'bar'] + replicas = 2 + ring = hash.HashRing(hosts, replicas=replicas) + self.assertEqual(hosts, ring.hosts) + self.assertEqual(replicas, ring.replicas) + + def test_create_with_different_partition_counts(self): + hosts = ['foo', 'bar'] + CONF.set_override('hash_partition_exponent', 2) + ring = hash.HashRing(hosts) + self.assertEqual(2 ** 2, len(ring.part2host)) + + CONF.set_override('hash_partition_exponent', 8) + ring = hash.HashRing(hosts) + self.assertEqual(2 ** 8, len(ring.part2host)) + + CONF.set_override('hash_partition_exponent', 16) + ring = hash.HashRing(hosts) + self.assertEqual(2 ** 16, len(ring.part2host)) + + def test_distribution_one_replica(self): + hosts = ['foo', 'bar', 'baz'] + ring = hash.HashRing(hosts, replicas=1) + self.assertEqual(['foo'], ring.get_hosts('fake')) + self.assertEqual(['bar'], ring.get_hosts('fake-again')) + + def test_distribution_two_replicas(self): + hosts = ['foo', 'bar', 'baz'] + ring = hash.HashRing(hosts, replicas=2) + self.assertEqual(['foo', 'bar'], ring.get_hosts('fake')) + self.assertEqual(['bar', 'baz'], ring.get_hosts('fake-again')) + + def test_distribution_three_replicas(self): + hosts = ['foo', 'bar', 'baz'] + ring = hash.HashRing(hosts, replicas=3) + self.assertEqual(['foo', 'bar', 'baz'], ring.get_hosts('fake')) + self.assertEqual(['bar', 'baz', 'foo'], ring.get_hosts('fake-again')) + + def test_ignore_hosts(self): + hosts = ['foo', 'bar', 'baz'] + ring = hash.HashRing(hosts) + self.assertEqual(['bar'], ring.get_hosts('fake', + ignore_hosts=['foo'])) + self.assertEqual(['baz'], ring.get_hosts('fake', + ignore_hosts=['foo', 'bar'])) + self.assertEqual([], ring.get_hosts('fake', + ignore_hosts=hosts)) + + def test_ignore_hosts_with_replicas(self): + hosts = ['foo', 'bar', 'baz'] + ring = hash.HashRing(hosts, replicas=2) + self.assertEqual(['bar', 'baz'], ring.get_hosts('fake', + ignore_hosts=['foo'])) + self.assertEqual(['baz'], ring.get_hosts('fake', + ignore_hosts=['foo', 'bar'])) + self.assertEqual(['baz', 'foo'], ring.get_hosts('fake-again', + ignore_hosts=['bar'])) + self.assertEqual(['foo'], ring.get_hosts('fake-again', + ignore_hosts=['bar', 'baz'])) + self.assertEqual([], ring.get_hosts('fake', + ignore_hosts=hosts)) + + def test_more_replicas_than_hosts(self): + hosts = ['foo', 'bar'] + ring = hash.HashRing(hosts, replicas=10) + self.assertEqual(hosts, ring.get_hosts('fake')) + + def test_ignore_non_existent_host(self): + hosts = ['foo', 'bar'] + ring = hash.HashRing(hosts) + self.assertEqual(['foo'], ring.get_hosts('fake', + ignore_hosts=['baz'])) |