Mercurial > hg > Papers > 2018 > suruga-thesis
changeset 22:18ccb3cef737
fix
| author | suruga |
|---|---|
| date | Mon, 19 Feb 2018 14:12:01 +0900 |
| parents | b7a3d0b7530f |
| children | ae83bdf21518 |
| files | .DS_Store paper/.DS_Store paper/final_main/.DS_Store paper/final_main/chapter1.tex paper/final_main/chapter2.tex paper/final_main/chapter4.tex paper/final_main/main.aux paper/final_main/main.dvi paper/final_main/main.lof paper/final_main/main.log paper/final_main/main.lol paper/final_main/main.pdf paper/final_main/main.toc |
| diffstat | 13 files changed, 81 insertions(+), 82 deletions(-) [+] |
line wrap: on
line diff
--- a/paper/final_main/chapter1.tex Mon Feb 19 11:34:24 2018 +0900 +++ b/paper/final_main/chapter1.tex Mon Feb 19 14:12:01 2018 +0900 @@ -15,11 +15,12 @@ 分散データシステムは、データの整合性 (一貫性)、常にアクセスが可能であること (可用性)、データを分散させやすいかどうか (分割耐性)、この 3 つを同時に保証するこ とは出来ない。これは CAP 定理と呼ばれる。 一貫性と可用性を重視しているのが、現在最も使われているデータベースであるRelational Database(RDB)である。そのため、データを分割し、複数のノードにデータを分散させることが難しく、結果スケールアウトが困難になってしまうという問題がある。分断耐性を必要とする場合は、NoSQLデータベースを選択する。 - 当研究室では、これらの問題を解決した、煩雑なデータ設計が必要ないスケーラビリ ティのあるデータベースを目指して、非破壊的木構造データベース Jungle を開発している。JungleはNoSQLを元に開発されているため、分断耐性を持っている。また、Jungle は、全体の整合性ではなく、木ごとに閉じた局所的な整合性を保証している。 整合性のある木同士をマージすることで新しい整合性のある木をす繰り出すことも 可能であるため、データの伝搬も容易である。Jungle は、これまでの開発によって木構造を格納する機能をもっている。 + 当研究室では、これらの問題を解決した、煩雑なデータ設計が必要ないスケーラビリ ティのあるデータベースを目指して、非破壊的木構造データベース Jungle[2] を開発している。JungleはNoSQLを元に開発されているため、分断耐性を持っている。また、Jungle は、全体の整合性ではなく、木ごとに閉じた局所的な整合性を保証している。 整合性のある木同士をマージすることで新しい整合性のある木をす繰り出すことも 可能であるため、データの伝搬も容易である。Jungle は、これまでの開発によって木構造を格納する機能をもっている。 \section{研究目的} Jungleは現在、JavaとHaskellによりそれぞれの言語で開発されている。本研究で扱うのはJava版である。 -これまでに行われた分散環境上でのJungleの性能を検証する実験では、huskellで書かれたJungleの方が、Javaで書かれたJungleよりも、読み込みで 3.25 倍, 書き込みで 3.78 倍の性能差が確認できた。 -huskellは、モダンな型システムを持ち, 型推論と 型安全により、信頼性に重きを置いてプログラミングを行う関数型言語である。対して、Javaはコンパイラ型言語であり、構文に関してはCやC\#の影響を受けており、プログラムの処理に関してはHuskellよりもパフォーマンスが高い言語であるといえる。処理速度においてはHuskellよりも高いことを予想されていたのにもかかわらず、Java版がHuskell版よりも遅くなってしまった原因として、性能測定時に使用するテストプログラムのフロントエンドにWebサーバーJettyが使用されていたことが考えられる。これでは、この性能結果が、異なる言語で実装されたJungleの性能差によるものなのか、Webサーバーの性能差によるものなのかがわからない。 +これまでに行われた分散環境上でのJungleの性能を検証する実験[5]では、Huskellで書かれたJungleの方が、Javaで書かれたJungleよりも読み込み、書き込み共に高い性能差を出していた。 + +Huskellは、モダンな型システムを持ち, 型推論と 型安全により、信頼性に重きを置いてプログラミングを行う関数型言語である。対して、Javaはコンパイラ型言語であり、構文に関してはCやC\#の影響を受けており、プログラムの処理に関してはHuskellよりもパフォーマンスが高い言語であるといえる。処理速度においてはHuskellよりも高いことを予想されていたのにもかかわらず、Java版がHuskell版よりも遅くなってしまった原因として、性能測定時に使用するテストプログラムのフロントエンドにWebサーバーJettyが使用されていたことが考えられる。 そこで、本研究では、新たにWebサーバーを取り除いた測定用プログラムを作成し、純粋なJava版Jungleの性能を測定する方法を提案する。 %\section{論文の構成}
--- a/paper/final_main/chapter2.tex Mon Feb 19 11:34:24 2018 +0900 +++ b/paper/final_main/chapter2.tex Mon Feb 19 14:12:01 2018 +0900 @@ -14,6 +14,10 @@ Jungleはデータの変更を非破壊で行なっており、編集ごとのデータをバージョンとしてTreeOperationLogに残している。Jungleの分散ノード間の通信は木の変更のTreeOperationLogを交換することによって、分散データベースを構成するよう設計されている。 \section{分散機構} +Jungleの分散設計は、Git や Mercurial といった分散バージョン管理システム(以下、分散管理システム)の機能を参考に作られている。分散管理システムとは、多人数によるソフトウェア開発において変更履歴を管理するシステムである。分散管理システムでは開発者それぞれがローカルにリポジトリのクローンを持ち、開発はこのリポジトリを通して行われる。ローカルのリポジトリは独立に存在し、サーバ上にあるリポジトリや他人のリポジトリで行われた変更履歴を取り込みアップデートをかけることができる。また、逆にローカルリポジトリに開発者自身がかけたアップデートを他のリポジトリへと反映させることもできる。分散管理システムではどれかリポジトリが壊れたとしても、別のリポジトリからクローンを行うことができる。ネットワークに障害が発生しても、ローカルにある編集履歴をネットワーク復帰後に伝えることができる。 +このように、分散管理システムはデータ変更の履歴を自由に受け取ることが可能である。しかし、お互いが同じデータに対して編集を行なっている場合、変更履歴を自由に受け取ることができないことがある。これを衝突という。衝突は、分散管理システムを参考にしている Jungle においても起こる問題である。 +Jungleはリクエストが来た場合、現在持っているデータを返す。その為、データは最新のものであるかは保証されない。この場合、古いデータに編集が加えられ、それを更に最新のデータへ伝搬させる必要がある。このように他のリポジトリにより先にデータ編集が行われているとき、データの伝搬が素直にできない為、衝突が起きてしまう。この衝突に対し、分散管理システムではMergeと呼ばれる作業を行う。Mergeとは、相手のリポジトリのデータ編集履歴を受け取り、ローカルにあるリポジトリの編集と合わせる作業である。Jungleは、アプリケーションレベルでのMergeを実装することで、衝突を解決する。 + Jungleの分散機構は、木構造、すなわちツリー型を想定したネットワークトポロジーを形成し、サーバー同士を接続することで通信を行なっている。ツリー型であれば、データの整合性をとる場合、一度トップまでデータを伝搬させることで行える。トップまたはトップまでの間にあるサーバーノードでデータを運搬中に衝突が発生したらMergeを行い、その結果を改めて伝搬すればよいからである(図\ref{fig:tree}）。 \begin{figure}[htbp] @@ -30,8 +34,6 @@ \item Mergeされたデータがservernode 1,servernode 2へ伝搬 \item servernode1からMergeされたデータがservernode 3、servernode 4へ伝搬。全体でデータの整合性が取れる。 \end{enumerate} - - リング型(図\ref{fig:ring} ）やメッシュ型(図\ref{fig:mesh} ）のトポロジーでは、データの編集結果を他のサーバーノードに流す際に、流したデータが自分自身に返ってくることでループが発生してしまう可能性がある。 ツリー型であれば、閉路がない状態でサーバーノード同士を繋げることができる為、編集履歴の結果を他のサーバーノードに流すだけですみ、結果ループを防ぐことができる。
--- a/paper/final_main/chapter4.tex Mon Feb 19 11:34:24 2018 +0900 +++ b/paper/final_main/chapter4.tex Mon Feb 19 14:12:01 2018 +0900 @@ -1,8 +1,6 @@ %比較実験は間に合わないかもしれない %もしかしたら、本当に結果だけ出して、手法として紹介する...? \chapter{性能評価} -\section{java版jungleとhuskell版jungleの比較} - \section{java版jungleの分散性能の評価}
--- a/paper/final_main/main.aux Mon Feb 19 11:34:24 2018 +0900 +++ b/paper/final_main/main.aux Mon Feb 19 14:12:01 2018 +0900 @@ -10,50 +10,49 @@ \@writefile{lot}{\addvspace {10\p@ }} \@writefile{toc}{\contentsline {section}{\numberline {2.1}Jungleデータベースの構造}{3}} \@writefile{toc}{\contentsline {section}{\numberline {2.2}分散機構}{3}} -\@writefile{lof}{\contentsline {figure}{\numberline {2.1}{\ignorespaces ツリー型のトポロジー}}{4}} -\newlabel{fig:tree}{{2.1}{4}} +\@writefile{lof}{\contentsline {figure}{\numberline {2.1}{\ignorespaces ツリー型のトポロジー}}{5}} +\newlabel{fig:tree}{{2.1}{5}} \@writefile{lof}{\contentsline {figure}{\numberline {2.2}{\ignorespaces ring型のトポロジー}}{5}} \newlabel{fig:ring}{{2.2}{5}} -\@writefile{lof}{\contentsline {figure}{\numberline {2.3}{\ignorespaces メッシュ型のトポロジー}}{5}} -\newlabel{fig:mesh}{{2.3}{5}} -\@writefile{toc}{\contentsline {chapter}{\numberline {第3章}評価実験}{6}} +\@writefile{lof}{\contentsline {figure}{\numberline {2.3}{\ignorespaces メッシュ型のトポロジー}}{6}} +\newlabel{fig:mesh}{{2.3}{6}} +\@writefile{toc}{\contentsline {chapter}{\numberline {第3章}評価実験}{7}} \@writefile{lof}{\addvspace {10\p@ }} \@writefile{lot}{\addvspace {10\p@ }} -\@writefile{toc}{\contentsline {section}{\numberline {3.1}実験目的}{6}} -\@writefile{lot}{\contentsline {table}{\numberline {3.1}{\ignorespaces HaskellとJavaの比較}}{6}} -\newlabel{tab:compare}{{3.1}{6}} -\@writefile{toc}{\contentsline {section}{\numberline {3.2}実験概要}{7}} -\@writefile{lof}{\contentsline {figure}{\numberline {3.1}{\ignorespaces 複数のjungleに書き込まれたデータがrootのjungleへ到達する時間を計測する}}{7}} -\newlabel{fig:gaiyou}{{3.1}{7}} -\@writefile{toc}{\contentsline {section}{\numberline {3.3}実験環境}{8}} -\@writefile{lot}{\contentsline {table}{\numberline {3.2}{\ignorespaces KVMの詳細}}{8}} -\newlabel{tab:kvm}{{3.2}{8}} -\@writefile{lot}{\contentsline {table}{\numberline {3.3}{\ignorespaces 仮想クラスタの詳細}}{8}} -\newlabel{tab:vm}{{3.3}{8}} -\@writefile{toc}{\contentsline {section}{\numberline {3.4}TORQUE Resource Manager}{8}} -\@writefile{lof}{\contentsline {figure}{\numberline {3.2}{\ignorespaces TORQUEの構成}}{9}} -\newlabel{fig:torque}{{3.2}{9}} -\newlabel{LogupdateTest.pl}{{3.1}{9}} -\@writefile{lol}{\contentsline {lstlisting}{\numberline {3.1}本実験で投入するジョブスクリプト}{9}} -\@writefile{toc}{\contentsline {section}{\numberline {3.5}分散フレームワーク Alice による分散環境の構築}{10}} -\@writefile{lof}{\contentsline {figure}{\numberline {3.3}{\ignorespaces AliceによるJungleの木構造トポロジーの形成}}{10}} -\newlabel{fig:topologymanager}{{3.3}{10}} -\@writefile{lof}{\contentsline {figure}{\numberline {3.4}{\ignorespaces トポロジーの形成}}{11}} -\newlabel{fig:LogupdateTree}{{3.4}{11}} -\@writefile{toc}{\contentsline {section}{\numberline {3.6}測定用プログラムの実装}{12}} -\newlabel{Logupdate}{{3.2}{12}} -\@writefile{lol}{\contentsline {lstlisting}{\numberline {3.2}測定用プログラムの起動部分}{12}} -\@writefile{toc}{\contentsline {chapter}{\numberline {第4章}性能評価}{14}} +\@writefile{toc}{\contentsline {section}{\numberline {3.1}実験目的}{7}} +\@writefile{lot}{\contentsline {table}{\numberline {3.1}{\ignorespaces HaskellとJavaの比較}}{7}} +\newlabel{tab:compare}{{3.1}{7}} +\@writefile{toc}{\contentsline {section}{\numberline {3.2}実験概要}{8}} +\@writefile{lof}{\contentsline {figure}{\numberline {3.1}{\ignorespaces 複数のjungleに書き込まれたデータがrootのjungleへ到達する時間を計測する}}{8}} +\newlabel{fig:gaiyou}{{3.1}{8}} +\@writefile{toc}{\contentsline {section}{\numberline {3.3}実験環境}{9}} +\@writefile{lot}{\contentsline {table}{\numberline {3.2}{\ignorespaces KVMの詳細}}{9}} +\newlabel{tab:kvm}{{3.2}{9}} +\@writefile{lot}{\contentsline {table}{\numberline {3.3}{\ignorespaces 仮想クラスタの詳細}}{9}} +\newlabel{tab:vm}{{3.3}{9}} +\@writefile{toc}{\contentsline {section}{\numberline {3.4}TORQUE Resource Manager}{9}} +\@writefile{lof}{\contentsline {figure}{\numberline {3.2}{\ignorespaces TORQUEの構成}}{10}} +\newlabel{fig:torque}{{3.2}{10}} +\newlabel{LogupdateTest.pl}{{3.1}{10}} +\@writefile{lol}{\contentsline {lstlisting}{\numberline {3.1}本実験で投入するジョブスクリプト}{10}} +\@writefile{toc}{\contentsline {section}{\numberline {3.5}分散フレームワーク Alice による分散環境の構築}{11}} +\@writefile{lof}{\contentsline {figure}{\numberline {3.3}{\ignorespaces AliceによるJungleの木構造トポロジーの形成}}{11}} +\newlabel{fig:topologymanager}{{3.3}{11}} +\@writefile{lof}{\contentsline {figure}{\numberline {3.4}{\ignorespaces トポロジーの形成}}{12}} +\newlabel{fig:LogupdateTree}{{3.4}{12}} +\@writefile{toc}{\contentsline {section}{\numberline {3.6}測定用プログラムの実装}{13}} +\newlabel{Logupdate}{{3.2}{13}} +\@writefile{lol}{\contentsline {lstlisting}{\numberline {3.2}測定用プログラムの起動部分}{13}} +\@writefile{toc}{\contentsline {chapter}{\numberline {第4章}性能評価}{15}} \@writefile{lof}{\addvspace {10\p@ }} \@writefile{lot}{\addvspace {10\p@ }} -\@writefile{toc}{\contentsline {section}{\numberline {4.1}java版jungleとhuskell版jungleの比較}{14}} -\@writefile{toc}{\contentsline {section}{\numberline {4.2}java版jungleの分散性能の評価}{14}} -\@writefile{toc}{\contentsline {section}{\numberline {4.3}性能測定方法の評価}{14}} -\@writefile{toc}{\contentsline {chapter}{\numberline {第5章}結論}{15}} +\@writefile{toc}{\contentsline {section}{\numberline {4.1}java版jungleの分散性能の評価}{15}} +\@writefile{toc}{\contentsline {section}{\numberline {4.2}性能測定方法の評価}{15}} +\@writefile{toc}{\contentsline {chapter}{\numberline {第5章}結論}{16}} \@writefile{lof}{\addvspace {10\p@ }} \@writefile{lot}{\addvspace {10\p@ }} -\@writefile{toc}{\contentsline {section}{\numberline {5.1}まとめ}{15}} -\@writefile{toc}{\contentsline {section}{\numberline {5.2}今後の課題}{15}} +\@writefile{toc}{\contentsline {section}{\numberline {5.1}まとめ}{16}} +\@writefile{toc}{\contentsline {section}{\numberline {5.2}今後の課題}{16}} \bibcite{1}{1} \bibcite{2}{2} \bibcite{3}{3}
--- a/paper/final_main/main.lof Mon Feb 19 11:34:24 2018 +0900 +++ b/paper/final_main/main.lof Mon Feb 19 14:12:01 2018 +0900 @@ -1,12 +1,12 @@ \addvspace {10\p@ } \addvspace {10\p@ } -\contentsline {figure}{\numberline {2.1}{\ignorespaces ツリー型のトポロジー}}{4} +\contentsline {figure}{\numberline {2.1}{\ignorespaces ツリー型のトポロジー}}{5} \contentsline {figure}{\numberline {2.2}{\ignorespaces ring型のトポロジー}}{5} -\contentsline {figure}{\numberline {2.3}{\ignorespaces メッシュ型のトポロジー}}{5} +\contentsline {figure}{\numberline {2.3}{\ignorespaces メッシュ型のトポロジー}}{6} \addvspace {10\p@ } -\contentsline {figure}{\numberline {3.1}{\ignorespaces 複数のjungleに書き込まれたデータがrootのjungleへ到達する時間を計測する}}{7} -\contentsline {figure}{\numberline {3.2}{\ignorespaces TORQUEの構成}}{9} -\contentsline {figure}{\numberline {3.3}{\ignorespaces AliceによるJungleの木構造トポロジーの形成}}{10} -\contentsline {figure}{\numberline {3.4}{\ignorespaces トポロジーの形成}}{11} +\contentsline {figure}{\numberline {3.1}{\ignorespaces 複数のjungleに書き込まれたデータがrootのjungleへ到達する時間を計測する}}{8} +\contentsline {figure}{\numberline {3.2}{\ignorespaces TORQUEの構成}}{10} +\contentsline {figure}{\numberline {3.3}{\ignorespaces AliceによるJungleの木構造トポロジーの形成}}{11} +\contentsline {figure}{\numberline {3.4}{\ignorespaces トポロジーの形成}}{12} \addvspace {10\p@ } \addvspace {10\p@ }
--- a/paper/final_main/main.log Mon Feb 19 11:34:24 2018 +0900 +++ b/paper/final_main/main.log Mon Feb 19 14:12:01 2018 +0900 @@ -1,4 +1,4 @@ -This is e-pTeX, Version 3.14159265-p3.7.1-161114-2.6 (utf8.euc) (TeX Live 2017) (preloaded format=platex 2018.2.19) 19 FEB 2018 11:34 +This is e-pTeX, Version 3.14159265-p3.7.1-161114-2.6 (utf8.euc) (TeX Live 2017) (preloaded format=platex 2018.2.19) 19 FEB 2018 14:11 entering extended mode restricted \write18 enabled. %&-line parsing enabled. @@ -605,47 +605,47 @@ ]) (./chapter2.tex [2] 第 2 章 -File: pic/tree.pdf Graphic file (type pdf) -<pic/tree.pdf> [3 ] +File: pic/tree.pdf Graphic file (type pdf) +<pic/tree.pdf> File: pic/ring.pdf Graphic file (type pdf) <pic/ring.pdf> File: pic/mesh.pdf Graphic file (type pdf) <pic/mesh.pdf> -) (./chapter3.tex [4] [5] +) (./chapter3.tex [4] [5] [6] 第 3 章 -[6 +[7 ] File: ./pic/gaiyou.pdf Graphic file (type pdf) <./pic/gaiyou.pdf> - [7] + [8] File: ./pic/torque.pdf Graphic file (type pdf) <./pic/torque.pdf> -LaTeX Warning: Reference `src:LogupdateTest.pl' on page 8 undefined on input li +LaTeX Warning: Reference `src:LogupdateTest.pl' on page 9 undefined on input li ne 100. -[8] [9] +[9] [10] File: pic/topologymanager3.pdf Graphic file (type pdf) <pic/topologymanager3.pdf> - [10] + [11] File: pic/LogupdateTree.pdf Graphic file (type pdf) <pic/LogupdateTree.pdf> - [11] (./plsource.txt)) [12] (./chapter4.tex [13] + [12] (./plsource.txt)) [13] (./chapter4.tex [14] 第 4 章 -[14 +[15 ]) (./chapter5.tex 第 5 章 -) (./bibliography.tex [15 +) (./bibliography.tex [16 -]) (./thanks.tex [16 +]) (./thanks.tex [17 -]) [17 +]) [18 ] (./main.aux) @@ -658,10 +658,10 @@ Here is how much of TeX's memory you used: 4043 strings out of 493640 49134 string characters out of 6148698 - 191714 words of memory out of 5000000 + 191716 words of memory out of 5000000 7556 multiletter control sequences out of 15000+600000 16433 words of font info for 66 fonts, out of 8000000 for 9000 929 hyphenation exceptions out of 8191 - 27i,9n,32p,662b,1686s stack positions out of 5000i,500n,10000p,200000b,80000s + 27i,9n,32p,795b,1686s stack positions out of 5000i,500n,10000p,200000b,80000s -Output written on main.dvi (21 pages, 54816 bytes). +Output written on main.dvi (22 pages, 57708 bytes).
--- a/paper/final_main/main.lol Mon Feb 19 11:34:24 2018 +0900 +++ b/paper/final_main/main.lol Mon Feb 19 14:12:01 2018 +0900 @@ -1,2 +1,2 @@ -\contentsline {lstlisting}{\numberline {3.1}本実験で投入するジョブスクリプト}{9} -\contentsline {lstlisting}{\numberline {3.2}測定用プログラムの起動部分}{12} +\contentsline {lstlisting}{\numberline {3.1}本実験で投入するジョブスクリプト}{10} +\contentsline {lstlisting}{\numberline {3.2}測定用プログラムの起動部分}{13}
--- a/paper/final_main/main.toc Mon Feb 19 11:34:24 2018 +0900 +++ b/paper/final_main/main.toc Mon Feb 19 14:12:01 2018 +0900 @@ -4,17 +4,16 @@ \contentsline {chapter}{\numberline {第2章}分散版jungleデータベース}{3} \contentsline {section}{\numberline {2.1}Jungleデータベースの構造}{3} \contentsline {section}{\numberline {2.2}分散機構}{3} -\contentsline {chapter}{\numberline {第3章}評価実験}{6} -\contentsline {section}{\numberline {3.1}実験目的}{6} -\contentsline {section}{\numberline {3.2}実験概要}{7} -\contentsline {section}{\numberline {3.3}実験環境}{8} -\contentsline {section}{\numberline {3.4}TORQUE Resource Manager}{8} -\contentsline {section}{\numberline {3.5}分散フレームワーク Alice による分散環境の構築}{10} -\contentsline {section}{\numberline {3.6}測定用プログラムの実装}{12} -\contentsline {chapter}{\numberline {第4章}性能評価}{14} -\contentsline {section}{\numberline {4.1}java版jungleとhuskell版jungleの比較}{14} -\contentsline {section}{\numberline {4.2}java版jungleの分散性能の評価}{14} -\contentsline {section}{\numberline {4.3}性能測定方法の評価}{14} -\contentsline {chapter}{\numberline {第5章}結論}{15} -\contentsline {section}{\numberline {5.1}まとめ}{15} -\contentsline {section}{\numberline {5.2}今後の課題}{15} +\contentsline {chapter}{\numberline {第3章}評価実験}{7} +\contentsline {section}{\numberline {3.1}実験目的}{7} +\contentsline {section}{\numberline {3.2}実験概要}{8} +\contentsline {section}{\numberline {3.3}実験環境}{9} +\contentsline {section}{\numberline {3.4}TORQUE Resource Manager}{9} +\contentsline {section}{\numberline {3.5}分散フレームワーク Alice による分散環境の構築}{11} +\contentsline {section}{\numberline {3.6}測定用プログラムの実装}{13} +\contentsline {chapter}{\numberline {第4章}性能評価}{15} +\contentsline {section}{\numberline {4.1}java版jungleの分散性能の評価}{15} +\contentsline {section}{\numberline {4.2}性能測定方法の評価}{15} +\contentsline {chapter}{\numberline {第5章}結論}{16} +\contentsline {section}{\numberline {5.1}まとめ}{16} +\contentsline {section}{\numberline {5.2}今後の課題}{16}