[erlang-questions] finding the nearest key in a key-value table

[Dmitry Kolesnikov]

Yes, I mean k-buckets from Kademlia. 
From my perspective, a node eviction policy is an application specific task.
I see reasons why 20 is chosen for Kademlia but any one can choose other 
eviction methods using memory limits or something else.

I’ve used gb_trees + lists (using keyXXX methods) to implement k-bucket with k=20.
The read/write access time was acceptable for me. However, some other data structure 
is required to implement it for scalable k. Maybe nested trees or dict / tree symbiosis.   

- Dmitry



On 27 May 2014, at 16:12, Joe Armstrong <erlang@REDACTED> wrote:

> You mean K as in Kademlia ? - I thought about this
> 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
> 
> When a bucket if full (in Kademlia) we throw away the least recently active entry in the bucket concerned- it seems to me that
> there is no reason to throw away anything until we have a really large number of machines.
> 
> If there we 10M machine we'd need 40MB to store the IPs which is still << 1GB - in other words a DHT
> with 10M machines only needs a 40MB cache of IPs ...
> 
> /Joe
> 
> 
> 
> On Tue, May 27, 2014 at 3:00 PM, Dmitry Kolesnikov <dmkolesnikov@REDACTED> wrote:
> 
> On 27 May 2014, at 15:56, Jesper Louis Andersen <jesper.louis.andersen@REDACTED> wrote:
> 
>> 
>> On Tue, May 27, 2014 at 2:55 PM, Joe Armstrong <erlang@REDACTED> wrote:
>> Now why would anybody want to put 20 byte binaries in a hash table and find the K nearest hits :-)
>> 
>> Distributed Hash Table rings ;)
> 
> In this case, k-bucket is the right data structure to keep nodes.  
> 
> 
>> 
>> -- 
>> J.
>> _______________________________________________
>> erlang-questions mailing list
>> erlang-questions@REDACTED
>> http://erlang.org/mailman/listinfo/erlang-questions
> 
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20140527/7564fe52/attachment.htm>