Multi-PAXOS擬似コード

PAXOSの説明はWikipediaで

元々のPAXOSのうち、同じProposerから連続してproposeされる時、チョット効率よく処理をする改良としてMulti-PAXOSというアルゴリズムがある。そのMulti-PAXOSの擬似コードが無かったので作った。まだ試していないので動くかどうかは不明。

  • iの扱いが省略されていたのでnと同じように追加。
  • 参考資料でiの扱いが簡潔に書かれていたり、元の論文がふんわりしているのは、PAXOS以前の実装・条件に依存する動作があるためと思われる。下記の擬似コードも自分で使う用に補完している。
  • 送信コマンドと返信コマンドがペアリングできる必要があるのでは？基本的なPAXOSの擬似コードではnはローカル変数で、ペアリングのキーになっているようだ。
  • 基本的なPAXOSのProposer-5の動作は、Proposerがacceptコマンドを過半数に送り切る前に死んだ場合、Learnerが状態を確定できない状態を対策するためにあるようだ。同状態の検知はLearnerで検知できるので、ProposerがやるよりLearnerがやったほうが状態がわかりやすいかと。
  • Alloyなどの形式手法でうまく動くかどうか確認したいけど、どうやるんだろうね？

参考

もともとのPAXOSの擬似コード

http://people.csail.mit.edu/alinush/6.824-spring-2015/paxos-algorithm.html

   --- Paxos Proposer ---

 1  proposer(v):
 2    while not decided:
 2      choose n, unique and higher than any n seen so far
 3      send prepare(n) to all servers including self
 4      if prepare_ok(n, na, va) from majority:
 5        v' = va with highest na; choose own v otherwise   
 6        send accept(n, v') to all
 7        if accept_ok(n) from majority:
 8          send decided(v') to all


    --- Paxos Acceptor ---

 9  acceptor state on each node (persistent):
10   np     --- highest prepare seen
11   na, va --- highest accept seen

12  acceptor's prepare(n) handler:
13   if n > np
14     np = n
15     reply prepare_ok(n, na, va)
16   else
17     reply prepare_reject


18  acceptor's accept(n, v) handler:
19   if n >= np
20     np = n
21     na = n
22     va = v
23     reply accept_ok(n)
24   else
25     reply accept_reject

作った擬似コード

■Client/Learner

値Vを設定するとき
  • Proposerにset(V)を送る
reply_set()を受信したとき
  • 完了
値を取得する時
  • 全てのAcceptorにlearn()を送る
reply_learn(n, i, v)を受信したとき
  • if 受信した{n, i, v}の数を集計し、過半数を獲得したものがある
    • {n, i, v}を採用
  • else
    • 全てのAcceptorにlearn()を送る

■Proposer

初期状態
  • np=0
  • ip=0
  • reset=true
set(v)を受信したとき
  • np+=1
  • vp=v
  • if reset==true
    • 全てのAcceptorにprepare(np)を送る
  • else
    • 全てのAcceptorにaccept(np, ip, vp)を送る
reply_prepare(res, n, i)を受信したとき
  • if res=='ok'がAcceptor過半数
    • ip=max(i)+1
    • 全てのAcceptorにaccept(np, ip, vp)を送る
  • else(返事が来ない、'ng'が来たなどが過半数)
    • np=max(n)+1
    • reset=true
    • 全てのAcceptorにprepare(np)を送る
reply_accept(res, n, i)を受信したとき
  • if res=='ok'がAcceptor過半数
    • ip=max(i)+1
    • reset=false
    • reply_set()を返信
  • else
    • np=max(n)+1
    • reset=true
    • 全てのAcceptorにprepare(np)を送る

■Acceptor

初期状態
  • np=0
  • na=0
  • ia=0
  • last_nid=null
prepare(n)を受信したとき
  • if n > np
    • if src_nid != last_nid
      • i=0
    • else
      • i=ia
    • reply_prepare('ok', np=n, i)を返信
  • else
    • reply_prepare('ng', na)を返信
accept(n, i, v)を受信したとき
  • if n >= np && ia > i
    • np=na=n, va = v, ia = i, last_nid=src_nid
    • replpy_accept('ok', np, ia)を返信
  • else
    • reply_accept('ng', np)を返信
learn()を受信したとき
  • reply_learn(na, ia, va)を戻す