[openstack-dev] [Ironic] (Non-)consistency of the Ironic hash ring implementation

Nejc Saje nsaje at redhat.com
Wed Sep 3 11:50:01 UTC 2014



On 09/02/2014 11:33 PM, Robert Collins wrote:
> The implementation in ceilometer is very different to the Ironic one -
> are you saying the test you linked fails with Ironic, or that it fails
> with the ceilometer code today?

Disclaimer: in Ironic terms, node = conductor, key = host

The test I linked fails with Ironic hash ring code (specifically the 
part that tests consistency). With 1000 keys being mapped to 10 nodes, 
when you add a node:
- current ceilometer code remaps around 7% of the keys (< 1/#nodes)
- Ironic code remaps > 90% of the keys

The problem lies in the way you build your hash ring[1]. You initialize 
a statically-sized array and divide its fields among nodes. When you do 
a lookup, you check which field in the array the key hashes to and then 
return the node that that field belongs to. This is the wrong approach 
because when you add a new node, you will resize the array and assign 
the fields differently, but the same key will still hash to the same 
field and will therefore hash to a different node.

Nodes must be hashed onto the ring as well, statically chopping up the 
ring and dividing it among nodes isn't enough for consistency.

Cheers,
Nejc

>
> The Ironic hash_ring implementation uses a hash:
>      def _get_partition(self, data):
>          try:
>              return (struct.unpack_from('>I', hashlib.md5(data).digest())[0]
>                      >> self.partition_shift)
>          except TypeError:
>              raise exception.Invalid(
>                      _("Invalid data supplied to HashRing.get_hosts."))
>
>
> so I don't see the fixed size thing you're referring to. Could you
> point a little more specifically? Thanks!
>
> -Rob
>
> On 1 September 2014 19:48, Nejc Saje <nsaje at redhat.com> wrote:
>> Hey guys,
>>
>> in Ceilometer we're using consistent hash rings to do workload
>> partitioning[1]. We've considered generalizing your hash ring implementation
>> and moving it up to oslo, but unfortunately your implementation is not
>> actually consistent, which is our requirement.
>>
>> Since you divide your ring into a number of equal sized partitions, instead
>> of hashing hosts onto the ring, when you add a new host,
>> an unbound amount of keys get re-mapped to different hosts (instead of the
>> 1/#nodes remapping guaranteed by hash ring). I've confirmed this with the
>> test in aforementioned patch[2].
>>
>> If this is good enough for your use-case, great, otherwise we can get a
>> generalized hash ring implementation into oslo for use in both projects or
>> we can both use an external library[3].
>>
>> Cheers,
>> Nejc
>>
>> [1] https://review.openstack.org/#/c/113549/
>> [2]
>> https://review.openstack.org/#/c/113549/21/ceilometer/tests/test_utils.py
>> [3] https://pypi.python.org/pypi/hash_ring
>>
>> _______________________________________________
>> OpenStack-dev mailing list
>> OpenStack-dev at lists.openstack.org
>> http://lists.openstack.org/cgi-bin/mailman/listinfo/openstack-dev
>
>
>



More information about the OpenStack-dev mailing list