Effective Javaを読んでまとめてみる
はじめに
秋からの業務でJavaを書くこととなった. Javaを使う上での best practiceを学びたいと思い, おすすめされたEffective Javaを読み始めた. 著者の主張を自分なりに解釈してまとめることとする. 項目数が100近くあるので, いくつかに分ける.
Item 1-5
Item 1: constructorよりもstatic factory methodsを使うこと
static factory methodsの利点は以下である:
- 利点1 : 名前がつけられること
- 利点2 : immutable (呼び出されるときに新しいobjectを作る必要がない)
- 利点3 : 柔軟性(任意のsub typeを返り値として設定可能)
- 利点4 : input parameterであるfunctionによって, 返り値となるobjectを変化させることができる
利点5 : 返り値となるobjectが不要
欠点1 : sub classにできない (public/protected constructorがないclassのため)
- 欠点2 : プログラマにとって, static factory methodsを見つけるのが難しい
Item 2: constructorのparameterが多数のときにはbuilder patternを利用すること
objectを作成する書き方は大きく3種類ある.
Telescoping constructor pattern
個々の引数に応じてconstructorをオーバーロードしまくるパターン.
見ての通りスケールしない.
public class NutritionFacts {
private final int servingSize; // (ml) required
private final int servings; // (per container) required
private final int calories; // (per serving) optional
private final int fat; // (g/serving) optional
private final int sodium; // (mg/serving) optional
private final int carbohydrate; // (g/serving) optional
public NutritionFacts(int servingSize, int servings) {
this(servingSize, servings, 0);
}
public NutritionFacts(int servingSize, int servings, int calories) {
this(servingSize, servings, calories, 0);
}
...
}
JavaBeans Pattern
default valueを埋め, setterを利用して値を代入する.
public class NutritionFacts {
private final int servingSize = -1;
private final int servings = -1;
private final int calories = 0;
private final int fat = 0;
private final int sodium = 0;
private final int carbohydrate = 0;
public NutritionFacts() { }
....
Builder Pattern
public class NutritionFacts {
private final int servingSize;
private final int servings;
private final int calories;
private final int fat;
private final int sodium;
private final int carbohydrate;
public static class Builder() {
// Required parameters
private final int servingSize;
private final int servings;
// Optional parameters - initialized to default values
private final int calories;
private final int fat;
private final int sodium;
private final int carbohydrate;
public Builder(int servingSize, int servings) {
this.servingSize = servingSize;
this.servings = servings;
}
public Builder calories(int val) {
calories = val;
return this;
}
public Builder fat(int val) {
fat = val;
return this;
}
public Builder sodium(int val) {
sodium = val;
return this;
}
public Builder carbohydrate(int val) {
carbohydrate = val;
return this;
}
public NutritionFacts build() {
return new NutritionFacts(this);
}
}
private NutritionFacts(Builder builder) {
servingSize = builder.servingSize;
servings = builder.servings;
calories = builder.calories;
fat = builder.fat;
sodium = builder.sodium;
carbohydrate = builder.carbohydrate;
}
}
以下のように利用できる.
NutritionFacts cocaCola = new NutritionFacts.Builder(240, 8).calories(100).sodium(35).carbohydrate(27).build()
mandatory parametersはbuilder constructorに引き渡し, optionalなparametersは個別にsetしてbuildする.
このように多数のparametersがある際にはbuilder patternが有効である.
Item 3: singleton propertyにはenumを強いること
singletonの実装には大きく3つの方法がある.
public final fieldで定義
public class Elvis {
public static final Elvis INSTANCE = new Elvis();
private Elvis() { ... }
public void leaveTheBuilding() { ... }
}
- 利点1: singletonのクラスであることが自明
- 利点2: 簡潔
static factory
Date classなどでよく使われている実装方法である.
public class Elvis {
private final Elvis INSTANCE = new Elvis();
private Elvis() { ... }
public static Elvis getInstance() { return INSTANCE; }
public void leaveTheBuilding() { ... }
}
- 利点1: 柔軟性がある (例. Factoryはsingletonじゃないobjectを返す, といった変更がAPIを変えずに可能)
- 利点2: genericsを使ったsingleton factoryを利用できる
singletonであることを保証するため, すべてのinstance fieldにtransientを宣言してreadResolve methodを定義する必要がある. そうしなければ, instanceがdeserializeされた際に新しいinstanceが生成されてしまう.
private Object realResolve() {
return INSTANCE;
}
enum
public enum Elvis {
INSTANCE;
public void leaveTheBuilding() { ... }
}
- 利点1: public final field の方法よりも簡潔
- 利点2: 自動的にserializationできる
- 利点3: 単一instanceを保証できる (serializationやreflectionされた場合においても可能)
よって, singletonにはenumを利用するのが最も良い.
Item 4: private constructorにはnoninstantiabilityを強いること
noninstantiableはconstructorを呼び出すことを許さないことである. noninstantiabilityを得るため, 以下の例では privateなconstructorに AssertionError() を入れている.
public class UtilityClass {
// Suppress default constructor for noninstantiability
private UtilityClass() {
throw new AssertionError();
}
}
これにより, constructorが呼ばれないことを保証できる.
Item 5: ハードコード.singletonよりもDIをすること
以下に SpellCheckerクラスを示す.
public class SpellChecker {
private static final Lexicon dictionary = ...;
private SpellChecker() {} // Noninstantiable
public static boolean isValid(String word) { ... }
public static List<String> suggestions(String typo) { ... }
}
この例では dictionary をハードコーディングしている.
ハードコーディングには大きく2つの欠点がある: - 欠点1: 柔軟性...言語(日本語, 英語など)によってdictionaryは異なるはずなのに, ハードコーディングでは柔軟に変更できない. - 欠点2: テスタビリティ...SpellCheckerクラスがdictionaryに依存しているため, テストが実施できない.
その他の方法として, SeppCheckerをsingletonとして実装することも可能である. しかしながら, こちらもハードコーディングと同様に柔軟性とテスタビリティの観点から避けるべきである. これらの欠点を克服するために, DIをすべきである.
public class SpellChecker {
private static final Lexicon dictionary;
// DI
private SpellChecker(Lexicon dictionary) {
this.dictionary = Objects.requireNonNull(dictionary);
}
public static boolean isValid(String word) { ... }
public static List<String> suggestions(String typo) { ... }
}
次回は Item6-10 をまとめる.
Sort-Tile-Recursive (STR) algorithmの論文についてまとめてみる
これは何?
Sort-Tile-Recursive (STR) algorithm に関して日本語・英語で説明された記事がなかった (+英語で書かれたスライドが間違っていた) ため, 原論文を読んでまとめることとした.
Sort-Tile-Recursive (STR) とは?
R-treeと共に用いられるpacking algorithmの一種である.
以下の論文で提案されている.
何に使うの?
幾何データを管理するインデックスとして使われている.
例えばGoogleのGeofencingシステムでは, 空間インデックスとしてSTR-treeが利用されている. これは幾何計算ライブラリJTS Topology Suiteに実装されているものを利用している.
R-treeとは?
木構造の一種である. 主に多次元データ(平面図形, 位置座標, 立体図形等)を管理するのに用いられる.
例えば以下の図は, R1からR19までの長方形データを管理するR-treeの例である. 複数の矩形をまとめて新たな長方形 (=ノード) とすることで, 空間クエリによる問い合わせを効率よく処理する. ここでいう「効率のよさ」とは, 空間クエリに対して無関係な長方形がヒットしないことを指す.
packing algorithmとは?
packing algorithm: 複数あるデータをまとめる (=packingする) アルゴリズムである.
論文中では特に, R-treeに合わせて用いるpacking algorithmとしてNearest-X (NX), Hilbert Sort (HS), Sort-Tile-Recursive (STR)の三種類を比較して評価している.
三種類に共通する処理
R-tree構築の処理フローを述べる.
定義
r: 長方形データ数
Minimum Bounding Rectangle (MBR): その図形を囲う最小外接矩形
ページ番号: グループの識別子
処理フロー
r個の長方形データをceil(r/b)個のグループb個にpackingする.
各グループのMBRとページ番号を出力する. ページ番号は子ポインタとして, 次のより高いレベル(=浅い深さ)のノードで利用される.
最初にpackingすることで, 各グループは要素数がbで, 最後のグループはb以下の要素数となる. これらのグループはすべて同じ葉レベル (=根から同じ深さ)になる.
例えば下図のようにr=13, b=6とする. この時 ceil(13/6) = 3であるので, グループは6,6,1で分けられる.
長方形を何らかのpacking algorithmでpackingして高レベルのノードを作る, といった処理を再帰的に実施する.
本稿ではNXとHSについては触れず, STRを対象とする.
STRによるpacking
多次元に拡張できるアルゴリズムであるが, 本稿では2次元についてのみ対象とする.
定義
r: 長方形データ数
P: グループ数
S: スライス数
前提
r個の超長方形で構成されるk次元のデータファイルを考える.
超長方形: 各k次元は区間 [Ai, Bi] (1<=i<=k) 内に存在する (例. k=2であれば長方形が最大b個存在)
k=1の時
B-treeと同じ
k=2の時
2次元平面上で空間をいくつかにスライス(=分割)することを考える. スライスされた部分空間をtileと呼ぶ.
P = ceil(r/b), S = ceil(sqrt(P))とする.
r個の長方形について, それぞれの中心点(x, y)を計算する.
中心点のx座標で全長方形をソートし, S本の縦線でスライスする.
中心点のy座標で各slice内の長方形をソートし, b個ずつpackingしてノードとする.
手順2では, R2のx座標 < R1のx座標であるため順序を入れ替えている.
手順3では, y座標で昇順ソートした後に高いレベルのノードを生成する.
sliceされる際, 個々のtileは計Sb個の長方形を含む. 最後のtileはSb以下の長方形を含む.
k>2の時
k=2を一般化することができる. 内容省略.
STRで何が嬉しいの?
定性的
x軸とy軸でソートを繰り返すため, 各長方形が可能な限り正方形上に近い形でpackingされる.
定量的
空間クエリの問い合わせに対するディスクアクセス回数が減少 (HS, NXと比べて)
ディスクアクセス回数が少ない->クエリに不要なデータを検索していない->効率がよい, というロジックである.
しかしながら, 図形・クエリサイズによってはHSに負けてしまうこともある. 特にCFDデータセットを用いた場合はHSに負けている.
まとめ
論文に謎の変数nが誤植されていたり, 唯一存在した解説スライド(英語)が間違っていたりと色々ありましたが, 実際に論文のほう読んで理解できたので良かったです.
冒頭でも述べましたが, JTS Topology Suiteで実装されているほど有名な空間インデックスなので, 空間クエリの種類や管理するデータの特性によってはお世話になるかと思います.
時間があればHSも調べてみたいです. おわり.
今更ながらJavaでSortアルゴリズムを実装した
はじめに
Javaに親しむ一貫として、有名なSortアルゴリズムを3つ実装してみた。
今回実装したのは、QuickSort、BucketSort、MergeSortの3つ。
(ジェネリクスの扱いになれてなくて、結局int型配列で実装した)
package motacapla.lib; public class Sort<T> { private final int[] array; public Sort(int[] array) { this.array = array; } public int[] quickSort() { quickSortRecur(0, array.length-1); return array; } private void quickSortRecur(int left, int right) { if(left >= right) return; int pivot = array[(left+right)/2]; while(left <= right) { while(pivot > array[left]) left++; while(pivot < array[right]) right--; if(left <= right) { int tmp = array[left]; array[left] = array[right]; array[right] = tmp; left++; right--; } } quickSortRecur(left, pivot); quickSortRecur(pivot, right); } public int[] bucketSort(int maxValue) { int[] answer = new int[maxValue+1]; for(int i=0; i<array.length; i++) answer[array[i]]++; int[] answerArray = new int[array.length]; for(int i=0, j=0; i<answer.length; i++) { while(answer[i] > 0) { answerArray[j] = i; answer[i]--; j++; } } return answerArray; } public int[] mergeSort() { mergeSortRecur(0, array.length-1); return array; } private void mergeSortRecur(int l, int r) { if (l < r) { int m = (l+r)/2; mergeSortRecur(l, m); mergeSortRecur(m+1, r); merge(l, m, r); } } private void merge(int l, int m, int r) { int n1 = m - l + 1; int n2 = r - m; int L[] = new int [n1]; int R[] = new int [n2]; for (int i=0; i<n1; ++i) L[i] = array[l + i]; for (int j=0; j<n2; ++j) R[j] = array[m + 1+ j]; int i = 0, j = 0; int k = l; while (i < n1 && j < n2) { if (L[i] <= R[j]) { array[k] = L[i]; i++; } else { array[k] = R[j]; j++; } k++; } while (i < n1) { array[k] = L[i]; i++; k++; } while (j < n2) { array[k] = R[j]; j++; k++; } } }
テスト
1ケースのみだが、テストコードも書いたので以下に示す。
package motacapla.lib; import static org.junit.Assert.*; import org.junit.Test; public class SortTest { static final int ary_size = 10; @Test public void testquickSort() { int [] array = new int[ary_size]; int [] answer = new int[ary_size]; for(int i=0; i<ary_size; i++) { array[i] = ary_size-i; answer[i] = i+1; } Sort<Integer> srt = new Sort<Integer>(array); assertArrayEquals(answer, srt.quickSort()); } @Test public void testbucketSort() { int [] array = new int[ary_size]; int [] answer = new int[ary_size]; int maxValue = 0; for(int i=0; i<ary_size; i++) { array[i] = ary_size-i; answer[i] = i+1; maxValue = Math.max(maxValue, answer[i]); } Sort<Integer> srt = new Sort<Integer>(array); assertArrayEquals(answer, srt.bucketSort(maxValue)); } @Test public void testmergeSort() { int[] actual = { 5, 1, 6, 2, 3, 4 }; int[] expected = { 1, 2, 3, 4, 5, 6 }; Sort srt = new Sort(actual); actual = srt.mergeSort(); for(int i=0; i<actual.length; i++) { System.out.println(actual[i]); } assertArrayEquals(expected, srt.mergeSort()); } }
TODO
RadixSortやHeapSortも実装したい！
合意プロトコル(Consensus Protocol)についてまとめてみる 第3章 3-phase commit (3PC)
この記事は何?
下記の続編で、3記事目である。
というわけで今日は3-phase commit (3PC) についてまとめてみる。
3-phase commit (3PC) とは
commitまでに3つのフェーズが存在し、それらをpassした時にのみcommitする、そうでなければabortする。2PCと凄く似ているが、2PCが同期(ブロッキング)なのに対して3PCは非同期(non-blocking)な合意プロトコルである。
3PCではトランザクションがcommitかabortされる間の時間に上限(time out)を設けている。time outを持っている理由は、デッドロックを回避するためである。
例えば、2PCにおけるcommit-request phaseで、coordinatorがall participantsから返事を受け取ったとしよう。この時coordinatorがロックを取得した後に死ぬと、participantsはデッドロックに陥る。
よって、もしあるトランザクションが3PCによりcommitしようとしてロックを行っている場合、time outによりそのロックが解除されることが保証される。
全体の処理シーケンスは下図になる。
基本的には2PCと同等である。
非常に興味深い点は、coordinatorがpreCommitを実施する際に、participantsからの返事の多数決がyesであれば、commitフェーズに以降して続行される点である。
問題点
- ネットワークがセグメント化された場合に、いかなる方法を持ってしても回復できない
※ Keidar and Dolev's E3PC algorithmでこの欠点を解消している。
- トランザクション完了までに3RTTs(Rount-Trip Time)必要なため、レイテンシが高い。
References
Three-phase commit protocol - Wikipedia
Consensus, Two Phase and Three Phase Commits - Balraja Subbiah - Medium
合意プロトコル(Consensus Protocol)についてまとめてみる 第2章 2-phase commit (2PC)
この記事は何?
下記の続編である。今回は2 Phase Commit (2PC) についてまとめる。
2-phase commit (2PC) とは
2PCはatomic commitment protocol (ACP) の一種である。このatomic commitとは、"変更"操作の集合として処理が実行される/されないが決定することである。つまり全ての変更が実行される or ロールバックされ全て実行されないのいずれかしかないことを意味する(=原子性の保証)。
2PCのイメージを下図に示す。
2PCではリクエストを送る coordinator プロセスと 処理を担う participant(=worker) プロセスが存在する。
2PCという名の通り、第1 Phaseと第2 Phaseの二段階で処理が実施される。
第1 Phaseでは、coordinatorからcommit予定の全participantプロセスに対してprepareリクエストを送信する。ここで全員からYesの返事があれば、第2 Phaseへと進む。timeoutもしくはNoの返事があれば、そこでabortする。
第2 Phaseでは、coordinatorから全participantプロセスに対してcommitリクエストを送信する。ここで全員はcommitを実施し、結果をcoordinatorに送信する。
基本的にはこれだけであるが、異常系についても想像すると面白い。
例. coordinatorが死んだと思っていたら実は生きていた件、coordinatorを復活させるべきヒーラーが死んでいる件
www.slideshare.net
References
Dependency Injection (DI) について入門した話
これは何?
「Dependency Injection (DI) を知ってますか？」と聞かれ、何も分からなかったので調べてまとめました Javaでコードを書いてみたので、参考になればと思います
DIとは
DIは"あるクラスが他クラスのオブジェクトを引数で受けとる"ようなソフトウェアパターンを指します。
逆にDIでないのは"あるクラスが他クラスのオブジェクトを生成する"ようなソフトウェアパターンを指します。
これだけだと分からないので、続けてコードを書いてみましょう。
SampleCode
ここに上げました
Java-practice/src/main/java/motacapla/di at master · motacapla/Java-practice · GitHub
前提
説明のために下記のCatクラスを用意しました、可愛く鳴きます
public class Cat { private String name; public Cat(String name) { this.name = name; } public String meow() { return this.name+"meow!"; } }
DI
DIされた実装は以下になります、Catクラスの変数catを渡しております
public class diSample { private Cat cat; public diSample(Cat cat) { this.cat = cat; } public String call() { return this.cat.meow(); } }
テスト(使い方)は以下になります、newしたものを外から突っ込みます
import static org.junit.Assert.*; import org.junit.Test; public class diSampleTest { @Test public void testNotd() { Cat cat = new Cat("Mike"); diSample di = new diSample(cat); assertEquals("Mikemeow!", di.call()); } }
DIされていない
DIされていない実装です、notdiSampleクラス内でCatクラスのオブジェクトをnewしてますね！これが「依存性(Dependency)」です！
public class notdiSample { private Cat cat; public notdiSample() { this.cat = new Cat("Mike"); } public notdiSample(String s) { this.cat = new Cat(s); } public String call() { return this.cat.meow(); } }
テスト(使い方)は以下になります、直接コンストラクタ呼んじゃうよ〜
import static org.junit.Assert.*; import org.junit.Test; public class notdiSampleTest { @Test public void testDi() { notdiSample di = new notdiSample(); assertEquals("Mikemeow!", di.call()); } @Test public void testDi2() { notdiSample di = new notdiSample("nyan"); assertEquals("nyanmeow!", di.call()); } }
で、結局何が嬉しいの?
DIパターンのPros/Consをまとめました。
Pros.
- Catクラスを呼び出さずにdiSampleクラスを利用できる。
依存性がある場合はdiSampleクラスを利用するために、他クラスの実装も必要になる。
今回はそうでもないが、他クラス(上記例のCatクラス)が大規模で重い場合、メモリ消費量の増加や実行時間の増大につながる。テストをする時にはクリティカルになりえる?
- Catクラスを類似したクラスへ簡単に変えられる
例えばCatクラスを継承したBabyCatクラスを考える。これをdiSampleで利用する場合、引数でBabyCatクラスを渡すだけで良い (はず) 。
- モックを利用できる。 (モックオブジェクトを使ったユニットテストを促進)
送信メッセージ側で一時的にテスト用クラスを作り、モックとして使うことができる。
例えばロガーのモックを使うことで、ログを吐かれることなくdiSampleクラス単体をテストできる。
以下が参考になった。
Cons.
- テストの入力範囲が曖昧になる
- テストの入力パターンが膨大になる
- 引数が膨大になるので、修正する場合に大変 (解決策: DIコンテナを使う)
DIコンテナをよく分からずに使うと サービスロケータパターン になるらしい
DIコンテナ, サービスロケータパターンはまた別の機会で
興味深い議論
以下より抜粋。
"TDD が開始になったとき、論じられた最初の問題の１つが、「テストできるようにするためにコードを変更すべきか」でした。コードの可視度を変えるべきでしょうか。コードのデザインを変えるべきでしょうか。これにより、テスト可能なコードとOOカプセル化の間に衝突が生じているのです。テストを可能にするために、デベロッパがコードの密閉部をさらし始めたのです。最初は密閉フィールドやメソッドでしたが、今ではデザイン全部をさらしているのです。"
まとめ
いかがでしたか？
DIを使う場面も分かったのではないでしょうか！？
(とりあえず競プロのライブラリ整備するところから、言語に慣れるの始めたい...)
TODO: DIコンテナ, サービスロケータパターンの勉強
おわり！
References
猿でも分かる! Dependency Injection: 依存性の注入 - Qiita
合意プロトコル(Consensus Protocol)についてまとめてみる 第1章 概要と背景知識について
この記事は何?
分散環境下において合意を取るためのプロトコルがいくつか存在するので、それらを簡単にまとめることとする。
※分散システムの勉強を兼ねて書いておりますので、間違い等ありましたらご指摘頂けると幸いです。
利用用途
分散合意プロトコルは、以下のようなシチュエーションで使われている:
- リーダ選出 (Leader election)
例. master-slaveモデルの分散システムにおいてmasterがダウンした際に、master eligible nodesから次なるmasterを選出する
- ログ複製の管理 (Replicated state machine)
例. masterが正しいログを保持し、複製を他のnodesに配る
そもそも合意って何?
"The distributed consensus problem deals with reaching agreement among a group of processes connected by an unreliable communications network"
プロセス系全体として一つの値を決定すること、だと解釈している。
例えば5人の人間A,B,C,D,Eが存在し、お昼ご飯について合意を取るとする。
A,B,Cがラーメンを食べる、Dがカレーを食べる、Eが寿司を食べるとなった時、多数決を取り「ラーメンを食べる」で系として合意を得るイメージ?
分散合意プロトコルの話に入る前に、前提となる背景知識について述べる。
背景知識
Byzantine Generals Problem (1982)
Byzantine Generals Problem(ビザンチン将軍問題)は "相互に通信しあう何らかのオブジェクト群において、通信および個々のオブジェクトが故障または故意によって偽の情報を伝達する可能性がある場合に、全体として正しい合意を形成できるかを問う問題" である。 (Wikipediaより)
例え話として、通信など無縁な時代において、小国A, B, C, D, Eの軍隊らが協力し、大国Fを攻めようと画策している状況を考える。
当然A-E単独で攻め込んだところで返り討ちに合うことは目に見えているため、協力して大国Fを攻め落とそうという話になった。
しかし、A-Eは地理的に離れているため、協力するためには攻撃の日を "合意" することで決定する必要がある。
ある小国ともう一方の小国における "通信" 手段は連絡兵を送り合うことのみであるが、小国間には危険な地域があるため、連絡兵がもう一方の小国へ無事に辿り着けない可能性がある。
さらには、A-Eのどれかの国が裏切りを図る可能性もある。
このような状況下でA-E全体として正しい合意を得られるか？を問う問題である。
同期システムの場合、特に弱ビザンチン将軍問題において 3t < n (n: ノード数, t: 障害数) であれば、合意をとることができる (逆にいうと the oral-messages model において3t ≧ n の場合に解決できないことが示されている)
the oral-messages modelは以下参照。
一方、非同期システムの場合、障害が発生した場合において有限時間内に合意を取る方法はない https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf ということがMichael J. Fischer, Nancy Lynch, and Mike Patersonらによって示されている。これをFLP impossibilityと呼び、後述する。
Two general's Problem
Byzantine Generals ProblemはTwo General's Problemを一般化したものである。
つまり、例え話のA-EがA,Bの2つになった問題と解釈してよい。(雑)
FLP impossibility (1985)
Byzantine Generals Problemで触れたFLP impossibilityの話。
非同期システムにおける分散合意の不可能性を説いた論文で、要約すると、
"どのようなプロトコルであっても、たった 1 つでも不完全なプロセスが含まれるのなら終了に達しない可能性を持つことを示している。"
つまり「落ちたか遅延しているかが不明なプロセスが発生した場合、有限時間内で合意に至るアルゴリズムはない」 とのこと。 (論文はまた後日読む)
※ただし前提条件として、故障検知が不可・プログラムが決定的を仮定している。
ちなみに同期システムにおける同問題はByzantine Generals Problemで、合意を取る方法は既にある。
A Brief Tour of FLP Impossibility
論文翻訳: Impossibility of Distributed Consensus with One Faulty Process - MOXBOX / HazMat
分散合意プロトコル
ここでは分散合意プロトコルの種類についてのみ述べる。
個々の内容に関しては非常にボリュームがあるため、次回以降まとめることとする。
- 2相コミット(2 Phase-Commit, 2PC)
PrepareフェーズとCommitフェーズという2段階のフェーズに分かれてトランザクションを実施する。
- 3相コミット(3 Phase-Commit, 3PC)
Voteフェーズ、Prepareフェーズ、Commitフェーズという3段階のフェーズに分かれてトランザクションを実施する。
- Paxos
今日の様々な分散システムの合意をとるために使われているプロトコル。
亜種が非常に多い、難しいことで有名?
Paxosの派生は沢山ある (というか元々のものを忠実に再現することが難しい) らしく、例えばChubbyやApache Zookeeper で採用されている(Zab)は派生の一例である。
- Raft
Diego Ongaro et al.,によって提案されたプロトコル。
Paxosよりも学習者にとって分かりやすいという点を売りにしている。
Paxosよりも制約が多いが、実用上は問題ないとのこと。
特徴として、強力なリーダ選出がある。
- Viewstamped Replication
Paxosに非常に似た手法らしい、あまり情報がなかったので論文を読みたい。
- Mencius
あんまり情報出てこなかった...
それぞれReferencesに参考文献を載せた
(余談) ブロックチェーン?
- Practical Byzantine Fault Tolerance (PBFT)
- Proof of Work (PoW) <- Bitcoinで使われてるやつ
- Proof of Stake (PoS)
次回
2PCからまとめていきます〜！
References
全般
Paxos
ざっくり理解するPaxos - 小野マトペの納豆ペペロンチーノ日記
Paxos, Raftなど分散合意プロトコルを概観する(1) - 備忘録 blog
Raft
Viewstamped Replication
Mencius
Mencius: Building Efficient Replicated State Machines for WANs
