P2P探訪 Raider 楽観的チョーク解除ではぶられる確率

ひとつだけランダムにChokeを解除する機能が備わっています。Chokeがされ続けて1ピースもダウンロードが開始されない状況が長く発生するのかどうか検証しました。

[Choke]

Torrentでは、一度にアップロードするPeerを制限しています。だいたい、4つくらいです。4つの内1つはランダムに切り替わります。4つの内3つは戦略的に切り替えます。つまり、転送速度に時間がかからないPeerや、以前にデータをダウンロードさせてもらったPeerに優先的にデータをアップロードするのに使用します。

低回線でひとつもデータの断片を持たない場合、ランダムに切り替わるものだけが頼りになります。長時間データがアップロードされない状況に陥ることはないのでしょうか？検証しました。

[楽観的Chokeであふれる確率]

このランダムに割り振られるアップロードするPeerを選ぶことを楽観的チョーク解除と呼ぶことにします。Chokeがデータをアップロードしない。Unchokeがデータわアップロードする。という意味です。

Peerが4つある場合

以下のような組み合わせが考えられます。○がunchokeされる。 ×がchokeされる。

○○○○ 

×○○○,○×○○
○○×○,○○○× 

××○○,×○×○
×○○×,○××○
○×○×,○○×× 

○×××,×○××
××○×,×××○

×××× 

また、○となる確率は1/4、×となる確率は3/4ですから、

4つすべてのPeerからダウンロードできる確率は(1/256)3つからダウンロードできる確率は(12/256)、2つのPeerからダウンロードできる確率は(54/256)、1つからダウンロードできる確率は、(108/256)、どのPeerからもダウンロードできない確率は(81/256)となります。

同様にどのPeerからもダウンロードできない確率、

Peerが 4の場合は、 (3**4)/(4**4) = 0.31

Peerが 5の場合は、 (4**5)/(5**5) = 0.32

Peerが50の場合は、(49**50)/(50**50) = 0.36

Peerが1000000の場合は = 0.36

といった感じになります。また、30秒ごとに切り替わりますから、Peerが50であった場合、30秒後もはぶられる確率は、0.12、60秒後もはぶられる確率は、0.04となります。

Seederが存在している限り、ダウンロードがまったまできなくなる状況が続くことはなさそうです。

[PS]

簡単な2項分布の問題でした。2項分布つにいては、Googleしてください。

書き間違えてた。書き直した。

思ったよりもChokeが長く続く可能性があるのに驚いた。何か間違えているかな?

初期状態では、どれが戦略的に優先すべきPeerが不明なわけだから、(46**50)/(50**50)=0.015となる。また、((x-4)/x)**xは0.020くらいに収束する。つまり、Peer数が増えても状況はかわらない。

....ミスッた。別の記事で書き直します。

P2P探訪 Raider JavaFXでHtmlServerを立ててMediaPlayerを再生する

「へちまたん」にTorrentでダウンロード中の動画を再生する機能を追加することにしました。

動画再生にはJavaFXのMediaPlayerを使用することにしました。しかし、JavaFXのMediaPlayerは、ファイルとアドレスしか指定できません。ダウンロード中のデータをJavaFXのMediaPlauerに渡すにはどうすればよいのでしょうか？

「へちまたん」で回答を紹介します。

[回答]

「へちまたん」は、HtmlServerの機能をもたせることで解決しました。

1. 動画ファイルをダウンロードする。

2. ダウンロード中の動画ファイルをMediaPlayerに渡すサーバーを立ち上げる。

3. 動画再生側(MediaPlayer)は「へちまたん」が立ち上げたサーバーにデータを取得しにいく。

といった感じです。

[必要な実装]

基本、GETリクエストを受けとたらそのデータを返すだけです。しかし、終盤の映像だけ再生したいといったことがある場合、これだけではうまくいきまん。

Rangeリクエストに対応する必要があります。

[Rangeリクエスト]

Rangeリクエストはダウンロードするデータの位置を指定する事ができます。

例えば、200MBの「どかまぎ列伝」というデータがあったとしましょう。20分くらい動画とします。ユーザーはこの動画すでに見たことがあるのです。しかし、終盤のシーンは見逃してしまいましたとします。理由は色々あると思いますが、とりあえず見逃したのです。なので、15分くらいの動画再生を飛ばしたいはずです。もしも、通常通り動画をサーバーからデータを読み込むと、0Bから読み込みを開始します。途中からとかできません。0Bから読み込み始めます。

