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

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

• http://www.bittorrent.org/beps/bep_0005.html
• http://pdos.csail.mit.edu/~petar/papers/maymounkov-kademlia-lncs.pdf

PS

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

• GitBook なぜなにTorrent
  https://nazenani-torrent.firefirestyle.net

Dart用の作成したTorrent Libraryは以下で公開しています。

• https://github.com/kyorohiro/dart_hetimatorrent
• https://github.com/kyorohiro/dart_hetimatorrent/tree/master/example/TorrentDHT

---

Kyorohiro work