文書ディレクトリ

KBucket.java

sourcecode

詳細ノート

概念紹介

コード分析

KBucketImpl.java

sourcecode

ノート

注記

コード

方法

I 2 PContextとConcurrentSetの2つのファイル

を参照してください.

KBucket.java

sourcecode

package net.i2p.kademlia;
/*
 * free (adj.): unencumbered; not under the control of others
 * Written by jrandom in 2003 and released into the public domain 
 * with no warranty of any kind, either expressed or implied.  
 * It probably won't make your computer catch on fire, or eat 
 * your children, but it might.  Use at your own risk.
 *
 */

import java.util.Set;

import net.i2p.data.SimpleDataStructure;

/**
 * Group, without inherent ordering, a set of keys a certain distance away from
 * a local key, using XOR as the distance metric
 *
 * Refactored from net.i2p.router.networkdb.kademlia
 * @since 0.9.2 in i2psnark, moved to core in 0.9.10
 */
public interface KBucket<T extends SimpleDataStructure> {

    /** 
     * Lowest order high bit for difference keys.
     * The lower-bounds distance of this bucket is 2**begin.
     * If begin == 0, this is 43the closest bucket.
     */
    public int getRangeBegin();

    /**
     * Highest high bit for the difference keys.
     * The upper-bounds distance of this bucket is (2**(end+1)) - 1.
     * If begin == end, the bucket cannot be split further.
     * If end == (numbits - 1), this is the furthest bucket.
     */
    public int getRangeEnd();

    /**
     * Number of keys already contained in this kbucket
     */
    public int getKeyCount();

    /**
     * Add the peer to the bucket
     *
     * @return true if added
     */
    public boolean add(T key);

    /**
     * Remove the key from the bucket
     * @return true if the key existed in the bucket before removing it, else false
     */
    public boolean remove(T key);
    
    /**
     *  Update the last-changed timestamp to now.
     */
    public void setLastChanged();

    /**
     *  The last-changed timestamp
     */
    public long getLastChanged();

    /**
     * Retrieve all routing table entries stored in the bucket
     * @return set of Hash structures
     */
    public Set<T> getEntries();

    public void getEntries(SelectionCollector<T> collector);

    public void clear();
}

詳細メモ

概念の紹介

まず、kbucketがどういう意味かを知るにはkademiliaアルゴリズムを理解する必要があります.それはp 2 pデータベースに関連するアルゴリズムで、一定の情報を分散的に格納するために使用されます.もっと詳しく知りたいのはリンクでkademiliaアルゴリズム、分散型ストレージを知ることができます
簡単に言えば、k-bucketを用いていくつかの情報を格納することであり、これらの情報はアドレス情報と理解することができ、各k-bucketには、本ノードと距離が等しいノードの情報が組み込まれている.
ここでのノードの距離の意味は,ノード情報,routerid,ノード間の距離がxorであるか,距離xorであるかを1組の01シーケンスで表すことであり,これは単独の異或プログラムで計算され,以下は比較的詳細な解釈である.
前述の距離は、学号(Node ID)間の異または距離(XOR distance)である.イソORはyes/noまたはバイナリに対する演算である.排他的論理和のアルゴリズムは、001000000と0000000001の距離は01000001(10進数換算で26+1、65).このように類推する.通信録はどのように距離で階層化されていますか?次の例では、異距離または距離で階層化され、基本的にはビット数で階層化されていると理解できます.0000110をベースノードとし、1つのノードのIDが前のすべてのビット数が同じで、最後の1ビットだけが異なる場合、このようなノードは1つだけである0000111であり、ベースノードとの異或値は000001、すなわち距離は1である.0000110の場合、このようなノードは「k−bucket 1」に分類される.1つのノードのIDで、前のすべてのビット数が同じで、最後から2番目のビットから異なる場合、このようなノードは2つしかありません:0000101、0000100、ベースノードとの異或値は0000011と0000010、すなわち距離範囲は3と2です.0000110では、このようなノードは「k-bucket 2」に分類される.1つのノードのIDの場合、前のすべてのビット数が同じで、最後からn番目のビットから異なる場合、このようなノードは2(i-1)個しかなく、ベースノードとの距離範囲は[2(i-1)、2 i)、0000110の場合、このようなノードは「k-bucket i」に分類される.ソース:著者:Li_Heng_liusリンク:https://www.jianshu.com/p/f2c31e632f1d

コード解析

