# HG changeset patch # User Shinji KONO # Date 1524480625 -32400 # Node ID f55662d3643f322b1b4e3dbe13631ccbf34bd1f9 # Parent 5be85f2a6d0776962e0def681fb313e0c28b791c fix diff -r 5be85f2a6d07 -r f55662d3643f paper/pic/tree.graffle Binary file paper/pic/tree.graffle has changed diff -r 5be85f2a6d07 -r f55662d3643f paper/pic/tree.pdf Binary file paper/pic/tree.pdf has changed diff -r 5be85f2a6d07 -r f55662d3643f paper/sigos.tex --- a/paper/sigos.tex Sat Apr 21 19:07:47 2018 +0900 +++ b/paper/sigos.tex Mon Apr 23 19:50:25 2018 +0900 @@ -140,7 +140,7 @@ Jungle では、木のノードの位置を NodePath クラスを使って表す。 NodePath クラスはルートノードからスタートし、対象のノードまでの経路を数字を用いて指し示す。また、ルートノードは例外として-1と表記される。 NodePath クラスを用いて \textless -1,0,2,3 \textgreater を表している際の例を(図\ref{fig:nodepath})に示す。 \begin{figure}[htpb] \begin{center} - \includegraphics[width=60mm]{./pic/nodepath.pdf} + \includegraphics[width=60mm]{pic/nodepath.pdf} \end{center} \caption{NodePath} \label{fig:nodepath} @@ -162,51 +162,173 @@ 完全にランダムな変更が巨大な木に対して必要な場合には、Jungleの木そのものをRed Black Tree として構築する手法を使うことができる。この場合は木の構造を固定することはできないが、 O(log n)での木の変更が可能になる。これは表構造そのものになる。これにより、Jungle をRDBして使うことも可能になった。Reb Black Jungle Tree 用には専用のNode Pathが提供される。 -\section{分散環境でのJungleDBの書き出し実験方法の提案} -Jungleは分散環境で動くデータベースを目指して開発している。 -Jungleには大量の様々な木が存在し、その大きさも様々である。 -それぞれの木を異なるJungleノードに格納することにより、木が大量になる場合にも一定した性能が出るようにしたい。 -一つの木が極端に大きくなる場合もあるが、それを分散して格納するのは難しい。 -ここでは、一つの木は一つのノードに納まる大きさだと仮定する。 -Jungleの木は信頼性向上とアクセス速度の向上のために、複数のノードに格納される。 -木の変更は複数のノードを伝搬し、特定のJungleの木のルートノードに到達する。 -そこで、木の状態が確定する。 -一つのルートノードではなく、複数のノードに対して、多数決Commitなどの方法を用いることも考えられるが、 -今回は単一のルートノードを用いる。 -この方法は、読み込みに対して書き込みが少ない場合、あるいは書き込みが単一ノードのみからくる場合に有効であると考えられる。(図\ref{fig:WriteTime}) + +\section{Jungleの分散構成} + +Jungle で木構造を分散させるために、Alice による通信を使用する。木への変更をコマンドログとして記録し、それをAliceを用いて他のノードに転送する。 +他のノードはログに従って自分の持っている木を変更する。複数のノードで変更を共有する手法は様々なものが開発されてきているが、現在は以下のような +簡単なものを実装している。 + +まず、ノードを木構造に接続する。変更ログを自ノードに接続されているノードに向かって送信する。受けとったノードは自分の木を変更したのち、 +送られてきたノード以外の自分のノードに接続されているノードに変更ログを転送する(Split Horizon)。この方法では全部のノードに単純に +変更が伝搬する。変更が衝突した場合は、Merge処理を行う。Merge 処理は失敗しないと仮定する。Merge処理による変更は他ノードに転送しない。 +失敗しないMergeは一般的な整合性を保証することはできないが、SNSへの投稿などの場合では十分に機能する。今回は分散実装の確認のために +簡単な方法を実装した。多数決などの複雑な分散機構を載せることも将来的には可能である。 +通信部分はAliceを用いて実装されているので、Jungleの分散構成は Alice のToplogy Manager によって動的あるいは静的に構成される。 + +\begin{figure}[htbp] + \centering + \includegraphics[width=100mm]{pic/tree.pdf} + \caption{ツリー型のトポロジー} + \label{fig:tree} +\end{figure} + +(図\ref{fig:tree}）の矢印の流れを以下に示す。 +\begin{enumerate} + \item servernode 1, servernode 2からきたデータがservernode 0 で衝突。 + \item 衝突したデータのMergeが行われる。 + \item Mergeされたデータがservernode 1,servernode 2へ伝搬 + \item servernode1からMergeされたデータがservernode 3、servernode 4へ伝搬。全体でデータの整合性が取れる。 +\end{enumerate} + + +\section{JungleとAliceの問題点} + +Jungleの分散実装を行う時に、Aliceで分散プログラムを記述させる時の問題点がいくつか明らかになった。 + +まず、Jungle とAlice の機能の重複がある。Alice を採用したのは簡単にJungleの分散構成を実現するためだが、Jungle もAliceも、一種の +データベースであり、キーにより木構造あるいはオブジェクトを格納している。差は扱うデータが木構造かどうかと、トランザクションの取扱いの違いである。 -従来のJungleDBの分散機能の測定はJetty Webサーバー込みで行なっており、DBに対する負荷は直接的には大きくなかった。 -JungleDBに対して十分な負荷をかけるhttpリクエストを生成するのは困難であった。 -そこで、Jungleの分散性能そのものを調べるために、Webサーバー抜きで測定したい。 +Alice はDataSegmentをキーにより通信するが、このキーはプログラムの任意の位置からアクセスすることができる。つまり大域変数的に扱うことが可能である。 +DataSegment へのアクセスはキーを取得したCodeSegmentのみであり、変更はキューに格納され、読み出しはキューに沿って行われる。従って、通常の大域変数 +と違い、並列実行時に不整合が起きることはない。しかし、キーが大域的に見えているので、DataSegmentへのアクセスをモジュール内などに制限することは難しい。 + +現状のJungleの木のノードには属性と値の組があり、DBのレコードとして機能するが、値として使えるのはByteBufferであり型を持っていない。 +Jungle のトランザクションはEitherという方法で実装されており、細かいエラーチェックを行う必要があり煩雑である。 + +Alice のDataSegmentの管理は Singleton で実装されており、同一プロセス上で複数のAliceのインスタンスを立ち上げることができない。これにより +分散アルゴリズムのテストを単一プロセスで行うことができないという問題がある。また、NAT越えの実装を行う時にも複数のプロセスが必要になって +しまう。 + +現状のAlice の記述方法が煩雑で、型の整合性をコンパイル時に指定できない。これに付いては次節でさらに詳しく述べる。 + + +\section{CodeSegmentの記述方法} +CSをユーザーが記述する際にはCodeSegmentクラスを継承して記述する(ソースコード \ref{src:StartCodeSegment} , \ref{src:CodeSegment})。 +継承することによりCode Segmentで使用するData Segment APIを利用する事ができる。 + +Alice には、Start CS (ソースコード \ref{src:StartCodeSegment} )というC の main に相当するような最初に +実行される CS がある。 +Start CSはどのDSにも依存しない。つまりInput DSを持たない。 +このCSをmainメソッド内でnewし、executeメソッドを呼ぶことで実行を開始させることができる。 + + +\lstinputlisting[label=src:StartCodeSegment, caption=StartCodeSegmentの例]{source/StartCodeSegment.java} +\lstinputlisting[label=src:CodeSegment, caption=CodeSegmentの例]{source/TestCodeSegment.java} + +\newpage + +ソースコード \ref{src:StartCodeSegment} は、5行目で次に実行させたいCS(ソースコード \ref{src:CodeSegment} )を作成している。 +8行目でOutput DS APIを通してLocal DSMに対してDSをputしている。 +Output DS APIはCSの{\tt ods}というフィールドを用いてアクセスする。 +{\tt ods}は{\tt put}と{\tt update}と{\tt flip}を実行することができる。 +TestCodeSegmentはこの"cnt"というkeyに対して依存関係があり、8行目でputが行われるとTestCodeSegmentは実 +行される。 + + +CSのInput DSは、CSの作成時に指定する必要がある。指定はCommandType(PEEKかTAKE)、DSM名、そしてkey よっ +て行われる。 +Input DS API はCSの{\tt ids}というフィールドを用いてアクセスする。 +Output DSは、{\tt ods}が提供するput/update/flipメソッドをそのまま呼べばよかったが、Input DSの場合{\tt ids}にpeek/takeメソッドはなく、create/setKeyメソッド内でCommandTypeを指定して実行する。 -JungleDBの通信は、研究室で開発した分散フレームワークAliceによって行われる。 -Aliceはノードの木構造接続を自動的に行うTopologyManagerを持っている。 -ここでは、Jungleの木それぞれに対してノードの木構造を別々に構成する必要がある。 -これは、TopologyManagerを改良することによって行う。 -Aliceはまた、通信を圧縮して行う機能も持っており、それによる高速化も期待できる。 -通信されるのは、Jungleの木に対する変更Logであり、これをまとめて転送することにより、圧縮がうまく働くと期待される。 -複数のノードの変更は、互いに競合することがあり、ノード間をルートに向かって通信していく間に競合を解消する必要がある。 -これをMergeをいう。 -従来のDBのような変更では、Mergeが失敗することがある。 -失敗した場合は、複数の木構造がまとめて失敗してしまう。 -JungleではMergeが失敗しないような場合、例えば、SNSへのコメントの追加などではうまく働く。 -従来のDBとしてJungleを使う場合には、単一ノードで使用するか、多数決Commitを使うことになるが、ここではそれは測定しない。 +ソースコード\ref{src:CodeSegment}は、0から9までインクリメントする例題である。 +2行目では、Input DS APIがもつcreateメソッドでInput DSを格納する受け皿(Receiver)を作っている。 +引数には{\tt PEEK}または{\tt TAKE}を指定する。 +\begin{itemize} +\item {\ttfamily Receiver create(CommandType type)} +\end{itemize} + +4行目から6行目はコンストラクタである。コンストラクタはオブジェクト指向のプログラミング言語で新たなオ +ブジェクトを生成する際に呼び出されて内容の初期化を行う関数である。 + + TestCodeSegmentのコンストラクタが呼ばれた際には、 + \begin{enumerate} + \item CSが持つフィールド変数 {\tt Receiver input}に{\tt ids.create(CommandType.TAKE)}が行われ、{\tt input}が初期化される。 + \item 5行目にあるTestCodeSegmentのコンストラクタのTAKEが実行される。 + \end{enumerate} + +5行目は、2行目のcreateで作られたReceiverが提供するsetKeyメソッドを用いてLocal DSMからDSを取得している。 +\begin{itemize} +\item \verb+void setKey(String managerKey, String key)+ +\end{itemize} +setKeyメソッドはpeek/takeの実行を行う。どのDSMのどのkeyに対してpeekまたはtakeコマンドを実行させるかを指定できる。コマンドの結果がレスポンスとして届き次第CSは実行される。 + +\newpage + +実行されるrunメソッドの内容は +\begin{enumerate} +\item 10行目で取得されたDSをInteger型に変換してcountに代入する。 +\item 12行目でcountをインクリメントする。 +\item 16行目で次に実行されるCSを作る。run内の処理を終えたらCSは破棄されるため、処理を繰り返したい場合はこのように新しいくCSを作る必要がある。この時点で次のCSはInput DSの待ち状態に入る。 +\item 17行目でcountをLocal DSMにputする。Input DSが揃い待ち状態が解決されたため、次のCSが実行される。 +\item 13行目が終了条件であり、countの値が10になれば終了する。 + \end{enumerate} +となっている。 + +1.で用いられているasInteger()はasClassメソッドの一部であり、asClassはtake/peekで取得したDSをObject型から任意の型で取得するためのAPIである。 + +\begin{itemize} + \item {\ttfamily T asClass(Class clazz)} +\end{itemize} + +CS内でDSのデータを扱うには、正しい型を意識しながらこのasClassメソッドを使わなければならない。 -今回、実験で分散構造としてJungleの動くノード16台を木構造に接続する。 -この木のルートノードをルートjungleと呼び、末端ノードをリーフjungleと呼ぶ。 - \begin{figure}[htpb] - \begin{center} - \includegraphics[width=80mm]{./pic/WriteTime.pdf} - \end{center} - \caption{複数のルートノードを持つ木構造} - \label{fig:WriteTime} -\end{figure} -まず、末端のJungleにUserが書き込みをし、Jungleからuserにレスポンスが返ってくるまでの時間を測定する。 -次に、Jungleの変更がルートのJungleにコピーされるまでの時間の測定方法を提案する。Jungle同士の接続には、当研究室で開発している分散フレームワークであるAliceを用いる。 -\section{まとめ} -本研究では、始めに破壊的木構造データベースであるJungleについて説明を行い、次にJungleの性能を上げるために実装した点を挙げ、最後に分散環境での Jungle の書き出し実験の手法について述べた。実装した点は、まず Jungle の Index の Update を高速化させるために、前の版の Index と値を共有しながら Update を行う、差分 Update の実装を行なった。次に、線形の木を正順で構築する際、木の変更の手間が O(n) になる問題を解決するために、 Differential Jungle Tree の実装をした。 Differential Jungle Tree は、自身の末尾のノードの情報を保持している。この末尾ノードを使用して、木の編集や検索を行う。次に、自動的に木のバランスを行い、最適な形の木構造を構築する Red Black Jungle Tree を実装した。 Red Black Jungle Tree は、自身が Index を構築する Default Jungle Tree により、編集できる。また、ノードは、木のバランスによって Path が編集ごとに変わってしまうため、属性名と属性値のペアでノードを指定できる、 Red Black Jungle Tree Editor の実装を行なった。 -また、Jungleの分散機能に対する測定手法を提案した。 -今後の課題として、Jungleは非破壊でデータを保持し続けるため、非常に多くのメモリを使用してしまう。ある程度の単位で過去のデータの掃除を行いたい。Jungleは、過去の木に対するアクセスをサポートしているため、データの掃除を行うタイミングが明確ではない。なので、メモリから追い出すタイミングを定義する必要がある。 +このように、InputDSを記述するには、一度フィールドでReceiverをcreateして、その後Reveiverに対してsetKeyで待ち合わせるkeyを指定しなければならない。 +このようにインプットの処理が分離されてしまっていては、記述が煩雑な上にコードを読んだ際にどのkeyに対して待ち合わせを行っているのか直感的に分からない。 + +さらに、setKeyは明確な記述場所が決まっていないため、そのDSを待ち合わせているCS以外からも呼び出せてしまう(ソースコード\ref{src:StartSetKey})。 + + \lstinputlisting[label=src:StartSetKey, caption=setKeyを外部から呼び出す例]{source/StartSetKey.java} + \lstinputlisting[label=src:SetKey, caption=外部setKeyによりどのkeyを待っているかがわからないCSの例]{source/SetKey.java} + +このような書き方をされると、CSだけを見てどのkeyに対して待ち合わせを行っているのかわからないため、setKeyを呼び出しているコードを辿る必要がある。 +これでは見通しが悪いため、どこでkeyを指定するのか明確にすべきである。 + +可読性の低いコードはプログラマの負担となるため、CSが何を待ち合わせているのかそのCSを見ただけで理解できるように記述の分離問題を改善しなくてはならない。 + +setKeyはCSのコンストラクタで指定することが多い。 +このとき、指定するkeyは引数などから動的に受け取り、セットすることができる。 +しかし、それでは実際にどんな処理が行われているのかわかりづらく、また、putする部分などの該当するkeyを扱う全てコードを変更しなければならない。 +このように、AliceではCSを使いまわすことを考慮して動的なsetKeyを可能にしてしまったせいで、慎重に書かなければプログラムの信頼性が保てないようになってしまっている。 +そのため、動的なsetKeyはできないように制限し、コードの見通しを良くする必要がある。 +CSに対してインプットとなるkeyが静的に決まれば、待ち合わせているkeyに対してのputのし忘れなどの問題をコンパイル時のモデル検査などで発見することができると考えられる。 + +inputDSを受け取るReceiverはデータをObject型で持っており、そのデータをCS内で扱うには正しい型にキャストする必要がある。 +しかし、inputDSで指定するのはkeyのみであり、そのデータの型までは分からない。 +そのため、DSの型を知るにはputしている部分まで辿る必要がある。 +辿ってもflipされている可能性もあるため、最初にそのDSをputしている部分を見つけるのは困難である。 +従って、待ち合わせているkeyにどのような型のデータが対応しているのかをそのCSを見ただけで分かるようにするべきと考える。 + +key名とそのkeyで待ち合わせたDSを受け取るReceiver名は異なることがある。 +もしプログラマが適当に命名してしまえば後々混乱を招くため、待ち合わせるkey名とinput DS の変数名一致を強制させたい。 + +\section{分散フレームワークChristieの設計} + +以上の問題を踏まえ、新しい分散フレームワークChristieの設計とプロトタイプの実装を行った。 +Christieに必要な要件は以下のように考える。 + +\begin{itemize} +\item {\ttfamily create/setKeyのような煩雑なAPIをシンプルにし可読性を向上させる} +\item {\ttfamily 並列分散環境下での型の整合性を保証する構文と仕組みを提供する} +\item {\ttfamily 一つのプロセス内で複数のインスタンスを同時に立ち上げられる} +\item {\ttfamily 木構造などのデータ構造をネットワーク上でやりとりできる} +\item {\ttfamily 通信に用いるキーの階層的管理を提供する} +\item {\ttfamily これらの仕組みを実現するメタ計算機構を提供する} +\end{itemize} + + + + %参考文献　 diff -r 5be85f2a6d07 -r f55662d3643f paper/source/SetKey.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/source/SetKey.java Mon Apr 23 19:50:25 2018 +0900 @@ -0,0 +1,8 @@ +public class TestCodeSegment extends CodeSegment { + private Receiver input = ids.create(CommandType.TAKE); + + @Override + public void run(){ + System.out.println("data = " + input.asInteger()); + } +} diff -r 5be85f2a6d07 -r f55662d3643f paper/source/StartCodeSegment.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/source/StartCodeSegment.java Mon Apr 23 19:50:25 2018 +0900 @@ -0,0 +1,11 @@ +public class StartCodeSegment extends CodeSegment { + + @Override + public void run() { + new TestCodeSegment(); + + int count = 0; + ods.put("local", "cnt", count); + } + +} diff -r 5be85f2a6d07 -r f55662d3643f paper/source/StartSetKey.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/source/StartSetKey.java Mon Apr 23 19:50:25 2018 +0900 @@ -0,0 +1,8 @@ +public class StartCodeSegment extends CodeSegment { + @Override + public void run() { + TestCodeSegment cs = new TestCodeSegment(); + cs.input.setKey("data"); + ods.put("local", "data", 1); + } +} diff -r 5be85f2a6d07 -r f55662d3643f paper/source/TestCodeSegment.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/source/TestCodeSegment.java Mon Apr 23 19:50:25 2018 +0900 @@ -0,0 +1,19 @@ +public class TestCodeSegment extends CodeSegment { + private Receiver input1 = ids.create(CommandType.TAKE); + + public TestCodeSegment() { + input1.setKey("local", "cnt"); + } + + @Override + public void run() { + int count = input1.asInteger(); + System.out.println("data = " + count); + count++; + if (count == 10){ + System.exit(0); + } + new TestCodeSegment(); + ods.put("local", "cnt", count); + } +}