Mainline DHT

Mainline DHTは、BitTorrentプロトコルを通じてピアを見つけるためにBitTorrentクライアントが使用する、Kademliaに基づく分散ハッシュテーブル（DHT）の名称である。BitTorrentにおける分散トラッキングのためにDHTを用いるというアイデアは、最初に2005年5月にAzureus 2.3.0.0（現在のVuze）で実装され、そこで大きな人気を得た^[1][2]。これとは無関係に、ほぼ同時期にBitTorrent, Inc.がMainline DHTと呼ばれる同様のDHTを自社のクライアントに導入し、BitTorrentプロトコルにおける分散トラッキングの使用を一般化させた。測定によれば、2013年時点でMainline DHTの同時ユーザー数は1,600万から2,800万に達し、1日の中でも少なくとも1,000万の変動があるとされる^[3]。

概要

Mainline DHTは、広く知られたKademlia DHTの設計に基づいている^[4]。DHTがピアの配布に使用される以前は、トラッカーのみがピアを見つける手段であった^[5]。DHTを使用する主な利点は、その分散型の性質がBitTorrentプロトコルの設計理念に合致している点である。DHTは、トレントのSHA-1ハッシュによって識別されたピアのリストを分散して保持することで機能する。

各クライアントはランダムに160ビットのノードIDを選択し、ノード間の距離はそれらのIDのXORによって計算される。Mainline DHTは、既知のノードを追跡するためにk-バケットを使用する。

ファイルをダウンロードする際、クライアントはまず自身のk-バケットを照会して、トレントのinfo_hashに最も近いノードを探す。これらのノードに接続してピアを発見する。ピアが見つかれば、クライアントは通常のBitTorrentプロトコルと同様に複数のソースからファイルをダウンロードする^[5]。

動作

トレントのSHA-1ハッシュであるinfohashは、Kademliaのキーと同義であり、オーバーレイ・ネットワーク内でピア（値）を探すために使用される。スウォーム内のピアを見つけるために、ノードはinfohashをキーとするget_peersクエリ（KademliaのFIND_VALUEに相当）をキー距離において最も近い既知のノードに送信する。Kademliaと同様に、ノードが値（ピア）を返さない場合、探索は反復的に続行される。ただし、探索が終了した後、クライアントは自身のピアの連絡先情報を、トレントのinfohashに最も近いIDを持つ応答ノードに挿入する。

トークン

ノードは、他者が勝手に他のホストをトレントに登録するのを防ぐために、トークンと呼ばれる追加の手段を使用する。ピアを求めるクエリに対する応答には、この不透明な値が含まれる。ノードが、自身が制御するピアがトレントをダウンロードしていることを発表するには、同じノードに対する最近のピア検索クエリで受け取ったトークンを提示する必要がある。ノードがトレントの「announce」を試みる際、問い合わせ先のノードは、トークンと問い合わせ元ノードのIPアドレスを照合する。

Mainline DHTは、IPアドレスと5分ごとに変化する秘密値を連結したSHA-1ハッシュをトークン値として使用する。最大10分前までのトークンが有効とされる。

KRPC

Mainline DHT内のノードは、IPアドレスとポート番号の組み合わせで構成される。ノード同士は、KRPCと呼ばれるRPCプロトコルを通じて通信する。KRPCは、UDP上でBencodeされた辞書を送受信する単純なプロトコルである。

KRPCメッセージは、全メッセージに共通する2つのキーと、メッセージの種類に応じた追加キーを持つ辞書である。すべてのメッセージには、トランザクションIDを表す文字列値を持つキー"t"が含まれる。このトランザクションIDは送信ノードによって生成され、応答時にエコーされるため、同じノードへの複数のクエリに対する応答を識別できる。このトランザクションIDは通常、2オクテット程度の短いバイナリ文字列で十分である。もう1つの共通キーは"y"であり、メッセージの種類を示す1文字の値を持つ。"y"の値は、"q"（クエリ）、"r"（応答）、"e"（エラー）のいずれかである。

クエリ

クエリ、すなわち"y"の値が"q"であるKRPCメッセージ辞書には、さらに2つのキー"q"と"a"が含まれる。キー"q"は、クエリのメソッド名を含む文字列であり、キー"a"は、クエリの引数を名前付きで格納した辞書である。

応答

応答、すなわち"y"の値が"r"であるKRPCメッセージ辞書には、追加のキー"r"が含まれる。"r"の値は、名前付きの戻り値を含む辞書である。応答メッセージは、クエリが正常に完了した際に送信される。

エラー

エラー、すなわち"y"の値が"e"であるKRPCメッセージ辞書には、追加のキー"e"が含まれる。"e"の値はリストであり、最初の要素はエラーコードを示す整数、2番目の要素はエラーメッセージを示す文字列である。クエリが処理不能な場合にエラーメッセージが送信される。

ルーティングテーブル

バケットは、Kademliaとは異なる構造をしている。Kademliaが160個のバケットを持つのに対し、BitTorrentでは1つのバケットから開始する。バケットが満杯になった場合、以下のいずれかが実行される：

• バケットの分割
• 古いノードへのping（Kademliaと同様）

ただし、バケットの範囲内に自身のノードIDが含まれている場合に限り、分割が実行される。分割されるバケットは、旧バケットの範囲を半分ずつ持つ2つの新しいバケットに置き換えられ、旧バケットにあったノードは2つの新バケットに再分配される。

このバケットの実装には2つの利点がある：

• 160個未満のバケットで済むため、ルーティングテーブルに必要なメモリが少なくなる。
• バケット検索時に隣接バケットから追加のノードを取得する必要がなく、現在のバケットに十分なノードがあることが保証される。

実装

Mainline DHTは、BitTorrent (ソフトウェア)のバージョン4.2.0（2005年11月）で初めて導入された。それ以降、他の多くのクライアントにも実装されている：

• μTorrent
• Transmission
• rTorrent
• KTorrent
• BitComet
• Deluge^[6]
• BitSpirit
• Vuze（MlDHTプラグイン使用）
• Shareaza
• Tixati
• qBittorrent