Skip to content

consistency

Jump to bottom
wzs edited this page Aug 27, 2018 · 1 revision

一致性

介绍

通过CAP理论可知, 在设计一个分布式系统时, 只能满足 一致性, 可用性, 分区容忍性 的两点. 但是因为网络分区是非人为控制的, 所以设计师要在一致性和可用性之间做出抉择.

  • 建议在看一致性之前, 先了解下 cap定律和base理论, 在讨论任何分布式系统时, CAP总是核心的需求.

本文的主要内容是以下几方面

  1. 一致性有那些级别:
    • 强一致性: 任意时刻, 所有节点的数据都是相同的.
    • 弱一致性: 任意时刻, 所有节点的数据不一定都是相同的. 弱一致性有很多不同的实现, 分布式系统中常用的是最终一致性.
    • 最终一致性: 最终一致性保证两点: 保证用户最终能够读取到数据最新状态的值; 保证不同节点上的相同的数据总在趋向于变得一致.
  2. 分布式系统的一致性与其他编程领域的一致性有什么区别
    • 按照不同领域, 事务中所指的一致性与分布式系统所指的一致性又有所不同, 事务的一致性关注 事务执行的中间状态是否对外界可见, 分布式系统的一致性着重于多个节点的值保持相同. 但是, 数据库中 CAP 所指的一致性与分布式系统中的一致性基本相同.
  3. 分布式系统的一致性算法一般要解决哪些问题
    • 在分布式系统中节点通信的模型有两种: 内存共享 和 消息传递, 基于消息通信模型的分布式系统不可避免的存在以下问题: 进程 变慢/阻塞/杀死/重启, 消息可能会延迟/丢失/重复(暂时先不考虑消息被修改的情况, 既拜占庭错误), 一致性算法主要解决的问题是, 在一个可能发生上述问题的系统中, 如何就某个值达成一致, 且保证无论发生以上任何异常, 都不会破坏决议的一致性.
      • 共享内存, 既借助第三方服务器/资源, 分布式系统中的各节点都去读取该内容. 但是, 依然存在第三方服务异常的情况. 分布式系统都不会不会采用此策略.
  4. 接下来的内容都是 分布式系统的一致性算法的实现, 赶时间的同学可以直接从 分布式锁服务 开始, 个人感觉这一部分是重点. 比较闲的同学可以从基础的 Quorum系统NRW策略 开始.

Quorum系统NRW策略

NRW策略是强一致性算法, 性能较最终一致性算法的系统低.

Quorum机制, 是分布式系统中一种保证数据冗余和最终一致性的算法, 主要思想来源于 鸽巢原理

  • 鸽巢原理: 若有N个笼子和N+1只鸽子, 所有的鸽子都关在笼子里, 那么至少有一个笼子里有两个鸽子.

NRW策略, 解释如下:

  • N: 数据拥有的副本数
  • R: 完成读操作所需要读取的最小副本数. 即一次读操作所需要参与的最小节点数目.
  • W: 完成写操作所需要写入的最小副本数. 即一次写操作所需要参与的最小节点数目.

NRW策略, 就是指: 只要保证 R+W>N, 就可以保证强一致性. 即在 N 个副本中, 有 R 个更新到最新的数据, 读取任意大于 N-R 的副本, 那么至少有一个副本的数据是最新的数据(使用 版本号/时间戳等 标记数据的版本, 用于判断是否是最新的数据)

当 R+W>N 时, 那么分布式系统是 强一致性 的系统.

当 R+W<=N 时, 分布式系统是 弱一致性 的系统, 是否能实现 最终一致性 取决于系统异步更新的实现方式.

R W 可以根据系统的特点进行合理的设置, 比如一下特例

  1. W=1, R=N: 每次只需写入等待一个节点返回正常写入的回应即可, 读取时读取全部节点的数据. 适合写入操作很多, 但读取操作很少的系统. 但是若有一个节点故障, 则读操作无法完成.
  2. W=N, R=1: 与 1 相反.
  3. W=R=N/2+1: 均衡上面两个情况

两阶段提交算法

