Mercurial > hg > Papers > 2011 > shoshi-jssst

view jssst2011/index.html @ 7:f542388881a9 default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
added slides beta
author Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
date Sun, 25 Sep 2011 03:42:16 +0900
parents
children
line wrap: on
line source

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
        "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html xmlns="http://www.w3.org/1999/xhtml">

<head>
<title>S5: An Introduction</title>
<!-- metadata -->
<meta name="generator" content="S5" />
<meta name="version" content="S5 1.3" />
<meta name="presdate" content="[YYYYMMDD]" />
<meta name="author" content="[your name]" />
<meta name="company" content="[your company]" />
<!-- meta extensions -->
<meta name="subject" content="[subject]" />
<meta name="creator" content="[creator]" />
<meta name="contributor" content="[contributor]" />
<meta name="publisher" content="[publisher]" />
<!-- meta temporary -->
<meta http-equiv="content-type" content="text/html; charset=utf-8" />
<meta http-equiv="Content-Script-Type" content="text/javascript" />
<meta http-equiv="Content-Style-Type" content="text/css" />
<!-- configuration parameters -->
<meta name="defaultView" content="slideshow" />
<meta name="controlVis" content="hidden" />
<!-- configuration extensions -->
<meta name="tranSitions" content="true" />
<meta name="fadeDuration" content="500" />
<meta name="incrDuration" content="250" />
<!-- configuration autoplay extension -->
<meta name="autoMatic" content="false" />
<meta name="playLoop" content="false" />
<meta name="playDelay" content="10" />
<!-- configuration audio extension -->
<meta name="audioSupport" content="false" />
<meta name="audioVolume" content="100" />
<meta name="audioError" content="false" />
<!-- configuration audio debug -->
<meta name="audioDebug" content="false" />
<!-- style sheet links -->
<link rel="stylesheet" href="ui/default_utf/slides.css" type="text/css" media="projection" id="slideProj" />
<link rel="stylesheet" href="ui/default_utf/outline.css" type="text/css" media="screen" id="outlineStyle" />
<link rel="stylesheet" href="ui/default_utf/print.css" type="text/css" media="print" id="slidePrint" />
<link rel="stylesheet" href="ui/default_utf/opera.css" type="text/css" media="projection" id="operaFix" />
<!-- embedded styles -->
<style type="text/css" media="all">
/* embedded styles */
</style>
<!-- S5 JS -->
<script src="ui/default_utf/slides.js" type="text/javascript"></script>
</head>
<body>

<div class="layout">
<div id="controls"><!-- DO NOT EDIT --></div>
<div id="currentSlide"><!-- DO NOT EDIT --></div>
<div id="header"></div>
<div id="footer">
<h1>Cassandraと非破壊的構造を用いたCMSのスケーラビリティ検証環境の構築</h1>
<h2>2011/09/27 ソフトウェア科学会</h2>
</div>
</div>

<div class="presentation">
<div class="slide">
<h1>Cassandraと非破壊的構造を用いたCMSのスケーラビリティ検証環境の構築</h1>
<h3>琉球大学 玉城 将士</h3>
<h4>琉球大学 情報工学科 河野 真治</h4>
</div>

<div class="slide">
<h1>はじめに</h1>
<p>本研究では,スケーラビリティのあるCMSを開発するため非破壊的木構造とCassandraを用いた設計と実装を行って来た.</p>
<p>今回は,CMSの非破壊的に編集する際に必要となる，効率的な二分木辞書の開発と</p>
<p></p>システムの検証を仮想マシンクラスタ上で行うために環境構築と管理ツールの開発を行った.</p>
</div>
</div>

<div class="slide">
<h1>非破壊木構造を用いたCMS</h1>
<small>
<p>本研究では，スケーラビリティのあるCMSを開発するために，コンテンツを非破壊的木構造を用いて管理する方法を採用した．</p>
<p>非破壊的木構造とは，木構造を並列に編集することの出来る方法である．</p>
<p>また,木構造を保存するためのバックエンドに分散データベースであるCassandraを使用することで，スケーラビリティを確保している．</p>
</small>
<center>
<img class="scale" width="582" height="209" src="./fig/CMSDESC.png"/>
</center>
</div>

<div class="slide">
<h1>非破壊木構造を用いたCMS</h1>
<small>
<p>本CMSでは，コンテンツを木構造を用いて管理する．</p>
<p>木構造のノードは辞書と子供のリストを保持しており，辞書には自由に値を設定することが出来る．</p>
<p>非破壊的木構造は基本的なアイディアとして木構造を再編集せずに編集の際に木のノードの一部をコピーすることで元木構造の不変性を保証する．</p>
</small>
<center>
	<img class="scale" width="645" height="247" src="./fig/NDT01.png"/>
</center>
</div>

<div class="slide">
<h1>非破壊木構造を用いたCMS</h1>
<p>木構造を用いたコンテンツを表すには以下のような例があげられる．</p>
<center>
<img class="scale" width="692" height="331" src="./fig/treeexample.png"/>
</center>
</div>

