Mercurial > hg > Papers > 2011 > shoshi-sigos

changeset 1:423aed897131 default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
謝辞を追加
author shoshi<shoshi@cr.ie.u-ryukyu.ac.jp>
date Wed, 16 Mar 2011 19:47:06 +0900
parents ed565825e76c
children
files ARC195OS117-23.aux ARC195OS117-23.dvi ARC195OS117-23.log ARC195OS117-23.pdf ARC195OS117-23.tex fig/desttree.pdf fig/monotree.pdf graffle/desttree.graffle graffle/monotree.graffle
diffstat 9 files changed, 62 insertions(+), 79 deletions(-) [+]
line wrap: on
line diff
--- a/ARC195OS117-23.aux	Thu Mar 10 18:47:54 2011 +0900
+++ b/ARC195OS117-23.aux	Wed Mar 16 19:47:06 2011 +0900
@@ -15,9 +15,8 @@
 \bibstyle{ipsjunsrt}
 \bibcite{SHOSHI1}{1}
 \bibcite{DYNAMO}{2}
-\bibcite{YCSB}{3}
-\bibcite{SEDA1}{4}
-\bibcite{SEDA2}{5}
-\bibcite{BIGTABLE}{6}
+\bibcite{SEDA1}{3}
+\bibcite{SEDA2}{4}
+\bibcite{BIGTABLE}{5}
 \newlabel{ref:ConPool}{{9}{1239}}
 \gdef\ipsj@lastpage{1239}
Binary file ARC195OS117-23.dvi has changed
--- a/ARC195OS117-23.log	Thu Mar 10 18:47:54 2011 +0900
+++ b/ARC195OS117-23.log	Wed Mar 16 19:47:06 2011 +0900
@@ -1,4 +1,4 @@
-This is pTeX, Version 3.141592-p3.1.10 (utf8.euc) (Web2C 7.5.4) (format=platex-euc 2010.10.19)  10 MAR 2011 18:44
+This is pTeX, Version 3.141592-p3.1.10 (utf8.euc) (Web2C 7.5.4) (format=platex-euc 2010.10.19)  16 MAR 2011 19:45
 **ARC195OS117-23
 (./ARC195OS117-23.tex
 pLaTeX2e <2006/11/10>+0 (based on LaTeX2e <2003/12/01> patch level 0)
@@ -111,69 +111,68 @@
 )
 \openout1 = `ARC195OS117-23.aux'.
 
-LaTeX Font Info:    Checking defaults for OML/cmm/m/it on input line 37.
-LaTeX Font Info:    ... okay on input line 37.
-LaTeX Font Info:    Checking defaults for T1/cmr/m/n on input line 37.
-LaTeX Font Info:    ... okay on input line 37.
-LaTeX Font Info:    Checking defaults for OT1/cmr/m/n on input line 37.
-LaTeX Font Info:    ... okay on input line 37.
-LaTeX Font Info:    Checking defaults for OMS/cmsy/m/n on input line 37.
-LaTeX Font Info:    ... okay on input line 37.
-LaTeX Font Info:    Checking defaults for OMX/cmex/m/n on input line 37.
-LaTeX Font Info:    ... okay on input line 37.
-LaTeX Font Info:    Checking defaults for U/cmr/m/n on input line 37.
-LaTeX Font Info:    ... okay on input line 37.
-LaTeX Font Info:    Checking defaults for JY1/mc/m/n on input line 37.
-LaTeX Font Info:    ... okay on input line 37.
-LaTeX Font Info:    Checking defaults for JT1/mc/m/n on input line 37.
-LaTeX Font Info:    ... okay on input line 37.
+LaTeX Font Info:    Checking defaults for OML/cmm/m/it on input line 16.
+LaTeX Font Info:    ... okay on input line 16.
+LaTeX Font Info:    Checking defaults for T1/cmr/m/n on input line 16.
+LaTeX Font Info:    ... okay on input line 16.
+LaTeX Font Info:    Checking defaults for OT1/cmr/m/n on input line 16.
+LaTeX Font Info:    ... okay on input line 16.
+LaTeX Font Info:    Checking defaults for OMS/cmsy/m/n on input line 16.
+LaTeX Font Info:    ... okay on input line 16.
+LaTeX Font Info:    Checking defaults for OMX/cmex/m/n on input line 16.
+LaTeX Font Info:    ... okay on input line 16.
+LaTeX Font Info:    Checking defaults for U/cmr/m/n on input line 16.
+LaTeX Font Info:    ... okay on input line 16.
+LaTeX Font Info:    Checking defaults for JY1/mc/m/n on input line 16.
+LaTeX Font Info:    ... okay on input line 16.
+LaTeX Font Info:    Checking defaults for JT1/mc/m/n on input line 16.
+LaTeX Font Info:    ... okay on input line 16.
 LaTeX Font Info:    Font shape `JT1/mc/bx/n' in size <14.4> not available
