Implement consistent hashing common methods

Implement consistent hashing functions and add unit tests.

These will be used by each conductor service to determine
which nodes it is responsible for, and by each API service
to determine where to route RPC requests for specific nodes.

Change-Id: I6d6ae987e76e2d11f8f3f8843800a17d8ff1aaa0
bp: instance-mapping-by-consistent-hash

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']))