Mercurial > hg > Papers > 2014 > nobuyasu-master

--- a/paper/chapter1.tex	Thu Feb 20 19:30:18 2014 +0900
+++ b/paper/chapter1.tex	Tue Mar 04 00:25:04 2014 +0900
@@ -140,8 +140,8 @@

 \subsection{Cassandra}
 Cassandra\cite{cassandra} は2008年7月にFacebookによってオープンソースとして公開された Key-Value なデータベースである.
-AmazonのDynamo\cite{dynamo} という分散Key-Valueデータベースの影響を受けて作られている.
-スキーマレスな NoSQL データベースになる.
+AmazonのDynamo\cite{dynamo}とBigTable\cite{bigtable}を合わせた特徴を持っている.
+Key-Value なため, スキーマレスな NoSQL データベースとなる.

 Cassandraはサーバノードの配置にConsistent hashingアルゴリズムを用いる.
 Consistent hashingによりノードは論理的にリング上に配置される.
--- a/paper/chapter2.tex	Thu Feb 20 19:30:18 2014 +0900
+++ b/paper/chapter2.tex	Tue Mar 04 00:25:04 2014 +0900
@@ -23,7 +23,7 @@
 これではロックによりスケーラビリティが損なわれてしまう.

 \subsection{非破壊的木構造}
-非破壊的木構造は破壊的木構造とは異なり, 一度作成した木を破壊することはない.
+非破壊的木構造\cite{shoshi:2011a}は破壊的木構造とは異なり, 一度作成した木を破壊することはない.
 非破壊的木構造においてデータの編集は, ルートから編集を行うノードまでコピーを
 行い新しく木構造を作成することで行われる.
 図\ref{fig:nondestractive}は非破壊的木構造のデータ編集を示している.
--- a/paper/chapter4.tex	Thu Feb 20 19:30:18 2014 +0900
+++ b/paper/chapter4.tex	Tue Mar 04 00:25:04 2014 +0900
@@ -2,7 +2,7 @@
 　前章では Jungle のアーキテクチャと分散設計について説明した.
 トポロジーの形成と他サーバノードのデータのアクセス方法には Alice を使用する.
 また, Jungle ではデータ編集のログとして TreeOperationLog がある.
-この TreeOperationLog を Alice により他サーバノードへ送ることでデータの分散を行う.
+この TreeOperationLog を Alice により他サーバノードへ送ることでデータの分散を行う\cite{nobuyasu:2013a}.

 本章では Jungle に行った分散実装について述べる.
 まず, Aliceによるトポロジー形成の仕方を述べ, Aliceを利用したプログラミングの方法に
--- a/paper/chapter5.tex	Thu Feb 20 19:30:18 2014 +0900
+++ b/paper/chapter5.tex	Tue Mar 04 00:25:04 2014 +0900
@@ -4,7 +4,7 @@
 性能比較の為に簡易な掲示板プログラムをJungleとCassandra それぞれに作成した.
 複数のノードに繋がっている状態においても性能を測りたいため, 学科が提供する
 VMWareの並列環境を利用する. また, 我々の研究室が利用しているブレードサーバ
-上で動いているKVMもクライアントとして利用する.
+上で動いているKVMもクライアントとして利用する\cite{shoshi:2011b}.
 Jungleは永続性はなく分散だけ実装で測定を行っている.

 \section{実験方法}
--- a/paper/introduciton.tex	Thu Feb 20 19:30:18 2014 +0900
+++ b/paper/introduciton.tex	Tue Mar 04 00:25:04 2014 +0900
@@ -1,10 +1,10 @@
 \chapter{序論}
 \pagenumbering{arabic}
-ITシステムが巨大化していくにつれ, 障害発生事例が社会に与える影響もより大きな物となる.
+　ITシステムが巨大化していくにつれ, 障害発生事例が社会に与える影響もより大きな物となる.
 それに伴い, ITシステムにおけるディペンダビリティへの注目が増している.

 そこで, DEOSプロジェクトはITシステムにおけるディペンダビリティを担保する技術体系をまとめ, 制度化, さらには事業化を目指している.
-DEOSプロジェクトは2006年に独立行政法人科学技術機構(JST)はCRESTプログラムの1つとして始まったプロジェクトである.
+DEOSプロジェクトは2006年に独立行政法人科学技術機構(JST)のCRESTプログラムの1つとして始まったプロジェクトである.
 DEOSプロジェクトは, 変化し続ける目的や環境の中でシステムを適切に対応させ, 継続的にユーザが求めるサービスを提供することができるシステムの構築法を
 開発することを目標としている\cite{deos2013}.
 DEOSプロジェクトではそれらの技術体系を「オープンシステムディペンダビリティ」として定義し, それをDEOSプロセスとしてまとめた(図\ref{fig:deos_proccess}).
@@ -53,13 +53,13 @@
 ウェブサービスに使用されるデータベースの性能をあげる方法としては, このスケールアウトが求められている.

 本研究で扱うスケーラビリティとはこのスケールアウトのことをさす.
-そういう意味では最も使われているデータベースであるRelational Databaseはスケーラビリティを持つのは困難である.
+最も使われているデータベースであるRelational Databaseはマシンを追加して負荷を分散させることが容易ではない, そのためスケーラビリティを持つことが困難である.
 Relational Databaseにはないスケーラビリティを持つデータベースとしてNoSQLと呼ばれるデータベースがある.
 NoSQLデータベースはConsistency hashingやShardingといった方法を使いデータを分散させスケーラビリティを得ている.
-データベースにおいてデータを分散させスケーラビリティを上げることはもはや必須となっている.
+データベースにおいてスケールアウトによりスケーラビリティを上げることはもはや必須となっている.

 本論文では, スケーラビリティのあるデータベースを目指して木構造データベースJungleの提案する.
-すなわち, Jungleに分散と永続性の実装をう.
+すなわち, Jungleに分散と永続性の実装を行う.
 既存の分散データベースであるCassandraとの比較を行うため, 簡易掲示板を作成し並列環境から負荷をかけることで
 性能比較を行った.
--- a/paper/master_paper.bib	Thu Feb 20 19:30:18 2014 +0900
+++ b/paper/master_paper.bib	Tue Mar 04 00:25:04 2014 +0900
@@ -2,22 +2,13 @@
  note = "http://msgpack.org/",
  title = "MessagePack"
 }
