<br><br>
<div class="gmail_quote">On Fri, May 4, 2012 at 11:36 AM, Huxinwei <span dir="ltr"><<a href="mailto:huxinwei@huawei.com" target="_blank">huxinwei@huawei.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 lang="ZH-CN" vlink="purple" link="blue">
<div>
<p class="MsoNormal"><span style="FONT-FAMILY:'Calibri','sans-serif';COLOR:#1f497d;FONT-SIZE:10.5pt" lang="EN-US">I tried Strategy 2 like this:<u></u><u></u></span></p>
<p class="MsoNormal"><span style="FONT-FAMILY:'Calibri','sans-serif';COLOR:#1f497d;FONT-SIZE:10.5pt" lang="EN-US"> for (v=0, o = 0; v < SD_MAX_VNODES; v++, o++) {<u></u><u></u></span></p>
<p class="MsoNormal"><span style="FONT-FAMILY:'Calibri','sans-serif';COLOR:#1f497d;FONT-SIZE:10.5pt" lang="EN-US"> if (o >= nr) o = 0;<u></u><u></u></span></p>
<p class="MsoNormal"><span style="FONT-FAMILY:'Calibri','sans-serif';COLOR:#1f497d;FONT-SIZE:10.5pt" lang="EN-US"> vnodes[v].id = UINT64_MAX / SD_MAX_VNODES * v;<u></u><u></u></span></p>
<p class="MsoNormal"><span style="FONT-FAMILY:'Calibri','sans-serif';COLOR:#1f497d;FONT-SIZE:10.5pt" lang="EN-US"> vnodes[v].node = &(nodes[o]);<u></u><u></u></span></p>
<p class="MsoNormal"><span style="FONT-FAMILY:'Calibri','sans-serif';COLOR:#1f497d;FONT-SIZE:10.5pt" lang="EN-US"> vnodes[v].node_idx = o;<u></u><u></u></span></p>
<p class="MsoNormal"><span style="FONT-FAMILY:'Calibri','sans-serif';COLOR:#1f497d;FONT-SIZE:10.5pt" lang="EN-US"> }<u></u><u></u></span></p>
<p class="MsoNormal"><span style="FONT-FAMILY:'Calibri','sans-serif';COLOR:#1f497d;FONT-SIZE:10.5pt" lang="EN-US"> for (v=0; v < SD_MAX_VNODES; v++) {<u></u><u></u></span></p>
<p class="MsoNormal"><span style="FONT-FAMILY:'Calibri','sans-serif';COLOR:#1f497d;FONT-SIZE:10.5pt" lang="EN-US"> c = ((unsigned int)(v+random()))%SD_MAX_VNODES;<u></u><u></u></span></p>
<p class="MsoNormal"><span style="FONT-FAMILY:'Calibri','sans-serif';COLOR:#1f497d;FONT-SIZE:10.5pt" lang="EN-US"> vnode = vnodes[v];<u></u><u></u></span></p>
<p class="MsoNormal"><span style="FONT-FAMILY:'Calibri','sans-serif';COLOR:#1f497d;FONT-SIZE:10.5pt" lang="EN-US"> vnodes[v] = vnodes[c];<u></u><u></u></span></p>
<p class="MsoNormal"><span style="FONT-FAMILY:'Calibri','sans-serif';COLOR:#1f497d;FONT-SIZE:10.5pt" lang="EN-US"> vnodes[c] = vnode;<u></u><u></u></span></p>
<p class="MsoNormal"><span style="FONT-FAMILY:'Calibri','sans-serif';COLOR:#1f497d;FONT-SIZE:10.5pt" lang="EN-US"> }<u></u><u></u></span></p>
<p class="MsoNormal"><span style="FONT-FAMILY:'Calibri','sans-serif';COLOR:#1f497d;FONT-SIZE:10.5pt" lang="EN-US"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="FONT-FAMILY:'Calibri','sans-serif';COLOR:#1f497d;FONT-SIZE:10.5pt" lang="EN-US">It surely helps to ensure an equally distribution.<u></u><u></u></span></p>
<p class="MsoNormal"><span style="FONT-FAMILY:'Calibri','sans-serif';COLOR:#1f497d;FONT-SIZE:10.5pt" lang="EN-US">But on the other hand, it’s important to track the mapping from vnode to node then, to minimize the data movement when join/leave happens.<u></u><u></u></span></p>
<p class="MsoNormal"><span style="FONT-FAMILY:'Calibri','sans-serif';COLOR:#1f497d;FONT-SIZE:10.5pt" lang="EN-US">It’s basically how swift (from openstack) do. And I found it overwhelm for sheepdog.</span></p>
</div></div></blockquote>
<div> </div>
<div>With strategy 2, data movement are are distributed to all of nodes when node join/leave. I have not found idea to decrease the impact. </div>
<blockquote style="BORDER-LEFT:#ccc 1px solid;MARGIN:0px 0px 0px 0.8ex;PADDING-LEFT:1ex" class="gmail_quote">
<div lang="ZH-CN" vlink="purple" link="blue">
<div>
<p class="MsoNormal"><span style="FONT-FAMILY:'Calibri','sans-serif';COLOR:#1f497d;FONT-SIZE:10.5pt" lang="EN-US"><u></u><u></u></span></p>
<p class="MsoNormal"><span style="FONT-FAMILY:'Calibri','sans-serif';COLOR:#1f497d;FONT-SIZE:10.5pt" lang="EN-US"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="FONT-FAMILY:'Calibri','sans-serif';COLOR:#1f497d;FONT-SIZE:10.5pt" lang="EN-US">Strategy 3 is basically how glusterfs do.<u></u><u></u></span></p>
<p class="MsoNormal"><span style="FONT-FAMILY:'Calibri','sans-serif';COLOR:#1f497d;FONT-SIZE:10.5pt" lang="EN-US">But, recording hash space also means you’ll face a lot of data movement again.<u></u><u></u></span></p>
<p class="MsoNormal"><span style="FONT-FAMILY:'Calibri','sans-serif';COLOR:#1f497d;FONT-SIZE:10.5pt" lang="EN-US">glusterfs use “link” extensively to avoid data moving. Should we do that too ?</span></p></div>
</div></blockquote>
<div> </div>
<div>I think recording hash space like this. Then the data movement maybe a little. </div>
<div> </div>
<div>Use one 4MB object to store the hash information. The information include hash token and bitmap for every node. The bitmap marks how much hash space has been used. When new node joins the cluster, check all of the bitmaps of every node and find the right hash space for the new node.</div>
<div> </div>
<div>The object can have multi copies with the same contents.</div>
<div> </div>
<div>For example, nodes A B C D E. Every bitmap have 8 bits.</div>
<div>Node C bitmap: 1 1 1 1 0 0 0 0</div>
<div>Node D bitmap: 0 0 1 1 0 0 0 0</div>
<div>Then I can assign the blank hash space between C and D to the new coming node.</div>
<div> </div>
<div>It is just a simple assumption. I have not got the right solution. With this assumption, all of the nodes read/write one object that records hash infomation, so there is race condition probably. </div>
<div> </div>
<blockquote style="BORDER-LEFT:#ccc 1px solid;MARGIN:0px 0px 0px 0.8ex;PADDING-LEFT:1ex" class="gmail_quote">
<div lang="ZH-CN" vlink="purple" link="blue">
<div>
<p class="MsoNormal"><span style="FONT-FAMILY:'Calibri','sans-serif';COLOR:#1f497d;FONT-SIZE:10.5pt" lang="EN-US"><u></u><u></u></span></p>
<p class="MsoNormal"><span style="FONT-FAMILY:'Calibri','sans-serif';COLOR:#1f497d;FONT-SIZE:10.5pt" lang="EN-US"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="FONT-FAMILY:'Calibri','sans-serif';COLOR:#1f497d;FONT-SIZE:10.5pt" lang="EN-US">BTW: I found the easiest way to improve distribution while maintain the simplicity of current algo. Is to increase VNODES_PER_NODE.<u></u><u></u></span></p>
<p class="MsoNormal"><span style="FONT-FAMILY:'Calibri','sans-serif';COLOR:#1f497d;FONT-SIZE:10.5pt" lang="EN-US">The downside is, of course, more memory to use for the vnode_list. </span><span style="FONT-FAMILY:Wingdings;COLOR:#1f497d;FONT-SIZE:10.5pt" lang="EN-US">L</span></p>
</div></div></blockquote>
<div> </div>
<div>Yes, I agreed with you. </div>
<div> </div>
<div>Perhaps every strategy has its proper condition and has different configurations to tune its efficiency. </div>
<div> </div>
<div>Thanks</div>
<div>Haiti</div>
<blockquote style="BORDER-LEFT:#ccc 1px solid;MARGIN:0px 0px 0px 0.8ex;PADDING-LEFT:1ex" class="gmail_quote">
<div lang="ZH-CN" vlink="purple" link="blue">
<div>
<p class="MsoNormal"><span style="FONT-FAMILY:'Calibri','sans-serif';COLOR:#1f497d;FONT-SIZE:10.5pt" lang="EN-US"><u></u><u></u></span></p>
<p class="MsoNormal"><span style="FONT-FAMILY:'Calibri','sans-serif';COLOR:#1f497d;FONT-SIZE:10.5pt" lang="EN-US"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="FONT-FAMILY:'Calibri','sans-serif';COLOR:#1f497d;FONT-SIZE:10.5pt" lang="EN-US">FYI.<u></u><u></u></span></p>
<div style="TEXT-ALIGN:center" class="MsoNormal" align="center"><span lang="EN-US">
<hr align="center" size="2" width="100%">
</span></div>
<p class="MsoNormal"><span lang="EN-US">Xinwei Hu<br></span><span>华为技术有限公司<span lang="EN-US"> Huawei Technologies Co., Ltd.<br></span></span><u></u><img alt="Company_logo" align="left" width="102" height="32"><u></u><span lang="EN-US"><br>
<br>Phone: <br>Fax: <br>Mobile: <br>Email: <a href="mailto:huxinwei@huawei.com" target="_blank">huxinwei@huawei.com</a><br></span><span>地址：深圳市龙岗区坂田华为基地 邮编：<span lang="EN-US">518129<br>Huawei Technologies Co., Ltd.<br>Bantian, Longgang District,Shenzhen 518129, P.R.China<br>
<a href="http://www.huawei.com/" target="_blank">http://www.huawei.com</a></span></span><span lang="EN-US"> <u></u><u></u></span></p>
<div style="TEXT-ALIGN:center" class="MsoNormal" align="center"><span lang="EN-US">
<hr align="center" size="2" width="100%">
</span></div>
<p class="MsoNormal"><span>本邮件及其附件含有华为公司的保密信息，仅限于发送给上面地址中列出的个人或群组。禁<span lang="EN-US"><br></span>止任何其他人以任何形式使用（包括但不限于全部或部分地泄露、复制、或散发）本邮件中<span lang="EN-US"><br></span>的信息。如果您错收了本邮件，请您立即电话或邮件通知发件人并删除本邮件！<span lang="EN-US"><br>
</span></span><span style="FONT-FAMILY:'Arial','sans-serif';COLOR:gray;FONT-SIZE:7.5pt" lang="EN-US">This e-mail and its attachments contain confidential information from HUAWEI, which <br>is intended only for the person or entity whose address is listed above. Any use of the <br>
information contained herein in any way (including, but not limited to, total or partial <br>disclosure, reproduction, or dissemination) by persons other than the intended <br>recipient(s) is prohibited. If you receive this e-mail in error, please notify the sender by <br>
phone or email immediately and delete it!</span><span style="FONT-FAMILY:'Calibri','sans-serif';COLOR:#1f497d;FONT-SIZE:10.5pt" lang="EN-US"><u></u><u></u></span></p>
<div style="BORDER-BOTTOM:medium none;BORDER-LEFT:blue 1.5pt solid;PADDING-BOTTOM:0cm;PADDING-LEFT:4pt;PADDING-RIGHT:0cm;BORDER-TOP:medium none;BORDER-RIGHT:medium none;PADDING-TOP:0cm">
<div>
<div style="BORDER-BOTTOM:medium none;BORDER-LEFT:medium none;PADDING-BOTTOM:0cm;PADDING-LEFT:0cm;PADDING-RIGHT:0cm;BORDER-TOP:#b5c4df 1pt solid;BORDER-RIGHT:medium none;PADDING-TOP:3pt">
<p class="MsoNormal"><b><span style="FONT-FAMILY:'Tahoma','sans-serif';FONT-SIZE:10pt" lang="EN-US">From:</span></b><span style="FONT-FAMILY:'Tahoma','sans-serif';FONT-SIZE:10pt" lang="EN-US"> <a href="mailto:sheepdog-bounces@lists.wpkg.org" target="_blank">sheepdog-bounces@lists.wpkg.org</a> [mailto:<a href="mailto:sheepdog-bounces@lists.wpkg.org" target="_blank">sheepdog-bounces@lists.wpkg.org</a>] <b>On Behalf Of </b>HaiTing Yao<br>
<b>Sent:</b> Friday, May 04, 2012 10:24 AM<br><b>To:</b> <a href="mailto:sheepdog@lists.wpkg.org" target="_blank">sheepdog@lists.wpkg.org</a><br><b>Subject:</b> [Sheepdog] Add more hash strategy<u></u><u></u></span></p></div>
</div>
<div>
<div class="h5">
<p class="MsoNormal"><span lang="EN-US"><u></u> <u></u></span></p>
<div>
<p class="MsoNormal"><span lang="EN-US">Hi,<u></u><u></u></span></p></div>
<div>
<p class="MsoNormal"><span lang="EN-US"> <u></u><u></u></span></p></div>
<div>
<p class="MsoNormal"><span lang="EN-US">I read codes about hash now and tried to do something. I need some comments to do it properly. <u></u><u></u></span></p></div>
<div>
<p class="MsoNormal"><span lang="EN-US"> <u></u><u></u></span></p></div>
<div>
<p class="MsoNormal"><span lang="EN-US">Strategy 1 (We used now)<u></u><u></u></span></p></div>
<div>
<p class="MsoNormal"><span lang="EN-US"> <u></u><u></u></span></p></div>
<div>
<p class="MsoNormal"><span lang="EN-US">Random tokens per node<u></u><u></u></span></p></div>
<div>
<p class="MsoNormal"><span lang="EN-US"> <u></u><u></u></span></p></div>
<div>
<p class="MsoNormal"><span lang="EN-US">Partition by random token. The partition token is produced by hash function with node IP/port.<u></u><u></u></span></p></div>
<div>
<p class="MsoNormal"><span lang="EN-US"> <u></u><u></u></span></p></div>
<div>
<p class="MsoNormal"><span lang="EN-US">Strategy 2<u></u><u></u></span></p></div>
<div>
<p class="MsoNormal"><span lang="EN-US"> <u></u><u></u></span></p></div>
<div>
<div>
<p class="MsoNormal"><span lang="EN-US">Random tokens per node<u></u><u></u></span></p></div>
<div>
<p class="MsoNormal"><span lang="EN-US"> <u></u><u></u></span></p></div>
<div>
<p class="MsoNormal"><span lang="EN-US">Equal sized partitions. The hash space is divided into Q equally sized partitions. Q is the number of nodes or vnodes.<u></u><u></u></span></p></div>
<div>
<p class="MsoNormal"><span lang="EN-US"> <u></u><u></u></span></p></div>
<div>
<p class="MsoNormal"><span lang="EN-US">Strategy 3<u></u><u></u></span></p></div>
<div>
<p class="MsoNormal"><span lang="EN-US"> <u></u><u></u></span></p></div>
<div>
<div>
<p class="MsoNormal"><span lang="EN-US">Random tokens per node<u></u><u></u></span></p></div>
<div>
<p class="MsoNormal"><span lang="EN-US"> <u></u><u></u></span></p></div>
<div>
<p class="MsoNormal"><span lang="EN-US">Equal sized partitions. When there is node join/leaving, the equal size may be broken to minimize the data movement.<u></u><u></u></span></p></div>
<div>
<p class="MsoNormal"><span lang="EN-US"> <u></u><u></u></span></p></div>
<div>
<p class="MsoNormal"><span lang="EN-US">For strategy 3, need write hash space to disk. I think I can use the object to record the infomation.<u></u><u></u></span></p></div>
<div>
<p class="MsoNormal"><span lang="EN-US"> <u></u><u></u></span></p></div>
<div>
<p class="MsoNormal"><span lang="EN-US">Do we need add the strategy 2/3, or there is better strategies? <u></u><u></u></span></p></div>
<div>
<p class="MsoNormal"><span lang="EN-US"> <u></u><u></u></span></p></div>
<div>
<p class="MsoNormal"><span lang="EN-US">Thanks <u></u><u></u></span></p></div>
<div>
<p class="MsoNormal"><span lang="EN-US">Haiti<u></u><u></u></span></p></div>
<div>
<p class="MsoNormal"><span lang="EN-US"> <u></u><u></u></span></p></div>
<div>
<p class="MsoNormal"><span lang="EN-US"> <u></u><u></u></span></p></div></div></div>
<div>
<p class="MsoNormal"><span lang="EN-US"> <u></u><u></u></span></p></div></div></div></div></div></div></blockquote></div><br>