-(Font)              Font shape `JT1/gt/m/n' tried instead on input line 84.
+(Font)              Font shape `JT1/gt/m/n' tried instead on input line 63.
 LaTeX Font Info:    Font shape `JY1/mc/bx/n' in size <14.4> not available
-(Font)              Font shape `JY1/gt/m/n' tried instead on input line 84.
+(Font)              Font shape `JY1/gt/m/n' tried instead on input line 63.
 
 
 Class ipsjpapers Warning: \title is too wide. Break line(s) by \\ on input line
- 84.
+ 63.
 
 LaTeX Font Info:    External font `cmex10' loaded for size
-(Font)              <10.95> on input line 84.
+(Font)              <10.95> on input line 63.
 LaTeX Font Info:    External font `cmex10' loaded for size
-(Font)              <8> on input line 84.
+(Font)              <8> on input line 63.
 LaTeX Font Info:    Font shape `JT1/mc/bx/n' in size <12> not available
-(Font)              Font shape `JT1/gt/m/n' tried instead on input line 84.
+(Font)              Font shape `JT1/gt/m/n' tried instead on input line 63.
 LaTeX Font Info:    Font shape `JY1/mc/bx/n' in size <12> not available
-(Font)              Font shape `JY1/gt/m/n' tried instead on input line 84.
+(Font)              Font shape `JY1/gt/m/n' tried instead on input line 63.
 
 LaTeX Font Warning: Font shape `JT1/mc/m/sc' undefined
-(Font)              using `JT1/mc/m/n' instead on input line 84.
+(Font)              using `JT1/mc/m/n' instead on input line 63.
 
 
 LaTeX Font Warning: Font shape `JY1/mc/m/sc' undefined
-(Font)              using `JY1/mc/m/n' instead on input line 84.
+(Font)              using `JY1/mc/m/n' instead on input line 63.
 
 LaTeX Font Info:    External font `cmex10' loaded for size
-(Font)              <7> on input line 84.
+(Font)              <7> on input line 63.
 LaTeX Font Info:    Font shape `JT1/mc/bx/n' in size <9> not available
-(Font)              Font shape `JT1/gt/m/n' tried instead on input line 100.
+(Font)              Font shape `JT1/gt/m/n' tried instead on input line 79.
 LaTeX Font Info:    Font shape `JY1/mc/bx/n' in size <9> not available
-(Font)              Font shape `JY1/gt/m/n' tried instead on input line 100.
-LaTeX Font Info:    Try loading font information for OMS+cmr on input line 109.
-
+(Font)              Font shape `JY1/gt/m/n' tried instead on input line 79.
+LaTeX Font Info:    Try loading font information for OMS+cmr on input line 89.
 (/opt/local/share/texmf-dist/tex/latex/base/omscmr.fd
 File: omscmr.fd 1999/05/25 v2.5h Standard LaTeX font definitions
 )
 LaTeX Font Info:    Font shape `OMS/cmr/m/n' in size <8> not available
-(Font)              Font shape `OMS/cmsy/m/n' tried instead on input line 109.
+(Font)              Font shape `OMS/cmsy/m/n' tried instead on input line 89.
  [1234
 
 ]
 File: fig/SEDA.pdf Graphic file (type pdf)
  <fig/SEDA.pdf>
 LaTeX Font Info:    Font shape `JT1/mc/bx/n' in size <7> not available
