java.lang.Object
net.i2p.kademlia.KBucketSet<T>
Type Parameters:
T - type of SimpleDataStructure objects stored in buckets
public class KBucketSet<T extends SimpleDataStructure>extends Object
In-memory storage of buckets sorted by XOR metric from base (us) passed in via constructor. This starts with one bucket covering the whole key space, and may eventually be split to a max of number of bits in data type (160 for SHA1Hash or 256 for Hash), times 2**(B-1) for Kademlia value B.

Refactored from net.i2p.router.networkdb.kademlia.

  • Field Details

    • _log

      private final Log _log
      Logger for the routing table.

    • _context

      private final I2PAppContext _context
      The app context.

    • _us

      private final T extends SimpleDataStructure _us
      The local node's key.

    • _buckets

      private final List<KBucket<T extends SimpleDataStructure>> _buckets
      The bucket list is locked by _bucketsLock, however the individual buckets are not locked. Users may see buckets that have more than the maximum k entries, or may have adds and removes silently fail when they appear to succeed.

      Closest values are in bucket 0, furthest are in the last bucket.

    • _rangeCalc

      private final KBucketSet.Range<T extends SimpleDataStructure> _rangeCalc
      Calculator of the bucket range for a key.

    • _trimmer

      private final KBucketTrimmer<T extends SimpleDataStructure> _trimmer
      Trimmer deciding which entries to drop.

    • _bucketsLock

      private final ReentrantReadWriteLock _bucketsLock
      Locked for reading only when traversing all the buckets. Locked for writing only when splitting a bucket. Adds/removes/gets from individual buckets are not locked.

    • KEYSIZE_BITS

      private final int KEYSIZE_BITS
      Number of bits in a key.

    • NUM_BUCKETS

      private final int NUM_BUCKETS
      Number of buckets in the set.

    • BUCKET_SIZE

      private final int BUCKET_SIZE
      Entries one bucket holds.

    • B_VALUE

      private final int B_VALUE
      B value from the kademlia paper.

    • B_FACTOR

      private final int B_FACTOR
      Factor scaling the bucket ranges.

  • Constructor Details

    • KBucketSet

      public KBucketSet(I2PAppContext context, T us, int max, int b)
      Use the default trim strategy, which removes a random entry.
      Parameters:
      context - the router context
      us - the local identity (typically a SHA1Hash or Hash) The class must have a zero-argument constructor.
      max - the Kademlia value "k", the max per bucket, must be > 4
      b - the Kademlia value "b", split buckets an extra 2**(b-1) times, 1 <= b <= 8, use 1 for bittorrent, Kademlia paper recommends 5
      Throws:
      IllegalArgumentException - if max <= 4, or b is outside 1..8
      RuntimeException - if the us class has no zero-argument constructor

    • KBucketSet

      public KBucketSet(I2PAppContext context, T us, int max, int b, KBucketTrimmer<T> trimmer)
      Use the supplied trim strategy.
      Parameters:
      context - the router context
      us - the local identity
      max - the Kademlia value "k", the max per bucket, must be > 4
      b - the Kademlia value "b", 1 <= b <= 8
      trimmer - the trim strategy
      Throws:
      IllegalArgumentException - if max <= 4, or b is outside 1..8
      RuntimeException - if the us class has no zero-argument constructor

  • Method Details

    • getReadLock

      private void getReadLock()
      Takes the read lock.

    • releaseReadLock

      private void releaseReadLock()
      Releases the read lock.

    • getWriteLock

      private boolean getWriteLock()
      Try to acquire the write lock.
      Returns:
      true if the lock was acquired

    • releaseWriteLock

      private void releaseWriteLock()
      Releases the write lock.

    • add

      public boolean add(T peer)
      Add a peer to the appropriate bucket. Will split the bucket if necessary.
      Parameters:
      peer - the router hash to insert
      Returns:
      true if the peer is new to the bucket it goes in, or false if it was already in it. Always returns false on an attempt to add ourselves.

    • shouldSplit

      private boolean shouldSplit(KBucket<T> b)
      No lock required.
      Parameters:
      b - the bucket to test
      Returns:
      true if the bucket is over BUCKET_SIZE and its range covers more than one key

    • split

      private void split(int r)
      Grabs the write lock. Caller must NOT have the read lock. The bucket should be splittable (range start != range end).
      Parameters:
      r - the range start of the bucket to be split

    • locked_split

      private void locked_split(int r)
      Creates two or more new buckets. The old bucket is replaced and discarded.

      Caller must hold write lock The bucket should be splittable (range start != range end).

      Parameters:
      r - the range start of the bucket to be split

    • size

      public int size()
      The current number of entries.
      Returns:
      total number of entries across all buckets

    • getBucketCount

      public int getBucketCount()
      Number of buckets in this set.
      Returns:
      the bucket count

    • getBucketCapacity

      public int getBucketCapacity()
      The number of entries a single bucket holds before splitting.
      Returns:
      the per-bucket capacity

    • getFullestBucketSize

      public int getFullestBucketSize()
      The entry count of the fullest bucket, to spot eviction pressure.
      Returns:
      zero or more

    • getRoot

      public T getRoot()
      The key this set is rooted on; bucket ranges are bit positions of the XOR distance from this key.
      Returns:
      non-null

    • getBucketBValue

      public int getBucketBValue()
      The B value: the number of subranges the key space is split into at the top level.
      Returns:
      one or more

    • getDebugBucketRows

      public List<String[]> getDebugBucketRows()
      Snapshot of every bucket for the debug console, one row per bucket: {index, bucket count, range begin, range end, key count, keys} as strings. Ranges are bit positions of the XOR distance from the root key. Keys are the entry keys' toString() values, comma-separated, empty if the bucket is empty.
      Returns:
      non-null, empty if no buckets exist

    • remove

      public boolean remove(T entry)
      Remove a peer from its bucket.
      Parameters:
      entry - the peer to remove
      Returns:
      true if removed

    • clear

      public void clear()
      Clear all buckets.

    • getAll

      public Set<T> getAll()
      Return all entries in all buckets.
      Returns:
      a copy in a new set

    • getAll

      public Set<T> getAll(Set<T> toIgnore)
      All entries in all buckets, excluding the specified entries.
      Parameters:
      toIgnore - entries to exclude
      Returns:
      a copy in a new set

    • getAll

      public void getAll(SelectionCollector<T> collector)
      Add all entries in all buckets to the provided collector.

      The read lock is held only long enough to copy the bucket references out of the list, then released before the collector runs. Collectors do netDb, banlist and profile lookups, so holding the lock across the pass blocked every add(T) and bucket split in the router for the duration of a full traversal of the whole keyspace — and this is called once per DSRM reply and once per outbound explore query. A concurrent split may leave a snapshot entry already emptied and a concurrent add may not appear; both were already possible outcomes of the unsynchronized per-bucket access documented on _buckets.

      Parameters:
      collector - the collector to add entries to

    • getClosest

      public List<T> getClosest(int max)
      The keys closest to us. Returned list will never contain us.
      Parameters:
      max - maximum number of keys to return
      Returns:
      non-null, closest first

    • getClosest

      public List<T> getClosest(int max, Collection<T> toIgnore)
      The keys closest to us. Returned list will never contain us.
      Parameters:
      max - maximum number of keys to return
      toIgnore - entries to exclude
      Returns:
      non-null, closest first

    • getClosest

      public List<T> getClosest(T key, int max)
      The keys closest to the key. Returned list will never contain us.
      Parameters:
      key - the target key
      max - maximum number of keys to return
      Returns:
      non-null, closest first

    • getClosest

      public List<T> getClosest(T key, int max, Collection<T> toIgnore)
      The keys closest to the key. Returned list will never contain us.
      Parameters:
      key - the target key
      max - maximum number of keys to return
      toIgnore - entries to exclude
      Returns:
      non-null, closest first

    • pickBucket

      private int pickBucket(T key)
      The bucket number (NOT the range number) that the xor of the key goes in Caller must hold read lock.
      Parameters:
      key - the key whose bucket is wanted
      Returns:
      0 to max-1 or -1 for us

    • getBuckets

      List<KBucket<T>> getBuckets()
      Returned list is a copy of the bucket list, closest first, with the actual buckets (not a copy).

      Primarily for testing. You shouldn't ever need to get all the buckets. Use getClosest(int) or getAll() instead to get the keys.

      Returns:
      non-null

    • getBucket

      private KBucket<T> getBucket(T key)
      The bucket that the xor of the key goes in Caller must hold read lock.
      Parameters:
      key - the key whose bucket is wanted
      Returns:
      null if key is us

    • pickBucket

      private int pickBucket(int range)
      The bucket number that contains this range number Caller must hold read lock or write lock.
      Parameters:
      range - the range number whose bucket is wanted
      Returns:
      0 to max-1 or -1 for us

    • createBuckets

      private List<KBucket<T>> createBuckets()
      Builds the initial bucket list.
      Returns:
      the new buckets

    • createBucket

      private KBucket<T> createBucket(int start, int end)
      Builds one bucket covering a range.
      Parameters:
      start - the first bit of the range
      end - the last bit of the range
      Returns:
      the new bucket

    • getRange

      int getRange(T key)
      The number of bits minus 1 (range number) for the xor of the key. Package private for testing only. Others shouldn't need this.
      Parameters:
      key - the router hash whose bucket range is wanted
      Returns:
      0 to max-1 or -1 for us

    • getExploreKeys

      public List<T> getExploreKeys(long age)
      For every bucket that hasn't been updated in this long, or isn't close to full, generate a random key that would be a member of that bucket. The returned keys may be searched for to "refresh" the buckets.
      Parameters:
      age - the maximum age in milliseconds
      Returns:
      non-null, closest first

    • getExploreKeys

      public List<T> getExploreKeys(long age, int max)
      For every bucket that hasn't been updated in this long, or isn't close to full, generate a random key that would be a member of that bucket, up to max keys. The closest bucket's key is always first. The remaining buckets are visited in random order so a capped pass does not always starve the far end of the keyspace.
      Parameters:
      age - the maximum age in milliseconds
      max - the maximum number of keys to generate
      Returns:
      non-null, closest bucket first

    • getBucketEntries

      public Set<T> getBucketEntries(T key)
      A copy of the entries of the bucket the given key belongs to.
      Parameters:
      key - the key whose bucket entries are wanted
      Returns:
      non-null, empty if the key is us or fits no bucket

    • generateRandomKey

      T generateRandomKey(KBucket<T> bucket)
      Generate a random key to go within this bucket Package private for testing only. Others shouldn't need this.
      Parameters:
      bucket - the bucket to pick a random key for
      Returns:
      a random key in the bucket's range

    • makeKey

      private T makeKey(byte[] data)
      Make a new SimpleDataStructure from the data.
      Parameters:
      data - size <= SDS length, else throws IAE, can be 1 bigger if top byte is zero
      Returns:
      a new data structure holding the given key bytes

    • toString

      public String toString()
      Overrides:
      toString in class Object