<HTML><BODY style="word-wrap: break-word; -khtml-nbsp-mode: space; -khtml-line-break: after-white-space; "><BR><DIV><DIV>On Apr 10, 2007, at 9:56 , Richard Jones wrote:</DIV><BR class="Apple-interchange-newline"><BLOCKQUOTE type="cite"><P style="margin: 0.0px 0.0px 0.0px 0.0px"><FONT face="Monaco" size="2" style="font: 10.0px Monaco">Every time we added memcached servers to the pool, the rehashing of all keys<SPAN class="Apple-converted-space"> </SPAN></FONT></P> <P style="margin: 0.0px 0.0px 0.0px 0.0px"><FONT face="Monaco" size="2" style="font: 10.0px Monaco">would kill our database while the cache filled up again. We implemented a<SPAN class="Apple-converted-space"> </SPAN></FONT></P> <P style="margin: 0.0px 0.0px 0.0px 0.0px"><FONT face="Monaco" size="2" style="font: 10.0px Monaco">consistent hashing algorithm that our memcached clients are now using to map<SPAN class="Apple-converted-space"> </SPAN></FONT></P> <P style="margin: 0.0px 0.0px 0.0px 0.0px"><FONT face="Monaco" size="2" style="font: 10.0px Monaco">keys to servers. Now we can add new memcached servers without causing<SPAN class="Apple-converted-space"> </SPAN></FONT></P> <P style="margin: 0.0px 0.0px 0.0px 0.0px"><FONT face="Monaco" size="2" style="font: 10.0px Monaco">chaos :)</FONT></P> <P style="margin: 0.0px 0.0px 0.0px 0.0px; font: 10.0px Monaco; min-height: 14.0px"><BR></P> <P style="margin: 0.0px 0.0px 0.0px 0.0px"><FONT face="Monaco" size="2" style="font: 10.0px Monaco">Here is the blurb and the code:</FONT></P> <P style="margin: 0.0px 0.0px 0.0px 0.0px"><FONT face="Monaco" size="2" style="font: 10.0px Monaco"><A href="http://www.last.fm/user/RJ/journal/2007/04/10/392555/">http://www.last.fm/user/RJ/journal/2007/04/10/392555/</A></FONT></P> </BLOCKQUOTE></DIV><DIV><BR class="khtml-block-placeholder"></DIV><DIV><SPAN class="Apple-tab-span" style="white-space:pre"> </SPAN>This is a very interesting idea, and I'd like to add a consistent hash driver to my java interface, but there's a bit of gap between your writeup and what the implementation.</DIV><DIV><BR class="khtml-block-placeholder"></DIV><DIV><SPAN class="Apple-tab-span" style="white-space:pre"> </SPAN>In the java interface, all I see is that you've added a new hash type that's based off an MD5. Is that actually an important detail? It seems like you should be able to use any hash that produces an even 32-bits.</DIV><DIV><BR class="khtml-block-placeholder"></DIV><DIV><SPAN class="Apple-tab-span" style="white-space:pre"> </SPAN>Is it OK if I use your C implementation as a specification?</DIV><BR><DIV> <SPAN class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><DIV>-- </DIV><DIV>Dustin Sallings</DIV><BR class="Apple-interchange-newline"></SPAN> </DIV><BR></BODY></HTML>