<div dir="ltr">I just tried a simple experiment<div><br></div><div>I made a 1M table of random IP adresses.</div><div>Assume we ask the 20 nearest machines where there 20 nearest machine are</div><div>this is 20 RPCs and we put the results (400 of them) back in the table</div>
<div>to update the table with 400 entries and find the twenty nearest in the table took</div><div>10ms with a very naive ordered_sets lookup. This is fast enough for now ...</div><div><br></div><div>/Joe</div><div><br></div>
</div><div class="gmail_extra"><br><br><div class="gmail_quote">On Tue, May 27, 2014 at 3:26 PM, Dmitry Kolesnikov <span dir="ltr"><<a href="mailto:dmkolesnikov@gmail.com" target="_blank">dmkolesnikov@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word">Yes, I mean k-buckets from Kademlia. <div>From my perspective, a node eviction policy is an application specific task.</div>
<div>I see reasons why 20 is chosen for Kademlia but any one can choose other </div><div>eviction methods using memory limits or something else.</div><div><br></div><div>I’ve used gb_trees + lists (using keyXXX methods) to implement k-bucket with k=20.</div>
<div>The read/write access time was acceptable for me. However, some other data structure </div><div>is required to implement it for scalable k. Maybe nested trees or dict / tree symbiosis.   </div><span class="HOEnZb"><font color="#888888"><div>
<br></div><div>- Dmitry</div></font></span><div><div class="h5"><div><br></div><div><br></div><div><br><div><div>On 27 May 2014, at 16:12, Joe Armstrong <<a href="mailto:erlang@gmail.com" target="_blank">erlang@gmail.com</a>> wrote:</div>
<br><blockquote type="cite"><div dir="ltr">You mean K as in Kademlia ? - I thought about this<div>In Kademlia K is 20 so we store 20 IPs per bit of a 160 bit sha1 hash ie  3200 IPs this takes 12.8KB</div><div><br></div><div>
When a bucket if full (in Kademlia) we throw away the least recently active entry in the bucket concerned- it seems to me that</div>
<div>there is no reason to throw away anything until we have a really large number of machines.</div><div><br></div><div>If there we 10M machine we'd need 40MB to store the IPs which is still << 1GB - in other words a DHT</div>

<div>with 10M machines only needs a 40MB cache of IPs ...</div><div><br></div><div>/Joe</div><div><br></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Tue, May 27, 2014 at 3:00 PM, Dmitry Kolesnikov <span dir="ltr"><<a href="mailto:dmkolesnikov@gmail.com" target="_blank">dmkolesnikov@gmail.com</a>></span> wrote:<br>

<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><br><div><div><div><div>On 27 May 2014, at 15:56, Jesper Louis Andersen <<a href="mailto:jesper.louis.andersen@gmail.com" target="_blank">jesper.louis.andersen@gmail.com</a>> wrote:</div>

<br><blockquote type="cite"><div dir="ltr"><div class="gmail_extra"><br><div class="gmail_quote">On Tue, May 27, 2014 at 2:55 PM, Joe Armstrong <span dir="ltr"><<a href="mailto:erlang@gmail.com" target="_blank">erlang@gmail.com</a>></span> wrote:<br>



<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Now why would anybody want to put 20 byte binaries in a hash table and find the K nearest hits :-)</blockquote></div><br>



Distributed Hash Table rings ;)<br clear="all"></div></div></blockquote><div><br></div></div></div><div>In this case, k-bucket is the right data structure to keep nodes.  </div><span><font color="#888888"><div>
<br></div><br></font></span><blockquote type="cite"><span><font color="#888888"><div dir="ltr"><div class="gmail_extra"><div><br></div>-- <br>J.
</div></div></font></span><div>
_______________________________________________<br>erlang-questions mailing list<br><a href="mailto:erlang-questions@erlang.org" target="_blank">erlang-questions@erlang.org</a><br><a href="http://erlang.org/mailman/listinfo/erlang-questions" target="_blank">http://erlang.org/mailman/listinfo/erlang-questions</a><br>

</div></blockquote></div><br></div></blockquote></div><br></div>
</blockquote></div><br></div></div></div></div></blockquote></div><br></div>