# HG changeset patch # User Nobuyasu Oshiro # Date 1391391508 -32400 # Node ID 2e53de70f64e1ea70a07b3459176f135dd673a39 # Parent 04f63b011feeeee35a841f55469994da09b90401 Fixed slide diff -r 04f63b011fee -r 2e53de70f64e slides/graffle/merge_impl1.graffle --- a/slides/graffle/merge_impl1.graffle Mon Feb 03 09:43:16 2014 +0900 +++ b/slides/graffle/merge_impl1.graffle Mon Feb 03 10:38:28 2014 +0900 @@ -53,6 +53,132 @@ Bounds + {{186, 220}, {69, 36}} + Class + ShapedGraphic + ID + 129 + Shape + Rectangle + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 2A\'82\'f0\'92\'c7\'89\'c1} + + + + Class + LineGraphic + ID + 128 + Points + + {248, 248} + {193, 248} + + Style + + stroke + + HeadArrow + 0 + Legacy + + LineType + 1 + TailArrow + FilledArrow + + + + + Class + LineGraphic + ID + 127 + Points + + {358, 248.69137573242188} + {303, 248.69137573242188} + + Style + + stroke + + HeadArrow + FilledArrow + Legacy + + LineType + 1 + TailArrow + 0 + + + + + Bounds + {{297, 220}, {69, 36}} + Class + ShapedGraphic + ID + 126 + Shape + Rectangle + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 2B\'82\'f0\'92\'c7\'89\'c1} + + + + Bounds {{38.2528076171875, 239}, {69, 36}} Class ShapedGraphic @@ -141,8 +267,8 @@ 122 Points - {450, 260.04291712116543} - {426.49924119410218, 258.7097886371468} + {450, 260.05541113276905} + {426.49922249609187, 258.73079228333796} Style @@ -176,8 +302,8 @@ 121 Points - {107.2528076171875, 256.99997839274545} - {125.46880340576172, 256.99996698411769} + {107.2528076171875, 256.99998639009777} + {125.46880340576172, 256.99998639009777} Style @@ -211,8 +337,8 @@ 120 Points - {402.02946723861231, 329.15684189793234} - {410.64639842655112, 354.60612798829442} + {402.02941558804184, 329.15686304943409} + {410.64627854496194, 354.60617670803515} Style @@ -246,8 +372,8 @@ 119 Points - {161.52946362279454, 329.1568422179347} - {170.14639345951389, 354.60612762643075} + {161.52941197221759, 329.15686336943639} + {170.14627357791323, 354.60617634617159} Style @@ -434,8 +560,8 @@ 113 Points - {387.62236973629228, 328.54183262904701} - {375.97896183908267, 356.16803336448282} + {387.62253883761252, 328.54191891490035} + {375.97938100993071, 356.16824724912578} Style @@ -469,8 +595,8 @@ 112 Points - {380.66432492551081, 322.41374128893654} - {333.54337904264867, 362.29645895690038} + {380.66432871618662, 322.4137467226123} + {333.54339492351937, 362.29648161406601} Style @@ -722,8 +848,8 @@ 102 Points - {147.12236686160171, 328.54183262904706} - {135.47895896439221, 356.16803336448288} + {147.12253596292197, 328.54191891490041} + {135.47937813524018, 356.16824724912584} Style @@ -757,8 +883,8 @@ 101 Points - {140.16432205082012, 322.41374128893665} - {93.043376167957874, 362.29645895690038} + {140.16432584149609, 322.41374672261225} + {93.043392048828608, 362.29648161406601} Style @@ -973,7 +1099,7 @@ MasterSheets ModificationDate - 2014-02-02 18:16:57 +0000 + 2014-02-03 00:45:17 +0000 Modifier Oshiro Nobuyasu NotesVisible diff -r 04f63b011fee -r 2e53de70f64e slides/graffle/merge_impl2.graffle --- a/slides/graffle/merge_impl2.graffle Mon Feb 03 09:43:16 2014 +0900 +++ b/slides/graffle/merge_impl2.graffle Mon Feb 03 10:38:28 2014 +0900 @@ -46,14 +46,162 @@ Creator Oshiro Nobuyasu DisplayScale - 1 0/72 in = 1 0/72 in + 1 0/72 in = 1.0000 in GraphDocumentVersion 8 GraphicsList + Class + LineGraphic + Head + + ID + 125 + + ID + 135 + Points + + {262.72256034511082, 354.76202392578125} + {261.5, 359.05178833007812} + {244.62945929128361, 366.64383849972063} + + Style + + stroke + + HeadArrow + FilledArrow + Legacy + + LineType + 1 + TailArrow + 0 + + + Tail + + ID + 134 + + + Bounds - {{183.10385588268571, 275}, {172, 38.070119395706797}} + {{231.5, 331.76202392578125}, {69, 23}} + Class + ShapedGraphic + ID + 134 + Shape + Rectangle + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 2B\'82\'f0\'92\'c7\'89\'c1} + + + + Class + LineGraphic + Head + + ID + 126 + + ID + 131 + Points + + {500.59607486494139, 354.76202392578125} + {501, 359} + {488.94359478040002, 365.41500959028326} + + Style + + stroke + + HeadArrow + FilledArrow + Legacy + + LineType + 1 + TailArrow + 0 + + + Tail + + ID + 130 + + + + Bounds + {{465, 331.76202392578125}, {69, 23}} + Class + ShapedGraphic + ID + 130 + Shape + Rectangle + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg1252\cocoartf1265 +\cocoascreenfonts1{\fonttbl\f0\fnil\fcharset128 HiraKakuProN-W3;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc + +\f0\fs24 \cf0 2A\'82\'f0\'92\'c7\'89\'c1} + + + + Bounds + {{183.1038639889174, 269}, {172, 38.070119395706797}} Class ShapedGraphic ID @@ -138,8 +286,8 @@ 127 Points - {169.41315739350551, 322.98349027875952} - {211.23798738352451, 361.05360967446632} + {169.41315739350554, 322.98349027875952} + {211.23798738352451, 361.05360967446626} Style @@ -261,8 +409,8 @@ 120 Points - {402.02946723861231, 329.15684189793234} - {410.64639842655112, 354.60612798829442} + {402.02941558804184, 329.15686304943409} + {410.64627854496194, 354.60617670803515} Style @@ -296,8 +444,8 @@ 119 Points - {161.52946362279454, 329.1568422179347} - {170.14639345951389, 354.60612762643075} + {161.52941197221759, 329.15686336943639} + {170.14627357791323, 354.60617634617159} Style @@ -445,8 +593,8 @@ 113 Points - {387.62236973629228, 328.54183262904701} - {375.97896183908267, 356.16803336448282} + {387.62253883761252, 328.54191891490035} + {375.97938100993071, 356.16824724912578} Style @@ -480,8 +628,8 @@ 112 Points - {380.66432492551081, 322.41374128893654} - {333.54337904264867, 362.29645895690038} + {380.66432871618662, 322.4137467226123} + {333.54339492351937, 362.29648161406601} Style @@ -733,8 +881,8 @@ 102 Points - {147.12236686160171, 328.54183262904706} - {135.47895896439221, 356.16803336448288} + {147.12253596292197, 328.54191891490041} + {135.47937813524018, 356.16824724912584} Style @@ -768,8 +916,8 @@ 101 Points - {140.16432205082012, 322.41374128893665} - {93.043376167957874, 362.29645895690038} + {140.16432584149609, 322.41374672261225} + {93.043392048828608, 362.29648161406601} Style @@ -922,7 +1070,7 @@ MasterSheets ModificationDate - 2014-02-02 18:24:21 +0000 + 2014-02-03 00:46:50 +0000 Modifier Oshiro Nobuyasu NotesVisible diff -r 04f63b011fee -r 2e53de70f64e slides/images/merge_impl1.png Binary file slides/images/merge_impl1.png has changed diff -r 04f63b011fee -r 2e53de70f64e slides/images/merge_impl2.png Binary file slides/images/merge_impl2.png has changed diff -r 04f63b011fee -r 2e53de70f64e slides/images/tree_conflict.png Binary file slides/images/tree_conflict.png has changed diff -r 04f63b011fee -r 2e53de70f64e slides/images/tree_conflict2.png Binary file slides/images/tree_conflict2.png has changed diff -r 04f63b011fee -r 2e53de70f64e slides/images/tree_conflict3.png Binary file slides/images/tree_conflict3.png has changed diff -r 04f63b011fee -r 2e53de70f64e slides/index.html --- a/slides/index.html Mon Feb 03 09:43:16 2014 +0900 +++ b/slides/index.html Mon Feb 03 10:38:28 2014 +0900 @@ -207,73 +207,20 @@
-