この場合、1秒間1MB読み取れる、恵まれた環境の人でも、150秒です。2分以上待たされることになります。そんな問題を解決するのが、Rangeリクエストです。

Rangeリクエストは位置を指定してダウンロードできます。15分後のデータからくださいといったことが可能になるわけです。

[位置を指定してダウンロード]

動画を再生する側は簡単です。Getリクエストのヘッダーに欲しいデータの位置を指定するだけです。300MBのデータの10MBから最後までデータが欲しい場合は、「Range: bytes=10000000-」とヘッダーを追加します。これは、JavaFXのMediaPlayerの中で勝手にやってくれます。

サーバー側は、「Accept-Ranges: bytes」「Content-Range: bytes 10000000-300000000/300000001」とヘッダーを追加して、指定された位置のデータを返すだけでよいです。

といった感じで、特別難しい処理が必要ではないです。HttpのGetリクエストに追加するヘッダーが変わる事ぐらいしか特別なことはしていません。

マルチパートでレスポンスを返すといった、ちょっと複雑なケースもあります。しかし、動画の配信で呼ばれることは、ほぼほぼないでしょう。より詳しい情報はrfc2616を参照してください。

[Hetimatanのコード]

つくりかけですが..

https://github.com/kyorohiro/Hetimatan/blob/master/Hetimatan/src/net/hetimatan/net/http/SimpleHttpServer.java

P2P探訪 Raider やる気スイッチ 「はじめに」

Raiderのメタファで、Torrentクローンを作成しています。 Java で作成しています。

そろそろ、Applet上で動作するデモができそうです。 試してみて解ったことが結構ありました。

そこで、学習したしことを、epub形式でまとめることにしました。

https://github.com/kyorohiro/Raider/tree/master/Raider/doc/torrent/matome.epub

だが、やる気スイッチが入らない。なので、そこそこまとまった書きかけのものをさらすことにした。 そうすれば、やる気スイッチが入るかもしれない。

↓書き直します。たぶん、ひとかけらも残りませんが..。はじめにの章の部分

この文書について

Bittorrentのクローンを作成しています。その時に調査した結果をまとめたのこの文章です。

少しでも興味を持たれたかた。この文書を通して少しでもTorrentの理解の助けになれば幸いです。

ちまたでは、Torrentは違法なファイル共有アプリという認識が強いように思います。Twitterの検索機能で、Torrentと検索して見てください。Torrentに関するネガティブなイメージな。違法な利用を助長するようなツイートを発見することができるでしょう。

GooleでTorrentと検索してみてください。「アメリカ合衆国のデジタル ミレニアム著作権法に基づいたクレームに応じ、このページから 1 件の検索結果を除外しました。」といった文言が表示されます。また、Twiiterで検索した結果と同じように違法な利用を助長するようなサイトを発見することができるでしょう。

しかし、こういったネガティブなイメージはTorrentの一面でしかありません。まっとうな使われ方も大くされており。

例えば、大規模なネットワークシステムのデプロイといったことが上げられます。デプロイというのは、ユーザーへサービスを提供するために準備作業の事をいいます。

Googleであれば、データを即座に検索できるようにサーバーを立ち上げる。Youtubeならば、動画を再生できるようにする。Twitterならば、ツイートを送信だとか表示できるようにするといった事です。

大手のネットワークサービスでは、数千代、数万台のコンピュータが動作しております。 これらのコンピュータに変更を加える必要が出てきた場合には、修正するためのデータを数千代、数万台のコンピュータに配信する必要がでてきます。

こういった、データの配信にTorrent技術は使用されています。

例えば、OSのイメージの配信に使用されています。OSというWindowsやMacなどメーカーがCDやDVDといった記憶媒体を通して配布されている事をイメージするかも知れません。

しかし、独自にOSをパッケージングする事は、大手のメーカがする仕事というわれではありません。今では、個人が趣味でOSをパッケージングして配信する事も可能です。可能なだけでは、ありきたりな行為になりつつあります。

個人で配信する場合、当然ながら数千台、数万台のサーバーを用意する事はできません。また、CDやDVDの記憶媒体を大量に配る事にしても限界があります。

そういった、個人がデータを配布するのに、Torrentの技術が使用されています。

また、Torrentを学ぶことは、P2Pの記述を学ぶうえで最適な題材ではないかと考えられます。