<div class="slide">
<h1>CMSの問題点</h1>
<p>例で示したとおり，ノードはそれぞれ要素の辞書と子供のリストを保持する．編集の際に一部のノードをコピーするため，辞書とリストのコピーが必要となる．</p>
<p>通常のHashTableのコピー自体には要素数分のコピーが必要になり，これは非効率的である．</p>
<p>そのため，本研究ではこれを改良するために，AVLと非破壊的木構造を利用したコピーの計算量がO(1)であり，挿入・削除がO(log n)な辞書を開発する．</p>
</div>

<div class="slide">
<h1>AVLとは？</h1>
<small>
<p>バランス木の一つで，<span style="color:red">すべての節において，左部分木と右部分木の高さの差が１以内に収まらなければならない</span>という制約のある二分木である．</p>
<p>ある節において制約が崩れる場合，木の回転を行うことによりバランスを回復させることが出来る．</p>
</small>
<center>
<img class="scale" width="679" height="351" src="./fig/AVL.png"/>
</center>
</div>

<div class="slide">
<h1>非破壊的木構造</h1>
<small>
<p>編集元の木構造を破壊することなく，必要な部分のみコピーオンライトで新しい木構造を構成する方法である．</p>
<p>編集元の木構造は不変なため，並列に読み書きすることが可能である．</p>
</small>
<center>
	<img class="scale" width="645" height="247" src="./fig/NDT01.png"/>
	<p style="font-size: small;">FをGに書き換えた場合の例</p>
</center>
</div>

<div class="slide">
<h1>NDAVLTreeMap</h1>
<small>
<p>非破壊的木構造(Non-Destructive Tree)とAVLを組み合わせた辞書であり，以下の特徴がある．</p>
<ul>
	<li>並列に読み書きができる．</li>
	<li>AVLの特徴である検索・挿入のO(logN)は崩さない．</li>
	<li>辞書のコピー自体は二分木のルートを共有するだけで良い．</li>
</ul>
</small>
</div>

<div class="slide">
<h1>NDAVLTreeMap</h1>
<p>例：挿入の操作</p>
<small>
<p>二分木辞書に７を挿入する．挿入位置を検索する同時にノードの複製を行い，挿入位置に７を挿入する．</p>
</small>
<center>
<img class="scale" width="646" height="284" src="./fig/NDTAVL01.png"/>
</center>
</div>

<div class="slide">
<h1>NDAVLTreeMap</h1>
<p>例：挿入の操作</p>
<small>
<p>挿入したノードより親ノードへと辿り，回転が必要な場合は回転処理を行う．</p>
</small>
<center>
<img class="scale" width="757" height="352" src="./fig/NDTAVL02.png"/>
</center>
</div>

<div class="slide">
<h1>NDAVLTreeMap</h1>
<p>例：挿入の操作</p>
<small>
<ul>
	<li>最後にCAS(CompareAndSwap)を用いて辞書の二分木への参照を置き換える．</li>
	<li>CASに失敗した場合は，最新の二分木を用いて再度編集を行う．</li>
</ul>
</small>
</div>

<div class="slide">
<h1>NDAVLTreeMap</h1>
<p>例：辞書のコピー</p>
<small>
<p>非破壊的木構造は編集が完了した木構造は破壊されない，そのため不変であり，複数の辞書で二分木を共有しても問題はない．</p>
</small>
</div>

<div class="slide">
<h1>ここまでのまとめ</h1>
<small>
<ul>
	<li>本研究では，木構造を用いたCMSの開発を行なってきた．</li>
	<li>CMSはコンテンツを編集する際に，モデルである木構造を非破壊的に編集する．</li>
	<li>非破壊編集時に，ノードのコピー内部で辞書のコピーが発生するため，通常の辞書では非効率的．</li>
	<li>非破壊的木構造とAVLを合わせた辞書を用いることによりコピーのコストを抑えることが出来る．</li>
</ul>
</small>
</div>

<div class="slide">
<h1>スケーラビリティ検証環境の構築</h1>
<small>
<p>システムのスケーラビリティ検証を行うためには，並列に負荷をかけてスループットの計測を行う必要があり，クラスタ環境が必要となる．</p>
<p>そこで，高性能サーバーと仮想化を用いて，ベンチマークを行う仮想クラスタ環境の構築が必要となった．</p>
</small>
<center>
<img class="scale" width="698" height="329" src="./fig/cluster.png"/>
</center>
</div>

<div class="slide">
<h1>スケーラビリティ検証環境の構築</h1>
<small>
<p>仮想化を用いたクラスタ環境の構築の際には，一つの仮想マシンが物理マシンのリソースを占有してしまうと，同一の物理マシンで動作している仮想マシンの動作に影響が出てくると考えられる．</p>
<p>そのため，仮想マシンのリソースを制限して他の仮想マシンに影響が出ないようにする必要がある．</p>
<p>以上の点を考慮しつつ以下の環境を用いてサーバー用・クライアント用の２つ仮想クラスタ環境の構築を行った．</p>
</small>
</div>

