LoginSignup
0
0

More than 3 years have passed since last update.

@kyorohiro(kiyohiro kawamura)

Dart で Torrentクライアントを作ろう(10+?) Dart で Mainline DHT を Codingしてみよう (2) kBucket RootingTable の実装編

Last updated at Posted at 2015-08-10

RootingTableを実装してみよう。

  • KIdを実装する
  • kBucketを実装する
  • RootingTableを実装する

RootingTableを実装してみましょう。コードに落とす事で理解も深まります。

KIDを実装する。

InfoHashもPeerIDもKIDとして表せる。

InfoHash と InfoHash、Peer IDとInfoHash Peer ID とPeer ID のXOR距離を計算する必要があるのでした。これらのIDは、すべて20バイトのデータであり同じものとして定義できます。本文ではKIDと呼ぶことにします。

XORでは160bitの値を扱う必要があります。しかし、Dart言語では160bitに対応する
数値を持っていません。53bitまでしか使えません。これは、Dart言語の問題というわけではなく、ほとんどの言語で、160bitの値を扱うことができません。

- XOR距離を数値に直す機能はなくても良い

本書では160bitの数値を定義しないで実装する方法で進めます。
実際に実装してみるとわかるのですが、XOR距離を求める必要はありません。RootingTable上のどの位置に格納されるのかという情報と、大小比較する機能が必要になります。

作成していきましょう。まずは、最初の定義、KID は、20byteのデータを持つ事とする。

class KId {
  List<int> _values = null;
  List<int> get value => new List.from(_values);
  KId(List<int> id) {
    if(id == null || id.length != 20) {
      throw {};
    }
    this._values = new Uint8List.fromList(id);
  }
  int get length => _values.length;
  int operator [](int idx) => _values[idx];
  Iterator<int> get iterator => _values.iterator;
}

XOR の計算機能を追加する

KIdはXOR距離が計算できる必要があります。数値としては表現する事は諦めましたが、計算した結果はKIDとして返す機能は必要です。バイト配列の各値ごとに xorをとる事で実現できます。

class KId {
  ...
  ...
  ...
  KId xor(KId b, [KId output = null]) {
    if (output == null) {
      output = new KId.zeroClear();
    }
    for (int i = 0; i < b._values.length; i++) {
      output._values[i] = this._values[i] ^ b._values[i];
    }
    return output;
  }
}

大小比較の機能を追加する

大小比較の機能を追加します。この機能を追加する事により、ソートが可能になります。
ソートができるようになると、あるKIDに近い値順に一覧を出すとかできるようになります。
まさに、これから作成しようとしている、InfoHashに近い値を持つPeer一覧を返す機能そのものです。

class KId {
  ...
  ...
  ...
  bool operator >(KId b) {
    for (int i = 0; i < b._values.length; i++) {
      if (this._values[i] == b._values[i]) {
        continue;
      } else if (this._values[i] > b._values[i]) {
        return true;
      } else {
        return false;
      }
    }
    return false;
  }

  bool operator ==(KId b) {
    for (int i = 0; i < b._values.length; i++) {
      if (this._values[i] != b._values[i]) {
        return false;
      }
    }
    return true;
  }

  bool operator >=(KId b) {
    return (this == b ? true : (this > b ? true : false));
  }

  bool operator <(KId b) {
    return (this == b ? false : !(this > b));
  }

  bool operator <=(KId b) {
    return (this == b ? true : (this > b ? false : true));
  }

以上でKIDの作成は完了です。事の顛末を知りたい方は、以下を参照してください。
https://github.com/kyorohiro/dart_hetimatorrent/tree/master/lib/src/dht

実装作業は、必ずテストを書きながら、動作確認しながら、進めてください。

kBucketを実装する。

kBucketは、K個のPeetについての情報を格納する入れ物です。これは、値を追加する時に制限をもたせたListとして表現できますね。

今回の実装ではkBucketが満杯になった場合は古いデータから削除するようにしています。
このあたりは、実際に動作させてみて最適な方法を試行錯誤すべきでしょう。

class KBucket {
  int _k = 8;
  int get k => _k;
  List<KPeerInfo> peerInfos = null;