まず、Torrentはもっとも普及した通信方法であります。それだけではなく、最新の技術を取り入れ進化し続けている技術でもあります。

Torrentを学習すると、ネットワークアプリ作成のノウハウ、分散ハッシュテーブル、 ゲーム理論を応用した柔軟なネットワーク等など、基本から応用まで、扱う事になります。

なによりも、多くのアプリや仕様がオープンに公開されており、P2Pを実例をもって学ぶことができるのです。

Torrent以外でメジャーなP2Pアプリはありました。しかし、Torrentほどおっぴろげなものはないでしょう。日本で流行したWinnyのソースは公開されていません。Winnyについて知りたければハックする必要があります。海外で流行したWinmxもそうです。

Torrentはその仕様が公開されています。どのような通信プロトコルで通信されているかが文書化されています。おおくの実装例、オープンソースとして公開されています。公開されているだけではありません。さまざまなプログラム言語で書かれています。Python Ruby Java JavaScript C++ 等などありとあらゆる言語で書かれています。

もしも、煮詰まったとき等は、これらの実装を読む事で保管する事も可能でしょう。あなたの得意な言語で読む事でできるのです。

Torrentのアングラな面は一面に過ぎないすぎないこと。優れた技術は多くの実用的なプロダクトで利用されていること。また、TorrentがP2Pの教材として優れておいることを理解しいただけけば幸いです。

P2P探訪 Raider やる気スイッチ 「トレントって何」

Raiderのメタファで、Torrentクローンを作成しています。 Java で作成しています。

そろそろ、Applet上で動作するデモができそうです。 試してみて解ったことが結構ありました。

そこで、学習したしことを、epub形式でまとめることにしました。

https://github.com/kyorohiro/Raider/tree/master/Raider/doc/torrent/matome.epub

だが、やる気スイッチが入らない。なので、そこそこまとまった書きかけのものをさらすことにした。 そうすれば、やる気スイッチが入るかもしれない。

↓書き直します。たぶん、ひとかけらも残りませんが..

トレントっ何

Torrentは効率良くデータを配信するするためプロトコルです。とても効率良く配信ができるため、様々な分野で利用されています。

個人では多くのユーザーにデータを届けたい場合非常にコストがかかります。これは、今までのインターネットのデータ配信をする方法では不可能でした。不可能だったことがP2Pテクノロジーによって可能になったのです。

P2Pテクノロジー

データの配信はとてもコストが高い

インターネット上でデータを配信するためには、サーバーとデータを通信する必要があります。ここでいうサーバーというのは、URLにヒモづくコンピュータという認識でよいです。

例えば、Googleで検索する場合は、http://www.google.com、 Youtubeで動画を見るには、http://www.youtube.com といったアドレスにIEやFirefoxやChromeといったブラウザからアクセスしていますね。

そういった、ブラウザからアクセスした先にはコンピュータがあり、あなたに期待に答えるように、検索結果や、動画の配信をしてくれます。

このデータを配信するサーバーはとてもコストがかかります。コストというのはお金だとか、時間だとかです。

例えば、ニコ生配信とかで、2000人くらいのユーザーが見に来るような場合、2000×50KB=100MB必要となります。 ご家庭にある通信回線は10MB程度ですから。100MBという値は、すでに個人で配信できる量ではなくなります。

また、これらを配信するサーバーを運営している方々は、こういったコストを負担してサービスを提供しているのです。

低コストでデータの配信が可能な優れもの

Torrentはこれらのコストをきわめて最小化することできます。あなたが、こういったサービスを自ら提供することも容易になりました。このサーバーにコストがかかる問題の解決策として、Torrentでは、データをダウンロードするユーザーも、データ配信に加わることにしたのです。

例えば、30分のアニメを200MBのデータとして配信する場合、1分間に2MB、1秒間に51KBのデータを配信する必要があります。

サーバー側が10MBの通信回線を持っていて、2.5MBを配信に使用する場合、同時にに50人くらい配信できます。これが限界です。

しかし、50人が2.5MBを配信に使用してくれれば、2.5×50MBつまり150MBの配信が可能になります。

150MBだと、3000人程度に配信が可能です。

また。この3000人が、2.5MB配信にまわしてくれれば、2.5×3000MB=7500MBの配信が可能になります。これは、15万人に配信が可能です。

