# Cover ![](/files/-LALzkm3payTyqZyDaYy)\ [ By kyorohiro](http://kyorohiro.github.io/) [イントロ](/intro) * [はじめに](/intro/introduction) * [Torrentとは](/intro/about) * [ゴール](/intro/goal) * [Torrentファイルを読み込む](/torrentfile) * [About](/torrentfile/about) * [Bencode](/torrentfile/bencode) * [Bencodeの実装](/torrentfile/implementation) * [TorrentFileの中身](/torrentfile/content) * [Httpサーバーを作成してみる](/http) * [UPnpによるポートマップ](/upnp) * [UPnPによるポートマップ](/upnp/about) * [UPnPの実装](/upnp/implementation) * [Trackerへアクセスしてみる](/tracker) * [About](/tracker/about) * [TrackerはHttpサーバ](/tracker/http) * [リクエストの中身](/tracker/request) * [レスポンスの中身](/tracker/response) * [テスト](/tracker/test) * [ダウンロードゲームへ参加してみる](/client) * [About](/client/about) * [ダウンロードゲーム](/client/downloadgame) * [ブロックデーターの実装](/client/blockdata) * [配信用、Peerを作成してみよう](/client/updater) * [基本戦術](/client/basicss) * [Chokeの実装](/client/chokeimpl) * [DHTに対応してみる](/dht) * [About](/dht/about) * [Tracker無しでPeerを探す](/dht/aboutdht) * [KademliaのkBucketを利用している](/dht/kbucket) * [RootingTableを実装してみよう](/dht/kbucketimpl) * [FindNodeでネットワークの構築](/dht/findnodes) * [FindNodeを実装](/dht/findnodesimpl) * [GetPeersでInfoHashに対応するPeerを探す](/dht/getpeers) * [テスト](/dht/test) * \[Dartの基礎] * \[なぜDart] * [Hello World](/dartno/helloworld) * [Test/Debug](/dartno/observatory) * [Get started with Observatory](/dartno/observatory/observatory_getstarted) # イントロ ![](/files/-LALzsARnuegZ-98GugF) # はじめに * **Torrent は悪いイメージもあるが、世の中に貢献している** * **P2Pの学習に最適** 今、私はTorrentクライアントを開発しています。 この本は、その時に P2P について学習した事をまとめたものです。 今でこそ、仕様書に書かれている内容に満足していますが、当 初は上手く理解できない所が、かなりありました。 実際に作成していくうちに、理解できる範囲が広がっていきま した。そして、そろそろ完成というところまで進みました。 この本では、この経験にならい、実際に Torrent クローンを作 成しながら、P2Pについて解説して行きたいと思います。 ## ネガティブなイメージ ちまたでは、Torrent は違法なファイル共有アプリという認識 が強いように思います。 Twitter の検索機能で、Torrent と検索 してみてください。 あなたは、Torrentについてネガティブなイメージを持 つことでしょう。違法な利用を助長するようなツイートを発見 する事ができるからです。 Google で、Torrentと検索してみてください。 「 アメリカ合衆 国のデジタルミレニアム著作権法に基づいたクレームに応じ、 このページからxx件の検索結果を除外しました。」 といった文 言が表示されます。また、Twitterで検索した結果と同じように 違法な利用を助長するようなサイトを発見することができるで しょう。 ## 世の中に貢献している しかし、こういったネガティブなイメージは Torrent の一面で しかありません。まっとうな使い方も多くされています。 例えば、大規模なネットワークシステムのデプロイといった事 があげられます。デプロイとは、ユーザーへサービスを提供す るための、準備作業の事をいいます。 Google であれば、データを即座に検索できる用にサーバーを 立ち上げる。 Twitter ならば、ツイートの送信、表示、などを できるようにするといった事です。 大手のネットワークでは数千、数万のコンピュータが動作して います。 これらのコンピュータへ変更を加える必要が出てきた場合に は、この変更を数千、数万のコンピュータへ反映する必要があ ります。こういったデータの配信の Torrent の技術が利用され ています。 また、大量にデータを配信する環境が必要ななのは企業だけで はありません。個人でも活用されています。例えば、OSのイメ ージの配信に利用されています。 OSというと、WindowsやMACなどメーカーが CD や DVD と いった記憶媒体を通して配布される事をイメージするかも知れ ません。 しかし、独自にOSをパッケージングする事は、大手の企業だ けがする仕事ではありません。今では個人が趣味でOSをパッ ケージングして配信する事も可能です。可能なだけではなく、 ありふれた行為になりつつあります。 しかし、個人で配信する場合、当然ながら数千、数万のサーバ ーを用意する事はできません。また、 CD や DVD の記憶媒体 を大量に配るにしても限界があります。そういった、個人がデ ータを配布するのにTorrentの技術が利用されています。 ## 学習に最適 また、Torrent を学ぶことは、P2Pを学ぶ上で最適な教材でな いかと考えられます。 まず Torrent は、もっとも普及した P2P の通信方法でありま す。 それだけではなく、 最新の技術を取り入れ進化し続けて いる技術でもあります。 Torrent を学習すると、ネットワークアプリの作成のノウハ ウ、 分散ハッシュテーブル、 ゲーム理論を応用した柔軟なネ ットワークなどなど、 基本から応用まで扱う事になります。 なによりも、おおくのアプリや仕様がオーブンに公開されてお り、P2Pを実例をもって学ぶことができるのです。 Torrent 以外でメジャーな P2P アプリはあります。 しかし Torrent ほど、オッピロゲなはないでしょう。日本で流行した Winny のソースは公開されていません。 Winny について知りた ければ、 ハックする必要があります。海外で流行したWinmxも そうです。 Torrentはその仕様が公開されています。どのような通信プロト コルが利用されているのか文章化されています。おおくの実装 例がオープンソースとして公開されています。公開されている だけではありません。さまざまな言語で書かれています。 Python、 Ruby、Java、JavaScript、C++ などなど、ありとあ らゆる言語で書かれています。 もしも、煮詰まった時は、これらの実装を読む事で保管する事 も可能でしょう。あなたの得意な言語で読む事ができるので す。 ## さいごに Torrent のネガティブなイメージは一面にすぎない事。多くの史 実用的なプロダクトを利用されていること。 また、Torrent がP2P の教材として優れている事ほ理解して頂けたでしょうか？ 少しでも興味を持たれた方、本書を通してTorrentの理解の助け になれば幸いです。 Kyorohiro work # Torrentとは * **データの配信はコストが高い** * **Torrentは、低コストでデータは配信を可能にした** Torrentを違法なファイル共有ソフトという認識をもたれてい るかも知れません。しかし、それは間違いです。 Torrent は違 法な利用を助長するような機能は含まれていません。たとえ ば、Torrent には匿名性はほとんどありません。 また、Torrent クライアントはネットワークから特定のファイルを探し出し共 有する機能を持っていません。 つまり、 Torrent クライアントを利用してデータをダウンロー ドする事は、Webブラウザーを利用して、Webサーバーからデ ータをダウンロードするのと差がありません。 どちらも、Google などの検索エンジンを使用して欲しいデータを探し、 データをダウンロードします。ただ違うのは、 Torrent はどの 通信方法よりも効率良くデータを配信することができることで す。 ## データの配信はとてもコストが高い インターネットでデータ配信するとしましょう。 例えば生放 送で動画を配信したい場合、どのくらいのコストがかかるでし ょうか？ 例えば、320×240 の画面サイズの動画だと、1秒間に50kb程度 の帯域を使用します。任期のある生放送などは、一度に2000人 以上の人が視聴します。この場合、2000×50kb=100mbのデー ター転送が必要になります。 ご家庭にある通信回線は10MB程度ですから、100MBという値 は既に個人で配信できる量ではありません。 ## 低コストでデータ配信が可能な優れもの Torrentはこれらのコストをきわめて最小化することができま す。Torrentの仕組みを利用すれば、こういったサービスを個人 が提供する事ができます。 Torrent はデータをダウンロードするユーザーもデータの配 信に加わるようにする事でこの問題を解決しました。 当然のことですが、配信に加わるコンピュータが増えれば増え るほど配信できるデータ量は増えます。 例えば、2.5MBのデータ配信を配信するとしましょう。 これ は、同時に50人くらいに配信できます。しかし、これが限界で す。もしも、この50人が2.5MBの帯域をデータの配信に利用し てくれたら、50×2.5mb= 150mbの配信が可能になります。 3000人程度にデータを配信できます。 さらに、この3000人がデータの2.5MBの帯域を利用してくれ たら、3000×2.5mb=7500mbの配信が可能です。これは、15万 人に配信が可能な規模です。 Torrentはこのような仕組みを実際に形にしました。Torrentによ って、データを欲しがっている全ての人に素早くデータを配信 する事ができるようになったのです。 Kyorohiro work # ゴール * \*\*本書の目的は、P2Pが難解な問題であるという誤解 をとく事\*\* 本書は、Torrentプロトコルについてまとめたものです。しか し、作者(kyorohiro)はBittorrent(オリジナル)の作成者ではないので、その仕組みや、その仕組みにした意図をすべて組み取ることはできま せん。 本書に記載されている内容は、kyorohiroが解釈し解決 した事が書かれています。オリジナルではありません。オリジナルのように思案して、思考できるようになるべく、Torrentクローンを作成しました。その仕組みを理解して実現しました。そして、独自のP2Pネッ トワークを思案して検討するに至ります。しかし偽物です。 色々書いていますが、偽物のの発言ですから「そのように解釈したのか？」「それは違うのではないか？」「この人、もしかして理解できていないのでは？」的な視点で見てもらうのが、丁度良いと思います。 ## 本書が目指すゴール 本書を読む事で、誰もがP2Pアプリを作る事ができるようになります。P2Pで動画配信、P2Pを応用した柔軟なネットワークについて思案し、実現できる事ができるようになります。 P2Pと聞いて「何か難しい事をしているのではないか？」「DHTと聞いて、高度な数学的難解な問題？」といった誤解を解きます。 本書を読んだ後もP2Pはなんら難しい事ではなくて、小学生が算数の問題を解くような簡単な問題なのだと理解していることでしょう。そして、あなたは、最新の論文を読み。それも足らず、新たな仕組みを提案する側にたっているに違い有りません。 Kyorohiro work # Torrentファイルを読み込む ![](/files/-LALzsNnLeP5gyDxkXXX) # About * **Torrent ファイルを読みこんでみよう** Torrentでのデータのダウンロード処理は、Torrentファイルを読み込むことから始まります。 それにならい、実際に Torrent ファイルを読み込み、必要な情報を取得するところからはじめて見ましょう。 Torrent File には、さまざまなP2Pのエッセンスが含まれています。ダウンロードするデータが適切なものであることを、どのように判別するのでしょうか。P2Pネットワークを構築するにあたり、必要な情報は何なのでしょうか? 本章を通じて紹介していきます。 Kyorohiro work # Bencode * **Torrentファイルはbencodeで書かれている。** * **Bencodeは、Integer、String、List、Dictionaryを扱える。** ## Torrentファイルは Bencoding Torrentファイルは、bencode という形式で書かれています。 Torrentファイルに記載されている事を読み解くためには、 bencode を解釈できるようにならなくてはなりません。まずは、Bencode のパーサーを書いていきましょう。 Bencodingは、文字列、整数、辞書、リストの4つのデータを 扱うことができます。 ``` beninteger : “i” [0-9]* “e” benstring : “:” string length : [0-9]* bendiction : “d” “e” benlist : “l” “e” benobject : beninteger | benstring | bendiction | benlist listelements : benobject ( benobject)* dictelements : benstring benobject (benstring benobject)* ``` そして、上記のようなフォーマットで書かれています。 #### 文字列(String)を扱える Bencode で文字列は、「<文字の長さ> “:” <文字>」という形式 で書かれています。例えば、「torrentという文字列は、 bencodeでは、「7:torrent」と書く事ができます。 もうひとつ、bencode の文字列は、バイトデータとして扱われ る事もあります。IPアドレスのバイト表示や、Hash値などの非 アスキーな範囲のデータなども、本形式で扱うことができます。 例えば、日本語で「アイ」はSJISで表現すると「0x83, 0x41, 0x83, 0x43」の4バイトで表現できます。この場合、Bencode では、「4:アイ」と表記できます。 **oden を、Bencodeで表現する** ``` 4:oden ``` **おでん(SJIS)を、Bencodeで表現する** ``` 6:オデン ``` **SHA1Hashデータを、Bencodeで表現する** ``` 20: ``` #### 整数(Number)を扱える 整数は0より大きな値を表現するデータです。「“i” \*\[0-9] “e”」 という形式で表すことができます。例えば、1024は「i1024e」 と書くことができます。 ファイルのサイズ、ポート番号、といった、数字で表現できる ものに利用します。 **2 を、Bencodeで表現する。** ``` i2e ``` **1024を、Bencodeで表現する** ``` i1024e ``` **3.14を、Bencodeで表現する** 「3.14」BencodeのNumber表見する事ができません。扱えるのは整数値だけです。 #### リストを扱える リストは複数のデータを順序ありで保持することができます。 Bencodeでは「"l" "e"」という形式で表すことができます。 例えば、所持してる本、「てんで性悪キューピッド」「幽☆遊☆白書」「レベルE」「HUNTER×HUNTER」といった本の一覧は、個別に Bencodeで表現すると、「22:てんで性悪キューピット」、「12:幽☆遊☆白書」、「7:レベルE」、「13:HUNTER×HUNTER」となります。 これをListで「l22:てんで性悪キューピット12:幽☆遊☆白書7:レベルE13:HUNTER×HUNTERe」とまとめる事ができます。 **「あいうえお、かきくけこ」をBencodeで表現する** ``` l12:あいうえお12かきくけこe ``` **「128、 100、500」を、Bencodeで表現する** ``` li128ei100ei500ee ``` ### 辞書 辞書はキーワードとデータを関連づけて保持する事ができます。「 “d” “e”」という形式で表現できます。 例えば、RPGゲームの主人公のパラメータとして、名前、レベル、習得した魔法、といったものが設定されているとしましょう。 名前を勇者、レベルが1、習得した魔法をハリトとカティノとしてみましょう。それぞれBencodeで、「4:名前」「4:勇者」「6:レベル」「i1e」「4:魔法」、「l6:ハリト8:カティノe」と表現できます。 これらをまとめて、「d4:名前4:勇者6:レベルi1e4:魔法l6:ハリト8:カティノee」と辞書で表見できます。 **levelが13で、nameが山田、Bencodeで表現する** \`\` di5:leveli13e4:name4山田e \`\`\` ## 今後の表記について 今後、データ構造を表す場合は、以下の表記を利用します。 リスト 「li512e4:teste」は、\[512,"test"] 辞書 「d5:leveli13e5magic6halitoe」は {level:13,magic:"halito"} Kyorohiro work # Bencodeの実装 * **Bencodingはパースしやすい構造** * **BNFから機械的にコードを抽出** ## 見慣れたデータ構造に落とす Benodingを実装してみましょう。Bencodingで扱えるデータは、Number, String, List, Dictionary でした。これらを、Dartから扱えるようにしましょう。 具体的には、Dartでサポートされているデータ構造に変換していきます。DartのNumber,Uint8Array,List,Mapへ変換していきます。 BencodeのNumberは、Dartのnumで表現できます。BencodeのStringは、UInt8Arrayで表現できます。Stringでないところは少しトリッキーです。Bencodeでは、バイト配列を扱うこともあります。Unicodeでは使えないデータもStringとして扱うことになりまいから、Stringでなく、UInt8Arrayを利用します。Bencodeのリストは、Dart言語の Listで、Bencodeの辞書は、Dart言語では Map で表現できます。 具体的には、以下のようなAPIを考えます。 ``` class Bencode { static Uint8List encode(Object obj); static Object decode(List buffer); } ``` もちろん、Bencodeの実装は見慣れた形式に落とす方法だけではありません。BencodeのStringはBenString、ListはBenList、DictionaryはBenDict、といった専用のクラスに変換する方法も可能です。 Dartの Map は、BencodeのMapよりも扱える範囲が広いですから、Dartのデータ構造から、Bencodeのデータ構造へ変換ができないパターンがあります。例えば、以下のような形式はBencodeでは表現できません。 ``` int // 0.1 といった少数点を含む場合 // -1といつたマイナス値を含む場合 Map // keyがStringでない場合 ``` このような制約がある事を、BenString, BenList といった構造を定義する事でAPIとして表現する事ができます。 しかし、今回は「見慣れた構造に落とす」という方針で設計しました。 ## Bencodeはパースしやすい構造 Bencode はパースが容易な構造になっています。なぜならば、 どのデータ構造なのかが、最初の一文字目で判別する事ができるからです。 “i” ならば、整数。 “0123456789” のどれかならば、文字列、”l” ならばリスト、”d” ならば辞書 といった感じです。 これを、コードに直すと、以下のような感じになります。 ``` int index = 0; Object decodeBenObject(Uint8List buffer) { if( 0x30 <= buffer[index] && buffer[index]<=0x39) {//0-9 return decodeBytes(buffer); } else if(0x69 == buffer[index]) {// i return decodeNumber(buffer); } else if(0x6c == buffer[index]) {// l return decodeList(buffer); } else if(0x64 == buffer[index]) {// d return decodeDiction(buffer); } throw new ParseError("benobject", buffer, index); } ``` 見ての通り、先頭の値に応じて処理が分岐しているだけで す。後は、おのおのデータ構造とみなして、変換してあげれば 完成です。 ## もっと Parser Torrentクライアントを実装するにあたり、さまざまなプロトコルを実装していきます。 プログラム言語や自然言語ほど、複雑ではないので容易に解析可能です。 このタイミングでBNFで定義された文法を解析する方法について解説します。 ### BNF から機械的にパーサーを書くことができる BNFで書かれた構文は機械的にパーサーを書く事ができます。 ``` • 規則名をメソッドにする。 • ルールに文字列がでてきた場合、一致するかチェックする • ルールに規則がでてきた場合、そのメソッドを呼び出す • ルールに違反かる場合は、Exception をスローする。 ``` プログラム言語、自然言語といったものは、もう少し工夫が必 要ですが、今回は、基本的なルールを守るだけで実装できま す。もう少し詳細な情報が欲しい場合は、「Language Implementation Patterns 」という本を読む事をお勧めです。 具体的に、Bencode 用のパーサーを作成しながら、見ていきま しょう。 例えば、Dictionary は以下のように書けます。 ``` Map decodeDiction(data.Uint8List buffer) { if(buffer[index++] != 0x64) { throw new ParseError("bendiction", buffer, index); } Map ret = decodeDictionElements(buffer); if(buffer[index++] != 0x65) { throw new ParseError("bendiction", buffer, index); } return ret; } ``` BNFと一対一の関係がある事が解ると思います。Dictionary は 27 「 “d” bendictionelements “e”」と文法で表現されます。ですか ら、”d”という文字か確認。 dictionelements のメソッドを呼 び出す。“e”という文字か確認する。 ルール通りです。 ## テストを書く テストを書きながら、パーサーを書いていきましょう。まずは 整数からです。 ``` unit.test("bencode: number", () { num ret = hetima.Bencode.decode(toBuffer("i1024e")); unit.expect(1024, ret); }); ``` このテストを満たすように、パーサーを書きます。bencodingで整数は、 「“i” \*(0-9) “e”」と書けます。なので、これもル ールに従って以下のように書けます。 ``` num decodeNumber(data.Uint8List buffer) { if(buffer[index++] != 0x69) { throw new ParseError("bennumber", buffer, index); } int returnValue = 0; while(index 事の顛末を知りたい方は参照してください。 Kyorohiro work # TorrentFileの中身 * **TorrentファイルはBencodingで記載されている** * **Trackerのアドレスが記載されている** * **ファイル名が記載されている** * **ブロックデータごとのSHA1 Hashが記載されている** ## Torentファイルを読み込んでみよう 無事、Bencodeのパーサーを書く事ができました。これで、 Torrentファイルの中身を解析できます。Torrentファイルの中身 を確認してみましょう。 さっそく、Torrentファイルを読み込んでみましょう。Parserを 作成していない方は、「 dart\_hetimalib\_test/tree/master/hetimalib\_sample/TorrentFileParser」を利用してください。 読み込んで見ると以下のようなデータ構成である事がわかりま す。 ``` { "announce":http://example.com/tracker, "created by":torrent generator, "creation date":1364723642, "encoding":utf-8, "info":{ "length":1024, "name":xxx "piece length":16384, "pieces":<......20バイト単位のバイナリデータ> } } ``` ### announce Tracker サーバーのアドレスが記載されています。本アドレス のサーバー にからデータを配信してくれる端末を紹介してもらえます。 ### created by 本ファイル生成したツールを示す名前のようです。 ### creation date 本ファイルが生成された日にちを表しているようです。 ### info.length 配信されているデータのサイズです。1024byte のデータである 事がわかります。 ### info.name 配信されているデータのファイル名です。xxx という名前であ る事が解ります。 ### piece length データを配信する際に、分割するサイズです。16kb単位で分割 する事がわかります。 ### pieces 分割されたデータごとのHash値です。データーの正当性を判定 するのに使用します。 ## ファイルが複数の場合 ひとつのファイルを配信するデータは説明した通りです。複数 のファイルをパッケージする場合は、もう少し構造が複雑にな ります。 ``` { "announce":http://example.com/tracker, "created by":torrent generator, "creation date":1364723642, "encoding":utf-8, "info":{ “files”: [ { length:512, path:[aaa, bbb.mp3] }, { length:1024, path:[ccc, ddd.mp3] }, ] "name":xxx "piece length":16384, "pieces":<......20バイト単位のバイナリデータ> } ``` さきほどのと比較すると、info辞書の中に、files リストが増え ています。今回の場合だと、「xxx/aaa/bbb.mp3」、「xxx/ccc/ ddd.mp3」という2つのデータが含まれている事が読み取れま す。 ## Torrentファイルを作成してみよう これらの理解できた事を整理して、理解出来ていない事を発見 しながら、Torrentファイルを作成するツールを作成してみまし ょう。無事作成できたならば、だいたいは理解できたという事 になります。既に、Bencoding のパーサーはありますから、ゴ ールは目の前です。 ``` { Map file = {}; Map info = {}; file[TorrentFile.KEY_ANNOUNCE] = announce; file[TorrentFile.KEY_INFO] = info; info[TorrentFile.KEY_NAME] = name; info[TorrentFile.KEY_PIECE_LENGTH] = piececSize; info[TorrentFile.KEY_LENGTH] = targetLength; info[TorrentFile.KEY_PIECE] = pieceBuffer; Bencode.encode(file); } ``` といった感じで、必要な情報をMapに配置して、Bencode にエ ンコードすれば完成です。 実際に作成してみると、明らかでなかった点が現れてきます。 例えば、ファイルが複数ある場合は、pieceデータをどのよう に算出するのでしょうか？ まだ、明らかになっていませんでし た。2つ生成する方法を思いつきました。どちらかが、Torrent で採用されている方法だと良いのですが..。 1. ファイル単位で、pieceデータを作成する。 2. 複数ファイルは結合してひとつのファイルと見なしてから、pieceデータを作成する。 実際に試してみたところ、 2の方法が採用されているようで す。具体的には、 ``` { Blob fileA =... Blob fileB =... Blob image = new Blob([fileA, fileB]); FileReader reader = new FileReader(); reader.readAsArrayBuffer(image).then((e){ int start = 0; do { int end = start+pieceLength; if(end # Httpサーバーを作成してみる * socketでプログラム # UPnpによるポートマップ ![](/files/-LALznTzrkTPc7xvb4t_) # UPnPによるポートマップ * **Natを越えないとP2P通信できない** * **UPnPを使えば、TCPでもNat越えができる** Socketを使う事で簡単に、インターネットを利用したアプリケーションが作成する事ができます。プラウザーとかメーラーとかです。 しかし、P2Pアプリケーションを作る場合は、もう一つ考慮しなくてはならない事があります。それが、「Nat越え」です。 P2Pアプリとして、必ず満たさなければならない条件は、何でしょうか？ それは、ユーザーが所有する端末同士が直接データ通信をできる事です。P2Pの定義そのものですね。 これができません。 Nat越えをする方法はいくつかあります。本章では、UPnPを用いてNat越えをする方法について解説したいと思います。 ## Global IP が必要 P2P通信するするためには、相手に自分の「IPアドレス」と「Port番号」を教える。必要ががあります。しかし、Nat越えの問題を解決しないと、これができません。 ご家庭からインターネットにアクセスする場合、ルーターというデバイスを利用しています。 ルーターは、ルータに接続している端末に 「Private IP」 を割り振ります。 ``` >> netstat ``` とコマンドを入力してみましょう。「192.168.100.1」といったアドレスが端末に割り振られている事が確認できます。このアドレスを相手に伝えても、通信ができません。 ### ルータから教えてもらおう しかし、ルーターからインターネットに接続できているという事は、「Global IP」をルーターは持っているから通信できるのです。つまり、ルーターは「Global IP」をルーターは知っている。しかし、ルーターを利用している端末は「Global IP」をしらないという問題があります。 ## UPnPを用いてPort Mappingをしよう UPNPを実現するには、UDPとTCPを用いて通信できる必要があります。 具体的には、 * UDP Multicast を利用して、使用中のルーターに、ポートマッピングを依頼するためのアドレスを教えてもらう。 * TCP を使って、教えてもらったアドレスからポートマッピングの依頼をだす。 といった事をします。実際にTryしてみましょう。 ### 依頼先を調べる UDPで以下のメッセージを通知する ``` M-SEARCH * HTTP/1.1 MX: 3 HOST: 239.255.255.250:1900 MAN: "ssdp:discover" ST: urn:schemas-upnp-org:service:WANIPConnection:1 ``` もしもルーターが存在していれば、以下のような返答があります。 ``` HTTP/1.1 200 OK CACHE-CONTROL: max-age=1800 ST: urn:schemas-upnp-org:service:WANIPConnection:1 USN: uuid:E8088BD3-E808-8BD3-A042-E8088BD3A042::urn:schemas-upnp-org:service:WANIPConnection:1 EXT: SERVER: E588 UPnP/1.0 MiniUPnPd/1.6 LOCATION: http://192.168.100.1:54616/rootDesc.xml OPT: "http://schemas.upnp.org/upnp/1/0/"; ns=01 01-NLS: 1 BOOTID.UPNP.ORG: 1 CONFIGID.UPNP.ORG: 1337 DATE: Sun, 14 Sep 2014 00:42:14 GMT ``` LOCATIONで指定されたアドレスのXMLファイルのタグの中に依頼先のアドレスが記載されています。このアドレスへ依頼をだせば、インターネットから、あなたの端末へアクセスできるようになります。 ### 外部の端末から見えているアドレスを聞く ``` POST 192.168.100.1 HTTP/1.1 Host: 192.168.100.1 Connection: close SOAPACTION: "urn:schemas-upnp-org:service:WANIPConnection:1#GetExternalIPAddress" Content-Length: 324 ``` 成功すると、以下のような返信を受け取ります。 ``` HTTP/1.1 200 OK Content-Type: text/xml; charset="utf-8" Connection: close Content-Length: 360 Server: E588 UPnP/1.0 MiniUPnPd/1.6 EXT: DATE: Sun, 14 Sep 2014 01:46:07 GMT ``` ### ポートマッピングの依頼をだす ``` POST 192.168.100.1 HTTP/1.1 Host: 192.168.100.1 Connection: close SOAPACTION: "urn:schemas-upnp-org:service:WANIPConnection:1#AddPortMapping" Content-Length: 629 48083 TCP 8083 192.168.100.100 1 test 0 ``` ``` HTTP/1.1 200 OK Content-Type: text/xml; charset="utf-8" Connection: close Content-Length: 263 Server: E588 UPnP/1.0 MiniUPnPd/1.6 EXT: DATE: Sun, 14 Sep 2014 01:39:27 GMT ``` Kyorohiro work # UPnPの実装 * **UDPでSSDPグループに参加する** * **UDPでSSDPグループからデバイスを検索する** * **TCPでルーターへリクエストを送る** ## UPnPを実装しよう 概要は説明した通りです。実際に実装してみましょう。サンプル実装を以下におきました。 * ライブラリ * サンプルアプリ 実際に作ってもらうのが、もっとも効果的です。しかし、そんな時間がない方がほとんどでしょう。また、UPnP用のライブラリを利用するので、実装をする必要がないという方もいることでしょう。 なので、本章では実際に実装しながら、処理の流れを解説していきます **注意** Dart を利用するのてすが、Socket API は、hetimanetを使用します。2015/6/1において、Dart用に提供されている socketは、"chrome api ver1 " "chrome api ver2"、"dart:io"等いくつかあります。 利用するAPIに依存しないように、hetimanetでsocketを再定義して対応することにしました。 ### SSDPグループに参加する 通常、UDP Socketを生成して、IPが"239.255.255.250"、Portが"1900"のグループに参加します。 参加することで、SSDPグループに追加されたデバイス等が把握できるようになったり、グループに参加していないデバイスを無視したりできるようになります。 しかし、Chrome Socketから、上手く動作できなかったので、今回は、グループに参加していません。 #### **(1) UDPソケットを生成する。** まずは、UDPソケットを生成しましょう。こんな感じです。 ``` HetiSocketBuilder _socketBuilder = new HetiSocketBuilderChrome(); HetiUdpSocket _socket = _socketBuilder.createUdpClient(); _socket.onReceive().listen((HetiReceiveUdpInfo info) { print("receive udp info"); }); _socket.bind("0.0.0.0", 0).then((int v){ if (v >=0) { print("bind ok"); } else { print("bind error"); } } ``` 「bind ok」とコンソールに文字が表示されれば成功です。 #### **(2) SSDPグループからデバイスを検索する** 無事にUDPソケットを生成できる事を確認できたら、次はSSDPグループに、ポートマップに対応できるデバイスがないか依頼を出します。 ``` _socket.send( convert.UTF8.encode(SSDP_M_SEARCH_WANPPPConnectionV1), SSDP_ADDRESS, SSDP_PORT).then((HetiUdpSendInfo iii) { print("send ok"); }).catchError((e) { completer.completeError(e); }); ``` 先ほど生成したUDPSocketを利用して、"239.255.255.250"、Portが"1900"に 以下のメッセージを送っているだけです。 ``` M-SEARCH * HTTP/1.1 MX: 3 HOST: 239.255.255.250:1900 MAN: "ssdp:discover" ST: urn:schemas-upnp-org:service:WANIPConnection:1 ``` 難しい事はないですね。これで、UPnPに対応したルーターが存在していれば、前の章で説明した。タグを含むxmlファイルを取得できます。 #### **(3) グローバルIPを取得する** ルーターへ依頼をだせるようになりました。試しに、ルーターにGlobal IPについて問い合わせて見ましょう。 UPnPに対応しているルーターは、TCPサーバーが立ち上がっています。TCPサーバーへリクエストを送ります。 ``` HetiHttpClient client = new HetiHttpClient(new HetiSocketBuilderChrome())); client.connect(host, port).then((int v) { return client.post(path, convert.UTF8.encode(body), { KEY_SOAPACTION: soapAction, "Content-Type": "text/xml" }); }).then((HetiHttpClientResponse response) { print("receive response"); }).catchError((e){ print("failed request"); }); ``` 前章で説明した値を、pathとbodyに設定すれば無事リクエストを送信できます。 ## 作成したライブラリは以下の通り * ルータを発見する ``` UpnpDeviceSearcher .createInstance(new hetimacl.HetiSocketBuilderChrome()) .then((hetima.UpnpDeviceSearcher searcher) { searcher.onReceive().listen((hetima.UPnpDeviceInfo info) { }); searcher.searchWanPPPDevice(); }); ``` * ポートマッピングする ``` UpnpPPPDevice#addPortMapping( localIP, localPort, remotePort, UPnpPPPDevice.VALUE_PORT_MAPPING_PROTOCOL_TCP) .then((UpnpPortMappingResult r) { }); ``` * グローバルアドレスを調べる ``` UpnpPPPDevice#requestGetExternalIPAddress() .then((String address){ }); ``` * ポートマッピングする ``` UpnpPPPDevice#addPortMapping( localIP, localPort, remotePort, UPnpPPPDevice.VALUE_PORT_MAPPING_PROTOCOL_TCP) .then((UpnpPortMappingResult r) { }); ``` * グローバルアドレスを調べる ``` UpnpPPPDevice#requestGetExternalIPAddress() .then((String address){ }); ``` Kyorohiro work # Trackerへアクセスしてみる ![](/files/-LALzrlGrSsKDmygJdXQ) # About * **データを配信してくれるPeerを探すところから始まる** * **Trackerサーバーを利用する方法について解説します** これまでの成果で、Torrentファイル から必要な情報を取り 出す事が出来るようになりました。Torrentクライアント は、 Torrentファイルを解析が終わると、Trackerサーバーにアクセスし ます。 P2Pアプリケーションは、データを配信してくれるPeerを探すところから始まります。Googleで検索ワードを指定しても欲しい情報を探すように、P2Pアプリもなんらかの方法で、データを配信してくれるPeerを発見する必要があります。TorrentはTrackerサーバーを利用する方法でこれを実現しています 本章では、実際に簡易の Trackerサーバーを作成しながら、Tracker から Peer の一覧を取得する方法について解説し ます。 (※) Torrentでは、Peerの一覧をP2Pネッワーク上で管理する方法も提供しています。DHTの章で紹介します。 Kyorohiro work # TrackerはHttpサーバ * **TrackerはHttpサーバ** * **Get リクエストでデータ** Tracker は Httpサーバーです。皆さんがいつも利用しているイ ンターネットのからサイトを表示するのと同じルールで動作し ています。 例えば、インターネットで調べ物をしたい時に、Googleを利用 すると思います。ChromeなりFirefoxなり、IEなどを利用し て、「 」にアクセスします。すると、検索ワードを入力するためのページが表示されます。 Trackerもそれと同様の仕組みで動作しています。異なるのは、 人が見やすいように加工されたHtml形式のページを渡す変わり に、Bencodingでエンコードされたバイナリーデータが渡すところです。 ## Getリクエストで依頼をだす Tracker では、Getリクエストを利用して、データを配信してい るPeerの一覧を取得はます。Getリクエストは、URLの末端 に、「?xx=yyy\&mm=nnn」といった文字列を付与したもので す。 Googleなどの検索エンジンで検索した後、アドレスを確認してみてください。例えば、androidと検索した場合、「? q=android\&oq=android」といった文字列が追加されていると思 います。「q=」の後に検索ワードの「android」が続いています。 このように、Getリクエストは、アドレスにサーバーへしてほしい指示やデータを含めることができます。 Trackerも同様の仕組みで、依頼をだしています。 ## Httpサーバーを作成しよう TrackerがHttpサーバーである事がわかったところで、 Http サーバーを作成してみましょう。Dart言語では、簡単にHttpサー バーを作成する事ができます。 まずは、ブラウザーからGetリクエストを受け取った時にHello と表示してみます。 ``` { HttpServer.bind(address, port).then((io.HttpServer server) { server.listen((HttpRequest request) { request.response.write("hello"); request.response.close(); }); }); } ``` といった感じで書けます。Getリクエストで渡された値を知り たい場合には、「request.uri.queryParameters」として、確認 できます。例えば、「 test」というキーで渡された値を相手に返すコードは以下のよ うに書けます。 ``` { HttpServer.bind(address, port).then((io.HttpServer server) { server.listen((HttpRequest request) { Map parameter = request.uri.queryParameters; request.response.write("hello"+ parameter[“test”]); request.response.close(); }); }); } ``` これで、Getリクエストを扱う事ができるようになりました 。後は、このリクエストに応じて、Peerの一覧、つまりは、 今までリクエストしてきた端末のアドレス等を渡せば、簡易の Trackerサーバーが完成します。 Kyorohiro work # リクエストの中身 * **peer id を生成する** * **info 辞書 の Hashを生成する** * **portを用意する** * **アドレスを生成する** * **Get リクエストでデータ** 実際に、Trackerサーバー とTrackerクライアント の間でやり取 りされるデータの形式について解析していきます。 Tracker はデータを配信している Peer の一覧を管理していま す。以前解説した通り、Torrentではデータをダウンロードする 側もデータの配信にまわるのでした。 Torrent ではこの仕組みを実現するために、Trackerへ自身を登 録する対価として、Peerの一覧を取得できるような仕組みにな っています。 ## データ配信に必要なものが入っている データ配信に必要なものは、配信するデータ、配信するサーバ ーのIPアドレス、配信するサーバーのポート番号、配信する端 末のID、どのデータを配信かるかの情報です。 まず一つ目、配信するデータは、Trackerに初めてアクセスす る時には持っていないものなので、ここでは除外しましょう。 次に必要と思われるのが、IPアドレスです。このアドレスも用 意する必要ありません。TrackerがあなたのIPアドレスを知って いるからです。具体的には、Trackerにアクセスする際に、自身 のIPアドレスをTrackerは知る事ができます。 例えば、Httpサーバーで通信相手のIPアドレスを返すようなプ ログラムは以下のような感じで書けます。 ``` { HttpServer.bind(address, port).then((io.HttpServer server) { server.listen((HttpRequest request) { request.response.write(request.connectionInfo.remoteAddress.toString();); request.response.close(); }); }); } ``` このように、Httpサーバーは、相手のIPアドレスを知っていま す。なので、リクエストに含める必要はなさそうです。 その次に必要と思われるのはポート番号です。他のPeerからの 接続を待ち受けるには、IPアドレスとPort番号が必要です。 Tracker は待ち受けしている Port 番号を IPアドレス のように 知るすべはありません。リクエストとして通知してあげる必要 がありそうです。 最後に、IDが必要です。Peerを識別する情報としてIPアドレス を利用する方法が考えられます。しかし、IPアドレスは複数の 端末で共有している場合や、通信環境によっては同一のIPアド レスを長時間維持するができなかったりします。 そこで、Peerごとに識別子を自身で生成して、それを利用しま す。 もう一つ、必要なものがありました。どのデータをダウンロー ドしたいかといった情報です。Trackerは同一のアドレスで多数 のデータを配信するPeerを管理することがあります。どのデー タを配信してほしいのかを Tracker に通知する必要がありま す。 だいたい、リクエストら必要な情報が見えてきました。具体的 にGetリクエストで使用する値について見ていきましょう。 ## Info辞書からIDを生成 まずは、どのデータをダウンロードしたいかを指定するための IDを用意しましょう。 Torrent が扱う全てのデータは衝突しな い固有の識別子を持っています。これは、ひとつの配信データ を複数の Tracker で管理したい場合に有効な方法です。唯一の IDで有るならば、このTrackerで管理しても、関係のないデー タが混ざる事がないからです。このような方法を用いる事で、 Tracker への負荷を分散する事が可能になります。 では、どのように唯一IDを生成するのでしょうか。特定の管理 団体などにIDをもらう必要があるのでしょうか？Torrentでは SHA1 が用いられています。 SHA1 は、全てのデシタルデータに 160bit(20byte) の ID をふ るアルゴリズムです。2の160乗のIDの振る事ができますから、 異なるデータなのに、同じIDを振られる事はありません。 Torrentでは、Info辞書のSHA1をとりIDとして利用します。 Dartでは以下のように書けます。 ``` { data.Uint8List list = Bencode.encode(file.mMetadata[TorrentFile.KEY_INFO]); crypto.SHA1 sha1 = new crypto.SHA1(); sha1.add(list.toList()); sha1.close(); //return value is id } 見ての通り Torrentファイルのなかの Info 辞書の部分のバイナ リでデータのSHA1をとるだけです。 ## 自身のIDを用意する Info辞書の識別子と同様に、自身のIDも20バイトのバイナリデ ータを利用します。そして、IDの生成は各Torrentクライアント 行います。IDの生成は、Info辞書のSHA1をとった時のように明 確に生成するルールは存在していません。 他の Torrent クライアントが生成したIDと衝突しない用に注意 し生成する必要があります。 ここでは、「乱数を使う方法」を紹介します。 ``` class PeerIdCreator { static math.Random \_random = new math.Random(new DateTime.now().millisecond); static List createPeerid(String id) { List output = new List(20); for (int i = 0; i < 20; i++) { output\[i] = \_random.nextInt(0xFF); } List idAsCode = id.codeUnits; for(int i=0;i<5&\&i\ } ``` これで、レスポンスされデータの形式については、済みまし た。では、実際にTrackerサーバー、Trackerクライアントほ実 装してみましょう。 Kyorohiro work # テスト * *Trackerサーバーを動作させて理解を深めよう.る\** 実際に Trackerサーバー を作って動作確認してみましょう。優 れた Tracker サーバー を作るのは大変です。もしかすると終わ りのない作業かも知れません。 依頼があった相手に渡すPeerの一覧をどのようにして選定する か。既にネットワークから離脱したPeerをどのようにして発見 するか？ といった問題は実際に観測してみて、実際に使ってみた結果を 分析して行くほかありません。 安直な Trackerサーバー は、こんな感じで作る事ができるでし ょう。 * Peerの一覧はシャッフルして最大50個渡す。 * Peerの一覧は200くらい記録する。他は古いものから廃棄 まずは、こんな感じで良いでしょう。 ``` ShuffleLinkedList managedPeerAddress = new ShuffleLinkedList(); void update(TrackerRequest request) { managedPeerAddress.addLast(new PeerAddress(request.peerId, request.address, request.ip, request.port)); if(managedPeerAddress.length > max) { managedPeerAddress.removeHead(); } } TrackerResponse createResponse() { TrackerResponse response = new TrackerResponse(); response.interval = this.interval; managedPeerAddress.shuffle(); for(int i=0;i<50&&i といったリクエストを受け取った事でしょう。Googleで 「scrape torrent」 で検索する unofficial なTracker拡張で利用 されるものである事が解る事でしょう。こんな感じで、実際に 動作させて見る事で、一気に理解の範囲が広がっていきます。 Kyorohiro work # ダウンロードゲームへ参加してみる ![](/files/-LALzmk3WSZwiM9uWMns) # About * **Torrentのダウンロードは、数学で有名なゲーム** * **本章では、このゲームについて紹介と実装をしていく** TrackerからPeerの一覧を取得てきるようになりました。Peer一覧を取得すると、Peerどうしでデータを配信しあうフェーズに入ります。 ## Torrentのデータ配信はゲーム P2Pでは、よく未解決な数学的な問題(ゲーム)を利用してプロトコルが設計されます。 例えば、Bitcoinは、「一定回数の「0」の連続から始まるハッシュ値」を計算して競うゲームを行います。このゲームが有効に実施されるのは、このハッシュ値を少ない時間で求める計算方法が存在していないから有効に動作するのです。 Torrentも同様に数学的に証明されていないゲームといいますか、悪意をもったユーザーが勝利しないとされているゲームを利用しています。 本章では、Torrentネッワーク上でPeerどうしが行っているゲームについて解説していきます。 ## ゲームを利用して、仕組みを構築する知見を得る 本章を通して、「数学的なパズルやゲームや未解決問題を利用して仕組みを構築する事についての知見」を得る事ができます。 皆さんが独自のP2Pネットワークを構築する時に必ずこの考え方は、有効なはずです。 Kyorohiro work # ダウンロードゲーム * **お互いにデータを配信しあう** * **同時に、複数のPeerからダウンロードする** * **ダウンロード速度が早いところからアップロードする。** * **アップロード速度が早いところかダウンロードする。** * **同時に、複数のPeerからダウンロードす** * **配信に協力しないTorrentには配信しない** TrackerからPeerの一覧を取得できるようになりました。TorrentのP2Pネットワークから、実際にデーターをダウンロードしてみましょう。 #### Torrent のダウンロードはゲーム Torrentクライアントどうしのデータのやりとりをダウンロードゲームと呼ぶ事にします。Torrentは特定のサーバーからダウンロードするのではなくて、Peerどうしで融通しあいます。この時の融通しあい方の、ゲーム性が高いのが、ダウンロードゲームと呼ぶ事にした理由です。 決まったルールに従ってダウンロードするのではなく、Peerどうしで駆け引きを行いお互いにダウンロード速度を競い合います。駆け引きのうまいAIは有利にデータをダウンロードできます。しかし、逆に駆け引きの下手なAIはダウンロードに時間がかかるといった感じです。 #### 悪意のあるPlayerもゲームの一部 このことによって、耐久性の高いネットワークを構築できます。決められたルールを適用している場合、そのルールの考慮漏れがある場合、、悪意のあるPlayerの暗躍を原理的に許す事になります。 しかし、悪意をもったゲームプレイヤーも、いちプイヤーとして考えて対処することになります。 この攻略方が見つかるまでは、(悪意のあるPlayerが勝つような)有効な仕組みとして働き続けます。 また、後述する「つきあいかたの科学」の中で紹介されている「おうむ返し戦略」が今のところもっとも強い戦略として知られています。そして、今もなお、有効なゲームであり続けてるのです。 ## Torrentはデーターを配信しあう Torrentでは、Peerどうしが所持してしいるデータを配信しあいます。 例えば、"まぎか.mp4" というデータをPeer A が所持していて、Peer B が このデータを欲しい場合 ![](/files/-LALzkOb0gvaN2REcCcz) Peer A が Peer Bにデーターを提供します。 同様に、Peer B が Peer A が欲しがるデータを所持していた場合、 ![](/files/-LALzkP5YaJ1zl7hr1Pe) "まぎか.mp4"をダウンロードしながら、"エスカ.mp4"を配信します。 ## Torrentはブロック単位で配信しあう Torrent の場合は、このデータを共有する単位は、ファイル単位ではなくて、ブロック単位で管理しています。 ``` { "announce":http://example.com/tracker, "created by":torrent generator, "creation date":1364723642, "encoding":utf-8, "info":{ "length":1024, "name":xxx "piece length":16384, "pieces":<......20バイト単位のバイナリデータ> } } ``` 上記のような、TorrentFile の中に記載されている、"piece length" の単位でデータを分割しています。 例えば、piece\_lengthが8で、\[0,1,2,3,4,5,........]というデータを持つ場合、 ![](/files/-LALzkRTPuApncnoMEHN) といった感じで、n個に分割します。 ## 効率よくデータを配信するほうほうを模索する。 効率よくデータをネットワーク全体に配信するために、Torrent Clientは様々な工夫を凝らします。 ### 1. 同時に、複数のPeerからダウンロードする 同時に、複数のpeerからデーターをダウンろロードします。これによって、いって時間にダウンロードできるデーター量が安定します。あるPeerの回線が混雑して遅くなっても、他の回線が早いpeerがその分をおぎなってくれます。 上がり速度よりも、下がり速度の方が早い回線がほとんどです。同時に複数のPeerからデータをダウウンロードすることで、下り速度いっぱいをり利用してダウンロードすることも可能です。 ### 2. ダウンロード速度が早いところへアップロードする。 ダウンロード速度は、回線の速度、混み具合、経路などによって、変化していきます。 Torrent Client は、通信状態を計測してして、アップロード速度が早いpeerからデーターをダウンロードするようにします。 Torrent Client で良く使われ方法として、同時にダウンロードするPeer数をK個に固定して、一定時間ごとに、アップロード速度がお遅かった、peerを、それ以外のダウンロード可能なpeerと入れ替えます。 これによって、ダウンロード速度が早いK個のpeerを探しつつ、現状で最適なPeerかたデーターをダウンロードできるようになりますようになります。 ### 3. 配信しないTorrentには配信しない 配信して欲しいデータを持っているPeerへデータを配信しているにも関わらず、Chokeされ続けている場合、Choke仕返します。 万物の等価交換が基本です。得たらその分を還元する事を相手に期待します。 #### 囚人のジレンマと「つきあい方の科学」 このような、敵対的な行動をする相手に対して、こちらも敵対的行動を示す事を、しっぺ返し戦略といいます。 この問題については、「つきあい方の科学」を参照してください。 Torrentの仕様は公開されています。なので、協調しないPeer を作成する事も可能です。例えば、ダウンロードだけとして配信しないTorrentとか。 このように利己的な Torrent Client が増えるとデータの配信が不安定になります。なので、長期的に考えて、データー配信に参加しないTorrentよりも、配信に参加したTorrent方がよりよい結果をうむ仕組みが必要になります。 **\[囚人のジレンマ問題なので、協調しないのが合理的]** | Peer A Peer B | 配信する | 配信しない | | ---------------- | ---- | ----- | | 配信する | 2 2 | 0 3 | | 配信しない | 3 0 | 1 1 | お互い協調すると、お互いに2の利益を得る事ができる。片方だけ配信すると、配信しない側だけ得をする。配信したPeerだけ4の利益を得る。お互いに配信しないとお互いに損をする。といった事がおきます。 利己的に判断すると、相手が裏切る場合を考慮した場合、合理的に自身の利益を最大化するために、データーを配信しないという選択をします。 * 相手が、「配信するを選択｣をしたとする場合、自分は「配信しない選択」が有効。 * 相手が、「配信するを選択」をしたとする場合、「自分は配信しない選択」をする方が有効。 つまり、相手の選択によらず、配信しない方がより良い利益を、得る事ができる。 つまり、データをダウンロード専用のTorrentクライアントを作れば、使う人が増えるに違いないとなるわけです。 **\[無限ゲームとして見ると、おうむ返しがメジャー]** 一度だけだと、裏切る事が最良の選択ですが、無限ゲームの場合だと少し状況が変わってきます。 「つきあいの科学」の中で、実際に行われた実験について解説されています。 囚人のジレンマに基づいて、「協調するか」、「裏切るか」の選択をおこなうゲームを行いました。AIどうしを戦わせるゲームです、さまざまな分野の方に協力してもらいました。 参加した人は、優勝を狙い様々なAIを組みました。「裏切り続けるAI」や「仏の顔は3度までAI」や「ランダムな選択をするAI」など、様々なAIが用意されました。ひのAIを網羅的に戦わせた結果、もっとも良い成績をのこしたのが、このおうむ返し戦略(TIT-FOR-TAT)なのです。 **\[予想される戦略]** 無限ゲームでは、おうむ返し戦略が有効な事がわかりました。しかし、有限ゲームではどうでしょうか。いつかは、ダウンロードは終わります。 たとえば、ダウンロードゲームの場合では、ダウンロード完了後に、協調することは合理的な選択でしょうか? 実際のところ、協力しても得られる利益はゼロです。配信する帯域分はマイナスともいえます。 このことから、予想される戦略は、データのダウンロードが完了するまでは、協力的だけど、データのダウアンロードが完了してしまうと、非協力的になる事が予想されます。 実際のところ、この推論はだいたいあっていて、インターネットでのTorrentの使い方として、データのダウンロードが終わったら、データー配信リストから削除する的な対応をするユーザーがかにれいるようです。 彼らの戦略はとても利己的、かつ合理的なのが解ると思います。 # ブロックデーターの実装 * **Bitfieldを実装** * **BlockDataを実装** ブロック単位でデータを管理するためのコードを書いてみましょう。 ## Bitfield実装 Bitfieldを実装していきす。 Bitfield Bool値(0, 1)を持つ任意の長さの配列です。 Torrentの場合だと、1がデータを持っている、0がデータを持っていないという事を表します。 ``` class BitfieldSample { List _data = []; BitfieldSample(int length) { _data = new List.filled(length, false); } bool operator [](int idx) => _data[idx]; void operator []=(int idx, bool value) { _data[idx] = value; } int get length => _data.length; } ``` Torrentはこの値をバイト配列として利用するので、変換するメソッドを用意しておきましょう。 ``` class Bitfield { .... .... List toBytes() { int bytesLengths = _data.length ~/ 8 + (_data.length % 8 == 0 ? 0 : 1); Uint8List ret = new Uint8List(bytesLengths); for (int i = 0; i < _data.length; i++) { if (this[i] == true) { ret[i ~/ 8] |= 0x80 >> (7 - (i % 8)); } } return ret; } } ``` こんな感じです。0x80が先頭Bitで、0x01が末Bit端なのが特徴です。 ## BlockDataの実装 BlockDataで扱うデータは、メモリーに収まらないことがあります。OSのイメージとかだと1GByteをこえます。ファイルとかで扱うと思います。 しかし、テストを書いたりする場合は、メモリーに収まるデータのみを対象としたほうが扱いやすいですし。場合によっては、ファイルではあるけどねクラウド上のファイルだったりします。 ここでは、以下のような、インターフェイスを利用することにします。 ``` abstract class HetimaData { async.Future getLength(); async.Future write(Object buffer, int start); async.Future read(int offset, int length, {List tmp:null}); } ``` BlockDataは、Blockごとにデータの状態を管理します。なので、blockごとにデータを所持しているか、所持していないかを判断できるようにします。 ``` class BlockDataSample { BitfieldSample _info = null; HetimaData _data = null; int _blockSize = 0; int _fileSize = 0; BlockDataSample(int fileSize, int blockSize, HetimaData data) { _info = new BitfieldSample(fileSize ~/ blockSize + (fileSize % blockSize == 0 ? 0 : 1)); _data = data; _blockSize = blockSize; _fileSize = fileSize; } bool operator [](int idx) => _info[idx]; int get length => _info.length; } ``` ブロックごとにデータごとにも書き込み、読み込みの機能を追加します。 ``` Future writeBlock(int index, List data) async { WriteResult ret = await _data.write(data, index * _blockSize); _info[index] = true; return ret; } Future readBlock(int index) async { int start = index * _blockSize; int end = (start + _blockSize > _fileSize ? _fileSize : start + _blockSize); return _data.read(start, end - start); } ``` これで完成です。 # 配信用、Peerを作成してみよう * Handshakeする * ダウンロード許可を与える * リクエストされたらデータをアップロードする #### 駆け引きのないAIから作成してみよう 実際にデータ配信用のPeerを作成してみましょう。ただし、初めから、ダウンロードゲームで良い結果を生むAIを作成するのは難しいです。 まずは、簡単なところから手をつけていきましょう。 データを配信するだけのTorrent Clientを作成してみましょう。 駆け引きとかはありません。データの配信リクエストを受けとったら、その指示通りデータを配信するといったものを作成していきたいと思います。 #### ダウンロードゲームへ参加方法を学習しよう 実際に実装してみて、ダウンロードゲームに参加してみましょう。実際に実装してみて、その振る舞いを観察してみましょう。 メッセージがどのように使われているか?仕様の認識が間違っていないか? などを把握する事ができます。 ## まずば、HandShakeする。 まずは、ハンドシェイク処理を行います。Torrent Clientがサポートしているプロトコルは何か?このセッションでやりとりするデータは何かを交換します。 中身はこんな感じ。 ![](/files/-LALzrpcs2wvDJ9WO2dv) 19はプロトコル名の長さ、"Bittorrent protocol"がプロトコル。 reserved は、拡張用に予約されている領域。infohash の部分がtorrent file を識別するのに使用するID。peer\_id がpeerを識別するIDです。 Trackerから、IPアドレスとPort番号を教えてもらうと、Torrent Clientは、このメッセージを送信します。 InfoHashを検証して、回線に余裕があれば、相手からもこのメッセージが送信されます。 これで、ハンドシェークの完了です。 ## 所持しているBlockを相手に伝える。 次に所持しているデーターを相手に伝えます。 ![](/files/-LALzrqCCjKr0DVU_Xcg) length がメッセージの長さ。5 がメッセージを識別するID。Bitfieldはlength-1バイトの大きさを持つBitfieldデータ。 ## 相手にダウンロードする許可を与える。 次に、相手にダウンロードする許可を与えます。unchokedメッセージを渡します。 ![](/files/-LALzrqoaYUMygObXoqq) 0001がメッセージ長で、1がunchokeを示すIDです。 ## データのダウンロードに興味がないことを伝える 配信専用なので、通信相手からデータをダウンロードする趣旨がないことを伝えておきましょう。 ![](/files/-LALzrrJqOa-qDybKweh) 0001がメッセージ長で、3がnotintersted、エッセージである事を示すIDです。 ## データを配信する Torrent Clientでは、配信リクエストを受けたBlockを配信します。れクエストがない状態でデーターを配信することはありません。 Requestメッセージが相手から送られます。 ![](/files/-LALzrs0-7YCoDATMsXC) indexが、Blockの位置、beginとlengthがアップロードして欲しい、開始位置、その長さです。 だいたい、16\*1024 byteの単位でレクエストしてきます。 Pieceメッセージを返します。 ![](/files/-LALzrsczIqf_OsivF6F) ## その他のメッセージ これで、データ配信で利用するメッセージは網羅しました。他にもいくつか紹介できていないメッセージかるあるので紹介します。 ### メッセージの構造 HandShake以外のメッセージは、決まった構造をしている事にお気づきでしょうか? ![](/files/-LALzrtYYbNvrn2WzgZz) こんな感じです。最初の4バイトが、メッセージの長さです。次にIDが渡されます。そして、メッセージの中身が渡されます。 | メッセージ名 | Length | ID | 内容 | | ----------- | ----------- | -- | ---------------- | | KeepAlive | 0 | なし | 通信可能かチェック | | Choke | 1 | 0 | ダウンロード不許可 | | Unchoke | 1 | 1 | アップロード許可 | | Interest | 1 | 2 | ダウンロード許可要求 | | NotInterest | 1 | 3 | ダウンード許可不要 | | Have | 5 | 4 | 所持しているBlockを知らせる | | Bitfield | 1+bitfield長 | 5 | 所持しているBlockを知らせる | | Request | 13 | 6 | ダウンロード要求 | | Piece | 13+データ長 | 7 | データアップロード | | Cancel | 13 | 8 | ダウンロード要求破棄 | # 基本戦術 * 10個のメッセージを利用する * Choke を利用してアップロード数を制限 * 配信に協力しないPeerをChokeする * 開始時でも、確率的に、2〜3のPeerからUnchokeされる ## 10個のメッセージを利用する | メッセージ名 | 送信側から | 受信側から | | ----------- | ---------------- | ---------- | | KeepAlive | 通信可能かチェック | 得になし | | Choke | アップロード不許可 | ダウンロード不許可 | | Unchoke | アップロード許可 | ダウンロード許可 | | Interest | ダウンロード許可要求 | アップロード許可要求 | | NotInterest | ダウンード許可不要 | アップロード許可不要 | | Request | ダウンロード要求 | アップロード要求 | | Cancel | ダウンロード要求破棄 | アップロード要求破棄 | | Piece | データアップロード | データダウンロード | | Bitfield | 所持しているBlockを知らせる | | | Have | 所持しているBlockを知らせる | | これらのメッセージをやりとりして、データの配信とダウンロードを行います。 ネットワーク全体に効率良くデーターが配信されると同時に、すばやく、データをダウンロードできる環境が望ましいです。 ダウンロードする側としては、Unchokeメッセージを送信してもらいたい。配信する側としては、限られた数のPeer以外はUnchokeメッセージを送信したくない。といった感じでしょうか。 ## Choke を利用してアップロード数を制限 Choke機能を利用してアップロードを制限しましょう。アップロードする側の戦略としては、なるたけ、回線速度の良いPeerへたくさんデータを配信することです。 太い回線のPeerが配信に参加した方が、効率良くデータ配布できますから、合理的な判断です。 #### 回線の太いPeerへ優先して配信する。 もっとも太い回線をもっているPeerと通信し続けるのが良いでしょう。 しかし、もっとも太い回線を持っているPeerを知らないわけですから、 良い選択をしているか判断できません。 そこで、回線の太いPeerへのアップロードをしつつ、回線の太いPeerを探す事を行います。 例えば、 1. 5個のUnchoke中のPeerの中で、もっとも回線が細いPeerには、Chokeメッセージを送信する 2. Choke中のPeerからランダムにひとつのPeerを選択して、Unchokeメッセージを送信する。 3. これを、30秒ごとに繰り返す。 回線の速度は、30秒間の間に実際にアップロードしたバイト数とかで判断します。 この方法をとる事で、他にも良い効果があります。 * A. 回線の細いPeerへもデータを配布できる。 * B. 同時にアップロードする量を調整できる。この例だと5個 * C. 回線の太いPeerへの配信よりも、アップロードして欲しいデータが減ると、ダウンロード速度が落ちたと判断される。 特にCの特徴が重要です。後述する方法と組み合わせる事で、自ら積極的に配信に協力しないと、素早くデータをダウンロードできないといった特徴を持たせる事ができます。 以上で終了ですが、最適な選択を選ぶ方法としては、「A/Bテスト」、「バンディットアルゴリズム」とかでググってみてください。 ## 配信に協力しないPeerをChokeする データをダウンロードはするけど、配信しないPeerに対して、対策が必要です。しかし、あるPeerが協力的なのか、非協力的なのかを判断する方法はおおくありません。 例えば、ダウンロードして欲しいデータを持っているPeerがあったとします。そのPeerへたくさんアップロードしているのに、Chokeされたままという場合を考えてみましょう。この、Peerは協力的でない可能性があります。なので、このようなPeerはChokeしてアップロードを停止します。 ## 確率的に、2〜3のPeerからUnchokeされる Chokeをする事によって、具体的にどうのような事が起きているのかを確率的に見てみましょう。 #### (peer数が3の場合) 3つのPeerのネットワークで、各々のPeerは、2つがUnchokeする場合について見てみましよう。 あるPeerがChoke,Uncokeを受けるパターンは以上のとおり、8パターンあります。 これに、Chokeされる確率は1/3であることを考慮すると。 | Unchokeの数 | パターン | 確率 | | --------- | ------------ | -------------------------- | | 無し | ooo | 2/3 x 2/3 x 2/3 x 1 == 30% | | ひとつ | xoo,oxo,oox | 1/3 x 2/3 x 2/3 x 3 == 45% | | ふたつ | oxx,xox,xxo, | 1/3 x 1/3 x 2/3 x 3 == 22% | | 全部 | xxx | 1/3 x 1/3 x 1/3 x 1 == 3% | #### (peer数が4の場合) | Chokeの数 | パターン | 確率 | | ------- | -------------------------------- | ---------------------------------- | | 無し | oooo | 2/4 x 2/4 x 2/4 x 2/4 x 1 == 6.25% | | ひとつ | xooo,oxoo,ooxo, ooox | 2/4 x 2/4 x 2/4 x 2/4 x 4 == 25% | | ふたつ | xxoo,xoxo,xoox, oxxo, oxox, ooxx | 2/4 x 2/4 x 2/4 x 2/4 x 6 == 37.5% | | みっつ | oxxxx,xoxx,xxox, xxxo | 2/4 x 2/4 x 2/4 x 2/4 x 4 == 25% | | 全部 | xxxx | 2/4 x 2/4 x 2/4 x 2/4 x 1 == 6.25% | #### (peer数が1000の場合) 1000個のPeerについても検証してみましょう。1000個あると書き出すのがきつくなります。 数式に落として考えて見ましょう。 | unchokeの数 | | | --------- | ----- | | 0 | 13.5% | | 1 | 27.0% | | 2 | 27.0% | | 3 | 18.0% | | 4 | 9.0% | | 5 | 3.6% | | 6 | 1.1% | #### 図に直すと以下のような感じになります。 ![](/files/-LALznvfy6Ekd1aAXLe5) ## 回線速度、Peer数に応じて、Peerへダウンロード要求する 実際には、Seeder化したPeerへはunchokeする必要はないので、not seeder / seeder くらいの数のPeerからUnchokeされる事になります。 場合によっては、20-30のPeerからUnchokeされることになります。どのSeederを選ぶのがより良い選択なのかするこてで、効率的にダウンロードすることができるようになります。 ### 帯域をコントロールする。 ダウンロードする # Chokeの実装 * アルゴリズムとして定義することで検証可能にする * PeerInfoクラスを定義する * UnchokeしたPeerからChokeするPeerを選択する * ChokeしたPeerから、UnchokeするPeerを選択する Chokeを実装してみましょう。Torrentクライアントの通信部分やアプリケーションの部分と、アルゴリズムの部分は分離する事が望ましいです。 このアルゴリズムじたいをテスト可能にするためです。アプリケーション層とまぜると、アプリケーションの操作としてテストしなくては検証できません。 通信部分の一部としてしまっては、通信機能としてテストする事になります。通信部分を利用しなくてはテスト出来ない状態になります。 アルゴリズムとして定義する事で、検証が容易になります。 ## PeerInfoクラスを定義する Chokeアルゴリズムに必要な要素を考えて、PeerInfoというクラスを定義しました。 PeerInfoには、Peerのステータスの一覧が定義しました。 ``` abstract class TorrentClientPeerInfo { static const int STATE_NONE = 0; static const int STATE_ON = 1; static const int STATE_OFF = 2; String ip = ""; int port = 0; List get peerId; int get downloadedBytesFromMe; int get uploadedBytesToMe; int get chokedFromMe; int get chokedToMe; int get interestedToMe; int get interestedFromMe; bool get amI; bool get isClose; int get uploadSpeedFromUnchokeFromMe; } ``` ``` class TorrentClientPeerInfos { List _peerInfos = []; List get rawpeerInfos => _peerInfos; int get numOfPeerInfo => _peerInfos.length; TorrentClientPeerInfos() {} List getPeerInfos(Function filter) { List t = []; for (TorrentClientPeerInfo x in _peerInfos) { if (filter(x)) { t.add(x); } } return t; } void addPeerInfo(TorrentClientPeerInfo info) { _peerInfos.add(info); } } ``` 前章で定義したメッセージに対応したものですね。 このListからChokeする、UnchokeするPeerの一覧を返すメソッドを作れば、Choke機能を実装したことになります。 ## UnchokeしたPeerからChokeするPeerを選択する ``` List extractChokePeerFromUnchoke(TorrentClientPeerInfos infos, int maxOfReplace, int maxOfUnchoke) { List unchokedPeers = infos.getPeerInfos((TorrentClientPeerInfo info) { return (info.isClose == false && info.chokedFromMe == TorrentClientPeerInfo.STATE_OFF && info.amI == false); }); List alivePeer = infos.getPeerInfos((TorrentClientPeerInfo info) { return (info.isClose == false && info.amI == false); }); List ret = []; if (alivePeer.length > maxOfUnchoke) { unchokedPeers.sort((TorrentClientPeerInfo x, TorrentClientPeerInfo y) { return x.uploadSpeedFromUnchokeFromMe - y.uploadSpeedFromUnchokeFromMe; }); int numOfReplace = alivePeer.length - maxOfUnchoke; numOfReplace = ((maxOfReplace < numOfReplace) ? maxOfReplace : numOfReplace); for (int i = 0; i < numOfReplace && i < unchokedPeers.length; i++) { ret.add(unchokedPeers[i]); } } return ret; } ``` ## ChokeしたPeerから、UnchokeするPeerを選択する ``` List extractUnchokePeerFromChoke(TorrentClientPeerInfos infos, int numOfUnchoke) { List unchokeInterestedPeers = infos.getPeerInfos((TorrentClientPeerInfo info) { return (info.isClose == false && info.interestedToMe == TorrentClientPeerInfo.STATE_ON && info.chokedFromMe == TorrentClientPeerInfo.STATE_ON && info.amI == false); }); List unchokeNotInterestedPeers = infos.getPeerInfos((TorrentClientPeerInfo info) { return (info.isClose == false && info.interestedToMe != TorrentClientPeerInfo.STATE_ON && info.chokedFromMe == TorrentClientPeerInfo.STATE_ON && info.amI == false); }); unchokeInterestedPeers.shuffle(); List ret = []; for (int i = 0; i < unchokeInterestedPeers.length && ret.length < numOfUnchoke; i++) { ret.add(unchokeInterestedPeers[i]); } for (int i = 0; i < unchokeNotInterestedPeers.length && ret.length < numOfUnchoke; i++) { ret.add(unchokeNotInterestedPeers[i]); } return ret; } ``` ## Choke、UnchokeするPeerを選択する 今までに作成したメソッドを合わせことで実現できます。 ``` TorrentAIChokeTestResult extractChokeAndUnchoke(TorrentClientPeerInfos infos, int maxUnchoke, int maxReplace) { List unchokeFromMePeers = infos.getPeerInfos((TorrentClientPeerInfo info) { return (info.isClose == false && info.chokedFromMe == TorrentClientPeerInfo.STATE_OFF && info.amI == false); }); List aliveAndNotChokePeer = infos.getPeerInfos((TorrentClientPeerInfo info) { return (info.isClose == false && info.amI == false && info.chokedFromMe != TorrentClientPeerInfo.STATE_OFF); }); List chokePeers = extractChokePeerFromUnchoke(infos, maxReplace, maxUnchoke); for (TorrentClientPeerInfo info in chokePeers) { aliveAndNotChokePeer.remove(info); } int n = unchokeFromMePeers.length - chokePeers.length; List unchokePeers = extractUnchokePeerFromChoke(infos, maxUnchoke - n); for (TorrentClientPeerInfo info in unchokePeers) { aliveAndNotChokePeer.remove(info); } TorrentAIChokeTestResult ret = new TorrentAIChokeTestResult(); ret.choke.addAll(chokePeers); ret.choke.addAll(aliveAndNotChokePeer); ret.unchoke.addAll(unchokePeers); return ret; } ``` # DHTに対応してみる ![](/files/-LALznChlLY5ukadDMYt) # About 前章までで紹介した方法では、ダウンロードゲームに参加するためのPeer探しは、サーバー・クライアント方式でした。 せっかく、P2Pアプリなのに、P2Pで完結していないのは少し残念ですね。本章では、TrackerなしでP2Pで完結する方法について紹介します。 本章を通して、実際にKademlia(DHT)を利用したP2Pネットワークを組めるようになります。 サーバーを用意しなくても、様々なネットワークサービスを作るためのノウハウを獲得したという事になります。対規模なネットワークサービスを構築するため、負荷分散についいての考え方の一つを得る事にもなります。 ## キーワード * Kademlia * DHT * スモールワールド Kyorohiro work # Tracker無しでPeerを探す * **Trackerがなくてもデータを探せる** * **六次の隔たりで実現している** * **距離を定義してネットワークを構築する** 本章では、Mainline DHT と呼ばれる機能の解説と実装をしていきます。 ## Trackerなしで、ネットワーク構築できる 当初のスペック(bep003)では、Torrentクライアントは、P2Pネットワークを構築する際に、Trackerサーバーへアクセスして、データを共有するPeerを教えてもらう必要がありました。このTrackerの役割を、P2Pネットワーク上で実現したものが、Mainline DHTです。 今までは、基本的には、データを共有するには、Trackerサーバーを、WWW上に公開する必要がありました。しかし、DHTを採用することで、WWW上にTrackerサーバーを公開しなくてもデータを共有できるようになりました。 ## 六次の隔たりを利用する では、どのようにして、Trackerの変わりとなるP2Pネックワークを構築するのでしょうか。 具体的には、Trackerが行っていた。「InfoHash(20バイトのユニークな値)を、問い合わせると。データを共有してくれるTorrentクライアントを紹介してくれる」 という機能をP2Pで実現する必要があります。 ### - より詳しい人を紹介してもらう事を繰り返す 「六次の隔たり」というこ言葉をご存知でしょうか?知り合いを6人くらいたどると、世界中のすべての人と繋がっているそうです。イェール大学のスタンレー・ミルグラム教授による、「スモール・ワールド現象」が有名です。 **同封した写真の人物はボストン在住の株式仲買人です。この顔と名前の人物をご存知でしたらその人の元へこの手紙をお送り下さい。この人を知らない場合は貴方の住所氏名を書き加えた上で、貴方の友人の中で知っていそうな人にこの手紙を送って下さい」という文面の手紙をそれぞれに送った。その結果42通 (26.25%) が実際に届き、42通が届くまでに経た人数の平均は5.83人であった。(****)** 大好きな作家さんや、尊敬するプログラマーも、関節的な知り合いというわけですね。このように、賢く質問して回れば、特定の人にメッセージを届ける事ができます。 ### - P2Pでも同じ方法で実現している 対象としているP2Pネッワークも「六次の隔たり」によって実現しています。「スモール・ワールド現象」の実験と同じように、P2Pネットワークへ依頼を投げます。 * 知り合いのTorrentクライアントに、「InfoHashに関連するデータを所持しているTorrentクライアントがいないが聞く」 * もしも、所持していなければ、「所持していそうなTorrentクライアントを教えてもらう。」 スモールワールドの実験の依頼内容の手紙と見ていますね!! このような単純な機能だけでTrackerの役割をP2Pで実現できます。 ## 距離を定義する もう少し具体的に、「知っていそうな人を紹介する」を、P2Pネットワーク上で実現する方法を考えてみましょう。 P2Pネットワークに、InfoHashという20バイトのデータが渡されます。これを受け取ったは端末は、所持する数十のPeerからもっとも、InfoHashに対応するデータを持っていそうなPeerを紹介する必要があります。 DHTでは距離を定義して、紹介するPeerを決定します具体的には、「InfoHashにより近いPeerを紹介する」という事をします。 この距離はなんでも良いです。例えば、皆さんが学校で習ったユークリット距離でも良いでしょう。 ユークリット距離は、我々が日常世界で利用している距離のことです。例えば、東京駅から大阪駅までの走行距離は、508.0km。直線だと401kmくらい。神戸と名古屋は、東京よりも大阪り方が近い。仙台や神奈川は大阪よりも東京のほうが近いといった感じに定義できます。 各PeerにInfoHashと同様のIDを振り。InfoHashとPeerの距離を計算できるようにするのです。 ## ネットワークに偏りを作る もうひとつ、「六次の隔たり」を実現するには、現実世界のおなじように、距離の近いものほど詳しく、距離の遠いものほど詳しくないといった状況をつくる必要があります。 自分の会社の同僚や同級生については、よく知っているでしょう。同級生よりも、同じ部活の友人などについては、より詳しく知っている事でしょう。しかし、別の会社の事や、別の学校の事は、詳しくないと思います。 P2Pネットワーク上に同様の構造を実現しないと、「InfoHashに近いPeerを紹介したけど、その紹介した人は、InfoHashに近いPeerの事を知らない」と問題が発生します。 この問題を解決するために、自分に近いPeerについてはたくさんの情報をもち、自分に遠いPeerについては少しだけ情報を持つようにしてあげます。これを、ネットワーク全体で繰り返す事で、現実世界と同じように、距離が近いPeerどうしはお互いを良く知っている状態が構築されるようになります。 Kyorohiro work # 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 | | 0 | 0 | 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についてはより詳しいのでした。Kademliaでは、kBucketのRootingTableでPeerの一覧を管理しています。 kBucketは、K個のPeerの情報をグローピングする入れ物です。それだけです。K個以上保持する事ができないので、それ以上のPeerを追加するには、kBucketから不要なPeerを削除する必要があります。 Kademlia の 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に選別されます。 ![](/files/-LALzjlDz4mHY8YgFBk6) 次は図で見てみましょう。どうでしょうか。各Peerごとに、kBucketに格納される位置は直感的な配置になっているのではないでしょうか? 枝が移動するごとにの、格納するindexが大きくなっているのが解るでしょう。 このように、xor距離は、図形的に見ると直感的で合理的な構造になっているのです。 Kyorohiro work # 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のデータを持つ事とする。 ```dart class KId { List _values = null; List get value => new List.from(_values); KId(List 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 get iterator => _values.iterator; } ``` #### XOR の計算機能を追加する KIdはXOR距離が計算できる必要があります。数値としては表現する事は諦めましたが、計算した結果はKIDとして返す機能は必要です。バイト配列の各値ごとに xorをとる事で実現できます。 ```dart 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一覧を返す機能そのものです。 ```dart 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の作成は完了です。事の顛末を知りたい方は、以下を参照してください。 実装作業は、必ずテストを書きながら、動作確認しながら、進めてください。 ## kBucketを実装する。 kBucketは、K個のPeetについての情報を格納する入れ物です。これは、値を追加する時に制限をもたせたListとして表現できますね。 今回の実装ではkBucketが満杯になった場合は古いデータから削除するようにしています。 このあたりは、実際に動作させてみて最適な方法を試行錯誤すべきでしょう。 ```dart class KBucket { int _k = 8; int get k => _k; List 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 get iterator => peerInfos.iterator; } ``` 以上でkBucketの作成は完了です。事の顛末を知りたい方は、以下を参照してください。 ## RootingTableを実装する 前章で説明したとおり、RootingTableは、0〜160までの161個のkBucketを保持する事ができるのでした。 まずは、最初の定義、kBucketを161個保持することができる。 ```dart class KRootingTable { List _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 | 0 | | 1 | 001 | 1 | | 2, 3 | 010, 011 | 2 | | 4, 5, 6, 7 | 100, 101, 110, 111 | 3 | 実際に表に落としてみると、左から右へ1bitずつ確認していって、最初に1であった場所によって、kBucket位置が決まる事がわかります。 これをコードに落としましょう。 ```dart class KRootingTable { List _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メソッドが追加されます。しかし、今までに解説した内容で実装できるのはここまでとなります。 Kyorohiro work # FindNodeでネットワークの構築 * **FindNodeクエリでネットワークを構築する** * **リスポンスを受けたらRootingTableを更新する** 前章で、kBucketとRootingTableについては説明しました。このRootinhTableを更新しながら、実際にDHTのネットワークを組んでみましょう。 ## FindNodeクエリでネットワークを構築する Mainline DHT こと、KademliaではUDPを利用してPeerどうしが通信を行います。 DHRのネットワークを構築は、FindNodeクエリとFindNodeレスポンスのみで実現しています。 本章では、FindNodeクエリについて解説していきます。 ### 指定したKIDに近い距離にあるPeerを紹介してもらう事ができる FindNodeクエリを利用すると事で、指定したKIDともっとも距離が近いNodeを教えてもらう事ができます。 以下のようなBencodeで表現できます。 ``` arguments: { "t":"aa", "y":"q", "q":"find_node", "a":{ "id" : "", "target" : "" } } response: { "t":"aa", "y":"r", "r":{ "id" : "", "nodes" : "" } } ``` "t" は送信側が任意に決める事ができる値です。レスポンスには、送信時に指定した値が渡されます。この値を元にどのクエリのレスポンスかを判断する事がてきます。 "id"には、クエリを送信するPeerのKIDがして入ります。 "target"に指定したKIDと距離が近いPeerが帰りまする "nodes" は、26byteのbyteデータの集まりで、20byteのPeer IDとIPとPort番号が格納されています。 ### ネッワークへの参加/構築 ネットワークの構築はFindNodeクエリを利用します。我々は、自分に近いKIDを持つPeerについて詳しくなる必要があるのでした。 "id" に自分自信のPeer ID を指定して、 Node の一覧を取得します。 Rooting Table の中の上位 K個について、 FindNode を行います。この上位K個が固定されまで、 FindNod eを繰り返します。 なんども、この操作を繰り返しているうちに、DHT上でもっとも自分自信に近いPeerを発見できまます。 実際に1000個のPeerを生成して、試してみると以下の分布を得ることができました。 Kは8としました。 | Rooting Table index | Peerの数 | コメント | | ------------------- | ------ | ------ | | 0 | 1 | 自分自信です | | 147 | 1 | .. | | 154 | 1 | .. | | 155 | 4 | .. | | 156 | 4 | .. | | 157 | 6 | .. | | 158 | 8 | .. | | 159 | 8 | .. | | 160 | 8 | .. | TorrentのDHTネットワークに接続した場合も同じような結果になります。自分自信に近いNodeは、Rooting Tabe index の、l130-150くらいのところに集まります。 ![](/files/-LALzt6lb0DcafhGUQYy) 実際にグラフに直してみると、150の付近で相当近くにあPeerである事がわかります。 ref Kyorohiro work # FindNodeを実装 * **MainLine DHT は、UDPで通信** 通信ライブラリとして、hetimanetを使用しています。APIのインターフェイスは他の通信ライブラリと大きな違いはありません。なので、お使いのものと読み替えて読み進めてください。 ## RootingTableに、FindeNodeの機能を追加する 所持しているPeerInfoを指定されたKIDでソートして探す。 ``` class KRootingTable { ... ... ... List findNode(KId id) { List ids = []; for (KBucket b in _kBuckets) { for (KPeerInfo i in b.iterable) { ids.add(i); } } ids.sort((KPeerInfo a, KPeerInfo b) { return a.id.xor(id).compareTo(b.id.xor(id)); }); List ret = []; for (KPeerInfo p in ids) { ret.add(p); if (ret.length >= _kBucketSize) { return ret; } } return ret; } ... ... } ``` ## (1) KNodeはUDPサーバー機能を持つ。 まずは、UDPを用いて、通信部分を書いてみましょう。Torrentの仕様では、DHTとして動作するPeerをNodeと読んでいます。 DHTの通信を行う主体として、KNode class を定義することにします。 UDP serverは、メッセージを受け取るメッセージはbencodeなのでした。パースしてそのMessageを使うclassに渡します。 ```dart class KNode { bool _isStart = false; bool get isStart => _isStart; HetiSocketBuilder _socketBuilder = null; HetiUdpSocket _udpSocket = null; KNode(HetiSocketBuilder socketBuilder) { this._socketBuilder = socketBuilder; } Future start({String ip: "0.0.0.0", int port: 28080}) async { (_isStart != false ? throw "already started" : 0); _udpSocket = this._socketBuilder.createUdpClient(); return _udpSocket.bind(ip, port, multicast: true).then((int v) { _udpSocket.onReceive().listen((HetiReceiveUdpInfo info) { KrpcMessage.decode(info.data, this).then((KrpcMessage message) { onReceiveMessage(info, message); }); }); _isStart = true; }); } Future stop() async { if (_isStart == false || _udpSocket == null) { return null; } return _udpSocket.close().whenComplete(() { _isStart = false; _ai.stop(this); }); } } ``` ## (2) Krpc Messageをパースする機能を持つ MainLine DHT では、PeerとPeerの通信には、Bencodeが利用されます。 すでにBencodeのパーサーは作成ずみなので、難しいことはないはずです。 ``` class KrpcMessage { KrpcMessage.fromMap(Map map) { _messageAsMap = map; } static Future decode(List data) async { Map messageAsMap = null; try { Object v = Bencode.decode(data); messageAsMap = v; } catch (e) { throw {}; } return new KrpcMessage.fromMap(messageAsMap); } } ``` こんな感じです。あとは、必要に応じて、パースした結果を読み取るだけです。 ``` class KrpcMessage { ... ... List get transactionId => _messageAsMap["t"]); String get transactionIdAsString => UTF8.decode(transactionId); // List get messageType => _messageAsMap["y"]; String get messageTypeAsString => UTF8.decode(messageType); // List get query => _messageAsMap["q"]; ... ... } ``` こんな感じです。BEP5のスペックをみると結構ありますがも気長にコーディングしていけば、半日くらいで終わると思います。 ## (3) メッセージを送信する機能を持つ ``` class KNode { .. .. sendMessage(KrpcMessage message, String ip, int port) { return _udpSocket.send(message.messageAsBencode, ip, port); } .. } class FindNode { static int queryID = 0; static KrpcMessage createQuery(List queryingNodesId, List targetNodeId) { List transactionId = UTF8.encode("fi${queryID++}"); return new KrpcMessage.fromMap({"a": {"id": queryingNodesId, "target": targetNodeId}, "q": "find_node", "t": transactionId, "y": "q"}); } static KrpcMessage createResponse(List compactNodeInfo, List queryingNodesId, List transactionId) { return new KrpcMessage.fromMap({"r": {"id": queryingNodesId, "nodes": compactNodeInfo}, "t": transactionId, "y": "r"}); } } ``` メッセージの送信は、受信用に作成したUDPSocketを利用します。こうすることで、受信相手に、ポート番号を伝えることができます。 ## (4) ネットワークへの参加用のコードを書く RootingTableに所持しているデータの中から、自分自信ともっとも近いKIDをもつPeerへFindNodeクエリを送信する ``` class KNodeWorkFindNode { ... ... updateP2PNetworkWithoutClear(KNode node) { node.rootingtable.findNode(node.nodeId).then((List infos) { for (KPeerInfo info in infos) { if (!_findNodesInfo.rawsequential.contains(info)) { _findNodesInfo.addLast(info); node.sendFindNodeQuery(info.ipAsString, info.port, node.nodeId.value).catchError((_) {}); } } }); } ... ... } ``` レスポンスを受けとったら、もう一度繰り返す ``` class KNodeWorkFindNode { ... ... onReceiveQuery(KNode node, HetiReceiveUdpInfo info, KrpcMessage query) { if (query.queryAsString == KrpcMessage.QUERY_FIND_NODE) { KrpcFindNode findNode = query.toFindNode(); return node.rootingtable.findNode(findNode.targetAsKId).then((List infos) { return node.sendFindNodeResponse(info.remoteAddress, info.remotePort, query.transactionId, KPeerInfo.toCompactNodeInfos(infos)).catchError((_) {}); }); } node.rootingtable.update(new KPeerInfo(info.remoteAddress, info.remotePort, query.nodeIdAsKId)); updateP2PNetworkWithoutClear(node); } ... .. } ``` 一定時間だったら、もう一度アクセスする ``` class KNodeWorkFindNode { ... ... onTicket(KNode node) { _findNodesInfo.clear(); updateP2PNetworkWithoutClear(node); } ``` ## (5) FindeNodeクエリに対応したレスポンスを返せるようにしよう ``` class KNodeWorkFindNode { ... ... onReceiveResponse(KNode node, HetiReceiveUdpInfo info, KrpcMessage response) { if (response.queryFromTransactionId == KrpcMessage.QUERY_FIND_NODE) { KrpcFindNode findNode = response.toFindNode(); for (KPeerInfo info in findNode.compactNodeInfoAsKPeerInfo) { node.rootingtable.update(info); } } node.rootingtable.update(new KPeerInfo(info.remoteAddress, info.remotePort, response.nodeIdAsKId)); updateP2PNetworkWithoutClear(node); } .. } ``` # GetPeersでInfoHashに対応するPeerを探す * **GetPeersでPeerを探す** * **AnnouncePeerでP2Pネットワーク上に値を保存する** 前章でP2Pネットワークを作成する事ができました。本章では、作成したP2Pネットワークにデータを記録する方法について解説していきます。 ## GetPeerでネットワークとFindNodeはほとんど同じ。 MainLine DHT ではGetPeersメッセージを利用して、データを所持しているPeerを探します。 GetPeerコマンドは「指定してKIDに対応するデータを所持しているPeerを知っていれば、そのPeerについて教えてもらう」、もしも知っていなければ、もっとも近いPeerを教えてもらう。といった事をします。 この操作を何度も繰り返す事で、KIDともっとも近くにあるNodeを発見する事ができます。 これは、ほとんど、FinddNodesと同じような動作ですね。 * KIDの近いPeerを紹介してもらうのが同じ * なんども、送信と受信を繰り返すのが同じ 実装もほとんど同じになります。 ## AnnouncePeerでデータを記録する GetPeerを繰り返して、上位K個のNodeが固定されたら、AnnounePeerメッセージを利用してデータを記録してもらいます。 K個のNodeへデータの記録を依頼します。複数のPeerへ依頼することによって、堅牢性が高まります。 * 発見されやすくなる * 登録したPeerが離脱しても大丈夫 * 登録したPeerの負荷を分散することができる。 ## メッセージの構成 ``` arguments: { "t":"aa", "y":"q", "q":"get_peers", "a": { "id" : "", "info_hash" : "<20-byte infohash of target torrent>" } } response: have value { "id" : "", "token" :"", "values" : ["", ""] } response: have node info { "t":"aa", "y":"r", "r": { "id" : "", "token" :"", "nodes" : "" } } ``` FindNodeとほとんど同じですね。本書では"token"と"values"が初めて出てきました。 "token" は、レスポンスを返す側に自由に決めることができるバイトデータです。AnnouncePeerクエリを送信する時に使います。このバイトデータのサイズもレスポンスを返す側のクライアントによって、異なります。 "value" は、6バイトのデータ\[ ,]をList形式で、複数個格納しています。 ref ## 実装について findNodeで解説したとおりです。findNodeを実装したノウハウでそのままgetPeersも実装できると思います。 なので、特別、解説するページをさかないようにしました。 Kyorohiro work # テスト * *DHTを動作させてみよう!!\** DHTの解説は完了です。実際に動作させてみましょう。実際にTorrentのネットワークに繋がるアプりケーションを作ろうとすると、2〜3人日、またはそれ以上かかると思います。 作ってもらうのも良いのですが、 本章では hetimatorrentを利用したサンプルアプリを紹介します。 ## 指定したKIDをネットワークから探すサンプル ``` main() { KNode node = new KNode(new HetiSocketBuilderChrome(), verbose: true); // node.start(ip: "0.0.0.0", port: 28080).then((_) { node.onGetPeerValue.listen((KGetPeerValue v) { print("---onGetPeerValue ${v.ipAsString} ${v.port} ${v.infoHashAsString} "); }); }); // initial node String initailNodeIp = "0.0.0.0"; int initailNodePort = 38080; node.addBootNode(initailNodeIp, initailNodePort); // search target List infoHash = new List.filled(20, 4); node.startSearchValue(new KId(infoHash), 18080, getPeerOnly: true); new Future.delayed(new Duration(minutes:30)).then((_){ print(node.rootingtable.toInfo()); return node.stop(); }); } ``` UI付きのサンプルアプリは以下を参照してください。 # \[Dartの基礎] # \[なぜDart] # Hello World ## Hello World コンソールに "HelloWorld!!" と文字列を表示するプログラムを書いてみましょぅ。 ### 1. DartPadを開く ### 2. プログラムを書く ``` void main() { print('Hello World (1) !!'); print("Hello World (2) !!"); print(""" Hello World (3) !!"""); } ``` ### 3. RUNボタンを押す。 ``` HTML OUTPUT CONSOLE Hello World (1) !! Hello World (2) !! Hello World (3) !! ``` と文字列が表示されます。 ## 四則演算 ### 1. DartPadを開く ### 2. プログラムを書く ``` void main() { print(""" 1+1 = ${1+1} 1-1 = ${1-1} 2*2 = ${2*2} 4/2 = ${4/2} 5/3 = ${5/3} 5~/3 = ${5~/3} 5%3 = ${5%3} 5/0 = ${5/0} 1+2*(1+2) = ${1+2*(1+2)} 1==1 = ${1==1} 1==0 = ${1==0} 1!=1 = ${1!=1} 1!=0 = ${1!=0} 1<0 = ${1<0} 0<0 = ${0<0} -1<0 = ${-1<0} 1>0 = ${1>0} 0>0 = ${0>0} -1>0 = ${-1>0} 1<=0 = ${1<=0} 0<=0 = ${0<=0} -1<=0 = ${-1<=0} 1>=0 = ${1>=0} 0>=0 = ${0>=0} -1>=0 = ${-1>=0} """); } ``` ### 3. RUNボタンを押す。 ``` 1+1 = 2 1-1 = 0 2*2 = 4 4/2 = 2 5/3 = 1.6666666666666667 5~/3 = 1 5%3 = 2 5/0 = Infinity 1+2*(1+2) = 7 1==1 = true 1==0 = false 1!=1 = false 1!=0 = true 1<0 = false 0<0 = false -1<0 = true 1>0 = true 0>0 = false -1>0 = false 1<=0 = false 0<=0 = true -1<=0 = true 1>=0 = true 0>=0 = true -1>=0 = false ``` と文字列が表示されます。 ## 変数 ### 1. DartPadを開く ### 2. プログラムを書く ``` void main() { int a = 1; double b = 1.1; int c = (a+b).toInt(); double d = a+b; var e = a+b; String f = "test"; String g = "game"; print("${c} ${d} ${e} ${f+g}"); // ++ print("[++]"); print("${++a} ${a++}"); print("${a}"); // -- print("[--]"); print("${--a} ${a--}"); print("${a}"); a = 1; a += 10; print("a+= ${a}"); a = 1; a -= 10; print("a-= ${a}"); a = 2; a *= 3; print("a*= ${a}"); a = 6; a ~/= 3; print("a~/= ${a}"); a = 5; a %= 3; print("5%= ${a}"); } } ``` ### 3. RUNボタンを押す。 ``` 2 2.1 2.1 testgame [++] 2 2 3 [--] 2 2 1 a+= 11 a-= -9 a*= 6 a~/= 2 5%= 2 ``` と文字列が表示されます。 ## スコープ ### 1. DartPadを開く ### 2. プログラムを書く ``` int a = 100; int b = 200; void main() { print("[A] ${a} ${b}"); int a = 1; print("[B] ${a} ${b}"); { int b = 2; print("[C] ${a} ${b}"); } print("[D] ${a} ${b}"); { a = 1000; b = 2000; } print("[E] ${a} ${b}"); } ``` ### 3. RUNボタンを押す。 ``` [A] 100 200 [B] 1 200 [C] 1 2 [D] 1 200 [E] 1000 2000 ``` と文字列が表示されます。 ## If 文 ### 1. DartPadを開く ### 2. プログラムを書く ``` void main() { if(true) { print("[A] true"); } if(1!=1) { print("[B] true"); } else { print("[B] false"); } int a = 2; if(a==1) { print("[C] 1"); } else if(a ==2){ print("[C] 2"); } else { print("[C] other"); } } ``` ### 3. RUNボタンを押す。 ``` [A] true [B] false [C] 2 ``` と文字列が表示されます。 ## Switch 文 ### 1. DartPadを開く ### 2. プログラムを書く ``` void main() { int a = 0; switch(a) { case 0: print("a=0"); break; case 1: print("a=1"); break; default: print("other"); } String b = "test"; switch(b) { case "tests": print("b=test"); break; case "test": print("b=test"); break; default: print("other"); } int c = 0; switch(c) { case 0: case 1: print("c=0 or c=1"); break; default: print("other"); } } ``` ### 3. RUNボタンを押す。 ``` a=0 b=test c=0 or c=1 ``` と文字列が表示されます。 ## While 文 ### 1. DartPadを開く ### 2. プログラムを書く ``` void main() { int i = 0; while(i<10) { print("${i}"); i++; } } ``` ### 3. RUNボタンを押す。 ``` 0 1 2 3 4 5 6 7 8 9 ``` と文字列が表示されます。 ## Do-While 文 ### 1. DartPadを開く ### 2. プログラムを書く ``` void main() { int i = 0; do { print("${i}"); i++; } while(i<10); } ``` ### 3. RUNボタンを押す。 ``` 0 1 2 3 4 5 6 7 8 9 ``` と文字列が表示されます。 ## For 文 ### 1. DartPadを開く ### 2. プログラムを書く ``` void main() { for (int i=0;i<10;i++) { print("${i}"); } } ``` ### 3. RUNボタンを押す。 ``` 0 1 2 3 4 5 6 7 8 9 ``` と文字列が表示されます。 ## Function ### 1. DartPadを開く ### 2. プログラムを書く ``` int plus(int a, int b) { return a + b; } void main() { print("${plus(100,10)}"); } ``` ### 3. RUNボタンを押す。 ``` 110 ``` と文字列が表示されます。 ## Class ### 1. DartPadを開く ### 2. プログラムを書く ``` class A { int a = 0; int b = 0; printStatus() { print("${a} ${b}"); } } void main() { A a = new A(); a.printStatus(); a.a = 100; a.b = 200; a.printStatus(); A b = a; b.printStatus(); a.a = 3; a.printStatus(); b.printStatus(); } ``` ### 3. RUNボタンを押す。 ``` 0 0 100 200 100 200 3 200 3 200 ``` と文字列が表示されます。 # Test/Debug 本書ではテストファーストで開発を進める事を推奨しています。 テストで固めて、コードをリファクタリングできるように維持していきましょう。 本章では、「Observatory」の使い方についての日本語訳を掲載します。 ## Observatory: A Profiler for Dart App 引用() Observatoryは profiling と debugging 用のツールです。 ``` ObservatoryはFreeでGETできます。 https://www.dartlang.org/downloads/ から取得できます。 issueやrequestは、 http://dartbug.com/new で受け付けています。 ``` Observatoryは動作中のDart VM の中身を覗くことができます。そして、即座にレポートしてくれます。 * どの部分に時間を費やしていたか * allocatedした メモリーを調べます。 * コードのどの部分が実行されたわかります * メモリーリークをデバックできます * メモリーの断片化をデバックできます 次のビデオは、Dart Developer Summit をレコードしたものです。John McCutchan と Todd Turnidge で 使い方について解説しています。 ### Using Observatory * [get started with Observatory](/dartno/observatory/observatory_getstarted) To learn about specific features, read these pages: * [Allocation Profile](https://www.dartlang.org/tools/observatory/allocation-profile.html) * [Code Coverage](https://www.dartlang.org/tools/observatory/code-coverage.html) * [CPU Profile](https://www.dartlang.org/tools/observatory/cpu-profile.html) * [Debugger](https://www.dartlang.org/tools/observatory/debugger.html) * [Evaluating Expressions](https://www.dartlang.org/tools/observatory/evaluate.html) * [Heap Map](https://www.dartlang.org/tools/observatory/heap-map.html) * [Isolate](https://www.dartlang.org/tools/observatory/isolate.html) * [Metrics](https://www.dartlang.org/tools/observatory/metrics.html) * [User and VM Tags](https://www.dartlang.org/tools/observatory/tags.html) The following pages have reference information about Observatory: * [dart: The Standalone VM](https://www.dartlang.org/tools/dart-vm/#observatory) * [Glossary of VM Terms](https://www.dartlang.org/tools/observatory/glossary.html) * [Screens in Observatory](https://www.dartlang.org/tools/observatory/screens.html) #### Support and discussion Join the [Observatory discussion mailing list](https://groups.google.com/a/dartlang.org/forum/#!forum/observatory-discuss) to ask questions and chat with users. #### Filing bugs and feature requests To see existing issues or create a new one directly, see all [Observatory issues](https://github.com/dart-lang/sdk/labels/Area-Observatory). # Get started with Observatory の訳 ### \[Contents] * Get Observatory * Start Observatory * Standalone apps from the command line * Web apps * Observatory UI * VM screen * What next? ``` ObservatoryはFreeでGETできます。 https://www.dartlang.org/downloads/ から取得できます。 issueやrequestは、 http://dartbug.com/new で受け付けています。 ``` ## Get Observatory Observatory は Dart SDK 中の toolsのひとつです。 からダウンロードできます。 Dartでアプリケーションをつくる場合2つの方法があります。 ひとつは、standalone applications として動作させる方法です。もうひとつは、web applications として動作させる方法です。 standalone appsの場合、 command line から Observatory を使う事ができます。 browser-based apps の場合、command line からDartium 上でアプリを起動させる事で、Observatory を利用できます。 つまり、どちらの場合でもObservatoryを利用する事ができます。 ## Start Observatory standaloneか web appかによって、 Observatory 有効にする方法は異なります。 しかし、UIについてだいだい同じです。 #### Standalone apps from the command line Observatoryを有効にするには、dartvm を起動する時にオプションを追加します。 例えば、 ``` dart --observe