スキップしてメイン コンテンツに移動

P2P探訪 Raider その1 Bittorrent File Format



[Raider Purpose]
 P2Pについて学習するために、Raiderというメタファーのgithubリポジトリを作成しました。
 まずは、もっとも有名な Torrentプロトコルを実装してみようと思います。 
 
 私にとっては、BitTorrentの仕様書だけを頼りに実装するのは難しいことです。
 そこで、Raiderでは、以下のアプローチとっています。
  1. bittorrentについて、実現できそうなシナリオを作る。
  2. 調査しながら、コードを書く
  3. 評価して、次のシナリオを決める。

 今は最初に実現しようとしているのは、以下のようなものです。
  # torrentファイルの読み込みと作成をする。
  これなら、簡単に実現できそうですね!!
 

[Torrent file format]
# bencoding
Torrent file は bencoding によって構成されています。 まずは、bencoingを扱えるようにする必要があります。
bencodingは integer, string(byte array), list, diction で構成されています。
bencoding は以下のような簡単なルールでencodeされます。

  beninteger   : "i" [0-9]* "e"
  benstring    : [0-9]* ":"  # bytes array/string length is prev [0-9]*.
  bendiction   : "d" dictelements "e" 
  benlist      : "l" listelements "e"
  benobject    : beninteger | benstring | beniction | benlist
  listelements : benobject (benobject)*
  dictelements : benstring benobject (benstring benobject)*

簡単といえるのは、先頭1文字で、どのデータ構造でできているかが判断できるようになっているからです。
例えば、 integerならば、'i' stringならば、's'といった感じです。
なので、bencodingのdecoderは、以下のようなシナリオで実現できます。
1. 一文字読み込む。
2. どのデータか判別する。
3. データ形式に応じて読み込む。
4. 1に戻る。

# torrent file format
bencodingが扱えるようになれば、torrent fileから必要な情報を取得することができるようになります。
torret file から取得できる情報はどんなものかは、別の機会に解説します。ここでは、torrent fileには 2つのフォーマットがあることとデータ構造を説明します。

torrent fileでは、ダウンロード/アップロードの対象としているファイルが、ひとつの場合と複数の場合で、構造がすこしだけことなります。参考までにデータ構造を紹介します。

- single file pattern
bendiction 
  benstring "announce"
  beninteger "creation date"
  bendiction "info"
    beninteger "length"
    benstring "name"
    beninteger "piece length"
    bebstring "pieces"

- multi file pattern
bendiction 
  benstring "announce"
  beninteger "creation date"
  bendiction "info"
    benlist "files"
      bendiction
        beninteger "length"
        benlist "path"
           benstring
      bendiction
      ..
      ..          
    beninteger "length"
    benstring "name"
    beninteger "piece length"
    bebstring "pieces"