このクラスの定義を見てみましょう.インターフェースです.このKBucketはコンテナに関連するインターフェースです.汎用(汎用紹介)が使われているためです.汎用は一般的にコンテナのために設計されています.ここではあまり説明しませんが、そのコンテナの役割は私たちが紹介したKBucketの役割と相互に証明されています.これは汎用インタフェースなので、インタフェースについては、そのすべての変数とメンバーメソッドはabstractであるべきです.そこで彼らの名前を見て、その機能について大まかな理解を持って、KBucketLmpl、javaで分析しました.
このTに対して、それは1つの汎型で、汎型はここで具体的なタイプを指定していないが範囲を与えた特定のタイプと解釈することができて、彼はKBucketの中の要素であるべきで、1つのノードの関連する情報を含んでいます

KBucketImpl.java

sourcecode

package net.i2p.kademlia;
/*
 * free (adj.): unencumbered; not under the control of others
 * Written by jrandom in 2003 and released into the public domain
 * with no warranty of any kind, either expressed or implied.
 * It probably won't make your computer catch on fire, or eat
 * your children, but it might.  Use at your own risk.
 *
 */

import java.util.Collections;
import java.util.Set;

import net.i2p.I2PAppContext;
import net.i2p.data.SimpleDataStructure;
import net.i2p.util.ConcurrentHashSet;

/**
 *  A concurrent implementation using ConcurrentHashSet.
 *  The max size (K) may be temporarily exceeded due to concurrency,
 *  a pending split, or the behavior of the supplied trimmer,
 *  as explained below.
 *  The creator is responsible for splits.
 *
 *  This class has no knowledge of the DHT base used for XORing,
 *  and thus there are no validity checks in add/remove.
 *
 *  The begin and end values are immutable.
 *  All entries in this bucket will have at least one bit different
 *  from us in the range [begin, end] inclusive.
 *  Splits must be implemented by creating two new buckets
 *  and discarding this one.
 *
 *  The keys are kept in a Set and are NOT sorted by last-seen.
 *  Per-key last-seen-time, failures, etc. must be tracked elsewhere.
 *
 *  If this bucket is full (i.e. begin == end && size == max)
 *  then add() will call KBucketTrimmer.trim() do
 *  (possibly) remove older entries, and indicate whether
 *  to add the new entry. If the trimmer returns true without
 *  removing entries, this KBucket will exceed the max size.
 *
 *  Refactored from net.i2p.router.networkdb.kademlia
 *  @since 0.9.2 in i2psnark, moved to core in 0.9.10
 */
class KBucketImpl<T extends SimpleDataStructure> implements KBucket<T> {
    /**
     *  set of Hash objects for the peers in the kbucket
     */
    private final Set<T> _entries;
    /** include if any bits equal or higher to this bit (in big endian order) */
    private final int _begin;
    /** include if no bits higher than this bit (inclusive) are set */
    private final int _end;
    private final int _max;
    private final KBucketTrimmer<T> _trimmer;
    /** when did we last shake things up */
    private long _lastChanged;
    private final I2PAppContext _context;
    
    /**
     *  All entries in this bucket will have at least one bit different
     *  from us in the range [begin, end] inclusive.
     */
    public KBucketImpl(I2PAppContext context, int begin, int end, int max, KBucketTrimmer<T> trimmer) {
        if (begin > end)
            throw new IllegalArgumentException(begin + " > " + end);
        _context = context;
        _entries = new ConcurrentHashSet<T>(max + 4);
        _begin = begin;
        _end = end;
        _max = max;
        _trimmer = trimmer;
    }
    
    public int getRangeBegin() { return _begin; }

    public int getRangeEnd() { return _end; }

    public int getKeyCount() {
        return _entries.size();
    }
    
    /**
     *  @return an unmodifiable view; not a copy
     */
    public Set<T> getEntries() {
        return Collections.unmodifiableSet(_entries);
    }

    public void getEntries(SelectionCollector<T> collector) {
        for (T h : _entries) {
             collector.add(h);
        }
    }
    
    public void clear() {
        _entries.clear();
    }
    
    /**
     *  Sets last-changed if rv is true OR if the peer is already present.
     *  Calls the trimmer if begin == end and we are full.
     *  If begin != end then add it and caller must do bucket splitting.
     *  @return true if added
     */
    public boolean add(T peer) {
        if (_begin != _end || _entries.size() < _max ||
            _entries.contains(peer) || _trimmer.trim(this, peer)) {
            // do this even if already contains, to call setLastChanged()
            boolean rv = _entries.add(peer);
            setLastChanged();
            return rv;
        }
        return false;
    }
    
