[Sheepdog] The distribution of objects is not even enough ?

MORITA Kazutaka morita.kazutaka at gmail.com
Thu Apr 26 18:49:29 CEST 2012


On Thu, Apr 26, 2012 at 6:13 PM, Huxinwei <huxinwei at huawei.com> wrote:
>> -----Original Message-----
>> From: Liu Yuan [mailto:namei.unix at gmail.com]
>> Sent: Thursday, April 26, 2012 5:08 PM
>> To: Huxinwei
>> Cc: sheepdog at lists.wpkg.org
>> Subject: Re: [Sheepdog] The distribution of objects is not even enough ?
>>
>> On 04/26/2012 04:53 PM, Huxinwei wrote:
>>
>> > Hi list,
>> >
>> > I made some tests against the consistent hashing algorithm of
>> > sheepdog. Here are some samples: ============================
>> number
>> > of objects: 600000, replication is 3, total is 1800000 the cluster
>> > contains 100 nodes expecting 18000 objects per node acceptable
>> > variation is 600 (objects per node) With 2 (2.00 percent) nodes add,
>> > 33915 objects (1.88 percent) need to be relocated. 34.00 per is
>> > underload, with least as 14757 32.00 per is overload, with most as
>> > 23376
>> >
>> > number of objects: 600000, replication is 3, total is 1800000 the
>> > cluster contains 600 nodes expecting 3000 objects per node acceptable
>> > variation is 100 (objects per node) With 2 (0.00 percent) nodes add,
>> > 5881 objects (0.33 percent) need to be relocated. 33.00 per is
>> > underload, with least as 2342 31.00 per is overload, with most as
>> > 3790
>> >
>> > number of objects: 200000, replication is 3, total is 600000 the
>> > cluster contains 200 nodes expecting 3000 objects per node acceptable
>> > variation is 100 (objects per node) With 2 (1.00 percent) nodes add,
>> > 6363 objects (1.06 percent) need to be relocated. 33.00 per is
>> > underload, with least as 2432 32.00 per is overload, with most as
>> > 3623 ============================
>> >
>> > The object ID is generated via standard random() call. As you can
>> > see, currently algorithm is good enough to handle adding nodes.
>> > However, the distribution of objects on nodes is not even enough. The
>> > worst case is about 25% more/less objects on a single node. This also
>> > means we are going to waste about 25% disk space of the total.
>> >
>> > Could anyone comment on the testing result ? Am I testing it wrong ?
>> > Or there's really something to improve here.
>> >
>>
>>
>> Sheepdog internally have a virtual nodes mechanism to handle this very
>> problem. That is, one physical node will be virtually distributed on the
>> hash ring by a specified number (default 64).
>
> The test above is done with 64 vnodes per node.
> It actually calls nodes_to_vnodes and obj_to_sheep directly.

Perhaps, the FNV hash function is not good enough for our purpose.
Can you send the test program to the mailing list?

Thanks,

Kazutaka



More information about the sheepdog mailing list