- Jungleの分散設計:分散版管理システム -

-

Jungleは分散設計を行うにあたってGitやMercurialといった分散版管理システムを意識している

-

分散版管理システムとは多人数によるソフトウェア開発において変更履歴を管理するシステム

-

分散版管理システムは次の特徴とAPIを持つ

-
    -
  • 開発者それぞれがリポジトリのクローンしてローカルに持ち、開発はローカルのリポジトリを通すことで行われる
  • -
  • ローカルのリポジトリは独立に存在し、サーバ上にある他人のリポジトリから変更履歴をとることができる。また自身の変更履歴を伝えることもできる
  • -
  • データ更新時に先に別の更新が入っていた(衝突)場合はMergeによりデータの整合性をとる
  • -
-
- -
-

- Jungleの分散設計:分散版管理システム -

-

分散版管理システムAPI

-
    -
  • commit:データに変更を加えたことをリポジトリに登録
  • -
  • push:ローカルのリポジトリで行った変更履歴を他のリポジトリへまとめて送る
  • -
  • pull:他のリポジトリからの変更履歴をまとめて受け取る
  • -
-

- -

- -

分版版管理システムはリポジトリが壊れても別のリポジトリよりデータを復旧できることと、push/pullそれとMergeによる整合性 - の確保で、高いスケーラビリティを持っている

