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

[HaiTing Yao]

On Fri, Apr 27, 2012 at 12:49 AM, MORITA Kazutaka <morita.kazutaka at gmail.com
> wrote:

>  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
>

Now the random position assignment of each node on the ring leads to
non-uniform data and load distribution. The vnodes can decrease the
non-uniform but can not solve it.

Perhaps we can add two themes:

1, assign equal-sized partition to every node

2, Adjust the partition to node when node add/leaving or storage imbalance

These need assign and store the hash information. I am looking this. I have
not find the good implemention. Perhaps we can talk about it and find good
solution.

Thanks
Haiting


>  --
> sheepdog mailing list
> sheepdog at lists.wpkg.org
> http://lists.wpkg.org/mailman/listinfo/sheepdog
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.wpkg.org/pipermail/sheepdog/attachments/20120427/187abafb/attachment-0003.html>