Mercurial > hg > Papers > 2013 > toma-jssst

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Slides/jssst.html	Thu Sep 12 02:11:52 2013 +0900
@@ -0,0 +1,255 @@
+<!DOCTYPE html>
+
+<!--
+  Google HTML5 slide template
+
+  Authors: Luke Mahé (code)
+           Marcin Wichary (code and design)
+
+           Dominic Mazzoni (browser compatibility)
+           Charles Chen (ChromeVox support)
+
+  URL: http://code.google.com/p/html5slides/
+-->
+
+<html>
+	<head>
+		<title>
+      Haskellによる非破壊的木構造を用いたCMSの実装
+    </title>
+
+		<meta charset='utf-8'>
+		<script
+			src='http://web.amothic.com/html5slides/slides.js'></script>
+	</head>
+
+	<style>
+		/* Your individual styles here, or just use inline styles if that’s
+		what you want. */
+
+
+	</style>
+
+	<body style='display: none'>
+
+		<section class='slides layout-regular template-concurrency'>
+
+			<!-- Your slides (<article>s) go here. Delete or comment out the
+				slides below. -->
+
+			<article>
+				<h1>
+					Haskellによる非破壊的木構造を用いたCMSの実装
+				</h1>
+				<p>
+					Daichi TOMA
+					<br>
+					Sep 13, 2013
+				</p>
+			</article>
+
+			<article>
+				<h3>
+          はじめに
+				</h3>
+        <p>
+        本研究室では非破壊的木構造データベース Jungle の開発を行っている。
+        非破壊的木構造は、通常の木構造と違い、木構造自体を破壊せずに編集を行うことが可能である。
+        </p>
+        <p>
+        Jungle には、既に Java による実装があるが、本研究ではHaskellによる再実装を行った。
+        その結果、Java 版と同程度の性能を得ることができた。また、Java 版の実装と比較し、開発期間及びコード行数の短縮ができた。
+        </p>
+			</article>
+
+			<article>
+				<h3>
+          非破壊的木構造データベース Jungle
+				</h3>
+        <p>
+        非破壊的木構造を取り扱うデータベースである。
+        既に Java による実装が存在する。
+        </p>
+
+        <p>
+        特徴を以下に示す。
+        <ul>
+          <li>複数の非破壊的木構造を扱える
+          <li>編集者は、提供されるAPIを利用して編集を行う
+        </ul>
+        </p>
+			</article>
+
+			<article>
+				<h3>
+          破壊的木構造
+				</h3>
+        <ul>
+          <li>木構造で保持するデータを直接書き換える
+          <li>編集および参照する際にロックを行う必要がある
+        </ul>
+        <p>
+        ロックを行わなければ、参照中に他の編集者が編集してしまうと、整合性がなくなってしまう。
+        </p>
+          図を入れる。見やすいように線とか太くする。
+			</article>
+
+			<article>
+				<h3>
+          非破壊的木構造
+				</h3>
+        <ul>
+          <li>元の木構造を書き換えることなく、編集を行う
+          <li>ルートノードの更新以外にロックは必要ない
+        </ul>
+        <p>
+        参照中に他の編集者が編集してしまっても、整合性がなくなることはない。
+        </p>
+          図を入れる。見やすいように線とか太くする。
+			</article>
+
+			<article>
+				<h3>
+          非破壊的木構造の特徴
+				</h3>
+        <p>
+        非破壊的木構造は、破壊的木構造と異なり以下の利点がある。
+        </p>
+        <ul>
+          <li>一度作成された木構造は破壊されることがない
+          <li>破壊されることがないため、自由にコピーを行っても構わない
+          <li>自由にコピーを行なっても構わないのでロックを必要としない
+        </ul>
+        <p>
+        ロックを必要とせず、自由にコピーを行えるため、スケーラブルなシステムに有用である。
+        </p>
+			</article>
+
+			<article>
+				<h3>
+          Haskell
+				</h3>
+        <p>
+        Haskell は、純粋関数型プログラミング言語である。
+        変数への代入は一度のみで、書き換えることはできない。
+        </p>
+        <p>
+        非破壊的木構造は変数への代入が発生しないことから、関数型言語と相性が良いと考えられる。
+        そのため、Haskell を用いて再実装を行った。
+        </p>
+			</article>
+      <!--
+        Jungleの実装について
+          STMとか
+        実装にかかった時間、コード行数
+      -->
+
+			<article>
+				<h3>
+          性能評価
+				</h3>
+        <p>
+          非破壊的木構造データベース Jungle を用いて簡易掲示板システムを作成し、既存の Java 版との性能比較を行った。
+        </p>
+        <p>
+          Haskell 版 Jungle の HTTP サーバには、Haskell によって書かれた Warp を用いた。
+        </p>
+        <p>
+          Java 版 Jungle の HTTP サーバには、Jetty を用いた。
+        </p>
+			</article>
+
+			<article>
+				<h3>
+          実験方法
+				</h3>
+        <ul>
+          <li>複数のクラスタを利用して、サーバに対して並列にアクセスを5000回行い、それぞれクラスタの実行平均時間をとる
+          <li>クラスタの台数を増やすことにより負荷を上昇させる
+          <li>測定するのは書き込みと読み込みであり、 掲示板のメッセージの取得と掲示板のメッセージの編集を行う
+        </ul>
+			</article>
+
+			<article>
+				<h3>
+          実験環境
+				</h3>
+        xeon使ったよーとか
+			</article>
+
+			<article>
+				<h3>
+          実験結果
+				</h3>
+        ほぼ同じぐらい
+			</article>
+
+			<article>
+				<h3>
+          並列実行
+				</h3>
+        <ul>
+          <li>Haskell 版 Jungle では、並列実行に問題を抱えている
+          <li>複数のスレッドが立ち上がり、並列実行していることは確認したが、シングルコアで実行した場合と比較して実行結果が遅くなる
+        </ul>
+			</article>
+
+			<article>
+				<h3>
+          並列実行
+				</h3>
+          <img src="images/para.png", width="400px">
+        <ul>
+          <li>本研究とは別に、簡単な例題を並列で動かした場合でも期待する実行速度の向上は得られなかった。並列処理で速度向上を達成することは今後の課題である
+        </ul>
+			</article>
+
+			<article>
+				<h3>
+          遅延評価
+				</h3>
+        <ul>
+          <li>Haskell は遅延評価を行うが、書き込みの際に問題が生じる
+          <li>何かしらの結果を表示するまで、簡約可能な式の状態で積まれたままとなる
+          <li>その際メモリを消費し、効率のよい領域に入りきらないサイズになると非常に実行結果が遅くなる
+        </ul>
+          <img src="images/delay_memory.png", width="400px">
+			</article>
+
+			<article class="smaller">
+				<h3>
+          遅延評価
+				</h3>
+          <img src="images/delay.png", width="400px">
+        <ul>
+          <li>評価を行ったあとに実行時間がどのように変わるかを示すために、実験方法を変更した。クラスタ台数を変更する際に10台増やすごとに一度読み込みを挟むようにした。書き込みを繰り返すと実行時間が悪化し、読み込み後、急激に実行時間が下がる。
+          <li>読み込みの際には、数万回以上の書き込みを処理するため数秒から数十秒かかる
+          <li>書き込みは、インクリメントしている値を書き込んでいるが順序などは正しく処理できている
+          <li>この問題を解決するために、全て遅延評価するのではなく、適切な箇所で即時評価を行うことで領域効率を改善する必要がある
+        </ul>
+			</article>
+
+			<article>
+				<h3>
+          まとめ
+				</h3>
+        <ul>
+          <li>Haskell による非破壊的木構造を用いた CMS の実装を行った。
+          <li>木構造データベース Jungle と、HTTP サーバ Warp を用いて、簡易掲示板システムを開発し、既存の Java の実装と同程度の性能を達成できた
+          <li>Java の実装と比較して開発期間およびコード行数は非常に短くなった。
+        </ul>
+			</article>
+
+			<article>
+				<h3>
+          今後の課題
+				</h3>
+        <ul>
+          <li>マルチスレッドで実行した際の実行速度の向上
+          <li>書き込みの際に、遅延評価のためにメモリを多く使用する問題がある。いくつかの式を即時評価するように変更し、領域効率の改善を計る。
+          <li>木構造を永続化する仕組みの実装
+          <li>分散環境でJungleを効率よく利用するために、木構造をマージする仕組みを実装
+        </ul>
+			</article>
+	</body>
+</html>