<div class="slide">
<h1>スケーラビリティ検証環境の構築</h1>
<p>クライアント用クラスタ</p>
<div style="width: 50%; float: left;">
<ul>
	<li>物理マシン</li>
	<ul>
		<li>CPU: Xeon X5660 2.67GHz(6/HT)</br>※CPUを２個搭載</li>
		<li>メモリ: 130GB</li>
		<li>ハイパーバイザ: WMWare vShpare4</li>
		<li>仮想マシン数: 6台</li>
	</ul>
</ul>
</div>
<div style="width: 50%; float: left;">
<ul>
	<li>仮想マシン</li>
	<ul>
		<li>CPU: 仮想CPU 4Core</li>
		<li>メモリ: 8GB</li>
		<li>OS: CentOS5.5</li>
	</ul>
</ul>
</div>
<br style="clear: both;"/>
<small>
<p>クライアント用クラスタでは物理サーバーが８台用意されており合計４８台のVMを利用することが出来る．</p>
</small>
</div>

<div class="slide">
<h1>スケーラビリティ検証環境の構築</h1>
<p>サーバー用クラスタ</p>
<div style="width: 50%; float: left;">
<ul>
	<li>物理マシン</li>
	<ul>
		<li>CPU: Xeon X5660 2.67GHz(6/HT)</br>※CPUを２個搭載</li>
		<li>メモリ: 130GB</li>
		<li>ハイパーバイザ: KVM</li>
		<li>仮想マシン数: 任意</li>
	</ul>
</ul>
</div>
<div style="width: 50%; float: left;">
<ul>
	<li>仮想マシン</li>
	<ul>
		<li>CPU: 仮想CPU 4-8Core</li>
		<li>メモリ: 8GB</li>
		<li>OS: Fedora 14</li>
	</ul>
</ul>
</div>
<br style="clear: both;"/>
<small>
<p>サーバー用クラスタはサーバーの性能を変化させて検証を行うため，決まったリソースを割り振ったVMを用意していない．</p>
</small>
</div>

<div class="slide">
<h1>スケーラビリティ検証環境管理ツールの開発</h1>
<p>以上で仮想クラスタ環境を構築することができたが，クラスタの整備は単純作業の繰り返しで，管理ソフトを起動しての作業は効率が悪い．</p>
<p>仮想マシンは仮想環境が提供するAPIなどを用いて設定をプログラミングすることができる．</p>
<p>本研究では，設定を簡略化するためlibvirtを用いて仮想化クラスタの管理ツールの開発を行った．</p>
</div>

<div class="slide">
<h1>libvirt</h1>
<p>libvirtとは，様々な仮想環境を操作するための共通なAPIを提供するライブラリである．</p>
<p>仮想・物理マシン両方の情報や設定を共通のAPIを用いて操作することが出来る．</p>
<ul>
	<li>対応言語: C,Python,PHP,Java</li>
	<li>対応環境: Xen,KVM,VMware ESX,...</li>
</ul>
<p>今回の検証環境ではKVMとVMWareの２つの仮想環境を利用しているため，共通の操作を提供するlibvirtを採用した．</p>
</div>

<div class="slide">
<h1>php-webvirt</h1>
<small>
<p>libvirtを用いた管理ツールはいくつか存在するが，どれもインストールが大変であったり，不要な機能があったりする．</p>
<p>そこで，本研究ではインストールが容易で簡易な仮想化管理環境であるphp-webvirtの開発を行った．</p>
<p>php-webvirtはCakePHPとlibvirtで作成されており，主に以下の機能を提供する．</p>
<ul>
	<li>仮想マシンの起動・終了</li>
	<li>仮想マシンの作成・破棄</li>
	<li>ストレージプールの管理</li>
	<li>VNCを用いた画面の表示</li>
</ul>
</small>
</div>

<div class="slide">
<h1>php-webvirt</h1>
<p>ここにphp-webvirtの動作画面(1)を載せる予定</p>
</div>

<div class="slide">
<h1>php-webvirt</h1>
<p>ここにphp-webvirtの動作画面(2)を載せる予定</p>
</div>

<div class="slide">
<h1>まとめ</h1>
<small>
<ul>
	<li>本研究では，スケーラビリティの検証環境を仮想環境を用いて行った．</li>
	<li>仮想環境においては複数の仮想マシンが物理マシンで動作するため，リソースの制限が重要だと考えられる．</li>
	<li>また，クラスタの整備は単純作業の繰り返しでありハイパーバイザが提供するライブラリを用いて自動化することが出来る．</li>
	<li>そのため，複数のハイパーバイザで共通の操作を行えるlibvirtを用いた管理ツールを開発した．</li>
</ul>
</small>
</div>

<div class="slide">
<h1>全体のまとめ</h1>
<p>書いたほうがいいかなー？</p>
</div>

</div>

</body>
</html>