在两阶段提交协议中, 系统一般包含两类节点: 协调者(coordinator/master), 通常一个系统中只有一个; 事务参与者(participants/cohorts/workers), 一般有多个, 在数据系统中可以理解为数据副本的个数. 两阶段提交算法正常执行情况下分两步进行:

  1. 阶段一: 请求阶段. 在请求阶段, 协调者通知事务参与者准备 提交或取消事务, 然后进入表决阶段. 在表决过程中, 参与者告诉协调者自己的决策: 同意或不同意事务(同意指事务在参与者本地执行成功, 不同意指事务在本参与者本地执行失败, 如消息未到达, 如超时)(注意, 事务在本地执行失败, 是指客观因素导致的, 而不是因为数据/服务本身的问题导致的失败)
  2. 阶段二: 提交阶段. 协调者根据第一轮的投票结果进行决策, 确定 事务提交或者取消. 当且仅当所有的参与者同意提交事务, 协调者才通知所有参与者提交事务, 否则通知所有参与者取消事务. 参与者在收到协调者发送的消息后立即执行相应的操作.

示例如下: ABCD四个人准备去爬山, A作为活动的发起者, BCD作为活动的参与者. 如果所有人都同意去爬山, 那么活动准备进行, 如果有一个参与者不同意, 那么活动取消, 使用2pc算法解决流程如下

  1. 阶段一: A 告诉 BCD, 下周去爬山, 然后A等待BCD的回应. BC收到信息, 回复A同意下周去爬山, D由于网络故障等原因没有及时收到信息(通信延迟), 此时 ABC 等待 D 的回应.第二天D收到A的消息, 但是D下周有事不能去爬山(事务在本地执行失败), 所以D回应A不同意
  2. 阶段二: A 根据所有参与者的回应, 发现D拒绝了提议, 所以A通知BCD下周活动取消. BCD 收到消息后重新把下周的计划清空(回滚到之前的状态).

两阶段提交算法在分布式系统中主要用于: 单用户对多数据副本的修改, 或者多数据副本的同步:

  1. 在分布式系统中, 客户端成为系统的协调者, 各个数据节点作为系统的参与者.
  2. 阶段一: 客户端(协调者) 向所有参与者(数据节点)发送消息: 修改的数据的信息 --> 收到消息的数据节点 备份修改前的数据(以备回滚) --> 修改数据, 成功则回应客户端修改成功, 修改失败则回应客户端修改失败 --> 客户端收到数据节点成功的回应, 则回复ok, 如果是错误回应, 则回复错误, 取消修改
  3. 阶段二: 客户端根据所有的回应, 如果全部成功 则提示修改成功, 如果存在失败的回应, 那么发信息给所有数据节点 回滚数据, 取消更改

可以看出, 两阶段提交算法还有其他很多的玩法, 比如说不需要BCD全部回复成功, 只要保证部分成功即可; 或者说错误重试, 或者说可以有多个提议, 参与者根据策略选择最新的/特殊的协议更新数据. 总之, 两阶段提交算法/Quorum机制 都是一种分布式系统中保持一致性的思想. 接下来我们开始接触下目前比较常用的其他一致性算法思想.

分布式锁服务

分布式锁是指 系统外部(用户)修改系统内数据时, 要先获得 操作许可(锁), 只有获得许可的用户才能修改数据, 用户修改完数据后释放锁. 一般而言, 同一时间只能有一个用户取得 操作许可(锁), 即只有前一个用户释放锁后, 其他用户才能重新获得锁.

分布式锁算法的实现中, 可以通过控制内容颗粒度上锁. 如, 如果需要保持文件的多个副本一直, 那么对整个文件上锁; 也可以对文件分段, 只对文件的部分内容上锁.

常用的 分布式锁 实现算法有 Lamport bakery algorithm(俗称面包店算法), Paxos算法 和 乐观锁.

Lamport面包店算法

Lamport面包店算法 由 Leslie Lamport 发明, 是为了解决多个线程并发访问 单用户资源 的互斥问题, 多个线程之间共享该资源.

该算法也称为 时间戳策略, 或者 Lamport逻辑时钟.

在分布式系统中, 可以将 事件的先后关系 理解为逻辑时钟, 使用 -> 表示. 如 事件A发生在事件B之前, 那么 A->B.

