# HG changeset patch # User Nobuyasu Oshiro # Date 1391237954 -32400 # Node ID d770a2b534b3b767f5b06b2f55b64cbf664057cb # Parent 2cb5ac9282b02097e73dafacdabe8aae62f4be2a Writed description of persistent diff -r 2cb5ac9282b0 -r d770a2b534b3 paper/abstract.tex --- a/paper/abstract.tex Sat Feb 01 11:44:34 2014 +0900 +++ b/paper/abstract.tex Sat Feb 01 15:59:14 2014 +0900 @@ -13,6 +13,7 @@ また, 例題アプリケーションとして簡易掲示板プログラムの作成を行った. Jungle と Cassandra により作成した掲示板プログラムに対して読み込みと書き込みの負荷をかけ 比較を行った. +結果, Cassandra以上の性能を確認することができた. \end{abstract} diff -r 2cb5ac9282b0 -r d770a2b534b3 paper/chapter1.tex --- a/paper/chapter1.tex Sat Feb 01 11:44:34 2014 +0900 +++ b/paper/chapter1.tex Sat Feb 01 15:59:14 2014 +0900 @@ -48,6 +48,15 @@ \newpage +\section{memcached} +memcachedは揮発性の分散型キャッシュである. +Key-Valueストアとなっている. +RDBとも連携して使うことができ, その場合メモリの中にデータを保持させることでディスクへのアクセスを減らし +処理性能を上げることができる. +メモリの容量がなくなると, LRU（Least Recently Used）のため一番古いデータはメモリから削除されていまう. +memcachedは永続性の + + \section{MongoDB} MongoDB は2009年に公開された NoSQL のデータベースである. JSON フォーマットのドキュメントデータベースであり, これはスキーマが無い @@ -74,12 +83,6 @@ \end{center} \end{figure} -\section{memcached} -memcachedは揮発性の分散型キャッシュである. -Key-Valueストアとなっている. -RDBとも連携して使うことができ, その場合メモリの中にデータを保持させることでディスクへのアクセスを減らし -処理性能を上げることができる. - \newpage diff -r 2cb5ac9282b0 -r d770a2b534b3 paper/chapter3.tex --- a/paper/chapter3.tex Sat Feb 01 11:44:34 2014 +0900 +++ b/paper/chapter3.tex Sat Feb 01 15:59:14 2014 +0900 @@ -192,17 +192,32 @@ \section{ログによるデータの永続性} % TreeOperationLog(ログ)をシリアライズ可能な形にしてデータをおくること % シリアライズできる形にしたものをそのままHDに書き出すだけでログの永続性は行える -Jungle は非破壊でさらにオンメモリにデータを保持するため, 使用するメモリの容量が大きくなる. +Jungle は非破壊でオンメモリにデータを保持している. だが, オンメモリのままでは電源が落ちた際にデータが失われてしまう. ディスクからデータを読み込むことでデータの復旧を行えるようにしたい. そこで, ログによるデータの永続性の実装を行う. -ログをどのようなデータ表現でハードディスクへと書きだすかという問題が発生するが, これは Alice を使うことで +Jungleの永続性実装の余地としてJournalという機能が用意されている. +このJournalにはディスクへ書き出すためのクラスとしてWriterが用意されている. +Jungleはデータの編集が完了した際にこのWriterクラスのwrite関数を呼び出すようになっている. + +このJournalとWriterクラスを新たに用意し, ディスクへと書き込み行える機能を実装する. +このとき, ログをどのようなデータ表現でハードディスクへと書きだすかという問題が発生するが, これは Alice を使うことで 解決している. -Alice を用いるため MessagePack によりシリアライズ可能な TreeOperationLog ができる. +Aliceを用いるためMessagePackによりシリアライズ可能な TreeOperationLog ができる. このシリアライズ可能な TreeOperationLog をそのままハードディスクへ書き込むこととでログの永続性ができる. + + + + + + + + + + diff -r 2cb5ac9282b0 -r d770a2b534b3 paper/chapter4.tex --- a/paper/chapter4.tex Sat Feb 01 11:44:34 2014 +0900 +++ b/paper/chapter4.tex Sat Feb 01 15:59:14 2014 +0900 @@ -60,17 +60,15 @@ \begin{figure}[htpb] \begin{center} - \includegraphics[scale=0.70]{figures/tree_topology.pdf} + \includegraphics[scale=0.70]{figures/tree_topology_noarrow.pdf} \caption{Alice によるネットワークトポロジー形成} \label{fig:tree_topology} \end{center} \end{figure} -矢印に書かれている文字列は, 相手のデータにアクセスするキーを示す. -"child1", "child2", "parent" というキーを使うことで別のサーバノードにあるデータを取得することができる. -%子共となるノードは "parent" キーにより親の DSM (Remote DSM) にアクセスすることができる. -%また, 親も子供となるノードの DSM に対して "child1" や "child2" キーによりアクセスすることが可能となる. -これでトポロジーマネージャーが起動される. +%矢印に書かれている文字列は, 相手のデータにアクセスするキーを示す. +%"child1", "child2", "parent" というキーを使うことで別のサーバノードにあるデータを取得することができる. +%これでトポロジーマネージャーが起動される. \subsection{アプリケーション側の記述} 次は Jungle 側のプログラムが最初に Alice のトポロジーノードと通信を行うようにする. @@ -170,7 +168,7 @@ 次はネットワークを介して他サーバノードのDataSegmentにアクセスするプログラムについて述べる. まず, Aliceにより2分木3ノードのトポロジーが形成された場合を想定する. -その時に実際に作られるトポロジーを図\ref{fig:remote_cs}に示す. +その時に実際に作られるトポロジーは図\ref{fig:remote_cs}となる. \begin{figure}[htpb] \begin{center} \includegraphics[scale=0.70]{figures/remote_codesegment.pdf} @@ -288,7 +286,7 @@ 他サーバノードへ伝える必要のある情報が増えた場合, このようにNetworkTreeOperationLogに情報を付与することで 対応することができる. -\subsection{ログの送信} +\subsection{ログの送信部分} ログを送信するタイミングはいつ行うか. それは, 木の編集が成功した時である. 木の編集が成功した結果得られるTreeOperationLogをNetworkTreeOperationLogに変換し, \verb|ods.put|を使って @@ -319,29 +317,144 @@ ods.put("log", log); } \end{lstlisting} -上で述べた問題は, 通常のアプリケーションとして使用する分には発生しない. -だが, ベンチマークテストなど, 大量の負荷をかけた際に発生する. -ベンチマークテストでは大量のログが生成される. +上で述べた問題は, ベンチマークテストなど, 大量の負荷をかけたさいに発生する. +負荷とはJungleのデータに変更を加わることである. +データの変更により大量のログが生成される. そのため, \verb|ods.put|によりDataSegmentの"log"にアクセスが集中してしまい, レスポンスが 悪くなっていた. \verb|ods.put|を行うタイミングには気をつけなければず, 上記のコードにしても改良の余地はある. +\subsection{他サーバノードへのログの送信} +上記の実装によりDataSegmentの"log"キーにアクセスすることでTreeOperationLogを取得できるようになった. +次はこのデータを他サーバノードへ送る部分の実装を行う. +他サーバノードに対してデータを送るときに必要なことは, そのサーバノードのDataSegmentにアクセスする +キーである. +Aliceでは接続を行っている相手のDataSegmentのキーのリストは"\_CLIST"キーを使うことで取得することができる. +"\_CLIST"キーで得られるリストを使って他サーバノードへとデータをputするコードを次に示す. -\begin{lstlisting}[frame=lrbt,label=src:,caption=,numbers=left] +\begin{lstlisting}[frame=lrbt,label=src:log_put,caption=他サーバノードへのログの送信部分,numbers=left] +public class LogUpdateCodeSegment extends CodeSegment { + Receiver log = ids.create(CommandType.TAKE); + Receiver clist = ids.create(CommandType.PEEK); + + public LogUpdateCodeSegment() { + log.setKey("log"); + clist.setKey("_CLIST");; + } + + List list = clist.asClass(List.class); + for (String node : list) { + ods.put(node, log.key, log.getVal()); + } + : +\end{lstlisting} +変数logはNetworTreeOperationLogが入っている. +変数listには"\_CLIST"により得られたデータが入っている. +それは文字列のListとなっている. +listの中身を1つずつ受け取り, \verb|ods.put|する際に引数として渡してやることで, 他サーバノードの +DataSegmentにアクセスが行える. -\end{lstlisting} +listの具体的な内容は, 図\ref{fig:tree_topology}で組まれたトポロジーでいうところの, "parent", "child1", "child2" +の文字列となっている. +もし子どもとなるサーバノードがないときは"parent"だけがListには入れられる. -\begin{lstlisting}[frame=lrbt,label=src:,caption=,numbers=left] - +\subsection{ログの受信とデータ反映} +次は受け取ったログからデータの編集を行う部分の実装を行う. +Jungleはのデータを変更する手段として木構造データ毎にTreeEditorクラスが提供される. +このTreeEditorを使用し, ログに入っているTreeOperationを1つ1つ取り出し同じ編集を行わせる. +例えば次のようになる. +\begin{lstlisting}[frame=lrbt,label=src:data_edit,caption=ログを受け取ってのデータの反映,numbers=left] +// Receiver log <- "log"キーから取得できるデータが張っている +// Jungle jugnle +NetworkTreeOperationLog netLog = log.asClass(NetworkTreeOperationLog.class); // NetworkTreeOperationLogへのコンバート +String treeName = netLog.getTreeName(); +JungleTree tree = jungle.getTreeByName(treeName); +TreeEditor editor = tree.getLocalTreeEditor(); // Editor の取得 +for (TreeOperation op : netlog) { + NodePath path = op.getNodePath(); + NodeOperation nodeOp = op.getNodeOperation(); + either = edit(editor, path, nodeOp, nodeOp.getPosition()); // データの編集を行う. + if(either.isA()) { + // エラー処理.編集失敗 + } + editor = either.b(); +} \end{lstlisting} - +7行目で取り出されたTreeOperationからさらにNodePathとNodeOperationを取り出しているのが8行目と9行目になる. +最後にedit関数にTreeEditorとNodePath, それとNodeOpeartionを引き渡している. +edit関数は次のようになる. +\begin{lstlisting}[frame=lrbt,label=src:data_edito2,caption=edit関数の実装,numbers=left] +Either edit(JungleTreeEditor editor, NodePath path, + NodeOperation nodeOp, int pos) { + String key = "; + Command c = nodeOp.getCommand(); + switch (c) { + case PUT_ATTRIBUTE: + key = nodeOp.getKey(); + ByteBuffer value = nodeOp.getValue(); + return editor.putAttribute(path, key, value); + case DELETE_ATTRIBUTE: + key = nodeOp.getKey(); + return editor.deleteAttribute(path, key); + case APPEND_CHILD: + return editor.addNewChildAt(path, pos); + case DELETE_CHILD: + return editor.deleteChildAt(path, 0); +} +\end{lstlisting} +NodeOperationのAPIの種類（Command）毎に使用するTreeEditorのAPIを変えている. +もしNodeOperationのAPIの種類を増えるようなことが合っても, 上記のコードのように +対応するTreeEditorのAPIを書くことで対応できる. +%\subsection{ローカルのデータ編集専用のTreeEditorの用意} +%データ編集が行われ, -\subsection{local専用の編集の用意} +\section{永続性の実装} +次は, ログの書き出しによる永続性の実装について述べる. +第3章でJungleはWriterいう永続性実装のための機能が元々用意されていることを述べた. +永続性で考えなければならないことは, どのようなデータをどんなデータ表現で書き込むかということである. +今回の実装ではログであるTreeOperationLogを書き出す. +また, TreeOperationLogの情報を保持しつつ, MessagePackでシリアライズできるクラスとして +NetworkTreeOperationLogの実装を行った. + +つまり, WriterでNetworkTreeOperationLogを書き出すようにすればよい. +以下にログをディスクへ書き出すためのクラスPersistentChangeListWriterの実装を示す. +\begin{lstlisting}[frame=lrbt,label=src:,caption=NetworkTreeOperationをディスクへ書き出す,numbers=left] +public class PersistentChangeListWriter implements ChangeListWriter { + + MessagePack msgpack; + OutputStream out; + public PersistentChangeListWriter(OutputStream _out, MessagePack _msgpack) { + out = _out; + msgpack = _msgpack; + } + @Override + public Result write(ChangeList cs) + { + NetworkTreeOperationLog log + = new NetworkTreeOperationLog(cs.uuid(), cs.getTreeName(), cs); + try { + msgpack.write(out, log); + out.flush(); + return Result.SUCCESS; + } catch (IOException e) { + // エラー処理 + } + return Result.FAILED; +} +\end{lstlisting} +write関数はJungleのデータ編集が完了すると呼び出される関数である. +引数として渡されているChangeListはTreeOperationLogと同じく\verb|Iterable|を継承している. +またUUIDや木の名前も取得することができる. +そのため, NetworkTreeOperationLogへと変換が行える. +ログの書き出しを行いたいときはこのPersistentChangeListWriterを設定することで行えるようになった. +これにより木の編集が行われるたびにNetworkTreeOperationLogが書き込まれていく. +読み込みたいときはMessagePackを使ってディスクから読み込み, データ分散実装と同じの方法で木の編集を行っていく +ことができる(Listing\ref{src:data_edit}, \ref{src:data_edit2}). \section{掲示板プログラムにおけるマージの実装} @@ -397,5 +510,3 @@ %環境下においては timestamp に従い子ノードを追加する位置を決めるようにする. - - diff -r 2cb5ac9282b0 -r d770a2b534b3 paper/conclusion.tex --- a/paper/conclusion.tex Sat Feb 01 11:44:34 2014 +0900 +++ b/paper/conclusion.tex Sat Feb 01 15:59:14 2014 +0900 @@ -11,6 +11,7 @@ Aliceにより自由にトポロジーを組め, 他サーバノードへのデータアクセス機構を手に入れることができた. Jungleの分散実装ではデータの編集履歴であるTreeOperationLogをAliceが使用できるようにし, 木の名前と いった必要な情報を追加することでデータの分散を行った. +また, Jungleに元々設計されていたJournalを使ってログをディスクへ書き出すことで永続性の実装を行った 最後に簡易掲示板を作成, Cassandraとの性能比較を行った. 読み込み, 書き込みの負荷をかける実験を2つ行った. 1つの実験ではサーバノード1台に対し複数のクライアントから負荷をかけた. @@ -27,6 +28,7 @@ ノード毎に木構造単位で別々のデータを保持し, 持っていない木のデータ に対して要求がくると他からとってきて返すといった機能が必要になる. + \subsection{Mergerアルゴリズムの設計} JungleはMergeを使うことでデータ衝突の問題を解決をはかるが, この Mergeはアプリケーション毎に考えなければならない. @@ -42,5 +44,14 @@ そのためにはトポロジーに割り当てられた際に他ノードから自分の持っているデータとの 差分のデータを流してもらうといった機能が必要になってくる. +\subsection{過去のデータの掃除について} +Jungleは非破壊でデータを保持し続けるため, メモリの使用量が大きい. +ある程度の単位で過去のデータの掃除を行いたい. +今回分散実装を行ったことで, 多数のノードでデータが保持され, その内の数台が +ディスクへ書き出すといったことも可能になった. +だが, Mergeの問題含め, どのタイミングで過去のデータを掃除すべきかは自明ではない. +分断耐性の実装の問題とも関わってくるが, どのデータがどれだけ複製して持っているといった +情報も扱う必要がでてくるかもしれない. + %\subsection{Treeのバランスの問題} diff -r 2cb5ac9282b0 -r d770a2b534b3 paper/master_paper.bib --- a/paper/master_paper.bib Sat Feb 01 11:44:34 2014 +0900 +++ b/paper/master_paper.bib Sat Feb 01 15:59:14 2014 +0900 @@ -1,14 +1,10 @@ -@misc{deos2013, -author = "{Mario Tokoro, Editor}", -title = "{Open Systems Dependability - Dependability Engineering for Ever-Changing Systems}", -journal = "ISBN: 978-1-4665-7751-0, CRC Press", -year = "2013" -} -@misc{d-add2013, -author = "{永山 辰巳 and 横手 靖彦}", -title = "{オープンシステムディペンダビリティとD-Caseを繋ぐリポジトリ}", -year = "2013" -} +@article{shoshi:2013a, + author = "大城 信康 and 河野 真治", + title = "Data Segment の分散データベースへの応用", + journal = "日本ソフトウェア科学会", + month = "September", + year = 2013 +} @article{shoshi:2010a, author = "玉城 将士 and 河野 真治", title = "Cassandraを使ったCMSのPCクラスタを使ったスケーラビリティの検証", @@ -32,7 +28,6 @@ month = "August", year = 2011 } - @article{cassandra, author = "Avinash Lakshman and Prashant Malik.", title = "Cassandra - a decentralized structured storage system", @@ -68,3 +63,15 @@ title = "SEDA : An Architecture for Well-Conditioned , Scalable Internet Services", journal = "SOSP" } + +@misc{deos2013, +author = "{Mario Tokoro, Editor}", +title = "{Open Systems Dependability - Dependability Engineering for Ever-Changing Systems}", +journal = "ISBN: 978-1-4665-7751-0, CRC Press", +year = "2013" +} +@misc{d-add2013, +author = "{永山 辰巳 and 横手 靖彦}", +title = "{オープンシステムディペンダビリティとD-Caseを繋ぐリポジトリ}", +year = "2013" +} diff -r 2cb5ac9282b0 -r d770a2b534b3 paper/master_paper.pdf Binary file paper/master_paper.pdf has changed