    /**
     *  @return if removed. Does NOT set lastChanged.
     */
    public boolean remove(T peer) {
        boolean rv = _entries.remove(peer);
        //if (rv)
        //    setLastChanged();
        return rv;
    }
    
    /**
     *  Update the last-changed timestamp to now.
     */
    public void setLastChanged() {
        _lastChanged = _context.clock().now();
    }

    /**
     *  The last-changed timestamp, which actually indicates last-added or last-seen.
     */
    public long getLastChanged() {
        return _lastChanged;
    }
    
    @Override
    public String toString() {
        StringBuilder buf = new StringBuilder(1024);
        buf.append(_entries.size());
        buf.append(" entries in (").append(_begin).append(',').append(_end);
        buf.append(") : ").append(_entries.toString());
        return buf.toString();
    }
}

メモ

コメント

関連情報

はconcurrenthashsetを使用して同時を実現し、concurrenthashmapはjavaの自己パッケージクラスであり、concurrenthashsetはこの工事が自分で書いたクラスであり、具体的にどのように実現したのかは今は気にしないで、同時の集合であることを知っていて、効率が高くて安全であれば

同時性のため、最大値kが制限を超える可能性がある.ここでは,我々のアルゴリズムにおけるkの意味を説明し,各bucketに格納可能な最大値

である.

kBucketの追加情報も削除情報も正当性の検証を経ていない

.

beiginとendの値は変更できません.bucketのすべてのエンティティ要素には少なくとも1つの違いがあります(hash値の01シーケンスを言って、kademilaアルゴリズムを知っています.私が何を言っているか知っています).

bucketのkeyの格納順序はlast-seenに従って

並べ替えられるものではない.

bucketがいっぱいになった場合(例えばbeigin==endまたはsize==max)、いっぱいになった場合add関数を呼び出して要素を追加するとtrimmerを使用して要素を削除し、古いエンティティ

をremoveします.

コード#コード#

この1つのファイルのメモを取る时とても葛藤して、1つは自身がこのKBucketImplのコードに対して1回见たことがあって、别にkademilaのアルゴリズムに対して一定の理解があって、その上このファイルの书くコードは复雑ではありませんて、しかしその中のいくつかの点が私が见て分からないため、しかし半日考えて理解していないで、やはり先にこれらの问题を残して、それから补います.
記録しておきますJAvaファイル、このファイルは汎用クラスで、コンテナ、インタフェースですが、ここではKBucketImplを記録します.名前からKBucketクラスの実装であることがわかります.
Kademilaアルゴリズムの理解から,Kbucketはノード情報を組み込むためのbucketであり,本来は1つのノード情報だけでよいが,安全性と安定性を高めるために複数のノードを用いたため,KBucket自体はコンテナであり,これはsetによって完成し,無秩序な繰り返しの集合であることが分かった.

class KBucketImpl<T extends SimpleDataStructure> implements KBucket<T> {
    /**
     *  set of Hash objects for the peers in the kbucket
     */
    private final Set<T> _entries;
    /** include if any bits equal or higher to this bit (in big endian order) */
    private final int _begin;
    /** include if no bits higher than this bit (inclusive) are set */
    private final int _end;
    private final int _max;
    private final KBucketTrimmer<T> _trimmer;
    /** when did we last shake things up */
    private long _lastChanged;
    private final I2PAppContext _context;

Tは汎用型でsimpledatastructureのサブクラスであり、注記ではhashクラス

であることを示す

_entriesは集合であり、hashクラスを要素として格納し、各要素は関連情報

を格納する.

これについてはbeginと_endは、定数であり、作用の疑いは異なる高位低位

であるべきである.

_maxは定数であり、bucketごとに格納できる最大数

である.

trimmerは、修正のための

です.

_Lastchangedは、前回の変更時間

を記録する

_context作用疑い

方法

構造関数の注意_entitieはset集合であり、concurrentHashsetを使用して構築され、構造のsizeは最大値よりも4大きい.これは同時およびその他の操作などのため、最大値よりも少し打つため、max 1点

を超える必要がある.

の3つのget関数は、getEntries関数の戻り値がset集合であることに注意し、セキュリティのために元の集合を返すのではなくCollectionを呼び出す.unmodifiableSetメソッドは、変更できないセット

を返します.

add()とremove():削除された機能関数、具体的な操作はconcurrentsetを見て

を理解します.

I 2 PContextとConcurrentSetの2つのファイルを見てみましょう