Mercurial > hg > Papers > 2014 > nobuyasu-master

comparison slides/index.html @ 78:04f63b011fee

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Writed description of merge
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Mon, 03 Feb 2014 09:43:16 +0900
parents bd73f0e1cdd4
children 2e53de70f64e
comparison
equal deleted inserted replaced
77:bd73f0e1cdd4 78:04f63b011fee
123 <h3> 123 <h3>
124 コンテンツマネジメントシステム(CMS) 124 コンテンツマネジメントシステム(CMS)
125 </h3> 125 </h3>
126 <p>Webコンテンツを構成するテキストや画像などのデジタルコンテンツを管理し配信するシステム。</p> 126 <p>Webコンテンツを構成するテキストや画像などのデジタルコンテンツを管理し配信するシステム。</p>
127 <li>例：ブログツール、Wiki</li> 127 <li>例：ブログツール、Wiki</li>
128 <p>『分散』コンテンツマネジメントシステムに求められること。</p> 128 <p>分散コンテンツマネジメントシステムに求められること。</p>
129 <li>Webコンテンツを分散して管理</li> 129 <li>Webコンテンツを分散して管理</li>
130 <li>スケールアウトするシステム</li> 130 <li>スケールアウトするシステム</li>
131 <p>データ全体の整合性に遅延がある結果整合性でも問題なく。書き込みや読み込みを優先としたデータベースが必要。</p> 131 <p>データ全体の整合性に遅延がある、結果整合性でもよい。書き込みや読み込みを優先としたデータベースが必要。</p>
132 <p>そこで、非破壊的木構造データベースJungleの提案を行った。</p> 132 <p>そこで、非破壊的木構造データベースJungleの提案を行った。</p>
133 </article> 133 </article>
134 134
135 <article> 135 <article>
136 <h3>非破壊的木構造データベースJungle</h3> 136 <h3>非破壊的木構造データベースJungle</h3>
212 </h3> 212 </h3>
213 <p>Jungleは分散設計を行うにあたってGitやMercurialといった分散版管理システムを意識している</p> 213 <p>Jungleは分散設計を行うにあたってGitやMercurialといった分散版管理システムを意識している</p>
214 <p style="margin-top:-10px;">分散版管理システムとは多人数によるソフトウェア開発において変更履歴を管理するシステム</p> 214 <p style="margin-top:-10px;">分散版管理システムとは多人数によるソフトウェア開発において変更履歴を管理するシステム</p>
215 <p style="margin-top:-10px;">分散版管理システムは次の特徴とAPIを持つ</p> 215 <p style="margin-top:-10px;">分散版管理システムは次の特徴とAPIを持つ</p>
216 <ul> 216 <ul>
217 <li>開発者それぞれがリポジトリのクローンを持ち、開発はローカルのリポジトリを通すことで行われる</li> 217 <li>開発者それぞれがリポジトリのクローンしてローカルに持ち、開発はローカルのリポジトリを通すことで行われる</li>
218 <li>ローカルのリポジトリは独立に存在し、サーバ上ある他人のリポジトリから変更履歴をとることができる。また自身の変更履歴を伝えることもできる</li> 218 <li>ローカルのリポジトリは独立に存在し、サーバ上にある他人のリポジトリから変更履歴をとることができる。また自身の変更履歴を伝えることもできる</li>
219 <li>データ更新時に先に別の更新が入っていた(衝突)場合はMergeによりデータの整合性をとる</li> 219 <li>データ更新時に先に別の更新が入っていた(衝突)場合はMergeによりデータの整合性をとる</li>
220 </ul> 220 </ul>
221 </article> 221 </article>
222 222
223 <article> 223 <article>
232 </ul> 232 </ul>
233 <p style="text-align:center;"> 233 <p style="text-align:center;">
234 <img style="height:200px;" src="./images/distributed_repository.png"> 234 <img style="height:200px;" src="./images/distributed_repository.png">
235 </p> 235 </p>
236 <small> 236 <small>
237 <p>分版版管理システムはリポジトリが壊れても別のリポジトリよりデータを復旧できることと、いつでも 237 <p>分版版管理システムはリポジトリが壊れても別のリポジトリよりデータを復旧できることと、push/pullそれとMergeによる整合性
238 読み込みが可能なため、高いスケーラビリティを持っている</p> 238 の確保で、高いスケーラビリティを持っている</p>
239 </small> 239 </small>
240 </article> 240 </article>
241 241
242 <article> 242 <article>
243 <h3> 243 <h3>
290 </table> 290 </table>
291 <p>サーバノード同士でツリートポロジーを形成する。データ編集をどのように行ったのかを示すログ commit log を伝搬させデータの分散を行う。</p> 291 <p>サーバノード同士でツリートポロジーを形成する。データ編集をどのように行ったのかを示すログ commit log を伝搬させデータの分散を行う。</p>
292 </small> 292 </small>
293 </article> 293 </article>
294 294
295 <article>
296 <h3>
297 Mergeによる更新の衝突の解決
298 </h3>
299 <small>
300 <table style="font-size: 0.7em; width:100%;" >
301 <tr>
302 <td><p style="margin-top:-5px; margin-bottom:-5px; text-align:center;"><img src="./images/tree_conflict.png"></p></td>
303 </tr>
304 <tr>
305 <td><p style="margin-top:-5px; margin-bottom:-5px; text-align:center;"><img src="./images/tree_conflict3.png"></p></td>
306 </tr>
307 </table>
308 <p style="margin-top:0px;">上の図は通常のデータ更新を示す</p>
309 <p style="margin-top:-20px;">下の図は、同じ木に対して2つのデータの更新があったが編集を無事終えるケースを示す</p>
310 </small>
311 </article>
312
313 <article>
314 <h3>
315 Mergeによる更新の衝突の解決ができない場合
316 </h3>
317 <table style="font-size: 0.7em; width:100%;" >
318 <tr>
319 <td><p style="margin-top:-5px; margin-bottom:-5px; text-align:center;"><img src="./images/tree_conflict2.png"></p></td>
320 </tr>
321 </table>
322 <p>木の同じノードに対してデータの編集が行われた場合、どのような編集結果にすればよいかわからない。</p>
323 <p>どのような木が組まれ、どのようにデータを保存するかはアプリケーション毎に変わってくる。そのため、アプリケーション毎に
324 Mergeアルゴリズムは考えなくてはならない。</p>
325
326 </article>
295 327
296 <article> 328 <article>
297 <h3> 329 <h3>
298 Jungleの分散実装:掲示板システムにおけるMerge 330 Jungleの分散実装:掲示板システムにおけるMerge
299 </h3> 331 </h3>
300 <p>Mergeとはデータ更新の衝突が起きた際の解決方法</p>
301 <p>Jungleではアプリケーション毎にMergeアルゴリズムを設計</p> 332 <p>Jungleではアプリケーション毎にMergeアルゴリズムを設計</p>
302 <p>後述する性能比較に用いた掲示板システムにおけるMergeの実装を考える</p> 333 <p>後述する性能比較に用いた掲示板システムにおけるMergeの実装を考える</p>
303 <p>掲示板システムにおけるデータ構造を以下に示す</p> 334 <p>掲示板システムにおけるデータ構造を以下に示す</p>
304 <p style="text-align:center;"> 335 <p style="text-align:center;">
305 <img src="./images/bulletinboard.png"> 336 <img src="./images/bulletinboard.png">
325 <td><p style="margin-top:-5px; margin-bottom:-5px; text-align:center;"><img src="./images/merge_impl3.png"></p></td> 356 <td><p style="margin-top:-5px; margin-bottom:-5px; text-align:center;"><img src="./images/merge_impl3.png"></p></td>
326 </tr> 357 </tr>
327 </table> 358 </table>
328 </small> 359 </small>
329 </article> 360 </article>
330
331 361
332 <article> 362 <article>
333 <h3> 363 <h3>
334 分散データベースJungleの評価 364 分散データベースJungleの評価
335 </h3> 365 </h3>
632 </ul> 662 </ul>
633 </article> 663 </article>
634 664
635 <article> 665 <article>
636 <h3> 666 <h3>
667 Mergeは必ずできるのか
668 </h3>
669 <p>Mergeを必ず行うことは難しい</p>
670 <p>例えば、更新するデータが画像だった場合、2つの画像のデータから新しい画像を作るわけにはいかない。</p>
671 <p>後に更新したものを優先するといった方法をとるか、ユーザの選択に委ねるしかない。</p>
672 </article>
673
674
675 <article>
676 <h3>
637 分散Key-ValueストアCassandraの特徴 677 分散Key-ValueストアCassandraの特徴
638 </h3> 678 </h3>
639 <small style="line-height:30px;"> 679 <small style="line-height:30px;">
640 <p>ring型トポロジーを形成。ring上にはHash値があり、書き込むデータのキーのハッシュ値により書き込むノードを決定</p> 680 <p>ring型トポロジーを形成。ring上にはHash値があり、書き込むデータのキーのハッシュ値により書き込むノードを決定</p>
641 <p>1つのデータの複製を最大何とるかというReplication factorの設定がある。</p> 681 <p>1つのデータの複製を最大何とるかというReplication factorの設定がある。</p>