Mercurial > hg > Papers > 2014 > nobuyasu-master

diff slides/index.html_back @ 85:07aec327a7bc
Added slides.htlm
author: Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date: Mon, 03 Feb 2014 13:06:41 +0900
parents: bd73f0e1cdd4
--- a/slides/index.html_back	Mon Feb 03 12:17:40 2014 +0900
+++ b/slides/index.html_back	Mon Feb 03 13:06:41 2014 +0900
@@ -1,189 +1,742 @@
-<!DOCTYPE html>
-<html>
-<head>
-  <meta charset='utf-8'>
-  <title>分散データベース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>分散データベースJungleの実装</h1>
-    <h2>琉球大学大学院　情報工学専攻 修士2年次　大城信康</h2>
-  </div>
-</div>
-
-<div class="presentation">
-
-  <!-- add slides here; example -->
-  
-  <div class='slide cover'>
-    <h1>分散データベースJungleに関する研究</h1>
-    <ul>
-	<p>琉球大学　大城信康
-	<br>
-	14 Jan 2013
-	</p>
-    </ul>
-  </div>
-
-  <div class='slide'>
-    <h1>研究の背景と目的</h1>
-    <ul>
-	<li>スマートフォンやタブレット端末の普及により、大量のデータを扱うウェブサービスが現れてきている。</li>
-	<li>しかしそれに伴い、サーバサイド側への負荷も増大しウェブサービスがダウンする事態が出てきている。</li>
-	<li>そのため、スケーラビリティはウェブサービスにおいて重要な性質の1つとなっている。</lii>
-	<li>スケーラビリティとは、ある複数のノードから構成される分散ソフトウェアがあるとき、その分散ソフトウェアに対して単純にノード
-	    を追加するだけで性能を線形に上昇させることができる性質である</li>
-	<li>スケーラビリティのあるプログラムについてアーキテクチャの設計から行った</li>
-    </ul>
-  </div>
-
-  <div class='slide'>
-    <h1>研究の背景と目的</h1>
-
-    <ul>
-	<li>当研究室では非破壊的木構造を用いたデータベースである Jungle を開発している</li>
-	<li>非破壊的木構造とは、データの編集の際に一度木構造として保存したデータには触れず、新しく木構造を作成してデータの編集を行うこと</li>
-	<li>Jungle は分散データベースとして設計・実装されているが、分断耐性や永続性といった部分の実装がまだ
-	    行われていない</li>
-	<li>本研究では、Jungle を用いてスケーラビリティをもつアーキテクチャの追求を行う</li>
-    </ul>
-  </div>
-
-  <div class='slide'>
-    <h1>今週の作業</h1>
-    <ul>
-	<li>論文の執筆</li>
-	<li>ベンチマーク測定環境の構築</li>
-    </ul>
-  </div>
-
-  <div class='slide'>
-    <h1>ベンチマーク測定環境の構築</h1>
-    <ul>
-	<li>csクラスタ(VM)上で掲示板プログラムを走らせ、ベンチマークをとる</li>
-	<li>Jungle と Cassandra 両方を走らせる環境の構築を行った</li>
-	<h2>問題が発生</h2>
-	<li>Cassandra でConsistencyLevelをいじってもデータを伝搬してくれない</li>
-	<li>Jungle の分散結果が良くならない。圧倒的に遅い。Cassandra の結果の2倍3倍遅くなる</li>
-    </ul>
-  </div>
-
-  <div class='slide'>
-    <h1>問題解決</h1>
-    <ul>
-	<li>Cassandra はConsistencyLevelとは別にReplication factorというレプリケーション(複製)をとるノードの数を指定する項目がある</li>
-	<li>Cassandra のConsistencyLevelはこのReplication factorの数に対して行われる</li>
-	<ul>
-	    <li>Replication factorをNとした場合、ConsistencyLevelをALLにするとこのNの数だけノードに書き込まれるのをまつ</li>
-	    <li>Replication factorをノードの全体の数に合わせてあげるとよい</li>
-	    <li>Replication factorの設定はv1.1くらいまでは設定ファイルでできるが、v1.2からはキースペース生成時に設定するか
-	    ./bin/cassandra-cli を使ってCassandraのデータにアクセスして変更する必要がある</li>
-	</ul>
-	<br>
-	<li>Jungle の結果が悪い原因</li>
-	<ul>
-	    <li>Javaのメモリの量を増やす設定をいれることで解決</li>
-	</ul>
-    </ul>
-  </div>
-
-  <div class='slide'>
-    <h1>単体・複数ノードへの負荷</h1>
-    <ul>
-	<li>クライアント数最大12台。各クライアント5000回のリクエストを出す</li>
-    </ul>
-    <img src="./images/write_bench.png">
-  </div>
-
-  <div class='slide'>
-    <h1>ベンチマーク改良</h1>
-    <ul>
-	<li>Jungleの結果をbldsvで起動した時に近い結果になることが確認できた</li>
-	<li>Cassandra も Jungle のグラフも横ばいになっている。クライアント側からの負荷が足りない。</li>
-	<li>Cassandra の ConsystencyLevel をいじっても結果が変わらないのも負荷が足りないから？</li>
-	<h2>次の課題</h2>
-	<li>クライアント側はKVMで動かしていて現在12台しか無い</li>
-	<li>負荷をかけるプログラムをforkすることでプロセスを増やして負荷を増やすよう改良する必要がある</li>
-	<br>
-	<li>論文書こう</li>
-    </ul>
-  </div>
-
-  <div class='slide'>
-    <h1>今後の作業</h1>
-    <ul>
-	<li>修論作成</li>
-	<li>ベンチマークプログラム作成</li>
-    </ul>
-  </div>
-</div> <!-- presentation -->
-</body>
-</html>
+<!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="height:300px;" src="./images/destructive_tree_slide.png">
+	</p>
+      </article>
+
+      <article>
+        <h3>破壊的木構造</h3>
+	<p>破壊的木構造ではデータの編集中にそのデータを読むことができない</p>
+	<p>編集が完了するまでまたなければならない</p>
+	<p style="text-align:center;">
+	    <img style="width:500px;" src="./images/destructive_tree_demerit.png">
+	</p>
+      </article>
+
+      <article>
+        <h3>
+	    非破壊的木構造
+	</h3>
+	<p>非破壊的木構造は一度作成したデータは変更しない</p>
+	<p>新しい木構造を作成することでデータの編集を行う</p>
+	<p style="text-align:center;">
+	    <img style="height:300px;" src="./images/non_destructive_tree_slide.png">
+	</p>
+	<p></p>
+      </article>
+
+      <article>
+        <h3>
+	    非破壊的木構造におけるデータ編集
+	</h3>
+	<p>目的とするノード5ををコピーして内容を編集する。ノード100となる</p>
+	<p>ルートノードから目的のノード5までに続くルートノードとノード2のコピーとりノード100と繋げる</p>
+	
+	<p style="text-align:center;">
+	    <img style="width:700px;" src="./images/non_destructive_tree_edit.png">
+	</p>
+      </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>
+      </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>ツリートポロジーを形成</th>
+		<th>commit log伝搬によるデータ分散</th>
+	    </tr>
+	    <tr>
+		<td>
+		    <img src="./images/tree_topology.png">
+		</td>
+		<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>
author	Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date	Mon, 03 Feb 2014 13:06:41 +0900
parents	bd73f0e1cdd4
children