ikemonn's blog

技術ネタをちょこちょこと

Paxos Made Simple 読んだ

Paxos Made Simpleを読んだ時のメモ。

どんなもの?

  • Paxos
    • 分散合意アルゴリズム
      • 複数のプロセスが値を提案した時に、どのように1つの値を選ぶかについて

技術や手法の肝は?

  • The Problem

    • safety requirements

      • 提案された値のみが選ばれる
      • 1つの値のみが選ばれる
      • 値が選ばれた後でしたか、その値は使えない
    • roles

      • proposer
      • acceptor
      • learner
    • 1つのprocessが複数のroleを担っても良い

    • 分散システムの問題点
      • Agentは任意の速度で処理を行う
      • 処理が止まって、失敗するかもしれないし再起動するかもしれない
      • メッセージは到達するまで任意の時間がかかる
      • メッセージは重複するかもしれないし、失われるかもしれない
      • メッセージは壊れた状態では届かない
  • Chosing a Value

    • 1つの値を選ぶのに一番簡単な方法はacceptorを1つにすること
      • SPOFになるのでダメ
    • acceptorを複数にし、proposerが複数のacceptorに提案を送る
      • 過半数のacceptorがacceptした値が選ばれるとする
    • P1. acceptorは最初に受け取った提案をacceptしなければならない
      • 同時に異なるproposerからいくつかの値がproposeされて、acceptorがそれぞれ別の値をacceptしていると、どの値も過半数にならない時がある
      • acceptorは1つ以上の提案をacceptできるようにする
        • 提案にユニークなIDをつけるようにする
          • 提案 = (ID, 値)
        • 過半数のacceptorに1つの値がacceptされた時に、値が選ばれたとする
      • 複数の提案を選べるようになると、値がどんどん上書きされていってしまう
    • P2. 値vの提案が選ばれたら、それより大きいIDのproposalの値はvでなければならない
      • 提案が選択されたあとの上書きを防げる
      • 提案は少なくとも1つのacceptorにacceptされる必要がある
    • P2a. 値vの提案が選ばられたら、全てのacceptorによってacceptされたものより大きなIDの提案は値vを持たねばならない
      • これだと、P1が満たせない(acceptorは最初に受け取った提案をacceptせねばならない)
      • 新しいacceptorが異なる値の提案をしたときに、P1を満たすためにはその提案をacceptせねばならない(P2aに違反)
    • P2b. 値vの提案が選ばれたら、それより大きなIDを持つ提案は全て値vを持つ
    • P2c. ID:n, 値:vの提案が発行されたら、下記のようなacceptor群Sが存在しなければならない
      • a) ID:nより小さな提案をacceptしているacceptorはSにはいない
      • b) ID:nより小さい全ての提案の中で最も大きいnumberの提案の値がv
    • ID:n より小さい提案を全部無視して欲しい
    • prepare request
      • ID:n より小さい提案をacceptしないことを約束する
    • accept request
      • 提案を受け入れた
    • P1a. AcceptorはID:nより大きなIDのprepare requestにresponseしていない場合、ID:nの提案をacceptできる
  • Paxos
    • Phase 1
      • ProposerがID:nの提案を選び、prepare reqをacceptorの過半数に送る
      • もしID:nがPromise済みのIDよりも大きければacceptし、違ったら現在acceptしている提案を返す
    • Phase 2
      • ProposerがAcceptorの大半からprepare reqを受け取ったら、それぞれのacceptorに accept reqを送る(ID:n, value:v)
      • acceptorがID:nのaccept reqを受け取る
        • nがPromiseした提案のID以上ならaccept
  • Learning a Chosen Value
    • 提案が選ばれたことを確認するにはLearnerを使う
    • 過半数のacceptorに提案がacceptされたことをlearnerに確認させる
    • Distinguished learnerにacceptorが提案がacceptされたことを報告する
      • Distinguished learnerが他のlearnerに通知する

次に読むべき論文は?