P2P usasabi 1 1 1 1 1 P2P usasabi P2P Counication ethods for Virtual Peers on usasabi P2P Platfor asanori Shikano, 1 Tatsuya Ueda, 1 Kota Abe, 1 Hayato Ishibashi 1 and Toshio atsuura 1 1. Peer-to-Peer(P2P) P2P P2P P2P usasabi 1 1) P2P P2P P2P P2P P2P The authors have been developing usasabi P2P platfor, which supports virtual peers. Virtual peers achieve fault-tolerance of running progra by executing the sae progra on ultiple peers siultaneously. In this paper, counication ethods for virtual peers are described. The ethods take into account the fact that a virtual peer consists of ultiple peers which run in consistent with others, and that the ebership of a virtual peer ight be changed as tie goes on. 仮想ピア A 通常ピア 仮想ピア B 1 Graduate School for Creative Cities, Osaka City University 1 P2P ネットワーク 1 c 2009 Inforation Processing Society of Japan
プロセスプロセスプロセス 仮想ピア制御 プロセス制御 usasabi PIAX Overlay Transport AL Skip Graph プロセス usasabi メンバピア 3 仮想プロセスプロセスプロセス usasabi usasabi メンバピアメンバピア仮想ピア Java V Windows, acos X, Linux, etc. 2 usasabi 2. P2P usasabi P2P usasabi 1) usasabi P2P Java usasabi PIAX 2) 2 usasabi Java usasabi OS 2.1 1 1 3 P2P 2.2 1 Paxos 3),4) Paxos State achine Replication 3) Paxos 2.2.1 Paxos Paxos (ulti-paxos) Paxos 2 c 2009 Inforation Processing Society of Japan
Leader Peer Peer Peer Round Initiation Collect Last Last 4 Begin Propose Accept Accept Success Begin Paxos Propose Accept Accept Success Paxos 4 1 ( 1 ) Collect ( 2 ) Collect Last ( 3 ) Last ( 4 ) Begin Begin ( 5 ) Begin Accept ( 6 ) Accept Success 2.2.2 usasabi Paxos usasabi 3 Paxos usasabi Java Paxos Accept Success 1 4) Paxos Success usasabi 2.3 1 P2P usasabi 1) 3. 3.1 3.2 3.1 p v v p 3.1.1 p v 3 c 2009 Inforation Processing Society of Japan
(AL) AL PIAX P2P 1 Skip Graph 5) v ID(v.id) 1 p v v.id p v v 3.1.2 2.2 Paxos AL Paxos Paxos p v (1) (2) p v p v 3.1.3 ID p v 1 ID ID ID p ID PIAX p ID v ID 3.1.4 v p API 3.1.5 v p p 3.1.2 p v 3.1.6 p ID v ID(v.id) v 3 history reply ID INITIAL PROCESSED REPLIED ) ( 1 ) AL ( a ) history (state) ( b ) state INITIAL Paxos ( c ) state REPLIED reply 4 c 2009 Inforation Processing Society of Japan
( d ) state PROCESSED ( 2 ) Paxos ( a ) history (state) ( b ) state INITIAL ( c ) state PROCESSED ( d ) ( 3 ) (res) API ( a ) (state) REPLIED history ( b ) reply res ( c ) res history reply (1) p v p v p v (2) p ax REPLIED ax 3.1.7 5 6 6 2 1 2 Success(, 100) Success(, 101) 2.2.2 Paxos Success(, 100) 3.2 s r r s マルチキャスト送信 5 通常ピア p ピア 0 仮想ピア v ピア 1 ピア 2 Begin(, 100) Begin(, 100) リーダは を提案 (Paxos シーケンス番号 100) 合意成立プロセスに リーダのみ応答送信 Success(, 100) 既に 100 番は合意されているので無視 Success(, 100) プロセスに プロセスに s r s s r API 3.1 s p 3.2.1 s s l r AL s r AL s l r r s l AL s l s l 2 5 c 2009 Inforation Processing Society of Japan
一定時間後 を再送信 100 番の合意成立プロセスに 一定時間後 を再送信 6 通常ピア p リーダは を提案 (Paxos シーケンス番号 100) ( 再送 ) メッセージ喪失 は未処理 (INITIAL) なので, リーダは を提案 (Paxos シーケンス番号 101) r fo r eply ( 再々送 ) 2 3.2.2 ピア 0 101 番の合意成立 は既に処理中 (PROCESSED) なので, 無視 ピア 1 ピア 2 Begin(, 100) Begin(, 100) ( 再送 ) ( 再送 ) Begin(, 101) Begin(, 101) Success(, 100) Success(, 101) Success(, 101) ( 再々送 ) は既に応答済 (REPLIED) なので, リーダのみ応答再送 仮想ピア v A c cept(100) 100 番の Success が来ていないので待つ Success(, 100) は既に処理中 (PROCESSED) なので, 無視 ( 再々送 ) プロセスに s r s s Paxos 3.2.3 s r s s l r s l : 2 ( 1 ) s s l Success : s l r API s l r API ( 2 ) s l : r r s l : 2 ( 1 ) r s l : s l Paxos ( 2 ) r s l : s (s l) s l Paxos 3.2.4 s r API ( 1 ) ID ID ID ID ID ID ( 2 ) r ID(r.id) 6 c 2009 Inforation Processing Society of Japan
( 3 ) ( 4 ) r s (4) s r (res) 3.1.6 (1) (2) res (2) (c) r 3.1.6 s ID(s.id) 3.2.5 s 7 r s 8 8 s1 100 Paxos Last 3),4) 4. t (RTT) 2t RTT 4.1 RTT p v RTT p AL v PIAX AL Skip Graph log 2 (n) n Skip Graph Paxos 通常ピア p マルチキャスト送信 リーダは を提案 (Paxos シーケンス番号 100) 合意成立プロセスに を処理したプロセスが を r に送信することを決定, リーダのみマルチキャスト送信 リーダは reply for を提案 (Paxos シーケンス番号 101) 合意成立プロセスに reply リーダのみ応答を送信 reply for ピア s0 7 Begin(, 100) Success(, 100) プロセスに を処理したプロセスが を r に送信することを決定, 非リーダは を送信しない reply for Begin(reply, 101) Success(reply, 101) プロセスに reply 仮想ピア s ピア s1 Begin(, 100) Success(, 100) を処理したプロセスが を r に送信することを決定, 非リーダは を送信しない reply for Begin(reply, 101) Success(reply, 101) ピア s2 リーダは を提案 (Paxos シーケンス番号 200) プロセスに reply for プロセスに reply ピア r0 合意成立プロセスに Begin(, 200) Accept(200) Success(, 200) プロセスに 仮想ピア r ピア r1 s Begin(, 200) Accept(200) Success(, 200) プロセスに Begin Accept 2t t p RTT (log 2 (n) + 3)t AL v p v p AL v RTT 4t p p AL ピア r2 7 c 2009 Inforation Processing Society of Japan
通常ピア p リーダは を提案 (Paxos シーケンス番号 100) を処理したプロセスが を r に送信することを決定, リーダのみマルチキャスト送信 新リーダになる, の合意が必要と判断 を処理したプロセスが を r に送信することを決定, リーダのみマルチキャスト送信 reply は未処理 (INITIAL) なので, 新リーダは を提案 (Paxos シーケンス番号 102) 8 100 番の合意成立プロセスに ピア s0 reply for Begin(, 100) 仮想ピア s ピア s1 Begin(, 100) Success(, Success(, 100) 100) 障害発生離脱 リーダの障害検出リーダになろうとする 新リーダは を提案 (Paxos シーケンス番号 100) 100 番の合意成立プロセスに 新リーダは を提案 (Paxos シーケンス番号 101) 101 番の合意成立プロセスに reply リーダのみ応答を送信 Collect Last Begin(, 100) Success(, 100) Begin(reply, 101) Begin(reply, 102) Accept(102) Success(reply, 101) Success(reply, 102) 102 番の合意成立 reply は既に処理中 (PROCESSED) なので, 無視 ピア s2 メッセージ喪失 メッセージ喪失 プロセスに reply reply は既に処理中 (PROCESSED) なので, 無視 仮想ピア r Paxos で を合意 を仮想プロセスで処理リーダは応答をマルチキャスト送信 r s 4.2 RTT s r RTT (2 log 2 (n) + 2)t AL 3.2.1 RTT (log 2 (n) + 3)t 4.1 s r 2 RTT 4t 5. P2P usasabi RTT 2 AL RTT history reply 2 2 (18700069) 1). P2P usasabi., Vol. 2009-IOT-4, pp. 131 136, 2009. 2). P2P PIAX., Vol.49, No.1, pp. 402 413, 2008. 3) Leslie Laport, etal. The part-tie parliaent. AC Trans. on Coputer Systes, Vol.16, pp. 133 169, 1998. 4) Roberto De Prisco, etal. Revisiting the Paxos algorith. In Proc. of 11th Int. Workshop on Distributed Algoriths (WDAG 97), pp. 111 125. Springer-Verlag, 1997. 5) Jaes Aspnes, etal. Skip graphs. AC Trans. on Algoriths, Vol.3, No.4, pp. 1 25, 2007. 8 c 2009 Inforation Processing Society of Japan