Mainline DHT と呼ばれる機能を解説/実装していきます。DHTは Distribution Hash Tableの略語です。
DHTはとても便利な道具です。DHTを使用してP2Pネッワークを構築すると、数回のリクエストで、P2Pネットワーク上から欲しいデータを発見できるようになります。
また、本文は、Torrentクライアント作成のチュートリアルの中の一部ですが、なるたけ独立して読めるように書いてみたつもりです。
-
もしかすると、サーバーサイドの負荷分散のアイデアの一つとして、参考になるものがあるかも知れません。
-
もしかすると、読了後、XOR距離が好きになるかもしれません。
Mainline DHTは、TrackerなしでPeerを探すことができる。
- Trackerがなくてもデータを探せる
- 六次の隔たりで実現している
- 距離を定義してネットワークを構築する
Mainline DHTは Trackerなしで、ネットワーク構築できる
Torrentクライアントは、P2Pネットワークを構築する際に、Trackerサーバーへアクセスして、データを共有するPeerを教えてもらう必要がありました。このTrackerの役割を、P2Pネットワーク上で実現したものが、Mainline DHTです。
今までは、Trackerサーバーの部分はP2P方式ではなくて、サーバー・クライアント方式でした。このため、基本的には、データを共有するには、Trackerサーバーを、WWW上に公開する必要がありました。しかし、DHTを採用することで、WWW上にTrackerサーバーを公開しなくてもデータを共有できるようになりました。
六次の隔たりを利用する
では、どのようにして、Trackerの変わりとなるP2Pネックワークを構築するのでしょうか。
具体的には、Trackerが行っていた。「InfoHash(20バイトのユニークな値)を、問い合わせると。データを共有してくれるTorrentクライアントを紹介してくれる」 という機能をP2Pで実現する必要があります。
この仕組みをP2Pで実現するために、DHTでは、すでに利用しているTorrentクライアントに、「InfoHashに関連するデータを所持しているTorrentクライアントがいないが聞く」。もしも、所持していなければ、「所持していそうなTorrentクライアントを教えてもらう。」ということを行います。基本、これだけでTrackerの役割をP2Pで実現できます。
「六次の隔たり」というこ言葉をご存知でしょうか?知り合いを6人くらいたどると、世界中のすべての人とつながっているそうです。イェール大学のスタンレー・ミルグラム教授による、「スモール・ワールド現象」が有名です。
同封した写真の人物はボストン在住の株式仲買人です。この顔と名前の人物をご存知でしたらその人の元へこの手紙をお送り下さい。この人を知らない場合は貴方の住所氏名を書き加えた上で、貴方の友人の中で知っていそうな人にこの手紙を送って下さい」という文面の手紙をそれぞれに送った。その結果42通 (26.25%) が実際に届き、42通が届くまでに経た人数の平均は5.83人であった。(https://ja.wikipedia.org/wiki/六次の隔たり)
大好きな作家さんや、尊敬するプログラマーも、関節的な知り合いというわけですね。P2Pネッワークも同様に、「六次の隔たり」によって実現しています。
距離を定義する
もう少し具体的に、「知っていそうな人を紹介する」を、P2Pネットワーク上で実現する方法を考えてみましょう。
P2Pネットワークに、InfoHashという20バイトのデータが渡されます。これを受け取ったは端末は、所持する数十のPeerからもっとも、InfoHashに対応するデータを持っていそうなPeerを紹介する必要があります。
DHTでは距離を定義して、紹介するPeerを決定します具体的には、「InfoHashにより近いPeerを紹介する」という事をします。 この距離はなんでも良いです。例えば、皆さんが学校で習ったユークリット距離でも良いでしょう。
ユークリット距離は、我々が日常世界で利用している距離のことです。例えば、東京駅から大阪駅までの走行距離は、508.0km。直線だと401kmくらい。神戸と名古屋は、東京よりも大阪り方が近い。仙台や神奈川は大阪よりも東京のほうが近いといった感じに定義できます。
ネットワークに偏りを作る
もうひとつ、「六次の隔たり」を実現するには、現実世界のおなじように、距離の近いものほど詳しく、距離の遠いものほど詳しくないといった状況をつくる必要があります。
自分の会社の同僚や同級生については、よく知っているでしょう。同級生よりも、同じ部活の友人などについては、より詳しく知っている事でしょう。しかし、別の会社の事や、別の学校の事は、詳しくないと思います。
P2Pネットワーク上に同様の構造を実現しないと、「InfoHashに近いPeerを紹介したけど、その紹介した人は、InfoHashに近いPeerの事を知らない」と問題が発生します。
この問題を解決するために、自分に近いPeerについてはたくさんの情報をもち、自分に遠いPeerについては少しだけ情報を持つようにしてあげます。これを、ネットワーク全体で繰り返す事で、現実世界と同じように、距離が近いPeerどうしはお互いを良く知っている状態が構築されるようになります。
KademliaのkBucketを利用している
- 距離はXOR
- kBucketでRootingTableを構築している
Torrentで採用されているDHTは、「Kademlia」と呼ばれているものです。本章では、KademliaのなかでもkBucketを用いたRootingTableについて紹介して行きます。
XORで距離を定義する。
前章で説明した通り、DHTでは距離を定義する必要がありました。Kademliaでは、この距離にxorを利用します。xorの距離とはどのようなものでしょうか?具体的にみていきましょう。
- 数字は2進数で表現できる
コンピュータプログラムでは、数字を2進数で表現できる事はご存じてじょうか。2進数とは、1と0のみで数字を表す方法の事で、256は二進数で、11111111 と表現できます。同様に、1 は 00000001、2は00000010、3は00000011、5は、0000101と表現できます。
例えば、00000011を10進数にもどす場合は、「1 + (0×2) + (1×(2×2))=5」と計算します。同様に10進数に戻す場合は、00000010は、「0+ (1×2)=2」と計算できます。
- XORはこの二進数にした値について行う
XOR距離は、この2進数に直した値にxorをする事をいいます。AとBの xor距離をとる事を、 A ^ B と書く事にしましょう。
ますば、xorとは何か? 与えられ値の何れかが、1の時、1となる計算方法のことです。
| 値A | 値B | A^B |
| 1 | 1 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 1 | 0 |
これを、おのおの桁ごとに計算していきます。
「256(11111111) ^ 3(00000011) --> 252 (11111100)」、同様に「252 (11111100) ^ 256(11111111) --> 3(00000011)」といった感じで計算できます。
xorは対称距離
xorは、A ^ B と B ^ A は同じ値になります。例えば、「256(11111111) ^ 3(00000011) --> 252 (11111100)」「 3(00000011) ^ 256(11111111) --> 252 (11111100)」といった感じです。
xorを距離として使うと、Peer間の距離が、お互いに同じになります。
これは。 Peer A から見た Peer B も Peer B から見た Peer A も同じ距離になるわけです。
これと、kBucket の RootingTable が合わさるともっと、綺麗な特徴が見えてきます。
kBucket の RootingTableを利用している
前章で、DHTでは各PeerがPeerの一覧を持っいると説明しました。そして、その一覧には偏りがあり自分に近いPeerについてはより詳しいのでした。Kademuliaでは、kBucketのRootingTableでPeerの一覧を管理しています。
kBucketは、K個のPeerの情報をグローピングする入れ物です。それだけです。K個以上保持する事ができないので、それ以上のPeerを追加するには、kBucketから不要なPeerを削除する必要があります。
Kademulia の RootingTableは、0〜160の161個のkBucketを所持する事ができます。それぞれのkBucketは、Peerからの距離が、2の0乗より小さい、2の1乗より小さい、2の2乗より小さい.....2の160乗より小さい値を所持する事がでます。
ちょっと複雑ですね。具体的に見ていきましょう。
図に直すと直感的な構造をしている
まずは、具体的にXOR距離がどのようなものか見ていきましょう。IDとして使用可能な160bit(20byte)を扱って説明するのは助長なので、ここでは、3bitのIDとして説明していきます。
本質は扱うIDに依存しませんので、気にせずに読み進めてください。
| 値 | 2進数 | A ^ 010 | table index |
| 0 | 000 | 2 | 2 |
| 1 | 001 | 3 | 2 |
| 2 | 010 | 0 | 0 |
| 3 | 011 | 1 | 1 |
| 4 | 100 | 6 | 3 |
| 5 | 101 | 7 | 3 |
| 6 | 110 | 4 | 3 |
| 7 | 111 | 5 | 3 |
010 の値を持つPeerとしてDHTに参加する場合について、上記の表にまとてみました。
各値に応じて、xor距離、どのkBucketに記録されるかが解るようにしました。
例えば、ID 010 のPeerとのxor距離は 0 です。そして、0番目のkBucketに格納されます。
同IDの場合の説明は当然すぎるので、IDが101の場合も見てみましょう。Peerとのxor距離は 7、 4番目のkBucketに格納されます。
格納するkBucketの位置の求め方が難しかったかもしれません。xorの値によって決まり、「0, 1, 2〜4, 4〜8」という範囲で0〜3のkBucketに選別されます。
次は図で見てみましょう。どうでしょうか。各Peerごとに、kBucketに格納される位置は直感的な配置になっているのではないでしょうか?
枝が移動するごとにの、格納するindexが大きくなっているのが解るでしょう。
このように、xor距離は、図形的に見ると直感的で合理的な構造になっているのです。
次回、次次回について
次回、次次回で、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