Mercurial > hg > Papers > 2019 > aka-thesis

comparison slide/slide.md @ 12:2e843f65ac5f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
update
author akahori
date Tue, 19 Feb 2019 15:28:07 +0900
parents 9627f1774b45
children 117794d50054
comparison
equal deleted inserted replaced
11:534d552b4273 12:2e843f65ac5f
8 8
9 - OS単位での分散システム 9 - OS単位での分散システム
10 - ブロックチェーンとは 10 - ブロックチェーンとは
11 - ブロックチェーンのfork 11 - ブロックチェーンのfork
12 - コンセンサスアルゴリズム 12 - コンセンサスアルゴリズム
13 - Proof of Work と Paxos 13 - Proof of Work と Paxos
14 - Christieとは 14 - Christieとは
15 - TopologyManagerの実装 15 - TopologyManagerの実装
16 - PCクラスタ上でPaxosを動かした話 16 - PCクラスタ上でPaxosを動かした話
17 - まとめ 17 - まとめ
18 18
19
20 # OS単位での分散システム 19 # OS単位での分散システム
21 20
22 - コンピュータでデータが壊れることはあり得る. 誤操作や, データの破損, 最悪の場合システムの重要な部分のデータの破損も起こりうる. 21 - コンピュータでデータが壊れることはあり得る. 誤操作や, データの破損, 最悪の場合システムの重要な部分のデータの破損も起こりうる.
23
24 - ブロックチェーンはデータを分散でき, 破損や不整合の検知が可能である. 22 - ブロックチェーンはデータを分散でき, 破損や不整合の検知が可能である.
25
26 - 当研究室ではGearsOS, そしてGearsOSに組み込む予定がある分散フレームワークChristieがある. 23 - 当研究室ではGearsOS, そしてGearsOSに組み込む予定がある分散フレームワークChristieがある.
27
28 - Christieにブロックチェーンを実装し, GearsOSに組み込むことで, GearsOS間の分散システムが可能になる. また, 分散システムを作らずとも, hash chainとしてデータの破損を検知できる. 24 - Christieにブロックチェーンを実装し, GearsOSに組み込むことで, GearsOS間の分散システムが可能になる. また, 分散システムを作らずとも, hash chainとしてデータの破損を検知できる.
29
30 - よって, Christieにブロックチェーンを実装する. 25 - よって, Christieにブロックチェーンを実装する.
31
32 26
33 # ブロックチェーンとは 27 # ブロックチェーンとは
34 28
35 ブロックチェーンとは分散型台帳技術と呼ばれる. 複数のトランザクションをまとめたブロックをつなげたものを, 台帳と呼ぶ. その台帳をシステムに参加しているすノードが参照できる技術である. 29 ブロックチェーンとは分散型台帳技術と呼ばれる. 複数のトランザクションをまとめたブロックをつなげたものを, 台帳と呼ぶ. その台帳をシステムに参加しているノードが保持する技術である.
36 30
37 ノード同士はP2Pでつながっており, 対等である. そのため, 管理者がいなくてもデータの管理が行える. 31 ノード同士はP2Pでつながっており, 対等である. そのため, 管理者がいなくてもデータの管理が行える.
32
33 # ブロックチェーンとは
34
35 <div style="text-align: center;">
36 <img src="./images/blockchain.svg" alt="blockchain" width="1000" height="600">
37 </div>
38 38
39 # ブロックチェーンとは 39 # ブロックチェーンとは
40 40
41 ブロックチェーンにも種類がある. パブリックブロックチェーンとプライベートブロックチェーンである. 以下に, その違いを述べる. 41 ブロックチェーンにも種類がある. パブリックブロックチェーンとプライベートブロックチェーンである. 以下に, その違いを述べる.
42 42
51 51
52 ブロックがいたるところで作られると, 異なる高さの違うチェーンが複数できる. この状態をforkという. 52 ブロックがいたるところで作られると, 異なる高さの違うチェーンが複数できる. この状態をforkという.
53 53
54 forkが起こった場合, どちらかを正しいものとしてブロックを積み上げたい. そのため, コンセンサスアルゴリズムを用いて, どちらか1方に統合する. 54 forkが起こった場合, どちらかを正しいものとしてブロックを積み上げたい. そのため, コンセンサスアルゴリズムを用いて, どちらか1方に統合する.
55 55
56
57 # コンセンサスアルゴリズム 56 # コンセンサスアルゴリズム
58 57
59 - コンセンサスアルゴリズムは分散環境上で値を一意に決めるためのアルゴリズムである. 58 - コンセンサスアルゴリズムは分散環境上で値を一意に決めるためのアルゴリズムである.
60 - Paxos, Raftなどが有名. 簡単に言えば多数決を安全に行うためのアルゴリズム. 59 - Paxos, Raftなどが有名. 簡単に言えば多数決を安全に行うためのアルゴリズム.
61 - 故障モデルというものがあって, コンセンサスアルゴリズムでレベルが4段階ある. Paxos, Raftはレベル3で, ノードに裏切り者がいなければ安全に動く. 60 - 故障モデルというものがあって, コンセンサスアルゴリズムでレベルが4段階ある. Paxos, Raftはレベル3で, ノードに裏切り者がいなければ安全に動く.
62 - PBFTがレベル4である<s>が読んでないのでわからない</s> 61 - PBFTがレベル4である<s>が読んでないのでわからない</s>
63
64 - Proof of Workを使っているパブリックブロックチェーンは「ブロックが多ければ多いほど」, レベル4に近づく. 62 - Proof of Workを使っているパブリックブロックチェーンは「ブロックが多ければ多いほど」, レベル4に近づく.
65 63
66 # パブリックブロックチェーンのコンセンサスアルゴリズム 64 # パブリックブロックチェーンのコンセンサスアルゴリズム
67 65
68 - パブリックブロックチェーンのコンセンサスアルゴリズムは, 「ある程度ブロックの差がついたら, 長い方を正とする」というもの. 66 - パブリックブロックチェーンのコンセンサスアルゴリズムは, 「ある程度ブロックの差がついたら, 長い方を正とする」というもの.
69 67 - これだけだと, 裏切り者が適当なブロックをガシガシ積めば攻撃できるのでレベル4にはなれない. これを大幅に補強したのがProof of Work.
70 - これだけだと, 裏切り者が適当なブロックガシガシ積めば攻撃できるのでレベル4にはなれない. これを大幅に補強したのがProof of Work.
71
72 - Proof of Workは, 簡単に言えばブロックのHashに条件をつけるアルゴリズム. つまり, 新しいブロックを作るのが難しくなる. 68 - Proof of Workは, 簡単に言えばブロックのHashに条件をつけるアルゴリズム. つまり, 新しいブロックを作るのが難しくなる.
73 69 - 新しいブロックを作るのが難しいので, みんなで協力して作ったチェーンが自然に勝つ. また, 改ざんも難しい. ただし, トランザクションの確定が遅い.
74 - 新しいブロックを作るのが難しいので, みんなで協力して作ったチェーンが自然に勝つ. また, 改ざんも難しくなる. ただし, トランザクションの確定が遅い.
75 70
76 # プライベートブロックチェーンのコンセンサスアルゴリズム 71 # プライベートブロックチェーンのコンセンサスアルゴリズム
77 72
78 - プライベートブロックチェーンは管理者が許可するノードしか参加しない. つまり, レベル3のコンセンサスアルゴリズムで十分. 73 - プライベートブロックチェーンは管理者が許可するノードしか参加しない. つまり, レベル3のコンセンサスアルゴリズムで十分.
74 - 新しいブロックもパブリックブロックチェーンより早く作れる.
75 - コンセンサスアルゴリズムの中でPaxosが速いらしいので, 今回はこちらも実装してみます.
79 76
80 - 新しいブロックもパブリックブロックチェーンより早く作れる. 77 # Paxos
81 78
82 - コンセンサスアルゴリズムの中でPaxosが速いらしいので, 今回はこちらも実装してみます. 79 - Lamport先生が「故障モデルレベル3での合意が不可能なのを証明してやる」と言って証明の途中で逆に編み出してしまったらしいアルゴリズム.
80 - レベル3のアルゴリズムの基礎となっている.
81 - proposerが値を提案し, acceptorが決め, Learnerが集計して多数決を取って決まった値を保持.
82
83 # Paxos説明の前の用語説明
84
85 -
86
87 # [25行でわかるPaxosアルゴリズム](http://nil.csail.mit.edu/6.824/2015/notes/paxos-code.html)
88
89 - Proposerは
83 90
84 # Christieとは 91 # Christieとは
85 92
86 - 研究室で使っていたAliceの問題点を解消した, 分散プログラミングを簡単に書けるjavaのフレームワーク. 93 - 研究室で使っていたAliceの問題点を解消した, 分散プログラミングを簡単に書けるjavaのフレームワーク.
87
88 - Continued based C(CbC)と似た書き方が可能. 94 - Continued based C(CbC)と似た書き方が可能.
89
90 - まだAliceから引き継いでない機能でTopologyManagerというものがあるので, それも実装. 95 - まだAliceから引き継いでない機能でTopologyManagerというものがあるので, それも実装.
91 96
92 # TopologyManagerとは 97 # TopologyManagerとは
93 98
94 - TopologyManagerは参加を表明したノード(TopologyNode)を元にTopologyを作る. 99 - TopologyManagerは参加を表明したノード(TopologyNode)を元にTopologyを作る.
95
96 - TopologyManagerは静的Topologyと動的Topologyを作れる. 100 - TopologyManagerは静的Topologyと動的Topologyを作れる.
97
98 - 静的Topologyはdotファイルというものを読み込んで, そのとおりにTopologyを生成する. 101 - 静的Topologyはdotファイルというものを読み込んで, そのとおりにTopologyを生成する.
99
100 - 動的Topologyは参加を表明したノードを動的に配置する. が, 今はTreeしか実装していません. 102 - 動的Topologyは参加を表明したノードを動的に配置する. が, 今はTreeしか実装していません.
101
102 103
103 # PCクラスタ上でPaxosを動かした話 104 # PCクラスタ上でPaxosを動かした話
104 105
105 - ブロックチェーンにおいて, 分散環境上でテストしなければいけないのはコンセンサスアルゴリズムである. そのため, Paxosを実装し, 実際の分散環境上で動かした. 106 - ブロックチェーンにおいて, 分散環境上でテストしなければいけないのはコンセンサスアルゴリズムである. そのため, Paxosを実装し, 実際の分散環境上で動かした.
106
107 - 評価は値が一意に決まるかどうかである. 値が一意に決まるならば, リーダーがコンセンサスをとっても良いし, ブロックについてコンセンサスをとっても良い. 107 - 評価は値が一意に決まるかどうかである. 値が一意に決まるならば, リーダーがコンセンサスをとっても良いし, ブロックについてコンセンサスをとっても良い.
108
109 - 今回は単純化のために, 整数でコンセンサスを取る. 108 - 今回は単純化のために, 整数でコンセンサスを取る.
110 109
111 110
112 # 実験1 111 # 実験1
113 112
116 # 実験3 115 # 実験3
117 116
118 # まとめ 117 # まとめ
119 118
120 - コンセンサスアルゴリズムのPaxosを実装しました. 119 - コンセンサスアルゴリズムのPaxosを実装しました.
121
122 - ブロック, トランザクション, proof of workも実装しました. ただ, トランザクションはファイルのデータを読めるようにはしていません. 120 - ブロック, トランザクション, proof of workも実装しました. ただ, トランザクションはファイルのデータを読めるようにはしていません.
123
124 - これらを繋げてブロックチェーンにできれば, Christieにブロックチェーンが実装されます. パブリックブロックチェーンもプライベートブロックチェーンもどちらも作れます. 121 - これらを繋げてブロックチェーンにできれば, Christieにブロックチェーンが実装されます. パブリックブロックチェーンもプライベートブロックチェーンもどちらも作れます.