1. 介绍

紧接第一部分引出的paxos算法。本节开始对paxos算法做一些解释。

2. paxos简介

2.1 什么是paxos

2.2 paxos的几种分类

  1. classic paxos: 1个实例(确定1个值)写入需要2轮2RPC
  2. multi paxos: 约为1轮RPC,确定1个值(第一次RPC做了合并)
  3. Fast Paxos: 没冲突:1轮RPC确定一个值 有冲突:2轮RPC确定一个值

2.3 paxos的执行条件

  1. 存储必须是可靠的:没有数据丢失和错误(否则需要用Byzantine Paxos)
  2. 容忍:消息丢失(节点不可达)、消息乱序

2.4 基本术语

  • Proposer: 发起paxos的进程
  • Acceptor: 存储节点,接受、处理和存储消息
  • Quorum(Acceptor的多数派):n/2+1个Acceptors集合
  • Round:1轮包含2个阶段:Phase-1和Phase-2
  • rnd(每一轮的编号):单调递增;后写胜出;全局唯一(用于区分proposer)
  • last_rnd(Acceptor看到的最大rnd): Acceptor记住这个值来识别哪个proposer可以写
  • Value(v): Acceptor接受的值
  • Value round number(vrnd): Acceptor接受的v的时候的rnd

值“被确定”的定义:有多数(多于半数)个Acceptor接受了这个值

3. classic paxos

3.1 阶段1

3.2 阶段2

未完待续