[Raider's parse system]
Bittorrent のbencodingのencode/decode方法はとてもシンプルです。Bittorrentのパースをチックすると良いでしょう。ですが、Radierではね LLライクな方法を採用しました。特に理由はありません。仕様から空で考えたら、別の実装になってしまいました。


- comment about LL parse 
LL については、 [*3] を参照してください。
簡単にコメントします。 LLは文法とJava Method が一対一で対応付けられます。
※ 機械的な作業で実現できます。

例えば、以下のような文法の場合
   benstring    : "i" [0-9]* "e"
   beninteger   : "i" [0-9]* "e"
   benobject    : beninteger | benstring

以下のような感じで一対一の対応で書けます。
 static void benstring(reader) throws xxException {
    try {
       reader.mark();
       if(check(string grammer)) {
       } else {
          reader.backtoMark(); 
          throw xxException;
       }
    } finally {
      reader.releasemark();
    }
 }

 static void beninteger(reader) throws xxException  {
    try {
       reader.mark();
       if(check(integer grammer)) {
       } else {
          reader.backtoMark(); 
          throw xxException;
       }
    } finally {
      reader.releasemark();
    }
 }
 static void benobject(reader) throws xxException {
     try {benstring()}catch(xxException e){}
     try {beninteger()}catch(xxException e){throw e;}
 }

bencoding
https://github.com/kyorohiro/Raider/tree/master/Raider/src/info/kyorohiro/raider/util/bencode

torrent file
https://github.com/kyorohiro/Raider/tree/master/Raider/src/info/kyorohiro/raider/util/torrent

[reference]
- Torrent spec
  http://en.wikipedia.org/wiki/Torrent_file
  http://www.bittorrent.org/beps/bep_0003.html
  http://sourceforge.net/projects/bittorrent/
  
- LL Parser[*3] 
  http://pragprog.com/book/tpdsl/language-implementation-patterns
  

コメント

このブログの人気の投稿

KyoroStressの技術 -1- Low Memory Killer を意図的に発生させたい

[課題] Low Memory Killer を意図的に発生させたい Androidには、ヒープが涸渇すると使われていないアプリをKillする機能があります。 この記事では、意図的にヒープを枯渇させて、この状態をつくる方法について説明します。 単純にヒープを大量に消費するアプリを作成すれば良いように思えます。 しかし、これだけでは上手くいきません。   -A ひとつのアプリで消費できるヒープが制限されているため、ひとつのアプリで端末のヒープが涸渇している状態をつくれない。   -B ヒープを涸渇しているアプリがPFにKILLされる場合がある。 といった問題があります。 KyoroStressV2での解決方法を紹介します。 [KyoroStressでの解決方法] Kyoro Stress では、以下のような方法をとりました。 - 1. 複数のServiceを、各々異なるプロセスで起動する。 - 2. 各々Serviceで大量のヒープを消費する。 複数のプロセスを立ち上げれば、PFのヒープを枯渇させることができます。これで、(A)の問題が解決できました。 また、Bについては、「生きているプロセス」が「KILLされたプロセス」の分もヒープを消費すれば上手くいけそうです。 [BigEater(ヒープ消費サービス)の動作] KyoroStressV2で、ヒープを消費するサービスは以下のシナリオで動作しています。 - 1. 指定されたヒープを取得する。 is retry が true の時、指定されたヒープを取得できるまで、1を何度も繰り返す。 - 2. KILLされたサービスを復活させる。 is retry が true の時、Threadが死ぬまで、何度も2を繰り返す。 - 3. 終了 といった感じです。 このままでは、すべてのServiceがPFにKILLされたら上手くいかないように思うかも知れません。 しかし、時間がたつと(数秒)、PFはKILLしたServiceを再起動します。 このため、ServiceがすべてKILLされても、ヒープを大量に消費しようとする状態は保持されます。 [使い方] KyoroStressV2の操作方法…

P2P探訪 STUNでNAT越え その1

UPnPを用いて、NAT越えできました。しかし、ルータがUPnPをサポートしていなかったり。UPnPだけでは越えられないNATがあります。

本文では、その代案として前回解説できなかった。「適当なサーバーに接続してみて、相手から見えているアドレスを返してもらう方法」について解説していきます。

TCPの限界 インターネットで公開されている情報のほとんどは、TCPという通信方法でデータをやり取りされています。ですから、インターネットで情報を公開したい場合は、TCPサーバーを立ち上げる事を考える事でしょう。
 しかし、ルータがUPnPをサポートしていない場合、TCPを用いたサーバーを運用する事は困難になります。※ 基本、無理と考えもらって問題ありません。


接続相手から教えてもらう方法はどうした? 適当なサーバーに接続してみて、相手から見えているアドレスを返してもらう事で実現できないのでしょうか。前回はできそうな事を臭わせていました。しかし、TCPにおいて、これは困難です。

実際にTCPのプログラムを書き確認して見ましょう。接続相手のホストアドレスは推測できます。しかし、ポート番号を知るすべはありません。


import java.io.IOException; import java.net.Inet4Address; import java.net.ServerSocket; import java.net.Socket; import java.net.UnknownHostException; public class TCPTest { public static void main(String[] args) { TCPTest test = new TCPTest(); test.startServer(); try { Thread.sleep(3000); } catch (InterruptedException e) { e.printStackTrace(); } test.startClient(); } private Server mServer = new Server(); public void startServer() { mServer.start(); } public v…

P2P探訪 Raider その1-2 Torrentファイルフォーマット

というわけで、前回に引き続いて、この記事ではTorrentファイルについて説明します。 [Torrent file format] 前回、Bencodingを実装したのでTorremt Fileを読み込めることができるようになりました。 今回は、Torrentファイルから必要な情報を読み込む方法について解説します。 torretファイルから取得できる情報はどんなものかは、別の機会に解説します。 ここでは、torrentファイルには 2つのフォーマットがあることとデータ構造を説明します。 たとえば、「"announce"というデータが何なのか?」については解説しません。 torrentファイルでは、ダウンロード/アップロードの対象としているファイルが、ひとつの場合と複数の場合で構造がすこしだけことなります。 ひとつの時を、「single file」 複数の時を「multi file」と呼ぶことにます。 では、データ構造を紹介します。 - single file pattern bendiction benstring "announce" beninteger "creation date" bendiction "info" beninteger "length" benstring "name" beninteger "piece length" bebstring "pieces" - multi file pattern bendiction benstring "announce" beninteger "creation date" bendiction "info" benlist "files" bendiction beninteger "length" benlist "path" benstring be…