Mercurial > hg > Papers > 2015 > nozomi-sigos

comparison paper/chapter4.tex @ 0:0127effb8fcd

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
first commit
author Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
date Tue, 05 May 2015 15:36:41 +0900
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:0127effb8fcd
1 \chapter{改善点} \label{chapter:chapter4}
2 分散フレームワークAliceは、並列環境にも対応したフレームワークである。しかし、並列環境に対応していることを確認するためにbitonic sortを作成、計測したところ、Data Segmentの更新のオーバーヘッドにより、期待した効果を得ることができなかった。また、AliceVNCを開発する際にAliceの送受信部分に無駄なコピーが発見された。
3 これらを解決するためにAliceに改善を行った。
4 \section{SEDA Architecture}
5 SEDA Architecture \cite{cassandra, seda}とはマルチコアスレッドを用いて大量の接続を管理し、受け取ったデータを処理ごとに分けられたステージと呼ばれるスレッドに投げ、処理が終わると次のステージにデータを伝搬させていく処理方式である。
6 スループット重視のでありレスポンスは多段のパイプラインのせいで遅れてしまう。
7 Aliceに置いてSEDAを実装するにあたり、データを次のステージにへ伝搬する際、LinkedBlockingQueueを使用している。LinkedBlockingQueueは片方向の連結リストをベースとしたQueue実装である。enqueue / dequeueの操作時の排他制御にはそれぞれ別々のロックオブジェクトが使用されている。そのため、enqueueとdequeueが重なってもロック解除待ちは発生しないが、そのかわりに連結リストのNodeオブジェクトの生成操作などが発生してしまうため、enqueue操作の処理コストが高い。
8 さらに、非力なマシーンではSEDAの効果を得られず、スレッドを切り替えが頻繁に起こりオーバーヘッドになってしまう。
9
10 以上の理由からLocal Data Segmentに対して操作をする際はSEDAを使用せず処理を行なうように変更した。
11 変更前は、Local Data Segmentに対して操作する場合、putやpeekに沿ったCommandを作成するステージ(Code Segmentが実行されているスレッド)、受け取ったCommandを処理するステージ、Code SegmentにData Segmentをセットするステージ（peekとtakeの場合）の2段または3段のパイプラインで構成されていた。これらを1つのステージにまとめて処理することで、並列環境における性能を向上させた。
12
13 \section{Data Segment の再構成（flip 機能の追加）}
14 Data Segment APIのput、updateを呼ぶとOutput Data Segmentが毎回新しく作成される。そして出力するデータのコピーが行われる。しかし、Input Data Segmentとして取得したデータに変更を行い、Output Data Segmentとして出力する場合、コピーを行なうのは無駄である。そこで、このコピーを減らすことで速度改善を行った。
15
16 このコピーを無くし、Data Segmentの更新におけるオーバーヘッドを減らす方法として並列タスク管理フレームワーク Cerium\cite{yutaka:2010a, yutaka:2011a, yutaka:2011b}でも良好な結果を得ているflipを用いた。Ceriumにおけるflipは、Input Data SegmentとOutput Data SegmentをswapさせるAPIである。(ソースコード \ref{src:flipCerium})
17
18 \begin{table}[html]
19 \lstinputlisting[label=src:flipCerium, caption=Ceriumにおけるflip]{source/flip.cc}
20 \end{table}
21
22
23 \begin{table}[html]
24 \lstinputlisting[label=src:flipAlice, caption=Aliceにおけるflip]{source/flip.java}
25 \end{table}
26
27 \begin{table}[html]
28 \lstinputlisting[label=src:exampleFlip,caption=flipの使用例]{source/Sort.java}
29 \end{table}
30
31 Ceriumの場合、Output Data SegmentはTaskが実行された段階ですでに用意されている。そのためデータをOutput Data Segmentに書き込む前にflipを呼ぶ。
32 Aliceの場合、putまたはupdateを呼んだ段階でOutput Data Segmentが作られるため、ソースコード\ref{src:exampleFlip}のようにInput Data SegmentであるReceiverをflipメソッドに引数として渡すことで、無駄なコピーを減らす。
33
34 \section{Data Segmentのデータ表現の追加}
35 変更前はData Segmentのデータ表現はMessage Pack for JaveのValueオブジェクトのみを用いて表現していた。
36 Valueオブジェクトとは、Message Packのバイナリにシリアライズできる型のみで構成されたJavaのオブジェクトであり、自己記述形式のデータ形式となっている。そのため、ArrayValueを用いることにより、ユーザーはデータを後からつなげたりすることも可能である。
37
38 このValueオブジェクトの特徴の1つに、通信に関わる際のシリアライズ・デシリアライズを高速に行えることがある。
39 この特徴を用いて、Remote Data Segmentに対する通信の高速化を狙っていた。
40
41 しかし、Local Data Segmentに対する通信においては逆効果である。データをLocal Data Segmentに対してputするたびにValue型に変換するコストがかかる。データをpeekする際にもValue型から元の型に変換するというコストがかかる。
42
43 この問題を解決するために、一般的なJavaのクラスオブジェクトでもデータ表現を可能にした。Local Data Segmentに対してputする場合は、Valueオブジェクトに変換せず一般的なJavaのクラスオブジェクトのままで、Remote Data Segmentに対してputする場合にのみValueに変換する。これにより、無駄な変換コストを抑えられるようになった。
44
45 \section{Data Segmentのデータ表現の変更} \label {subsection:changeDSFormat}
46 AliceVNCは、\ref {section:AliceVNC}で説明したように、当研究室で開発しているTreeVNCを分散フレームワークAliceを用いて実装した画面共有システムである。
47
48 Topology Nodeは受け取った画面データを描画すると同時に、Remote Data Segmentに送信する。Remote Data Segmentに送信する際にはMessage PackによりValue型に変換し、その後シリアライズ化（byteArrayで表現されたバイナリに変換）される。Topology Nodeは受信するとデシリアライズしValue型に変換した後putされる。
49
50 このValue型への変換が問題である。受け取ったデータを自分の子ノードに対して送信する際には、デシリアライズしValue型に変換する必要はない。シリアライズ状態のまま子ノードに送信すれば、Value型に変換するオーバーヘッドとValue型をシリアライズするオーバーヘッドを無くすことができる。そこで、Remoteからputされたデータ表現をValue型からbyteArrayで表現されたbinaryに変更した。また、Remoteにputする際にもValue型に変換せずに直接byteArrayに変換するように変換した。
51
52
53 しかし、この変更で新しい問題が発生した。Remoteからputされたデータは必ずbyteArrayで表現される。しかし、putされたbyteArrayが全てシリアライズ化された状態であるとはいえない。一般的なJavaのクラスオブジェクトとしてbyteArrayが使用されている場合が存在する。例えば、AliceVNCで使われる画像データはbyteArrayで表現されているが、これはLocalからputされている。 Input Data Segmentが格納されるReceiverクラスには{\tt asClass()}というメソッドがある。
54
55 \begin{itemize}
56 \item \verb+public <T> T asClass(Class<T> clazz)+
57 \end{itemize}
58
59 このメソッドは取得したデータがRemoteからputされた場合、Value型でなっているためMessage Packを使い適切な型に変換するものである。しかし、byteArray型に変更したため、変換可否を判断することができなくなってしまった。
60
61 ここからわかることは、データを表現するにはデータ単体をやりとりするだけでは不十分ということである。変更以前はValue型であるということが状態を表していた。しかし、一般的なJavaのクラスオブジェクトとbyteArrayで表現されたbinaryが混在する現在では、データと一緒にデータの状態を表すメタデータもやりとりする必要がある。そこで、データとデータの状態を1つのオブジェクトにまとめ扱うように変更した。(ソースコード\ref {src:ReceiveData})
62
63 \begin{table}[html]
64 \lstinputlisting[label=src:ReceiveData, caption=データを表現するクラス]{source/ReceiveData.java}
65 \end{table}
66
67 {\tt val}がデータ本体が保存格納される。{\tt serialized}と{\tt byteArray}がデータの状態を表すメタデータである。{\tt serialized}
68 は、データ本体がシリアライズ化されているかを示す。{\tt byteArray}がデータ本体がbyteArrayであるかを示す。
69 この2つの状態があることで{\tt asClass()}を使い、適切に変換することができる。(ソースコード\ref {src:asClass})
70
71 \begin{table}[html]
72 \lstinputlisting[label=src:asClass, caption=asClassの処理]{source/asClass.java}
73 \end{table}
74
75 asClassが行う処理は、Localからputされたデータ（{\tt serialized}と{\tt byteArray}がfalseの場合または{\tt byteArray}のみtrueの場合）は、目的のClassにcastする。Remoteからputされたデータ（{\tt serialized}がtrueの場合）はMessage Packを使い変換する。
76
77 \subsubsection{Message Packの機能追加}
78 通信入力部はMessage PackのUnpackerを用いる事により、ストリームを次から次へとデシリアライズすることができる。
79 しかし、提供されているAPIは全てデシリアライズを行うものであり、シリアライズ状態のオブジェクトを取得することができない。そこでUnpackerにシリアライズ状態のオブジェクトを取得するメソッドを追加した。
80
81 \begin{table}[html]
82 \lstinputlisting[label=src:Incoming, caption=ByteBuffer作成部分]{source/IncomingTcpConnection.java}
83 \end{table}
84 ソースコード\ref {src:Incoming} は受け取ったデータをLocal Data Segmentに追加する処理である。
85 getSerializedByteArrayメソッドでシリアライズ状態のオブジェクトを取得している。
86
87 このメソッドの実装をもって、受け取ったデータをデシリアライズせずに、子ノードに渡すことが可能となった。
88
89 \section{パケットの再設計}
90 Aliceの通信の際には、CommandMessage.classのインスタンスをMessage Packによりシリアライズ化したものが送信される。
91 つまり、CommandMessage.classがパケットの構造を表すものといえる。
92
93 \begin{table}[html]
94 \lstinputlisting[label=src:CommandMessageBefore, caption=変更前のCommandMessage]{source/CommandMessagebefore.java}
95 \end{table}
96 ソースコード\ref {src:CommandMessageBefore}が変更前のCommandMessageの内容である。表\ref{tb:variable}はCommandMessageの各変数が何を表しているかを示したものである。
97 \begin{table}[htbp]
98 \caption{CommandMessageの変数名の説明}
99 \label{tb:variable}
100 \begin{center}
101 \begin{tabular} {|l|l|}
102 \hline
103 変数名&説明\\
104 \hline
105 type&CommandType {\tt PEEK, PUT}などを表す\\
106 \hline
107 seq&Data Segmentの待ち合わせを行っているCode Segmentを表すunique number\\
108 \hline
109 key&どのKeyに対して操作を行うか指定する\\
110 \hline
111 val&データ本体\\
112 \hline
113 quickFlag&SEDAを挟まずCommandを処理を行うかを示す\\
114 \hline
115 serialized&データ本体のシリアライズ状態を示す\\
116 \hline
117 \end{tabular}
118 \end{center}
119 \end{table}
120
121 このパケット構造に問題が存在する。DS本体はCommandMessageがシリアライズ化されるときにはすでに、シリアライズされている。つまり、このままCommandMessageをシリアライズ化を行うと、DS本体をもう1度シリアライズ化を行ってしまう。
122
123 \begin{table}[html]
124 \lstinputlisting[label=src:CommandMessage, caption=変更後のCommandMessage]{source/CommandMessage.java}
125 \end{table}
126
127 そこで、CommandMessageをソースコード\ref{src:CommandMessage}のように変更した。データ本体をCommandMessageのフィールドから外し、後からByteBufferにまとめることにより2度のシリアライズを防ぐ。(ソースコード\ref{src:convert})
128
129 \begin{table}[html]
130 \lstinputlisting[label=src:convert, caption=ByteBuffer作成部分]{source/CreateByteBuffer.java}
131 \end{table}
132
133 この実装ではCommandMessage部をヘッダーとして扱っている。データ部はCommandTypeが{\tt UPDATE、PUT、REPLY}の時のみ後から付加される。以前の実装ではbyte[]の値としてnullを示すNilValueがあるものとしてシリアライズ化されており、これもオーバーヘッドである。現在の実装にでは、CommandTypeが{\tt UPDATE、PUT、REPLY}以外はの時は、データ部をシリアライズ化しないため、nullをシリアライズ化するオーバーヘッドはなくなっている。