-
+

+ Jungleの分散設計 +

+

ここまでJungleに実装されている非破壊的木構造の利点について述べた。

+

次に、Jungleにおける分散設計について述べる。

+

データ分散を行うにあたり、まず考えることはトポロジーの形成と他のノードからデータの伝搬の仕方である。

+

Jungleはこの問題に対し、ツリートポロジーを形成し、データ編集の際に発生するcommit logを他のノードに流すことで解決する。

- Jungleの分散設計:分散版管理システム -

-

Jungleと分散版管理システムには似通った点がある

-
  • どちらもデータのコピーが自由
  • -
  • データ更新しても過去のデータに影響を与えない
  • -
    -

    同じAPIを実装することで、分散版管理システムと同じく高いスケーラビリティが期待できる

    -

    具体的には

    -
      -
    • pushやpullによる定期的なデータの更新
    • -
    • Mergeによる更新データ衝突の解決
    • -
    -
    - - -
    -

    - Jungleの分散実装 -

    -

    ここまでJungleの分散設計について説明した。

    -
    -

    これらのシステムを実装する為にまずはJungleのノード同士でネットワークトポロジーを - 組み、その上でデータをやりとりする機構が必要になる。

    -

    そこで、ネットワートポロジーを組みログによるデータの分散を行う仕組みをJungleに実装した。

    -

    また、Mergeの例として掲示板プログラムにおけるMergeの実装も行った。

    -
    - -
    -

    - Jungleの分散実装:ログによるデータ分散 + Jungleの分散設計:トポロジー形成とログによるデータ分散

    -

    今回Jungleの分散実装は以下のように行った

    @@ -293,8 +240,32 @@
    +

    + データ更新衝突の解決 +

    +

    トポロジー形成とデータ伝搬手段については述べた。

    +

    次に問題になることはデータの整合性をどのようにとるかである。

    +

    例えば、ノードの持つデータが全て同じ値にしなければならない場合は、データを持つノード全てにロックを掛けて + 変更を加える必要がある。この方法はスケールしない。

    +

    多少古い値を読んでも問題無く、結果整合性でよいというのなら幾つかのノードに書き込むだけで良い。こちらの方法はスケールする。

    +
    + +
    +

    + 非破壊的木構造の利点を活かした分散設計 +

    +

    Jungleで扱うつもりのデータは結果整合性でもよいCMSを想定していることを始めに説明した。

    +

    そこでJungleはMergeを使うことでデータの整合性をとることにした。

    +

    Mergeとは、2つ以上の変更を1つの変更にまとめることである。

    +

    分散システムにおいては、2つ以上のデータの更新が同じデータに対して行われていた場合、 + 更新を受け取って新しいデータを作ることを指す。

    +

    Mergeは自動で解決出来る場合とそうでない場合がある。

    +
    + + +

    - Mergeによる更新の衝突の解決 + Mergeによる更新の衝突を自然に解決

    ツリートポロジーを形成
    @@ -310,9 +281,11 @@ + +

    - Mergeによる更新の衝突の解決ができない場合 + Mergeによる更新の衝突が自然に解決できない場合

    @@ -327,6 +300,31 @@

    + JungleとMergeの相性 +

    +

    Jungleは非破壊で過去のデータも保持しているため、更新時に過去のデータを参照して自然なMergeを行うことが可能。

    +

    自然にMergeできない場合においても、アプリケーション毎にMergeアルゴリズムを設計することで対応する。

    +

    Mergeが自動で行われるようになれば、Jungleで扱う木構造データは編集を自由に行うことができる。

    +

    木構造データが自由に行えるようになれば、Jungleはデータのリクエストに対して手元のデータを返すことができる。

    +

    古いデータを編集されたものが更新されても、いずれはMergeにより最新のデータと合わせられるから。

    +

    +
    + + +
    +

    + Jungleの分散実装 +

    +

    以上がJungleにおける分散設計になる。

    +
    +

    この分散設計を元にJungleのサーバノード同士でツリトポロジーを構成し、ログによるデータ分散を実装した。

    +

    また、Mergeの例として掲示板プログラムにおけるMergeの実装も行った。

    +
    + + + +
    +

    Jungleの分散実装:掲示板システムにおけるMerge

    Jungleではアプリケーション毎にMergeアルゴリズムを設計

    @@ -688,6 +686,55 @@
    +
    +

    + Jungleの分散設計:分散版管理システム +

    +

    Jungleは分散設計を行うにあたってGitやMercurialといった分散版管理システムを意識している

    +

    分散版管理システムとは多人数によるソフトウェア開発において変更履歴を管理するシステム

    +

    分散版管理システムは次の特徴とAPIを持つ

    +
      +
    • 開発者それぞれがリポジトリのクローンしてローカルに持ち、開発はローカルのリポジトリを通すことで行われる
    • +
    • ローカルのリポジトリは独立に存在し、サーバ上にある他人のリポジトリから変更履歴をとることができる。また自身の変更履歴を伝えることもできる
    • +
    • データ更新時に先に別の更新が入っていた(衝突)場合はMergeによりデータの整合性をとる
    • +
    +
    + +
    +

    + Jungleの分散設計:分散版管理システム +

    +

    分散版管理システムAPI

    +
      +
    • commit:データに変更を加えたことをリポジトリに登録
    • +
    • push:ローカルのリポジトリで行った変更履歴を他のリポジトリへまとめて送る
    • +
    • pull:他のリポジトリからの変更履歴をまとめて受け取る
    • +
    +

    + +

    + +

    分版版管理システムはリポジトリが壊れても別のリポジトリよりデータを復旧できることと、push/pullそれとMergeによる整合性 + の確保で、高いスケーラビリティを持っている

    +
    +
    + +
    +

    + Jungleの分散設計:分散版管理システム +

    +

    Jungleと分散版管理システムには似通った点がある

    +
  • どちらもデータのコピーが自由
  • +
  • データ更新しても過去のデータに影響を与えない
  • +
    +

    同じAPIを実装することで、分散版管理システムと同じく高いスケーラビリティが期待できる

    +

    具体的には

    +
      +
    • pushやpullによる定期的なデータの更新
    • +
    • Mergeによる更新データ衝突の解決
    • +
    +
    +