# HG changeset patch # User akahori # Date 1550580595 -32400 # Node ID 117794d50054718d1bbc0700db404cf93aab9f45 # Parent 2e843f65ac5fd2c791a081702762b3981b445d9a update diff -r 2e843f65ac5f -r 117794d50054 final_main/bibliography.tex --- a/final_main/bibliography.tex Tue Feb 19 15:28:07 2019 +0900 +++ b/final_main/bibliography.tex Tue Feb 19 21:49:55 2019 +0900 @@ -8,38 +8,38 @@ %書籍、論文、URLによって若干書き方が異なる。 %URLを載せる人は参考にした年月日を最後に記入すること。 +\bibitem{christie} +河野 真治. 分散フレームワークChristieと分散木構造データベースJungle, IPSJ SIG Technical Report, May 2018. +\bibitem{christie} +照屋のぞみ. 分散フレームワークChristieの設計, Master’s thesis, 琉球大学 大学院理工学研究科, 2018. \bibitem{bitcoin} Bitcoin: A Peer-to-Peer Electronic Cash System \\ \url{https://bitcoin.org/bitcoin.pdf}\\ -(Accessed: 2018/2/15) +(Accessed: 2019/2/15) \bibitem{ethereum} Ethereum Homestead Documentation \\ \url{http://www.ethdocs.org/en/latest/}\\ -(Accessed: 2018/2/17) +(Accessed: 2019/2/17) \bibitem{paxos} Paxos made Simple \\ \url{https://lamport.azurewebsites.net/pubs/paxos-simple.pdf} -(Accessed: 2018/2/17) - -\bibitem{christie} -照屋のぞみ. 分散フレームワークChristieの設計, Master’s thesis, 琉球大学 大学院理工学研究科, 2018. - +(Accessed: 2019/2/17) \bibitem{torque} TORQUE Introduction. \\ \url{http://docs.adaptivecomputing.com/torque/4-2-8/help.htm#topics/0-intro/introduction.htm\%3FTocPath\%3DWelcome\%7C_____1}\\ -(Accessed: 2018/2/15) +(Accessed: 2019/2/15) \bibitem{qsub-doc} qsub document. \\ \url{http://docs.adaptivecomputing.com/torque/4-0-2/Content/topics/commands/qsub.htm}\\ -(Accessed: 2018/2/15) +(Accessed: 2019/2/15) \end{thebibliography} diff -r 2e843f65ac5f -r 117794d50054 final_main/chapter4/chapter4.tex --- a/final_main/chapter4/chapter4.tex Tue Feb 19 15:28:07 2019 +0900 +++ b/final_main/chapter4/chapter4.tex Tue Feb 19 21:49:55 2019 +0900 @@ -65,11 +65,120 @@ \item ノード間で繋がる前にput操作を行うとデータが送られない. \end{itemize} -Take, Peek操作でSuperClassの型を持ったデータを取り出す際にNullPointerExceptionが表示される問題に対しては, DataGearでdataを代入する際にSuperClass, interfacesまで比較するように書き換えた. また, 型の不一致が起こった際は例外を投げるようにした. TopologyNodeにおいて, 実行するCodeGearをputしておき, 参加するノードがすべて揃ったら, そのCodeGearを実行する. しかし, 実際には実行するCodeGearはCodeGearを継承したものである. Christieは, putされたdataのクラスとTakeされるデータのクラスが一致したならば, dataを代入するという処理を行っている. つまり, SuperClass, interfacesの型までは比較をしない. そのため, 型の不一致が起こり, dataの代入をしないため, NullPointerExceptionが表示されていた. +Take, Peek操作でSuperClassの型を持ったデータを取り出す際にNullPointerExceptionが表示される問題に対しては, DataGearでdataを代入する際にSuperClass, interfacesまで比較するように書き換えた. また, 型の不一致が起こった際は例外を投げるようにした. その修正後のコードをソースコード\ref{code:datagear}に示す. + +\begin{lstlisting}[caption=修正後のDataGearのソースコード,label=code:datagear] +public class DataGear{ + + ... + + public void setData(T data) { + Class dataClazz = data.getClass(); + + if(dataClazz == this.clazz){ + this.data = data; return; + } + + Class dataSuperClazz = dataClazz.getSuperclass(); + while (dataSuperClazz != null) { + if(dataSuperClazz == this.clazz) { + this.data = data; return; + } + dataSuperClazz = dataSuperClazz.getSuperclass(); + } + + Class[] interfaces = dataClazz.getInterfaces(); + for (Class interfaze : interfaces) { + if(interfaze == this.clazz) { + this.data = data; return; + } + } + + throw new ClassCastException("datagear cannot set class from " + dataClazz.getName() + " to " + clazz.getName()); + + } + +} +\end{lstlisting} + +TopologyNodeにおいて, 実行するCodeGearをputしておき, 参加するノードがすべて揃ったら, そのCodeGearを実行する. しかし, 実際には実行するCodeGearはCodeGearを継承したものである. Christieは, putされたdataのクラスとTakeされるデータのクラスが一致したならば, dataを代入するという処理を行っている. つまり, SuperClass, interfacesの型までは比較をしない. そのため, 型の不一致が起こり, dataの代入をしないため, NullPointerExceptionが表示されていた. + + + + +ノード間で繋がる前にput操作を行うとデータが送られない問題に対しては, waitを付け加えた. そのコードをソースコード\ref{code:rdg}に示す. この問題は, ノードが繋がる前にputを行うため, 相手のDataGearに書き込みが行われないために起きた. そのため, 相手とDataGearがつながるまでputメソッドをwaitしておき, つながってからput操作を行うように書き換えた. + +\begin{lstlisting}[caption=修正後のDataGearのソースコード,label=code:datagear] +public class RemoteDataGearManager extends DataGearManager{ + boolean connect = false; + Object lock = new Object(); -ノード間で繋がる前にput操作を行うとデータが送られない問題に対しては, waitを付け加えた. この問題は, ノードが繋がる前にputを行うため, 相手のDataGearに書き込みが行われないために起きた. そのため, 相手とDataGearがつながるまでputメソッドをwaitしておき, つながってからput操作を行うように書き換えた. + public RemoteDataGearManager(final String dgmName, final String address, final int port, CodeGearManager cgm) { + this.cgm = cgm; + RemoteDataGearManager manager = this; + new Thread("Connect-" + dgmName) { + public void run() { + do { + try { + SocketChannel sc = SocketChannel.open(new InetSocketAddress(address, port)); + connection = new Connection(sc.socket(), cgm); + connection.name = dgmName; + connection.socket.setTcpNoDelay(true); + + // add lock + synchronized (lock){ + connect = true; + lock.notify(); + } + } catch (IOException e) { + try { + Thread.sleep(50); + } catch (InterruptedException e1) { + e1.printStackTrace(); + } + } + } while (!connect); + IncomingTcpConnection in = new IncomingTcpConnection(connection); + in.setManager(manager); + in.setName(dgmName+"-IncomingTcp"); + in.setPriority(MAX_PRIORITY); + in.start(); + OutboundTcpConnection out = new OutboundTcpConnection(connection); + out.setName(dgmName + "-OutboundTcp"); + out.setPriority(MAX_PRIORITY); + out.start(); + } + }.start(); -\section{Christieの良い点, 悪い点} + } + + ... + + @Override + public void put(String key, Object data) { + + Command cm = new PutCommand(0, null, key, new DataGear(data)); + + if(!connect) connectWait(); // add wait + + connection.write(cm); + } + + // add method + public void connectWait(){ + synchronized (lock){ + while(!connect){ + try { + lock.wait(); + } catch (InterruptedException e) { + } + } + } + } +} +\end{lstlisting} + +\section{Aliceと比較したChristieの良い点, 悪い点} Christieの元となった分散フレームワークAliceと比較し, Christieの良い点, 悪い点をそれぞれ述べる. 良い点としては次のようなことが挙げられる. @@ -88,6 +197,25 @@ \item デバッグが難しい. cgm.setupでCodeGearが実行されるが, keyの待ち合わせで止まり, どこで止まっているかわからないことが多かった. 例えば, putするkeyのスペルミスなどでコードの待ち合わせが起こり, CodeGearが実行されず, エラーなども表示されずにwaitすることがあり, どこで止まっているかわからない事があった. \end{itemize} +\section{Christieにおけるブロックチェーンの実装の利点と欠点} + +Christieにおいてブロック, トランザクション, Paxos, Proof of Workを実装した. +その際, Christieで実装した場合の便利な点を述べる. + +\begin{itemize} +\item ブロック, トランザクションを送るのが簡単. ChristieはDataGearという単位でデータを保持する. そのため, ブロックやトランザクションはDataGearに包めばいい. +\item TopologyManagerでのテストが便利. dotファイルが有れば, TopologyManagerが任意の形でTopologyを作れる. そのため, ノードの配置については理想の環境を作れるため, 理想のテスト環境を作ることができる. +\item 機能ごとにファイルが実装できるため, 見通しが良い. ChristieはCbCのgotoと同じように関数が終わるとsetupによって別の関数に移動する. そのため自然に機能ごとにファイルを作るため, 見通しが良くなる. +\end{itemize} + +不便な点を以下に述べる. + +\begin{itemize} +\item デバッグが難しい. 4.4の「Christieの良い点, 悪い点」で述べたが, keyのスペルミスなどが起こると, CodeGearが実行されず, waitされる問題が出る. +\item Takeの待ち合わせでCGが実行されない. 2つのCGで同じ変数をTakeしようとすると, setupされた時点で変数がロックされる. このとき, 片方のCGはDGがすべて揃っているのに, すべての変数が揃っていないもう片方のCGに同名の変数がロックされ, 実行されない場合がある. +\end{itemize} + + \newpage diff -r 2e843f65ac5f -r 117794d50054 final_pre/Makefile --- a/final_pre/Makefile Tue Feb 19 15:28:07 2019 +0900 +++ b/final_pre/Makefile Tue Feb 19 21:49:55 2019 +0900 @@ -1,6 +1,6 @@ # Created by Daichi Toma on Nov 16, 2011 -TARGET=finalPre +TARGET=pre LATEX=platex BIBTEX=pbibtex diff -r 2e843f65ac5f -r 117794d50054 final_pre/images/chain-fork.graffle Binary file final_pre/images/chain-fork.graffle has changed diff -r 2e843f65ac5f -r 117794d50054 final_pre/images/chain-fork.pdf Binary file final_pre/images/chain-fork.pdf has changed diff -r 2e843f65ac5f -r 117794d50054 final_pre/images/chain.graffle Binary file final_pre/images/chain.graffle has changed diff -r 2e843f65ac5f -r 117794d50054 final_pre/images/kvm.graffle Binary file final_pre/images/kvm.graffle has changed diff -r 2e843f65ac5f -r 117794d50054 final_pre/images/kvm.pdf Binary file final_pre/images/kvm.pdf has changed diff -r 2e843f65ac5f -r 117794d50054 final_pre/images/paxos.graffle Binary file final_pre/images/paxos.graffle has changed diff -r 2e843f65ac5f -r 117794d50054 final_pre/images/paxos.pu --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/final_pre/images/paxos.pu Tue Feb 19 21:49:55 2019 +0900 @@ -0,0 +1,95 @@ +@startuml +title Paxos1 +/' ======= style ======= '/ + +skinparam sequence { +ArrowColor black +LifeLineBorderColor black + +ParticipantBorderColor black +ParticipantBackgroundColor white +ParticipantPadding 20 +} + +/' ======= node name ======= '/ + +/' === proposers === '/ +participant proposer1 +activate proposer1 +participant proposer2 +activate proposer2 + +/' === acceptors === '/ +participant acceptor1 +activate acceptor1 +participant acceptor2 +activate acceptor2 +participant acceptor3 +activate acceptor3 + +/' === learners === '/ +participant learner1 +activate learner1 + +/' ======= uml ======= '/ + +proposer2 -> acceptor1:Prepare request \n\ +Proposal(8, 2) +proposer2 -> acceptor2 +proposer2 -> acceptor3 + +acceptor1 --> proposer2:Promise Success\n\ +Proposal(8, 2) +acceptor2 --> proposer2:Promise Success\n\ +Proposal(8, 2) +acceptor3 --> proposer2:Promise Success\n\ +Proposal(8, 2) + +proposer1 -> acceptor1:Prepare request \n\ +Proposal(7, 1) +proposer1 -> acceptor2 +proposer1 -> acceptor3 + +acceptor1 --> proposer1:Promise Fail\n\ +Proposal(8, 2) +acceptor2 --> proposer1 +acceptor3 --> proposer1 + +proposer2 -> acceptor1:Accept request \n\ +Proposal(8, 2) +proposer2 -> acceptor2 +proposer2 -> acceptor3 + +acceptor2 --> proposer2:Accept \n\ +Proposal(8, 2) +acceptor2 --> learner1:accept \n\ +Proposal(8, 2) + +proposer1 -> acceptor1:Prepare request \n\ +Proposal(13, 1) +proposer1 -> acceptor2 +proposer1 -> acceptor3 + +acceptor1 --> proposer1:Promise Success\n\ +Proposal(13, 1) +acceptor3 --> proposer1:Promise Success\n\ +Proposal(13, 1) + +acceptor1 --> proposer2:Accept Fail\n\ +Proposal(13, 1) +acceptor3 --> proposer2:Accept Fail\n\ +Proposal(13, 1) +proposer1 -> acceptor1:accept request \n\ +Proposal(13, 1) +proposer1 -> acceptor2 +proposer1 -> acceptor3 + + +acceptor2 --> proposer1:accept \n\ +Proposal(13, 1) +acceptor2 --> learner1:accept \n\ +Proposal(13, 1) + + + +@enduml \ No newline at end of file diff -r 2e843f65ac5f -r 117794d50054 final_pre/images/paxos1.pdf Binary file final_pre/images/paxos1.pdf has changed diff -r 2e843f65ac5f -r 117794d50054 final_pre/images/paxos1.pu --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/final_pre/images/paxos1.pu Tue Feb 19 21:49:55 2019 +0900 @@ -0,0 +1,74 @@ +@startuml +title Paxos 1 +/' ======= style ======= '/ + +skinparam sequence { +ArrowColor black +LifeLineBorderColor black + +ParticipantBorderColor black +ParticipantBackgroundColor white +ParticipantPadding 20 +} + +/' ======= node name ======= '/ + +/' === proposers === '/ +participant proposer1 +activate proposer1 +participant proposer2 +activate proposer2 + +/' === acceptors === '/ +participant acceptor1 +activate acceptor1 +participant acceptor2 +activate acceptor2 +participant acceptor3 +activate acceptor3 + +/' === learners === '/ +participant learner1 +activate learner1 + +/' ======= uml ======= '/ + +proposer1 -> acceptor1:Prepare request \n\ +Proposal(7, 1) +proposer1 -> acceptor2 +proposer1 -> acceptor3 + +acceptor1 --> proposer1:Promise Success\n\ +Proposal(7, 1) +acceptor2 --> proposer1 +acceptor3 --> proposer1 + +proposer2 -> acceptor1:Prepare request \n\ +Proposal(8, 2) +proposer2 -> acceptor2 +proposer2 -> acceptor3 + +acceptor1 --> proposer2:Promise Success\n\ +Proposal(8, 2) +acceptor2 --> proposer2 +acceptor3 --> proposer2 + +proposer2 -> acceptor1:Accept request \n\ +Proposal(8, 2) +proposer2 -> acceptor2 +proposer2 -> acceptor3 + +acceptor1 --> proposer2:Accept \n\ +Proposal(8, 2) +acceptor1 -> learner1:Accept \n\ +Proposal(8, 2) + +acceptor2 --> proposer2:Accept \n\ +Proposal(8, 2) +acceptor2 -> learner1:Accept \n\ +Proposal(8, 2) + +learner1 -> learner1:chosen \n\ +Proposal(8, 2) + +@enduml \ No newline at end of file diff -r 2e843f65ac5f -r 117794d50054 final_pre/images/paxos1.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/final_pre/images/paxos1.svg Tue Feb 19 21:49:55 2019 +0900 @@ -0,0 +1,71 @@ +Paxos 1proposer1proposer1proposer2proposer2acceptor1acceptor1acceptor2acceptor2acceptor3acceptor3learner1learner1Prepare requestProposal(7, 1)Promise SuccessProposal(7, 1)Prepare requestProposal(8, 2)Promise SuccessProposal(8, 2)Accept requestProposal(8, 2)AcceptProposal(8, 2)AcceptProposal(8, 2)AcceptProposal(8, 2)AcceptProposal(8, 2)chosenProposal(8, 2) \ No newline at end of file diff -r 2e843f65ac5f -r 117794d50054 final_pre/images/paxos2.pdf Binary file final_pre/images/paxos2.pdf has changed diff -r 2e843f65ac5f -r 117794d50054 final_pre/images/paxos2.pu --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/final_pre/images/paxos2.pu Tue Feb 19 21:49:55 2019 +0900 @@ -0,0 +1,116 @@ +@startuml +title Paxos 2 +/' ======= style ======= '/ + +skinparam sequence { +ArrowColor black +LifeLineBorderColor black + +ParticipantBorderColor black +ParticipantBackgroundColor white +ParticipantPadding 20 +} + +/' ======= node name ======= '/ + +/' === proposers === '/ +participant proposer1 +activate proposer1 +participant proposer2 +activate proposer2 + +/' === acceptors === '/ +participant acceptor1 +activate acceptor1 +participant acceptor2 +activate acceptor2 +participant acceptor3 +activate acceptor3 + +/' === learners === '/ +participant learner1 +activate learner1 + +/' ======= uml ======= '/ + +proposer1 -> acceptor1:Prepare request \n\ +Proposal(7, 1) +proposer1 -> acceptor2 +proposer1 -> acceptor3 + +acceptor1 --> proposer1:Promise Success\n\ +Proposal(7, 1) +acceptor2 --> proposer1 +acceptor3 --> proposer1 + +proposer2 -> acceptor1:Prepare request \n\ +Proposal(8, 2) +proposer2 -> acceptor2 +proposer2 -> acceptor3 + +acceptor1 --> proposer2:Promise Success\n\ +Proposal(8, 2) +acceptor2 --> proposer2 +acceptor3 --> proposer2 + +proposer1 -> acceptor1:Accept request \n\ +Proposal(7, 1) +proposer1 -> acceptor2 +proposer1 -> acceptor3 + + + +acceptor1 --> proposer1:Accept Fail\n\ +Proposal(8, 2) +acceptor2 --> proposer1 +acceptor3 --> proposer1 + + +proposer2 -> acceptor2:Accept request \n\ +Proposal(8, 2) + +acceptor2 --> proposer2:Accept \n\ +Proposal(8, 2) +acceptor2 -> learner1:Accept \n\ +Proposal(8, 2) + +proposer1 -> acceptor1:Prepare request \n\ +Proposal(13, 1) +proposer1 -> acceptor2 +proposer1 -> acceptor3 + +acceptor2 --> proposer1:Promise Success\n\ +But Accepted \n\ +Proposal(8, 2) +acceptor1 --> proposer1:Promise Success\n\ +Proposal(13, 1) +acceptor3 --> proposer1 + +proposer2 -> acceptor1:Accept request \n\ +Proposal(8, 2) +proposer2 -> acceptor3 + +acceptor1 --> proposer2:Accept Fail\n\ +Proposal(8, 2) +acceptor3 --> proposer2 + +proposer1 -> acceptor1:Accept request \n\ +Proposal(13, 2) +proposer1 -> acceptor2 +proposer1 -> acceptor3 + +acceptor1 --> proposer2:Accept \n\ +Proposal(13, 2) +acceptor1 -> learner1:Accept \n\ +Proposal(13, 2) + + +acceptor2 --> proposer2:Accept \n\ +Proposal(13, 2) +acceptor2 -> learner1:Accept \n\ +Proposal(13, 2) + +learner1 -> learner1:chosen \n\ +Proposal(13, 2) + +@enduml \ No newline at end of file diff -r 2e843f65ac5f -r 117794d50054 final_pre/images/paxos2.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/final_pre/images/paxos2.svg Tue Feb 19 21:49:55 2019 +0900 @@ -0,0 +1,102 @@ +Paxos 2proposer1proposer1proposer2proposer2acceptor1acceptor1acceptor2acceptor2acceptor3acceptor3learner1learner1Prepare requestProposal(7, 1)Promise SuccessProposal(7, 1)Prepare requestProposal(8, 2)Promise SuccessProposal(8, 2)Accept requestProposal(7, 1)Accept FailProposal(8, 2)Accept requestProposal(8, 2)AcceptProposal(8, 2)AcceptProposal(8, 2)Prepare requestProposal(13, 1)Promise SuccessBut AcceptedProposal(8, 2)Promise SuccessProposal(13, 1)Accept requestProposal(8, 2)Accept FailProposal(8, 2)Accept requestProposal(13, 2)AcceptProposal(13, 2)AcceptProposal(13, 2)AcceptProposal(13, 2)AcceptProposal(13, 2)chosenProposal(13, 2) \ No newline at end of file diff -r 2e843f65ac5f -r 117794d50054 final_pre/images/paxos3.pdf Binary file final_pre/images/paxos3.pdf has changed diff -r 2e843f65ac5f -r 117794d50054 final_pre/images/paxos3.pu --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/final_pre/images/paxos3.pu Tue Feb 19 21:49:55 2019 +0900 @@ -0,0 +1,112 @@ +@startuml +title Paxos 3 +/' ======= style ======= '/ + +skinparam sequence { +ArrowColor black +LifeLineBorderColor black + +ParticipantBorderColor black +ParticipantBackgroundColor white +ParticipantPadding 20 +} + +/' ======= node name ======= '/ + +/' === proposers === '/ +participant proposer1 +activate proposer1 +participant proposer2 +activate proposer2 + +/' === acceptors === '/ +participant acceptor1 +activate acceptor1 +participant acceptor2 +activate acceptor2 +participant acceptor3 +activate acceptor3 + +/' === learners === '/ +participant learner1 +activate learner1 + +/' ======= uml ======= '/ + +proposer1 -> acceptor1:Prepare request \n\ +Proposal(7, 1) +proposer1 -> acceptor2 +proposer1 -> acceptor3 + +acceptor1 --> proposer1:Promise Success\n\ +Proposal(7, 1) +acceptor2 --> proposer1 +acceptor3 --> proposer1 + +proposer1 -> acceptor3:Accept Request \n\ +Proposal(7, 1) +acceptor3 --> proposer1: Accept \n\ +Proposal(7,1) +acceptor3 -> learner1:Accept \n\ +Proposal(7, 1) + + +proposer2 -> acceptor1:Prepare request \n\ +Proposal(8, 2) +proposer2 -> acceptor2 +proposer2 -> acceptor3 + +acceptor1 --> proposer2:Promise Success\n\ +Proposal(8, 2) +acceptor2 --> proposer2 +acceptor3 --> proposer2:Promise Success \n\ +But Accepted \n\ +Proposal(7, 1) + +proposer1 -> acceptor1:Accept request \n\ +Proposal(7, 1) +proposer1 -> acceptor2 + +acceptor1 --> proposer1:Accept Fail\n\ +Promised \n\ +Proposal(8, 2) +acceptor2 --> proposer1 + + +proposer1 -> acceptor1:Prepare request \n\ +Proposal(13, 1) +proposer1 -> acceptor2 +proposer1 -> acceptor3 + +acceptor1 --> proposer1:Promise Success\n\ +Proposal(13, 1) +acceptor2 --> proposer1 +acceptor3 --> proposer1 + + +proposer1 -> acceptor1:Accept request \n\ +Proposal(13, 1) +proposer1 -> acceptor2 +proposer1 -> acceptor3 + +acceptor1 --> proposer1:Accept \n\ +Proposal(13, 1) +acceptor1 -> learner1:Accept \n\ +Proposal(13, 1) + +acceptor2 --> proposer1:Accept \n\ +Proposal(13, 1) +acceptor2 -> learner1:Accept \n\ +Proposal(13, 1) + + + +acceptor3 --> proposer1:Accept \n\ +Proposal(13, 1) +acceptor3 -> learner1:Accept \n\ +Proposal(13, 1) + +learner1 -> learner1:chosen \n\ +Proposal(13, 1) + +@enduml \ No newline at end of file diff -r 2e843f65ac5f -r 117794d50054 final_pre/images/paxos3.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/final_pre/images/paxos3.svg Tue Feb 19 21:49:55 2019 +0900 @@ -0,0 +1,97 @@ +Paxos 3proposer1proposer1proposer2proposer2acceptor1acceptor1acceptor2acceptor2acceptor3acceptor3learner1learner1Prepare requestProposal(7, 1)Promise SuccessProposal(7, 1)Accept RequestProposal(7, 1)AcceptProposal(7,1)AcceptProposal(7, 1)Prepare requestProposal(8, 2)Promise SuccessProposal(8, 2)Promise SuccessBut AcceptedProposal(7, 1)Accept requestProposal(7, 1)Accept FailPromisedProposal(8, 2)Prepare requestProposal(13, 1)Promise SuccessProposal(13, 1)Accept requestProposal(13, 1)AcceptProposal(13, 1)AcceptProposal(13, 1)AcceptProposal(13, 1)AcceptProposal(13, 1)AcceptProposal(13, 1)AcceptProposal(13, 1)chosenProposal(13, 1) \ No newline at end of file diff -r 2e843f65ac5f -r 117794d50054 final_pre/images/proof-of-work-fork.graffle Binary file final_pre/images/proof-of-work-fork.graffle has changed diff -r 2e843f65ac5f -r 117794d50054 final_pre/images/proof-of-work-fork.pdf Binary file final_pre/images/proof-of-work-fork.pdf has changed diff -r 2e843f65ac5f -r 117794d50054 final_pre/images/proof-of-work.graffle Binary file final_pre/images/proof-of-work.graffle has changed diff -r 2e843f65ac5f -r 117794d50054 final_pre/images/proof-of-work.pdf Binary file final_pre/images/proof-of-work.pdf has changed diff -r 2e843f65ac5f -r 117794d50054 final_pre/images/ring.pdf Binary file final_pre/images/ring.pdf has changed diff -r 2e843f65ac5f -r 117794d50054 final_pre/images/名称未設定3.graffle Binary file final_pre/images/名称未設定3.graffle has changed diff -r 2e843f65ac5f -r 117794d50054 final_pre/pre.pdf Binary file final_pre/pre.pdf has changed diff -r 2e843f65ac5f -r 117794d50054 final_pre/pre.tex --- a/final_pre/pre.tex Tue Feb 19 15:28:07 2019 +0900 +++ b/final_pre/pre.tex Tue Feb 19 21:49:55 2019 +0900 @@ -3,6 +3,7 @@ \usepackage{picins} \usepackage{fancyhdr} \usepackage{abstract} +\usepackage{here} \usepackage{url} %\pagestyle{fancy} \lhead{\parpic{\includegraphics[height=1zw,keepaspectratio,bb=0 0 251 246]{pic/emblem-bitmap.pdf}}琉球大学主催 工学部情報工学科 卒業研究発表会} @@ -23,14 +24,13 @@ \renewcommand{\abstractname}{Abstract} \begin{document} \title{Blockchain implements in Christie} -%\title{Supporting NAT in Screen Sharing System TreeVNC} \author{155753A 氏名 {赤堀}{貴一} 指導教員 : 河野 真治} \date{} \twocolumn [ \maketitle \begin{onecolabstract} -Data corruption and inconsistency in computers causes severe problem. Therefore, detect corruption and inconsistency by Blockchain. The Blockchain is a distributed system. It is possible to compare between hash value and data which is correct. Even if there are incorrect operation and tampering, data are possible to recover with Blockchain. +Data corruption and inconsistency in computers causes severe problem. Therefore, we detect corruption and inconsistency by Blockchain. The Blockchain is a distributed system. It is possible to compare between hash value and data which is correct. Even if there are incorrect operation and tampering, data are possible to recover with Blockchain. We are developing Christie and GearsOS. Christie is a distributed framework and GearsOS is a Operating System. GearsOS Filesystem will refer to Christie. if implementing block chain in Christie and implementing it in GearsOS, makes it possible to detect data corruption and inconsistency in the GearsOS file system. In addition, it is possible to configure decentralized distributed network between Gears OS. if it does not configure, data is protected. So, our purpose can be achieved. @@ -40,14 +40,13 @@ \section{研究目的} -コンピュータにおいてデータの破損や不整合は深刻な異常を引き起こす原因となる. そのため, 破損, 不整合を検知するためにブロックチェーン技術を用いたい. ブロックチェーンは分散ネットワーク技術であり, データの破損や不整合をハッシュ値によって比較できる. そして, 誤操作や改ざんがあった場合でも, ブロックチェーンを用いることでデータの追跡が行える. +ブロックチェーンとは分散型台帳技術とも呼ばれ, 複数のトランザクションをまとめたブロックをHashでつなげたものを, システムに参加しているすべてのノードが保持できる技術である. -当研究室では分散フレームワークとしてChristieを開発しており, これはGearsOSにファイルシステムに組み込む予定がある. そのため, Christieにブロックチェーンを実装し, GearsOSに組み込むことにより, GearsOSのファイルシステムにおいてデータの破損, 不整合を検知できる. また, GearsOS同士による分散ファイルシステムを構成することができ, 非中央的にデータの分散ができるようになる. もし分散システムを構成しない場合でもデータの整合性保持は行え, 上記の目的は達成できる. +当研究室では分散フレームワークとしてChristieを開発している. これはGearsOSにファイルシステムに組み込む予定がある. そのため, Christieにブロックチェーンを実装し, GearsOSに組み込むことにより, GearsOSのファイルシステムにおいてデータの不整合を検知できる. また, GearsOS同士による分散ファイルシステムを構成することができ, 非中央的にデータの分散ができるようになる. もし分散システムを構成しない場合でもデータの整合性保持は行え, 上記の目的は達成できる. 本研究では, Christieにブロックチェーンを実装し, 実際に学科のPCクラスタ上の分散環境で動かす. \section{ブロックチェーン} -ブロックチェーンとは分散型台帳技術とも呼ばれ, 複数のトランザクションをまとめたブロックをつなげたものを, システムに参加しているすべてのノードが参照できる技術である. ブロックチェーンを実装することは次のようなメリットが有る. \begin{itemize} @@ -65,7 +64,7 @@ ブロックは図\ref{fig:chain}のようにhashでつながっている. 一つのブロックが変更されれば, その後に連なるブロックも整合性が保たれないため, これによってデータの整合性保持が行える. -\begin{figure}[h] +\begin{figure}[H] \centering \fbox{ \includegraphics[scale=0.3]{./images/chain.pdf} @@ -75,7 +74,7 @@ \end{figure} -トランザクション, ブロックともにノード間で伝搬され, ノードごとに検証される. そして検証を終え, 不正なトランザクション, ブロックであれば破棄する. 検証に通った場合は, トランザクションはTransaction PoolにTransactionを貯めておき, ブロックはブロックチェーンに取り組まれ, また検証したノードからトランザクション, ブロックがブロードキャストされる. ノード間はP2Pで通信が行われている. +トランザクション, ブロックともにノード間で伝搬され, ノードごとに検証される. そして検証を終え, 不正なトランザクション, ブロックであれば破棄する. 検証に通った場合は, トランザクションはTransaction PoolにTransactionを貯めておき, ブロックはブロックチェーンに取り組まれ, 検証したノードからトランザクション, ブロックがブロードキャストされる. ノード間はP2Pで通信が行われている. 同時に異なるノードで複数のブロックができることを, forkという. これによってブロックチェーンの分岐が起こる. ブロックチェーンの分岐を収束させるにはコンセンサスアルゴリズムを使用する. @@ -83,8 +82,63 @@ \section{コンセンサスアルゴリズム} コンセンサスアルゴリズムとは, 一意の値を分散環境上で決めるためのアルゴリズムである. -今回は分散アルゴリズムとしてPaxosを実装した. +今回は分散アルゴリズムとしてPaxosを実装した. + +Paxosは3つの役割のノードがある. + +\begin{description} +\item[proposer] 値を提案するノード. +\item[acceptor] 値を決めるノード. +\item[learner] acceptorから値を集計し, 過半数以上のacceptorが持っている値を決める. +\end{description} + +Paxosのアルゴリズムに入る前に, 定義された用語を説明する. 以下にその用語の定義を示す.\begin{description} +\item[提案] 提案は, 異なる提案ごとにユニークな提案番号と値からなる. 提案番号とは, 異なる提案を見分けるための識別子であり, 単調増加する. 値は一意に決まってほしいデータである. +\item[値(提案)がacceptされる] acceptorによって値(提案)が決まること. +\item[値(提案)が選択(chosen)される] 過半数以上のacceptorによって, 値(提案)がacceptされた場合, それを値(提案)が選択されたと言う. +\end{description} + + +Paxosのアルゴリズムは2フェーズある. + +1つ目のフェーズ, prepare-promiseは次のような手順で動作する. +\begin{enumerate} +\item proposerは提案番号nを設定した提案を過半数以上のacceptorに送る. これをprepareリクエストという. +\item acceptorはprepareリクエストが来たら次の動作をする. +\begin{enumerate} +\item もし, 以前に送られたprepareリクエストの提案番号より, 今送られてきたprepareリクエストの提案番号のほうが大きければ, それ以下の提案番号の提案を拒否するという約束を返す. この状態をPromiseしたという. +\item もし, 値がすでにacceptされていれば, accpetされた提案を返す. +\end{enumerate} +\end{enumerate} + +2つ目のフェーズ, accept-acceptedは次のような手順で動作する. +\begin{enumerate} +\item proposerは過半数のacceptorから返信が来たならば, 次の提案をacceptorに送る. これをacceptリクエストという. +\begin{enumerate} +\item もし, 約束のみが返ってきているならば, 任意の値vをprepareリクエストで送った提案に設定する. +\item もし, acceptされた提案が返ってきたら, その中で最大の提案番号を持つ提案の値v'をprepareリクエストで送った提案の値として設定する. +\end{enumerate} + +\item acceptorはacceptリクエストが来た場合, Promiseした提案よりもacceptリクエストで提案された提案番号が低ければ, その提案を拒否する. それ以外の場合はacceptする. +\end{enumerate} + + +このアルゴリズムによって, 各accptorごとに値が一意に決まる. 値を集計, 選択するのはLearnerの役割である. Learnerが値を集計する方法には2つの方法がある. + +\begin{enumerate} +\item Acceptorによって値がacceptされた時に, 各Learnerに送信される. ただし, Message通信量が, $Acceptorの数 \times Learnerの数$になる. +\item 1つのLearnerが各Learnerに選択された値を送信する. 1の方法に比べてMessage通信量が少なくなる($Acceptorの数 + Learnerの数$になる)代わりに, そのLearnerが故障した場合は各LearnerがMessageを受け取れない. +\end{enumerate} + +2つの方法はメッセージ通信量と耐障害性のトレードオフになっていることがわかる. + +Paxosでコンセンサスを取ることは, Proof of Workと比較して次のようなメリットがある. + +\begin{itemize} +\item CPUのリソースを消費しない +\item Transactionの確定に時間がかからない. +\end{itemize} \section{Christie} @@ -103,10 +157,60 @@ CGはCGMによって実行されるが, 実行するにはCGに必要なDGが全て揃う必要がある. もしDGが全て揃わない場合, CGMはずっとlistenし, データが揃うまで実行を待つ. +\section{Christieでのブロックチェーンの実装} +Christieでブロックチェーンのブロック, トランザクション, Paxosを実装した. + +その際の, Christieの便利な点を述べる. + +\begin{itemize} +\item ブロック, トランザクションを送るのが簡単. ChristieはDataGearという単位でデータを保持する. そのため, ブロックやトランザクションはDataGearに包めばいい. +\item TopologyManagerでのテストが便利. dotファイルが有れば, TopologyManagerが任意の形でTopologyを作れる. そのため, ノードの配置については理想の環境を作れるため, 理想のテスト環境を作ることができる. +\item ソースコードの機能ごとにファイルが実装できるため, 見通しが良い. ChristieはCbCのgotoと同じように関数が終わるとsetupによって別の関数に移動する. そのため自然に機能ごとにファイルを作るため, 見通しが良くなる. +\end{itemize} + +不便な点を以下に述べる. + +\begin{itemize} +\item デバッグが難しい. DGでのkeyのスペルミスなどが起こると, CodeGearが実行されず, waitされる問題が出る. +\item TakeFrom, PeekFromの使い方が難しい. TakeFrom, PeekFromは引数でDGM nameを指定する. しかし, DGMの名前を静的に与えるよりも, 動的に与えたい場合が多かった. +\item Takeの待ち合わせでCGが実行されない. 2つのCGで同じ変数をTakeしようとすると, setupされた時点で変数がロックされる. このとき, 片方のCGはDGがすべて揃っているのに, すべての変数が揃っていないもう片方のCGに同名の変数がロックされ, 実行されない場合がある. +\end{itemize} + + + + +\section{実験, 評価} +ブロックチェーンにおいて, 分散環境上でテストしなければいけないのはコンセンサスアルゴリズムである. そのため, Paxosを実装し, 琉球大学のPCクラスタ上で動かした. + +今回は単純化のために, 整数でコンセンサスを取る. ノードはproposerが2つ, acceptorが3つ, learnerが1つという構成で実験する. + +Paxosの実験は3回行った. Paxosにはlog4j2を実装しており, logを取るようにしている. そのため, そのlogから値が一意に決まるまでを調べた. 1つの実験の結果を図\ref{fig:paxos2}に示す. + +\begin{figure}[h] +\centering + \fbox{ + \includegraphics[scale=0.45]{./images/paxos2.pdf} + } +\caption{実験の結果1} +\label{fig:paxos2} +\end{figure} + +実際にLearnerの値が一意に決まっていることがわかる. + + \section{まとめ} +本研究ではブロックチェーンと, 分散環境上で値を一意に決めるコンセンサスアルゴリズムを述べ, Christieという分散フレームワークで実際にPaxosを作り, PCクラスタ上で動かした. その結果, コンセンサスの結果として一意のデータが取り出せることがわかった. + +まだPCクラスタ上ではブロックチェーンを動かすことができない. しかし, Block, Transaction, Hash生成, 署名のためのクラスはいずれも作られている. Transactionにおいてはまだファイルのデータを入れる機能は実装していないが, これらを組み合わせれば簡易的なブロックチェーンが作れる. そのため, あとはPaxosとこれらのクラスをどのようにつなげるかが問題となる. +また, Proof of Workを行うクラスも作られている. そのため, ブロックチェーンが実装できた場合, このクラスを用いてPaxosと速度比較も行える. + +今後の課題としては, Paxosによるブロックチェーンを作り, 分散クラスタ上でファイルのやり取りができるかを見る. その際にどの程度スケーラビリティがあるのか, Proof of Workと比較し, どの程度速度が違うのかを見ていきたい. + + + \nocite{*} \bibliographystyle{junsrt} \bibliography{reference} diff -r 2e843f65ac5f -r 117794d50054 final_pre/reference.bib --- a/final_pre/reference.bib Tue Feb 19 15:28:07 2019 +0900 +++ b/final_pre/reference.bib Tue Feb 19 21:49:55 2019 +0900 @@ -43,6 +43,21 @@ Read = {0}, Title = {Paxos Made Simple}, Year = {2001}} + +@manual{bitcoin, + title = "Bitcoin: A Peer-to-Peer Electronic Cash System", + author = "Satoshi Nakamoto", + url = "https://bitcoin.org/bitcoin.pdf", + year = "Accessed: 2019/2/15" + } + +@manual{ethereum, + title = "Ethereum Homestead Documentation", + author = "", + url = "http://www.ethdocs.org/en/latest/", + year = "Accessed: 2019/2/17" + } + @comment{BibDesk Static Groups{ diff -r 2e843f65ac5f -r 117794d50054 slide/images/accept-accepted.pdf Binary file slide/images/accept-accepted.pdf has changed diff -r 2e843f65ac5f -r 117794d50054 slide/images/accept-accepted.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/slide/images/accept-accepted.svg Tue Feb 19 21:49:55 2019 +0900 @@ -0,0 +1,3048 @@ + +image/svg+xml \ No newline at end of file diff -r 2e843f65ac5f -r 117794d50054 slide/images/blockchain.graffle Binary file slide/images/blockchain.graffle has changed diff -r 2e843f65ac5f -r 117794d50054 slide/images/blockchain.pdf Binary file slide/images/blockchain.pdf has changed diff -r 2e843f65ac5f -r 117794d50054 slide/images/blockchain.png Binary file slide/images/blockchain.png has changed diff -r 2e843f65ac5f -r 117794d50054 slide/images/blockchain.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/slide/images/blockchain.svg Tue Feb 19 21:49:55 2019 +0900 @@ -0,0 +1,950 @@ + +image/svg+xml \ No newline at end of file diff -r 2e843f65ac5f -r 117794d50054 slide/images/paxos1.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/slide/images/paxos1.svg Tue Feb 19 21:49:55 2019 +0900 @@ -0,0 +1,71 @@ +Paxos 1proposer1proposer1proposer2proposer2acceptor1acceptor1acceptor2acceptor2acceptor3acceptor3learner1learner1Prepare requestProposal(7, 1)Promise SuccessProposal(7, 1)Prepare requestProposal(8, 2)Promise SuccessProposal(8, 2)Accept requestProposal(8, 2)AcceptProposal(8, 2)AcceptProposal(8, 2)AcceptProposal(8, 2)AcceptProposal(8, 2)chosenProposal(8, 2) \ No newline at end of file diff -r 2e843f65ac5f -r 117794d50054 slide/images/paxos2.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/slide/images/paxos2.svg Tue Feb 19 21:49:55 2019 +0900 @@ -0,0 +1,102 @@ +Paxos 2proposer1proposer1proposer2proposer2acceptor1acceptor1acceptor2acceptor2acceptor3acceptor3learner1learner1Prepare requestProposal(7, 1)Promise SuccessProposal(7, 1)Prepare requestProposal(8, 2)Promise SuccessProposal(8, 2)Accept requestProposal(7, 1)Accept FailProposal(8, 2)Accept requestProposal(8, 2)AcceptProposal(8, 2)AcceptProposal(8, 2)Prepare requestProposal(13, 1)Promise SuccessBut AcceptedProposal(8, 2)Promise SuccessProposal(13, 1)Accept requestProposal(8, 2)Accept FailProposal(8, 2)Accept requestProposal(13, 2)AcceptProposal(13, 2)AcceptProposal(13, 2)AcceptProposal(13, 2)AcceptProposal(13, 2)chosenProposal(13, 2) \ No newline at end of file diff -r 2e843f65ac5f -r 117794d50054 slide/images/paxos3.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/slide/images/paxos3.svg Tue Feb 19 21:49:55 2019 +0900 @@ -0,0 +1,97 @@ +Paxos 3proposer1proposer1proposer2proposer2acceptor1acceptor1acceptor2acceptor2acceptor3acceptor3learner1learner1Prepare requestProposal(7, 1)Promise SuccessProposal(7, 1)Accept RequestProposal(7, 1)AcceptProposal(7,1)AcceptProposal(7, 1)Prepare requestProposal(8, 2)Promise SuccessProposal(8, 2)Promise SuccessBut AcceptedProposal(7, 1)Accept requestProposal(7, 1)Accept FailPromisedProposal(8, 2)Prepare requestProposal(13, 1)Promise SuccessProposal(13, 1)Accept requestProposal(13, 1)AcceptProposal(13, 1)AcceptProposal(13, 1)AcceptProposal(13, 1)AcceptProposal(13, 1)AcceptProposal(13, 1)AcceptProposal(13, 1)chosenProposal(13, 1) \ No newline at end of file diff -r 2e843f65ac5f -r 117794d50054 slide/images/prepare-promise.pdf Binary file slide/images/prepare-promise.pdf has changed diff -r 2e843f65ac5f -r 117794d50054 slide/images/prepare-promise.svg --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/slide/images/prepare-promise.svg Tue Feb 19 21:49:55 2019 +0900 @@ -0,0 +1,2341 @@ + +image/svg+xml \ No newline at end of file diff -r 2e843f65ac5f -r 117794d50054 slide/slide.html --- a/slide/slide.html Tue Feb 19 15:28:07 2019 +0900 +++ b/slide/slide.html Tue Feb 19 21:49:55 2019 +0900 @@ -86,7 +86,7 @@ @@ -94,7 +94,7 @@

目次

@@ -261,31 +353,44 @@
  • ブロックチェーンにおいて, 分散環境上でテストしなければいけないのはコンセンサスアルゴリズムである. そのため, Paxosを実装し, 実際の分散環境上で動かした.
  • 評価は値が一意に決まるかどうかである. 値が一意に決まるならば, リーダーがコンセンサスをとっても良いし, ブロックについてコンセンサスをとっても良い.
  • 今回は単純化のために, 整数でコンセンサスを取る.
    • +
  • また, ノードはproposerが2つ, acceptorが3つ, learnerが1つという構成で実験する.
    • -

    実験1

    +

    Paxos実験1

    + +
    + blockchain +
    -

    実験2

    +

    Paxos実験2

    + +
    + blockchain +
    -

    実験3

    +

    Paxos実験3

    + +
    + blockchain +
    -

    まとめ

    +

    まとめ