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