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

  • 0
    いいね
  • 0
    コメント
    この記事は最終更新日から1年以上が経過しています。

    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

    http://kyorohiro.strikingly.com