class DEVp2p::Kademlia::KBucket

Each k-bucket is kept sorted by time last seen - least-recently seen node at the head, most-recently seen at the tail. For small values of i, the k-buckets will generally be empty (as no appropriate nodes will exist). For large values of i, the lists can grow up to size k, where k is a system-wide replication parameter.

k is chosen such that any given k nodes are very unlikely to fail within an hour of each other (for example k = 20).

Attributes

left[RW]

Public Class Methods

new(left, right) click to toggle source
# File lib/devp2p/kademlia/k_bucket.rb, line 19
def initialize(left, right)
  @left, @right = left, right
  @nodes = []
  @replacement_cache = []
  @last_updated = Time.now
end

Public Instance Methods

add(node) click to toggle source

If the sending node already exists in the recipient’s k-bucket, the recipient moves it to the tail of the list.

If the node is not already in the appropriate k-bucket and the bucket has fewer than k entries, then the recipient just inserts the new sender at the tail of the list.

If the appropriate k-bucket is full, however, then the recipient pings the k-bucket’s least-recently seen node to decide what to do:

* on success: return nil
* on bucket full: return least recently seen node for eviction check
# File lib/devp2p/kademlia/k_bucket.rb, line 45
def add(node)
  @last_updated = Time.now

  if include?(node) # already exists
    delete node
    @nodes.push node
    nil
  elsif size < K # add if fewer than k entries
    @nodes.push node
    nil
  else # bucket is full
    head
  end
end
add_replacement(node) click to toggle source
# File lib/devp2p/kademlia/k_bucket.rb, line 60
def add_replacement(node)
  @replacement_cache.push node
end
delete(node) click to toggle source
# File lib/devp2p/kademlia/k_bucket.rb, line 64
def delete(node)
  return unless include?(node)
  @nodes.delete node
end
depth() click to toggle source

depth is the prefix shared by all nodes in bucket. i.e. the number of shared leading bits.

# File lib/devp2p/kademlia/k_bucket.rb, line 141
def depth
  return ID_SIZE if size < 2

  bits = @nodes.map {|n| Utils.bpad(n.id, ID_SIZE) }
  ID_SIZE.times do |i|
    if bits.map {|b| b[0,i] }.uniq.size != 1
      return i - 1
    end
  end

  raise "should never be here"
end
distance(node) click to toggle source
# File lib/devp2p/kademlia/k_bucket.rb, line 91
def distance(node)
  midpoint ^ node.id
end
each(&block) click to toggle source
# File lib/devp2p/kademlia/k_bucket.rb, line 27
def each(&block)
  @nodes.each(&block)
end
empty?() click to toggle source
# File lib/devp2p/kademlia/k_bucket.rb, line 170
def empty?
  @nodes.empty?
end
full?() click to toggle source
# File lib/devp2p/kademlia/k_bucket.rb, line 158
def full?
  size == K
end
head() click to toggle source

least recently seen

# File lib/devp2p/kademlia/k_bucket.rb, line 72
def head
  @nodes.first
end
id_distance(id) click to toggle source
# File lib/devp2p/kademlia/k_bucket.rb, line 95
def id_distance(id)
  midpoint ^ id
end
in_range?(node) click to toggle source
# File lib/devp2p/kademlia/k_bucket.rb, line 154
def in_range?(node)
  left <= node.id && node.id <= right
end
include?(node) click to toggle source
# File lib/devp2p/kademlia/k_bucket.rb, line 166
def include?(node)
  @nodes.include?(node)
end
midpoint() click to toggle source
# File lib/devp2p/kademlia/k_bucket.rb, line 87
def midpoint
  left + (right - left) / 2
end
nodes_by_id_distance(id) click to toggle source
# File lib/devp2p/kademlia/k_bucket.rb, line 99
def nodes_by_id_distance(id)
  raise ArgumentError, 'invalid id' unless id.is_a?(Integer)
  @nodes.sort_by {|n| n.id_distance(id) }
end
range() click to toggle source
# File lib/devp2p/kademlia/k_bucket.rb, line 83
def range
  [left, right]
end
should_split?() click to toggle source
# File lib/devp2p/kademlia/k_bucket.rb, line 104
def should_split?
  full? && splitable?
end
size() click to toggle source
# File lib/devp2p/kademlia/k_bucket.rb, line 162
def size
  @nodes.size
end
split() click to toggle source

split at the median id

# File lib/devp2p/kademlia/k_bucket.rb, line 116
def split
  split_id = midpoint

  lower = self.class.new left, split_id
  upper = self.class.new split_id + 1, right

  # distribute nodes
  @nodes.each do |node|
    bucket = node.id <= split_id ? lower : upper
    bucket.add node
  end

  # distribute replacement nodes
  @replacement_cache.each do |node|
    bucket = node.id <= split_id ? lower : upper
    bucket.add_replacement node
  end

  return lower, upper
end
splitable?() click to toggle source
# File lib/devp2p/kademlia/k_bucket.rb, line 108
def splitable?
  d = depth
  d % B != 0 && d != ID_SIZE
end
tail() click to toggle source

last recently seen

# File lib/devp2p/kademlia/k_bucket.rb, line 79
def tail
  @nodes.last
end