<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="Generator" content="Microsoft Word 12 (filtered medium)">
<!--[if !mso]><style>v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style><![endif]--><style><!--
/* Font Definitions */
@font-face
{font-family:Wingdings;
panose-1:5 0 0 0 0 0 0 0 0 0;}
@font-face
{font-family:宋体;
panose-1:2 1 6 0 3 1 1 1 1 1;}
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:"\@宋体";
panose-1:2 1 6 0 3 1 1 1 1 1;}
@font-face
{font-family:Tahoma;
panose-1:2 11 6 4 3 5 4 4 2 4;}
@font-face
{font-family:华文细黑;
panose-1:2 1 6 0 4 1 1 1 1 1;}
@font-face
{font-family:"\@华文细黑";
panose-1:2 1 6 0 4 1 1 1 1 1;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman","serif";}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
span.EmailStyle17
{mso-style-type:personal-reply;
font-family:"Calibri","sans-serif";
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 90.0pt 72.0pt 90.0pt;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="2050" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="ZH-CN" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.5pt;font-family:"Calibri","sans-serif";color:#1F497D">I tried Strategy 2 like this:<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.5pt;font-family:"Calibri","sans-serif";color:#1F497D"> for (v=0, o = 0; v < SD_MAX_VNODES; v++, o++) {<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.5pt;font-family:"Calibri","sans-serif";color:#1F497D"> if (o >= nr) o = 0;<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.5pt;font-family:"Calibri","sans-serif";color:#1F497D"> vnodes[v].id = UINT64_MAX / SD_MAX_VNODES * v;<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.5pt;font-family:"Calibri","sans-serif";color:#1F497D"> vnodes[v].node = &(nodes[o]);<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.5pt;font-family:"Calibri","sans-serif";color:#1F497D"> vnodes[v].node_idx = o;<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.5pt;font-family:"Calibri","sans-serif";color:#1F497D"> }<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.5pt;font-family:"Calibri","sans-serif";color:#1F497D"> for (v=0; v < SD_MAX_VNODES; v++) {<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.5pt;font-family:"Calibri","sans-serif";color:#1F497D"> c = ((unsigned int)(v+random()))%SD_MAX_VNODES;<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.5pt;font-family:"Calibri","sans-serif";color:#1F497D"> vnode = vnodes[v];<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.5pt;font-family:"Calibri","sans-serif";color:#1F497D"> vnodes[v] = vnodes[c];<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.5pt;font-family:"Calibri","sans-serif";color:#1F497D"> vnodes[c] = vnode;<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.5pt;font-family:"Calibri","sans-serif";color:#1F497D"> }<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.5pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.5pt;font-family:"Calibri","sans-serif";color:#1F497D">It surely helps to ensure an equally distribution.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.5pt;font-family:"Calibri","sans-serif";color:#1F497D">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.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.5pt;font-family:"Calibri","sans-serif";color:#1F497D">It’s basically how swift (from openstack) do. And I found it overwhelm for sheepdog.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.5pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.5pt;font-family:"Calibri","sans-serif";color:#1F497D">Strategy 3 is basically how glusterfs do.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.5pt;font-family:"Calibri","sans-serif";color:#1F497D">But, recording hash space also means you’ll face a lot of data movement again.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.5pt;font-family:"Calibri","sans-serif";color:#1F497D">glusterfs use “link” extensively to avoid data moving. Should we do that too ?<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.5pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.5pt;font-family:"Calibri","sans-serif";color:#1F497D">BTW: I found the easiest way to improve distribution while maintain the simplicity of current algo. Is to increase VNODES_PER_NODE.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.5pt;font-family:"Calibri","sans-serif";color:#1F497D">The downside is, of course, more memory to use for the vnode_list.
</span><span lang="EN-US" style="font-size:10.5pt;font-family:Wingdings;color:#1F497D">L</span><span lang="EN-US" style="font-size:10.5pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.5pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.5pt;font-family:"Calibri","sans-serif";color:#1F497D">FYI.<o:p></o:p></span></p>
<div class="MsoNormal" align="center" style="text-align:center"><span lang="EN-US" style="font-family:宋体;color:#1F497D">
<hr size="2" width="100%" align="center">
</span></div>
<p class="MsoNormal"><span lang="EN-US" style="font-size:10.0pt;font-family:华文细黑;color:black">Xinwei Hu<br>
</span><span style="font-size:10.0pt;font-family:华文细黑;color:black">华为技术有限公司<span lang="EN-US"> Huawei Technologies Co., Ltd.<br>
</span></span><!--[if gte vml 1]><v:shapetype id="_x0000_t75" coordsize="21600,21600" o:spt="75" o:preferrelative="t" path="m@4@5l@4@11@9@11@9@5xe" filled="f" stroked="f">
<v:stroke joinstyle="miter" />
<v:formulas>
<v:f eqn="if lineDrawn pixelLineWidth 0" />
<v:f eqn="sum @0 1 0" />
<v:f eqn="sum 0 0 @1" />
<v:f eqn="prod @2 1 2" />
<v:f eqn="prod @3 21600 pixelWidth" />
<v:f eqn="prod @3 21600 pixelHeight" />
<v:f eqn="sum @0 0 1" />
<v:f eqn="prod @6 1 2" />
<v:f eqn="prod @7 21600 pixelWidth" />
<v:f eqn="sum @8 21600 0" />
<v:f eqn="prod @7 21600 pixelHeight" />
<v:f eqn="sum @10 21600 0" />
</v:formulas>
<v:path o:extrusionok="f" gradientshapeok="t" o:connecttype="rect" />
<o:lock v:ext="edit" aspectratio="t" />
</v:shapetype><v:shape id="ridImg" o:spid="_x0000_s1026" type="#_x0000_t75" alt="Company_logo" style='position:absolute;margin-left:0;margin-top:0;width:76.5pt;height:24pt;z-index:1;visibility:visible;mso-wrap-style:square;mso-wrap-distance-left:0;mso-wrap-distance-top:0;mso-wrap-distance-right:0;mso-wrap-distance-bottom:0;mso-position-horizontal:left;mso-position-horizontal-relative:text;mso-position-vertical:absolute;mso-position-vertical-relative:line' o:allowoverlap="f">
<v:imagedata src="file:///C:\Users\h00206182\Application%20Data\Microsoft\Signatures\company_logo.jpg" />
<w:wrap type="square" anchory="line"/>
</v:shape><![endif]--><![if !vml]><img width="102" height="32" src="file:///C:\Users\h00206182\Application%20Data\Microsoft\Signatures\company_logo.jpg" align="left" alt="Company_logo" v:shapes="ridImg"><![endif]><span lang="EN-US" style="font-size:10.0pt;font-family:华文细黑;color:black"><br>
<br>
Phone: <br>
Fax: <br>
Mobile: <br>
Email: huxinwei@huawei.com<br>
</span><span style="font-size:10.0pt;font-family:华文细黑;color:black">地址：深圳市龙岗区坂田华为基地 邮编：<span lang="EN-US">518129<br>
Huawei Technologies Co., Ltd.<br>
Bantian, Longgang District,Shenzhen 518129, P.R.China<br>
http://www.huawei.com</span></span><span lang="EN-US" style="font-family:宋体;color:#1F497D">
<o:p></o:p></span></p>
<div class="MsoNormal" align="center" style="text-align:center"><span lang="EN-US" style="font-family:宋体;color:#1F497D">
<hr size="2" width="100%" align="center">
</span></div>
<p class="MsoNormal"><span style="font-size:7.5pt;font-family:华文细黑;color:gray">本邮件及其附件含有华为公司的保密信息，仅限于发送给上面地址中列出的个人或群组。禁<span lang="EN-US"><br>
</span>止任何其他人以任何形式使用（包括但不限于全部或部分地泄露、复制、或散发）本邮件中<span lang="EN-US"><br>
</span>的信息。如果您错收了本邮件，请您立即电话或邮件通知发件人并删除本邮件！<span lang="EN-US"><br>
</span></span><span lang="EN-US" style="font-size:7.5pt;font-family:"Arial","sans-serif";color:gray">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 lang="EN-US" style="font-size:10.5pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p></o:p></span></p>
<div style="border:none;border-left:solid blue 1.5pt;padding:0cm 0cm 0cm 4.0pt">
<div>
<div style="border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0cm 0cm 0cm">
<p class="MsoNormal"><b><span lang="EN-US" style="font-size:10.0pt;font-family:"Tahoma","sans-serif"">From:</span></b><span lang="EN-US" style="font-size:10.0pt;font-family:"Tahoma","sans-serif""> sheepdog-bounces@lists.wpkg.org [mailto:sheepdog-bounces@lists.wpkg.org]
<b>On Behalf Of </b>HaiTing Yao<br>
<b>Sent:</b> Friday, May 04, 2012 10:24 AM<br>
<b>To:</b> sheepdog@lists.wpkg.org<br>
<b>Subject:</b> [Sheepdog] Add more hash strategy<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<div>
<p class="MsoNormal"><span lang="EN-US">Hi,<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US"> <o:p></o:p></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. <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US">Strategy 1 (We used now)<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US">Random tokens per node<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US"> <o:p></o:p></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.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US">Strategy 2<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US"> <o:p></o:p></span></p>
</div>
<div>
<div>
<p class="MsoNormal"><span lang="EN-US">Random tokens per node<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US"> <o:p></o:p></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.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US">Strategy 3<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US"> <o:p></o:p></span></p>
</div>
<div>
<div>
<p class="MsoNormal"><span lang="EN-US">Random tokens per node<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US"> <o:p></o:p></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.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US"> <o:p></o:p></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.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US">Do we need add the strategy 2/3, or there is better strategies?
<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US">Thanks <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US">Haiti<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US"> <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US"> <o:p></o:p></span></p>
</div>
</div>
</div>
<div>
<p class="MsoNormal"><span lang="EN-US"> <o:p></o:p></span></p>
</div>
</div>
</div>
</body>
</html>