ikemonn's blog

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

Paxos Made Live - An Engineering Perspective を読んだ

Paxos Made Live - An Engineering Perspectiveを読んだ時のメモ。

どんなもの?

  • Paxosを実際のプロダクト(Chubby)で使用するために行った挑戦とその際に選択したアルゴリズムについて
    • Paxosは論文には1ページの擬似コードで説明されているが、実プロダクトで使うには数千行かかった(C++)
    • 論文では書かれていた耐障害性アルゴリズムは慎重に選択された一部の障害にしか耐えられなかった
      • 実世界ではアルゴリズム自体のエラーやオペレーターのエラー等が起こる

先行研究とくらべて何がすごい?

  • Paxosを実装し、Chubbyに組み込んだこと
    • 実プロダクトで使う際に、論文の内容だけでは足りなかったので下記を実装した
      • Handling disk corruption
      • Master leases
      • Epoch numbers
      • Group membership
      • Snapshots
      • Data transaction

技術や手法の肝は?

f:id:ikemonn:20170721152452p:plain

  • Architecture outline
    • Fault-tolerant replicated Log
      • 全てのレプリカは同一順序のエントリーをローカルログに持っている
    • Fault-tolerant DB
      • 下記から成る
        • local snapshot
        • DBの操作に関するreploy-log
      • Chubbyが自分の状態を保存するのにも使う
  • Paxos Basics

    • 3つのフェーズがある
        1. coordinatorとなるreplicaを選択する
        1. coordinatorは値を選択し、acceptメッセージで全てのreplicaにbroadcastする
        1. replicaの過半数がcoordinatorをacknowledgeしたら同意に至る
        2. coordinatorはreplicaに知らせるためにcommitメッセージをbroadcastする
        3. 一度過半数のreplicaがack messageを受け取って、ackしたら同意が成立する
          • たとえすべての少数派のreplicaがfailしても、少なくとも1つのreplicaには同意された値が届いている
    • 現実ではcoordinatorもfailするかもしれない
      • Paxosではcoordinatorは一度に1つとは言っていない
        • 複数のreplicaがcoordinatorとなるようにした
        • 複数のcoordinatorがそれぞれ別の値を選ぶかもしれない
      • Paxosは2つの追加のメカニズムを導入することで1つの値で同意に到れるようにした
          - 1. succesive coordinatorの順番を決める
              - 前回と今回のcoordinatorを区別する
                  - propose/promise messageで番号を送っているのでそれで区別
          - 2. 値を選択する時に、coordinatorが取れる選択肢を制限する
              - promise messageに直近acceptした値を入れて返す
        
  • Algorithmic challenges

    • Handling disk corruption
      • メディアの障害やオペレーターエラーによってdiskが破損する可能性がある
        • diskが壊れて永続的な状態を失うと、過去に他のreplicaが行ったpromiseを再実行する可能性がある
      • diskの破損の2パターン
        • ファイルの内容の変更された - チェックサムをいれる
        • ファイルにアクセスできなくなった
          • 空のdiskを持つ新しいreplicaと区別がつかない
          • 新しいreplica起動時にGFSにマーカーを残すことで検出する
            • replicaが空のdiskから再開されると検出される
      • 破損したdiskを持つreplicaの再構築
        • non-votingメンバーとしてPaxosに参加する
          • 最新の状態に追いつくためにcatch-up メカニズムを使用するが、promise/acknowlegement メッセージには反応しない
          • replicaが再構築されたと観測されるまでこの状態
        • まだこれは実装されていない
    • Master leases

      • 基本的なPaxosアルゴリズムを使ってreplicated data構造を実装する場合に古いデータを読み込む可能性がある
        • 他のレプリカが別のマスターを選択肢、古いマスターに通知すること無くデータ構造が変わった場合
      • master leaseを実装してこの問題を回避する
        • masterにleaseがある限り、他のレプリカがPaxosに値を正常に送信できないことが保証される
        • leaseを持つmasterがlocal dataに構造に最新の情報を持ち、localでの読み取り操作を行うことが出来る
          • leaseの期限切れになるまでに、マスターが更新しようとするので一度に数日間くらいleaseを持つ
      • まだ実装されていない
    • Epoch numbers

      • master replicaがrequestを受けてから、DBを更新するまでにマスターステータスを失う可能性がある
        • Chubbyは管理権が失われたり、再獲得されるとrequestの受付を中止する必要がある
      • グローバルエポックnumberを導入した
        • 2つのrepuestの間に連続してそのレプリカがmasterだったら、同じ値を受け取る
        • DBのエントリとして保存され、DBの操作はエポック番号の値を条件とする
    • Group membership
      • 現実のシステムでは一連のreplicaの変更を処理する必要がある
        • group membership
      • 文献には書かれていないし、アルゴリズムの正当性も証明されてない
      • 実システムでは必要なので実装した
    • Snapshots
      • 同意アルゴリズムを使っていくと、replicatited logが増えていく
      • ログが増えていくと2つの問題が起こる
        • disk spaceを無限に使う
        • 無限の復旧時間がかかる
      • snapshotをとるようにする
        • Paxosフレームワーク自体はデータ構造については、何も知らされていないためアプリケーション側がsnapshotを作成する
        • アプリケーションが任意のタイミングでshapshotをとり、Paxosに通知するとそれ以前のログを削除するようにした
    • Database transactions
      • ChubbyでのDB要件はkey-valueのペアを保存できて、一般的なDB操作(insert, delete, lookup, an atomic compare and swap)ができることだった
      • DB全体のsnapshotをとるのとsnapshotに適用したDB操作のログ(Paxos)に使えるように設計した
      • 定期的にDBの状態をsnapshotにとり、それに応じてログを削除する

どうやって有効と検証した?

f:id:ikemonn:20170721152511p:plain

  • 元々使われていた3DBと、自分たちで実装したDBを使用したChubbyのパフォーマンスを測定して比較した
    • 全体的にPaxosを利用した方がパフォーマンスが良い
  • replicated log sizeが100MBを超えるとsnapshotをとるように設定されており、そこでdiskに書き込むのでパフォーマンスが一時的に低下した
    • この部分の最適化の余地があるが、3DBよりはパフォーマンスが出ているので手を付けなかった

議論はある?

  • まだまだ最適化の余地がある
    • snapshot等
  • Paxosアルゴリズムの説明と実システムでのニーズには大きなギャップがある
  • The fault-tolerance computing communityはアルゴリズムの実装を容易にするツールを開発していない
  • The fault-tolerance computing communityは耐障害性システムを構築するために重要な要素であるテストに十分な注意を払っていない

次に読むべき論文は?

In Search of an Understandable Consensus Algorithm(Extended Version)