Java による授業向け画面共有システムの設計と実装

  • 大城 信康 谷成 雄
  • 琉球大学 並列信頼研究室

    本日の内容

  • 友人と作ったJavaによる画面共有システム「TreeVNC」について
  • TreeVNCを作るにあたって学んだJavaでの並列プログラミングの仕方やVNCのプロトコル話
  • TreeVNCの目的と背景

  • 大学の講義中、スクリーンに映されている画面は後ろの席程見えずらい。
  • その問題を手元のPCにも写せるようにすることで解決しようと考えた。
  • 60人以上での画面共有を行うことを目標とする。
  • VNCによる画面共有

  • 画面を共有する方法 -> VNC
  • VNC: Virtual Network Computing
    ネットワークを介してコンピュータを遠隔操作するプログラム
  • VNCのリモートPCの画面を写す機能を利用する。
  • VNCを用いての画面共有

  • まず、iMacで複数のPCからVNCをかけてみた。
  • -> 10台と繋ぐ前にVNCでの画面がカクカクに...
  • さらにCPU使用率も跳ね上がった。
  • 原因について考えたみる。
  • 通常のVNCの問題点

  • VNC Serverの負荷が重い。
  • Server側の通信網1本への通信負荷が高い。
  • 実際に測ってみた

    通常のVNCの問題点

  • 1台と48台でVNCをかけた時のスループットとサーバ側のCPU使用率
  • スループット(単位:Byte) CPU使用率
    1台 20M(最大速度) 55%
    48台 4M 100%
  • VNCに使われるCPUの使用率が100%になり、スループットが5分の1まで下がっている。
  • 通常のVNCの問題点

  • サーバへのCPU負荷が高い
  • 1本の通信網への負荷が高い
  • VNCの問題点の解決策

    クライアントを木構造で接続させるTreeVNC

    TreeVNCの利点

    通常のVNC TreeVNC
  • クライアントが増えてもかかる負荷一定。
  • 通信網1本に対する負荷が減り、安定した通信ができる(有線)。
  • TreeVNCの利点

    通常のVNC TreeVNC
    通常のVNC TreeVNC
    最大負荷 N*データ量 (クライアントの数に比例) (M+1) * データ量

    クライアントの数をN、木構造の子供の数をMとする

    TreeVNCの設計

  • 木構造での接続
  • TreeVNCのクライアントは最初にTop Proxyに接続を行う。
  • データは木の下へと流していくようにする。
  • tightVNC ViewerのJava版(ver 1.3)を元にTreeVNCの実装を行う。
  • 今回の主な内容

    RFB protocol

  • Remote Frame Buffer Protocol :
    GUI操作によるリモートアクセス用の通信プロトコル。VNCで用いられる。
  • 1~5まではinitial seaquenceとなる。
  • 6以降は繰り返し行われる処理。画面のデータが転送されてくる。
  • 画像の更新(FramebufferUpdate)

  • 転送される画面(フレームバッファ)のデータは変更があった部分(差分)だけが矩形単位で送られる。
  • で囲まれている矩形のデータだけが送られてくる。

    RFB Protocol

  • FramebufferUpdateRequest:
  • 画面に差分が発生したらサーバから教えて貰うためのリクエスト
  • バイト数
    型   [値]
    説明
    1
    U8         3
    message-type
    1
    U8
    incremental
    2
    U16
    x-position
    2
    U16
    y-position
    2
    U16
    width
    2
    U16
    height
  • このリクエストはTop Proxyだけが行う。
  • RFB Protocol

  • FramebufferUpdate:画面の更新データ
  • バイト数
    型   [値]
    説明
    1
    U8          0
    message-type
    1
    U8
    padding
    2
    U16
    number-of-rectangles
  • 以下number-of-rectanglesの数だけ矩形のデータが続く
  • バイト数
    型   
    説明
    2
    U16
    x-position
    2
    U16
    y-position
    2
    U16
    width
    2
    U16
    height
    4
    U32
    encoding-type
    ...
    ...
    PIXEL DATA

    RFB Protocol

  • 例:FramebufferUpdate
  • x-position 336
    y-position 388
    width 724
    height 449
    encoding-type 16(ZRLE)
    ZRLE ...

    データ転送量

    矩形の大きさと描画に必要なデータ量(単位:Byte)

    矩形の大きさ \ エンコード RAW ZRLE
    724 * 449 1.3M 0.8M
    1920 * 64 0.5M 0.15M
    1920 * 1080 8.2M 3.4M


    RAW、ZRLE、ZRLEEエンコードのデータ量の比較

    データ転送量

  • クライアントが60台とした時、通常のVNCと、2分木構成にしたTreeVNCの通信網への負荷の理論値を考える。
  • 通常のVNC TreeVNC
    最大負荷 N * データ量(クライアントの数に比例) (M+1) * データ量

    クライアントの数をN、木構造の子供の数をMとする

  • N = 60、 M = 2 、使用するエンコードはZRLEとする。
  • 724 * 449 の画面分のデータ(0.8M)を送信するとする。
  • データ転送量

    理論値

    通常のVNC TreeVNC
    最大負荷 48M 2.4M

    通常のVNC TreeVNC

    クライアント:60台 TreeVNCは2分木でTreeを構成

    エンコード

  • MacintoshでZRLEを使ってVNCを行うことができる
  • データ量がRAWデータの約4分の1ですむ。
  • TreeVNCではこのZRLEを扱っている。
  • ZRLE

  • ZRLE : Zlib Run-Length Encoding
  • 最初の4バイトにはZlibのデータの長さが、続いてZlibのデータが送られてくる。
  • バイト数
    型 
    説明
    4 U32 length
    length U8 array ZlibData
  • VNCでZRLEを使う場合は単一のzrleストリームを使ってデータの解凍を行う。
  • 問題が発生
  • ZRLEの問題

  • Zlibデータは辞書を元にデータの解凍を行う
  • 辞書がなければデータを正しく解凍できない
  • ZRLEの問題

  • 辞書はZlibデータの最初に送られてくる。
  • もしも、ZRLEのデータを最初から送っているのなら、辞書も送ることができる。
  • データの途中から送ると辞書は送られず、正しく解凍を行うことができない。
  • Zlibデータを扱うZlibInStreamがエラーを吐く
  • ZRLEE

  • そこで、ProxyがZRLEを使ってデータを受け取り圧縮し直して木の下へ流していくことにした。
  • Deflater nDeflater = deflater; // new Deflater();
    LinkedList out = new LinkedList();
    unzip(inflater, inputs, 0 , out, INFLATE_BUFSIZE);
    // dump32(inputs);
    int len2 = zip(nDeflater, out, 0, bufs);
    
  • この圧縮し直したデータはZRLEEと名付けた。
  • ZRLEE

  • クライアント側は毎回新しいZRLEのストリームを使うようにする。
  • 	    if (rfb.updateRectEncoding==RfbProto.EncodingZRLEE) 
       	       zrleInStream = null;
    	    if (zrleInStream == null)
    	       zrleInStream = new ZlibInStream();
    	  
  • Zlibの規約には辞書の取り出し(flush)については書かれている。
  • Javaでは実装されていなかった為、このような方法をとることになった。
  • ZRLEEの疑問点

  • ZRLEEには毎回辞書が付与されている。
  • ZRLEに比べるとデータ量は増えないのか...?
  • -> ZRLEと比較してみるとデータ量は変わらないことが判明
  • ZRLEEのデータ量

    1920*1080の描画にかかったデータ量

    ZRLE ZRLEE
    データ量 3.4M 3.2M
  • ZRLEよりデータ量が多くなるどころか少ない。
  • 原因
  • ZRLEEを使う利点

  • データ量が少なくですむ
  • 一度ZRLEEに圧縮してしまえば、データはそのまま流すことができる。
  • TreeVNCの設計にある「データを木の下へ流す」の条件を満たす。
  • データの転送

  • クライアントから接続されるとsenderスレッドが作られる。
  • senderスレッドによりデータの転送は並列に行われる。
  •  

  • MulticastQueueクラスを用いた並列な転送を行った。
  • MulticastQueue

  • MulticastQueue:データを順序よく読み込ませるクラス
  • 次のデータがなければwaitする データがputされ次第読み込みを再開する

    MulticastQueueは、java.util.CountDownnLatchにより実装されている。

    MulticastQueue

  • putでデータの入力
  • pollでデータの取り出し
  • Proxyは常に最新のデータの参照を渡す
  • クライアントは最新のデータから読み込み始める。
  • 実際のソースでみてみる

    MulticastQueueの問題点

  • クライアントがデータを読み込まない時...
  • 読み込まれないデータはProxyのメモリに残り続ける。
  • MulticastQueueの問題点

  • TimeOut(TO)スレッドを走らせ、最新のデータから取得できるようする。
  • どこからも参照されないデータはProxyのメモリから削除される。
  • 並列なデータ転送に関して...

  • 次のソースを見てください。
  • executor.execute(new SendThread(out, buffer));
    	
  • 実はこのソース、僕が最初に書いた並列にデータを転送させる部分です。
  • 一回のデータ転送に1スレッドを立てているというとても酷いソース
  • 3台つなげただけでプログラムが落ちた。
  • こんなプログラムだけは書かないようにしましょう...
  • 木の構成手順

    requestHostName();
    プロキシに対してホストのアドレスを要求する関数。

    木の構成手順

    transferParentAddress();
    クライアントに接続先を教える関数。

    実際にクライアントにおくっているデータは
    parentAddress -> 親のアドレス
    parentNum -> 親の番号
    treeNum -> 自分の木の番号
    leaderFlag -> リーダフラグ
    の4つである。
    リーダーは子供の中で一番若い番号の人がなる。
    リーダーフラグは木の再構成の際に使用する。

    木の構成手順

    connectAndAuthenticate();
    プロキシから受け取ったデータをもとに接続を開始する関数。

    木の構成手順

    新しいクライアントが来るたびに今まで説明した3つの関数を呼び出す。

    木の構成手順

    木の構成手順

    木の構成手順

    木の構成手順

    木の構成手順

    ここで接続先がクライアント1になっているがこれはプロキシ側で
    親の番号 = (自分の番号 - 1) / 親に対する子どもの数
    を計算してどの親に接続させれば良いかを決めてクライアントに報告している。
    このように番号で木を管理している。

    木の再構成手順

    クライアント1が落ちた時の再接続の処理についての説明。

    木の再構成手順

    lostHost();
    木を構成する際にリーダを決めたが、そのリーダだけが呼び出す関数。
    プロキシに対し落ちた親(クライアント1)の情報を報告する。

    木の再構成手順

    reportLastNode();
    ラストノードに対し落ちたクライアントの代わりをするように命令を出す。

    木の再構成手順

    connectAndAuthenticate();
    プロキシから受け取ったデータをもとに接続を開始する関数。
    この時クライアント6がクライアント1に変わる。

    木の再構成手順

    transferParentAddress();
    落ちた親の子供たちに対し新しい親のアドレスを報告する関数。

    木の再構成手順

    connectAndAuthenticate();
    プロキシから受け取ったデータをもとに接続を開始する関数。

    木の再構成手順

    再構成後の木

    最後に

  • 今回のTreeVNCは大学の授業「programming4」で作り始めた。
  • Javaは基本知識だけ、VNCの仕組みについては全く知らない状態からのスタートあった。
  • 木の再構成、MulticastやZRLEの問題にも出会ったがなんとかクリアすることができた。
  • Javaでの分散プログラミングは考えていたよりも楽であった。
  • 質問タイム