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

[MORITA Kazutaka]

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