-
-@article{shoshi:2013a,
+@article{nobuyasu:2013a,
  author = "大城 信康 and 河野 真治",
  title = "Data Segment の分散データベースへの応用",
  journal = "日本ソフトウェア科学会",
  month = "September",
  year = 2013
 }
-@article{shoshi:2010a,
-	author = "玉城 将士 and 河野 真治",
-	title = "Cassandraを使ったCMSのPCクラスタを使ったスケーラビリティの検証",
-	journal = "日本ソフトウェア科学会",
-	month = "August",
-	year = 2010
-}
-
 @article{shoshi:2011a,
 	author = "玉城 将士 and 河野 真治",
 	title = "Cassandraを使ったスケーラビリティのあるCMSの設計",
@@ -32,7 +23,6 @@
 	month = "August",
 	year = 2011
 }
-
 @article{cassandra,
 	author = "Avinash Lakshman and Prashant Malik.",
 	title = "Cassandra - a decentralized structured storage system",
@@ -57,18 +47,6 @@
 	author = "Giuseppe DeCandia and Deniz Hastorun and Madan Jampani and Gunavardhan Kakulapati and Avinash Lakshman and Alex Pilchin and Swaminathan Sivasubramanian and Peter Vosshall and Werner Vogels",
 	title = "Dynamo: Amazon's Highly Avaliable Key-value Store"
 }
-
-@article{seda:1,
-	author = "Matt Welsh",
-	title = "The Staged Event-Driven Architecture for Highly-Concurrent Server Applications"
-}
-
-@article{seda:2,
-	author = "Matt Welsh, David Culler, Eric Brewer",
-	title = "SEDA : An Architecture for Well-Conditioned , Scalable Internet Services",
-	journal = "SOSP"
-}
-
 @misc{deos2013,
 author = "所 眞理雄",
 title = "{DEOS プロジェクト研究成果集 Dependability Engineering for Open Systems}",
Binary file paper/master_paper.pdf has changed
--- a/poster/master.graffle/data.plist	Thu Feb 20 19:30:18 2014 +0900
+++ b/poster/master.graffle/data.plist	Tue Mar 04 00:25:04 2014 +0900
@@ -8745,7 +8745,7 @@
 	<key>MasterSheets</key>
 	<array/>
 	<key>ModificationDate</key>
-	<string>2014-02-20 10:25:06 +0000</string>
+	<string>2014-02-20 10:31:06 +0000</string>
 	<key>Modifier</key>
 	<string>Oshiro Nobuyasu</string>
 	<key>NotesVisible</key>
@@ -8845,7 +8845,7 @@
 		<key>SidebarWidth</key>
 		<integer>120</integer>
 		<key>VisibleRegion</key>
-		<string>{{333.73494646964195, 1825.3012415216879}, {1692.7711183748986, 1034.9397798462903}}</string>
+		<string>{{0, 0}, {1692.7711183748986, 1034.9397798462903}}</string>
 		<key>Zoom</key>
 		<real>0.82999998331069946</real>
 		<key>ZoomValues</key>
--- a/slides/index.html	Thu Feb 20 19:30:18 2014 +0900
+++ b/slides/index.html	Tue Mar 04 00:25:04 2014 +0900
@@ -1,699 +1,593 @@
-<!DOCTYPE html>
-<html>
-  <head>
-    <meta charset='utf-8'>
-    <title>分散 Database Jungle に関する研究</title>
-    <script src='slides.js'></script>
-    <style media='screen,projection'>
-     /****
-      * Add your styles here.
-      */
-
-   body { font-size: 175%; }
-
-  .step  { color: silver; }  /* or hide next steps e.g. .step { visibility: hidden; } */
-
-  .slide {
-    font-family: 'Open Sans', Arial, sans-serif;
-
-    color: rgb(102, 102, 102);
-    text-shadow: 0 1px 1px rgba(0, 0, 0, .1);
-  }
-
-  .slide h1, .slide h2, .slide h3 {
-    color: rgb(51, 51, 51);
-  }
-
-  .slide pre {
-   font-family: 'Droid Sans Mono', 'Courier New', monospace;
-   font-size: 80%;
-
-  padding: 5px 10px;
-
-  margin-top: 40px;
-  margin-bottom: 40px;
-
-  color: black;
-  background: rgb(240, 240, 240);
-  border: 1px solid rgb(224, 224, 224);
-  box-shadow: inset 0 2px 6px rgba(0, 0, 0, .1);
-  overflow: hidden;
-  }
-
-  .slide code {
-  font-family: 'Droid Sans Mono', 'Courier New', monospace;
-  color: black;
-  }
-
-  .slide h3 {
-         margin-top:-15px;
-   }
-
-    </style>
-  </head>
-  <body>
-
-    <section class='slides'>
-      <!-- Add your slides here. Delete or comment out the slides below. -->
-
-      <article class='cover'>
-        <h1>
-          分散 Database Jungle に関する研究
-          <br>
-
-        </h1>
-        <p>
-         大城 信康
-          <br>
-          Feb 3, 2013
-        </p>
-      </article>
-
-      <article>
-        <h3>
-	    概要
-        </h3>
-	    <p>非破壊的木構造データベースJungleに分散実装を行い掲示板システムに特化したデーターベースを作成し、その評価を行った。</p>
-	    <p>分散データベースCassandraより2倍以上速く、分散環境下においては10倍以上速い結果も確認された。</p>
-	    <br/>
-      </article>
-
-      <article>
-        <h3>
-	    研究の目的と背景
-	</h3>
-	<p>ウェブサービスにとってデータベースは必須であり、ウェブサービスの規模に比例してデータベースへの負荷も高まる。</p>
-	<p>データベースの処理能力の高さはそのままウェブサービスの質に繋がるため、データベースのスケーラビリティの確保は重要である。</p>
-	<p>スケーラビリティ確保の方法としてデータ分散があるが、分散する方法により性能も変わってくる。</p>
-	<p>スケーラビリティのある分散データベースとしてJungleの実装を行う。</p>
-      </article>
-
-
-      <article>
-        <h3>
-	    ウェブサービスにおけるデータベースの重要性
-	</h3>
-	<p>ウェブサービスへの負荷が高まることは、データベースへの負荷が高まることでもある。</p>
-	<p>データベースの性能が低ければ負荷に耐え切れずサービスはダウンする</p>
-	<p style="text-align:center;">
-	    <img src="./images/service_down.png">
-	</p>
-	<p>そのため、データベースにはスケーラビリティが必要</p>
-      </article>
-
-      <article>
-        <h3>
-	    スケーラビリティとは
-	</h3>
-	<p>システムが負荷の増大に対して柔軟に拡張して対応できる性質</p>
-	<p>主に次の2つの方法によりシステムはスケールされる</p>
-	<ul>
-	<li><font color="blue">スケールアップ</font>：<br/>高価な単一マシンによる性能アップ</li>
-	<br/>
-	<li><font color="red">スケールアウト</font>：<br/>汎用的なマシンを複数台用意することで性能アップ</li>
-	</ul>
-	<p>分散システムにおいては<font color="red">スケールアウト</font>によりスケーラビリティを高める</p>
-      </article>
-
-      <article>
-        <h3>
-	    データベースのスケーラビリティ
-	</h3>
-	<p>データベースのスケーラビリティを考えるとき、どういう用途で使用するかを考えるのが重要。</p>
-	<li>例えば、掲示板システムにおいては、書き込みと読み込みが速いことが求められる。</li>
-	<br/>
-	<p>ウェブサービスは、サービスの内容によってスケーラビリティの確保の仕方も変わってくる。</p>
-	<p>本研究で開発しているデータベースはコンテンツマネジメントシステム（CMS）を対象としている。</p>
-	<p style="text-align:center;">
-	    <img style="" src="./images/scalability.png">
-	</p>
-
-      </article>
-
-      <article>
-        <h3>
-	   コンテンツマネジメントシステム(CMS)
-	</h3>
-	<p>Webコンテンツを構成するテキストや画像などのデジタルコンテンツを管理し配信するシステム。</p>
-	<li>例：ブログツール、Wiki</li>
-	<p>分散コンテンツマネジメントシステムに求められること。</p>
-	<li>Webコンテンツを分散して管理</li>
-	<li>スケールアウトするシステム</li>
-	<p>データ全体の整合性に遅延がある、結果整合性でもよい。書き込みや読み込みを優先としたデータベースが必要。</p>
-	<p>そこで、非破壊的木構造データベースJungleの提案を行った。</p>
-      </article>
-
-      <article>
-        <h3>非破壊的木構造データベースJungle</h3>
-	<p>JungleはスケーラビリティのあるCMSの設計を目指して当研究室で開発されているデータベース。</p>
-	<p>データを木構造で、さらに非破壊で保持する。</p>
-	<br/>
-      </article>
-
-      <article>
-        <h3>
-	    非破壊的木構造
-	</h3>
-	<p>非破壊的木構造は一度作成したデータは変更しない</p>
-	<p>新しい木構造を作成することでデータの編集を行う</p>
-	<p style="text-align:center;">
-	    <img style="width:700px;" src="./images/non_destructive_tree_edit2.png">
-	</p>
-	<p></p>
-      </article>
-
-      <article>
-        <h3>
-	    非破壊的木構造の利点
-	</h3>
-	<p>非破壊的木構造は通常の木構造である破壊的木構造に比べ、以下のような利点を持つ</p>
-	<ul>
-	    <li>一度作成したデータは変更されない</li>
-	    <li>データが変更されないため自由にコピーを作ることができる(いつでも読み込みが可能)</li>
-	    <li>ロックがすくない。ロックが必要なのは最新のルートノードを登録するときだけ</li>
-	</ul>
-	<p>ロックが少なく、いつでもコピーが可能なことから、非破壊的木構造はスケーラブルなシステムに有用となる</p>
-      </article>
-
-      <article>
-	  <h3>
-	      Jungleの分散設計
-	  </h3>
-	  <p>ここまでJungleに実装されている非破壊的木構造の利点について述べた。</p>
-	  <p>次に、Jungleにおける分散設計について述べる。</p>
-	  <p>データ分散を行うにあたり、まず考えることはトポロジーの形成と他のノードからデータの伝搬の仕方である。</p>
-	  <p>Jungleはこの問題に対し、ツリートポロジーを形成し、データ編集の際に発生するcommit logを他のノードに流すことで解決する。</p>
-      </article>
-
-      <article>
-        <h3>
-	    Jungleの分散設計：トポロジー形成とログによるデータ分散
-	</h3>
-	<small>
-	<table>
-	    <tr>
-		<th>commit log伝搬によるデータ分散</th>
-	    </tr>
-	    <tr>
-		<td>
-		    <img src="./images/distributed_jungle.png">
-		</td>
-	    </tr>
-	</table>
-	<p>サーバノード同士でツリートポロジーを形成する。データ編集をどのように行ったのかを示すログ commit log を伝搬させデータの分散を行う。</p>
-	</small>
-      </article>
-
-      <article>
-	  <h3>
-	      非破壊的木構造の利点を活かした分散設計
-	  </h3>
-	  <p>Jungleで扱うつもりのデータは結果整合性でもよいCMSを想定していることを始めに説明した。</p>
-	  <p>そこでJungleはMergeを使うことでデータの整合性をとることにした。</p>
-	  <p>Mergeとは、2つ以上の変更を1つの変更にまとめることである。</p>
-	  <p>分散システムにおいては、2つ以上のデータの更新が同じデータに対して行われていた場合、
-	  更新を受け取って新しいデータを作ることを指す。</p>
-	  <p>Mergeは自動で解決出来る場合とそうでない場合がある。</p>
-      </article>
-
-
-      <article>
-        <h3>
-	    Mergeによる更新の衝突を自然に解決
-	</h3>
-	<small>
-	<table style="font-size: 0.7em; width:100%;" >
-	    <tr>
-		<td><p style="margin-top:-5px; margin-bottom:-5px; text-align:center;"><img src="./images/tree_conflict.png"></p></td>
-	    </tr>
-	    <tr>
-		<td><p style="margin-top:-5px; margin-bottom:-5px; text-align:center;"><img src="./images/tree_conflict3.png"></p></td>
-	    </tr>
-	</table>
-	<p style="margin-top:0px;">上の図は通常のデータ更新を示す</p>
-	<p style="margin-top:-20px;">下の図は、同じ木に対して2つのデータの更新があったが編集を無事終えるケースを示す</p>
-	</small>
-      </article>
-
-
-
-      <article>
-        <h3>
-	    Mergeによる更新の衝突が自然に解決できない場合
-	</h3>
-	<table style="font-size: 0.7em; width:100%;" >
-	    <tr>
-		<td><p style="margin-top:-5px; margin-bottom:-5px; text-align:center;"><img src="./images/tree_conflict2.png"></p></td>
-	    </tr>
-	</table>
-	<p>木の同じノードに対してデータの編集が行われた場合、どのような編集結果にすればよいかわからない。</p>
-	<p>どのような木が組まれ、どのようにデータを保存するかはアプリケーション毎に変わってくる。そのため、アプリケーション毎に
-	Mergeアルゴリズムは考えなくてはならない。</p>
-
-      </article>
-
-      <article>
-        <h3>
-	    JungleとMergeの相性
-	</h3>
-	<p>Jungleは非破壊で過去のデータも保持しているため、更新時に過去のデータを参照して自然なMergeを行うことが可能。</p>
-	<p>自然にMergeできない場合においても、アプリケーション毎にMergeアルゴリズムを設計することで対応する。</p>
-	<p>Mergeが自動で行われるようになれば、Jungleで扱う木構造データは編集を自由に行うことができる。</p>
-	<p>木構造データが自由に行えるようになれば、Jungleはデータのリクエストに対して手元のデータを返すことができる。</p>
-	<p>古いデータを編集されたものが更新されても、いずれはMergeにより最新のデータと合わせられるから。</p>
-	<p></p>
-      </article>
-
-
-      <article>
-        <h3>
-	    Jungleの分散実装
-	</h3>
-	<p>以上がJungleにおける分散設計になる。</p>
-	<br/>
-	<p>この分散設計を元にJungleのサーバノード同士でツリトポロジーを構成し、ログによるデータ分散を実装した。</p>
-	<p>また、Mergeの例として掲示板プログラムにおけるMergeの実装も行った。</p>
-      </article>
-
-
-
-      <article>
-        <h3>
-	    Jungleの分散実装:掲示板システムにおけるMerge
-	</h3>
-	<p>Jungleではアプリケーション毎にMergeアルゴリズムを設計</p>
-	<p>後述する性能比較に用いた掲示板システムにおけるMergeの実装を考える</p>
-	<p>掲示板システムにおけるデータ構造を以下に示す</p>
-	<p style="text-align:center;">
-	    <img src="./images/bulletinboard.png">
-	</p>
-      </article>
-
-      <article>
-        <h3>
-	    Jungleの分散実装:掲示板システムにおけるMerge
-	</h3>
-	<small>
-	<table style="font-size: 0.7em; width:100%;" >
-	    <tr>
-		<td><p>1</p></td>
-		<td><p style="margin-top:-5px; margin-bottom:-5px; text-align:center;"><img src="./images/merge_impl1.png"></p></td>
-	    </tr>
-	    <tr>
-		<td>2</td>
-		<td><p style="margin-top:-5px; margin-bottom:-5px; text-align:center;"><img src="./images/merge_impl2.png"></p></td>
-	    </tr>
-	    <tr>
-		<td>3</td>
-		<td><p style="margin-top:-5px; margin-bottom:-5px; text-align:center;"><img src="./images/merge_impl3.png"></p></td>
-	    </tr>
-	</table>
-	</small>
-      </article>
-
-      <article>
-        <h3>
-	    分散データベースJungleの評価
-	</h3>
-	<p>分散データベースとしてJungleの性能を評価する。</p>
-	<p>分散Key-ValueデーターべースCassandraと比較を行う。</p>
-	<p>比較方法は、Jungle, Cassandra をそれぞれバックエンドとした簡易掲示板を作成する。</p>
-	<p>掲示板に対してHTTP Requestで並列に読み込みと書き込みの負荷をかけ計測する。</p>
-	<p>レスポンスが返る平均時間と標準偏差を求めグラフ化する</p>
-      </article>
-
-
-      <article>
-        <h3>
-	    JungleとCassandraの比較方法
-	</h3>
-	<p>実験は以下の2つを行う</p>
-	<small>
-	    <table style="font-size: 0.7em; width:100%;">
-		<tr>
-		    <th>実験1:サーバ単体への負荷</th><th>実験2:複数台のサーバに対する負荷</th>
-		</tr>
-		<tr>
-		    <td><img style="width:400px;" src="./images/cluster_request_server.png"></td>
-		    <td><img style="width:400px;" src="./images/clients_request_servers.png"></td>
-		</tr>
-		<tr>
-		    <td><p>複数のクライアントから単体のサーバへ負荷をかける</p></td>
-		    <td><p>複数のクライアントから複数のサーバへ負荷をかける</p></td>
-		</tr>
-	    </table>
-	    <p>サーバ単体の性能と, 分散環境下における性能の2つを調べる。</p>
-	    <p>分散環境下におけるノードは全て繋がっている</p>
-	</small>
-      </article>
-
-      <article>
-        <h3>
-	    実験に使用するサーバの仕様
-	</h3>
-<!--
-	<p>実験1:単体サーバへの負荷で使用するサーバ側</p>
--->
-    <table style="font-size: 0.7em;">
-     <tr>
-      <th></th><th>ブレードサーバ</th>
-     </tr>
-     <tr>
-      <td>CPU</td>
-      <td>Intel(R) Xeon(R) CPU X5650@2.67GHz</td>
-     </tr>
-     <tr>
-      <td>コア数</td>
-      <td>24</td>
-     </tr>
-     <tr>
-      <td>Memory</td>
-      <td>132GB</td>
-     </tr>
-     <tr>
-      <td>OS</td>
-      <td>Fedora 16</td>
-     </tr>
-     <tr>
-      <td>HyperVisor</td>
-      <td>なし（物理マシン）</td>
-     </tr>
-    </table>
-    <small>
-    <p style="">並列環境</p>
-    </small>
-    <table style="font-size: 0.7em; margin-top:-20px; ">
-     <tr>
-      <th></th><th>VMWareクラスタ</th><th>KVMクラスタ</th>
-     </tr>
-     <tr>
-      <td>台数</td><td>48</td><td>12</td>
-     </tr>
-     <tr>
-      <td>CPU</td>
-      <td>Intel(R) Xeon(R) CPU X5650@2.67GHz</td>
-      <td>Intel(R) Xeon(R) CPU X5650@2.67GHz</td>
-     </tr>
-     <tr>
-      <td>コア数</td>
-      <td>4</td>
-      <td>4</td>
-     </tr>
-     <tr>
-      <td>Memory</td>
-      <td>8GB</td>
-      <td>8GB</td>
-     </tr>
-     <tr>
-      <td>OS</td>
-      <td>Fedora 16</td>
-      <td>Fedora 16</td>
-     </tr>
-     <tr>
-      <td>HyperVisor</td>
-      <td>VMWare ESXi</td>
-      <td>KVM (Linux Fedora 16)</td>
-     </tr>
-    </table>
-
-      </article>
-
-
-      <article>
-        <h3>
-	    実験1:単体サーバへの負荷
-	</h3>
-	<p style="text-align:center;">
-	    <img style="width:80%;" src="./images/cluster_request_server.png">
-	</p>
-      </article>
-
-      <article>
-       <h3>
-	   実験1：単体サーバへの負荷（読み込み）
-       </h3>
-       <small>
-	   <p>ブレードサーバ一台に対して複数のクライアントからの負荷</p>
-	   <table style="text-align:center;font-size:0.7em;">
-	   <tr>
-	       <td><img style="height:350px;" src="./images/bldsv12_read_bench.png"/></td>
-	   </tr>
-	   <tr>
-	       <th style="text-align:center;">読み込みの実験結果</th>
-	   </tr>
-	   </table>
-	   <p style="margin-top:0px;">JungleがCassandraより良い結果を示している</p>
-	   <p style="margin-top:-20px;">クライアントが55台のときのJungleの最速とCassandraの最遅は3倍近く離れている</p>
-       </small>
-      </article>
-
-      <article>
-       <h3>
-	   実験1：単体サーバへの負荷（書き込み）
-       </h3>
-       <small>
-	   <p>ブレードサーバ一台に対して複数のクライアントからの負荷</p>
-	   <table style="text-align:center;font-size:0.7em;">
-	   <tr>
-	       <td><img style="height:350px;" src="./images/bldsv12_write_bench.png"/></td>
-	   </tr>
-	   <tr>
-	       <th style="text-align:center;">書き込みの実験結果</th>
-	   </tr>
-	   </table>
-	   <p>読み込み同様Jungleのほうが良い結果を示している</p>
-	   <p>読み込みよりJungleとCassandraの結果が重なる部分が減っている</p>
-       </small>
-      </article>
-
-      <article>
-        <h3>
-	    実験1の考察
-	</h3>
-	<p>読み込み、書き込みともにJungleの性能がよく。平均だけみても2倍以上早い部分もある。</p>
-	<p>特に書き込みに関してはクライアントの数が増えるにつれ差が開いている。</p>
-<!--
-	<p>要因の1つとしてCassandraはディスクへ書き込みを行うが、Jungleは全てのデータをオンメモリで扱っていることもある</p>
-	<p>これはある意味当然だが、もう1つ要因をあげられる</p>
--->
-	<p>これはJungleが全体的にロックが少ないことが要因としてあげられる。</li>
-	<p>Jungleは非破壊でデータの保持をするため、読み込みは自由に行える。書き込み時には木のコピーをとりルートノードを入れ替える
-	ときのみロックが発生する。</p>
-      </article>
-
-      <article>
-       <h3>
-	   実験2:分散環境下における負荷
-       </h3>
-       <p style="text-align:center;">
-	   <img style="width:80%;" src="./images/clients_request_servers.png">
-       </p>
-      </article>
-
-      <article>
-       <h3>
-	    実験2：分散環境下における読み込み
-       </h3>
-       <small>
-	   <table style="text-align:center;font-size:0.7em;">
-	   <tr>
-	       <td><img style="height:350px;" src="./images/distributed_read_bench.png">
-	   </tr>
-	   <tr>
-	       <th style="text-align:center;">読み込みの実験結果</th>
-	   </tr>
-	   </table>
-	   <p>CassandraはConsistency Level ONE(赤)とQUORUM(緑)両方を測定</p>
-	   <p>Jungleは1秒から5秒をキープ</p>
-       </small>
-      </article>
-
-      <article>
-       <h3>
-	    実験2：分散環境下における書き込み
-       </h3>
-       <small>
-	   <table style="text-align:center;font-size:0.7em;">
-	   <tr>
-	       <td><img style="height:350px;" src="./images/distributed_write_bench.png">
-	   </tr>
-	   <tr>
-	       <th style="text-align:center;">書き込みの実験結果</th>
-	   </tr>
-	   </table>
-	   <p>CassandraはConsistency Level ONE(赤)とQUORUM(緑)両方を測定</p>
-	   <p>Jungleは5.5秒から7.3秒をキープ</p>
-       </small>
-      </article>
-
-
-      <article>
-        <h3>
-	    実験2の考察
-	</h3>
-	<p>こちらもJungleがCassadraより良い結果を示した。実験1よりも差がでている。</p>
-	<p>Jungleのグラフが横ばいになっていることに注目したい。</p>
-	<!--
-	    <p>Cassandraはノードの数が増えるに従いデータを取りにいくノードも増えることでレスポンスが遅くなっている。</p>
-	    -->
-	<p>Jungleはリクエストに対し手元にあるデータを返す。そのためノードの数が増えてもレスポンスの早さを維持できる。</p>
-	<p>Cassandraはデータを持っている数台のノードに読み込みに行くという作業が入るためJungleより遅くなってしまう</p>
-	<p>Jungleは同期を取らないためデータ全体の整合性は落ちるが、分散管理システムを参考にした設計の有用性を示すことができた。</p>
-      </article>
-
-
-      <article>
-        <h3>
-	    まとめ
-	</h3>
-	<p>本研究では非破壊的木構造Jungleに分散データベースの実装を行った</p>
-	<p>非破壊的木構造における利点を述べ、スケーラビリティの高い分散版管理システムとの類似性を述べた</p>
-	<p>Mergeアルゴリズムの1つとして掲示板プログラムにおけるMergeについて設計・実装を行った</p>
-	<p>性能比較の実験のためJungle、Cassandraで利用できる簡易掲示板の作成を行った</p>
-	<p>実験は単体サーバと分散環境下において行い、どちらともCassandraよりよい結果をえることができた</p>
-      </article>
-
-<!--
-      <article>
-        <h3>
-	    今後の課題
-	</h3>
-	<p>push/pull方式による分断耐性の実装</p>
-	<ul>
-	    <li>現実装ではJungleはデータ編集が行われた際に発生するログを非同期で他サーバノードへと送信している</li>
-	    <li>だがこの方法では接続が切れた際に再接続を行ったノードが全てのデータをとることができない</li>
-	    <li>そこで非同期とは別に同期をとり他ノードとに差分となるデータを送るということを行いたい</li>
-	    <li>これは分散管理システムにおけるpush/pull APIにあたる</li>
-	</ul>
-      </article>
--->
-      <article>
-        <h3>
-	    今後の課題
-	</h3>
-	<p>データ分割の実装</p>
-	<ul>
-	    <li>現在の実装は全てのノードで全てのデータを持たせている</li>
-	    <li>この方法ではメモリの使用量が高いこととネットワーク帯域への負荷が懸念される</li>
-	    <li>ノード単位で保持するデータを分ける実装が必要</li>
-	    <li>その場合、木構造単位でノード毎にデータを分ける</li>
-	    <li>持っていないデータの要求が来た場合は、データを持っているノードに取りに行くようにする</li>
-	</ul>
-      </article>
-
-      <article>
-        <h3>
-	    今後の課題
-	</h3>
-	<p>Mergeアルゴリズムの設計</p>
-	<ul>
-	    <li>JungleはMergeを使うことで更新データ衝突の問題を解決する。</li>
-	    <li>今回実装した掲示板プログラムにおけるMergeは単純なもの。</li>
-	    <li>他のアプリケーションではどのようにMergeを行うのか考察が必要。</li>
-	</ul>
-      </article>
-
-
-      <article>
-        <h3>
-	    今後の課題
-	</h3>
-	<p>過去のデータの掃除について</p>
-	<ul>
-	    <li>Jungleは非破壊でデータを保持するため過去のメモリの使用量が大きい</li>
-	    <li>ある程度の単位で過去のデータの掃除を行いたい</li>
-	    <li>そのためにはどのノードがどのデータを持っているかという情報を扱うことが必要</li>
-	    <li>どれくらいデータが古くなると掃除を行うか判断が必要</li>
-	</ul>
-      </article>
-
-      <article>
-        <h3>
-	</h3>
-	<p></p>
-	<ul>
-	</ul>
-      </article>
-
-      <article>
-        <h3>
-	    Mergeは必ずできるのか
-	</h3>
-	<p>Mergeを必ず行うことは難しい</p>
-	<p>例えば、更新するデータが画像だった場合、2つの画像のデータから新しい画像を作るわけにはいかない。</p>
-	<p>後に更新したものを優先するといった方法をとるか、ユーザの選択に委ねるしかない。</p>
-      </article>
-
-
-      <article>
-        <h3>
-	    分散Key-ValueストアCassandraの特徴
-	</h3>
-	<small style="line-height:30px;">
-	<p>ring型トポロジーを形成。ring上にはHash値があり、書き込むデータのキーのハッシュ値により書き込むノードを決定</p>
-	<p>1つのデータの複製を最大何とるかというReplication factorの設定がある。</p>
-	<p>Consistency Levelというデータの読み書きの際に何台のノードから読み書きするかを決定できる</p>
-	<p>Consistency LevelにはONE,QUORUM,ALLがある。QUORUMはReplication factorの数/2+1 のノードに読み書きする。</p>
-	</small>
-	<p>
-	    <img style="margin-top:-30px;" src="./images/consistency_quorum.png">
-	</p>
-      </article>
-
-
-      <article>
-        <h3>
-	    Jungleの分散設計:分散版管理システム
-	</h3>
-	<p>Jungleは分散設計を行うにあたってGitやMercurialといった分散版管理システムを意識している</p>
-	<p style="margin-top:-10px;">分散版管理システムとは多人数によるソフトウェア開発において変更履歴を管理するシステム</p>
-	<p style="margin-top:-10px;">分散版管理システムは次の特徴とAPIを持つ</p>
-	<ul>
-	    <li>開発者それぞれがリポジトリのクローンしてローカルに持ち、開発はローカルのリポジトリを通すことで行われる</li>
-	    <li>ローカルのリポジトリは独立に存在し、サーバ上にある他人のリポジトリから変更履歴をとることができる。また自身の変更履歴を伝えることもできる</li>
-	    <li>データ更新時に先に別の更新が入っていた(衝突)場合はMergeによりデータの整合性をとる</li>
-	</ul>
-      </article>
-
-      <article>
-        <h3>
-	    Jungleの分散設計:分散版管理システム
-	</h3>
-	<p>分散版管理システムAPI</p>
-	<ul style="margin-top:-20px;">
-	    <li>commit:データに変更を加えたことをリポジトリに登録</li>
-	    <li>push:ローカルのリポジトリで行った変更履歴を他のリポジトリへまとめて送る</li>
-	    <li>pull:他のリポジトリからの変更履歴をまとめて受け取る</li>
-	</ul>
-	<p style="text-align:center;">
-	<img style="height:200px;" src="./images/distributed_repository.png">
-	</p>
-	<small>
-	<p>分版版管理システムはリポジトリが壊れても別のリポジトリよりデータを復旧できることと、push/pullそれとMergeによる整合性
-	    の確保で、高いスケーラビリティを持っている</p>
-	</small>
-      </article>
-
-      <article>
-        <h3>
-	    Jungleの分散設計:分散版管理システム
-	</h3>
-	<p>Jungleと分散版管理システムには似通った点がある</p>
-	<li>どちらもデータのコピーが自由</li>
-	<li>データ更新しても過去のデータに影響を与えない</li>
-	<br/>
-	<p><font color="red">同じAPIを実装することで、分散版管理システムと同じく高いスケーラビリティが期待できる</font></p>
-	<p>具体的には</p>
-	<ul>
-	    <li>pushやpullによる定期的なデータの更新</li>
-	    <li>Mergeによる更新データ衝突の解決</li>
-	</ul>
-      </article>
-
-
-
-
-    </section>
-
-  </body>
-</html>
+<!DOCTYPE html>
+<html>
+<head>
+  <meta charset='utf-8'>
+  <title>分散 Database Jungle に関する研究</title>
+
+<!--
+   Notes on CSS media types used:
+
+   1) projection -> slideshow mode (display one slide at-a-time; hide all others)
+   2) screen     -> outline mode (display all slides-at-once on screen)
+   3) print      -> print (and print preview)
+
+   Note: toggle between projection/screen (that is, slideshow/outline) mode using t-key
+
+   Questions, comments?
+   - send them along to the mailinglist/forum online @ http://groups.google.com/group/webslideshow
+-->
+
+<!-- style sheet links -->
+<link rel="stylesheet/less" href="themes/blank/projection.css.less"  media="screen,projection">
+<link rel="stylesheet/less" href="themes/blank/screen.css.less"      media="screen">
+<link rel="stylesheet/less" href="themes/blank/print.css.less"       media="print">
+
+<link rel="stylesheet/less" href="blank.css.less"    media="screen,projection">
+
+<!-- Notes about less css support
+     - all less stylesheets (*.css.less) need to get listed/loaded first (before the less.js script)
+     - find more info about less.js online @ http://lesscss.org
+
+    ***** NOTE:
+   less.js browser script currently won’t work if you’re using Google Chrome
+    and the path to your page starts with "file:///" due to a known Chrome issue.
+   (In the developer/js console you will see:
+     XMLHttpRequest cannot load file:///../s6/shared/projection.css.less.
+     Cross origin requests are only supported for HTTP.)
+  -->
+
+<!-- add js libs (less, jquery) -->
+<script src="js/less-1.1.4.min.js"></script>
+<script src="js/jquery-1.7.min.js"></script>
+
+<!-- S6 JS -->
+<script src="js/jquery.slideshow.js"></script>
+<script src="js/jquery.slideshow.counter.js"></script>
+<script src="js/jquery.slideshow.controls.js"></script>
+<script src="js/jquery.slideshow.footer.js"></script>
+<script src="js/jquery.slideshow.autoplay.js"></script>
+<script>
+  $(document).ready( function() {
+    Slideshow.init();
+
+    // Example 2: Start Off in Outline Mode
+    // Slideshow.init( { mode: 'outline' } );
+
+    // Example 3: Use Custom Transition
+    // Slideshow.transition = transitionScrollUp;
+    // Slideshow.init();
+
+    // Example 4: Start Off in Autoplay Mode with Custom Transition
+    // Slideshow.transition = transitionScrollUp;
+    // Slideshow.init( { mode: 'autoplay' } );
+  } );
+</script>
+
+<!-- Better Browser Banner for Microsoft Internet Explorer (IE) -->
+<!--[if IE]>
+<script src="js/jquery.microsoft.js"></script>
+<![endif]-->
+
+</head>
+<body>
+
+<div class="layout">
+  <div id="header"></div>
+  <div id="footer">
+    <h1>分散 Database Jungle に関する研究</h1>
+    <h2>琉球大学大学院　情報工学専攻 修士2年次　大城信康</h2>
+  </div>
+</div>
+
+<div class="presentation">
+
+  <!-- add slides here; example -->
+
+  <div class='slide cover'>
+    <h1>分散 Database Jungleに関する研究</h1>
+    <ul>
+	<p>琉球大学　大城信康
+	<br>
+	Feb 3, 2013
+	</p>
+    </ul>
+  </div>
+
+  <div class='slide'>
+    <h1>概要</h1>
+	    <p>非破壊的木構造データベースJungleに分散実装を行い掲示板システムに特化したデーターベースを作成し、その評価を行った。</p>
+	    <p>分散データベースCassandraより2倍以上速く、分散環境下においては10倍以上速くなる結果も確認された。</p>
+	    <br/>
+  </div>
+
+  <div class='slide'>
+    <h1>研究の背景と目的</h1>
+	<p>ウェブサービスにとってデータベースは必須であり、ウェブサービスの規模に比例してデータベースへの負荷も高まる。</p>
+	<p>データベースの処理能力の高さはそのままウェブサービスの質に繋がるため、データベースのスケーラビリティの確保は重要である。</p>
+	<p>スケーラビリティ確保の方法としてデータ分散があるが、分散する方法により性能も変わってくる。</p>
+	<p>ウェブサービスのなかでも、コンテンツマネジメントシステムに合ったスケーラビリティの確保ができるデータベースの開発を行う。</>
+  </div>
+
+  <div class='slide'>
+    <h1>
+	    ウェブサービスにおけるデータベースの重要性
+    </h1>
+	<p>ウェブサービスへの負荷が高まることは、データベースへの負荷が高まることでもある。</p>
+	<p>データベースの性能が低ければ負荷に耐え切れずサービスはダウンする</p>
+	<p style="text-align:center;">
+	    <img src="./images/service_down.png">
+	</p>
+	<p>そのため、データベースにはスケーラビリティが必要</p>
+  </div>
+
+  <div class='slide'>
+    <h1>
+	    スケーラビリティとは
+    </h1>
+	<p>システムが負荷の増大に対して柔軟に拡張して対応できる性質</p>
+	<p>主に次の2つの方法によりシステムはスケールされる</p>
+	<ul>
+	<li><font color="blue">スケールアップ</font>：<br/>高価な単一マシンによる性能アップ</li>
+	<br/>
+	<li><font color="red">スケールアウト</font>：<br/>汎用的なマシンを複数台用意することで性能アップ</li>
+	</ul>
+	<p>分散システムにおいては<font color="red">スケールアウト</font>によりスケーラビリティを高める</p>
+	<p style="text-align:center;">
+	    <img style="" src="./images/scalability.png">
+	</p>
+  </div>
+
+  <div class='slide'>
+    <h1>
+	    データベースのスケーラビリティ
+    </h1>
+    <p>データベースのスケーラビリティを考えるとき、どういう用途で使用するかを考えるのが重要。</p>
+	<li>例えば、掲示板システムにおいては、書き込みと読み込みが速いことが求められる。</li>
+    <br/>
+    <p>ウェブサービスにおいても、どのようなサービスを行うかによってスケーラビリティの確保の仕方も変わってくる。</p>
+    <p>本研究で開発しているデータベースはコンテンツマネジメントシステム（CMS）を対象としている。</p>
+    <br/>
+  </div>
+
+  <div class='slide'>
+    <h1>
+	   コンテンツマネジメントシステム(CMS)
+    </h1>
+	<p>Webコンテンツを構成するテキストや画像などのデジタルコンテンツを管理し配信するシステム。</p>
+	<li>例：ブログツール、Wiki</li>
+	<p>分散コンテンツマネジメントシステムに求められること。</p>
+	<li>Webコンテンツを分散して管理</li>
+	<li>スケールアウトするシステム</li>
+	<p>データ全体の整合性に遅延がある、結果整合性でもよい。書き込みや読み込みを優先としたデータベースが必要。</p>
+	<p>そこで、非破壊的木構造データベースJungleの開発が行われた。</p>
+	<br/>
+  </div>
+
+  <div class='slide'>
+    <h1>
+        非破壊的木構造データベースJungle
+    </h1>
+	<p>JungleはスケーラビリティのあるCMSの設計を目指して当研究室で開発されているデータベース。</p>
+	<p>データを木構造で、さらに非破壊で保持する。</p>
+  </div>
+
+  <div class='slide'>
+    <h1>
+	    非破壊的木構造
+    </h1>
+	<p>非破壊的木構造は一度作成したデータは変更しない</p>
+	<p>新しい木構造を作成することでデータの編集を行う</p>
+	<p style="text-align:center;">
+	    <img style="width:700px;" src="./images/non_destructive_tree_edit2.png">
+	</p>
+  </div>
+
+  <div class='slide'>
+    <h1>
+	非破壊的木構造の利点
+    </h1>
+	<p>非破壊的木構造は通常の木構造である破壊的木構造に比べ、以下のような利点を持つ</p>
+	<ul>
+	    <li>一度作成したデータは変更されない</li>
+	    <li>データが変更されないため自由にコピーを作ることができる(いつでも読み込みが可能)</li>
+	    <li>ロックがすくない。ロックが必要なのは最新のルートノードを登録するときだけ</li>
+	</ul>
+	<p>ロックが少なく、いつでもコピーが可能なことから、非破壊的木構造はスケーラブルなシステムに有用となる</p>
+  </div>
+
+  <div class='slide'>
+    <h1>
+	Jungleの分散設計
+    </h1>
+    <p>ここまでJungleに実装されている非破壊的木構造の利点について述べた。</p>
+    <p>次に、Jungleにおける分散設計について述べる。</p>
+    <p>データ分散を行うにあたり、まず考えることはトポロジーの形成と他のノードからデータの伝搬の仕方である。</p>
+    <p>Jungleはこの問題に対し、ツリートポロジーを形成し、データ編集の際に発生するオペレーションを他のノードに流すことで解決する。</p>
+  </div>
+
+  <div class='slide'>
+    <h1>
+	Jungleトポロジーの形成
+    </h1>
+    <p>Jungleのトポロジー形成には当研究室で開発している並列分散フレームワークAliceを使用する。</p>
+    <p>Aliceは以下の機能が提供されている</p>
+    <ul>
+	<li>複数のノードによる分散トポロジーの設定</li>
+	<li>トポロジー上でのデータアクセス機構</li>
+    </ul>
+    <p>JungleにAliceを組み込み、Jungleのノード同士でトポロジーを形成する。</p>
+    <p>Aliceの機能である他ノードへのデータアクセス機構を使用してデータ分散を行う。</p>
+    </ul>
+  </div>
+
+
+
+  <div class='slide'>
+    <h1>
+	分散設計: データ編集オペレーション
+    </h1>
+    <p>Aliceにより、ネットワークトポロジーの作成と他サーバが持つデータアクセス機構を実装できた。</p>
+    <p>次はどのデータを取得することでデータの分散を行うか考えなければならない。</p>
+    <br>
+    <p>Jungleにはデータ編集に使われるオペレーションがある。</p>
+    <p>データ編集に使われるオペレーションをそのまま他サーバノードへ流すことでデータの分散が行える。</p>
+    <p>オペレーションには次の4つがある</p>
+    <ul>
+	<li>addNewChild:子ノードの追加を行う</li>
+	<li>deleteChildAt:指定したノードの削除を行う</li>
+	<li>putAttribute:子ノードにattributeに追加を行う</li>
+	<li>deleteAttribute:子ノードのattributeを削除する</li>
+	<br>
+  </div>
+
+  <div class='slide'>
+    <h1>
+	データ編集オペレーション
+    </h1>
+    <p>子ノードを追加し、その子ノードにattributeを追加する場合次のノードオペレーションが実行される。</p>
+    <ol>
+	<li>[APPEND_CHILD:<-1>:pos:0]</li>
+	<li>[PUT_ATTRIBUTE:<-1,0>:key:mes,value:hello]</li>
+    </ol>
+    <p>このノードオペレーションの実行結果を図に示す。</p>
+    <p style="text-align:center;">
+    <img src="./images/node_operation.png">
+    </p>
+    <p><font color="">トポロジー上でノードオペレーションを渡すことで同じ編集を行いデータの分散を行う。</font></p>
+    <br/>
+    <br/>
+  </div>
+
+
+  <div class='slide'>
+    <h1>
+	Jungle分散実装
+    </h1>
+    <p>以上の設計を元にJungleに分散実装を行った。</p>
+    <p>以下の図はJungleにおけるデータ分散の様子を表している。</p>
+    <p style="text-align:center;">
+	<img src="./images/distributed_jungle.png">
+    </p>
+    <p>Aliceでトポロジーを形成後は、データ編集に使われたオペレーションを他サーバノードに送られる。</p>
+    <p>オペレーションを受信したノードはデータ編集を行う。他にサーバが繋がっている場合はそちらにもオペレーションを送る。</p>
+    <br/>
+    <br/>
+  </div>
+
+  <div class='slide'>
+    <h1>
+	Jungle分散実装
+    </h1>
+    <p>これまでの実装でJungleのデータが分散が行われるようになった。</p>
+    <p>しかしもう１つ問題がある。複数のノードから書き込まれるデータの整合性を取る方法が必要である。</p>
+    <p>JungleではこれをMergeを使うことで自動的に解決する。</p>
+    <p>Mergeとは2つ以上の変更の結果を受けて1つの変更に変えることである。</p>
+    <p>今回は、性能比較に用いる掲示板システムにMergeの実装を行った。</p>
+    <p>掲示板システムにおけるMergeを説明する。</p>
+  </div>
+
+  <div class='slide'>
+    <h1>
+	掲示板システムにおけるMerge
+    </h1>
+    <p>2つの状態をもつ掲示板の書き込みができる。この2つの書き込みから新しい書き込みを作る。</p>
+    <p style="text-align:center;">
+	<img style="width:70%;" src="./images/bulletinboard_merge.png">
+    </p>
+    <p>掲示板はcommutativeなため、いつ書き込んでも良い。よってMergeが自動的に行える。</p>
+    <br/>
+  </div>
+
+
+
+
+  <div class='slide'>
+    <h1>
+	    分散データベースJungleの評価
+   </h1>
+	<p>分散データベースとしてJungleの性能を評価する。</p>
+	<p>分散Key-ValueデーターべースCassandraと比較を行う。</p>
+	<p>比較方法は、Jungle, Cassandra をそれぞれバックエンドとした簡易掲示板を作成する。</p>
+	<p>掲示板に対してHTTP Requestで並列に読み込みと書き込みの負荷をかけ計測する。</p>
+	<p>レスポンスが返る平均時間と標準偏差を求めグラフ化する</p>
+  </div>
+
+
+  <div class='slide'>
+      <h1>
+	  実験内容
+      </h1>
+	<p>実験は2つ行う</p>
+	<li>実験1：サーバを単体で起動し、複数のクライアントからの負荷をかける。</li>
+	<p style="text-align:center;">
+	    <img style="width:60%;" src="./images/cluster_request_server.png">
+	</p>
+	<p>サーバ単体の性能を比較する。</p>
+	<p>クライアントの増加に対してサーバ1台にかかるリクエストも増加</p>
+  </div>
+
+  <div class='slide'>
+      <h1>
+	  実験内容
+      </h1>
+	<li>実験2：サーバを単体で起動し、複数のクライアントからの負荷をかける。</li>
+	<p style="text-align:center;">
+	    <img style="width:60%;" src="./images/clients_request_servers.png">
+	</p>
+	<p>分散環境下における性能を比較する。</p>
+	<p>クライアントとサーバがともに増加するため、サーバ一台に対するリクエストは変わらず。</p>
+	<p>サーバが全体で受けるリクエストは増加する。</p>
+  </div>
+
+  <div class='slide'>
+    <h1>
+		    実験1:単体サーバへの負荷
+    </h1>
+	<p style="text-align:center;">
+	    <img style="width:70%;" src="./images/cluster_request_server.png">
+	</p>
+       <p>レスポンス速度(縦軸の数値)が低い程良い</p>
+       <p>クライアント(横軸の数値)の増加に対してレスポンス速度の増加がゆるやかなものほどよい</p>
+  </div>
+
+  <div class='slide'>
+    <h1>
+	単体サーバへの負荷:読み込み負荷
+   </h1>
+	<object data="./images/bldsv12_read_bench.svg" type="image/svg+xml"></object>
+	<p>Cassandraに比べJungleが全体的に良い結果を出している。</p>
+	<p>台数が増える毎にJungleとCassandraの平均時間の差は離れている。</p>
+	<br/>
+	<br/>
+  </div>
+
+
+  <div class='slide'>
+    <h1>
+	単体サーバへの負荷:書き込み負荷
+   </h1>
+	<object data="./images/bldsv12_write_bench.svg" type="image/svg+xml"></object>
+	<p>読み込み同様JungleがCassandraよりもより結果を出している。</p>
+	<p>読み込み以上にCassandraとの差がついている。</p>
+	<br/>
+  </div>
+
+
+
+  <div class='slide'>
+    <h1>
+	    実験1の考察
+    </h1>
+	<p>読み込み、書き込みともにJungleの性能がよく。平均だけみても2倍以上早い部分もある。</p>
+	<p>特に書き込みに関してはクライアントの数が増えるにつれ差が開いている。</p>
+	<!--
+	<p>要因の1つとしてCassandraはディスクへ書き込みを行うが、Jungleは全てのデータをオンメモリで扱っていることもある</p>
+	<p>これはある意味当然だが、もう1つ要因をあげられる</p>
+	-->
+	<p>これはJungleが全体的にロックが少ないことが要因としてあげられる。</p>
+	<p><font color="red">なぜロックが少ないか</font></p>
+	    <p>Jungleは非破壊でデータの保持をするため、読み込みは自由に行える。書き込み時には木のコピーをとりルートノードを入れ替える
+	ときのみロックが発生する。</p>
+  </div>
+
+  </div>
+
+  <div class='slide'>
+    <h1>
+	   実験2:分散環境下における負荷
+    </h1>
+       <p style="text-align:center;">
+	   <img style="width:70%;" src="./images/clients_request_servers.png">
+       </p>
+       <p>レスポンス速度(縦軸の数値)が低い程良い</p>
+       <p>クライアントとノードの数(横軸の数値)の増加に対してレスポンス速度の増加がゆるやかなものほどよい</p>
+  </div>
+
+
+  <div class='slide'>
+    <h1>
+	分散環境下における負荷：読み込み
+    </h1>
+	<object data="./images/distributed_read_bench.svg" type="image/svg+xml"></object>
+       <p>QUORUM(緑)はCassandraが3ノードに書き込んでいる結果を示す。</p>
+       <p>Jungle同じレスポンスを維持している。</p>
+    <p>Jungleは1秒から5秒をキープ</p>
+       <br/>
+  </div>
+
+
+  <div class='slide'>
+    <h1>
+	分散環境下における負荷：書き込み
+    </h1>
+	<object data="./images/distributed_write_bench.svg" type="image/svg+xml"></object>
+       <p>QUORUM(緑)はCassandraが3ノードに書き込んでいる結果を示す。</p>
+       <p>Jungle同じレスポンスを維持している。</p>
+       <p>Jungleは5.5秒から7.3秒をキープ</p>
+       <br/>
+       <br/>
+  </div>
+
+  <div class='slide'>
+    <h1>
+	    実験2の考察
+    </h1>
+	<p>こちらもJungleがCassadraより良い結果を示した。実験1よりも差がでている。</p>
+	<p>Jungleのグラフが横ばいになっていることに注目したい。</p>
+	<!--
+	    <p>Cassandraはノードの数が増えるに従いデータを取りにいくノードも増えることでレスポンスが遅くなっている。</p>
+	    -->
+	<p>Jungleはリクエストに対し手元にあるデータを返す。そのためノードの数が増えてもレスポンスの早さを維持できる。</p>
+	<p>Cassandraはデータを持っている数台のノードに読み込みに行くという作業が入るためJungleより遅くなってしまう</p>
+	<p>ただしJungleは全て非同期でデータの伝搬を行うため、データ全体の整合性は落ちる</p>
+  </div>
+
+  <div class='slide'>
+    <h1>
+	    まとめ
+    </h1>
+	<p>本研究では非破壊的木構造Jungleに分散データベースの実装を行った</p>
+	<p>非破壊的木構造における利点を述べ、分散実装を行った。</p>
+	<p>分散実装ではAliceを用いたトポロジー形成により、他ノードへデータ編集のオペレーションを送ることで
+	実装を行った。</p>
+	<p>データの整合性に関してはJungle側がMergeにより自動的にMergeを行うことで解決することを述べた。</p>
+	<p>Mergeアルゴリズムの1つとして掲示板プログラムにおけるMergeについて設計・実装を行った</p>
+	<p>性能比較の実験のためJungle、Cassandraで利用できる簡易掲示板の作成を行った</p>
+	<p>実験は単体サーバと分散環境下において行い、どちらともCassandraより平均時間が最低でも2倍以上速いという結果を示すことができた。</p>
+<!--
+	<p>特にQUORUMとの差は数十倍になるときもあった。</p>
+-->
+	<br/>
+  </div>
+
+  <div class='slide'>
+    <h1>
+	    今後の課題
+    </h1>
+	<p>Mergeアルゴリズムの設計</p>
+	<ul>
+	    <li>JungleはMergeを使うことで更新データ衝突の問題を解決する。</li>
+	    <li>今回実装した掲示板プログラムにおけるMergeは単純なもの。</li>
+	    <li>他のアプリケーションではどのようにMergeを行うのか考察が必要。</li>
+	</ul>
+  </div>
+
+
+
+  <div class='slide'>
+    <h1>
+	    今後の課題
+    </h1>
+	<p>過去のデータの掃除について</p>
+	<ul>
+	    <li>Jungleは非破壊でデータを保持するため過去のメモリの使用量が大きい</li>
+	    <li>ある程度の単位で過去のデータの掃除を行いたい</li>
+	    <li>そのためにはどのノードがどのデータを持っているかという情報を扱うことが必要</li>
+	    <li>どれくらいデータが古くなると掃除を行うか判断が必要</li>
+	</ul>
+  </div>
+
+
+  <div class='slide'>
+    <h1>
+
+    </h1>
+
+  </div>
+
+  <div class='slide'>
+    <h1>
+
+    </h1>
+
+  </div>
+
+  <div class='slide'>
+    <h1>
+	    分散Key-ValueストアCassandraの特徴
+    </h1>
+	<p>ring型トポロジーを形成。ring上にはHash値があり、書き込むデータのキーのハッシュ値により書き込むノードを決定</p>
+	<p>1つのデータの複製を最大何とるかというReplication factorの設定がある。</p>
+	<p>Consistency Levelというデータの読み書きの際に何台のノードから読み書きするかを決定できる</p>
+	<p>Consistency LevelにはONE,QUORUM,ALLがある。QUORUMはReplication factorの数/2+1 のノードに読み書きする。</p>
+	<p style="text-align:center;">
+	    <img style="margin-top:-30px;" src="./images/consistency_quorum.png">
+	</p>
+  </div>
+
+  <div class='slide'>
+    <h1>
+	    実験に使用するサーバの仕様
+    </h1>
+    <table style="font-size: 0.7em;">
+     <tr>
+      <th></th><th>ブレードサーバ</th>
+     </tr>
+     <tr>
+      <td>CPU</td>
+      <td>Intel(R) Xeon(R) CPU X5650@2.67GHz</td>
+     </tr>
+     <tr>
+      <td>コア数</td>
+      <td>24</td>
+     </tr>
+     <tr>
+      <td>Memory</td>
+      <td>132GB</td>
+     </tr>
+     <tr>
+      <td>OS</td>
+      <td>Fedora 16</td>
+     </tr>
+     <tr>
+      <td>HyperVisor</td>
+      <td>なし（物理マシン）</td>
+     </tr>
+    </table>
+    <small>
+    <p style="">並列環境</p>
+    </small>
+    <table style="font-size: 0.7em; margin-top:-20px; ">
+     <tr>
+      <th></th><th>VMWareクラスタ</th><th>KVMクラスタ</th>
+     </tr>
+     <tr>
+      <td>台数</td><td>48</td><td>12</td>
+     </tr>
+     <tr>
+      <td>CPU</td>
+      <td>Intel(R) Xeon(R) CPU X5650@2.67GHz</td>
+      <td>Intel(R) Xeon(R) CPU X5650@2.67GHz</td>
+     </tr>
+     <tr>
+      <td>コア数</td>
+      <td>4</td>
+      <td>4</td>
+     </tr>
+     <tr>
+      <td>Memory</td>
+      <td>8GB</td>
+      <td>8GB</td>
+     </tr>
+     <tr>
+      <td>OS</td>
+      <td>Fedora 16</td>
+      <td>Fedora 16</td>
+     </tr>
+     <tr>
+      <td>HyperVisor</td>
+      <td>VMWare ESXi</td>
+      <td>KVM (Linux Fedora 16)</td>
+     </tr>
+    </table>
+
+  </div>
+
+
+
+
+
+
+</div> <!-- presentation -->
+</body>
+</html>