  KBucket(int kBucketSize) {
    this._k = kBucketSize;
    this.peerInfos = [];
  }

  add(KPeerInfo peerInfo) {
    if (peerInfos.contains(peerInfo) == true) {
      peerInfos.remove(peerInfo);
    }
    peerInfos.add(peerInfo);
    if (peerInfos.length > k) {
      peerInfos.removeAt(0);
    }
  }

  int get length => peerInfos.length;
  KPeerInfo operator [](int idx) => peerInfos[idx];
  Iterator<KPeerInfo> get iterator => peerInfos.iterator;
}

以上でkBucketの作成は完了です。事の顛末を知りたい方は、以下を参照してください。
https://github.com/kyorohiro/dart_hetimatorrent/tree/master/lib/src/dht

RootingTableを実装する

前章で説明したとおり、RootingTableは、0〜160までの161個のkBucketを保持する事ができるのでした。
まずは、最初の定義、kBucketを161個保持することができる。

class KRootingTable {
  List<KBucket> _kBuckets = [];
  int _kBucketSize = 0;

  KRootingTable(int k_bucketSize) {
    this._kBucketSize = k_bucketSize;
    for (int i = 0; i < 161; i++) {
      _kBuckets.add(new KBucket(k_bucketSize));
    }
  }
}

KIdに値に応じて、追加するxBucketを決める機能を追加する

RootingTableを所持しているPeerとのXORを計算してもその値をもとに、どのxBucketに追加するかを決めます。

値 2進 index
0 000 1
2, 3 010, 011 2
4, 5, 6, 7 100, 101, 110, 111 3

実際に表に落としてみると、左から右へ1bitずつ確認していって、最初に1であった場所によって、kBucket位置が決まる事がわかります。

これをコードに落としましょう。

class KRootingTable {
  List<KBucket> _kBuckets = [];
  int _kBucketSize = 0;
  KId _ownerKId = null;
  KId get ownerKId => _ownerKId;

  KRootingTable(int k_bucketSize, KId ownerKId) {
    this._kBucketSize = k_bucketSize;
    for (int i = 0; i < 161; i++) {
      _kBuckets.add(new KBucket(k_bucketSize));
    }
    this._ownerKId = ownerKId;
  }

  int getRootingTabkeIndex(KId v) {
    // xor距離を計算する
    v = v.xor(_ownerKId);

    // 対応するkBucketを探す。
    for (int i = 0, ret = 19; i < 20; i++, ret--) {
      if (v[i] != 0) {
        for (int j = 0; j < 9; j++) {
          if (v[i] < (0x1 << j)) {
            return (ret * 8) + j;
          }
        }
        return i;
      }
    }
    return 0;
  }
}

Peerの情報が渡されたら、対応するkBucketに追加する

いままで、作成した機能を合わせる事で、RootingTableを更新できるようになります。

class KRootingTable {
  ...
  ...
  ...
  Future update(KPeerInfo info) {
    return new Future(() {
      _kBuckets[getRootingTabkeIndex(info.id)].add(info);
    });
  }
  ...
  ...
}

これで、RootingTableの作成は完了です。次の章の説明を得て、findNodeメソッドが追加されます。しかし、今までに解説した内容で実装できるのはここまでとなります。

一応ですね。今回作成したものを利用すれば、次の章で説明する機能がなくても、なんとか動作すると思います。
つまり、ランダムに知り合いを追加していったとしても、RootingTableの機能によって、最終的には、
自分に近いPeerについてより詳しく、自分と遠いPeerについてあまり詳しくない状況が作ります。

次の章で説明する機能を用いれば、もっと効率的に実現できます。

次回、次次回について

次回、次次回で、kBucketを利用して、ネットワークの構築方法していく流れを説明します。そして、実際に実装していきましょう。

Ref

PS

Qiitaに投稿した、Torrentのチュートリアルと、この文章は、gitbookの方でメンテナンスしていきます。もう少し詳しく知りたい方はこちらを参照してください。

Dart用の作成したTorrent Libraryは以下で公開しています。
- https://github.com/kyorohiro/dart_hetimatorrent
- https://github.com/kyorohiro/dart_hetimatorrent/tree/master/example/TorrentDHT

Kyorohiro work

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0