0

私は修正された Kademlia P2P システムをここに書いていますが、ここで説明している問題は元のシステムの実装と非常によく似ています。

では、k-Buckets を実装する最も効率的な方法は何でしょうか? 私にとって重要なのは、アクセス時間、並列処理 (読み取りと書き込み)、およびメモリ消費です。

ConcurrentLinkedQueue と ConcurrentHashMap でそれを行うことを考えましたが、それはかなり冗長で厄介ですよね?

現時点では、LinkedList を同期しているだけです。

これが私のコードです：

import java.util.LinkedList;

class Bucket {
    private final LinkedList<Neighbour> neighbours;
    private final Object lock;

    Bucket() {
        neighbours = new LinkedList<>();
        lock = new Object();
    }

    void sync(Neighbour n) {
        synchronized(lock) {
            int index = neighbours.indexOf(n);
            if(index == -1) {
                neighbours.add(n);
                n.updateLastSeen();
            } else {
                Neighbour old = neighbours.remove(index);
                neighbours.add(old);
                old.updateLastSeen();
            }
        }
    }

    void remove(Neighbour n) {
        synchronized(lock) {
            neighbours.remove(n);
        }
    }

    Neighbour resolve(Node n) throws ResolveException {
        Neighbour nextHop;
        synchronized(lock) {
            int index = neighbours.indexOf(n);
            if(index == -1) {
                nextHop = neighbours.poll();
                neighbours.add(nextHop);
                return nextHop;
            } else {
                return neighbours.get(index);
            }
        }
    }
}

不思議に思わないでください、私は別のネイバー立ち退きプロセスを実装しました。

4

1 に答える 1

1

では、k-Buckets を実装する最も効率的な方法は何でしょうか?

場合によります。付箋付きの実装 (バケット分割、マルチホーミングなど) を行いたい場合は、柔軟なリストまたはツリーが必要です。私の経験では、バケットの合計数を変更することはめったになく、バケットの内容のみを変更するため、書き込み配列のコピー + バイナリ検索はルーティング テーブルに適しています。

CoW セマンティクスを使用すると、配列の現在のコピーを取得し、対象のバケットを取得してからバケットをロックするだけで済むため、必要なロックが少なくなります。または、各バケット内でアトミック配列を使用します。しかし、もちろん、このような最適化は、高いスループットが期待される場合にのみ必要です。ほとんどの DHT ノードは、トラフィックが非常に少なく、多くても 1 秒あたり数パケットです。データを処理するには複数のスレッドが必要です。

CoW は、ルーティング テーブルのようなルックアップ キャッシュや、ルックアップ中に構築された一時的な訪問ノード/ターゲット ノード セットに対してはあまりうまく機能しません。これらは急速に変更されるためです。高負荷が予想される場合は、ConcurrentSkipListMaps を選択することをお勧めします。

簡略化されたおおよその実装が必要な場合は、160 要素の固定サイズの配列を使用してください。配列インデックスは、ノード ID に対する共有プレフィックス ビット数です。これはかなりうまく機能しますが、 kademliaの完全な論文で提案されている最適化の一部を考慮していません。

于 2014-12-18T16:43:19.553 に答える