といった感じで、データを受け取る側が増えれば増えるほど、配信可能なデータ数が増えるのがわかってもらえたでしょうか。これによって、サーバーを運営する側だけがコストを払わなくても良くなったのです。

EstevaX メモ パフォーマンス測定

[EstevaX 作業日記]
   KyoroTextのコードはすべて捨てることにしました。 新たに作り直します。
   次のアプリのメタファはEstevaです。  AESTIVALISを誤記した結果、Estevaになりました。
     # Just In Time に、情報を表示すること
     # AESTIVALIS のように直感的に扱えること
   を目標とします。


[課題]
    KyoroTextの反省として、パフォーマンスの問題があります。 ちょっとした修正が、大きくパフォーマンスに影響することがありました。
    そして、このような問題をそくざに検知することができませんでした。
    今回は開発を開始したタイミングで、この問題に対応したいと考えています。

[試み]
    EstevaXでは、 パフオーマンス測定用の自動テストを作ることにTRYしてみることしました。
    具体的には、以下のような感じです。
      -A. Instrumentation#setAutomaticPerformanceSnapshots()
      -B. Aでしている事を、別の方法で実現する。
      -C. cpuの使用率を計測する。

    ○Aは「Android Application Testing Guide」　で紹介された方法です。(http://dtmilano.blogspot.jp/)
    cpuの処理時間を元に計測できるので、より良い的なことがかかれいました。
 
    ○Bは、直接必要なAPIをたたけば良いのではないか？と考えるにいたり、「PerformanceCollector(Androidのソース)」から
    APIの使い方を流用することを思いつきまた。

    ○Cは、「TOPコマンドをたたくだけで良いかな」と考えています。
 

[A. Instrumentation#setAutomaticPerformanceSnapshots()]
   Instrumentation#setAutomaticPerformanceSnapshots()　を コールすると、Instrumentationが終了時に、
   以下のような素敵ログをはいてくれます。
   このうち、cpu_time execution_time に着目して、実際にプロセスが使用した時間を取得できます。
INSTRUMENTATION_RESULT: other_pss=3969
INSTRUMENTATION_RESULT: java_allocated=6146
INSTRUMENTATION_RESULT: global_freed_size=20128
INSTRUMENTATION_RESULT: native_private_dirty=16
INSTRUMENTATION_RESULT: native_free=132
INSTRUMENTATION_RESULT: global_alloc_count=1475
INSTRUMENTATION_RESULT: other_private_dirty=2880
INSTRUMENTATION_RESULT: global_freed_count=344
INSTRUMENTATION_RESULT: sent_transactions=-1
INSTRUMENTATION_RESULT: java_free=193
INSTRUMENTATION_RESULT: received_transactions=-1
INSTRUMENTATION_RESULT: pre_sent_transactions=-1
INSTRUMENTATION_RESULT: other_shared_dirty=2604
INSTRUMENTATION_RESULT: pre_received_transactions=-1
INSTRUMENTATION_RESULT: execution_time=5230398
INSTRUMENTATION_RESULT: native_size=2912
INSTRUMENTATION_RESULT: native_shared_dirty=24
INSTRUMENTATION_RESULT: cpu_time=317
INSTRUMENTATION_RESULT: java_private_dirty=1396
INSTRUMENTATION_RESULT: native_allocated=2779
INSTRUMENTATION_RESULT: gc_invocation_count=0
INSTRUMENTATION_RESULT: java_shared_dirty=8796
INSTRUMENTATION_RESULT: global_alloc_size=91221
INSTRUMENTATION_RESULT: java_pss=1685
INSTRUMENTATION_RESULT: java_size=6339
INSTRUMENTATION_RESULT: native_pss=16
INSTRUMENTATION_CODE: -1

   ためしに 私が書いたコードは、以下のところに起きました。
   https://github.com/kyorohiro/KyoroSamples/tree/master/InstrumentationSample

   adb shell am instrument -w .kyorohiro.samples.android.instrumentation/info.kyorohiro.samples.android.instrumentation.MyInstrumentation
   で動作します。



[-B. Aでしている事を、別の方法で実現する。]
    Aは使い勝手が悪いです。 instrumentationの動作が完了するまで結果が出力されまん。
    なので、別の方法をとることにしました。

    Androidの該当するコード(PerformanceCollector)を呼んでみると、対応するAPIは公開されていることがわかります。
    具体的には、SystemClock.uptimeMillis()　と、 Process.getElapsedCpuTime() です。
    直接このメソッドをコールすれば、プロセスがCPUの使用している時間だけをとることができます。
    かなり便利です。そして簡単です。

    ※ためしに 私が書いたコードは、以下のところに起きました。
    https://github.com/kyorohiro/KyoroSamples/tree/master/PerformanceCheckSample
    ※ ↑はCPUの使用時間以外も、Aの場合と同等の結果を任意のタイミングで返すことができます。


   当面は、 Process.getElapsedCpuTime()を使用してパフォーマンスを測定することにしました。
   何か問題が見つかるまでは、これでいこうと考えています。

Inside KyoroStress -1- Create Low Memory Killer situation on purpose!!

 Android PF have kill alive process when heigher priority process need heap. 
 This report  explain that produce Low Memory Killer situation on purpose

 You think it so simple. just to make application to consume many heap.
 but, it difficult that your thinking way.
 following problem
  - A. Android PF restrict application java heap per one process.
  - B. heap comsuming application is killed by Android PF.
  
 This report introduce KyoroStress 's solution.

[KyoroStress solution]
  Kyoro Stress done following approach.
    - 1. Booting many service in the process of differing respectively.
    - 2. Each Service consumes a lot of heaps. 

  The problem of A is solved by booting many process, and B too,
  alive heap is more consume instead of kill service's heap 


[BigEater(consuming heap service) 's senario]
  - 1. consume the specified heap.
     if retry is true, then consuming heap is repeated repeatedly until the specified heap is consumed
  - 2. recovery killed service
     if retry is true, then repeated repeatedly until killing this working thread.
  - 3. END

 you think. if ALL Service is killed by PF, when this senario is failed.
 but no problem. PF revcovery Killed service.
 so, keeping to consuming heap situation.

[KyoroStressV2 's manual]

  # start 
   start consuming heap.
  # stop
   stop consuming heap. and release.
  # num of big eater
   booting process num.
  # eatup java heap size
   consuming heap size per one process.
  # is retry
   retry option
  # show notification
   if true, consume notification.
　# lowMoemory
   if true, mean low memory state
  # availMemory
   available memory,
  # threshold
   boundary low memory state.
  #　dalvik.vm.heapsize 
   if android:largeHeap="true" 's application available heap size.
  #　dalvik.vm.heapgrowthlimit
   if android:largeHeap="false" 's application available heap size.
  # lahalito
   now consuming java heap
  # kadorto
   now recovery another killed process.
  # done all task
 　all task is end.

[Output]
  There is apk and source is following site 
   https://github.com/kyorohiro/KyoroStressV2
  Google Play address is following 
   https://play.google.com/store/apps/details?id=info.kyorohiro.helloworld.stressv2

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の操作方法について説明します。
  # start 
      ヒープの消費を開始します。
      ヒープの消費率監視を開始する。
  # stop
      ヒープの消費を終了する。そして、開放する。
  # num of big eater
      起動するプロセスの数
  # eatup java heap size
      ひとつのプロセスが消費するヒープサイズ
  # is retry
      オンならば、ヒープを確保できるまで、何度もトライする。
  # show notification
      オンならば、Notificaiotn表示をする。
　# lowMoemory
      true ならば、 ロウメモリー状態
  # availMemory
　　　使用可能なメモリ
  # threshold
      この値よりも低い場合は、ロウメモリー状態
  #　dalvik.vm.heapsize 
      ひとつのプロセスがandroid:largeHeap="true"の時に使用可能なJavaヒープ
  #　dalvik.vm.heapgrowthlimit
      android:largeHeap="false"の時に使用可能なJavaヒープ
  # lahalito
      指定されたヒープを取得しにいっている状態
  # kadorto
      PFのKILLされたサービスを再起動させようとしている状態
  # done all task
 　　 Serviceはすべての作業を完了した。そのため、もう何もすることはない状態


[成果物]
  以下の場所にソースとAPKがあります。
   https://github.com/kyorohiro/KyoroStressV2
  Google Playでも公開しています。
   https://play.google.com/store/apps/details?id=info.kyorohiro.helloworld.stressv2

[次回]
   より、詳細な仕組みは別の記事で解説します。
 - Serviceごとに、別プロセスにする方法は？
 - アプリが使用可能なヒープを調べる方法は？
 - Low Memory 状態を取得する方法は？
 - 制限を越えてヒープを取得する方法？

-------
kyorohiro work

kyorohiro.strikingly.com