paxos

2019-05-30

本文是看了视频后,关键页面的笔记记录.

paxos算法用于解决分布式系统中的一致性问题.

算法描述

paxos是一个投票决议的世界. 在这个世界中,一共有三种角色:Proposer,Acceptor,Learner. Proposer负责提出带有编号和值的提案. Acceptor负责接收提案. Learner负责学习提案.
提案决议的过程分为两个阶段:

PREPARE阶段
- 提出PREPARE 请求
  - Proposer 提出一个只带编号的提案,不能带有值,只能有编号
  - 多个Proposer 提的编号不能相同.
  - 如果一个request超时,那么就用一个更大的id
- Acceptor 接收到一个ID为P的PREPARE请求
  - 是否答应忽略ID为P的PREPARE请求?
    - 是,那就忽略
    - 否, 那就会保证忽略任何ID小于P的请求, 且是否曾经接受过提议?
      - 是, 将之前的提议的值+ID P的Promise再传给Proposer
      - 否, 仅将ID P的Promise传给Proposer
ACCEPT阶段
- Proposer 接收到一个ID为P的Promise请求
  - 是否接收超过半数的Promise请求
    - 是, 那是否这个Promise带有Value
      - 是,发送这个ID p以及Promise中的Value的ACCEPT-REQUEST给proposer
      - 否,任意选取一个Value,发送ID为P的ACCEPT-REQUEST给所有proposer
    - 否, 忽略
- Acceptor接收到一个ID为P的ACCEPT-REQUEST, 是否保证忽略这个为P的ID(有可能答应过更大的ID)
  - 是, 忽略
  - 否, 回复IDP和Value给所有的Leaners

争议的情况,两个Proposer产生了争议,可能导致整个过程无法进行下去. 解决办法是采用二进制退避算. 当Proposer2 收到Promise 8的时候, Promise 1会去等待一段时间,好让Proposer2 完成ACCEPT-REQUEST.

任何一个ID小于5的Request,都将不会被大多数者所接受
任何一个ID大于5的但携带有不同值的Request,将不会被大多数者所接受, 因为被接受的值将会被piggyback回去. 及时learner没有及时接收到value, 就算发起一个新的请求, 返回的值也是之前已经达成一致的Value

实际应用: 每一个log position都是一轮paxos协商过程

缺失模块。
1、请确保node版本大于6.2
2、在博客根目录（注意不是yilia根目录）执行以下命令：
npm i hexo-generator-json-content --save

3、在根目录_config.yml里添加配置：

  jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

杭州-51信用卡