事件的先后关系, 需满足以下条件

  1. 如果AB是同一进程中的事件, A在B之前发生, 那么 A->B
  2. 如果A是消息发送方, B是消息接收方, 那么 A->B
  3. 对于事件ABC, 有 A->B, B->C, 那么 A->C
  4. 对于任何事件A, A->A 是不成立的. 因为事件A是一个事件, 具有原子性.

根据如上定义(事件的先后关系), 并发(concurrent) 的概念定义如下:

  • 对于事件AB, 如果 A->B, B->A 都不成立, 那么 A和B 就是并发的.
  • 并发并不是指一定同时发生, 而是表示事件先后关系的不确定性. 也可以理解为 可以并发的事件 之间没有依赖.

逻辑时钟, 本质上是指一个事件到实数(假设时间是连续的)的函数, 该函数将 一个事件映射到一个实数, 表示该事件发生的时间. 举例而言, 就是: 对于 进程Pi, 时钟为Ci, 对于 进程Pi 中的 事件a, Ci将A映射到Ci(a). 整个系统的时钟中, 对于 进程Pi 中的 事件b, C(b)==Ci(b).

  • 注意, 这里的映射是单射.(待验证)
  • 如果事件在进程 pi pj 中并发发生, 即 Ci(a)==Cj(a') 且 i<j, 那么 a 在 a' 前.

逻辑时钟的设置规则如下

  1. 如果是 进程Pi 内的任何两个连续事件, 那么Ci值递增
  2. 如果事件a是Pi发送消息m, 事件b是Pj接收消息m, 那么 Ci(a)<Cj(b)

面包店算法/时间戳策略/逻辑时钟 其实很简单, 类似与我们去吃饭时的排号策略, 每个顾客都去前台领取一个号码, 然后按照号码顺序(时间戳/逻辑时钟)依次进桌(获取操作 共享资源 的权限).

  • 如果两个顾客有相同的号码, 则年龄较小的具有优先权; 在系统中即进程ID较小的具有优先权.
  • 在逻辑时钟策略中, 我们更多的是去了解在分布式系统中 先后事件的关系, 以及分布式系统中的并发概念. 逻辑时钟与分布式系统结合, 就可以实现分布式锁

接下来开始学习 Paxos算法. 据说, 目前所有已实现系统中的算法, 不是Paxos,就是Paxos算法的变种. 其中, Raft算法是zookeper中采用的算法, 也是Paxos算法的变种.

Paxos算法

参考 Paxos算法-维基百科

由于还没有使用过, 所以目前只是了解/熟悉. 等某一天, 真正用到, 或者准备好好研究(深入研究 zookeper 或者类似的事情时), 再来好好地完善 我们重点讲下 Paxos算法.

Paxos算法是 Leslie Lamport 于1990年提出的一种基于消息传递且具有高度容错性的一致性算法, Paxos 算法的主要思想是 两阶段提交算法的改良和分布式锁(逻辑时钟或者说时间戳策略)的结合.

首先, 大概了解下 Paxos算法 的提出,证明(建议先简单看下,留下印象, 然后在看算法内容和示例时验证, 最后在复习下 Paxos算法的证明)

  1. Paxos算法中, 将参与角色分为三类: proposers,acceptors,learners
    • proposers: 提议者, 或者说master, 负责提出议案, 议案包括议案编号和议案内容(最终需要的值)
    • acceptors: 参与者, 参与者收到议案后可以接受议案, 弱议案获取半数以上参与者的同意则形成决议.
    • learners: learners 只能获得被批准议案的内容.
  2. 只要保证 在一次 Paxos算法中, 只批准一个议案, 就可以保证分布式系统中的一致性. 要保证每次 Paxos算法 只批准一个议案, 那么需要以下约束
    • 一个参与者必须接受第一次收到的议案
    • 一旦 提议A 成为决议, 那么之后批准的决议必须有决议 A.
      • 原因: 为了在多个议案之间建立全序关系, 既保证之后的议案都有更大的序号
    • 一旦 提议A 成为决议, 那么之后参与者接受的议案中必须有 议案A 的值v.
    • 一旦 提议A 成为决议, 那么之后提议者发起的议案中必须有 议案A 的值v.
    • 重点 如果 议案N 具有 值v, 那么存在一个多数派, 要么他们中所有人都没有接受编号小于 N 的议案, 要么他们已经接受的所有 编号小于议案N的议案 中, 编号最大的那个议案具有 v.
      • 证明不再讨论, 详见维基百科.(等用到再去详细理解)

Paxos算法 的内容/流程

  1. 阶段一: prepare 阶段
    • 提议者A(master) 生成/选择一个 预提交议案, 编号为n, 然后通知所有已知的参与者该议案
    • 参与者收到 预提交议案,
      • 如果参与者没有已经接受的议案, 那么参与者接受该议案作为当前议案, 并回复提议者.
      • 如果议案编号小于该参与者之前已经回复的 预提交议案m, 参与者不回复.
      • 如果议案编号大于该参与者之前已经回复的 预提交议案m, 那么参与者将自己上次接受的 预提交议案m 回复给提议者A, 并且承诺不再回复小于 n 的预提交议案.
  2. 批准阶段: 当有一个提议者B 与大多数参与者对 预提交议案 有过通信后, 就可以进入批准阶段, 此时提议者B 向 所有回复B prepare请求(既预提交议案)的参与者发送 appect请求, 包括编号和议案内容(既需要更改的实际值),
    • 如果参与者大多数都回复同意 B 的议案或者大多数参与者还没有接受过议案, 那么该议案成为决议
    • 如果部分参与者异常/被强占,导致 B 未收到半数以上的回应, 那么提议者B 结束批准阶段, 重新向参与者发送消息, 申请沟通权.
    • 如果提议者B 收到参与者不同的答复
      • 如果半数以上参与者已经同意了某个议案C, 那么议案C 就是决议, 提议者B回复遵守该议案.
      • 如果没有半数以上参与者做出同样的决定, 如参与者12同意议案A', 参与者3同意议案B', 参与者4同意议案C', 那么提议者 B 表示遵守 A' B' C' 中最新的那个议案.

以上只是一个小介绍, 由于Paxos算法的理解和证明确实比较复杂, 我们再通过一个例子加深下理解

假设, 有一群驴友相约去旅游, 驴友之间通过短信 点对点 联系(既使用消息模型). 条件如下

  1. 假设共有驴友25人, 根据 Paxos算法, 选出5个人作为队长(注意, 本例子中队长是参与者), 其余驴友作为提议者. 一位队长同一时间只能跟一位驴友联系.
  2. 其他条件
    • 队长任意时间只能跟一位驴友通信, 且队长总是于与最新的驴友沟通
    • 假设队长/队友之间通过短信联系, 且每一条信息都有时间戳.
    • 至少有半数以上的队长同意了, 才可以进入 阶段二(批准阶段)

从驴友的角度看, 流程如下

  1. 阶段一:准备阶段 驴友向队长发送消息, 有以下三种回复情况
    • 短信时间戳太早, 队长拒绝沟通
    • 短信时间戳是队长收到的最新的, 队长同意和你沟通, 并且回复自己(此队长)决定的旅游地点, 或者告诉驴友自己还没有决定.
    • 同一时间只能与一位驴友通信, 所以不可能出现时间戳相同的.
  2. 阶段二:批准阶段 当有半数以上的队长同意过与某个驴友通信, 进入阶段二, 假设该驴友是 A.
    • 跟 A 沟通的队长们(半数以上)都没有决定旅游地点(既 A 的消息是队长们第一次收到的, 或者 A 的消息是队长们收到的最新的), A 给队长们发消息, 告诉他们自己提议的旅游地点 V(a)
      • 半数以上队长同意了, 那么最终形成的决议就是去 V(a). 当队长再收到其他驴友的消息时, 队长回复决议内容 V(a)
      • 部分队长异常/被其他驴友强占, 既 A 没有收到半数以上队长的同意. 此时 A结束批准阶段, 回到准备阶段.
    • 至少有一个队长决定去哪了, A 收到不同队长决定的多个决议,
      • 如果存在某旅游地点 b 被半数以上队长同意, 那么 V(b) 就是最终决议, A 遵从此决议, 也同意去b
      • 如果不存在半数队长以上同意的旅游地点, 如 队长1同意去三亚, 队长2/3同意去云南, 队长四同意去北京, 队长5无回应. 那么驴友 A 同意最新的决定, 既所有队长做出的决议中, 那格式最新的, A 就同意那个.

Raft算法

暂时不去深入学习了. 抽空再来

引用

Clone this wiki locally