<div class="gmail_extra"><br><br>
<div class="gmail_quote">On Fri, Apr 27, 2012 at 12:49 AM, MORITA Kazutaka <span dir="ltr"><<a href="mailto:morita.kazutaka@gmail.com" target="_blank">morita.kazutaka@gmail.com</a>></span> wrote:<br>
<blockquote style="BORDER-LEFT:#ccc 1px solid;MARGIN:0px 0px 0px 0.8ex;PADDING-LEFT:1ex" class="gmail_quote">
<div class="HOEnZb">
<div class="h5">On Thu, Apr 26, 2012 at 6:13 PM, Huxinwei <<a href="mailto:huxinwei@huawei.com">huxinwei@huawei.com</a>> wrote:<br>>> -----Original Message-----<br>>> From: Liu Yuan [mailto:<a href="mailto:namei.unix@gmail.com">namei.unix@gmail.com</a>]<br>
>> Sent: Thursday, April 26, 2012 5:08 PM<br>>> To: Huxinwei<br>>> Cc: <a href="mailto:sheepdog@lists.wpkg.org">sheepdog@lists.wpkg.org</a><br>>> Subject: Re: [Sheepdog] The distribution of objects is not even enough ?<br>
>><br>>> On 04/26/2012 04:53 PM, Huxinwei wrote:<br>>><br>>> > Hi list,<br>>> ><br>>> > I made some tests against the consistent hashing algorithm of<br>>> > sheepdog. Here are some samples: ============================<br>
>> number<br>>> > of objects: 600000, replication is 3, total is 1800000 the cluster<br>>> > contains 100 nodes expecting 18000 objects per node acceptable<br>>> > variation is 600 (objects per node) With 2 (2.00 percent) nodes add,<br>
>> > 33915 objects (1.88 percent) need to be relocated. 34.00 per is<br>>> > underload, with least as 14757 32.00 per is overload, with most as<br>>> > 23376<br>>> ><br>>> > number of objects: 600000, replication is 3, total is 1800000 the<br>
>> > cluster contains 600 nodes expecting 3000 objects per node acceptable<br>>> > variation is 100 (objects per node) With 2 (0.00 percent) nodes add,<br>>> > 5881 objects (0.33 percent) need to be relocated. 33.00 per is<br>
>> > underload, with least as 2342 31.00 per is overload, with most as<br>>> > 3790<br>>> ><br>>> > number of objects: 200000, replication is 3, total is 600000 the<br>>> > cluster contains 200 nodes expecting 3000 objects per node acceptable<br>
>> > variation is 100 (objects per node) With 2 (1.00 percent) nodes add,<br>>> > 6363 objects (1.06 percent) need to be relocated. 33.00 per is<br>>> > underload, with least as 2432 32.00 per is overload, with most as<br>
>> > 3623 ============================<br>>> ><br>>> > The object ID is generated via standard random() call. As you can<br>>> > see, currently algorithm is good enough to handle adding nodes.<br>
>> > However, the distribution of objects on nodes is not even enough. The<br>>> > worst case is about 25% more/less objects on a single node. This also<br>>> > means we are going to waste about 25% disk space of the total.<br>
>> ><br>>> > Could anyone comment on the testing result ? Am I testing it wrong ?<br>>> > Or there's really something to improve here.<br>>> ><br>>><br>>><br>>> Sheepdog internally have a virtual nodes mechanism to handle this very<br>
>> problem. That is, one physical node will be virtually distributed on the<br>>> hash ring by a specified number (default 64).<br>><br>> The test above is done with 64 vnodes per node.<br>> It actually calls nodes_to_vnodes and obj_to_sheep directly.<br>
<br></div></div>Perhaps, the FNV hash function is not good enough for our purpose.<br>Can you send the test program to the mailing list?<br><br>Thanks,<br><br>Kazutaka<br></blockquote>
<div> </div>
<div>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. </div>
<div> </div>
<div>Perhaps we can add two themes:</div>
<div> </div>
<div>1, assign equal-sized partition to every node</div>
<div> </div>
<div>2, Adjust the partition to node when node add/leaving or storage imbalance</div>
<div> </div>
<div>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.</div>
<div> </div>
<div>Thanks</div>
<div>Haiting </div>
<div> </div>
<blockquote style="BORDER-LEFT:#ccc 1px solid;MARGIN:0px 0px 0px 0.8ex;PADDING-LEFT:1ex" class="gmail_quote">
<div class="HOEnZb">
<div class="h5">--<br>sheepdog mailing list<br><a href="mailto:sheepdog@lists.wpkg.org">sheepdog@lists.wpkg.org</a><br><a href="http://lists.wpkg.org/mailman/listinfo/sheepdog" target="_blank">http://lists.wpkg.org/mailman/listinfo/sheepdog</a><br>
</div></div></blockquote></div><br></div>