Mercurial > hg > Papers > 2013 > toma-jssst
annotate Paper/jssst.tex @ 11:d968105de038
change some expression
| author | Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Fri, 19 Jul 2013 05:17:41 +0900 |
| parents | 70a3ea154c0b |
| children | 1b51599130cb |
| rev | line source |
|---|---|
| 0 | 1 % Sample file for the use of compsoft style file. |
| 2 % | |
| 3 \documentclass[T]{compsoft} | |
| 4 | |
| 5 % Preamble | |
| 6 % | |
| 7 % 「コンピュータソフトウェア」誌に掲載される論文の場合，次で | |
| 8 % 巻数，号数，開始ページ，終了ページを指定する． | |
| 9 %\volNoPp{16}{5}{78}{83} | |
| 10 | |
| 11 % ワークショップによる推薦論文の場合，ワークショップ名を指定する． | |
| 12 % \suisen{ワークショップ名} | |
| 13 | |
| 14 % 特集の場合，特集のタイトルを与える． | |
| 15 % \tokushu{特集のタイトル} | |
| 16 | |
| 17 % 大会論文の場合，\taikai で開催年を指定する．ここで指定した年から | |
| 18 % 大会の回数は計算される． | |
| 19 \taikai{2013} | |
| 20 | |
|
7
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
21 \pagestyle {empty} |
|
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
22 |
| 0 | 23 % ここに，使用するパッケージを列挙する． |
| 24 \usepackage[dvipdfmx]{graphicx} | |
|
3
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
25 \usepackage{url} |
|
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
26 \usepackage{listings,jlisting} |
| 0 | 27 |
|
3
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
28 \lstset{ |
|
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
29 language=Haskell,%プログラミング言語によって変える。 |
| 9 | 30 basicstyle={\ttfamily\footnotesize}, |
|
3
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
31 tabsize=2, |
|
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
32 frame=single, |
|
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
33 breaklines=true,%折り返し |
|
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
34 captionpos=b |
|
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
35 } |
| 0 | 36 % ユーザが定義したマクロなどはここに置く．ただし学会誌のスタイルの |
| 37 % 再定義は原則として避けること． | |
| 38 | |
| 39 \begin{document} | |
| 40 | |
| 41 % 論文のタイトル | |
| 42 \title{Haskellによる非破壊的木構造を用いたCMSの実装} | |
| 43 | |
| 44 % 著者 | |
| 45 % 和文論文の場合，姓と名の間には半角スペースを入れ， | |
| 46 % 複数の著者の間は全角スペースで区切る | |
| 47 % | |
| 48 \author{當眞 大千 \and 河野 真治 | |
| 49 % | |
| 50 % ここにタイトル英訳 (英文の場合は和訳) を書く． | |
| 51 % | |
|
7
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
52 \ejtitle{Implementation of the CMS using Nondestructive Tree Structure and Haskell} |
| 0 | 53 % |
| 54 % ここに著者英文表記 (英文の場合は和文表記) および | |
| 55 % 所属 (和文および英文) を書く． | |
| 56 % 複数著者の所属はまとめてよい． | |
| 57 % | |
|
1
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
58 \shozoku{Daichi TOMA, Shinij KONO}{琉球大学大学院理工学研究科情報工学専攻並列信頼研究室}% |
| 0 | 59 {Dept.Concurrency Reliance Laboratory, Information Engineering Course, Faculty of Engineering Graduate School of Engineering and Science, University of the Ryukyus} |
| 60 % | |
| 61 % 出典情報は \shutten とすれば出力される． | |
| 62 %\shutten | |
| 63 % | |
| 64 % 受付年月日，記事カテゴリなどは自動的に生成される． | |
| 65 %\uketsuke{1999}{8}{3} | |
| 66 % | |
| 67 % その他，脚注に入れるものがあれば，\note に記述する． | |
| 68 %\note{脚注に入れる内容} | |
| 69 } | |
| 70 | |
| 71 % | |
| 72 % 和文アブストラクト | |
| 73 \Jabstract{% | |
| 74 ウェブサービスではユーザの増加に対応し、容易に拡張できるスケーラビリティが求められる。 | |
| 2 | 75 コンテンツマネージメントシステムにおいてスケーラビリティを実現するためには、並列にデータへアクセスできる設計が必要となる。 |
|
1
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
76 本研究では、編集元の木構造を破壊することなく編集できる非破壊的木構造を利用する。 |
|
7
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
77 非破壊的木構造では、少ない排他制御で変更を行えるためスケーラビリティを確保できる。 |
|
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
78 コンテンツマネージメントシステムの実装にはプログラミング言語 Haskell を用いた。 |
| 9 | 79 Haskell で書かれた HTTP サーバ Warp を用いて簡易掲示板システムを開発し、既存の Java の実装と比較して短い開発期間やコード行数で、同程度の性能を達成できた。 |
| 0 | 80 } |
| 81 | |
| 82 % | |
| 83 % 英文アブストラクト（大会論文には必要なし) | |
| 84 % \Eabstract{} | |
| 85 % | |
| 86 \maketitle | |
|
7
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
87 \thispagestyle {empty} |
| 0 | 88 |
| 89 \section{はじめに} | |
| 2 | 90 ブロードバンド環境やモバイル端末の普及により、ウェブサービスの利用者数は急激に伸びている。 |
| 91 リクエスト数の増加を予想することは困難であり、負荷が増大した場合に容易に拡張できるスケーラビリティが求められる。 | |
| 92 ここでいうスケーラビリティとは、利用者や負荷の増大に対し、単なるリソースの追加のみでサービスの質を維持することができる性質のことである。 | |
| 93 コンテンツマネージメントシステムにおいてスケーラビリティを実現するためには、並列にデータへアクセスできる設計が必要となる。 | |
| 94 本研究では、編集元の木構造を破壊することなく編集できる非破壊的木構造を利用する。 | |
| 95 非破壊的木構造では、排他制御を行わずに変更を行えるためスケーラビリティを確保できる。 | |
| 0 | 96 |
|
7
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
97 コンテンツマネージメントシステムの実装には、プログラミング言語 Haskell を用いた。 |
| 2 | 98 Haskell は 純粋関数型プログラミング言語である。 |
|
7
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
99 純粋であるため、一度定義した変数の書き換えは許されていない。 |
|
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
100 また、生産性が高いことも特徴で、本システムの実装においても開発期間およびコード行数は非常に短くなった。 |
| 2 | 101 |
|
7
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
102 Haskellで書かれたHTTPサーバ Warp を用いて簡易掲示板システムを開発し、既存のJavaの実装と同程度の性能を達成できた。 |
| 2 | 103 |
| 104 \section{Haskell} | |
|
3
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
105 Haskell は、純粋関数型プログラミング言語である。 |
|
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
106 関数型プログラミング言語では、引数に関数を作用させていくことで計算を行う。 |
|
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
107 変数への代入は一度のみで、書き換えることはできない。 |
|
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
108 遅延評価や、強い静的型付けも Haskell の特徴である。 |
|
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
109 |
|
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
110 \section{Warp} |
|
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
111 Warp\cite{warp} は、軽量、高速な HTTP サーバである。 |
|
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
112 Haskell の軽量スレッドを活かして書かれている。 |
|
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
113 Haskell の ウェブフレームワーク である Yesod のバックエンドとして用いられており、現在も開発が続けられている。 |
|
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
114 |
| 5 | 115 \subsection{Warp を用いたウェブアプリケーションの構築} |
| 116 Warp を用いてウェブアプリケーションを構築する方法について考察する。 | |
|
3
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
117 % Source Codeは実行可能な状態でsrcに置いてある |
|
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
118 % firstline, lastlineで、どの範囲を表示するか指定できる |
| 5 | 119 \lstinputlisting[label=warp_sample, caption=Warpを用いたウェブアプリケーションの例, firstline=9]{src/warp.hs} |
|
3
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
120 |
| 5 | 121 ソースコード \ref{warp_sample}は、URLによって出力する結果を変更するウェブアプリケーションである。 |
|
3
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
122 /hello/worldへアクセスがあった場合は、インクリメントされる counter が表示される。 |
|
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
123 |
|
7
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
124 \paragraph*{main 関数} |
|
3
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
125 HTTP サーバを起動するには、Warp の run 関数を利用する。 |
|
7
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
126 run 関数は、利用する Port 番号と、application というリクエストを受けて何かしらのレスポンスを返す関数の2つを引数として受け取る。 |
|
3
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
127 |
|
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
128 関数型言語では、関数を第一級オブジェクトとして扱える。 |
|
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
129 また、今回は Haskell のカリー化された関数の特性を利用し、main 内で作成した IORef 型の counter を部分適用させている。 |
|
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
130 |
|
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
131 IORef を用いることで、Haskell で更新可能な変数を扱うことができる。 |
|
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
132 参照透過性を失うようにみえるが、Haskell は IO モナドを利用することで純粋性を保っている。 |
|
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
133 IORef 自体が入出力を行うわけではなく、単なる入出力操作の指示にすぎない。 |
|
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
134 IO モナドとして糊付けされた単一のアクションに main という名前を付けて実行することで処理系が入出力処理を行う。 |
|
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
135 |
|
7
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
136 \paragraph*{application 及び routes , findRoute 関数} |
|
3
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
137 application の実装では、routes という関数を独自に定義して、URL によって出力を変更している。 |
|
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
138 application に渡されるリクエストはデータ型で様々な情報が含まれている。 |
|
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
139 その中のひとつに pathInfo という、URL から hostname/port と、クエリを取り除いたリストがある。 |
|
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
140 この情報を routes という関数に渡すことで、routeSetting というリストから一致する URL がないか調べる。 |
|
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
141 routeSetting は、URL のリストとレスポンスを返す関数のタプルのリストである。 |
|
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
142 |
|
7
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
143 \paragraph*{notFound 及び hello 関数} |
|
3
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
144 レスポンスを返す関数は、いくつか定義されている。 |
|
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
145 その中で利用されている responseLBS は文字列からレスポンスを構築するためのコンストラクタである。 |
|
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
146 |
|
7
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
147 \paragraph*{world 関数} |
|
3
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
148 world は、インクリメントされる counter を表示するための関数である。 |
|
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
149 IORef 内のデータは直接触ることができないため、atomicModifyIORef を利用してデータの更新を行なっている。 |
|
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
150 atomicModifyIORef は、データの更新をスレッドセーフに行うことができる。 |
|
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
151 |
|
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
152 実際にプログラムを例にして説明したが、Warp は容易にプログラムに組み込むことができる。 |
|
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
153 我々のシステムでは Warp を用いて開発を行う。 |
|
1
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
154 |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
155 \section{コンテンツマネージメントシステムの設計} |
|
4
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
156 コンテンツマネージメントシステムのデータ構造としては木構造を用いる。 |
|
11
d968105de038
change some expression
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
157 我々は、スケーラビリティのある CMS の実現のために非破壊的木構造\cite{shoshi:2011a}を提案する。 |
|
1
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
158 非破壊的木構造とは、編集元の木構造を破壊することなく新しい木構造を構成することで木構造を編集する方法である。 |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
159 |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
160 破壊的木構造と異なりロックせずに並列に読むことができるため、自由にコピーを作成することが可能である。 |
|
7
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
161 コピーを複数作成し、アクセスを分散させることで性能を維持することができる。 |
|
1
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
162 |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
163 通常の破壊的木構造との違いを説明する。 |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
164 |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
165 \subsection{破壊的木構造} |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
166 破壊的木構造は、木構造を編集する際に木構造を置き換えることにより編集を実現する。 |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
167 図\ref{fig:destructive_tree_modification}では, ノード6をノードAへ書き換える処理を行なっている. |
| 0 | 168 |
|
1
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
169 \begin{figure}[!htbp] |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
170 \begin{center} |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
171 \includegraphics[width=70mm]{./images/destructive_tree_modification.pdf} |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
172 \end{center} |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
173 \caption{木構造の破壊的編集} |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
174 \label{fig:destructive_tree_modification} |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
175 \end{figure} |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
176 |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
177 この方法では、並列環境において問題が発生する。ある時点の木構造を参照する閲覧者と編集する編集者を考える。 |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
178 閲覧者が木構造を参照中に編集者が木構造を書き換えると、閲覧者が参照を開始した時点の木構造ではなく整合性は崩れている。 |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
179 整合性が崩れた状態では正しい状態のコンテンツを参照することはできない(図\ref{fig:destructive_tree_modification_in_lace})。 |
| 0 | 180 |
|
1
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
181 \begin{figure}[!htbp] |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
182 \begin{center} |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
183 \includegraphics[width=70mm]{./images/destructive_tree_modification_in_lace.pdf} |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
184 \end{center} |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
185 \caption{競合状態に陥る木構造の破壊的編集} |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
186 \label{fig:destructive_tree_modification_in_lace} |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
187 \end{figure} |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
188 |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
189 この状態を回避するためには、木構造にアクセスする際は木構造をロックする。 |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
190 しかし、ロックするということは排他処理を行い、木構造を利用している処理がひとつであることを保証するものであるため、並列度を下げることになる。 |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
191 結果、スケーラビリティを損なってしまうため、本システムに破壊的木構造は向かないことが分かる。 |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
192 |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
193 \subsection{非破壊的木構造} |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
194 非破壊的木構造は、木構造を書き換えることなく編集を行うため、読み書きを並列に行うことが可能である。 |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
195 図\ref{fig:nondestructive_tree_modification}では、図\ref{fig:destructive_tree_modification}同様に、ノード 6 をノード A へ書き換える処理を行なっている。 |
| 0 | 196 |
|
1
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
197 \begin{figure}[!htbp] |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
198 \begin{center} |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
199 \includegraphics[width=70mm]{./images/nondestructive_tree_modification.pdf} |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
200 \end{center} |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
201 \caption{木構造の非破壊的編集} |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
202 \label{fig:nondestructive_tree_modification} |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
203 \end{figure} |
| 0 | 204 |
|
1
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
205 非破壊的木構造の基本的な戦略は、変更したいノードへのルートノードからのパスを全てコピーする。 |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
206 そして、パス上に存在しない (編集に関係のない) ノードはコピー元の木構造と共有することである。 |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
207 |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
208 編集は以下の手順で行われる。 |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
209 |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
210 \begin{enumerate} |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
211 \item{変更したいノードまでのパスを求める。} |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
212 \item{変更したいノードをコピーし、コピーしたノードの内容を変更する。} |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
213 \item{求めたパス上に存在するノードをルートノードに向かって、コピーする。 コピーしたノードに一つ前にコピーしたノードを子供として追加する。} |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
214 \item{影響のないノードをコピー元の木構造と共有する。} |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
215 \end{enumerate} |
| 0 | 216 |
|
1
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
217 この編集方法で破壊的木構造の場合と同様に、ある時点の木構造を参照する閲覧者と編集する編集者を考える。 |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
218 閲覧者が木構造を参照している中、編集者が非破壊的な編集を行う。 |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
219 しかし、破壊的な方法とは異なり、元の木構造は破壊されることはないため編集後も整合性は崩れることはない(図\ref{fig:nondestructive_tree_modification_in_lace})。 |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
220 ロックをせずに並列に読み書きが可能であるため、スケーラブルなシステムに有用であると考えられる。 |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
221 元の木構造は破壊されることがないため、自由にコピーを作成しても構わない。したがってアクセスの負荷の分散も可能である。 |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
222 |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
223 \begin{figure}[!htbp] |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
224 \begin{center} |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
225 \includegraphics[width=70mm]{./images/nondestructive_tree_modification_in_lace.pdf} |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
226 \end{center} |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
227 \caption{並列に読み書きが可能な非破壊的木構造} |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
228 \label{fig:nondestructive_tree_modification_in_lace} |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
229 \end{figure} |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
230 |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
231 非破壊的木構造を用いて、コンテンツマネージメントシステムの開発を行う。 |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
232 |
|
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
233 \section{コンテンツマネージメントシステムの実装} |
|
4
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
234 コンテンツマネージメントシステムのデータ構造としては木構造を用いると述べた。 |
|
7
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
235 我々が開発している木構造データベース Jungle \cite{shoshi:2011b} について説明する。 |
|
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
236 |
|
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
237 Jungle は、非破壊的木構造を扱う木構造データベースで、既に Java による実装が存在する。 |
|
4
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
238 本研究では、Haskell を用いて実装を行った。 |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
239 コンテンツマネージメントシステムに組み込んで利用しているが、他のシステムに組み込むことも可能である。 |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
240 |
|
7
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
241 \subsection{利用方法} |
|
4
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
242 \paragraph*{木の作成} |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
243 はじめに、データベースオブジェクトと木の作成方法について述べる。 |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
244 Jungle は複数の木を保持することができる。 |
|
11
d968105de038
change some expression
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
245 木には名前がついており、名前を利用して作成・編集・削除を行うことができる。 |
|
4
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
246 |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
247 \begin{lstlisting}[label=new_jung, caption=データベースオブジェクトと木の作成] |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
248 jungle = createJungle |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
249 new_jung = createTree jungle "new_tree" |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
250 \end{lstlisting} |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
251 |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
252 createTree 関数を利用して木構造を作成する。 |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
253 |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
254 \paragraph*{木と木を構成するノード} |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
255 |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
256 データベースオブジェクトを作成し、木構造とルートノードを取得するためには以下のように記述する。 |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
257 |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
258 \begin{lstlisting}[label=get_tree, caption=木とノードの取得] |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
259 tree = getTreeByName new_jung "new_tree" |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
260 node = getRootNode tree |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
261 \end{lstlisting} |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
262 |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
263 getTreeByName 関数で名前を指定することで木構造を取得できる。 |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
264 getRootNode 関数でルートノードを取得できる。 |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
265 |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
266 \paragraph*{木の編集} |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
267 |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
268 addNewChildAt 関数で、ノードに新しい子を追加することができる。 |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
269 また、putAttribute 関数で、ノードが持つ連想リストを編集できる。 |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
270 どのノードを編集するかという情報は、ルートノードからのパスを渡すことで解決する。 |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
271 木を編集したあと、updateTree 関数を用いて既存のJungleに変更を加え新しいJungleを作成する。 |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
272 |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
273 \begin{lstlisting}[label=get_tree, caption=木の編集] |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
274 new_tree = addNewChildAt tree [0,1] 0 |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
275 new_tree2 = putAttribute new_tree [0,1,0] "key" "value" |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
276 new_jungle = updateTree jungle new_tree2 |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
277 \end{lstlisting} |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
278 |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
279 毎回、新しい変数に代入することで記述が少々煩雑になりやすい。 |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
280 State モナドを用いて記述を簡易にしたものもあるが、利用者にどのようなAPIを提供するかは検討中である。 |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
281 |
|
7
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
282 \subsection{実装の詳細} |
|
11
d968105de038
change some expression
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
283 \paragraph*{木の取り扱い} |
|
d968105de038
change some expression
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
284 Jungle の 木 の取り扱いには、Haskell の Map を用いている。 |
|
4
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
285 Mapは、平衡木を使った Haskell の連想リストである。 |
|
11
d968105de038
change some expression
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
286 連想リストを用いて、名前と木を結びつけている。 |
|
4
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
287 |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
288 \paragraph*{データ構造} |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
289 木のデータ構造は、データ型で定義されている。 |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
290 |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
291 \begin{lstlisting}[label=node, caption=データ構造] |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
292 data Node = Empty |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
293 | Node |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
294 { children :: Children |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
295 , attributes :: Attributes |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
296 } deriving (Show) |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
297 \end{lstlisting} |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
298 |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
299 各ノードは、Childrenとしてノードを複数持つことができる。 |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
300 ChildrenおよびAttributesも、Map を用いて定義されている。 |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
301 |
|
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
302 \paragraph*{ルートノードの取り扱い} |
| 8 | 303 非破壊的木構造であっても、どのノードが最新のルートノードなのかという情報が必要である。 |
|
4
77ee89ae45fb
add a description of implementation
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
3
diff
changeset
|
304 スレッドセーフに取り扱う必要があるため、Haskell のソフトウェア・トランザクショナル・メモリを用いて管理している。 |
|
1
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
305 |
|
11
d968105de038
change some expression
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
306 \subsection{開発期間} |
|
d968105de038
change some expression
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
307 関数型プログラミングでは、コードは短く簡潔になり、生産性が向上する。 |
|
d968105de038
change some expression
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
308 |
|
d968105de038
change some expression
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
309 Java 版の Jungle の実装と比較すると、コード行数は約3000行から約150行へ短くなった。 |
|
d968105de038
change some expression
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
310 またJava版の実装には 3 ヶ月程度かかったが、Haskell 版の実装は 2 週間程度しかかからなかった。 |
|
d968105de038
change some expression
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
311 |
|
1
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
312 \section{木構造データベース Jungle を用いた CMS の検証} |
| 5 | 313 木構造データベース Jungle 及び Warp を用いて簡単な掲示板ウェブアプリケーションを作成した。 |
| 314 同様のウェブアプリケーションを、Java による Jungle 実装 及び Cassandra\cite{cassandra} 上でも動かし性能比較を行う。 | |
| 315 Cassandra は、Facebook が自社のために開発した分散 Key-Value ストアデータベースであり、Dynamo\cite{dynamo}とBigTable\cite{bigtable}を合わせた特徴を持っている。 | |
| 316 Java 版では、組み込みウェブサーバである Jetty を利用する。 | |
| 317 | |
| 318 \subsection{実験方法} | |
| 319 複数のクラスタを利用して、サーバに対して並列にアクセスを 5000 回行い、それぞれクラスタの実行平均時間をとる。 | |
| 10 | 320 クラスタ台数を増やすことにより並列度を上昇させ、並列度と実行時間の平均をグラフ化する。 |
| 5 | 321 測定するのは書き込みと読み込みであり、掲示板のメッセージの取得と掲示板のメッセージの編集を行う。 |
| 322 | |
| 323 \subsection{実験環境} | |
| 324 負荷をかける対象であるサーバは、マルチコア環境が生かされているか確認するためにコア数の多いマシンを用いる。 | |
| 325 サーバの仕様を表\ref{tab:server_spec}に示す。 | |
|
1
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
326 |
| 5 | 327 \begin{table}[!htbp] |
| 328 \caption{検証に使用するサーバーの仕様} | |
| 329 \label{tab:server_spec} | |
| 330 \begin{center}\small | |
| 331 \begin{tabular}{|c||c|} \hline | |
| 332 名前 & 概要 \\ \hline \hline | |
| 333 CPU & Intel\textregistered Xeon\textregistered X5650 @2.67GHz * 2 \\ \hline | |
| 334 物理コア数 & 12 \\ \hline | |
| 335 論理コア数 & 24 \\ \hline | |
| 336 Memory & 132GB \\ \hline | |
| 337 OS & Fedora 16 \\ \hline | |
| 338 JavaVM & 1.6.0\_39-b04 \\ \hline | |
| 339 GHC & 7.6.3 \\ \hline | |
| 340 \end{tabular} | |
| 341 \end{center} | |
| 342 \end{table} | |
| 343 | |
| 344 Warp 及び Cassandra, Jetty は表\ref{tab:bulletinboard_components}のバージョンを利用した。 | |
|
3
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
345 |
| 5 | 346 \begin{table}[!htbp] |
| 347 \caption{Warp と Cassandra, Jetty のバージョン} | |
| 348 \label{tab:bulletinboard_components} | |
| 349 \begin{center} | |
| 350 \begin{tabular}{|c||c|} \hline | |
| 351 名前 & バージョン \\ \hline \hline | |
| 352 Warp & 1.3.9 \\ \hline | |
| 353 Cassandra & 1.2.6 \\ \hline | |
| 354 Jetty & 6.1.26 \\ \hline | |
| 355 \end{tabular} | |
| 356 \end{center} | |
| 357 \end{table} | |
| 358 | |
| 359 サーバに並列に負荷をかけるクラスタの仕様を表\ref{tab:cluster_spec_vmware}に示す。 | |
| 360 クラスタは最大で45台使用する。 | |
|
3
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
361 |
| 5 | 362 \begin{table}[!htbp] |
| 363 \caption{検証に利用するクラスタの仕様} | |
| 364 \label{tab:cluster_spec_vmware} | |
| 365 \begin{center}\small | |
| 366 \begin{tabular}{|c||c|} \hline | |
| 367 名前 & 概要 \\ \hline \hline | |
| 368 CPU & Intel\textregistered Xeon\textregistered X5650 @2.67GHz \\ \hline | |
| 369 Memory & 8GB \\ \hline | |
| 370 OS & CentOS 5.6 \\ \hline | |
| 371 HyperVisor & VMWare ESXi \\ \hline | |
| 372 \end{tabular} | |
| 373 \end{center} | |
| 374 \end{table} | |
| 375 | |
| 376 \subsection{実験結果} | |
| 377 読み込みの実験結果を図\ref{fig:read}、書き込みの実験結果を図\ref{fig:write}に示す。 | |
|
3
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
378 |
| 5 | 379 \begin{figure}[!htbp] |
| 380 \begin{center} | |
| 381 \includegraphics[width=70mm]{./images/read.pdf} | |
| 382 \end{center} | |
| 383 \caption{読み込みの実験結果} | |
| 384 \label{fig:read} | |
| 385 \end{figure} | |
| 386 | |
| 387 \begin{figure}[!htbp] | |
| 388 \begin{center} | |
| 389 \includegraphics[width=70mm]{./images/write.pdf} | |
| 390 \end{center} | |
| 391 \caption{書き込みの実験結果} | |
| 392 \label{fig:write} | |
| 393 \end{figure} | |
| 394 | |
| 395 Haskell版およびJava版のJungleは、ほぼ同程度の速度が出ていることが分かる。 | |
| 396 また、Cassandraと比較して、僅かながらJungleが速く処理を終えている。 | |
|
7
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
397 |
|
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
398 \subsection{遅延評価} |
|
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
399 |
|
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
400 Haskell は遅延評価を行うが、書き込みの際に問題が生じる。 |
|
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
401 何かしらの結果を表示するまで、簡約可能な式の状態で積まれたままとなる。 |
|
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
402 その際メモリを消費し、効率のよい領域に入りきらないサイズになると非常に実行結果が遅くなる。 |
|
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
403 図\ref{fig:write}の結果では、オプションで推奨されるヒープ領域のサイズを変更してある。 |
|
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
404 推奨されるヒープ領域のサイズを変更しない場合の実験結果を図\ref{fig:delay}に示す。 |
|
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
405 |
|
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
406 \begin{figure}[!htbp] |
|
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
407 \begin{center} |
|
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
408 \includegraphics[width=70mm]{./images/delay.pdf} |
|
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
409 \end{center} |
|
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
410 \caption{推奨されるヒープ領域のサイズを変更しない場合の実験結果} |
|
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
411 \label{fig:delay} |
|
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
412 \end{figure} |
|
3
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
413 |
|
11
d968105de038
change some expression
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
414 実行時に書き込みだけではなく、一定間隔に一度読み込みを挟むようにした。 |
|
d968105de038
change some expression
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
415 書き込みを繰り返すと実行時間が悪化し、読み込み後、急激に実行時間が下がる。 |
|
d968105de038
change some expression
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
416 読み込みの際には、数万回以上の書き込みを処理するため数秒かかる。 |
|
d968105de038
change some expression
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
417 書き込みは、インクリメントしている値を書き込んでいるが順序などは正しく処理できている。 |
|
7
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
418 |
|
11
d968105de038
change some expression
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
419 この問題を解決するために、全て遅延評価するのではなく適切な箇所で正格評価を行うことで領域効率を改善する必要がある。 |
|
7
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
420 |
|
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
421 \subsection{並列処理} |
|
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
422 |
|
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
423 Haskell 版 Jungle では、並列実行に問題を抱えている。 |
|
11
d968105de038
change some expression
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
424 複数のスレッドが立ち上がり、並列実行していることは確認したが、シングルコアで実行した場合と比較して実行結果が遅くなる。 |
|
7
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
425 図\ref{fig:read}や図\ref{fig:write}の結果では、Haskell版はシングルコアで実行している。 |
|
3
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
426 |
|
7
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
427 並列に動かした場合の実験結果を図\ref{fig:para}に示す。 |
|
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
428 |
|
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
429 \begin{figure}[!htbp] |
|
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
430 \begin{center} |
|
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
431 \includegraphics[width=70mm]{./images/para.pdf} |
|
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
432 \end{center} |
|
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
433 \caption{並列に動かした場合の実験結果} |
|
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
434 \label{fig:para} |
|
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
435 \end{figure} |
|
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
436 |
| 8 | 437 本研究のウェブアプリケーションとは別に、簡単な例題を並列で動かした場合でも実行速度の向上を確認することはできなかった。 |
| 10 | 438 並列処理で速度向上を達成することは今後の課題である。 |
|
7
925bf2208890
add a description of inspection
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
439 |
|
1
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
440 \section{おわりに} |
| 8 | 441 \subsection{本研究のまとめ} |
| 442 本研究では、Haskell による非破壊的木構造を用いた CMS の実装を行った。 | |
| 443 Haskellは生産性が高く、本システムの実装においても開発期間およびコード行数は非常に短くなった。 | |
|
1
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
444 |
| 8 | 445 木構造データベース Jungle と HTTP サーバ Warp を用いて簡易掲示板システムを開発し、既存のJavaの実装と同程度の性能を達成できた。 |
|
3
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
446 |
|
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
447 \subsection{今後の課題} |
| 8 | 448 書き込みの際に、遅延評価のためにメモリを多く使用する問題がある。 |
| 449 いくつかの式の評価を正格に切り替え、領域効率を向上しなければならない。 | |
|
3
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
450 |
| 8 | 451 また、並列処理を行った際に実行速度が向上するよう再設計を行う必要がある。 |
|
3
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
452 |
| 10 | 453 現在の Jungle には木構造を永続化する仕組みが備わっておらず、実装しなければならない。 |
|
3
2a4370ed68bc
add a description of the warp
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
454 |
| 8 | 455 分散環境で Jungle を効率よく利用するために、木構造をマージする仕組みを実装する必要がある。 |
| 456 マージにはお互いの木の情報が必要になる。 | |
| 457 どのようにマージすべきなのかは、ユーザが知っていると考えられるが、データベース間で過度の情報をやり取りを行うと負荷が上昇するおそれがある。 | |
| 458 どの程度の情報が必要であるのか検討しなければならない。 | |
|
1
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
459 \nocite{*} |
| 8 | 460 |
| 0 | 461 \bibliographystyle{junsrt} |
|
1
c53cb5bc27cd
add description for nondestructive tree structure
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
462 \bibliography{jssst} |
| 0 | 463 \end{document} |