-(Font)              Font shape `JT1/gt/m/n' tried instead on input line 114.
+(Font)              Font shape `JT1/gt/m/n' tried instead on input line 94.
 LaTeX Font Info:    Font shape `JY1/mc/bx/n' in size <7> not available
-(Font)              Font shape `JY1/gt/m/n' tried instead on input line 114.
+(Font)              Font shape `JY1/gt/m/n' tried instead on input line 94.
 File: ./fig/benchmark.pdf Graphic file (type pdf)
 
 <./fig/benchmark.pdf> [1235]
@@ -203,11 +202,11 @@
  ) 
 Here is how much of TeX's memory you used:
  1327 strings out of 94682
- 16121 string characters out of 1177958
+ 16129 string characters out of 1177958
  70924 words of memory out of 1500000
  4632 multiletter control sequences out of 10000+50000
  17303 words of font info for 67 fonts, out of 1200000 for 2000
  566 hyphenation exceptions out of 8191
- 29i,9n,34p,1950b,653s stack positions out of 5000i,500n,6000p,200000b,5000s
+ 29i,9n,34p,1872b,653s stack positions out of 5000i,500n,6000p,200000b,5000s
 
-Output written on ARC195OS117-23.dvi (6 pages, 29068 bytes).
+Output written on ARC195OS117-23.dvi (6 pages, 30556 bytes).
Binary file ARC195OS117-23.pdf has changed
--- a/ARC195OS117-23.tex	Thu Mar 10 18:47:54 2011 +0900
+++ b/ARC195OS117-23.tex	Wed Mar 16 19:47:06 2011 +0900
@@ -12,27 +12,6 @@
 \received{22}{7}{17}
 \accepted{22}{9}{17}
 
-% ユーザが定義したマクロなど．
-%\makeatletter
-%\let\@ARRAY\@array \def\@array{\def\<{\inhibitglue}\@ARRAY}
-%\def\<{\(\langle\)\nobreak}
-%\def\>{\nobreak\(\rangle\)}
-%%\def\|{\verb|}
-%\def\Underline{\setbox0\hbox\bgroup\let\\\endUnderline}
-%\def\endUnderline{\vphantom{y}\egroup\smash{\underline{\box0}}\\}
-%\def\LATEX{\iLATEX\Large}
-%\def\LATEx{\iLATEX\normalsize}
-%\def\LATex{\iLATEX\small}
-%\def\iLATEX#1{L\kern-.36em\raise.3ex\hbox{#1\bf A}\kern-.15em
-%    T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX}
-%\def\LATEXe{\ifx\LaTeXe\undefined \LaTeX 2e\else\LaTeXe\fi}
-%\def\LATExe{\ifx\LaTeXe\undefined \iLATEX\scriptsize 2e\else\LaTeXe\fi}
-%\def\Quote{\list{}{}\item[]}
-%\let\endQuote\endlist
-%\def\TT{\if@LaTeX@e\tt\fi}
-%\def\CS#1{\if@LaTeX@e\tt\expandafter\string\csname#1\endcsname\else
-%	$\backslash$#1\fi}
-
 %\checklines	% 行送りを確認する時に使用
 \begin{document}%{
 % 和文表題
@@ -74,7 +53,7 @@
 verify scalabilty of Cassandra. As a result , We confirm a scalability verification method , 
 feature and scale condition in Cassandra. \\
 In this time , We considered how to secure scalabilty confroming to the verification.
-According as the method , designed CMS and implemented Monotonic Tree-Modification to use data structure of CMS???
+According as the method , We designed CMS and implemented Monotonic Tree-Modification for the CMS's data structure
 
 % 英文概要
 \end{eabstract}
@@ -104,8 +83,9 @@
 
 \subsection{SEDA}
 SEDA(Staged Event-Driven Architecture)は, Cassandraで使用されているアーキテクチャである\cite{SEDA1}\cite{SEDA2}. 処理を複数のステージに分解しタスクキューとスレッドプールを用意し処理を行う. 処理の様子を図\ref{fig:SEDA}に示す. \\
-タスクが各ステージのタスクキューに入ると, スレッドプールにどれかのスレッドがタスクキューの中からタスクを取り出し処理を行う. 処理が終わるとそのタスクを次のステージのタスクキューに入れる.\\
-このアーキテクチャはマルチスレッドベースなためマルチコアなPCと多数のタスクがある状況で性能を発揮することができる. しかし, あまりにもスレッドプールやタスクが多すぎると, コンテキストに切り替えに時間がかかり性能は低下する. \\
+タスクが各ステージのタスクキューに入ると, スレッドプールにどれかのスレッドがタスクキューの中からタスクを取り出し処理を行う. 処理が終わるとそのタスクを次のステージのタスクキューに入れる.同様にして次のステージのスレッドプールがタスクキューからタスクを受け取り処理を行う．\\
+このアーキテクチャは数多くのスレッドを生成するためマルチコアなPCと多数のタスクがある状況で性能を発揮することができる. \\
+実際，Cassandraには20以上のスレッドが動作している．しかし, あまりにもスレッドプールやタスクが多すぎると, コンテキストに切り替えに時間がかかり性能は低下する. \\
 
 \begin{figure}[!htbp]
 \begin{center}
@@ -127,11 +107,12 @@
 \label{fig:benchmark}
 \end{figure}
 
+この実験では，徐々に負荷をかけるクラスタの台数を増加させ，並列度を上げていく．クラスタすべてが処理を完了するまでの平均をグラフにプロットし，比較した．\\
 \subsubsection{2Coreを搭載したコア数の少ないサーバーを用いた検証}
-ReadはCassandra/MySQLともに，同じような推移の仕方をしているが, Cassandraの方が遅い. しかし, WriteはCassandraの方が断然速く動作している. この実験では, Cassandraの動作を基準に考えたため書き込みのコマンドにREPLACEを使用した. REPLACEは置き換えるようなコマンドである. \\
-そのため, INSERTに比べて多少遅くなる. それがこのグラフに出ているのではないかと考えられる. SEDAは複数のスレッドで動作しているためコア数が少ないサーバーでは性能が出にくいことがわかる. \\
+ReadはCassandra/MySQLともに，似たような性能低下の推移をしていたがCassandraの方が遅い. しかし, WriteはCassandraの方が断然速く動作している. この実験では, Cassandraの動作を基準に考えたため書き込みのコマンドにREPLACEを使用した. REPLACEは置き換えるようなコマンドである. \\
+そのため, INSERTに比べて多少遅くなる.  SEDAは複数のスレッドで動作しているためコア数が少ないサーバーでは性能が出にくいことがわかる. \\
 \subsubsection{4Core8Threadsを搭載したコア数の多いサーバーを用いた検証}
-Read/Write共にMySQLの性能を超えることに成功した. Readにおいてはコア数が少ない場合に超えることが出来なかったが, 並列度が70度付近でMySQLを上回る性能がでている.
+Read/Write共にMySQLの性能を超えることに成功した. Readにおいてはコア数が少ない場合に超えることが出来なかったが, 並列度が70度付近でMySQLを上回る性能がでていた.
 Cassandraの平均時間は並列度が増加しても, MySQLよりは平均時間の上昇は少ない. これは, SEDAの特徴である多くのタスクを並列に実行すると性能を発揮することを確認することが出来た. \\
 また, SEDAはマルチスレッド前提であるため, コア数が少ないサーバーでは性能が出ず, コア数の多いサーバーで性能が発揮できるということが分かる．\\
 \subsubsection{クラスタ化したCassandraを用いた検証}
@@ -276,7 +257,7 @@
 \end{figure}
 
 \subsubsection{CassandraTreeEditor}
-TreeEditorでは，編集する際にNodeをそれぞれコピーするため，Cassandraへのリクエストが複数発生する．しかし，実際にはコピーが終わったあとにまとめてコピーを行えば良い．Cassandraには$batch_mutate$という機能があり，複数のColumnFamilyと複数のColumnに１度で変更を加えることができる．\\
+TreeEditorでは，編集する際にNodeをそれぞれコピーするため，Cassandraへのリクエストが複数発生する．しかし，実際にはコピーが終わったあとにまとめてコピーを行えば良い．Cassandraには\verb+batch_mutate+という機能があり，複数のColumnFamilyと複数のColumnに１度で変更を加えることができる．\\
 CassandraTreeEditorでは，NodeID ColumnFamilyとNode ColumnFamilyへの操作をまとめてリクエストするため，Cassandraへ発生するリクエストの回数は非破壊的に編集した場合でも１回である．
 
 \section{まとめと今後の課題}
@@ -287,15 +268,19 @@
 今後は，開発したデータ構造の性能評価と改良を行う．
 
 \section{謝辞}
+この研究はSymphony社との共同研究「分散化されたテキスト管理システムに関する研究」によって行われました．
+Symphony社の社員を始め，指導教官である河野真治先生には様々な助言や協力をして頂きました．ありがとうございました．
 
 \bibliographystyle{ipsjunsrt}
 \begin{thebibliography}{99}
-\bibitem{SHOSHI1} Cassandraを用いたCMSのPCクラスタを用いたスケーラビリティの検証
-\bibitem{DYNAMO} Dynamo: Amazon's Highly Avaliable Key-value Store
-\bibitem{YCSB} Benchmarking Cloud Serving Systems with YCSB
-\bibitem{SEDA1} The Staged Event-Driven Architecture for Highly-Concurrent Server Applications
-\bibitem{SEDA2} SEDA : An Architecture for Well-Conditioned , Scalable Internet Services
-\bibitem{BIGTABLE} Bigtable : A Distributed Storege System for Structured Data
+\bibitem{SHOSHI1}
+{Shoshi TAMAKI,Shinji KONO}:Cassandraを用いたCMSのPCクラスタを用いたスケーラビリティの検証,ソフトウェア科学会 (2010)
+\bibitem{DYNAMO} {Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati , Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall , Werner Vogels}:
+Dynamo: Amazon's Highly Avaliable Key-value Store , SOSP (2007)
+\bibitem{SEDA1}{Matt Welsh}: The Staged Event-Driven Architecture for Highly-Concurrent Server Applications
+\bibitem{SEDA2}{Matt Welsh, David Culler, Eric Brewer}: SEDA : An Architecture for Well-Conditioned , Scalable Internet Services , SOSP (2001)
+\bibitem{BIGTABLE}{Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach
+Mike Burrows, Tushar Chandra, Andrew Fikes, Robert E. Gruber}: Bigtable : A Distributed Storege System for Structured Data
 \end{thebibliography}
 
 \end{document}
Binary file fig/desttree.pdf has changed
Binary file fig/monotree.pdf has changed
Binary file graffle/desttree.graffle has changed
--- a/graffle/monotree.graffle	Thu Mar 10 18:47:54 2011 +0900
+++ b/graffle/monotree.graffle	Wed Mar 16 19:47:06 2011 +0900
@@ -1146,7 +1146,7 @@
 {\colortbl;\red255\green255\blue255;}
 \pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\qc\pardirnatural
 
-\f0\fs24 \cf0 11}</string>
+\f0\fs24 \cf0 100}</string>
 			</dict>
 		</dict>
 		<dict>
@@ -1790,7 +1790,7 @@
 		</dict>
 	</array>
 	<key>ModificationDate</key>
-	<string>2011-03-10 16:20:22 +0900</string>
+	<string>2011-03-16 19:43:45 +0900</string>
 	<key>Modifier</key>
 	<string>suika6039</string>
 	<key>NotesVisible</key>
@@ -1856,11 +1856,11 @@
 		<key>DrawerWidth</key>
 		<real>209</real>
 		<key>Frame</key>
-		<string>{{-1603, -85}, {1142, 781}}</string>
+		<string>{{-852, -1}, {1142, 778}}</string>
 		<key>ShowRuler</key>
 		<true/>
 		<key>VisibleRegion</key>
-		<string>{{0, 0}, {1111, 621}}</string>
+		<string>{{0, 0}, {1111, 618}}</string>
 		<key>Zoom</key>
 		<real>1</real>
 	</dict>